基于正態(tài)云模型的果蠅優(yōu)化算法

杜文軍，孫 斌

(東北電力大學(xué) 教務(wù)處，吉林 吉林132012)

針對(duì)科學(xué)研究中的優(yōu)化問(wèn)題和工程應(yīng)用中的復(fù)雜問(wèn)題，研究人員受自然界中生物種群群體行為的啟發(fā)提出了仿生智能算法，如遺傳算法[1]、細(xì)菌覓食算法[2]、人工魚(yú)群算法[3]、蟻群優(yōu)化算法[4]、灰狼優(yōu)化算法[5]等，這些算法不斷發(fā)展并廣泛應(yīng)用于流水線調(diào)度、電力規(guī)劃、光譜圖像、數(shù)字水印等領(lǐng)域，成為人們解決工程科學(xué)領(lǐng)域的強(qiáng)有力工具.2012年，學(xué)者Pan[6]受果蠅覓食過(guò)程中群體行為協(xié)作機(jī)制的啟發(fā)，提出一種新的智能優(yōu)化仿生算法：果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm，F(xiàn)OA).FOA的實(shí)現(xiàn)通過(guò)模擬果蠅群體的社會(huì)行為獲得問(wèn)題的最優(yōu)解，算法的尋優(yōu)規(guī)則簡(jiǎn)單、參數(shù)少、尋優(yōu)能力好，自提出以來(lái)受到眾多學(xué)者的重視和研究應(yīng)用.對(duì)FOA進(jìn)行改進(jìn)提高算法的效率是FOA研究主要焦點(diǎn)和方向，目前，對(duì)FOA的改進(jìn)路徑包括對(duì)算法的內(nèi)部搜索機(jī)制的改進(jìn)和與其他算法結(jié)合的外部改進(jìn)兩個(gè)方面.對(duì)算法的內(nèi)部改進(jìn)主要對(duì)算法的搜索步長(zhǎng)、最優(yōu)解的候選機(jī)制、果蠅個(gè)體的飛行策略等方面進(jìn)行改進(jìn)，通過(guò)在果蠅個(gè)體的位置更新公式中引入權(quán)重系數(shù)、自適應(yīng)參數(shù)、慣性因子等提高算法的全局搜索能力和局部搜索能力；通過(guò)對(duì)算法中味道濃度參數(shù)的調(diào)整、引入逃逸參數(shù)、將候選解的產(chǎn)生機(jī)制由非線性改為線性等提高算法的尋優(yōu)精度[7～9]；通過(guò)對(duì)算法中果蠅個(gè)體的飛行方向和飛行距離加入隨機(jī)策略和控制策略提高算法中種群的多樣性，避免算法早熟現(xiàn)象[10～12].對(duì)算法的外部改進(jìn)主要通過(guò)調(diào)整算法的種群規(guī)模和種類、與其他算法相結(jié)合設(shè)計(jì)混合式算法等方式，改變算法的種群規(guī)模和種類，在算法的尋優(yōu)過(guò)程中對(duì)不同的子種群采用不同策略提高算法的全局尋優(yōu)能力[13～14]；引入其他智能算法如差分進(jìn)化、混沌理論、禁忌搜索等，改進(jìn)算法的搜索機(jī)制以平衡算法的全局尋優(yōu)能力和局部尋優(yōu)能力[15～17].

本文在對(duì)影響FOA性能的相關(guān)參數(shù)做分析和研究的基礎(chǔ)上，通過(guò)對(duì)相關(guān)文獻(xiàn)的研究對(duì)FOA進(jìn)行改進(jìn)和優(yōu)化，從理論角度分析了FOA的缺陷，針對(duì)現(xiàn)有文獻(xiàn)對(duì)FOA的改進(jìn)研究忽略了算法搜索過(guò)程中味道濃度參數(shù)的隨機(jī)性、模糊性與不穩(wěn)定性，將云模型理論引入FOA的改進(jìn)，利用云模型理論中的正態(tài)云描述算法中味道濃度參數(shù)的隨機(jī)性、模糊性與不穩(wěn)定性屬性，改進(jìn)算法最優(yōu)解的產(chǎn)生機(jī)制，使其自適應(yīng)動(dòng)態(tài)調(diào)整，在算法的嗅覺(jué)搜索階段引入嗅覺(jué)靈敏度因子，由嗅覺(jué)靈敏度因子自適應(yīng)動(dòng)態(tài)調(diào)整算法的搜索步長(zhǎng)，提高算法的全局搜索能力和局部尋優(yōu)能力.最后，將改進(jìn)后的算法應(yīng)用于自動(dòng)組卷系統(tǒng)，通過(guò)與相關(guān)研究文獻(xiàn)的數(shù)據(jù)對(duì)比，對(duì)改進(jìn)后的FOA算法做了性能分析.

