《人工智能控制技術(shù)》 課件 chap6-進化算法

《人工智能控制技術(shù)》進化算法進化算法概述智能控制或智能方法研究的最終目標(biāo)之一是制造出具有人腦功能(如識別、學(xué)習(xí)、推理、綜合、分析、判斷和決策等)的機器，諸如學(xué)習(xí)機、智能計算機、智能機器人等。目前已經(jīng)比較實用化的智能方法主要有兩類:一是基于“符號和邏輯”的傳統(tǒng)人工智能派；二是基于“連接主義”神經(jīng)網(wǎng)絡(luò)理論派。這些方法的核心都是利用優(yōu)化技術(shù)來解決實際的問題。一般說來，在控制系統(tǒng)的建模與辨識、各類控制系統(tǒng)的設(shè)計（從簡單的PID調(diào)節(jié)器設(shè)計到復(fù)雜的離散事件系統(tǒng)設(shè)計）、高級控制算法的實現(xiàn)（如自適應(yīng)控制、魯棒控制、容錯控制、學(xué)習(xí)控制等）都需要優(yōu)化技術(shù)。進化算法概述遺傳學(xué)習(xí)算法是當(dāng)今隨機優(yōu)化理論中相當(dāng)活躍的一個分支。它與其他一些進化算法一起構(gòu)成了隨機搜索優(yōu)化的新理論。應(yīng)用廣泛的進化算法還有粒子群算法、蟻群算法等。粒子群算法是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機搜索算法，通常認(rèn)為它是群集智能的一種，它可以被納入多主體優(yōu)化系統(tǒng)。蟻群算法是由意大利學(xué)者多里戈（Dorigo）、馬涅佐（Maniezzo）等人于20世紀(jì)90年代首先提出來的。他們在研究螞蟻覓食的過程中，發(fā)現(xiàn)單個螞蟻的行為比較簡單，但是蟻群整體卻可以體現(xiàn)一些智能的行為。例如蟻群可以在不同的環(huán)境下，尋找最短到達食物源的路徑。這是因為蟻群內(nèi)的螞蟻可以通過某種信息機制實現(xiàn)信息的傳遞。后又經(jīng)進一步研究發(fā)現(xiàn)，螞蟻會在其經(jīng)過的路徑上釋放一種可以稱之為“信息素”的物質(zhì)，蟻群內(nèi)的螞蟻對“信息素”具有感知能力，它們會沿著“信息素”濃度較高路徑行走，而每只路過的螞蟻都會在路上留下“信息素”，這就形成一種類似正反饋的機制，這樣經(jīng)過一段時間后，整個蟻群就會沿著最短路徑到達食物源了。進化算法概述遺傳算法是建立在自然選擇和自然遺傳學(xué)機理基礎(chǔ)上的迭代自適應(yīng)隨機搜索算法,其基本思想是由美國密歇根大學(xué)霍蘭德（Holland）教授在1967年首先提出來的,并在1970年用計算機程序模擬了進化過程。遺傳學(xué)習(xí)算法的正式確立是以1975年霍蘭德教授出版的專著《AdaptioninNaturalArtificialSystem》為標(biāo)志。遺傳學(xué)習(xí)算法是通過機器來模仿生物界自然選擇機制的一種方法。它涉及高維空間的優(yōu)化搜索,雖然它的解并不一定是最優(yōu)的,但肯定是一個優(yōu)良的解。此后，大量新的進化算法被提出，如差分進化算法、模擬退火算法、進化策略、進化規(guī)劃、人工免疫算法等，這些算法的共同點都是從現(xiàn)有存在或自然界的事物出發(fā)，觀察其規(guī)律和內(nèi)在機理，根據(jù)觀察到的規(guī)律設(shè)計算法模擬自然界的過程，達到優(yōu)化計算的目的。遺傳算法等進化算法的優(yōu)點在于算法簡單、魯棒性強，而且大部分無需知道搜索空間的先驗知識。它同神經(jīng)元網(wǎng)絡(luò)優(yōu)化模型一樣表現(xiàn)為強大的并行處理性能。因此，它們的執(zhí)行時間與優(yōu)化系統(tǒng)的規(guī)模是一種線性關(guān)系，而不會隨著系統(tǒng)復(fù)雜程度增加帶來計算量猛增的現(xiàn)象。一旦進化算法在某一領(lǐng)域應(yīng)用成熟，也可利用大規(guī)模集成電路芯片來實現(xiàn)。遺傳算法遺傳算法的發(fā)展歷史1962年,霍蘭德的學(xué)生巴格利（Bagley）在博士論文中首次提出“遺傳算法”一詞。此后，霍蘭德指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1971年，霍爾斯泰因（Hollstien）在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。1975霍蘭德出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》，這是第一本系統(tǒng)論述遺傳算法的專著，霍蘭德在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。同年，德容（K.A.DeJong）完成了他的博士論文《一類遺傳自適應(yīng)系統(tǒng)的行為分析》該論文所做的研究工作，他把霍蘭德的模式理論與他的計算實驗結(jié)合起來。1985年，在美國召開了第一屆遺傳算法國際會議，并且成立國際遺傳算法學(xué)會，以后每兩年舉行一次。遺傳算法的發(fā)展歷史1989年，霍蘭德的學(xué)生戈德堡（D.E.Goldberg）出版了專著《搜索、優(yōu)化和機器學(xué)習(xí)中的遺傳算法》。該書總結(jié)了遺傳算法研究的主要成果，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。同年，美國斯坦福大學(xué)的科扎（Koza）基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機程序來表達問題的遺傳程序設(shè)計方法，成功地解決了許多問題。1991年，戴維斯（L.Davis）編輯出版了《遺傳算法手冊》，其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實例。1994年，科扎又出版了《遺傳程序設(shè)計，第二冊:可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設(shè)計的研究，使程序設(shè)計自動化展現(xiàn)了新局面。越來越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中。進入20世紀(jì)90年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴大，而且利用遺傳算法進行遺傳算法的發(fā)展歷史1991年瓦提（D.Whitey）在他的論文中提出了基于領(lǐng)域交叉的交叉算子，這個算子是特別針對用序號表示基因的個體的交叉，并將其應(yīng)用到了旅行商（TSP）問題中。阿克利（D.H.Ackley）等提出了隨機迭代遺傳爬山法采用了一種復(fù)雜的概率選舉機制，此機制中由m個“投票者”來共同決定新個體的值(m表示群體的大小)。該方法與單點交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能。貝爾尼尼（H.Bersini）和斯旺特（G.Seront）將遺傳算法與單一方法結(jié)合起來，形成了一種叫單一操作的多親交叉算子，2002年，戴曉明等應(yīng)用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題。2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法。2005年，江雷等針對并行遺傳算法求解TSP問題，探討了使用彈性策略來維持群體的多樣性，使得算法跨過局部收斂的障礙，向全局最優(yōu)解方向進化。遺傳算法的發(fā)展歷史隨著應(yīng)用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺傳算法的機器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學(xué)習(xí)算法。這一新的學(xué)習(xí)機制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓21世紀(jì)中新的智能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍，這不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用。五是遺傳算法和進化規(guī)劃以及進化策略等進化計算理論日益結(jié)合。進化規(guī)劃和進化策略幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點。遺傳算法的基本原理遺傳算法的提出是從生物界的進化理論中得到啟發(fā)。在自然界，優(yōu)秀的品種個體能夠在貧乏的環(huán)境下生存。對環(huán)境的適應(yīng)能力是每一物種生存的本能。表征各自個體的獨特性決定了它本身的生存能力，而這些特性是由其個體的遺傳碼決定的。確切地講，每一特性是由基因控制的?？刂苽€體特性的基因集就是染色體，它是在競爭環(huán)境中個體生存的關(guān)鍵因素。進化的驅(qū)動力在于自然選擇和繁殖以及它們重組的聯(lián)合作用。在有限的資源如食物、空間等條件下，每一物種為了生存只有進行競爭，其結(jié)果是適應(yīng)能力強的個體優(yōu)于弱者。也只有那些適應(yīng)能力強的個體得到生存和繁殖，這種自然現(xiàn)象就是自然界的“適者生存"規(guī)律。因此,強者的基因生存下來，弱者的基因漸漸消亡，自然選擇就是適者生存。繁殖過程使得基因呈現(xiàn)多樣性。進化是從父輩中的遺傳物質(zhì)（染色體）在繁殖中的重新組合時開始的。新的基因組合是從父母輩基因中繁殖下來的。這一過程又稱為“交叉”。交叉運算的本質(zhì)是將兩個父母輩的基因的某一段進行交換，以便通過可能的正確結(jié)合產(chǎn)生更優(yōu)秀的下一代。不斷地進行自然選擇和交叉運算使得基因鏈不斷地進化最終產(chǎn)生更好的個體。遺傳算法的基本原理遺傳算法的實質(zhì)是通過操作一組最優(yōu)化問題潛在解的全體來實現(xiàn)的，即通過問題解的編碼操作來尋優(yōu)，而這種編碼正等同于自然界物種的基因鏈。每一個體都與反映自身適應(yīng)能力相對強弱的“適應(yīng)度”相聯(lián)系。較高“適應(yīng)度”的個體具有較大的生存和繁殖機會，以及在下一代中占有更大的份額。在遺傳算法中染色體的重組是通過對兩個父母輩編碼串之間相互交換這樣一個“交叉"機制來實現(xiàn)的。遺傳算法的另一個重要算子“變異”通過隨機地改變編碼串中的某一位達到下一代能夠呈現(xiàn)一定的分散性。從優(yōu)化的角度來分析，“變異”的作用在于能夠?qū)崿F(xiàn)全局優(yōu)化，避免陷入局部極小值。遺傳算法的基本原理遺傳算法是根據(jù)生物界的遺傳和自然選擇的原理來實現(xiàn)的，它的學(xué)習(xí)過程是通過保持和修改群體解中的個體特性，并且保證這種修改能夠使下一代的群體中有利于與期望特性相近的個體在整個群體份額中占有的比例越來越多。同自然選擇一樣，這一過程是概率收斂的，它并不完全是隨機的。遺傳算法中的遺傳規(guī)則要求使那些與期望特性相近的個體具有迅速繁殖的最大概率。遺傳算法是通過連續(xù)不斷地對群體進行改進來搜索函數(shù)的最大值的，要注意這一搜索過程與搜索最優(yōu)群體的概念是不一樣的。此外，遺傳算法搜索的結(jié)果會有很大的差異。遺傳學(xué)習(xí)的基本機理是使那些優(yōu)于群體中其他個體的個體具有生存、繁殖以及保持更多基因給下一代的機會。因此，遺傳算法實質(zhì)上是在群體空間中尋求較優(yōu)解。遺產(chǎn)算法基本步驟霍蘭德教授在遺傳學(xué)的基礎(chǔ)上利用計算機來模擬生物的進化過程，從而實現(xiàn)復(fù)雜問題的優(yōu)化求解。他提出對由染色體(即由0或1組成的二進制串)構(gòu)成的種群進行操作，并利用一些簡單的編碼、選擇、繁殖等機制解決了一些極端復(fù)雜的問題。遺傳學(xué)習(xí)算法可以歸結(jié)為以下幾個步驟：1.群體的初始化；2.評價群體中每一個體的性能；3.選擇下一代個體；4.執(zhí)行簡單的操作算子(如交叉、變異)；5.評價下一代群體的性能；6判斷終止條件滿足否？若不，則轉(zhuǎn)(3)

