用于組合優(yōu)化的人工免疫算法設計與分析.pdf

1、克隆選擇算法是人工免疫系統(tǒng)領域中的重要算法之一。作為克隆選擇算法中重要的算子，元動力學算子很少受到關注。另一方面，進化非選擇算法是基于生物免疫進化機制和免疫非選擇機制而提出的一種新的算法，可應用于組合優(yōu)化和異常檢測等問題。但是，迄今為止，尚未有相關文獻專門研究用于組合優(yōu)化問題的進化非選擇算法的時間復雜度。
　　 本文主要針對人工免疫系統(tǒng)中的這兩個算法進行研究，具體工作包括以下幾個方面。
　　 (1)從實驗角度分析和討論了

2、不同元動力學策略對于克隆選擇算法性能的影響。傳統(tǒng)的元動力學策略是對二進制染色體中的每一位，以相同的概率生成0或者1。然而，對于有些問題，這種元動力學策略實際上并不能真的增加種群的多樣性。例如，該問題的解與0或者1的個數(shù)有關，而與0或者1在二進制染色體中的位置沒有關系的時候。因此，本文提出了三種新的元動力學策略。針對上面所提到的這類問題，這三種元動力學可以很明顯的起到均勻采樣的作用。實驗結果表明，本文提出的這三種元動力學策略在這一類問題上

3、具有較好的性能。
　　 (2)基于一個典型的組合優(yōu)化問題，對比分析了采用不同匹配閾值的進化非選擇算法在該問題上的平均時間復雜度。理論分析和實驗結果表明，有合適匹配閾值的進化非選擇算法的性能優(yōu)于傳統(tǒng)進化算法的性能。由此可知，非選擇算子對于提升進化類算法的性能有重要作用。
　　 (3)一方面，有合適匹配閾值的進化非選擇算法的性能優(yōu)于傳統(tǒng)進化算法的性能。另一方面，當匹配閾值不合適時，進化非選擇算法的性能未必優(yōu)于傳統(tǒng)進化算法。為

4、此，本文進一步分析和討論了，匹配閾值在一定范圍內(nèi)變化時，進化非選擇算法的性能會有怎樣的變化。理論結果和實驗結果表明，合適的匹配閾值在常數(shù)范圍內(nèi)變化時，進化非選擇算法的性能仍然優(yōu)于傳統(tǒng)進化算法；而當不合適的匹配閾值在常數(shù)范圍內(nèi)變化時，進化非選擇算法的性能未必優(yōu)于傳統(tǒng)進化算法的性能。
　　 總的來說，本文首先提出了三種新的元動力學策略，分析了元動力學算子對克隆選擇算法性能的影響。然后，分析了進化非選擇算法在一個組合優(yōu)化問題上的平均時