aai51自然計算及群體智能(文件)
【正文】 43 ACO國際研討會 ? ACO國際研討會 ? 199 2022年、 2022年、 2022年， 2022年，比利時布魯塞爾大學(xué) 44 基本蟻群算法的數(shù)學(xué)模型 45 P、 NP、 NPC、 NPhard問題 ? P類問題 – 所有可用 DTM (Deterministic onetape Turing Machine) 在多項式時間內(nèi)求解的判定問題 Π的集合。 – NP類問題是所有可用 NDTM (NonDeterministic onetape Turing Machine)在多項式時間內(nèi)求解的判定問題 Π的集合 47 P、 NP、 NPC、 NPhard問題 ? NPC類問題 (NPComplete) – 是 NP類中最困難的一類問題。即螞蟻是反應(yīng)型適應(yīng)性主體 – 在個體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨立選擇；在群體水平上，單只螞蟻的行為是隨機的，但蟻群可通過自組織過程形成高度有序的群體行為。 ?52 蟻群算法 時間 ： 20世紀(jì) 90年代 地點 ： 意大利 人物 ： 意大利 M． Dorigo， V． Maniezzo， A． Colorni 目的 ： 模擬自然界螞蟻搜索路徑的行為， 結(jié)果 ： 群體智能理論 應(yīng)用 ： 求解 NP問題 （ TSP問題、分配問題、 jobshop調(diào)度問題）， 解復(fù)雜優(yōu)化問題（離散優(yōu)化問題）有優(yōu)勢 53 應(yīng)用領(lǐng)域 ?解決大多數(shù)優(yōu)化問題 ?或轉(zhuǎn)化為優(yōu)化求解的問題。（導(dǎo)數(shù)，微分） 。 3 非直接 信息交流 ，（廣播） 4 可處理 離散 對象 5 實現(xiàn)簡單 56 實現(xiàn)簡單 算法中僅涉及各種基本的數(shù)學(xué)操作， 對 CPU和內(nèi)存的要求不高。 – E中的元素總是和 V中的序偶對有對應(yīng)關(guān)系，可用 V中的序偶代替 E中的元素。 Asymmetric ? NPhard類問題 – NPC NPhard ?NP P NPhard NPC 48 基本蟻群算法模型 ? 基本假設(shè) – 螞蟻之間通過信息素和環(huán)境進行通信。 – 若存在一個多項式時間 DTM程序，它在編碼策略 e之下求解判定問題 Π，即 L[Π, e]∈ P,則稱該判定問題屬于 P類問題。 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。1 高級人工智能 ? 第一章 人工智能概述 ? 第二章 歸結(jié)推理方法 ? 第三章 不確定性推理 ? 第四章 知識表達方法 ? 第五章 自然計算及群體智能 －蟻群算法 ? 第六章 自然計算及群體智能 －遺傳算法 2 自然計算與群體智能 趙林亮 計算機應(yīng)用技術(shù)研究所 3 創(chuàng)新：向大自然學(xué)習(xí) ? 生物體、自然生態(tài)系統(tǒng) ? 通過自身演化解決優(yōu)化問題 ? 模擬自然生態(tài)系統(tǒng)求解復(fù)雜優(yōu)化問題 ? 仿生優(yōu)化算法 – 遺傳算法 – 蟻群算法 – 微粒群算法 – 人工免疫算法 – 人工魚群算法 – 混合蛙跳算法 4 ? 遺傳算法 (GA) – 物競天擇，設(shè)計染色體編碼，交配 突變與適應(yīng)函數(shù)的萃取，優(yōu)化求解 ? 神經(jīng)網(wǎng)絡(luò) (ANN)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1