繼續(xù)；若滿足，則結(jié)束。遺傳算法需要解決的問題1.編碼機制；2.選擇機制；3.控制參數(shù)選擇；4.二進制字符串的群體構(gòu)成；5.適應(yīng)度函數(shù)的計算；6.遺傳算子(交叉、變異)的定義遺傳算法的基本原理1.編碼機制遺傳算法的基礎(chǔ)是編碼機制，編碼解決的問題就是如何將最優(yōu)化問題中的變量用某種編碼方式構(gòu)成一種遺傳規(guī)則能夠運算的字符串。編碼規(guī)則與待求問題的自然特性相關(guān)，例如在解決道路的最佳流量控制時,不同道路的流量變量是一個連續(xù)變量,因此需要對連續(xù)變量進行編碼。而在解決旅行商最優(yōu)路徑時可以用二進制數(shù)來表示，因而可以直接用二進制編碼來實現(xiàn)問題的求解。但不管是何種編碼方式，編碼規(guī)則必須滿足每一個解對應(yīng)于唯一的一個二進制字符串編碼。絕大多數(shù)最優(yōu)化問題處理的都是實值連續(xù)變量，常用的編碼是使用整數(shù)表示，即每一個變量首先經(jīng)線性變換，轉(zhuǎn)換到某一給定范圍內(nèi)的整數(shù)，然后用固定長度的二進制進行編碼，并將所有變量的二進制編碼合并成一個二進制字符串。例如，對于定義在-1.28到1.28之間的連續(xù)變量的編碼可以簡單地對變量值乘以一個實數(shù)100，并舍棄其小數(shù)部分得到相應(yīng)的二進制整數(shù)。這樣，連續(xù)變量可以通過線性變換，轉(zhuǎn)換到一個整數(shù)區(qū)間[-128,128]。遺傳算法的基本原理染色體的結(jié)構(gòu)選擇問題，即參數(shù)的排序，它也是影響遺傳學(xué)習(xí)算法收斂性的重要因素。由于群體的繁殖是通過遺傳學(xué)習(xí)算子來進行的，而這些算子的操作是針對所有參數(shù)的，尤其是交叉算子，它是將父母輩字符串(染色體)的某一點上斷裂后通過相互交換其中一部分而產(chǎn)生下一代。因此在這個算子的運算過程中隱含著排序相近的基因?qū)⒃谙乱淮斜３窒聛?，而相距較遠(yuǎn)的基因?qū)①x予不同的子代。這一特點希望我們盡量將一些相關(guān)性較強的參數(shù)基因排在一起。但遺憾的是在實際系統(tǒng)中哪些參數(shù)相關(guān)性強事先難以確定。遺傳算法的基本原理2.適應(yīng)度函數(shù)任何一個優(yōu)化問題都是與一定的目標(biāo)函數(shù)相聯(lián)系的，遺傳算法也不例外。目標(biāo)函數(shù)是用來評價每一個字符串個體性能的指標(biāo)。然而它的值域變化范圍會隨待求問題的不同而有很大的差異。為了使得遺傳算法與待求問題的本身無關(guān)且便于遺傳優(yōu)化的計算，人們引人了一個新的指標(biāo)函數(shù)，即“適應(yīng)度值”。它的大小反應(yīng)了群體中個體性能的優(yōu)劣，它的值域范圍為[0,1]?！斑m應(yīng)度值”的計算直接通過將目標(biāo)函數(shù)經(jīng)一定的線性變換映射到[0,1]區(qū)間內(nèi)的一個值，這一過程又稱為目標(biāo)函數(shù)的正規(guī)化過程。遺傳算法的選擇機制就是通過評價“適應(yīng)度值”來進行的。遺傳算法的基本原理

