社會演化算法及其在TSP問題中的應用.pdf

1、組合優(yōu)化是運籌學的重要分支，主要通過對數(shù)學方法的研究尋找離散事件的最優(yōu)編排、分組、次序或篩選等。大多數(shù)這類問題屬于NP完全問題。當問題規(guī)模逐漸擴大時，其解空間呈組合爆炸特征，無法用常規(guī)的方法求解。此類問題目前只能用啟發(fā)式算法進行求解。旅行商問題（TSP）就是一個經(jīng)典的組合優(yōu)化問題。
　　 本文給出了一種基于社會演化算法求解TSP問題的方法，該算法用認知主體取代了傳統(tǒng)遺傳算法的基于編碼的可行解生成方式；用基于“范式學習與更新”的進

2、化尋優(yōu)機制取代了傳統(tǒng)遺傳算法中基于模仿基因的遺傳和變異的進化尋優(yōu)機制，使其計算效率更優(yōu)。
　　 在本文的應用研究中，將社會演化算法和蟻群算法相結(jié)合，以蟻群算法作為認知主體的推理過程，得到認知主體進行學習的初步范式，再以社會演化算法中基于“范式的學習和更新”方式獲得最優(yōu)解。通過具體算例實驗仿真與TSP已知最優(yōu)解進行對比分析，結(jié)果表明，社會演化算法在種群規(guī)模較小，迭代次數(shù)較少的情況下也可獲得TSP最優(yōu)解。
　　 在求解TSP