基于群體競爭遺傳算法的帶時間窗車輛路徑規(guī)劃

摘 要：為了提升傳統(tǒng)遺傳算法的尋優(yōu)能力，本文提出了基于群體競爭的遺傳算法，并從算法設(shè)計(jì)上說明了其尋優(yōu)速度提升、不容易陷入局部最優(yōu)的原因;將基于群體競爭的遺傳算法應(yīng)用于復(fù)合函數(shù)最大值的求取上，并對比傳統(tǒng)遺傳算法的尋優(yōu)結(jié)果，結(jié)果發(fā)現(xiàn)前者尋優(yōu)速度快;最后將算法應(yīng)用于基于時間窗的車輛路徑規(guī)劃上，并得出了最優(yōu)解。

關(guān)鍵詞：群體競爭遺傳算法;時間窗;車輛路徑規(guī)劃

中圖分類號：TU443文獻(xiàn)標(biāo)識碼：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

將人或者動物身上的奧秘進(jìn)行解碼，并應(yīng)用于科學(xué)實(shí)踐，一直是科學(xué)家的夢想?，F(xiàn)在，很多成果已經(jīng)被普及，其在智能化算法應(yīng)用上的表現(xiàn)尤為突出，如遺傳算法、免疫算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)算法和模糊算法等[1-2]。遺傳算法在系統(tǒng)尋優(yōu)上存在絕對優(yōu)勢，所以被越來越多地應(yīng)用于路徑規(guī)劃上。

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

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

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

1.1 編碼

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

1.2 選擇方式

選擇方式的不同對遺傳算法具有很大影響，因?yàn)檫x擇的目的是要留下強(qiáng)勢的個體，但怎樣留、留多少將會關(guān)系到算法的運(yùn)算時間及尋優(yōu)的結(jié)果。遺傳算法在最早被提出時，使用輪盤賭注法進(jìn)行選擇。跟賭場的輪盤賭注有很大的相似性，某個個體是否被留下具有一定的隨機(jī)性。

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

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

1.3 交叉邏輯

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

1.4 變異規(guī)則

變異是以一定的概率改變某個個體上的某個基因。變異的概率不能過大，因?yàn)檫@樣會降低檢索效率。但是，變異也不能完全存在，否則可能會導(dǎo)致檢索過程陷入局部最優(yōu)而無法自拔。所以，適當(dāng)?shù)淖儺惛怕蕦?yōu)過程是有益的。

2 群體競爭遺傳算法在復(fù)合函數(shù)尋優(yōu)上的優(yōu)勢

為了對比普通遺傳算法和基于群體競爭遺傳算法在尋優(yōu)能力上的不同，本研究對一個復(fù)合函數(shù)進(jìn)行尋優(yōu)求解。設(shè)函數(shù)為：

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

下面分別用兩種算法求解此函數(shù)的最優(yōu)極大值。

2.1 普通遺傳算法

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

clear all;

close all;

clc;

Population_size=50; ? ? ? ? ? ? ? ? ? ? ? ? %種群數(shù)

L=20; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? %二進(jìn)制編碼長度

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

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

Generation=100; ? ? ? ? ? ? ? ? ? ? ? ? ? ? %遺傳代數(shù)

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

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

g=randint（Population_size，L）; ? ? ? ? ?%隨機(jī)產(chǎn)生種群

% 遺傳算法循環(huán)

for j=1：Generation

for i=1：Population_size ? ? ? ? ? ? ? ? %算適應(yīng)度值

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）;%尋找種群中的最優(yōu)值

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

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

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

% 基于輪盤賭的復(fù)制操作

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） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? %輸出適應(yīng)度進(jìn)化曲線

plot（trace）

xlabel（'迭代次數(shù)'）

ylabel（'目標(biāo)函數(shù)值'）

title（'適應(yīng)度進(jìn)化曲線'）

figure（2） ? ? ? ? ? ? ?%輸出需要尋優(yōu)的函數(shù)曲線

plot（t，func1（t））

xlabel（'自變量值'）

ylabel（'函數(shù)值'）

title（'尋優(yōu)函數(shù)曲線'）

% 適應(yīng)度函數(shù)

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 普通遺傳算法的求解結(jié)果。圖1是本研究需要尋優(yōu)的復(fù)合函數(shù)，將函數(shù)做成具有多個極大值是為了考察算法是否能夠跳出局部最優(yōu)而尋找到全局最優(yōu)值。算法最終運(yùn)行70多代之后，找到了最大值49.162。這說明，即使是傳統(tǒng)的遺傳算法，在進(jìn)行復(fù)核函數(shù)尋優(yōu)時也是沒有問題的。遺傳算法求解的適應(yīng)度進(jìn)化曲線見圖2。

2.2 群體競爭遺傳算法的求解結(jié)果

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

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

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

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

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

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

式中：[Pi（Si）]為懲罰函數(shù);[Si]表示到達(dá)第[i]個客戶點(diǎn)的時間;[ai]為早到懲罰系數(shù);[bi]為晚到懲罰系數(shù)。

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

[3]張杰飛，王曉麗.基于GCOA算法的帶時間窗車輛路徑規(guī)劃問題研究[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.