遺傳算法的基本原理轉(zhuǎn)輪選擇法的具體計算方法可以描述為：隨機產(chǎn)生一個0~2π之間的數(shù)，一旦落入某一個個體扇區(qū)時，則此個體被選中作為下一代的一個個體。一直繼續(xù)下去，直至下一代群體內(nèi)的所有個體都被選擇出來。在這里應(yīng)注意到，適應(yīng)度值越大的個體，它占有扇區(qū)的面積也越大，被隨機選中的概率也越大。因此從概率角度來分析轉(zhuǎn)輪選擇法滿足“優(yōu)勝劣汰”自然法則。但是必須指出的是，由于隨機性的存在，不可避免地會產(chǎn)生與比例選擇法的基本選擇法則有差異，即有些個體可能并沒有得到它應(yīng)該擁有的f_i/f?個個體的數(shù)目。但是這一現(xiàn)象在群體規(guī)模比較大時不重要，群體規(guī)模越大，這種情況出現(xiàn)的可能性越小。因此,遺傳算法屬于隨機搜索方法，具有概率收斂性。規(guī)模越大，呈現(xiàn)的概率性越正確，學(xué)習(xí)算法也就越完善。遺傳算法的基本原理

遺傳算法的基本原理

遺傳算法實例

遺傳算法實例

