智能控制系統(tǒng)五自然計算及群體智能

智能控制系統(tǒng)五自然計算及群體智能1第1頁，共52頁，2023年，2月20日，星期五創(chuàng)新：向大自然學(xué)習(xí)生物體、自然生態(tài)系統(tǒng)通過自身演化解決優(yōu)化問題模擬自然生態(tài)系統(tǒng)求解復(fù)雜優(yōu)化問題仿生優(yōu)化算法遺傳算法蟻群算法微粒群算法人工免疫算法人工魚群算法混合蛙跳算法2第2頁，共52頁，2023年，2月20日，星期五遺傳算法(GA)物競天擇，設(shè)計染色體編碼，交配突變與適應(yīng)函數(shù)的萃取，優(yōu)化求解神經(jīng)網(wǎng)絡(luò)(ANN)模彷生物神經(jīng)元，透過神經(jīng)元的訊息傳遞、訓(xùn)練學(xué)習(xí)、回溯，優(yōu)化求解模擬退火演算法(SA)模彷金屬退火過程基因表達式編程3第3頁，共52頁，2023年，2月20日，星期五基因DNA4第4頁，共52頁，2023年，2月20日，星期五5第5頁，共52頁，2023年，2月20日，星期五神經(jīng)網(wǎng)絡(luò)6第6頁，共52頁，2023年，2月20日，星期五7第7頁，共52頁，2023年，2月20日，星期五昆蟲蟻，蜂8第8頁，共52頁，2023年，2月20日，星期五9第9頁，共52頁，2023年，2月20日，星期五蟻群算法AntColonyOptimization(ACO)10第10頁，共52頁，2023年，2月20日，星期五鳥群算法ParticleSwarmOptimization有個帶頭鳥11第11頁，共52頁，2023年，2月20日，星期五魚群算法FishSwarmOptimization12第12頁，共52頁，2023年，2月20日，星期五蜂群算法

MarriageinHoneyBeesOptimization(MBO)13第13頁，共52頁，2023年，2月20日，星期五禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡(luò)（neuralnetworks）蟻群算法（群體（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangean）蜜蜂算法飛姿傳信，圈軸方向：蜜向，飛行圈數(shù)：距離14第14頁，共52頁，2023年，2月20日，星期五被模擬對象的智能層次昆蟲（低智能）蜜蜂、螞蟻——蜂群算法，蟻群算法脊椎動物門（較低智能）魚群、鳥群——魚群算法，鳥群算法，PSO遺傳算法家族（模擬生物界基本性質(zhì)，中智能）

GA,GP

GEP基因表達式編程

GEP–變異和雜交=PSO15第15頁，共52頁，2023年，2月20日，星期五AI上這一特殊分支的發(fā)展歷史GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1953SimulatedAnnealing模擬退火16第16頁，共52頁，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence198919691969ExpertSystem專家系統(tǒng)AI上這一特殊分支的發(fā)展歷史17第17頁，共52頁，2023年，2月20日，星期五TabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1975

遺傳算法GeneticAlgorithmAI上這一特殊分支的發(fā)展歷史18第18頁，共52頁，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1989SwarmIntelligence群體智能TabuSearchAI上這一特殊分支的發(fā)展歷史19第19頁，共52頁，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1991SwarmIntelligence蟻群算法AntsSystemAI上這一特殊分支的發(fā)展歷史20第20頁，共52頁，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystem199519891969ExpertSystem1995ParticleSwarmOptimization粒子群優(yōu)化算法AI上這一特殊分支的發(fā)展歷史21第21頁，共52頁，2023年，2月20日，星期五出版社：人民郵電出版社作者：[美]JamesKennedy/RussellC.Eberhart/YuhuiShi/2009年2月第1版第1次印刷22第22頁，共52頁，2023年，2月20日，星期五幾本相關(guān)的中文書23第23頁，共52頁，2023年，2月20日，星期五蟻群優(yōu)化算法AntColonyAlgorithm(ACA)24第24頁，共52頁，2023年，2月20日，星期五參考文獻APPEAREDINPROCEEDINGSOFECAL91-EUROPEANCONFERENCEONARTIFICIALLIFE,PARIS,FRANCE,ELSEVIERPUBLISHING,134–142.DistributedOptimizationbyAntColoniesAlbertoColorni,MarcoDorigo,VittorioManiezzoDipartimentodiElettronica,PolitecnicodiMilanoPiazzaLeonardodaVinci32,20133Milano,ItalyIEEETransactionsonSystems,Man,AndCybernetics-PartB:Cybernetics,Vol.26,No.1,Feb1996.29-41AntSystem:OptimizationbyaColonyofCooperatingAgentsMarcoDorigo,Member,IEEE,VittorioManiezzo,andAlbertoColornihttp://iridia.ulb.ac.be/~mdorigo/HomePageDorigo/25第25頁，共52頁，2023年，2月20日，星期五對螞蟻的觀察單只螞蟻智能不高;沒有集中的指揮無所作為蟻群，復(fù)雜的社會行為：協(xié)同工作筑巢、覓食、遷徙、清掃蟻巢、撫養(yǎng)后代依靠群體能力發(fā)揮出超出個體的智能26第26頁，共52頁，2023年，2月20日，星期五蟻群算法特點模擬螞蟻群體智能行為的仿生優(yōu)化算法較強的魯棒性優(yōu)良的分布式計算機制易于與其它方法結(jié)合27第27頁，共52頁，2023年，2月20日，星期五螞蟻的生物學(xué)特征別稱：玄駒、蚍蜉、狀元子屬節(jié)肢動物門，昆蟲綱，膜翅目，蟻科

