進(jìn)化算法簡(jiǎn)析

1、*粒子粒子群算法群算法*人工魚群人工魚群算法算法*蟻群算法蟻群算法*差分進(jìn)化算法差分進(jìn)化算法*粒子群算法粒子群算法起源起源*粒子群算法粒子群算法原理原理*粒子群算法粒子群算法流程流程*粒子群算法粒子群算法特點(diǎn)特點(diǎn) 粒子群算法，又稱粒子群優(yōu)化算法（Partical Swarm Optimization），縮寫為 PSO，是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化算法，由Eberhart 博士和kennedy 博士于1995年提出，其源于對(duì)鳥群捕食的行為研究。PSO同遺傳算法類似，是一種基于迭代的優(yōu)化算法。系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)值。但是它沒有遺傳算法用的交叉(crossover)以及變異(m

2、utation)，而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。Particle Swarm Optimization James Kennedy Russell C. Eberhart FoodGlobal Best SolutionPast Best Solution PSO算法不像遺傳算法那樣對(duì)個(gè)體進(jìn)行選擇、交叉和變異操作，而是將群體中的每個(gè)個(gè)體視為多維搜索空間中的一個(gè)沒有質(zhì)量和體積的粒子（點(diǎn)），粒子在搜索空間中以一定的速度飛行，并根據(jù)粒子本身的飛行經(jīng)驗(yàn)及同伴的飛行經(jīng)驗(yàn)對(duì)自己的飛行速度進(jìn)行動(dòng)態(tài)調(diào)整，即每個(gè)粒子通過統(tǒng)計(jì)迭代過程中自身的最優(yōu)值和群體的最優(yōu)值來(lái)不斷修正自己的前進(jìn)方向和速度大小，從而形

3、成群體尋優(yōu)的正反饋機(jī)制。PSO算法就是這樣依據(jù)每個(gè)粒子對(duì)環(huán)境的適應(yīng)度將個(gè)體逐步移到較優(yōu)的區(qū)域,并最終搜索、尋找到問題的最優(yōu)解。1. 隨機(jī)初始化粒子群體的位置和速度。通常是在允許的范圍內(nèi)隨機(jī)產(chǎn)生的,每個(gè)粒子的pbest坐標(biāo)設(shè)置為其當(dāng)前位置,且計(jì)算出其相應(yīng)的個(gè)體極值(即個(gè)體的適應(yīng)度值),而全局極值(即全局的適應(yīng)度值)就是個(gè)體極值中最好的,記錄該最好值的粒子序號(hào),并將gbest設(shè)置為該最好粒子的當(dāng)前位置。2. 計(jì)算每個(gè)粒子的適應(yīng)值。3. 對(duì)每個(gè)粒子,將其適應(yīng)值與個(gè)體極值進(jìn)行比較,如果較優(yōu),則更新當(dāng)前的個(gè)體極值。4. 對(duì)每個(gè)粒子,將其適應(yīng)值與全局極值進(jìn)行比較,如果較優(yōu),則更新當(dāng)前的全局極值。5. 根據(jù)

4、式(1)、(2),更新每個(gè)粒子的位置和飛行速度。6. 如未達(dá)到預(yù)先設(shè)定的停止準(zhǔn)則(通常設(shè)置為最大迭代次數(shù)),則返回步驟2,若達(dá)到則停止計(jì)算。優(yōu)點(diǎn)：優(yōu)點(diǎn)：*算法規(guī)則簡(jiǎn)單，容易實(shí)現(xiàn)，在工程應(yīng)用中比較廣。*收斂速度快，且有很多措施可以避免陷入局部最優(yōu)。*可調(diào)參數(shù)少，且對(duì)于參數(shù)的選擇已有成熟的理論研究成果。缺點(diǎn)：缺點(diǎn)： 容易產(chǎn)生早熟收斂（尤其是在處理復(fù)雜的多峰搜索問題中）、局部尋優(yōu)能力較差等。*人工魚群算法起源人工魚群算法起源*人工魚群算法人工魚群算法原理原理*人工魚群算法人工魚群算法流程流程*人工魚群算法特點(diǎn)人工魚群算法特點(diǎn)*算法算法全局收斂的基礎(chǔ)全局收斂的基礎(chǔ)行為描述行為描述行為選擇行為選擇算法描

5、述算法描述 人工魚群算法(Artificial Fish-Swarm Algorithm，AFSA)是一種基于模擬魚群行為的優(yōu)化算法，是由李曉磊等在2002年提出的一種新型的尋優(yōu)算法。在基本AFSA中，主要是利用了魚群的覓食、聚群和追尾行為，從構(gòu)造單條魚的底層行為做起，通過魚群中各個(gè)體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來(lái)的目的。李曉磊，邵之江，錢積新一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法系統(tǒng)工程理論與實(shí)踐行為選擇行為選擇 根據(jù)所要解決的問題性質(zhì)，對(duì)人工魚當(dāng)前所處的環(huán)境進(jìn)行評(píng)價(jià)，從而選擇一種行為。如較常用的評(píng)價(jià)方法就是選擇各行為中使得向最優(yōu)方向前進(jìn)最大的行為，也就是各行為中使得人工魚的下一

6、個(gè)狀態(tài)最優(yōu)的行為，如果沒有能使下一狀態(tài)優(yōu)于當(dāng)前狀態(tài)的行為，則采取隨機(jī)行為算法算法描述描述 鑒于以上描述的人工魚行為，每個(gè)人工魚探索它當(dāng)前所處的環(huán)境狀況和伙伴的狀況，其實(shí)伙伴的狀況相對(duì)于其自身應(yīng)該也是歸屬于環(huán)境的狀況，從而選擇一種行為，最終，人工魚集結(jié)在幾個(gè)局部極值的周圍。一般情況下，在討論求極大問題時(shí)，擁有較大的AF-food consistence值的人工魚一般處于值較大的極值域周圍，這有助于獲取全局極值域，而值較大的極值區(qū)域周圍一般能集結(jié)較多的人工魚，這有助于判斷并獲取全局極值。算法全局收斂的基礎(chǔ)算法全局收斂的基礎(chǔ)*1.覓食行為中try-number的次數(shù)較少時(shí)，為人工魚提供了隨機(jī)游動(dòng)的機(jī)

7、會(huì)，從而能跳出局部極值的鄰域；*2.隨機(jī)步長(zhǎng)的采用，使得在前往局部極值的途中，有可能轉(zhuǎn)而游向全局極值，當(dāng)然其相反的一面也會(huì)發(fā)生的，就是在去往全局極值的途中，可能轉(zhuǎn)而游向局部極值，這對(duì)一個(gè)個(gè)體當(dāng)然不好判定它的禍福，但對(duì)于一個(gè)群體來(lái)說(shuō)，好的一面往往會(huì)具有更大的機(jī)率；*3.擁擠度因子的引入限制了聚群的規(guī)模，只有較優(yōu)的地方才能聚集更多的人工魚，使得人工魚能夠更廣泛的尋優(yōu)*4.聚群行為能夠促使少數(shù)陷于局部極值的人工魚向多數(shù)趨向全局極值的人工魚方向聚集，從而逃離局部極值；*5.追尾行為加快了人工魚向更優(yōu)狀態(tài)的游動(dòng)，同時(shí)也能促使陷于局部極值的人工魚向趨向全局極值的更優(yōu)人工魚方向的追隨而逃離局部極值域優(yōu)點(diǎn)優(yōu)點(diǎn)

