解決最大團(tuán)問(wèn)題的蟻群優(yōu)化算法的研究與應(yīng)用.pdf

1、蟻群優(yōu)化算法是一種基于自然啟發(fā)的metaheuristic算法，從其提出到現(xiàn)在歷經(jīng)10多年的發(fā)展到目前已經(jīng)成為一種解決組合優(yōu)化問(wèn)題的有效工具。最大團(tuán)問(wèn)題是一個(gè)經(jīng)典的NP難的組合優(yōu)化問(wèn)題，很多實(shí)際問(wèn)題都可以抽象為對(duì)無(wú)向圖上最大團(tuán)問(wèn)題的求解，所以，對(duì)最大團(tuán)問(wèn)題的研究無(wú)論在理論上還是實(shí)際上都有重要意義。
　　鑒于此，本文對(duì)蟻群優(yōu)化算法解決最大團(tuán)問(wèn)題的能力進(jìn)行了研究，提出一個(gè)解決最大團(tuán)問(wèn)題的intensification和diversif

2、ication平衡協(xié)作的蟻群優(yōu)化算法。并且應(yīng)用這個(gè)算法改進(jìn)解決多序列比對(duì)問(wèn)題的progressvie算法。
　　本文首先簡(jiǎn)要介紹了解決最大團(tuán)問(wèn)題常用的metaheuristic方法，并對(duì)最大團(tuán)問(wèn)題進(jìn)行描述。然后詳細(xì)介紹了解決最大團(tuán)問(wèn)題的兩個(gè)機(jī)制類似的metaheuristic方法：迄今為止性能最好的遺傳算法—EA/G算法和現(xiàn)存的簡(jiǎn)單的蟻群優(yōu)化算法。接著，對(duì)解決最大團(tuán)問(wèn)題現(xiàn)存的簡(jiǎn)單的蟻群優(yōu)化算法進(jìn)行分析，指出它存在的不足，從而在此基

3、礎(chǔ)上提出一個(gè)改進(jìn)的蟻群優(yōu)化算法，并對(duì)該算法的intensification和diversification機(jī)制進(jìn)行了分析。此外還利用DIMACS提供的最大團(tuán)問(wèn)題的基準(zhǔn)實(shí)例，對(duì)改進(jìn)的蟻群優(yōu)化算法的性能進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明，該算法的性能不僅超過(guò)了簡(jiǎn)單的蟻群優(yōu)化算法，還超過(guò)了與其機(jī)制類似的迄今為止性能最好的遺傳算法—EA/G算法。最后，本文對(duì)改進(jìn)的蟻群優(yōu)化算法在多序列比對(duì)問(wèn)題上的應(yīng)用進(jìn)行了研究，采取分治思想改進(jìn)現(xiàn)有的progressive