AI人工智能的幾種常用算法概念備課講稿

1、AI 人工智能的幾種常用算法概念一、粒子群算法粒子群算法，也稱粒子群優(yōu)化算法（ Particle Swarm Optimization ），縮寫為 PSO ， 是近年來發(fā)展起來的一種新的進化算法 (（ Evolu2tionary Algorithm - EA ）。 PSO 算法屬于進化算法的一種，和遺傳算法相似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應度來評價解的品質(zhì)，但它比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的交叉 (Crossover) 和變異 (Mutation) 操作，它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術(shù)界的重視

2、，并且在解決實際問題中展示了其優(yōu)越性。優(yōu)化問題是工業(yè)設(shè)計中經(jīng)常遇到的問題 ,許多問題最后都可以歸結(jié)為優(yōu)化問題 .為了解決各種各樣的優(yōu)化問題 ,人們提出了許多優(yōu)化算法 ,比較著名的有爬山法、遺傳算法等 .優(yōu)化問題有兩個主要問題 :一是要求尋找全局最小點 ,二是要求有較高的收斂速度 .爬山法精度較高 ,但是易于陷入局部極小 .遺傳算法屬于進化算法 (EvolutionaryAlgorithms) 的一種 ,它通過模仿自然界的選擇與遺傳的機理來尋找最優(yōu)解 .遺傳算法有三個基本算子 :選擇、交叉和變異 .但是遺傳算法的編程實現(xiàn)比較復雜 ,首先需要對問題進行編碼 ,找到最優(yōu)解之后還需要對問題進行解碼 ,

3、另外三個算子的實現(xiàn)也有許多參數(shù) ,如交叉率和變異率 ,并且這些參數(shù)的選擇嚴重影響解的品質(zhì) ,而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗 .1995 年 Eberhart 博士和 kennedy 博士提出了一種新的算法 ;粒子群優(yōu)化 (ParticalSwarmOptimization-PSO) 算法 .這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術(shù)界的重視 ,并且在解決實際問題中展示了其優(yōu)越性.粒子群優(yōu)化 (ParticalSwarmOptimization-PSO) 算法是近年來發(fā)展起來的一種新的進化算法 (Evolu2tionaryAlgorithm-EA).PSO 算法屬于進化算法的一種

4、 ,和遺傳算法相似 ,它也是從隨機解出發(fā) ,通過迭代尋找最優(yōu)解 ,它也是通過適應度來評價解的品質(zhì) .但是它比遺傳算法規(guī)則更為簡單,它沒有遺傳算法的交叉 (Crossover)和變異 (Mutation) 操作 .它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)二、遺傳算法遺傳算法是計算數(shù)學中用于解決最佳化的，是進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。遺傳算法通常實現(xiàn)方式為一種模擬。對于一個最優(yōu)化問題，一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。傳統(tǒng)上，解用表示（即 0 和 1 的串），但也可以用

5、其他表示方法。進化從完全隨機個體的種群開始，之后一代一代發(fā)生。在每一代中，整個種群的適應度被評價，從當前種群中隨機地選擇多個個體（基于它們的適應度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當前種群。主要特點遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。的共同特征為： 首先組成一組候選解 依據(jù)某些適應性條件測算這些候選解的適應度 根據(jù)適應度保留某些候選解，放棄其他候選解 對保留的候選解進行某些操作，生成新的候選解。在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合

6、方式將遺傳算法與其它搜索算法區(qū)別開來。遺傳算法還具有以下幾方面的特點：(1)遺傳算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。(2)遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化。(3)遺傳算法基本上不用搜索空間的知識或其他輔助信息，而僅用適應度函數(shù)值來評估個體，在此基礎(chǔ)上進行遺傳操作。適應度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點使得遺傳算法的應用范圍大

7、大擴展。(4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導他的搜索方向。(5)具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，適應度大的個體具有較高的生存概率，并獲得更適應的基因結(jié)構(gòu)。三、貪婪算法概念：貪婪算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪算法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪算法常以當前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況。例如平時購物找錢時，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值

8、的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪算法。這種方法在這里總是最優(yōu)，是因為銀行對其發(fā)行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為 1、5 和 11 單位的硬幣，而希望找回總額為 15 單位的硬幣。按貪婪算法，應找 1 個 11 單位面值的硬幣和 4 個 1 單位面值的硬幣，共找回 5 個硬幣。但最優(yōu)的解應是 3 個 5 單位面值的硬幣。四、蟻群算法蟻群算法 (ant colony optimization, ACO) ，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型技術(shù)。它由 Marco Dorigo 于 1992 年在他的博士論文中引入，其靈

9、感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。自然界的種群相當廣泛 ,但大部分都有以下的能力 : 螞蟻們總能找到食物源和螞蟻窩之間的最短路徑 . 一旦這條最短路徑被發(fā)現(xiàn) , 螞蟻們就能在這條路上排成一行 , 在食物源和螞蟻窩之間搬運食物 . 螞蟻們是怎么做到的呢 ?我們知道 ,2 點間直線距離最短 . 但螞蟻們顯然不具備這樣的視力和智慧 . 它們無法從遠處看到食物源 , 也無法計劃一個合適的路徑來搬運食物 . 螞蟻們采用的方法是全體在老窩的周圍區(qū)域進行地毯式搜索 .而他們之間的是通過分泌化學物質(zhì)在爬過的路徑上 ,這種化學物質(zhì)叫 (Pheromone).螞蟻們習慣選擇信息素濃度高的路徑. 下面的圖

10、解釋了螞蟻們的工作原理.剛開始離開窩的時候 , 螞蟻們有兩條路徑選擇 : R1 和 R2. 這兩者機會相當 . 螞蟻們在爬過 R1 和 R2 的時候都留下了信息素 . 但是 , 由于 R2 的距離短 , 所需要的時間就少 , 而信息素會揮發(fā) , 所以螞蟻們留在 R2 上的信息素濃度就高 . 于是 ,越來越多的螞蟻選擇 R2 作為最佳路徑 , 即使它們是從 R1來到食物源 ,也將選擇R2返回螞蟻窩 . 而從老巢里出發(fā)的螞蟻們也越來越傾向于R2. 在這樣的趨勢下 ,R1漸漸變的無人問津了根據(jù)螞蟻們選擇路徑的方法而得到的啟發(fā), Dr. Dorigo 在 1991 年發(fā)表了 (Antalgorithm). 十多年來 , 螞蟻算法 ,以及各種改進過的螞蟻算法