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

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

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

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

遺傳算法的基本原理

遺傳算法實(shí)例

遺傳算法實(shí)例

遺傳算法實(shí)例

遺傳算法實(shí)例

遺傳算法實(shí)例

遺傳算法實(shí)例

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

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

粒子群算法具體流程粒子群算法實(shí)例

粒子群算法實(shí)例

粒子群算法實(shí)例

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

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