強(qiáng)化最優(yōu)和最差狼的郊狼優(yōu)化算法及其二次指派問題應(yīng)用

張新明 王豆豆 陳海燕 毛文濤 竇 智 劉尚旺

摘 要：針對郊狼優(yōu)化算法（COA）優(yōu)化性能不足的問題，提出一種強(qiáng)化最優(yōu)和最差狼的COA（BWCOA）方法。首先，對于組內(nèi)最差郊狼的成長，在最優(yōu)郊狼引導(dǎo)的基礎(chǔ)上引入全局最優(yōu)郊狼引導(dǎo)操作，以提高最差郊狼的社會適應(yīng)能力（局部搜索能力）;然后，在組內(nèi)最優(yōu)郊狼的成長過程中嵌入一種隨機(jī)擾動操作，即以郊狼之間的隨機(jī)擾動促進(jìn)成長，發(fā)揮組內(nèi)每個(gè)郊狼的能動性，提高種群的多樣性進(jìn)而強(qiáng)化全局搜索能力;

最后，組內(nèi)其他郊狼的成長方式保持不變。將BWCOA運(yùn)用到復(fù)雜函數(shù)優(yōu)化和以醫(yī)院科室布局為例的二次指派問題（QAP）中。

在CEC-2014復(fù)雜函數(shù)上的實(shí)驗(yàn)結(jié)果表明，與COA以及其他最先進(jìn)的算法相比，BWCOA獲得1.63的平均均值排名和Friedman檢驗(yàn)中1.68的秩均值，均排名第一。另外，在6組QAP上的實(shí)驗(yàn)結(jié)果表明，BWCOA獲得了5次均值最優(yōu)的結(jié)果。

實(shí)驗(yàn)結(jié)果均表明BWCOA具有更強(qiáng)的競爭性。

關(guān)鍵詞： 智能優(yōu)化算法;郊狼優(yōu)化算法;全局最優(yōu);二次指派問題;醫(yī)院科室定位

中圖分類號：TP181

文獻(xiàn)標(biāo)志碼：A

Abstract：? In view of poor performance of Coyote Optimization Algorithm （COA）， a Best and Worst coyotes strengthened COA （BWCOA） was proposed. Firstly， for growth of the worst coyote in the group， a global optimal coyote guiding operation was introduced on the basis of the optimal coyote guidance to improve the social adaptability （local search ability） of the worst coyote. Then， a random perturbation operation was embedded in the growth process of the optimal coyote in the group， which means using the random perturbation between coyotes to promote the development of the coyotes and make full play of the initiative of each coyotes in the group to improve the diversity of the population and thus to enhance the global search ability， while the growing pattern of the other coyotes kept unchanged. BWCOA was applied to complex function optimization and Quadratic Assignment Problem （QAP） using hospital department layout as an example. Experimental? results on CEC-2014 complex functions show that compared with COA and other state-of-the-art algorithms， BWCOA obtains 1.63 in the average ranking and 1.68 rank mean in the Friedman test， both of the results are the best. Experimental? results on 6 QAP benchmark sets show that BWCOA obtains the best mean values for 5 times. These prove that BWCOA is more competitive.Key words：? intelligent optimization algorithm; Coyote Optimization Algorithm （COA）; global optimal; Quadratic Assignment Problem （QAP）; hospital department location

0 引言

現(xiàn)實(shí)生活中隨處存在著優(yōu)化問題，以往人們依靠生活經(jīng)驗(yàn)和數(shù)學(xué)分析的方法來求得最優(yōu)解。但隨著科學(xué)技術(shù)的發(fā)展，需要解決的優(yōu)化問題越來越復(fù)雜，越來越多樣，傳統(tǒng)的方法不能很好解決這些問題[1]。因此，許多受某些自然現(xiàn)象和生物信息啟發(fā)的智能優(yōu)化算法被提出，如粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法[2]、人工免疫算法（Artificial Immune Algorithm， AIA）[1]、生物地理學(xué)優(yōu)化（Biogeography-Based Optimization， BBO）算法[3]、灰狼優(yōu)化（Grey Wolf Optimizer， GWO）算法[4]、蛙跳算法（Shuffled Frog Leading Algorithm， SFLA）[5]和螢火蟲算法（Firefly Algorithm， FA）[6]。這些算法易于實(shí)現(xiàn)，能較好地解決各種復(fù)雜的優(yōu)化問題，受到廣大學(xué)者的關(guān)注。但是“無免費(fèi)午餐定理”[4]表明某個(gè)算法不可能解決所有的問題，因此，新算法和改進(jìn)的算法不斷地產(chǎn)生來解決復(fù)雜優(yōu)化問題。

