aai51自然計(jì)算及群體智能-免費(fèi)閱讀
【正文】 ?分類(lèi)、聚類(lèi)、模式識(shí)別、 ?多目標(biāo)優(yōu)化、 ?QoS、 ?流程規(guī)劃 ?信號(hào)處理 ?機(jī)器人控制、 ?決策支持 54 背景 群體智能理論包括： 微粒群算法， Particle Swarm Optimization, PSO 魚(yú)群 鳥(niǎo)群 追尾 ? 蟻群算法 (Ant Colony Optimization, ACO) ? 簡(jiǎn)單社會(huì)系統(tǒng)的模擬 55 蟻群優(yōu)化算法研究背景 與傳統(tǒng)進(jìn)化算法 梯度算法的差異 ：， 概率搜索 1 并行 +分布 ， 無(wú)中控， 個(gè)別螞蟻死亡 無(wú)關(guān)大局 2 因而程序 堅(jiān)固 。 – 有重要實(shí)際意義和工程背景 – TSP (Traveling Salesman Problem) ? Symmetric。 AC上蟻氣 ：兩次信息素疊加（去 回） AB路只有去一次信息素 X(AC)X(ABC)，下一只螞蟻：選擇路徑 AC AC上信息素越來(lái)越多，進(jìn)入良性循環(huán) B A C 35 Fig. 1. An example with real ants a) Ants follow a path between points A and E. b) An obstacle is interposed。 ants can choose to go around it following one of the two different paths with equal probability. c) On the shorter path more pheromone is laid down. 36 Fig. 2. An example with artificial ants a) The initial graph with distances. b) At time t=0 there is no trail on the graph edges。 Asymmetric ? NPhard類(lèi)問(wèn)題 – NPC NPhard ?NP P NPhard NPC 48 基本蟻群算法模型 ? 基本假設(shè) – 螞蟻之間通過(guò)信息素和環(huán)境進(jìn)行通信。 3 非直接 信息交流 ，（廣播） 4 可處理 離散 對(duì)象 5 實(shí)現(xiàn)簡(jiǎn)單 56 實(shí)現(xiàn)簡(jiǎn)單 算法中僅涉及各種基本的數(shù)學(xué)操作， 對(duì) CPU和內(nèi)存的要求不高。 ?52 蟻群算法 時(shí)間 ： 20世紀(jì) 90年代 地點(diǎn) ： 意大利 人物 ： 意大利 M． Dorigo， V． Maniezzo， A． Colorni 目的 ： 模擬自然界螞蟻搜索路徑的行為， 結(jié)果 ： 群體智能理論 應(yīng)用 ： 求解 NP問(wèn)題 （ TSP問(wèn)題、分配問(wèn)題、 jobshop調(diào)度問(wèn)題）， 解復(fù)雜優(yōu)化問(wèn)題（離散優(yōu)化問(wèn)題）有優(yōu)勢(shì) 53 應(yīng)用領(lǐng)域 ?解決大多數(shù)優(yōu)化問(wèn)題 ?或轉(zhuǎn)化為優(yōu)化求解的問(wèn)題。 – NP類(lèi)問(wèn)題是所有可用 NDTM (NonDeterministic onetape Turing Machine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問(wèn)題 Π的集合 47 P、 NP、 NPC、 NPhard問(wèn)題 ? NPC類(lèi)問(wèn)題 (NPComplete) – 是 NP類(lèi)中最困難的一類(lèi)問(wèn)題。 33 良性循環(huán)如何進(jìn)行？ 符號(hào)和假定：路徑上的信息素濃度記為 X 螞蟻均勻釋放信息素， dx/dt =常數(shù) 蟻穴 A，食物源 C， 路徑 1： A?C， 路徑 2： A?B?C 等邊三角形 ABC 找到食物，沿原路返回 B A C 34 良性循環(huán)如何進(jìn)行？ 螞蟻 M1： A?C，螞蟻 M2： A?B?C 找到食物（分布、并行），沿原路返回 AC 比 AB
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1