GCOA算法

王曉麗++賈東明

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

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.

關鍵詞： 淘汰機制；協作機制；編碼方式；路徑優化

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

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

1 算法的提出

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

2 實際問題的解決

該算法依靠群體的進化特性而進行優化，最終可以求取最優解。為了驗證算法的可行性，對函數f（x）=x+10sin（5x）+7cos（4x），自變量取值在[0，10]范圍內的最大值進行求解。函數在自變量規定的取值范圍內，有8個極大值?？梢酝ㄟ^這樣的函數來分析本算法是否會陷入局部最優。

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

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

2.3 協作 隨機選取最優個體的10位連續二進制數字轉化為新進個體的同一位置，對于每個新個體所得到的位置均不相同。其余未選中的部位隨機產生二進制數字。

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

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

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

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

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

3 GCOA算法在物流車輛路徑優化中的應用

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

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

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

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

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

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

3.2 問題的解決

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

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

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

③協作。協作的過程依然是新產生的30個個體向最優個體學習的過程，選擇的目標段依然是連續10位數據的組合，并且點位隨機產生。

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

4 結論

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

參考文獻：

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

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

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

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

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