基于蟻群算法的集合覆蓋問題求解及其應用研究.pdf

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

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