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

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

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

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