問題：
從某物流中心用多台配送車輛向多個客戶送貨,每個客戶的位置和貨物需求量一定,每台配送車輛的載重量一定,其一次配送的最大行駛距離一定,要求合理安排車輛配送路線,使目标函數得到優化,并滿足以下條件:
(1) 每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量;
(2) 每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離;
(3) 每個客戶的需求必須滿足,且隻能由一台配送車輛送貨。
若以配送總裡程最短為目标函數,則可建立如下優化問題的數學模型
思路：
(1) 編碼方法的确定
直接生産L 個1～L 間的互不重複的自然數的排列,該排列即構成一個個體。按照物流配送路徑優化問題的限制條件,可依次将個體中的元素(客戶) 劃入各條配送路徑中。
設某個體中的客戶排列為41235 ,可用如下方法得到其對應的配送路徑方案:首先将客戶4 作為第一個客戶加入到配送路徑1 中,然後判斷能否滿足問題的限制條件,即客戶4 的需求量是否超過第一台車輛的最大載重量,且路徑0 - 4 - 0 的長度是否超過第一台車輛一次配送的最大行駛距離,設能夠滿足,則可将客戶1 作為第三個客戶加入到路徑1 中,然後判斷能否滿足問題的限制條件,設仍能滿足,則可将客戶2 作為第三個客戶加入到路徑1 中,設仍能滿足問題的限制條件,則可将客戶3作為第四個客戶加入到路徑1 中,設此時不能滿足
問題的限制條件,這說明客戶3 不能加入到路徑1中,由此可行第一條配送路徑:0 - 4 - 1 - 2 - 0 ;然後,将客戶3 作為第一個客戶加入配送路徑2 中。
若某個個體對應的配送路徑數大于配送車輛總台數,則說明該個體對應一個不可行解
(2) 初始群體的确定
随機産生一種1～L 這L個互不重複的自然數的排列,即形成一個個體。設群體規模為N ,則通過随機産生N 個這樣的個體,即可形成初始群體。
(3) 适應度評估方法的确定
對于某個個體所對應的配送路徑方案,要判定其優劣,一是要看其是否滿足問題的限制條件;二是要計算其目标函數值。
對于某個個體,設其對應的配送路徑方案的配送路徑條數與配送車輛總台數之差為M(若配送路徑條數≤配送車輛總台數,則取M = 0 ,表示該個體對應一個可行解;若配送路徑條數> 車輛總台數,則M > 0 ,表示該個體對應一個不可行解) ,其目标函數值為Z ,将M 看成該個體對應的配送路徑方案的不可行路徑條數,并設對每條不可行路徑的懲罰權重為Pw (該權重可根據目标函數的取值範圍取一個相對較大的正數) ,則該個體的适應度F 可用公式計算。
F = 1/ (Z + M ×Pw)
(4) 選擇操作
采用如下最佳個體保留與賭輪選擇相結合的選擇政策:将每代群體中的N 個個體按适應度由大到小排列,排在第一位的個體性能最優,将它複制一個直接進入下一代,并排在第一位;下一代群體的另N - 1 個個體需要根據前代群體的N 個個體的适應度,采用賭輪選擇法産生,具體地說,就是首先計算上代群體中所有個體适應度的總和ΣFj ,再計算每個個體的适應度所占的比例Fj/ΣFj (j = 1 ,2 , ⋯,N) ,以此作為其被選擇的機率。
既可保證最優個體生存至下一代,又能保證适應度較大的個體以較大的機會進入下一代
(5) 交叉操作
除排在第一位的最優個體外,另N - 1 個個體要按交叉機率Pc 進行配對交叉重組。
采用類OX法實施交叉操作,現舉例說明其操作方法:
①随機在父代個體中選擇一個交配區域,如兩父代個體及交配區域標明為:A = 47| 8563| 921 ,B = 83| 4691|257 ;
②将B 的交配區域加到A 的前面,A 的交配區域加到B 的前面,得:A’= 4691| 478563921 ,B’=8563| 834691257 ;
③在A’、B’中自交配區域後依次删除與交配區相同的自然數,得到最終的兩個體為:A”= 469178532 ,B”= 856349127 。
(6) 變異操作
采用連續多次對換的變異技術,使個體在排列順序上有較大的變化。變異操作是以機率Pm 發生的,一旦變異操作發生,則用随機方法産生交換次數J ,對所需變異操作的個體的基因進行J 次對換(對換基因的位置也是随機産生的) 。
(7) 爬山操作
對于通過遺傳操作形成的每代群體中的最優個體,要通過鄰域搜尋實施爬山操作。采用基因換位算子實作爬山操作,其具體操作方法是:
①在個體中随機選擇兩個基因,并交換它們的位置:
②判斷基因換位後其适應值是否增加,若适應值增加,則以換位後的個體取代原個體;
③重複①、②,直到達到一定的交換次數為止。
(8) 終止準則
采用進化指定代數的終止準則。
例：
某物流中心有2 台配送車輛,其載重量均為8t ,車輛每次配送的最大行駛距離為50km ,配送中心(其編号為0) 與8 個客戶之間及8 個客戶互相之間的距離dij 、8 個客戶的貨物需求量qj (i 、j = 1 ,2 , ⋯,8) 均見表1 。要求合理安排車輛配送路線,使配送總裡程最短。
采用以下參數:群體規模取20 ,進化代數取25 ,交叉機率取019 ,變異機率取0109 ,變異時基因換位次數取5 , 對不可行路徑的懲罰權重取100km ,實施爬山操作時爬山次數取20 。對執行個體随機求解10 次。
代碼：
public class GeneticAlgorithm {
double[][] d = { { 0, 4, 6, 7.5, 9, 20, 10, 16, 8 },
{ 4, 0, 6.5, 4, 10, 5, 7.5, 11, 10 },
{ 6, 6.5, 0, 7.5, 10, 10, 7.5, 7.5, 7.5 },
{ 7.5, 4, 7.5, 0, 10, 5, 9, 9, 15 },
{ 9, 10, 10, 10, 0, 10, 7.5, 7.5, 10 },
{ 20, 5, 10, 5, 10, 0, 7, 9, 7.5 },
{ 10, 7.5, 7.5, 9, 7.5, 7, 0, 7, 10 },
{ 16, 11, 7.5, 9, 7.5, 9, 7, 0, 10 },
{ 8, 10, 7.5, 15, 10, 7.5, 10, 10, 0 } };
double[] q = { 0, 1, 2, 1, 2, 1, 4, 2, 2 };
Random random = new Random();
int rows;
int time;
int mans;
int cars;
int tons;
int dis;
int PW;
double JCL = 0.9;
double BYL = 0.09;
int JYHW = 5;
int PSCS = 20;
/**
*
* @param rows
* 排列個數
* @param time
* 疊代次數
* @param mans
* 客戶數量
* @param cars
* 貨車數量
* @param tons
* 貨車載重
* @param distance
* 貨車最大行駛距離
* @param PW
* 懲罰因子
*
*/
public GeneticAlgorithm(int rows, int time, int mans, int cars, int tons,
int distance, int PW) {
this.rows = rows;
this.time = time;
this.mans = mans;
this.cars = cars;
this.tons = tons;
this.dis = distance;
this.PW = PW;
}
public String run() {
int[][] lines = new int[rows][mans];
// 适應度
double[] fit = new double[rows];
// 擷取rows個随機排列，并計算适應度
int j = 0;
for (int i = 0; i < rows; i++) {
j = 0;
while (j < mans) {
int num = random.nextInt(mans) + 1;
if (!isHas(lines[i], num)) {
lines[i][j] = num;
j++;
// System.out.print(num + ",");
}
}
// System.out.println();
fit[i] = calFitness(lines[i]);
// System.out.println(fit[i]);
}
int t = 0;
while (t < time) {
int[][] nextLines = new int[rows][mans];
// 适應度
double[] nextFit = new double[rows];
double[] ranFit = new double[rows];
double totalFit = 0, tempFit = 0;
for (int i = 0; i < rows; i++) {
totalFit += fit[i];
}
for (int i = 0; i < rows; i++) {
ranFit[i] = tempFit + fit[i] / totalFit;
tempFit += ranFit[i];
}
// 上代最優直接到下一代
double m = fit[0];
int ml = 0;
for (int i = 0; i < rows; i++) {
if (m < fit[i]) {
m = fit[i];
ml = i;
}
}
for (int i = 0; i < mans; i++) {
nextLines[0][i] = lines[ml][i];
}
nextFit[0] = fit[ml];
// 最優使用爬山算法
clMountain(nextLines[0]);
int nl = 1;
while (nl < rows) {
// 根據機率選取排列
int r = ranSelect(ranFit);
// 判斷是否交叉 不能超出界限
if (random.nextDouble() < JCL && nl + 1 < rows) {
int[] fLine = new int[mans];
int[] nLine = new int[mans];
// 擷取交叉排列
int rn = ranSelect(ranFit);
// 獲得交叉的段
int f = random.nextInt(mans);
int l = random.nextInt(mans);
int min, max, fpo = 0, npo = 0;
if (f < l) {
min = f;
max = l;
} else {
min = l;
max = f;
}
// 将截取的段加入新生成的基因
while (min <= max) {
fLine[fpo] = lines[rn][min];
nLine[npo] = lines[r][min];
min++;
fpo++;
npo++;
}
for (int i = 0; i < mans; i++) {
if (!isHas(fLine, lines[r][i])) {
fLine[fpo] = lines[r][i];
fpo++;
}
if (!isHas(nLine, lines[rn][i])) {
nLine[npo] = lines[rn][i];
npo++;
}
}
// 基因變異
change(fLine);
change(nLine);
// 加入下一代
for (int i = 0; i < mans; i++) {
nextLines[nl][i] = fLine[i];
nextLines[nl + 1][i] = nLine[i];
}
nextFit[nl] = calFitness(fLine);
nextFit[nl + 1] = calFitness(nLine);
nl += 2;
} else {
int[] line = new int[mans];
int i = 0;
while (i < mans) {
line[i] = lines[r][i];
i++;
}
// 基因變異
change(line);
// 加入下一代
i = 0;
while (i < mans) {
nextLines[nl][i] = line[i];
i++;
}
nextFit[nl] = calFitness(line);
nl++;
}
}
// 新的一代覆寫上一代
for (int i = 0; i < rows; i++) {
for (int h = 0; h < mans; h++) {
lines[i][h] = nextLines[i][h];
}
fit[i] = nextFit[i];
}
t++;
}
// 上代最優
double m = fit[0];
int ml = 0;
for (int i = 0; i < rows; i++) {
if (m < fit[i]) {
m = fit[i];
ml = i;
}
}
// System.out.println("最優結果為:");
// for (int i = 0; i < mans; i++) {
// System.out.print(lines[ml][i] + ",");
// }
// System.out.println();
return showResult(lines[ml]);
}
/**
* 爬山算法
*
* @param line
*/
public void clMountain(int[] line) {
double oldFit = calFitness(line);
int i = 0;
while (i < PSCS) {
int f = random.nextInt(mans);
int n = random.nextInt(mans);
change(line, f, n);
double newFit = calFitness(line);
if (newFit < oldFit) {
change(line, f, n);
}
i++;
}
}
/**
* 基因變異
*
* @param line
*/
public void change(int[] line) {
if (random.nextDouble() < BYL) {
int i = 0;
while (i < JYHW) {
int f = random.nextInt(mans);
int n = random.nextInt(mans);
change(line, f, n);
i++;
}
}
}
public void change(int[] line, int f, int n) {
int temp = line[f];
line[f] = line[n];
line[n] = temp;
}
/**
* 選擇随機的序列
*
* @param ranFit
* @return
*/
public int ranSelect(double[] ranFit) {
double ran = random.nextDouble();
for (int i = 0; i < rows; i++) {
if (ran < ranFit[i])
return i;
}
System.out.println("ERROR!!! get ranSelect Error!");
return 0;
}
/**
* 計算适應度
*
* @param line
* @return
*/
public double calFitness(int[] line) {
double carTon = 0;
double carDis = 0;
double newTon = 0;
double newDis = 0;
double totalDis = 0;
// 預設為2倍
int[][] ll = new int[cars * 2][mans];
int r = 0, l = 0, fore = 0, M = 0;
for (int i = 0; i < mans; i++) {
// 距離
newDis = carDis + d[fore][line[i]];
// 載重
newTon = carTon + q[line[i]];
// 超過貨車距離，載重
if ((newDis + d[line[i]][0]) > dis || newTon > tons) {
// 下一輛車
totalDis += carDis + d[fore][0];
l = 0;
r++;
fore = 0;
i--;
carTon = 0;
carDis = 0;
} else {
carDis = newDis;
carTon = newTon;
fore = line[i];
ll[r][l] = line[i];
l++;
}
}
// 加上最後一輛貨車距離
totalDis += carDis + d[fore][0];
// for (int i = 0; i < cars * 2; i++) {
// for (int j = 0; j < mans; j++) {
// System.out.print(ll[i][j]);
// }
// System.out.println();
// }
// System.out.println("總路徑長度為:" + totalDis);
if ((r - cars + 1) > 0)
M = r - cars + 1;
// 目标函數
double result = 1 / (totalDis + M * PW);
return result;
}
public String showResult(int[] line) {
double carTon = 0;
double carDis = 0;
double newTon = 0;
double newDis = 0;
double totalDis = 0;
// 預設為2倍
int[][] ll = new int[cars * 2][mans];
int r = 0, l = 0, fore = 0, M = 0;
for (int i = 0; i < mans; i++) {
// 距離
newDis = carDis + d[fore][line[i]];
// 載重
newTon = carTon + q[line[i]];
// 超過貨車距離，載重
if ((newDis + d[line[i]][0]) > dis || newTon > tons) {
// 下一輛車
totalDis += carDis + d[fore][0];
l = 0;
r++;
fore = 0;
i--;
carTon = 0;
carDis = 0;
} else {
carDis = newDis;
carTon = newTon;
fore = line[i];
ll[r][l] = line[i];
l++;
}
}
// 加上最後一輛貨車距離
totalDis += carDis + d[fore][0];
StringBuffer sb = new StringBuffer();
for (int i = 0; i < cars; i++) {
for (int j = 0; j < mans; j++) {
// System.out.print(ll[i][j]);
sb.append(ll[i][j]);
}
// System.out.println();
sb.append("\n");
}
// System.out.println("總路徑長度為:" + totalDis);
sb.append("總路徑長度為:" + totalDis + "\n");
if ((r - cars + 1) > 0)
M = r - cars + 1;
// 目标函數
double result = 1 / (totalDis + M * PW);
// System.out.println("最終權值為:" + result);
sb.append("最終權值為:" + result + "\n");
return sb.toString();
}
public boolean isHas(int[] line, int num) {
for (int i = 0; i < mans; i++) {
if (line[i] == num)
return true;
}
return false;
}
public static void main(String[] args) {
GeneticAlgorithm ga = new GeneticAlgorithm(20, 25, 8, 2, 8, 50, 100);
for (int i = 0; i < 10; i++) {
System.out.println("第" + (i + 1) + "次:");
long begin = System.currentTimeMillis();
ga.run();
long end = System.currentTimeMillis();
System.out.println("使用時間" + (end - begin) + "毫秒");
System.out.println();
}
}
}
輸出結果：
第1次:
最優結果為:
4,7,5,3,1,8,6,2,
47531000
86200000
00000000
00000000
總路徑長度為:70.0
最終權值為:0.014285714285714285
使用時間31毫秒
第2次:
最優結果為:
4,7,6,2,8,5,3,1,
47600000
28531000
00000000
00000000
總路徑長度為:67.5
最終權值為:0.014814814814814815
使用時間9毫秒
第3次:
最優結果為:
8,2,3,5,1,4,7,6,
82351000
47600000
00000000
00000000
總路徑長度為:70.5
最終權值為:0.014184397163120567
使用時間8毫秒
第4次:
最優結果為:
2,7,4,8,1,3,5,6,
27480000
13560000
00000000
00000000
總路徑長度為:69.0
最終權值為:0.014492753623188406
使用時間2毫秒
第5次:
最優結果為:
4,7,5,3,1,8,6,2,
47531000
86200000
00000000
00000000
總路徑長度為:70.0
最終權值為:0.014285714285714285
使用時間2毫秒
第6次:
最優結果為:
1,3,5,8,2,6,7,4,
13582000
67400000
00000000
00000000
總路徑長度為:67.5
最終權值為:0.014814814814814815
使用時間15毫秒
第7次:
最優結果為:
1,3,5,6,8,4,7,2,
13560000
84720000
00000000
00000000
總路徑長度為:69.0
最終權值為:0.014492753623188406
使用時間2毫秒
第8次:
最優結果為:
2,7,4,8,6,5,3,1,
27480000
65310000
00000000
00000000
總路徑長度為:69.0
最終權值為:0.014492753623188406
使用時間3毫秒
第9次:
最優結果為:
6,7,4,1,3,5,8,2,
67400000
13582000
00000000
00000000
總路徑長度為:67.5
最終權值為:0.014814814814814815
使用時間64毫秒
第10次:
最優結果為:
8,6,4,1,3,5,7,2,
86400000
13572000
00000000
00000000
總路徑長度為:70.0
最終權值為:0.014285714285714285
使用時間3毫秒