在昆蟲界種類最多，生存量最大約260屬，16000多種，已命名的9000多種拖動1400自重的食物舉起自重400倍的物體起源于1億年前的恐龍時代28第28頁，共52頁，2023年，2月20日，星期五螞蟻的社會形態(tài)蟻后、雄蟻、工蟻、兵蟻信息交流方式：化學(xué)通信分泌化學(xué)刺激物：信息素(pheromone)彼此平等，利他主義個體協(xié)作，協(xié)調(diào)一致共和國29第29頁，共52頁，2023年，2月20日，星期五螞蟻的群體行為螞蟻個體簡單群體：高度機構(gòu)化的社會組織遠(yuǎn)超螞蟻個體能力行為1：覓食食物隨機散布找到一條蟻巢到食物源的最佳路徑適應(yīng)環(huán)境變化：出現(xiàn)障礙方法：蟻過留素（雁過留聲），聞素而跟信息正反饋30第30頁，共52頁，2023年，2月20日，星期五良性循環(huán)：路好（有食且近）蟻多信息素多蟻多…..（隨時會蒸發(fā)掉一部分），開始：信息素濃度路短素濃。31第31頁，共52頁，2023年，2月20日，星期五良性循環(huán)如何進行？符號和假定：路徑上的信息素濃度記為X螞蟻均勻釋放信息素，dx/dt=常數(shù)蟻穴A，食物源C，路徑1：AC，路徑2：ABC等邊三角形ABC找到食物，沿原路返回BAC32第32頁，共52頁，2023年，2月20日，星期五良性循環(huán)如何進行？螞蟻M1：AC，螞蟻M2：ABC

找到食物（分布、并行），沿原路返回AC比ABC短，M1回到A點時，M2才到C點。AC上蟻氣：兩次信息素疊加（去-回）AB路只有去一次信息素X(AC)>X(ABC)，下一只螞蟻：選擇路徑ACAC上信息素越來越多，進入良性循環(huán)BAC33第33頁，共52頁，2023年，2月20日，星期五Fig.1.Anexamplewithrealantsa)AntsfollowapathbetweenpointsAandE.b)Anobstacleisinterposed;antscanchoosetogoarounditfollowingoneofthetwodifferentpathswithequalprobability.c)Ontheshorterpathmorepheromoneislaiddown.34第34頁，共52頁，2023年，2月20日，星期五Fig.2.Anexamplewithartificialantsa)Theinitialgraphwithdistances.b)Attimet=0thereisnotrailonthegraphedges;therefore,antschoosewhethertoturnrightorleftwithequalprobability.c)Attimet=1trailisstrongeronshorteredges,whicharetherefore,intheaverage,preferredbyants.35第35頁，共52頁，2023年，2月20日，星期五要點螞蟻群居群動，很少有獨行俠，選擇信息素濃的路徑，喜歡熱鬧，追求蟻氣（人氣）人也類似。

兩家飯店，一家熱熱火火，一家門可羅雀，選哪家？選登山旅游線，一般人選人氣多的（信息素濃的）信息素啟發(fā)性知識：人氣高的，自有其優(yōu)點飯店請名人寫詩歌作畫、寫對聯(lián)，留下信息素商業(yè)”托”,假造信息素優(yōu)勢：并行+分布+信息素70%選紅火的，不一定每人是這樣稱為按概率.0.7選紅火的36第36頁，共52頁，2023年，2月20日，星期五雙橋?qū)嶒?GossS,1989)Naturwissenschaften76,579-581(1989)Self-organizedShortcutsintheArgentineAntS.Goss,S.Aron,J.L.Deneubourg,andJ.M.PasteelsUnitofBehaviouralEcology,C.P.231,Universit6LibredeBruxelles,B-1050Bruxelles37第37頁，共52頁，2023年，2月20日，星期五Fig.1.AcolonyofIhumilisselectingtheshortbranchesonbothmodulesofthebridgea)onemoduleofthebridgeb)andc):photostaken4and8minafterplacementofthebridge38第38頁，共52頁，2023年，2月20日，星期五雙橋?qū)嶒灁?shù)學(xué)模型假設(shè)條件：1、非對稱橋上的信息量與過去一個時間段內(nèi)經(jīng)過該橋的螞蟻數(shù)目成正比；2、某一時刻螞蟻按照橋上殘留的信息量多少來選擇其中某座橋3、經(jīng)過該橋的螞蟻數(shù)目越多則橋上的殘留信息量就越大設(shè)短橋為A，長橋為B，mA和mB分別表示經(jīng)過橋A和橋B的螞蟻數(shù)目

