AAI51自然計(jì)算及群體智能

高級(jí)人工智能章人工智能概述第二章歸結(jié)推理方法第三章不確定性推理第四章知識(shí)表達(dá)方法第五章自然計(jì)算及群體智能－蟻群算法第六章自然計(jì)算及群體智能－遺傳算法1AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!自然計(jì)算與群體智能趙林亮計(jì)算機(jī)應(yīng)用技術(shù)研究所zhaoll@2AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!創(chuàng)新：向大自然學(xué)習(xí)生物體、自然生態(tài)系統(tǒng)通過(guò)自身演化解決優(yōu)化問(wèn)題模擬自然生態(tài)系統(tǒng)求解復(fù)雜優(yōu)化問(wèn)題仿生優(yōu)化算法遺傳算法蟻群算法微粒群算法人工免疫算法人工魚群算法混合蛙跳算法3AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!基因DNA4AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!神經(jīng)網(wǎng)絡(luò)5AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!昆蟲蟻，蜂6AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!蟻群算法AntColonyOptimization(ACO)7AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!魚群算法FishSwarmOptimization8AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡(luò)（neuralnetworks）蟻群算法（群體（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangean）蜜蜂算法飛姿傳信，圈軸方向：蜜向，飛行圈數(shù)：距離9AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!AI上這一特殊分支的發(fā)展歷史GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1953SimulatedAnnealing模擬退火10AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!TabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1975遺傳算法GeneticAlgorithmAI上這一特殊分支的發(fā)展歷史11AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1991SwarmIntelligence蟻群算法AntsSystemAI上這一特殊分支的發(fā)展歷史12AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!出版社：人民郵電出版社作者：[美]JamesKennedy/RussellC.Eberhart/YuhuiShi/2009年2月第1版第1次印刷13AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!蟻群優(yōu)化算法AntColonyAlgorithm(ACA)14AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!對(duì)螞蟻的觀察單只螞蟻智能不高;沒有集中的指揮無(wú)所作為蟻群，復(fù)雜的社會(huì)行為：協(xié)同工作筑巢、覓食、遷徙、清掃蟻巢、撫養(yǎng)后代依靠群體能力發(fā)揮出超出個(gè)體的智能15AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!螞蟻的生物學(xué)特征別稱：玄駒、蚍蜉、狀元子屬節(jié)肢動(dòng)物門，昆蟲綱，膜翅目，蟻科

在昆蟲界種類最多，生存量最大約260屬，16000多種，已命名的9000多種拖動(dòng)1400自重的食物舉起自重400倍的物體起源于1億年前的恐龍時(shí)代16AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!螞蟻的群體行為螞蟻個(gè)體簡(jiǎn)單群體：高度機(jī)構(gòu)化的社會(huì)組織遠(yuǎn)超螞蟻個(gè)體能力行為1：覓食食物隨機(jī)散布找到一條蟻巢到食物源的最佳路徑適應(yīng)環(huán)境變化：出現(xiàn)障礙方法：蟻過(guò)留素（雁過(guò)留聲），聞素而跟信息正反饋17AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!良性循環(huán)如何進(jìn)行？符號(hào)和假定：路徑上的信息素濃度記為X螞蟻均勻釋放信息素，dx/dt=常數(shù)蟻穴A，食物源C，路徑1：AC，路徑2：ABC等邊三角形ABC找到食物，沿原路返回BAC18AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!Fig.1.Anexamplewithrealantsa)AntsfollowapathbetweenpointsAandE.b)Anobstacleisinterposed;antscanchoosetogoarounditfollowingoneofthetwodifferentpathswithequalprobability.c)Ontheshorterpathmorepheromoneislaiddown.19AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!要點(diǎn)螞蟻群居群動(dòng)，很少有獨(dú)行俠，選擇信息素濃的路徑，喜歡熱鬧，追求蟻氣（人氣）人也類似。

