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

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

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

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

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