遺傳算法實例

遺傳算法實例

遺傳算法實例

遺傳算法實例

遺傳算法實例目標(biāo)函數(shù)J的優(yōu)化過程目標(biāo)函數(shù)J和適應(yīng)函數(shù)F的優(yōu)化過程粒子群算法粒子群算法粒子群算法是對鳥群飛行覓食行為的研究，此算法基于群體迭代，使鳥群中的所有個體在解空間中追隨最優(yōu)個體進行搜索，通過集體協(xié)作方式達到最優(yōu)，是近些年來迅速發(fā)展的一種進化算法。粒子群算法源于對鳥群捕食行為研究，是一種基于迭代的優(yōu)化工具。從隨機解出發(fā)，通過迭代來尋找最優(yōu)解并用適應(yīng)度的概念對解的品質(zhì)進行評價。粒子群中的每個粒子都代表問題的一個可能解，通過粒子個體的行為，實現(xiàn)群體內(nèi)的信息交互，體現(xiàn)出問題求解的智能性。粒子群算法的發(fā)展歷史粒子群算法源于對鳥群捕食行為研究，是一種基于迭代的優(yōu)化工具。從隨機解出發(fā)，通過迭代來尋找最優(yōu)解并用適應(yīng)度的概念對解的品質(zhì)進行評價。粒子群中的每個粒子都代表問題的一個可能解，通過粒子個體的行為，實現(xiàn)群體內(nèi)的信息交互，體現(xiàn)出問題求解的智能性。粒子群（PSO）算法實現(xiàn)方便，收斂速度較快，參數(shù)設(shè)置相對較少且無需梯度信息，是一種高效的搜索算法，目前已經(jīng)被廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)的訓(xùn)練等領(lǐng)域。算法提出以后，很快受到重視，但是粒子群算法中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應(yīng)，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象。同時，粒子群算法的性能也依賴于算法參數(shù)。為了克服上述不足，各國研究人員相繼提出了各種改進措施。主要有四類：粒子群初始化、鄰域拓?fù)洹?shù)選擇和混合策略。粒子群算法的發(fā)展歷史根據(jù)粒子鄰域是否為整個群體，粒子群算法可以分為全局模型gbest和局部模型lbest。對于全局模型，每個粒子與整個群體的其他粒子進行信息交換，并有向所有粒子中的歷史最佳位置移動的趨勢。肯尼指出，全局模型雖然具有較快的收斂速度，但更容易陷入局部極值。為了克服全局模型的缺點，研究人員采用每個粒子僅在一定的鄰域內(nèi)進行信息交換，提出各種局部模型。性能空間指根據(jù)性能指標(biāo)(如適應(yīng)度、目標(biāo)函數(shù)值)劃分的鄰域。研究最多的方法是按粒子存儲陣列的索引編號進行劃分，主要有：環(huán)形拓?fù)?、輪形拓?fù)浠蛐切瓮負(fù)?、塔形拓?fù)?、馮.諾以曼拓?fù)湟约半S機拓?fù)涞?。針對不同的?yōu)化問題，這些拓?fù)涞男阅鼙憩F(xiàn)各異；但總的來說，隨機拓?fù)渫鶎Υ蠖鄶?shù)問題能表現(xiàn)出較好的性能，混合PSO就是將其它進化算法或傳統(tǒng)優(yōu)化算法或其它技術(shù)應(yīng)用到粒子群算法中，用于提高粒子多樣性、增強粒子的全局探索能力，或者提高局部開發(fā)能力、增強收斂速度與精度。這種結(jié)合的途徑通常有兩種：一是利用其它優(yōu)化技術(shù)自適應(yīng)調(diào)整收縮因子/慣性權(quán)值、加速常數(shù)等；二是將粒子群算法與其它進化算法操作算子或其它技術(shù)結(jié)合。粒子群算法的發(fā)展歷史粒子群算法，也叫粒子群優(yōu)化算法1995年由美國電氣工程師艾伯哈特（Eberhart）和社會心理學(xué)家肯尼（Kenney）提出。理查德（Richard）和文圖拉（Ventura）提出了基于質(zhì)心結(jié)構(gòu)(CVTs)的種群初始化方法；薛明志等人采用正交設(shè)計方法對種群進行初始化；坎帕納（Campana）將標(biāo)準(zhǔn)粒子群迭代公式改寫成線性動態(tài)系統(tǒng)；蘇格汗（Suganthan）引入一個時變的歐式空間鄰域算子克萊爾（Clere）對隨機拓?fù)溥M行研究并運用到粒子群算法為了初始種群盡可能均勻覆蓋整個搜索空間，提高全局搜索能力，理查德（Richard）和文圖拉（Ventura）提出了基于質(zhì)心結(jié)構(gòu)(CVTs)的種群初始化方法；薛明志等人采用正交設(shè)計方法對種群進行初始化；坎帕納（Campana）將標(biāo)準(zhǔn)粒子群迭代公式改寫成線性動態(tài)系統(tǒng)，并基于此研究粒子群的初始位置，使它們具有正交的運動軌跡，都從不同方面改進了粒子群算法。蘇格汗（Suganthan）引入一個時變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴展到整個種群。粒子群算法的發(fā)展歷史克萊爾（Clere）對隨機拓?fù)溥M行了進一步分析，并在2006年版和2007年版的標(biāo)準(zhǔn)粒子群算法中采用了隨機拓?fù)洹Ａ_賓遜（Robinson）和莊振益將遺傳算法與粒子群算法結(jié)合分別用于天線優(yōu)化設(shè)計和遞歸神經(jīng)網(wǎng)絡(luò)設(shè)計；納卡（Naka）將遺傳算法中的選擇操作引入到粒子群算法中，按一定選擇率復(fù)制較優(yōu)個體；安吉麗（Angeline）則將錦標(biāo)賽選擇引入粒子群算法，根據(jù)個體當(dāng)前位置的適應(yīng)度，將每一個個體與其它若干個個體相比較，然后依據(jù)比較結(jié)果對整個群體進行排序，用粒子群中最好一半的當(dāng)前位置和速度替換最差一半的位置和速度，同時保留每個個體所記憶的個體最好位置；米蘭達（Miranda）使用了變異、選擇和繁殖多種操作同時自適應(yīng)確定速度更新公式中的鄰域最佳位置以及慣性權(quán)值和加速常數(shù)。其他學(xué)者對粒子群做了其他有益的改進，所有這些改進都極大的推動了粒子群算法的發(fā)展。粒子群算法的基本原理受到鳥類群體行為的啟發(fā)，肯尼和艾爾伯特利用生物學(xué)家赫珀（Hepper）的模型提出了粒子群算法。在赫珀模型當(dāng)中，所有鳥類在一塊棲息地附近聚群，他們知道棲息地中有一處食物，但只知道自身距離食物的相對位置，不明確食物的具體位置。因此，為了找到食物，所有鳥類需要搜索距離食物最近鳥類的周圍區(qū)域。在粒子群算法中，每個鳥類個體用一個無質(zhì)量的粒子來表示，其適應(yīng)值由被優(yōu)化的函數(shù)所決定；每個粒子具有速度和位置兩個參數(shù)，分別表示鳥類個體飛行的快慢和方向。粒子會單獨地在解空間內(nèi)不斷搜尋最優(yōu)解，并將目前搜索到的局部最優(yōu)解與其他粒子共享，稱作個體極值；整個種群目前搜尋到的最優(yōu)解稱作全局極值。所有粒子會根據(jù)這兩個極值來不斷更新自己的速度和位置，向目標(biāo)不斷靠近。粒子群算法的基本原理在粒子群算法中，每個鳥類個體用一個無質(zhì)量的粒子來表示，其適應(yīng)值由被優(yōu)化的函數(shù)所決定；每個粒子具有速度和位置兩個參數(shù)，分別表示鳥類個體飛行的快慢和方向。粒子會單獨地在解空間內(nèi)不斷搜尋最優(yōu)解，并將目前搜索到的局部最優(yōu)解與其他粒子共享，稱作個體極值；整個種群目前搜尋到的最優(yōu)解稱作全局極值。所有粒子會根據(jù)這兩個極值來不斷更新自己的速度和位置，向目標(biāo)不斷靠近。需要調(diào)整的參數(shù)