二次指派問題（Quadratic Assignment Problem， QAP）是一個(gè)復(fù)雜的優(yōu)化問題，在不同的領(lǐng)域中有廣泛的應(yīng)用，比如醫(yī)院科室布局問題[7]、求解物流設(shè)施[8]、任務(wù)分配問題和航班調(diào)度問題等[9]。用智能優(yōu)化算法來解決QAP也是熱點(diǎn)之一，比如使用混合分布估計(jì)算法求解物流設(shè)施QAP，利用水循環(huán)優(yōu)化算法求解QAP，提出混合搜索算法解決QAP等[8]。

受分布在北美的犬種的靈感，2018年P(guān)ierezan等[10]提出了郊狼優(yōu)化算法（Coyote Optimization Algorithm， COA），模擬郊狼群生活、成長、生死、被組驅(qū)離和接納等現(xiàn)象。在COA中，每一頭郊狼代表一個(gè)候選解，每個(gè)解向量由郊狼的社會狀態(tài)因子構(gòu)成，這些狀態(tài)因子包括郊狼內(nèi)在因素和外在因素，每一個(gè)狀態(tài)因素代表一個(gè)決策變量，用社會適應(yīng)能力來衡量一頭郊狼的好壞。

雖然COA與GWO都是狼群優(yōu)化算法，但COA的不同之處在于：GWO根據(jù)動物的等級和狩獵方式來進(jìn)行搜索，而COA關(guān)注狼的社會結(jié)構(gòu)和文化背景;GWO中使用三頭等級較高的灰狼來引導(dǎo)其他的灰狼捕獵，而COA中僅僅使用一頭最好的狼來引導(dǎo)郊狼成長。

COA與SFLA在結(jié)構(gòu)上比較相似，都是把一個(gè)種群分成幾組子群來進(jìn)行迭代，但SFLA的子群中只對最差的青蛙進(jìn)行更新，而COA對子群中的每一頭郊狼實(shí)施成長過程。

COA是一種新穎的智能優(yōu)化算法，有著獨(dú)特的搜索模型和框架，有較好的開采能力和探索能力。但由于COA提出時(shí)間短，仍有許多地方需要完善以及拓展應(yīng)用領(lǐng)域。

因此，本文提出了一種強(qiáng)化最優(yōu)和最差狼的COA（Best and Worst coyotes strengthened COA， BWCOA）來增強(qiáng)COA的優(yōu)化性能。

在COA的基礎(chǔ)上，對于組內(nèi)最差郊狼成長，引入全局最優(yōu)郊狼引導(dǎo)操作，提高局部搜索能力。對于組內(nèi)最優(yōu)郊狼成長，嵌入一種隨機(jī)擾動操作，提高種群的多樣性進(jìn)而強(qiáng)化全局搜索能力。如此形成BWCOA。

另外，將COA的貪心算法替換為靜態(tài)貪心算法，以提高算法的穩(wěn)定性和增強(qiáng)全局搜索能力;并將種群分組參數(shù)設(shè)置為動態(tài)調(diào)整提高可操作性。

整個(gè)迭代完成之后，選擇最能適應(yīng)環(huán)境的郊狼作為問題的全局解決方案。從算法1可以看出，COA有以下優(yōu)點(diǎn)：1）COA把郊狼群隨機(jī)分為多個(gè)子狼群，有較好的搜索模型和框架，與PSO等算法相比，具有更好的探索能力;2）通過alpha狼和cult對郊狼的成長引導(dǎo)，COA具有較強(qiáng)的開采能力;3）通過出生死亡和環(huán)境因素影響的變異操作，COA具有較強(qiáng)的探索能力;4）COA對組內(nèi)每個(gè)解進(jìn)行更新，與SFLA相比，有更高的獲得最優(yōu)解的概率;5）隨機(jī)分組，并在每次演化中，子組隨機(jī)選擇驅(qū)離和接受郊狼，使得種群多樣性增強(qiáng);6）采用貪心算法（步驟7））獲得成長后的郊狼又參與隨后郊狼的成長過程，可以加速收斂，這種貪心算法稱為動態(tài)貪心算法。

2 強(qiáng)化最優(yōu)和最差狼的郊狼優(yōu)化算法

2.1 COA存在的問題及改進(jìn)的動機(jī)

雖然COA有許多優(yōu)點(diǎn)，但由于提出時(shí)間短，仍有許多地方需要完善，如在處理某些復(fù)雜優(yōu)化問題時(shí)，優(yōu)化性能不足。從算法1可以看出，在組內(nèi)郊狼成長中，依靠組內(nèi)最優(yōu)郊狼的引導(dǎo)，可能會導(dǎo)致算法陷入局部最優(yōu)。郊狼的出生和死亡操作雖有一定的全局搜索能力，但在處理一些復(fù)雜優(yōu)化問題時(shí)，探索能力不足。另外，依據(jù)行政管理學(xué)的“抓兩頭帶中間”的思想，即在一個(gè)單位人員管理中，抓好先進(jìn)和后進(jìn)就可以帶動中間人員的積極性，以便提高整個(gè)單位人員的工作效率。因此，為了提高郊狼算法的優(yōu)化性能，本文提出了一種強(qiáng)化最優(yōu)和最差狼的COA（BWCOA）。

2.2 全局最優(yōu)郊狼引導(dǎo)強(qiáng)化最差郊狼

在COA中，每組郊狼生長是根據(jù)組內(nèi)的最優(yōu)郊狼和組文化趨勢以及兩頭隨機(jī)郊狼來更新的，局部搜索能力受限。本文在最差郊狼在組內(nèi)成長過程中，嵌入了一種全局最優(yōu)郊狼引導(dǎo)操作。如式（10）和（11）所示：

其中：rand（1，D）是D維的隨機(jī)變量;Cg是全局最優(yōu)郊狼;Cl是組內(nèi)最優(yōu)郊狼;Cw是組內(nèi)最差的郊狼。選擇對最差郊狼進(jìn)行全局最優(yōu)郊狼的引導(dǎo)，可以保證最差的郊狼向著最優(yōu)位置趨近，提高算法的局部搜索能力。

另外，為了保證算法在開采和探索之間保持平衡，在搜索的前期，采用式（10）進(jìn)行組內(nèi)最差郊狼成長操作，從式（10）可以看出，在全局最優(yōu)郊狼、組內(nèi)最優(yōu)郊狼和組內(nèi)最差郊狼的差值的基礎(chǔ)上乘以系數(shù)（2*rand（1，D）-1），其范圍為-1到1，且每一維都在隨機(jī)擾動，在組內(nèi)最差郊狼的每一狀態(tài)因子周圍大范圍的搜索，以此在提高算法局部搜索能力的同時(shí)兼顧全局搜索能力。在搜索的后期，更注重局部開采，使用式（11）來進(jìn)行組內(nèi)最差郊狼成長操作。從式（11）可以看出，在全局最優(yōu)郊狼、組內(nèi)最優(yōu)郊狼和組內(nèi)最差郊狼的差值的基礎(chǔ)上乘以系數(shù)（0.5+0.5*rand），其范圍為0.5到1，且此系數(shù)對于每一維都是一樣的，在組內(nèi)最差郊狼的周圍小范圍地搜索，更強(qiáng)化算法的局部搜索能力。

2.3 隨機(jī)擾動強(qiáng)化最優(yōu)郊狼

在COA中，郊狼的生死算子能獲得全局搜索能力，從算法1可以看出，組內(nèi)郊狼成長算子能獲得局部搜索能力，但是每一次迭代，組內(nèi)郊狼成長執(zhí)行Np*Nc次，而郊狼的生死只執(zhí)行Np次。全局搜索能力與局部搜索能力不能很好地保持平衡。而依據(jù)現(xiàn)代智能理論，一個(gè)優(yōu)化算法只有在全局搜索能力與局部搜索能力達(dá)到平衡時(shí)，才能獲得最佳的優(yōu)化性能。因此，為了提高全局搜索能力，在子群的最優(yōu)郊狼成長過程中嵌入一種隨機(jī)擾動操作見式（12）：

其中：a和b是在種群中隨機(jī)選擇的兩頭郊狼的標(biāo)號。從式（12）可以看出，組內(nèi)最優(yōu)郊狼受兩部分的影響：第一部分是組內(nèi)最差郊狼;第二部分是全局最優(yōu)郊狼和最差郊狼的差值加上兩個(gè)隨機(jī)郊狼的差值。全局最優(yōu)郊狼和組內(nèi)最差郊狼的區(qū)別較大，兩者相減范圍較大，再加上兩個(gè)隨機(jī)選擇的郊狼差值，使得郊狼的成長過程不僅受到全局最優(yōu)郊狼的影響，而且也受子群中郊狼的相互影響，增加了種群的多樣性，進(jìn)而提高全局搜索能力。

3.4 收斂性分析

本文是對COA的改進(jìn)算法，因此，本節(jié)只對BWCOA和COA進(jìn)行收斂性分析。兩種算法在CEC-2014基準(zhǔn)函數(shù)上做實(shí)驗(yàn)，公共參數(shù)如下：D=10，MaxNFs為10000*D，Run為51，N為40。選取部分函數(shù)做收斂性分析，選取的函數(shù)與3.1節(jié)相同。代表性函數(shù)的收斂如圖3所示。

從圖3可以看出，在6個(gè)函數(shù)上，BWCOA的收斂速度都明顯優(yōu)于COA的收斂速度。在單峰函數(shù)（圖3（a））上，BWCOA的收斂速度大幅度地優(yōu)于COA的收斂速度，特別是在迭代25000次之后，表明BWCOA提高了算法的開采能力和尋優(yōu)精度;在多峰函數(shù)（圖3（b）、（c）），BWCOA的收斂速度都比COA的收斂速度快，特別是在迭代5000次之后，BWCOA的收斂速度大幅度地優(yōu)于COA，表明BWCOA提高了探索能力，很好地平衡探索與開采;在混合函數(shù)（圖3（e）和組合函數(shù)（圖3（f））上，BWCOA的收斂速度比COA的收斂速度快，特別是在迭代2000次之后，BWCOA的收斂速度大幅度地優(yōu)于COA，表明BWCOA在處理復(fù)雜優(yōu)化函數(shù)時(shí)，表現(xiàn)優(yōu)異。因此，BWCOA提高了COA的收斂速度。

3.5 在二次指派問題上的應(yīng)用

QAP是多項(xiàng)式時(shí)間內(nèi)不可解的組合優(yōu)化問題，最早由Koopmans和Beckmann在1957年提出[17]，QAP可以描述為將一組設(shè)施分配給一組位置的問題，這些位置之間有給定的距離，且設(shè)施之間有給定的流。求解QAP是根據(jù)任意兩個(gè)位置之間的距離和任意兩個(gè)設(shè)備之間的流，將一組設(shè)備分配到一組位置的問題，以最小化成本見式（13）。

常用兩個(gè)矩陣來表示設(shè)施（F）和位置（L），每個(gè)矩陣的大小為T*T。 fxy是每對設(shè)施之間的流或權(quán)重，代表從設(shè)施x到設(shè)施y的流或權(quán)重。dxy表示位置x到位置y的距離。

QAP可以應(yīng)用到許多實(shí)際的問題上，例如，醫(yī)院科室定位的建模，以優(yōu)化科室的配置，減少每個(gè)病人的時(shí)間消耗，提高醫(yī)院為病人服務(wù)的效率。例如一個(gè)簡單的例子，在一間醫(yī)院的某單層，

在某單層中，每個(gè)科室的重要程度不一樣，人流多的科室比較重要;相反，人流少的科室次重要，兩個(gè)科室之間的重要度由流表示。矩陣F代表兩個(gè)部門之間的流，矩陣L代表兩個(gè)位置之間的距離。下一步是將這組科室分配到這組地點(diǎn)，使患者在科室之間的成本最小化。

使用BWCOA解決QAP，首先應(yīng)解決如何將用于連續(xù)優(yōu)化問題的BWCOA用于離散優(yōu)化問題。本文借鑒文獻(xiàn)[7]的方法，每個(gè)解的維數(shù)代表QAP中位置或者設(shè)施的數(shù)量，每個(gè)解代表不同位置的排列，對應(yīng)一種位置分配方案，通過算法循環(huán)迭代，找到最優(yōu)的分配方案。假設(shè)一個(gè)QAP，有10個(gè)設(shè)施點(diǎn)，需要分配到10個(gè)位置點(diǎn)，如圖4（a）所示。1號設(shè)施分配到8號位置，2號設(shè)施分配到5號位置，3號設(shè)施分配到1號位置，等等。QAP被認(rèn)為是一個(gè)排列離散問題，因此當(dāng)智能優(yōu)化算法解決QAP時(shí)，使用最大實(shí)值將實(shí)值映射成排列序列，如圖4（b）所示。

本文用BWCOA來解決QAP，對比算法采用COA、IPSO（Improved PSO）和IFA（Improved Firefly Algorithm）。IPSO和IFA來自網(wǎng)站（http：//yarpiz.com/359/ ypap104-quadratic-assignment-problem），是PSO和FA的改進(jìn)算法，擅長解決QAP，因此，具有較強(qiáng)的可比性。

4種算法的參數(shù)設(shè)置如下：N是100，Run為30，最大迭代次數(shù)是1000。實(shí)驗(yàn)記錄了每個(gè)算法在數(shù)據(jù)集上的均值、方差、最大值和最小值。在表3中，基準(zhǔn)數(shù)據(jù)來自文獻(xiàn)[7]，一直作為解決QAP的標(biāo)準(zhǔn)集。

從表3可以看出：在數(shù)據(jù)集chr15a的方差、chrl8b的均值、chr20a的最小值和chr20b的最小值上，BWCOA排第二，其他的均排第一。總的來說， BWCOA能較好地處理QAP。

4 結(jié)語

COA是最近提出的一種智能優(yōu)化算法，需要改進(jìn)完善和擴(kuò)展應(yīng)用領(lǐng)域，因此，本文針對COA優(yōu)化性能不佳，提出了一種改進(jìn)的COA，即強(qiáng)化最優(yōu)和最差狼的COA（BWCOA），并應(yīng)用于QAP。首先，為了提高收斂速度，對于最差郊狼，在組內(nèi)最優(yōu)郊狼引導(dǎo)的基礎(chǔ)上，嵌入全局最優(yōu)郊狼引導(dǎo)操作。其次，為了進(jìn)一步彌補(bǔ)全局搜索能力不足，對于組內(nèi)的最優(yōu)郊狼，在其成長過程中嵌入一種隨機(jī)擾動操作，即以郊狼的相互作用影響成長過程，增強(qiáng)種群的多樣性。最后，組內(nèi)其他郊狼仍采用原成長方式不變，并采用靜態(tài)貪心算法。CEC-2014基準(zhǔn)函數(shù)的實(shí)驗(yàn)結(jié)果表明，與COA和其他對比算法相比，在總體上，BWCOA的優(yōu)化性能優(yōu)于對比算法。QAP的實(shí)驗(yàn)結(jié)果也表明與對比算法相比，BWCOA有更強(qiáng)的競爭性。在未來，將進(jìn)一步完善COA，提高優(yōu)化性能，并擴(kuò)展其應(yīng)用領(lǐng)域。

參考文獻(xiàn)（References）

[1] SAVSANI P， JHALA R L， SAVSANI V. Effect of hybridizing Biogeography-Based Optimization （BBO） technique with Artificial Immune Algorithm （AIA） and Ant Colony Optimization （ACO） [J]. Applied Soft Computing， 2014， 21： 542-553.

[2] 張新明， 王霞， 涂強(qiáng)， 等. 融合榜樣學(xué)習(xí)和反向?qū)W習(xí)的粒子群優(yōu)化算法[J]. 河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 45（6）： 91-99. （ZHANG X M， WANG X， TU Q， et al. Particle swarm optimization algorithm combing example learning and opposition learning[J]. Journal of Henan Normal University （Natural Science Edition）， 2017， 45（6）： 91-99.）

[3] 張新明， 康強(qiáng)， 王霞， 等. 差分遷移和趨優(yōu)變異的生物地理學(xué)優(yōu)化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2018， 39（6）： 1168-1177. （ZHANG X M， KANG Q， WANG X， et al. Biogeography-based optimization with differential migration and global-best mutation[J]. Journal of Chinese Computer Systems， 2018， 39（6）： 1168-1177.）

[4] MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software， 2014， 69： 46-61.

[5] 陳暄， 徐見煒， 龍丹. 基于蟻群優(yōu)化-蛙跳算法的云計(jì)算資源調(diào)度算法[J]. 計(jì)算機(jī)應(yīng)用， 2018， 38（6）： 1670-1674， 1681. （CHEN X， XU J W， LONG D. Resource scheduling algorithm of cloud computing based on ant colony optimization-shuffled frog leading algorithm[J]. Journal of Computer Applications， 2018， 38（6）： 1670-1674， 1681.）

[6] AYDILEK I B. A hybrid firefly and particle swarm optimization algorithm for computationally expensive numerical problems[J]. Applied Soft Computing， 2018， 66： 232-249.

[7] ABDEL-BASSET M， MANOGARAN G， EL-SHAHAT D， et al. Integrating the whale algorithm with Tabu search for quadratic assignment problem： a new approach for locating hospital departments[J]. Applied Soft Computing， 2018， 73： 530-546.

[8] 戢守峰， 羅蓉娟， 孫琦， 等. 一種求解物流設(shè)施二次分配問題的混合分布估計(jì)算法[J]. 運(yùn)籌與管理， 2018， 27（1）： 74-83. （JI S F， LUO R J， SUN Q， et al. A hybrid estimation of distribution algorithm for quadratic assignment problem[J]. Operations Research and Management Science， 2018， 27（1）： 74-83.）

[9] 牟廉明， 戴錫笠， 李坤， 等. 求解二次指派問題的最優(yōu)迭代最大最小螞蟻算法[J]. 計(jì)算機(jī)應(yīng)用， 2014， 34（1）： 199-203. （MOU L M， DAI X L， LI K， et al. Optimal iterative max-min ant system for solving quadratic assignment problem[J]. Journal of Computer Applications， 2014， 34（1）： 199-203.）

[10] PIEREZAN J， COELHO L D S. Coyote optimization algorithm： a new metaheuristic for global optimization problems[C]// Proceedings of the 2018 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2018： 1-8.

[11] LIANG J J， QU B Y， SUGANTHAN P N. Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization[EB/OL]. [2018-12-10]. http：//bee22.com/manual/tf_images/Liang%20CEC2014.pdf.

[12] TANG D， YANG J， DONG S， et al. A levy flight-based shuffled frog-leaping algorithm and its applications for continuous optimization problems[J]. Applied Soft Computing， 2016， 49： 641-662.

[13] GARG V， DEEP K. Performance of Laplacian biogeography-based optimization algorithm on CEC 2014 continuous optimization benchmarks and camera calibration problem[J]. Swarm and Evolutionary Computation， 2016， 27： 132-144.

[14] ASSAD A， DEEP K. A hybrid harmony search and simulated annealing algorithm for continuous optimization[J]. Information Sciences， 2018， 450： 246-266.

[15] GUPTA S， DEEP K. A novel random walk grey wolf optimizer[J]. Swarm and Evolutionary Computation， 2019， 44： 101-112.

[16] 王艷嬌， 史新夢. 跳躍海豚群算法[J/OL]. 控制理論與應(yīng)用 [2019-03-05]. http：//www.doc88.com/p-0087875377721.html. （WANG Y J， SHI X M. Jumping dolphin swarm algorithm[J]. Control Theory and Applications [2019-03-05]. http：//www.doc88.com/p-0087875377721.html.）

[17] KOOPMANS T C， BECKMANN M J. Assignment problems and the location of economic activities[J]. Econometrica， 1957， 25（1）： 53-76.

This work is partially supported by the National Natural Science Foundation of China （U1704158）， the Key Research Project of Higher Education Institutions in Henan Province （19A520026）.