求解約束滿足問(wèn)題的自適應(yīng)蟻群算法研究.pdf

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

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

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