GCOA算法

王曉麗++賈東明

摘要： 根據(jù)種群中個體的競爭與淘汰機制提出了一種群體競爭優(yōu)化算法（GCOA）。首先對算法的構(gòu)造思想進行了詳細的描述，然后用本算法求解具有多個極值點函數(shù)的最大值，從而分析算法的可行性。最后，使用本算法對物流車輛路徑的優(yōu)化問題進行了仿真研究，得出了算法的先進性。

Abstract： The group competition optimization algorithm is proposed according to the mechanism of competition and elimination of individuals in the population. At first， it describes the construction of the algorithm， solves the maximum value of the function that have multiple extreme points by this algorithm. Then， draw the conclusion that the algorithm is feasible. Finally， the optimization of the logistics vehicle routing problem is simulated by using this algorithm， and the advanced nature of the algorithm is obtained.

關鍵詞： 淘汰機制；協(xié)作機制；編碼方式；路徑優(yōu)化

Key words： elimination mechanism；cooperation mechanism；coding mode；routing optimization

中圖分類號：TP18 文獻標識碼：A 文章編號：1006-4311（2017）22-0170-02

1 算法的提出

作者通過麥特·里德雷所著的《美德的起源》一書中對群體中個體互助合作從而保證種群順利傳承的一段論證，捕捉到進化的實質(zhì)，即協(xié)作與淘汰，同時根據(jù)上述機制構(gòu)造了一種種群進化算法，而算法的目的是希望種群能夠得到優(yōu)化。編碼方式：為了將現(xiàn)實的問題與算法進行匹配或映射，我們需要對求解空間進行編碼操作。淘汰機制：在一個種群里隨機產(chǎn)生的若干個體，必須要經(jīng)歷淘汰。協(xié)作機制：個體經(jīng)歷淘汰之后，種群中個體的數(shù)量必然會減少，可以在這個時候引入一些新的個體，以保證種群大小不變。

2 實際問題的解決

該算法依靠群體的進化特性而進行優(yōu)化，最終可以求取最優(yōu)解。為了驗證算法的可行性，對函數(shù)f（x）=x+10sin（5x）+7cos（4x），自變量取值在[0，10]范圍內(nèi)的最大值進行求解。函數(shù)在自變量規(guī)定的取值范圍內(nèi)，有8個極大值。可以通過這樣的函數(shù)來分析本算法是否會陷入局部最優(yōu)。

2.1 編碼 用20位的二進制碼代表函數(shù)的自變量，20位的二進制碼轉(zhuǎn)化為十進制碼的話，范圍在[0，220 -1]。因此需要將本范圍的數(shù)據(jù)與自變量范圍[0，10]內(nèi)的數(shù)據(jù)對應起來。

2.2 淘汰 將本代中所有的個體求取適應度值，然后依據(jù)適應度值的大小將個體進行升序排列，將適應度值最小的N個個體清零。

2.3 協(xié)作 隨機選取最優(yōu)個體的10位連續(xù)二進制數(shù)字轉(zhuǎn)化為新進個體的同一位置，對于每個新個體所得到的位置均不相同。其余未選中的部位隨機產(chǎn)生二進制數(shù)字。

2.4 返回至第二步進行循環(huán)計算，直到規(guī)定的代數(shù)為止。上述問題求解過程中總共規(guī)定了100代。

2.5 分析 在上述的1、2、3步中，第3步是最為重要的。因為新產(chǎn)生的個體繼承了最優(yōu)個體的部分特性，并且隨機產(chǎn)生了其余位置的數(shù)據(jù)。如若繼承的部分恰巧是具有優(yōu)良特性數(shù)段的話，那其余部分數(shù)據(jù)改變相當于在最大值附近尋優(yōu)，保證了尋優(yōu)過程的持續(xù)進行。如若繼承的部分并不是最優(yōu)的數(shù)段，則此個體保證了數(shù)據(jù)在全局范圍內(nèi)隨機找最大值，那么數(shù)據(jù)陷入極值點被吸附的可能性就大為降低。因此第3步保證了全局最優(yōu)的尋找以及最優(yōu)值的精確化。

2.6 問題的解決 文章隨機產(chǎn)生一個具有50個個體的群體，每次淘汰30個個體，同時新產(chǎn)生30個個體進行最優(yōu)化學習。每次學習時都是隨機產(chǎn)生一個點位，并將最優(yōu)個體同一點位之后連續(xù)的10位數(shù)字學習到自身，然后進行仿真。仿真進行了20次，每次均能找到最優(yōu)點。程序運行中一次進化穩(wěn)定所經(jīng)歷代數(shù)較少的結(jié)果，但并不能保證每次運行都在如此短的代數(shù)之內(nèi)將問題解決。即使如此，所有20次仿真，在100代之內(nèi)均找到了問題的最優(yōu)解。因此得出了本算法可用于最優(yōu)化問題求解的可行性結(jié)論。