兩家飯店，一家熱熱火火，一家門可羅雀，選哪家？選登山旅游線，一般人選人氣多的（信息素濃的）信息素啟發(fā)性知識(shí)：人氣高的，自有其優(yōu)點(diǎn)飯店請(qǐng)名人寫詩(shī)歌作畫、寫對(duì)聯(lián)，留下信息素商業(yè)”托”,假造信息素優(yōu)勢(shì)：并行+分布+信息素70%選紅火的，不一定每人是這樣稱為按概率.0.7選紅火的20AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!Fig.1.AcolonyofIhumilisselectingtheshortbranchesonbothmodulesofthebridgea)onemoduleofthebridgeb)andc):photostaken4and8minafterplacementofthebridge21AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!參數(shù)h和k用以匹配真實(shí)實(shí)驗(yàn)數(shù)據(jù)第m+1只螞蟻首先計(jì)算然后生成一個(gè)在區(qū)間[0,1]上均勻分布的隨機(jī)數(shù)若，則選擇橋A，否則選擇橋B22AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!ACO國(guó)際研討會(huì)ACO國(guó)際研討會(huì)1998、2000年、2002年、2004年，2006年，比利時(shí)布魯塞爾大學(xué)23AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!P、NP、NP-C、NP-hard問(wèn)題P類問(wèn)題所有可用DTM(Deterministicone-tapeTuringMachine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問(wèn)題Π的集合。簡(jiǎn)記為O(p(n))即P={L:存在一個(gè)多項(xiàng)式時(shí)間DTM程序M，是的L=LM},其中LM表示程序M所識(shí)別的語(yǔ)言。若存在一個(gè)多項(xiàng)式時(shí)間DTM程序，它在編碼策略e之下求解判定問(wèn)題Π，即L[Π,e]∈P,則稱該判定問(wèn)題屬于P類問(wèn)題。24AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!P、NP、NP-C、NP-hard問(wèn)題NP-C類問(wèn)題(NP-Complete)是NP類中最困難的一類問(wèn)題。有重要實(shí)際意義和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard類問(wèn)題NP-CNP-hardNPPNP-hardNP-C25AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!TSP(TravelingSalesmanProblem)有向圖有向圖D的三元組為(V,E,f)，其中V是一個(gè)非空集合，其元素稱為有向圖的結(jié)點(diǎn)；E是一個(gè)集合，其元素稱為有向圖的弧段（邊）；f是從E到VxV上的一個(gè)映射（函數(shù)）。E中的元素總是和V中的序偶對(duì)有對(duì)應(yīng)關(guān)系，可用V中的序偶代替E中的元素。一個(gè)有向圖Ｄ可簡(jiǎn)記為(V,E).26AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!TSP(TravelingSalesmanProblem)TSP簡(jiǎn)單形象描述給定n個(gè)城市，一個(gè)旅行商從某一城市出發(fā)，訪問(wèn)各城市一次且僅有一次后再回到原出發(fā)城市，要求找出一條最短的巡回路徑可分為對(duì)稱TSP(SymmetricTravelingSalesmanProblem)和非對(duì)稱TSP(AsymmetricTravelingSalesmanProblem)TSP是NP-C問(wèn)題n城市規(guī)模的TSP，存在(n-1)!/2條不同閉合路徑。27AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!應(yīng)用領(lǐng)域解決大多數(shù)優(yōu)化問(wèn)題或轉(zhuǎn)化為優(yōu)化求解的問(wèn)題。分類、聚類、模式識(shí)別、多目標(biāo)優(yōu)化、QoS、流程規(guī)劃信號(hào)處理機(jī)器人控制、決策支持28AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!蟻群優(yōu)化算法研究背景與傳統(tǒng)進(jìn)化算法-梯度算法的差異：，

概率搜索1并行+分布，無(wú)中控，個(gè)別螞蟻死亡無(wú)關(guān)大局2因而程序堅(jiān)固。3非直接信息交流，（廣播）4可處理離散對(duì)象5實(shí)現(xiàn)簡(jiǎn)單

29AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!遺傳算法(GA)物競(jìng)天擇，設(shè)計(jì)染色體編碼，交配突變與適應(yīng)函數(shù)的萃取，優(yōu)化求解神經(jīng)網(wǎng)絡(luò)(ANN)模彷生物神經(jīng)元，透過(guò)神經(jīng)元的訊息傳遞、訓(xùn)練學(xué)習(xí)、回溯，優(yōu)化求解模擬退火演算法(SA)模彷金屬退火過(guò)程基因表達(dá)式編程30AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!31AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!32AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!33AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!鳥群算法ParticleSwarmOptimization有個(gè)帶頭鳥34AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!蜂群算法

MarriageinHoneyBeesOptimization(MBO)35AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!被模擬對(duì)象的智能層次昆蟲（低智能）蜜蜂、螞蟻——蜂群算法，蟻群算法脊椎動(dòng)物門（較低智能）魚群、鳥群——魚群算法，鳥群算法，PSO遺傳算法家族（模擬生物界基本性質(zhì)，中智能）GA,GP

GEP基因表達(dá)式編程GEP–變異和雜交=PSO36AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence198919691969ExpertSystem專家系統(tǒng)AI上這一特殊分支的發(fā)展歷史37AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1989SwarmIntelligence群體智能TabuSearchAI上這一特殊分支的發(fā)展歷史38AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!GeneticAlgorithmTabuSearch195319911975AntsSystem199519891969ExpertSystem1995ParticleSwarmOptimization粒子群優(yōu)化算法AI上這一特殊分支的發(fā)展歷史39AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!幾本相關(guān)的中文書40AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!參考文獻(xiàn)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,andAlbertoColorniiridia.ulb.ac.be/~mdorigo/HomePageDorigo/41AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!蟻群算法特點(diǎn)模擬螞蟻群體智能行為的仿生優(yōu)化算法較強(qiáng)的魯棒性優(yōu)良的分布式計(jì)算機(jī)制易于與其它方法結(jié)合42AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!螞蟻的社會(huì)形態(tài)蟻后、雄蟻、工蟻、兵蟻信息交流方式：化學(xué)通信分泌化學(xué)刺激物：信息素(pheromone)彼此平等，利他主義個(gè)體協(xié)作，協(xié)調(diào)一致共和國(guó)43AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!良性循環(huán)：路好（有食且近）蟻多信息素多蟻多…..（隨時(shí)會(huì)蒸發(fā)掉一部分），開始：信息素濃度路短素濃。44AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!良性循環(huán)如何進(jìn)行？螞蟻M1：AC，螞蟻M2：ABC找到食物（分布、并行），沿原路返回AC比ABC短，M1回到A點(diǎn)時(shí)，M2才到C點(diǎn)。AC上蟻氣：兩次信息素疊加（去-回）AB路只有去一次信息素X(AC)>X(ABC)，下一只螞蟻：選擇路徑ACAC上信息素越來(lái)越多，進(jìn)入良性循環(huán)BAC45AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!Fig.2.Anexamplewithartificialantsa)Theinitialgraphwithdistances.b)Attimet=0thereisnotrailonthegraphedges;therefore,antschoosewhethertoturnrightorleftwithequalprobability.c)Attimet=1trailisstrongeronshorteredges,whicharetherefore,intheaverage,preferredbyants.46AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!雙橋?qū)嶒?yàn)(GossS,1989)Naturwissenschaften76,579-581(1989)Self-organizedShortcutsintheArgentineAntS.Goss,S.Aron,J.L.Deneubourg,andJ.M.PasteelsUnitofBehaviouralEcology,C.P.231,Universit6LibredeBruxelles,B-1050Bruxelles47AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第47頁(yè)!雙橋?qū)嶒?yàn)數(shù)學(xué)模型假設(shè)條件：1、非對(duì)稱橋上的信息量與過(guò)去一個(gè)時(shí)間段內(nèi)經(jīng)過(guò)該橋的螞蟻數(shù)目成正比；2、某一時(shí)刻螞蟻按照橋上殘留的信息量多少來(lái)選擇其中某座橋3、經(jīng)過(guò)該橋的螞蟻數(shù)目越多則橋上的殘留信息量就越大設(shè)短橋?yàn)锳，長(zhǎng)橋?yàn)锽，mA和mB分別表示經(jīng)過(guò)橋A和橋B的螞蟻數(shù)目 mA+mB=m當(dāng)所有m只螞蟻都經(jīng)過(guò)兩座橋之后，第m+1只螞蟻選擇橋A的概率為：而選擇橋B的概率為：48AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第48頁(yè)!發(fā)展意大利學(xué)者M(jìn)Dorigo，Vmaniezzo和AColorni20世紀(jì)90年代：螞蟻系統(tǒng)（antsystem，AS）求解旅行商問(wèn)題（TravelingSalesmanProblem，簡(jiǎn)稱TSP）90年代中期，用于廣泛領(lǐng)域，取得成果MDorigo發(fā)展為優(yōu)化技術(shù)-蟻群優(yōu)化（AntColonyOptimization，簡(jiǎn)稱ACO）WJGutjahr：ACO的收斂性用于合優(yōu)化，函數(shù)優(yōu)化、系統(tǒng)辨識(shí)、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘、網(wǎng)絡(luò)路由49AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第49頁(yè)!基本蟻群算法的數(shù)學(xué)模型50AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第50頁(yè)!P、NP、NP-C、NP-hard問(wèn)題NP類問(wèn)題(Non-deterministicPolynomial)若存在一個(gè)多項(xiàng)式函數(shù)g(x)和一個(gè)驗(yàn)證算法H,對(duì)一類判定問(wèn)題A的任何一個(gè)“是”回答，滿足其輸入長(zhǎng)度d(s)不超過(guò)g(d(I)),其中d(I)為I的輸入長(zhǎng)度，且驗(yàn)證算法中S為I的“是”回答的計(jì)算時(shí)間不超過(guò)g(d(I)),則稱判定問(wèn)題A為非多項(xiàng)式確定問(wèn)題。NP類問(wèn)題是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問(wèn)題Π的集合51AAI51自然計(jì)算及群體智能共56頁(yè)，您現(xiàn)在瀏覽的是第51頁(yè)!基本蟻群算法模型基本假設(shè)螞蟻之間通過(guò)信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍的