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

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

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

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

實驗結(jié)果均表明BWCOA具有更強的競爭性。

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

中圖分類號：TP181

文獻標志碼：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)實生活中隨處存在著優(yōu)化問題，以往人們依靠生活經(jīng)驗和數(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]。這些算法易于實現(xiàn)，能較好地解決各種復(fù)雜的優(yōu)化問題，受到廣大學(xué)者的關(guān)注。但是“無免費午餐定理”[4]表明某個算法不可能解決所有的問題，因此，新算法和改進的算法不斷地產(chǎn)生來解決復(fù)雜優(yōu)化問題。

二次指派問題（Quadratic Assignment Problem， QAP）是一個復(fù)雜的優(yōu)化問題，在不同的領(lǐng)域中有廣泛的應(yīng)用，比如醫(yī)院科室布局問題[7]、求解物流設(shè)施[8]、任務(wù)分配問題和航班調(diào)度問題等[9]。用智能優(yōu)化算法來解決QAP也是熱點之一，比如使用混合分布估計算法求解物流設(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中，每一頭郊狼代表一個候選解，每個解向量由郊狼的社會狀態(tài)因子構(gòu)成，這些狀態(tài)因子包括郊狼內(nèi)在因素和外在因素，每一個狀態(tài)因素代表一個決策變量，用社會適應(yīng)能力來衡量一頭郊狼的好壞。

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

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

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

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

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

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

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

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

2.1 COA存在的問題及改進的動機

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

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

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

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

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

2.3 隨機擾動強化最優(yōu)郊狼

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

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

3.4 收斂性分析

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

從圖3可以看出，在6個函數(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ù)時，表現(xiàn)優(yōu)異。因此，BWCOA提高了COA的收斂速度。

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻（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] 張新明， 王霞， 涂強， 等. 融合榜樣學(xué)習(xí)和反向?qū)W習(xí)的粒子群優(yōu)化算法[J]. 河南師范大學(xué)學(xué)報（自然科學(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] 張新明， 康強， 王霞， 等. 差分遷移和趨優(yōu)變異的生物地理學(xué)優(yōu)化算法[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)化-蛙跳算法的云計算資源調(diào)度算法[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]. 運籌與管理， 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]. 計算機應(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）.