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

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

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

3、，如果問題規(guī)模很大，對時間的要求很高，使用回溯算法和相容性技術(shù)需要更多的時間，但如果使用蟻群算法來求解約束滿足問題，因為不需要回溯也沒有因使用相容性技術(shù)簡化網(wǎng)絡(luò)時所帶來的巨大的時間開銷，所以求解效率會更高。本文以約束求解算法和基本的蟻群算法為基礎(chǔ)，使用蟻群算法來求解約束滿足問題。(1)本文分析討論了算法框架MAC,和嵌入在MAC算法中的一些弧相容算法，如AC3，AC4，AC6，AC2001算法，分析解釋了MAC算法如何回溯和如何選擇分支

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