1 FOA原理概述及算法表述

1.1 FOA算法原理

自然界中的果蠅在覓食過(guò)程中呈現(xiàn)出顯著的社會(huì)群體行為，在覓食過(guò)程中，果蠅個(gè)體對(duì)腐爛食物的味道及其敏感，在飛行過(guò)程根據(jù)嗅覺(jué)器官感受到的食物發(fā)出味道的濃度，向群體中的其他個(gè)體發(fā)送信息，同時(shí)接受群體中的其它個(gè)體發(fā)送的信息，從而使整個(gè)群體都向距離食物最近的個(gè)體聚攏，繼續(xù)開(kāi)展搜索，循環(huán)往復(fù)直到達(dá)到找到食物的目的[18].果蠅在覓食過(guò)程的行為軌跡，如圖1所示.

圖1 果蠅群體覓食的過(guò)程軌跡圖示[19]

1.2 FOA算法表述

標(biāo)準(zhǔn)FOA算法的主要部分為嗅覺(jué)搜索和視覺(jué)搜索兩個(gè)部分，算法描述如下：

步驟1：初始化參數(shù)

初始算法的種群規(guī)模popsize，設(shè)定種群果蠅個(gè)體的尋優(yōu)范圍LR，因?yàn)镕OA的尋優(yōu)過(guò)程通過(guò)縱坐標(biāo)和橫坐標(biāo)的二維空間搜索，設(shè)定種群中果蠅個(gè)體的初始位置為(X_axis，Y_axis)；設(shè)定算法尋優(yōu)過(guò)程中的最大迭代次數(shù)maxgen及尋優(yōu)半徑初始值RV.算法中果蠅個(gè)體的初始位置為

(1)

步驟2：開(kāi)始迭代，進(jìn)行尋優(yōu)

步驟2.1：嗅覺(jué)搜索

果蠅個(gè)體按照固定步長(zhǎng)更新位置，按照隨機(jī)的方向和距離進(jìn)行搜索，某一時(shí)刻果蠅i的位置為

(2)

步驟2.2：計(jì)算每個(gè)果蠅個(gè)體的味道濃度判定值

(3)

(4)

步驟2.3：評(píng)價(jià)當(dāng)前種群的適應(yīng)度函數(shù)值，計(jì)算種群中每個(gè)果蠅個(gè)體的味道濃度值Smelli，選擇種群味道濃度值最大或者最小的個(gè)體為當(dāng)前種群的最優(yōu)個(gè)體，記錄其位置和味道濃度為

Smelli=Fitness(Si)，

(5)

[bestSmell，bestIndex]=max/min(Smelli).

(6)

步驟3：視覺(jué)搜索

記錄步驟2.1中的最優(yōu)個(gè)體的位置信息和味道濃度值，當(dāng)前種群的個(gè)體向最優(yōu)個(gè)體飛行并更新位置為

SmellBest=bestSmell，

(7)

Y_axis=Y(bestIndex)，

(8)

Y_axis=Y(bestIndex).

(9)

步驟4：迭代尋優(yōu)步驟.

重復(fù)步驟2和步驟3 .若迭代過(guò)程中有更優(yōu)個(gè)體，則以新的個(gè)體的位置和味道濃度更新種群最優(yōu)，否則繼續(xù)嗅覺(jué)搜索過(guò)程直到達(dá)到迭代次數(shù)maxgen結(jié)束算法.

FOA在全局尋優(yōu)能力方面表現(xiàn)突出，但存在收斂速度過(guò)快、易陷入局部最優(yōu)的問(wèn)題[20]，對(duì)高維問(wèn)題的解決能力有限[21].FOA算法中種群規(guī)模、迭代次數(shù)、尋優(yōu)半徑等參數(shù)的選取是影響算法性能的重要因素，研究表明增加種群規(guī)模和迭代次數(shù)可以提高算法的收斂精度，但算法耗費(fèi)的時(shí)間相對(duì)增加，當(dāng)種群規(guī)模、迭代次數(shù)達(dá)到一定程度時(shí)算法可能會(huì)陷入局部最優(yōu)，導(dǎo)致收斂精度不會(huì)進(jìn)一步提高[22].

2 基于云模型的改進(jìn)FOA

(10)

其中：μ(x)表示(0，1)之間具有平穩(wěn)趨勢(shì)的隨機(jī)數(shù).

在FOA中，果蠅個(gè)體的位置是隨機(jī)的，果蠅個(gè)體相對(duì)于原點(diǎn)的距離也是隨機(jī)的，決定了果蠅個(gè)體的味道濃度計(jì)算具有隨機(jī)性和不確定性的特點(diǎn)，算法通過(guò)判斷果蠅個(gè)體的味道濃度決定下一步搜索的尋優(yōu)步長(zhǎng)和方向，而味道濃度的不確定性和隨機(jī)性決定了搜索步長(zhǎng)和方向的模糊性.在FOA中沒(méi)有體現(xiàn)味道濃度隨機(jī)性和模糊性，而且在算法尋優(yōu)過(guò)程中采用固定步長(zhǎng)也使得算法在搜索效率和收斂精度上受到影響.因此，本文對(duì)FOA算法的嗅覺(jué)搜索過(guò)程進(jìn)行改進(jìn)，在果蠅個(gè)體位置更新時(shí)考慮味道濃度的影響，引入味道濃度因子控制算法尋優(yōu)半徑自適應(yīng)調(diào)整，為了體現(xiàn)果蠅個(gè)體味道濃度的模糊性特點(diǎn)，以果蠅個(gè)體到原點(diǎn)的距離為云滴，利用正態(tài)云模型生成確定度為味道濃度參數(shù)的正態(tài)云，使得味道濃度值服從正態(tài)分布，從而使候選解在解空間均勻生成.改進(jìn)后的FOA算法表述如下：

步驟1：初始化

設(shè)定算法種群規(guī)模popsieze的值、算法尋優(yōu)過(guò)程中的最大迭代次數(shù)maxgen、種群果蠅個(gè)體的尋優(yōu)范圍LR，設(shè)置算法種群當(dāng)前迭代代數(shù)g，設(shè)置果蠅個(gè)體搜索步長(zhǎng)的自適應(yīng)調(diào)整范圍參數(shù)RVmin，RVmax，RVmin為搜索半徑的最小值，RVmax為搜索半徑的最大值，初始果蠅個(gè)體的初始位置為(X_axis，Y_axis).

(11)

步驟2：開(kāi)始迭代，進(jìn)行尋優(yōu)

步驟2.1：嗅覺(jué)搜索

果蠅個(gè)體根據(jù)味道濃度因子動(dòng)態(tài)調(diào)整搜索步長(zhǎng)，更新位置，果蠅i的位置更新為

(12)

RVi=SFi×rand()，

(13)

(14)

果蠅個(gè)體的搜索半徑由味道濃度因子SFi動(dòng)態(tài)調(diào)整，當(dāng)果蠅個(gè)體的當(dāng)前味道濃度Si小于當(dāng)前種群的平均味道濃度Savg時(shí)，味道濃度因子為搜索步長(zhǎng)的最小值RVmin加變化量，反之則設(shè)定果蠅個(gè)體的搜索步長(zhǎng)為最大搜索步長(zhǎng).

步驟2.2：計(jì)算果蠅種群的味道濃度參數(shù)

計(jì)算當(dāng)前種群中每個(gè)果蠅個(gè)體到原點(diǎn)的距離DISTi、果蠅種群平均距離DISTavg和最大距離DISTmax，根據(jù)云模型定義可知要使用正態(tài)云模型描述味道濃度參數(shù)的模糊性與隨機(jī)性，就是要以當(dāng)前果蠅種群到原點(diǎn)的平均距離DISTi為期望，以種群到原點(diǎn)的最大距離和最小距離為范圍(DISTmax～DISTmin)生成云滴，從而使果蠅個(gè)體的味道濃度參數(shù)體現(xiàn)出模糊性和隨機(jī)性.計(jì)算過(guò)程為

(15)

(16)

Ex=DISTavg，

En=r1×(DISTmax-DISTavg)×2，

(17)

He=r2×En，

(18)

(19)

其中：r1、r2為控制參數(shù).

步驟2.3：評(píng)價(jià)當(dāng)前種群的適應(yīng)度函數(shù)值

計(jì)算種群中每個(gè)果蠅個(gè)體的味道濃度值Smelli，選擇種群味道濃度值最大或者最小的個(gè)體為當(dāng)前種群的最優(yōu)個(gè)體，記錄其位置和味道濃度為

Smelli=Fitness(Si)，

(20)

[bestSmell，bestIndex]=max/min(Si).

(21)

步驟3：視覺(jué)搜索

記錄最優(yōu)果蠅個(gè)體的位置和味道濃度值，當(dāng)前種群的個(gè)體向最優(yōu)個(gè)體飛行并更新位置為

X_axis=X(bestIndex)，

(22)

Y_axis=Y(bestIndex)，

(23)

步驟4：迭代尋優(yōu)

