最大獨(dú)立集和最小弱頂點(diǎn)覆蓋問題求解及其應(yīng)用研究.pdf

1、全局優(yōu)化問題，特別是組合優(yōu)化問題，是科學(xué)研究與工程計(jì)算中最基本的問題之一，這類問題的求解一直是算法研究領(lǐng)域的熱點(diǎn)問題。全局優(yōu)化方法一般分為確定型和隨機(jī)型方法，確定型方法在數(shù)學(xué)理論上較為完善，但難以應(yīng)用，而傳統(tǒng)的隨機(jī)型方法對(duì)于復(fù)雜的全局優(yōu)化問題又難以解決，這時(shí)啟發(fā)式算法的引入使得隨機(jī)型方法和整個(gè)全局優(yōu)化方法得到了新的發(fā)展，尤其是元啟發(fā)式算法。 蟻群優(yōu)化算法(AntColonyOptimization，簡(jiǎn)稱ACO)作為一種新的元啟發(fā)

2、式算法，具有分布式計(jì)算、自組織、正反饋以及貪心啟發(fā)等特點(diǎn)，使其能夠成功解決許多NP-hard組合優(yōu)化問題。ACO算法作為一種全局搜索算法，其全局優(yōu)化性能的優(yōu)劣在很大程度上與參數(shù)的正確選擇有關(guān)。但由于ACO算法參數(shù)之間的關(guān)聯(lián)性，使得最優(yōu)參數(shù)組合成為一個(gè)極其復(fù)雜的優(yōu)化問題，目前還沒有形成完善的理論依據(jù)，一般都是根據(jù)經(jīng)驗(yàn)來確定參數(shù)值。而禁忌搜索算法(TabuSearch，簡(jiǎn)稱TS)以其靈活的禁忌表和相應(yīng)的禁忌準(zhǔn)則來避免重復(fù)迂回搜索，具有強(qiáng)大的

3、全局優(yōu)化性能。所以為彌補(bǔ)ACO算法易出現(xiàn)停滯現(xiàn)象和陷入局部最優(yōu)這一缺陷，本文將ACO算法與TS算法組合起來，提出了基于禁忌搜索的蟻群優(yōu)化算法(TabuSearchBasedAntColonyOptimization，簡(jiǎn)稱TSBACO)，并將該算法用于求解最大獨(dú)立集問題。實(shí)驗(yàn)表明：禁忌搜索策略的引入，不僅提高了TSBACO算法的全局優(yōu)化性能而且還提高了搜索效率。 為了增強(qiáng)超大規(guī)模集成電路(VLSI)系統(tǒng)運(yùn)行時(shí)的可靠性與穩(wěn)定性，需要

4、在電路設(shè)計(jì)中引入容錯(cuò)技術(shù)增強(qiáng)系統(tǒng)的容錯(cuò)能力。在VLSI陣列的容錯(cuò)技術(shù)中，一般有冗余法和降階法兩種重構(gòu)方法，這兩種方法都屬于NP-hard問題。本文是通過冗余法來解決這一問題的，根據(jù)陣列中缺陷單元的分布情況，構(gòu)造相應(yīng)的矛盾圖模型，將陣列的重構(gòu)問題轉(zhuǎn)化為求解矛盾圖的獨(dú)立集問題。通過TSBACO算法對(duì)矛盾圖的獨(dú)立集進(jìn)行求解且使得所求獨(dú)立集大小恰為缺陷單元個(gè)數(shù)，找出合理的補(bǔ)償通道來完成陣列的重構(gòu)問題。實(shí)驗(yàn)分析表明該重構(gòu)方法是簡(jiǎn)單有效的。

5、 為進(jìn)一步驗(yàn)證TSBACO算法在求解組合優(yōu)化問題方面的實(shí)用性和有效性，本文將其應(yīng)用于網(wǎng)絡(luò)流量測(cè)量中的有效測(cè)量點(diǎn)選擇問題。通過對(duì)圖論中最小頂點(diǎn)覆蓋模型的研究，網(wǎng)絡(luò)流量測(cè)量點(diǎn)選擇問題可以抽象為最小弱頂點(diǎn)覆蓋問題，而求解該問題是一個(gè)NP-hard問題，于是本文又提出了一種求解最小弱頂點(diǎn)覆蓋問題的TSBACO算法。比較現(xiàn)有的求解算法，實(shí)驗(yàn)結(jié)果表明：本文提出的TSBACO算法能夠發(fā)現(xiàn)更小的弱頂點(diǎn)覆蓋集，且具有更好的可擴(kuò)展性，是網(wǎng)絡(luò)流量測(cè)量中的一種