mA+mB=m當(dāng)所有m只螞蟻都經(jīng)過兩座橋之后，第m+1只螞蟻選擇橋A的概率為：而選擇橋B的概率為：39第39頁，共52頁，2023年，2月20日，星期五參數(shù)h和k用以匹配真實實驗數(shù)據(jù)第m+1只螞蟻首先計算然后生成一個在區(qū)間[0,1]上均勻分布的隨機數(shù)若，則選擇橋A，否則選擇橋B40第40頁，共52頁，2023年，2月20日，星期五發(fā)展意大利學(xué)者MDorigo，Vmaniezzo和AColorni20世紀(jì)90年代：螞蟻系統(tǒng)（antsystem，AS）求解旅行商問題（TravelingSalesmanProblem，簡稱TSP）90年代中期，用于廣泛領(lǐng)域，取得成果MDorigo發(fā)展為優(yōu)化技術(shù)-蟻群優(yōu)化（AntColonyOptimization，簡稱ACO）WJGutjahr：ACO的收斂性用于合優(yōu)化，函數(shù)優(yōu)化、系統(tǒng)辨識、機器人路徑規(guī)劃、數(shù)據(jù)挖掘、網(wǎng)絡(luò)路由41第41頁，共52頁，2023年，2月20日，星期五ACO國際研討會ACO國際研討會

1998、2000年、2002年、2004年，2006年，比利時布魯塞爾大學(xué)42第42頁，共52頁，2023年，2月20日，星期五基本蟻群算法的數(shù)學(xué)模型43第43頁，共52頁，2023年，2月20日，星期五P、NP、NP-C、NP-hard問題P類問題所有可用DTM(Deterministicone-tapeTuringMachine)在多項式時間內(nèi)求解的判定問題Π的集合。簡記為O(p(n))即P={L:存在一個多項式時間DTM程序M，是的L=LM},其中LM表示程序M所識別的語言。若存在一個多項式時間DTM程序，它在編碼策略e之下求解判定問題Π，即L[Π,e]∈P,則稱該判定問題屬于P類問題。44第44頁，共52頁，2023年，2月20日，星期五P、NP、NP-C、NP-hard問題NP類問題(Non-deterministicPolynomial)若存在一個多項式函數(shù)g(x)和一個驗證算法H,對一類判定問題A的任何一個“是”回答，滿足其輸入長度d(s)不超過g(d(I)),其中d(I)為I的輸入長度，且驗證算法中S為I的“是”回答的計算時間不超過g(d(I)),則稱判定問題A為非多項式確定問題。NP類問題是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多項式時間內(nèi)求解的判定問題Π的集合45第45頁，共52頁，2023年，2月20日，星期五P、NP、NP-C、NP-hard問題NP-C類問題(NP-Complete)是NP類中最困難的一類問題。有重要實際意義和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard類問題NP-CNP-hardNPPNP-hardNP-C46第46頁，共52頁，2023年，2月20日，星期五基本蟻群算法模型基本假設(shè)螞蟻之間通過信息素和環(huán)境進行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對周圍的局部環(huán)境產(chǎn)生影響；螞蟻對環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。即螞蟻是反應(yīng)型適應(yīng)性主體在個體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨立選擇；在群體水平上，單只螞蟻的行為是隨機的，但蟻群可通過自組織過程形成高度有序的群體行為。47第47頁，共52頁，2023年，2月20日，星期五TSP(TravelingSalesmanProblem)有向圖有向圖D的三元組為(V,E,f)，其中V是一個非空集合，其元素稱為有向圖的結(jié)點；E是一個集合，其元素稱為有向圖的弧段（邊）；f是從E到VxV上的一個映射（函數(shù)）。E中的元素總是和V中的序偶對有對應(yīng)關(guān)系，可用V中的序偶代替E中的元素。一個有向圖Ｄ可簡記為(V,E).48第48頁，共52頁，2023年，2月20日，星期五TSP(TravelingSalesmanProblem)TSP設(shè)C={c