一種基于引力的合作克隆選擇算法

陽(yáng)文學(xué)

摘要 ：為充分挖掘抗體群中個(gè)體間的有關(guān)信息，提高算法性能，本文基于萬(wàn)有引力定律，提出了一種基于引力的合作克隆選擇算法。通過(guò)幾個(gè)函數(shù)優(yōu)化標(biāo)準(zhǔn)測(cè)試函數(shù)實(shí)驗(yàn)證實(shí)，本文算法有效提高了性能。

關(guān)鍵詞：克隆選擇；萬(wàn)有引力；函數(shù)優(yōu)化

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）09-0221-02

1 概述

近年來(lái)，受生物免疫系統(tǒng)啟發(fā)的人工免疫系統(tǒng)逐漸成為智能計(jì)算中的研究熱點(diǎn)，出現(xiàn)了多種基于免疫原理的啟發(fā)式算法。其中，模擬脊椎動(dòng)物免疫系統(tǒng)克隆選擇模型，人工克免疫克隆選擇算法被設(shè)計(jì)出來(lái)。相比較遺傳算法，人工克免疫克隆選擇算法表現(xiàn)出許多好的特性，如提高了收斂速度；保持了種群多樣性 ；較有效地克服早熟收斂、欺騙問(wèn)題等遺傳算法本身難以解決的問(wèn)題。因此廣泛應(yīng)用在模式識(shí)別、優(yōu)化等工程領(lǐng)域，近年來(lái)，也應(yīng)用到數(shù)據(jù)挖掘，網(wǎng)絡(luò)安全等領(lǐng)域。

本質(zhì)上，克隆選擇算法是以群體為基礎(chǔ)的搜索算法。從不同的角度來(lái)看，一個(gè)以群體為基礎(chǔ)的搜索算法，其個(gè)體在每次迭代中通過(guò)三個(gè)步驟來(lái)實(shí)現(xiàn)對(duì)搜索空間的探索和開發(fā)：自我適應(yīng)（自我調(diào)整），合作和競(jìng)爭(zhēng)。在自我調(diào)整的步驟中，每個(gè)個(gè)體提高其性能。在合作過(guò)程中，各個(gè)體通過(guò)信息傳遞相互協(xié)作。最后，在競(jìng)爭(zhēng)這一步，個(gè)體競(jìng)爭(zhēng)生存。這些步驟通常是隨機(jī)的形式，并且可以用不同的方式來(lái)實(shí)現(xiàn)。這些步驟從自然界啟發(fā)，是以群體為基礎(chǔ)的啟發(fā)式算法的原則思想，引導(dǎo)算法找到全局最優(yōu)解。在克隆選擇算法中，主要算子克隆、變異、選擇完成對(duì)搜索空間的探索和開發(fā)，其中克隆與變異是個(gè)體的自我調(diào)整，選擇就是競(jìng)爭(zhēng)。

然而，并不是所有的以群體為基礎(chǔ)的搜索算法對(duì)每個(gè)優(yōu)化問(wèn)題求解上都能提供了令人滿意的結(jié)果，也沒有一個(gè)啟發(fā)式算法，在解決所有優(yōu)化問(wèn)題時(shí)，均可以比其他所有算法性能更優(yōu)，換句話說(shuō)，某個(gè)算法能解決一些問(wèn)題性能更好，而解決其他一些問(wèn)題比別的算法更差。因此，新的高性能啟發(fā)式算法的研究會(huì)一直受到研究者的關(guān)注。

現(xiàn)有文獻(xiàn)中，克隆選擇算法自我適應(yīng)方面的研究較多，比如按照抗體適應(yīng)度，每個(gè)抗體克隆規(guī)模和變異概率有所不同，通?？贵w的克隆規(guī)模和變異概率是其適應(yīng)度的函數(shù)，克隆選擇算法中，個(gè)體間的競(jìng)爭(zhēng)體現(xiàn)在選擇操作，每代中，克隆后的抗體群中適應(yīng)度高的抗體會(huì)被選擇進(jìn)入下一代?？贵w間的合作研究很少，一個(gè)個(gè)體，向著更好地適應(yīng)度方向在運(yùn)動(dòng)，整體群體向著目標(biāo)運(yùn)動(dòng)，要更多的挖掘群體中個(gè)體間的有關(guān)信息，讓它們有助于整個(gè)抗體群更快速地向著目標(biāo)運(yùn)動(dòng)，基于這一點(diǎn)，本文從牛頓萬(wàn)有引力定律入手，以抗體間的引力合作為基礎(chǔ)，提出了基于引力的合作克隆選算法。

測(cè)試時(shí)，對(duì)于SGA和ACCA，設(shè)置交叉概率0.8，變異概率0.07，種群規(guī)模都為50；CSA、ACCA和本文算法的種群規(guī)模為50，克隆規(guī)模為25，保證各算法的總的函數(shù)計(jì)算次數(shù)相同；對(duì)于變異策略，ACCA采用 “尺度收縮”[1]，CSA和本文算法采用非均勻變異[2]；ACCA算法，設(shè)置變異參數(shù)[α]=2，[β]=0.2～10，[γ]=0.3。本文算法設(shè)置編碼長(zhǎng)度為10，引力常量G固定為0.1，合作抗體數(shù)Nbest固定為10 。對(duì)于二維測(cè)試函數(shù)優(yōu)化，取算法的總進(jìn)化代數(shù)為100；對(duì)于高維函數(shù)，取變量維數(shù)為10，算法總進(jìn)化代數(shù)為300。表1是隨機(jī)獨(dú)立運(yùn)行60次的統(tǒng)計(jì)結(jié)果（Visual studio 2010 C++編寫）。 （下轉(zhuǎn)第224頁(yè)）

可以從表中看出，對(duì)于二維測(cè)試函數(shù)f1 、f2和高維測(cè)試函數(shù)f3 、f4，本文算法在求解性能上（主要是求解精度和穩(wěn)定性）要優(yōu)于其他三種算法。

4 結(jié)論

本文從牛頓萬(wàn)有引力定律入手，以抗體間的引力合作為基礎(chǔ)，引入新的算子，充分利用了抗體群個(gè)體間的有關(guān)信息，讓它們有助于整個(gè)抗體群更快速地向著目標(biāo)運(yùn)動(dòng)。相比較其他一些克隆選擇或其他算法，經(jīng)過(guò)部分標(biāo)準(zhǔn)優(yōu)化測(cè)試函數(shù)實(shí)驗(yàn)，本文提出的算法在求解性能上有較有效提高。

參考文獻(xiàn)：

[1] 駱晨鐘，邵惠鶴.采用混沌變異的進(jìn)化算法[J].控制與決策，2000，15（5）：557-560.

[2] 杜海峰，公茂果，劉若辰，等.自適應(yīng)混沌克隆進(jìn)化規(guī)劃算法[J].中國(guó)科學(xué)E輯，信息科學(xué)，2005，35（8）：817-829.

[3] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京：清華大學(xué)出版社，1999.

[4] 焦李成，杜海峰，劉芳，等.免疫優(yōu)化計(jì)算、學(xué)習(xí)與識(shí)別[M].西安： 西安電子科技大學(xué)出版社，2006.