若當(dāng)前迭代代數(shù)gSmellBset，則以新的個(gè)體的位置和味道濃度更新種群最優(yōu)，否則繼續(xù)嗅覺(jué)搜索過(guò)程直到達(dá)到迭代次數(shù)g=maxgen結(jié)束算法.

3 改進(jìn)FOA算法應(yīng)用及實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證改進(jìn)FOA算法的有效性和算法性能，將改進(jìn)后的FOA算法應(yīng)用于自動(dòng)組卷系統(tǒng)，通過(guò)與相關(guān)文獻(xiàn)[25～26]改進(jìn)的FOA算法的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行比較，從組卷的精度和效率等方面評(píng)估改進(jìn)FOA算法收斂性能.

3.1 試卷的數(shù)學(xué)模型

試卷中的試題主要包含以下屬性：(1)試題編號(hào)(試題的唯一標(biāo)識(shí))；(2)題型編號(hào)(1-單選題，2-多選題，3-判斷題，4-填空題，5-問(wèn)答題)；(3)試題難度系數(shù)(學(xué)生的失分率)；(4)試卷區(qū)分度(區(qū)分學(xué)生水平能力)；(5)考試時(shí)間；(6)題分.

將一份試卷映射為一個(gè)果蠅個(gè)體，試卷中每道試題由上述6個(gè)屬性約束，構(gòu)成一個(gè)屬性向量(題號(hào)a1，題型a2，難度a3，區(qū)分度a4，時(shí)間a5，題分a6)，含有m道試題的試卷可以看作m×6矩陣A.

其中：aij為第i道試題的第j個(gè)屬性.

試卷模型的約束條件如下：

3.2 約束函數(shù)

圖2 標(biāo)準(zhǔn)FOA 和改進(jìn)后FOA 算法收斂對(duì)比

3.3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)過(guò)程中設(shè)置算法的種群規(guī)模為100，最大迭代次數(shù)為200，設(shè)置搜索半徑的最小值和最大值為2和5.設(shè)定一份試卷為一個(gè)果蠅個(gè)體，每份試卷的試題數(shù)量分別取30、50和70，經(jīng)過(guò)20次獨(dú)立運(yùn)行的結(jié)果，如表1所示.采用正態(tài)云模型改進(jìn)后的FOA果蠅個(gè)體在尋優(yōu)過(guò)程中，味道濃度因子自適應(yīng)調(diào)整搜索步長(zhǎng)，對(duì)于味道濃度值大于平均味道濃度值的個(gè)體，在尋優(yōu)過(guò)程中被賦予最大搜索半徑，加快了算法收斂速度；而對(duì)于味道濃度值小于平均味道濃度值的個(gè)體，在尋優(yōu)過(guò)程中根據(jù)味道濃度因子被賦予自適應(yīng)調(diào)整的搜索半徑，提高了算法的收斂精度，因而在優(yōu)化最小值Smin、平均值Smax、標(biāo)準(zhǔn)差Sst等表現(xiàn)出較好的效果.另外，在算法迭代過(guò)程中，以果蠅個(gè)體到原點(diǎn)的平均距離為期望生成云滴，使產(chǎn)生的可選解呈正態(tài)分布，促使算法可選解產(chǎn)生機(jī)制呈現(xiàn)出隨機(jī)性和模糊性，提高算法的全局尋優(yōu)能力.基于云模型的FOA算法在搜索初期，由于果蠅個(gè)體的味道濃度值賦予了較大的尋優(yōu)半徑，使得算法能夠較快的收斂，而在搜索的后期根據(jù)味道濃度因子自適應(yīng)調(diào)整步長(zhǎng)，有效的避免了算法陷入局部最優(yōu)，如圖2所示.

表1 基于云模型FOA與標(biāo)準(zhǔn)FOA及文獻(xiàn)改進(jìn)FOA收斂精度對(duì)比(popsize=100)

4 總 結(jié)

本文將云模型理論中的正態(tài)云模型應(yīng)用于FOA的優(yōu)化改進(jìn)，在算法的嗅覺(jué)搜索階段，引入了味道濃度影響因子，動(dòng)態(tài)自適應(yīng)調(diào)整果蠅個(gè)體的尋優(yōu)步長(zhǎng)，提高了算法的收斂速度，用正態(tài)云模型生成味道濃度參數(shù)云滴，改進(jìn)算法最優(yōu)解的產(chǎn)生機(jī)制，體現(xiàn)了算法的隨機(jī)性和模糊性，提高了算法的收斂精度，防止算法陷入局部最優(yōu).從算法在自動(dòng)組卷系統(tǒng)的應(yīng)用表明改進(jìn)后的算法在收斂速度、收斂精度方面都有所提高.