從人工螞蟻系統(tǒng)淺談復(fù)雜的研究ppt課件

1、從人工螞蟻系統(tǒng)從人工螞蟻系統(tǒng)淺談復(fù)雜性的研討淺談復(fù)雜性的研討中國(guó)科技大學(xué)計(jì)算機(jī)系中國(guó)科技大學(xué)計(jì)算機(jī)系: : 張巍張巍2001 2001 年年 11 11 月月 20 20 日日主要的目的 匯報(bào)我對(duì)匯報(bào)我對(duì) Complexity，Ant System 學(xué)習(xí)的幾點(diǎn)領(lǐng)會(huì)學(xué)習(xí)的幾點(diǎn)領(lǐng)會(huì)主要的內(nèi)容 復(fù)雜性 (Complexity) 研討的根本背景 多主體系統(tǒng) (Multiagent System) 的簡(jiǎn)介 人工螞蟻系統(tǒng) (Ant System)求解TSP問(wèn)題一、復(fù)雜性 (Complexity) 研討的背景1、來(lái)源：對(duì)決議

2、論和復(fù)原論的質(zhì)疑整體往往大于部分的“簡(jiǎn)單和 螞蟻的低智能蟻群的高智慧 螞蟻的簡(jiǎn)單行為蟻群的智能突現(xiàn)2、復(fù)雜系統(tǒng)多主體規(guī)那么相互作用1、主體Agent) 感知決策影響自治性、交互性、協(xié)作性、可通訊性、長(zhǎng)壽性2、自組織多主體系統(tǒng)的特征蟻群負(fù)反響 (Negative Feedback)正反響 (Positive Feedback) “滾雪球隨機(jī)擾動(dòng)的放大多重的相互作用3、AER模型Agents-Environment-Rules Mode)二、多主體系統(tǒng) (Multiagent System)三、實(shí)踐蟻群的尋食1、主體：螞蟻2、規(guī)那么：分工、通訊3、相互作用： 螞蟻螞蟻 螞蟻環(huán)境四、人工螞蟻系統(tǒng) (

3、AS) 求解TSP問(wèn)題1、游覽商問(wèn)題TSP)在全銜接的賦權(quán)圖中找到經(jīng)過(guò)每個(gè)結(jié)點(diǎn)且只經(jīng)過(guò)一次的最短通路。2、人工螞蟻系統(tǒng)Ant System Algorithm)四、人工螞蟻系統(tǒng) (AS) 求解TSP問(wèn)題螞蟻：只利用部分信息系統(tǒng)：找到全局的TSP通路 智能的突現(xiàn)Emergence)AS算法的根本思想：AS算法的根本步驟四、人工螞蟻系統(tǒng) (AS) 求解TSP問(wèn)題2、人工螞蟻系統(tǒng)初始：每個(gè)邊=一樣濃度的氣味 綠螞蟻從A開場(chǎng)爬， 根據(jù)氣味和邊長(zhǎng) (部分信息) 選擇邊，選了AB，到達(dá) B。在B： 看看還有哪些城沒(méi)去，按照上述方法找到下一條邊 這樣進(jìn)展下去，就得到一條通路。其他的螞蟻依次類推，都得到一條通

4、路。四、人工螞蟻系統(tǒng) (AS) 求解TSP問(wèn)題2、人工螞蟻系統(tǒng)一個(gè)新的旅程開場(chǎng)了 (又一次的迭代) 。記錄DABC，長(zhǎng)3；每個(gè)螞蟻通路的每條邊釋放一個(gè)單位氣味；DABC最短，追加氣味。假設(shè)這四條通路分別為： ABCD，長(zhǎng)9； BDCA，長(zhǎng)為12； CABD,長(zhǎng)為6； DABC，長(zhǎng)為3。迭代次數(shù)=預(yù)設(shè)置時(shí)，TSP通路找到了全局的結(jié)果AS算法的幾點(diǎn)闡明 四、人工螞蟻系統(tǒng) (AS) 求解TSP問(wèn)題2、人工螞蟻系統(tǒng)邊的選擇P = f (C , d) C：邊的氣味濃度； d：邊的長(zhǎng)度1C、d：部分的信息2允許隨機(jī)擾動(dòng)正負(fù)反響：AS算法的幾點(diǎn)闡明 四、人工螞蟻系統(tǒng) (AS) 求解TSP問(wèn)題2、人工螞蟻系統(tǒng)C(t+1) = (1-q)C(t) + kc(t)(1-q)C(t)：負(fù)反響項(xiàng)；kc(t)：正反響項(xiàng)。相互作用：螞蟻環(huán)境釋放氣味影響行為算法的時(shí)間復(fù)雜度： 四、人工螞蟻系統(tǒng) (AS) 求解TSP問(wèn)題2、人工螞蟻系統(tǒng)AS算法的幾點(diǎn)闡明 結(jié)果與啟示t：迭代次數(shù)，n：城市數(shù)“不收斂性五、幾個(gè)有待討論的問(wèn)題 Ant Syste