8、：*并行性：多個(gè)AF并行的進(jìn)行搜索；*簡(jiǎn)單性：算法中僅使用了目標(biāo)問題的函數(shù)值；*全局性：算法具有良好的跳出局部極值的能力；*快速性：算法中雖然有一定的隨機(jī)因素，但總體是在步步向最優(yōu)化搜索；*跟蹤性：隨著工作狀況或其他因素的變更造成的極點(diǎn)的漂移，具有快速跟蹤變化的能力。缺點(diǎn)缺點(diǎn)：*當(dāng)尋優(yōu)的區(qū)域較大，或處于變化平坦的區(qū)域時(shí)，收斂到全局最優(yōu)解的速度變慢，搜索效率劣化。*算法一般在優(yōu)化初期具有較快的收斂性，而后期卻往往收斂較慢。*隨著人工魚數(shù)目的增多，將會(huì)需求更多的存儲(chǔ)空間，也會(huì)造成計(jì)算量的增長(zhǎng)。*蟻群算法蟻群算法起源起源*蟻群算法蟻群算法原理原理*蟻群算法蟻群算法流程流程*蟻群算法蟻群算法特點(diǎn)特點(diǎn)

9、20世紀(jì)90年代意大利學(xué)者M(jìn)Dorigo等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題，取得了較好的試驗(yàn)結(jié)果。雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法。Macro Dorigo The Ant System:Optimization by a colony of cooperating agents 為了說(shuō)明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體

10、過程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口。就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激索濃度越低.當(dāng)后來(lái)的螞蟻再次碰到這個(gè)路口的時(shí)，選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來(lái)越大而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。 大量螞蟻組成的蟻群的集體行為實(shí)際上就構(gòu)成了一種信息正反饋現(xiàn)象:某一路徑上走過的螞蟻越多,則后來(lái)者選擇該路徑的概率就越大。該算法的本質(zhì)在于:1. 選擇機(jī)

11、制,信息素越多的路徑,被選擇的概率越大；2. 更新機(jī)制,路徑上面的信息素會(huì)隨螞蟻的經(jīng)過而增長(zhǎng),而且同時(shí)也隨時(shí)間的推移逐漸揮發(fā)消失;3. 協(xié)調(diào)機(jī)制,螞蟻之間實(shí)際上是通過信息素來(lái)相互通信協(xié)同工作。優(yōu)點(diǎn)：優(yōu)點(diǎn)：*蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性（對(duì)基本蟻群算法模型稍加修改，便可以應(yīng)用于其他問題）和搜索較好解的能力。*蟻群算法是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。*蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。缺點(diǎn)缺點(diǎn)：*如果參數(shù) 設(shè)置不當(dāng)，導(dǎo)致求解速度很慢且所得解的質(zhì)量特別差。*基本蟻群算法計(jì)算量大，求解所需時(shí)間較長(zhǎng)。*基本蟻群算法中理論上要求所有

12、的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路；但在實(shí)際計(jì)算中，在給定一定循環(huán)數(shù)的條件下很難達(dá)到這種情況。*差分進(jìn)化算法差分進(jìn)化算法起源起源*差分差分進(jìn)化算法原理進(jìn)化算法原理*差分進(jìn)化算法差分進(jìn)化算法流程流程*差分進(jìn)化算法差分進(jìn)化算法特點(diǎn)特點(diǎn)變異操作變異操作交叉操作交叉操作選擇操作選擇操作 差分進(jìn)化（Differential Evolution, DE）算法是由 Rainer Storn 和 Kenneth Price 為求解切比雪夫多項(xiàng)式而于 1996 年共同提出的一種采用浮點(diǎn)矢量編碼在連續(xù)空間中進(jìn)行隨機(jī)搜索的優(yōu)化算法。Differential Evolution A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces優(yōu)點(diǎn)：優(yōu)點(diǎn)：*算法通用，不依賴于問題信息；*算法原理簡(jiǎn)單，容易實(shí)現(xiàn)；*群體搜索，具有記憶個(gè)體最優(yōu)解的能力；*協(xié)同搜索，具有利用個(gè)體局部信息和群體全局信息指導(dǎo)算法進(jìn)一步搜索的能力；*易于與其他算法混合，構(gòu)造