蟻群算法的理論與性能研究.pdf

1、蟻群優(yōu)化算法是一種新型的求解復(fù)雜優(yōu)化問(wèn)題的元啟發(fā)式算法，它是由意大利學(xué)者M(jìn).Dorigo等人受到自然界中真實(shí)蟻群集體行為的靈感而首先提出來(lái)的，并用來(lái)解決離散優(yōu)化問(wèn)題。由于蟻群算法具有穩(wěn)健性、全局性、普遍性、分布式計(jì)算等優(yōu)點(diǎn)，其理論研究不斷深入，應(yīng)用領(lǐng)域不斷擴(kuò)大。大量實(shí)驗(yàn)結(jié)果表明，它在解決許多組合優(yōu)化問(wèn)題時(shí)都能表現(xiàn)出較好的求解能力，經(jīng)過(guò)了眾多國(guó)內(nèi)外學(xué)者不斷地對(duì)其進(jìn)行擴(kuò)展和改進(jìn)，蟻群算法正經(jīng)歷著一個(gè)不斷發(fā)展和完善的過(guò)程。 雖然通過(guò)對(duì)

2、大量應(yīng)用問(wèn)題的求解，已經(jīng)顯示出蟻群優(yōu)化算法的高效性，但它的成功主要在實(shí)驗(yàn)層次上，很少有理論來(lái)解釋利用蟻群算法為什么能夠成功地解決這些問(wèn)題。它能否保證所得到的解一定是全局最優(yōu)解，還有什么問(wèn)題利用蟻群算法不能解決，對(duì)于能夠解決的問(wèn)題，它的時(shí)間復(fù)雜性到底有多大。因此有必要研究蟻群優(yōu)化算法的欺騙性問(wèn)題。由于蟻群算法具有本質(zhì)上的并行特性，我們需要研究如何高效率地對(duì)它進(jìn)行并行化，如何平衡通信開銷與加速比之間的關(guān)系。蟻群算法的一個(gè)主要缺點(diǎn)是不能直接解

3、決連續(xù)優(yōu)化問(wèn)題。以往解決此類問(wèn)題的方案，大部分改變了蟻群優(yōu)化算法的基本結(jié)構(gòu)，不能充分發(fā)揮蟻群優(yōu)化算法的正反饋機(jī)制的優(yōu)勢(shì)。因此有必要研究在解決連續(xù)優(yōu)化問(wèn)題時(shí)該如何保持本質(zhì)模型的不變，如何充分利用信息素和啟發(fā)式信息，保證解的精確性的同時(shí)能加速收斂速度。 本文針對(duì)蟻群算法的上述問(wèn)題，作了下面的研究。 (1)研究蟻群算法求解欺騙性問(wèn)題時(shí)的收斂性和時(shí)間復(fù)雜度。以n-bit陷阱問(wèn)題為例，證明了蟻群算法一階欺騙性問(wèn)題在一定的信息素初始

4、值條件下，不滿足解的收斂性，但滿足值的收斂性。我們證明了，使用信息素帶限的蟻群算法MMAS求解n-bit陷阱問(wèn)題達(dá)到最優(yōu)解的時(shí)間復(fù)雜度為O(n2m.logn)，這里n為問(wèn)題的規(guī)模，m為螞蟻的個(gè)數(shù)。同時(shí)，我們的實(shí)驗(yàn)結(jié)果也驗(yàn)證了上述結(jié)論的正確性。 (2)提出了一種MPP上的自適應(yīng)的并行蟻群算法PACO。該算法在兩個(gè)方面進(jìn)行了重要改進(jìn)來(lái)加強(qiáng)算法的性能。一方面，我們提出一種處理機(jī)之間的信息交流策略，使得每個(gè)處理機(jī)可自適應(yīng)地選擇另外一個(gè)處

5、理機(jī)來(lái)交流信息并更新信息素。另一方面，我們還提出一種根據(jù)解的多樣性來(lái)自適應(yīng)地調(diào)節(jié)信息交流周期的方法，以在加強(qiáng)優(yōu)化能力的同時(shí)避免早熟收斂，以增加解的多樣性。我們對(duì)并行蟻群算法PACO值的收斂性進(jìn)行了分析與證明。我們用標(biāo)準(zhǔn)的旅行商問(wèn)題在大規(guī)模并行機(jī)上做了測(cè)試，實(shí)驗(yàn)結(jié)果表明，我們算法在收斂速度，加速比，穩(wěn)定性和準(zhǔn)確性各方面都要優(yōu)于別的并行蟻群算法。 (3)提出了一種用蟻群算法求解連續(xù)空間優(yōu)化問(wèn)題的方法。該方法保持了基本蟻群算法的基本框