求解約束滿足問題的自適應蟻群算法研究.pdf

1、蟻群算法是群智能優(yōu)化算法的一種，它根據(jù)螞蟻在覓食過程中，釋放一種叫信息素的化學物質標記較理想的覓食路徑，以為群體中其他成員提供可參考的先驗信息。約束滿足問題是由一系列變量、變量相應的值域以及變量之間的約束關系組成，目標是為這些變量找到一組或多組滿足所有約束關系的賦值。約束滿足問題通常都是NP難問題，旨在有限的時間內(nèi)找出令人滿意的解決方案。
　　本文首先介紹了利用蟻群算法解決約束滿足問題的基本方法，并對求解過程中蟻群算法的五種信息素

2、更新策略做出了詳細闡述，以二元約束滿足問題為例，采用五種基本的蟻群算法對該問題進行了求解，驗證蟻群算法解決約束滿足問題的性能，并通過對比各個信息素更新策略對二元約束滿足問題運行情況的影響，總結不同策略在求解約束滿足問題時的有效性。然后，設計并實現(xiàn)了一種自適應信息素更新策略選擇機制，使信息素的更新策略能隨著搜索條件的不同自適應地做出調整，從而使蟻群算法能更好的滿足問題的多種約束條件。最后，介紹了在求解約束滿足問題過程中的七種啟發(fā)式變量序，

3、螞蟻從空任務開始迭代選擇變量賦值，執(zhí)行一個任務即完成對每一個變量的一次賦值，因此，變量的選擇序對問題的求解也具有重要影響，本文通過實驗，對比了每種啟發(fā)式變量序的性能，并將自適應的啟發(fā)式變量序應用于求解約束滿足問題。
　　本文通過實驗研究，對比分析了不同信息素更新策略在利用蟻群算法解決約束滿足問題中的表現(xiàn)，并將自適應的信息素更新算法與性能較好的信息素更新策略相比較，通過參數(shù)調整、收斂性分析、收斂時間比照、代價值和成功率的對比，證明了