2.7 算法的進一步探討 作者對本算法與遺傳算法分別進行編程，進行本問題的最優(yōu)解求取，然后將結(jié)論進行對比，求解結(jié)果對比見表1。

由求解結(jié)果對比表可見：使用GA算法求取的最優(yōu)值是24.8176，使用GCOA算法求取的最優(yōu)值是24.8533。使用GA算法求取最優(yōu)值時平均需要經(jīng)歷26代，而GCOA算法需要經(jīng)歷20代。由此可見，對于本例所使用的函數(shù)來說，GCOA算法無論從最優(yōu)值還是從迭代代數(shù)來說，都是優(yōu)于GA算法的，并且值得一提的是，GCOA算法比GA算法的設計思路更為簡潔，用MATLAB程序進行實現(xiàn)時，GCOA編制了47行，而GA編制了74行。

3 GCOA算法在物流車輛路徑優(yōu)化中的應用

3.1 VRP問題的數(shù)學描述 已知一個配貨中心（用0表示）需將貨物配送至n（1，2，3…n）個客戶點，每個客戶點的需求量為qi（i=1，2，3…n），客戶點i到j的距離是Cij（i，j=1，2，3…n），每輛車的載貨能力均為Q，設T為實際使用到的車輛數(shù)，第K輛車經(jīng)過的客戶點總數(shù)用nk表示，集合Rk={rki|0？燮i？燮nk}表示第k輛車經(jīng)過的客戶點。

假設從配貨中心派出的車輛是統(tǒng)一的，即所有車輛的載貨能力是相同的。則問題須同時滿足下面列出的所有條件：

①任何一輛車都可從配貨中心出發(fā)，經(jīng)過多個客戶點而返回配貨中心，但所裝載的貨物不能超出車輛的載貨能力；

②每個客戶點都只能被一輛車供貨；

③所有客戶點的需求必須都能夠被滿足；

④求解所有車輛運送路徑的最小值。

3.2 問題的解決

文章主要解決具有1個配貨中心，20個客戶點的VRP問題。文中采用了被國內(nèi)多篇文獻所引用的數(shù)據(jù)進行求解，以便于進行結(jié)果的對比。各客戶點的需求量如表2所示，車輛的容量為8噸。

對于兩坐標點之間的距離，使用直線距離來進行計算，并應用GCOA算法來對此實際問題進行求解，解決思路如下：①編碼。本問題求解使用實數(shù)編碼來進行。比如15-14-17-4-5-3-6-18-9-11-13-16-2-8-1-20-12-19-7-10代表了車輛走過的路徑，但是此鏈中不是一輛車可以解決所有的問題，所以我們依次對客戶的需求量進行求和，如果某段的和小于8，但再加一個點后和就大于8的話，此段即為一輛車運輸。

②淘汰。在第一代時，隨機產(chǎn)生了50個個體作為一個種群。每次淘汰其中的30個個體。所使用的目標函數(shù)是總路徑最短，優(yōu)化的目的是使目標函數(shù)最小。我們可以將目標函數(shù)的倒數(shù)作為適應度函數(shù)，依然以求取適應度值最高為目標。每次淘汰的30個個體都是適應度最低的30個個體。

③協(xié)作。協(xié)作的過程依然是新產(chǎn)生的30個個體向最優(yōu)個體學習的過程，選擇的目標段依然是連續(xù)10位數(shù)據(jù)的組合，并且點位隨機產(chǎn)生。

④仿真結(jié)果。通過表3的對比結(jié)果可以看出，文章所提出的GCOA算法得出的結(jié)論是最優(yōu)的。而且經(jīng)過多次運行之后，GCOA算法所得出的結(jié)果范圍大致在850-890之間，具有很好的穩(wěn)定性。

4 結(jié)論

文章提出了GCOA算法并使用Matlab軟件對多極值點函數(shù)及VRP問題進行了優(yōu)化求解，最終得出了算法可行性及優(yōu)越性的結(jié)論。此算法剛被提出，并未經(jīng)過大量的實踐驗證，也許有些潛在的問題是作者未考慮到的。因此作者下一步的工作目標將是應用此算法求解更多的優(yōu)化問題，以求發(fā)現(xiàn)并改良算法中存在的問題。

參考文獻：

[1]程林輝.基于改進的遺傳算法的車輛路徑問題研究[D].中南民族大學碩士論文，2008：32-33.

[2]安立軍.遺傳算法在物流配送車輛優(yōu)化調(diào)度中的研究與應用[D].上海海事大學碩士論文，2007：19-33.

[3]辛焦麗，高麗.基于遺傳算法的蜂窩網(wǎng)絡接入信道動態(tài)分配方案的設計[J].現(xiàn)代電子技術，2016，39（15）：5-7.

[4]王鳳云，冉文學，張巧霞.蟻群算法在卷煙配送路徑優(yōu)化中的應用研究[J].物流技術，2011（05）：69-72.

[5]鐘惟鈺.遺傳算法在物流配送運輸車輛路徑優(yōu)化中的應用和改進[J].物流技術，2014，33（5）：323-325.