[發(fā)明專(zhuān)利]一種基于模擬退火與高斯擾動(dòng)的煙花算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710160095.7
• 申請(qǐng)日: 2017-03-17
• 公開(kāi)（公告）號(hào): CN106776469A
• 公開(kāi)（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 李席廣;韓守飛;拱長(zhǎng)青
• 申請(qǐng)（專(zhuān)利權(quán)）人: 沈陽(yáng)航空航天大學(xué)
• 主分類(lèi)號(hào): G06F17/00
• 分類(lèi)號(hào): G06F17/00;G06N3/00
• 代理公司: 沈陽(yáng)維特專(zhuān)利商標(biāo)事務(wù)所(普通合伙)21229
• 代理人: 甄玉荃

技術(shù)領(lǐng)域:

本發(fā)明涉及一種基于模擬退火與高斯擾動(dòng)的煙花算法。

背景技術(shù):

煙花算法(FWA)是譚營(yíng)教授于2010年因受到煙花在夜空中爆炸的啟發(fā)而提出的一種群體智能算法。FWA通過(guò)模擬煙花在空中爆炸的這種行為建立相應(yīng)的數(shù)學(xué)模型，通過(guò)引入隨機(jī)因素和選擇策略形成一種并行爆炸式搜索方式，進(jìn)而發(fā)展為能夠求解復(fù)雜問(wèn)題最優(yōu)解的全局概率搜索方法。FWA與一般群體智能優(yōu)化算法類(lèi)似，首先隨機(jī)初始化N個(gè)煙花，然后每個(gè)煙花經(jīng)歷爆炸和變異操作，并應(yīng)用映射規(guī)則保證變異后的個(gè)體仍然在可行域內(nèi)，最后保留最優(yōu)的煙花，然后應(yīng)用選擇策略從剩下的煙花中選擇出N-1個(gè)煙花，同最優(yōu)的煙花組成群體進(jìn)行下一次迭代。目前，煙花算法已被應(yīng)用到許多實(shí)際優(yōu)化問(wèn)題求解中，應(yīng)用領(lǐng)域包括方程組求解、非負(fù)矩陣分解的計(jì)算、垃圾郵件檢測(cè)算法中參數(shù)優(yōu)化等。

煙花算法的基本原則：若煙花對(duì)應(yīng)的適應(yīng)度函數(shù)值越小，則該煙花爆炸產(chǎn)生的火花數(shù)量越多，爆炸幅度越小；反之，若煙花對(duì)應(yīng)的適應(yīng)度函數(shù)值越大，則該煙花爆炸產(chǎn)生的火花數(shù)量越少，且爆炸幅度越大。

一般地，煙花算法由爆炸算子、變異爆炸、映射規(guī)則和選擇策略四部分組成。

基于以上的原則，煙花算法的基本步驟可以概括如下：

步驟1隨機(jī)初始化種群；

步驟2運(yùn)用爆炸算子產(chǎn)生火花；

步驟3運(yùn)用變異算子產(chǎn)生火花；

步驟4運(yùn)用映射規(guī)則將越界的火花拉回可行域內(nèi)；

步驟5利用選擇策略從所有的個(gè)體(煙花和火花)選出下一代群體；

步驟6是否滿(mǎn)足終止條件，滿(mǎn)足則停止，不滿(mǎn)足則返回步驟2繼續(xù)搜索。

與其他智能優(yōu)化算法一樣，煙花算法也存在后期收斂速度慢、易陷入局部最優(yōu)解，并且隨著位置偏移的增大，煙花算法的穩(wěn)定性差等問(wèn)題，本發(fā)明為了解決上述問(wèn)題，將模擬退火的思想引入到煙花算法中，并對(duì)煙花算法中某些單個(gè)的煙花個(gè)體進(jìn)行高斯擾動(dòng)，提出了一種基于模擬退火與高斯擾動(dòng)的煙花算法(SAFWA)。

發(fā)明內(nèi)容

為了解決煙花算法也存在后期收斂速度慢、易陷入局部最優(yōu)解，并且隨著位置偏移的增大，煙花算法的穩(wěn)定性差等問(wèn)題，本發(fā)明提出了一種基于模擬退火與高斯擾動(dòng)的煙花算法，在收斂速度和計(jì)算精度以及穩(wěn)定性發(fā)面這種算法均優(yōu)于煙花算法(FWA)、標(biāo)準(zhǔn)粒子群算法(SPSO)、增強(qiáng)煙花算法。

本發(fā)明解決其技術(shù)問(wèn)題所采用的技術(shù)方案是：

一種基于模擬退火與高斯擾動(dòng)的煙花算法，其特征是包括如下步驟：

步驟1：隨機(jī)給煙花的位置賦值，計(jì)算煙花的適應(yīng)度值，生成初始種群；

步驟2：設(shè)置煙花個(gè)數(shù)N，最大火花數(shù)Max，最小火花數(shù)Min，需要求解函數(shù)的可行域D，高斯變異的火花數(shù)N_g，爆炸幅度之和以及最大的函數(shù)評(píng)估次數(shù)It_max；

步驟3：找出初始種群里面適應(yīng)值最差的個(gè)體，記錄其位置信息P_worst；

步驟4：初始化初始溫度T₀、終止溫度T_f、退火系數(shù)a和最大迭代次數(shù)I_max；

步驟5：對(duì)當(dāng)前適應(yīng)值最差的個(gè)體進(jìn)行高斯變異，得到一個(gè)新解x_new：

x_new^k＝p_worst^k*g,k＝1,2,...,d

其中，p_worst^k表示最差個(gè)體的第k維，g是服從均值和方差都為1的正態(tài)分布，即g～N(1,1)，d表示每個(gè)個(gè)體的設(shè)置的維數(shù)；

步驟6：比較高斯擾動(dòng)前后的適應(yīng)值的大小；

步驟7：如果高斯擾動(dòng)后的適應(yīng)度值更優(yōu)(對(duì)最小化問(wèn)題，更優(yōu)就是適應(yīng)度值更小)，則接受高斯擾動(dòng)后的解，并且更新相應(yīng)的位置；如果高斯擾動(dòng)后的目標(biāo)值沒(méi)有高斯擾動(dòng)前的優(yōu)，則以一定的概率p去接受該解:

其中，Δx是高斯擾動(dòng)后的適應(yīng)度值和高斯擾動(dòng)前的適應(yīng)度值的差值，T為當(dāng)前的溫度，r是隨機(jī)產(chǎn)生的一個(gè)0和1之間的隨機(jī)數(shù)。

步驟8：執(zhí)行退溫操作：

T＝T*a

其中T的初始值為T(mén)₀；

步驟9：若滿(mǎn)足停止條件(達(dá)到設(shè)置的最大迭代次數(shù)或者溫度達(dá)到最低溫度)，則搜索停止，輸出優(yōu)化后的結(jié)果，否則，轉(zhuǎn)到步驟5繼續(xù)尋找適應(yīng)度值更優(yōu)的位置；