杜文軍，孫 斌

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

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

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

1 FOA原理概述及算法表述

1.1 FOA算法原理

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

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

1.2 FOA算法表述

標準FOA算法的主要部分為嗅覺搜索和視覺搜索兩個部分，算法描述如下：

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

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

(1)

步驟2：開始迭代，進行尋優(yōu)

步驟2.1：嗅覺搜索

果蠅個體按照固定步長更新位置，按照隨機的方向和距離進行搜索，某一時刻果蠅i的位置為

(2)

步驟2.2：計算每個果蠅個體的味道濃度判定值

(3)

(4)

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

Smelli=Fitness(Si)，

(5)

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

(6)

步驟3：視覺搜索

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

SmellBest=bestSmell，

(7)

Y_axis=Y(bestIndex)，

(8)

Y_axis=Y(bestIndex).

(9)

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

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

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

2 基于云模型的改進FOA

(10)

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

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

步驟1：初始化

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

(11)

步驟2：開始迭代，進行尋優(yōu)

步驟2.1：嗅覺搜索

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

(12)

RVi=SFi×rand()，

(13)

(14)

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

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

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

(15)

(16)

Ex=DISTavg，

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

(17)

He=r2×En，

(18)

(19)

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

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

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

Smelli=Fitness(Si)，

(20)

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

(21)

步驟3：視覺搜索

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

X_axis=X(bestIndex)，

(22)

Y_axis=Y(bestIndex)，

(23)

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

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

3 改進FOA算法應(yīng)用及實驗結(jié)果分析

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

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

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

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

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

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

3.2 約束函數(shù)

圖2 標準FOA 和改進后FOA 算法收斂對比

3.3 實驗結(jié)果及分析

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

表1 基于云模型FOA與標準FOA及文獻改進FOA收斂精度對比(popsize=100)

4 總 結(jié)

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