基于蟻群算法的約束求解.pdf

1、約束滿足問(wèn)題是人工智能中一個(gè)非常重要的分支，現(xiàn)實(shí)中很多問(wèn)題都可以被抽象成用約束算法來(lái)解決的問(wèn)題，向生產(chǎn)調(diào)度和資源配置就常用約束算法來(lái)求解，在實(shí)際問(wèn)題中問(wèn)題的規(guī)?？赡軙?huì)非常大，也肯能是NP難問(wèn)題，如果用傳統(tǒng)的方法可能很難在在合理的時(shí)間內(nèi)得到滿意的解，而約束求解算法在解決這類問(wèn)題時(shí)有著很高的效率，約束算法中常用的是回溯算法如MAC算法，在回溯算法中也會(huì)嵌入弧相容的算法，弧相容是用來(lái)刪除一些不相容的值，來(lái)壓縮解空間，從而提高求解效率。

2、　　通過(guò)仿生學(xué)的研究，人們發(fā)現(xiàn)個(gè)體行為簡(jiǎn)單的螞蟻可以在沒(méi)有群體指揮的情況下完成復(fù)雜的任務(wù)，通過(guò)進(jìn)一步的研究發(fā)現(xiàn)螞蟻通過(guò)釋放信息素來(lái)完成合作交流的。在這個(gè)過(guò)程的啟發(fā)下意大利學(xué)者M(jìn).Dorigo,V.Maniezzo等人提出了蟻群算法，由于蟻群的覓食過(guò)程和TSP問(wèn)題很相似，所以蟻群算法通常用來(lái)解決TSP問(wèn)題。同樣蟻群算法也被用于生產(chǎn)調(diào)度，組合優(yōu)化，數(shù)據(jù)挖掘等領(lǐng)域。
　　約束求解技術(shù)雖然在求解約束滿足問(wèn)題時(shí)有著很好的效率，但在實(shí)際問(wèn)題中

3、，如果問(wèn)題規(guī)模很大，對(duì)時(shí)間的要求很高，使用回溯算法和相容性技術(shù)需要更多的時(shí)間，但如果使用蟻群算法來(lái)求解約束滿足問(wèn)題，因?yàn)椴恍枰厮菀矝](méi)有因使用相容性技術(shù)簡(jiǎn)化網(wǎng)絡(luò)時(shí)所帶來(lái)的巨大的時(shí)間開銷，所以求解效率會(huì)更高。本文以約束求解算法和基本的蟻群算法為基礎(chǔ)，使用蟻群算法來(lái)求解約束滿足問(wèn)題。(1)本文分析討論了算法框架MAC,和嵌入在MAC算法中的一些弧相容算法，如AC3，AC4，AC6，AC2001算法，分析解釋了MAC算法如何回溯和如何選擇分支

4、策略，AC3，AC4，AC6，AC2001算法檢查方式和檢查次數(shù)有關(guān)的各自具有的數(shù)據(jù)結(jié)構(gòu)。介紹了蟻群算法的原理和基本蟻群算法求解TSP問(wèn)題。(2)將適用于約束求解的benchmark數(shù)據(jù)建立成相應(yīng)的TSP問(wèn)題的模型，把每個(gè)變量的變量值映射成TSP問(wèn)題中的一個(gè)城市，螞蟻在爬行的時(shí)候并不會(huì)走完每個(gè)城市，只會(huì)走每個(gè)變量的一個(gè)值(3)螞蟻在對(duì)下一個(gè)節(jié)點(diǎn)進(jìn)行選擇時(shí)所遵循的概率公式會(huì)有所不同，本文提出了兩個(gè)公式，公式一螞蟻只遵循信息素濃度，公式二中