摘 要：為了提升傳統遺傳算法的尋優能力，本文提出了基于群體競爭的遺傳算法，并從算法設計上說明了其尋優速度提升、不容易陷入局部最優的原因;將基于群體競爭的遺傳算法應用于復合函數最大值的求取上，并對比傳統遺傳算法的尋優結果，結果發現前者尋優速度快;最后將算法應用于基于時間窗的車輛路徑規劃上，并得出了最優解。

關鍵詞：群體競爭遺傳算法;時間窗;車輛路徑規劃

中圖分類號：TU443文獻標識碼：A文章編號：1003-5168（2021）04-0016-04

Abstract： In order to improve the optimization ability of traditional genetic algorithms， this paper proposed a genetic algorithm based of group competition， and explained the reason why its optimization speed increased and it was not easy to fall into a local optimum from the algorithm design; applied the genetic algorithm based on group competition to the maximum value of the compound function， and compared with the optimization results of the traditional genetic algorithm， found that the former was fast; finally applied the algorithm to the vehicle path planning based on time window， and obtained the optimal solution.

Keywords： genetic algorithm of group competition;time window;vehicle path planning

將人或者動物身上的奧秘進行解碼，并應用于科學實踐，一直是科學家的夢想。現在，很多成果已經被普及，其在智能化算法應用上的表現尤為突出，如遺傳算法、免疫算法、蟻群算法、神經網絡算法和模糊算法等[1-2]。遺傳算法在系統尋優上存在絕對優勢，所以被越來越多地應用于路徑規劃上。

達爾文的《物種起源》對遺傳進化的思想進行了闡述，指出了微小概率的變異經過優勝劣汰的自然選擇，最后會引發群體的集體進化。這種進化思想被美國人霍蘭德成功應用于尋優算法，遺傳算法就此誕生。

1 基于群體競爭的遺傳算法

遺傳算法需要先對所求解的問題進行編碼，把求解空間編碼成二進制或者十進制的字符串，表示可行解的空間，其最終目的是應用于計算機的求解[3-5]。每一個由二進制或者十進制組成的編碼串可以看作是一個個體，個體中的每位二進制或者十進制稱為基因。在算法運行之初，先隨機產生多個個體，稱為種群。遺傳算法的搜索過程是基于選擇、交叉和變異的。每一個個體是否優秀是需要有一個適應度函數來作為評價依據的，選擇的目的就是要留下適應度較高的個體，淘汰適應度較低的個體。交叉的作用是以一定的概率選擇群體中的兩個個體，交換它們之間的幾個基因。變異是以一定的概率選擇其中的個體，對其某個基因進行一次改變。選擇保留了每一代中的優秀個體，交叉保證了優秀基因可以轉移，從而擴大了檢索空間，變異的目的在于避免陷入局部最優而無法跳出。遺傳算法的改良一般是在選擇、交叉、變異的方式上進行改良。基于群體競爭的遺傳算法主要操作過程如下。

1.1 編碼

編碼主要是對解空間進行映射，因此具體選擇二進制編碼還是十進制編碼的關鍵是根據具體問題進行分析。例如，在對復雜函數尋找最優解時，使用二進制更容易進行對應。而在進行帶時間窗的車輛路徑規劃時，采用十進制編碼更合適。所以，基于群體競爭的遺傳算法在編碼方式上并沒有改變。

1.2 選擇方式

選擇方式的不同對遺傳算法具有很大影響，因為選擇的目的是要留下強勢的個體，但怎樣留、留多少將會關系到算法的運算時間及尋優的結果。遺傳算法在最早被提出時，使用輪盤賭注法進行選擇。跟賭場的輪盤賭注有很大的相似性，某個個體是否被留下具有一定的隨機性。

后來有人使用了精英保留算法，即每次進行選擇時都對所有個體的適應度函數進行排序，保留適應度函數最高的1～3個個體。

基于群體競爭的遺傳算法，結合了輪盤賭注與精英保留策略的雙重優勢，將群體中的任意兩個個體進行適應度對比，保留適應度高的一個個體。這樣既存在隨機性，又能將優勢個體盡量保存下來，從而既保證尋優效率，又保證全局尋優能力。

1.3 交叉邏輯

傳統的遺傳算法是將新產生的種群中所有個體按一定概率來交叉任意兩個個體中的某段基因，從而增大了出現優秀基因的可能性。在群體競爭遺傳算法中，只對新產生的個體基因組進行改變。也就是說，將最優的5個個體進行記憶，從這5個個體中隨機抽取一段基因注入新產生的個體，然后隨機產生新個體的其他位置基因。這樣既容易將優秀基因留取，又容易產生新的個體，從而避免尋優過程陷入局部最優。

1.4 變異規則

