基于蟻群算法的集合覆蓋問(wèn)題求解及其應(yīng)用研究.pdf

1、集合覆蓋問(wèn)題已經(jīng)被證明為NP完全問(wèn)題，所有的NP完全問(wèn)題都不能在多項(xiàng)式算法時(shí)間內(nèi)求解。目前主要用近似算法優(yōu)化集合覆蓋問(wèn)題，對(duì)于復(fù)雜的或規(guī)模較大的集合覆蓋問(wèn)題，現(xiàn)有算法很難達(dá)到理想的優(yōu)化效果。 蟻群算法是建立在群體智能基礎(chǔ)上的一種進(jìn)化算法，講究螞蟻個(gè)體之間的合作，利用信息素正反饋機(jī)制，具有很強(qiáng)的搜索較優(yōu)解的能力。蟻群算法在很多復(fù)雜的組合優(yōu)化問(wèn)題上已有成功的應(yīng)用，其出色的優(yōu)化能力給集合覆蓋問(wèn)題的求解提供了新的思路。蟻群算法同時(shí)也有消

2、耗時(shí)間長(zhǎng)和容易陷于局部最優(yōu)解的缺點(diǎn)。對(duì)蟻群算法進(jìn)行深入分析后，本文提出了一種基于罰函數(shù)理論的蟻群算法PFACO(penaltyfunctionantcolonyoptimization)，仿真結(jié)果表明用PFACO求解集合覆蓋問(wèn)題在全局尋優(yōu)及收斂速度上效果顯著。 數(shù)字系統(tǒng)的測(cè)試集優(yōu)化問(wèn)題與集合覆蓋問(wèn)題本質(zhì)上相似。對(duì)兩種基本電路進(jìn)行分析后，可以對(duì)測(cè)試集優(yōu)化問(wèn)題建立相應(yīng)的集合覆蓋模型，從而將測(cè)試集優(yōu)化問(wèn)題轉(zhuǎn)化為集合覆蓋問(wèn)題。對(duì)時(shí)序電路