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

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

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

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

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