變異是以一定的概率改變某個個體上的某個基因。變異的概率不能過大，因為這樣會降低檢索效率。但是，變異也不能完全存在，否則可能會導致檢索過程陷入局部最優而無法自拔。所以，適當的變異概率對尋優過程是有益的。

2 群體競爭遺傳算法在復合函數尋優上的優勢

為了對比普通遺傳算法和基于群體競爭遺傳算法在尋優能力上的不同，本研究對一個復合函數進行尋優求解。設函數為：

[f（x）=（x-3）2+10sin5x+7cos4x+3sin（2x-1）] ? ? ? （1）

下面分別用兩種算法求解此函數的最優極大值。

2.1 普通遺傳算法

2.1.1 求解過程。若采用普通遺傳算法，則求解過程如下：

clear all;

close all;

clc;

Population_size=50; ? ? ? ? ? ? ? ? ? ? ? ? %種群數

L=20; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? %二進制編碼長度

P_cross=0.8; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?%交叉概率

P_mutates=0.2; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?%變異概率

Generation=100; ? ? ? ? ? ? ? ? ? ? ? ? ? ? %遺傳代數

X_max=10; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? %自變量最大值

X_min=0; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?%自變量最小值

g=randint（Population_size，L）; ? ? ? ? ?%隨機產生種群

% 遺傳算法循環

for j=1：Generation

for i=1：Population_size ? ? ? ? ? ? ? ? %算適應度值

M=g（i，：）;

m=0;

for k=1：L

m=M（k）*2^（k-1）+m;

end

x（i）=X_min+m*（X_max-X_min）/（2^L-1）;

Fitness（i）=func1（x（i））;

end

maxFitness=max（Fitness）;

minFitness=min（Fitness）;

r=find（Fitness==maxFitness）;%尋找種群中的最優值

g_Best=g（r（1，1），：）;

x_Best=x（r（1，1））;

Fitness=（Fitness-minFitness）/（maxFitness-minFitness）;

% 基于輪盤賭的復制操作

sum_Fitness=sum（Fitness）;

fitvalue=Fitness./sum_Fitness;

fitvalue=cumsum（fitvalue）;

ms=sort（rand（Population_size，1））;

fiti=1;

newi=1;

while newi<=Population_size

if （ms（newi））

n_f（newi，：）=g（fiti，：）;

newi=newi+1;

else

fiti=fiti+1;

end

end

% 基于概率的交叉操作

for i=1：2：Population_size

P=rand;

if P

q=randint（1，L）;

for k=1：L

if q（k）==1;

temp=n_f（i+1，k）;

n_f（i+1，k）=n_f（i，k）;

n_f（i，k）=temp;

end

end

end

end

% 基于概率的變異操作

i=1;

while i<=round（Population_size*P_mutates）

h=randint（1，1，[1，Population_size]）;

for k=1：round（L*P_mutates）

gg=randint（1，1，[1，L]）;

n_f（h，gg）=～n_f（h，gg）;

end

i=i+1;

end

g=n_f;

g（1，：）=g_Best;

trace（j）=maxFitness;

end

% 顯示找出的最大值及自變量位置

m=0;

for k=1：L

m=g_Best（k）*2^（k-1）+m;

end

x=X_min+m*（X_max-X_min）/（2^L-1）

maxFitness

t=0：0.1：10;

figure（1） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? %輸出適應度進化曲線

plot（trace）

xlabel（'迭代次數'）

ylabel（'目標函數值'）

title（'適應度進化曲線'）

figure（2） ? ? ? ? ? ? ?%輸出需要尋優的函數曲線

plot（t，func1（t））

xlabel（'自變量值'）

ylabel（'函數值'）

title（'尋優函數曲線'）

% 適應度函數

function result=func1（x）

fit=（x-3）.^2+10*sin（5*x）+7*cos（4*x）+3*sin（2*x-1）;

result=fit;

end

2.1.2 普通遺傳算法的求解結果。圖1是本研究需要尋優的復合函數，將函數做成具有多個極大值是為了考察算法是否能夠跳出局部最優而尋找到全局最優值。算法最終運行70多代之后，找到了最大值49.162。這說明，即使是傳統的遺傳算法，在進行復核函數尋優時也是沒有問題的。遺傳算法求解的適應度進化曲線見圖2。

2.2 群體競爭遺傳算法的求解結果

根據群體競爭遺傳算法的思路對普通遺傳算法進行改良，運行后，得出群體競爭遺傳算法求解的適應度進化曲線，如圖3所示。由此可以看出，其運行了不到10代就

得出了最優解。無論是哪種遺傳算法，并不能每次都保證在相同的代數中得出最優值。但是，如果運行10次之后求平均值，就能更清晰地得出結論。普通遺傳算法進化代數平均值是46次，而群體競爭遺傳算法的平均值是19次。所以，群體競爭遺傳算法的有效性非常明顯。