粒子群算法的發(fā)展歷史

粒子群算法具體流程粒子群算法實例

粒子群算法實例

粒子群算法實例

優(yōu)化結(jié)果粒子群算法具體流程

優(yōu)化結(jié)果蟻群群算法蟻群算法蟻群算法(AntColonyOptimization,ACO)是一種模擬自然界當(dāng)中蟻群覓食行為的模擬進化算法，由多里戈等人提出，后被應(yīng)用到了解決旅行商問題（TSP）上。這種算法具有分布計算、信息正反饋和啟發(fā)式搜索的特征，在本質(zhì)上是一種新型優(yōu)化算法，目前已經(jīng)在大規(guī)模集成電路設(shè)計問題、通訊網(wǎng)絡(luò)中的路由問題等取得了一定成就，同時作為一種全局搜索算法，可以有效地避免局部最優(yōu)問題。蟻群算法的發(fā)展歷史昆蟲學(xué)家通過對蟻群覓食規(guī)律的研究，發(fā)現(xiàn)螞蟻可以在沒有任何提示地情況下找到從蟻穴到食物源的最短路徑，并且能夠根據(jù)環(huán)境狀態(tài)的改變來搜索新路徑。在往返于蟻穴和食物源地過程中，螞蟻可以在路徑上分泌一種稱作信息素的化學(xué)物質(zhì)，當(dāng)一條路徑上通過的螞蟻數(shù)量越來越多時，他們會留下更多的信息素軌跡，使信息素的強度增大，導(dǎo)致后來者更有可能選擇該路徑，形成了一種正反饋機制，最后將整個蟻群聚集到最短路徑上。受蟻群覓食行為的啟發(fā)，意大利學(xué)者多里戈在1991年首次提出了一種基于螞蟻種群的新型優(yōu)化算法—蟻群算法，并將其應(yīng)用到了實際的優(yōu)化問題當(dāng)中。蟻群算法最初用于解決旅行商問題。對于蟻群算法而言，在明確基本原理的情況下，應(yīng)將研究重點放在算法模型的開發(fā)上，在實際應(yīng)用中，要對模型的收斂性和算法的復(fù)雜性重點把握。蟻群算法為自組織算法，采用并行和正反饋機制，這是不同于其他仿生優(yōu)化算法的最重要特點。蟻群算法的原理在蟻群算法當(dāng)中，每只螞蟻都會從初始狀態(tài)出發(fā)，經(jīng)過有限步移動后建立一個符合問題的可行解，它們之間通過信息素這種化學(xué)物質(zhì)進行交流，以相互協(xié)作的方式，不斷對目標(biāo)問題的較優(yōu)解進行搜索，最終找到高質(zhì)量解。在螞蟻的內(nèi)部，存儲了其過去的相關(guān)信息，例如在TSP問題當(dāng)中，會給每只螞蟻設(shè)置一個禁忌表，用于記錄螞蟻走過的城市，同時