3 群體競爭遺傳算法求解帶時間窗的車輛路徑規劃問題

在物流業迅速發展的時代，貨物配送問題已經成為熱點。怎樣快速有效地完成郵件投遞、航空鐵路調度、貨物配送已經成了大家特別關心的問題。因此，車輛路徑問題（VRP）應運而生。它是指合理組織現有車輛的運送路徑，讓貨車將貨物從中心站點運送至各客戶中心，在滿足車輛最大行駛里程、車輛最大容量、卸貨點對貨物的需求數量、卸貨點對時間的要求等約束條件下，達到某個結果（如使用車輛最少、總用時數最少、里程數最短、費用最低等）的最優。

有些貨物對保鮮時間是有要求的，所以需要對時間進行限定。例如，可以要求卸貨的時間必須在最早[ETi]和最晚[LTi]之間到達，則卸貨時間形成了一個窗口期[ETi-LTi]。它是在傳統VRP問題的基礎上給每個卸貨點客戶加上服務所允許的時間窗約束，就擴展成了有時間窗車輛路徑問題（Vehicle Routing Problems with Time Windows，VRPTW）。時間窗又分為硬時間窗和軟時間窗兩種。硬時間窗是必須在規定時間到達，軟時間窗是可以在時間窗外到達，但是不管早到還是晚到都必須受到懲罰。由于軟時間窗更切合實際，所以這里使用軟時間窗約束。具體的懲罰函數如下：

[Pi（Si）=ai（ETi-Si）SiLTi] ? ? ? ? ? ? （2）

式中：[Pi（Si）]為懲罰函數;[Si]表示到達第[i]個客戶點的時間;[ai]為早到懲罰系數;[bi]為晚到懲罰系數。

下面以一個具體的VRPTW問題來進行解答。假設現在有一個配送中心，有8個客戶點需要配送貨物，[qi]代表第[i]個客戶點的貨物需求量。每個客戶對貨物送達時間的要求分別是[ETi-LTi]，表1所顯示的是具體數值。配送的最終目的是合理調配所有車輛從配送中心出發，到達配送點完成配送后返回配送中心，并且總運行費用最少。為了將問題簡化，假定配送中心只有容量為8 t的車輛。

在計算過程中，假設車輛的行駛距離和時間成正比，并且每輛車的平均行駛速度為50 km/h。車場各任務點兩兩之間的距離如表2所示。

下面使用群體競爭遺傳算法進行問題的求解。為了使得編碼更容易與實際問題相對應，這里采用實數編碼。每一個個體在隨機產生時都是對1～8的數字進行無重復的重組，重組完成之后需要對貨物進行配置。例如，隨機產生5 6 4 2 1 7 3 8的個體時，5、6、4共需要貨物7.5 t，在增加2號時，其就超過8 t，所以在4和2之間進行一次隔斷，最終形成5 6 4|2 1 7|3|8，表示有4條路徑，分別是：配送中心—客戶5—客戶6—客戶4—配送中心;配送中心—客戶2—客戶1—客戶7—配送中心;配送中心—客戶3—配送中心;配送中心—客戶8—配送中心。適應度函數使用路徑之和+懲罰函數之和，最后尋找適應度函數最小的路徑作為最優路徑。使用算法求解后，最終得出結論：3 5 4|6 1 7|8 2。各路徑的距離分別是240、405、265 km，取得了最優的結果。

4 結語

本文先介紹了遺傳算法，然后介紹了基于群體競爭遺傳算法的原理。為了顯示新算法的優勢，本研究采用新算法對具有多極值的復合函數進行了求解，最后又將算法應用于具有時間窗的車輛路徑規劃問題處理中，得出了結論。求解結果表明，基于群體競爭的遺傳算法在尋優方面優于傳統遺傳算法。

參考文獻：

[1]王曉麗，賈東明.GCOA算法：一種新的智能優化算法[J].價值工程，2017（8）：170-171.

[2]謝秉磊，李軍，郭耀煌.有時間窗的非滿載車輛調度問題的遺傳算法[J].系統工程學報，2000（3）：290-294.

[3]張杰飛，王曉麗.基于GCOA算法的帶時間窗車輛路徑規劃問題研究[J].河南科技，2020（4）：26-29.

[4]NAZIF H，LEE L S.Optimized crossover genetic algorithm for vehicle routing problem with time windows[J].American Journal of Applied Sciences，2010（1）：95-101.

[5]BEN-TAL A，NEMIROVSKI A.Robust solutions of linear programming problems contaminated with uncertain data[J].Mathmatical programming，2000（3）：411-424.