Problem 21.docx

Problem 2

流程圖 開始 編碼(轉換成二元)

[初始化] 產生初始母體 計算合適度(Evaluate fitness)

是否滿足終止條件

是

最佳解

否 選擇 Selection

交配 Crossover

突變 Mutation

說明 Selection 1. Change the selection mechanism twice  Roulette wheel selection  Tournament selection Crossover 2. Change the type of crossover operator twice  Single point crossover  2-point crossover 3. Change the crossover probability twice  0.9  0.7 （後續表格中亦比較了其他數值） Mutation 4. Change the type of mutation operator twice  Bit flip  Displacement 5. Change the mutation probability twice  0.1  0.2 （後續表格中亦比較了其他數值） 6.

7.

8.

Change the population size three times  30  50  20 （後續表格中亦比較了其他數值） Change the population maintenance mechanism twice  Enlarged sampling space → Stochastic sampling [roulette wheel selection]  Enlarged sampling space → Mixed sampling [tournament selection] Change the stopping criterion three times (generation size)  50  70  100

- programming language: C++ - Output Size: 1.88127613067627 MiB - Compilation Time: 2.86s

程式說明（僅截取重點部分，完整程式碼如附錄） 選擇 0 和 1 以選擇使用模式 --------------------------------------------------------------------------#define ROULETTE_SELECTION 0 /* 1 = 輪盤法, 0 = 競爭法 */ #define TWOPOINT 1 /* 1 = 2-point, 0 = single point */ #define FLIP 1 /* 1 = bit flip, 0 = displacement */ #define ROULETTE 0 /* 1 = 輪盤法, 0 = 競爭法 */ 產生母體 ---------------------------------------------------------------------------

/* 利用 ceil 無條件進位, 求得 bits 的個數 */

int bits = ceil(log(9 * (int)pow(10, prec)) / log(2));

/* 隨機選定母體數量之(x,y)座標, 為 9 乘 (10 的 prec 次方) */

for (int i = 0; i < ps; i++) { x[i] = rand() % (9 * (int)pow(10, prec)); y[i] = rand() % (9 * (int)pow(10, prec)); cout << x[i] / pow(10, prec) - 4.5 << ", " << y[i] / pow(10, prec) - 4.5 << " f(x,y) = " << f(x[i] / pow(10, prec) - 4.5, y[i] / pow(10, prec) - 4.5) << '\n'; }

Selection 使用輪盤法 --------------------------------------------------------------------------#if defined ROULETTE_SELECTION double randomProbA = (rand() / (double)(RAND_MAX + 1u)); double randomProbB = (rand() / (double)(RAND_MAX + 1u)); int parentA = -1, parentB = -1; for (int i = 0; i < ps; i++) { parentA = ((randomProbA < probIntervalEndpoint[i]) && (parentA == -1)) ? i : parentA; parentB = ((randomProbB < probIntervalEndpoint[i]) && (parentB == -1)) ? i : parentB; } #else Selection 使用競爭法 --------------------------------------------------------------------------bool selectParent[ps] = {}; int parent[2] = {}; for (int c = 0; c < 2; c++) { double comp; int competitor1, competitor2; double f1, f2;

/* randomly pick 2 strings, compare their fitness */ /* loser may return to the population for next tournament */ do { comp = rand() % ps; } while (selectParent[comp])

competitor1 = comp; do { comp = rand() % ps; } while (selectParent[comp]) competitor2 = comp; f1 = f(x[competitor1] / pow(10, prec) - 4.5, y[competitor1] / pow(10, prec) - 4.5); f2 = f(x[competitor2] / pow(10, prec) - 4.5, y[competitor2] / pow(10, prec) - 4.5); selectParent[competitor1] = (f1< f2)?true:keep[competitor1]; selectParent[competitor2] = (f1< f2)?keep[competitor2]:true; parent[c] = (f1 < f2) ? competitor1 : competitor2; } parentA = parent[0]; parentB = parent[1]; #endif Crossover 使用single point --------------------------------------------------------------------------bitset<24> bitStringAx(x[parentA]); bitset<24> bitStringBx(x[parentB]); bitset<24> bitStringAy(y[parentA]); bitset<24> bitStringBy(y[parentB]); if (((rand() / (double)(RAND_MAX + 1u)) < pc) && (parentA != parentB)) /* 符合機率時, 會替換; 不在機率範圍內時, 不換; 父母若一樣不換*/ { int posXLeft, posXRight, posYLeft, posYRight; int posX = rand() % (bits - 1);

/* 選擇斷點 會有 bits-1 個區間的可以切 */

int posY = rand() % (bits - 1);

Crossover 使用2-point --------------------------------------------------------------------------#if defined TWOPOINT int posX2 = rand() % (bits - 1); int posY2 = rand() % (bits - 1); #endif bitset<24> bitStringMask(0); bitset<24> bitStringTemp(0); #if defined TWOPOINT posXLeft = (posX > posX2) ? posX : posX2; posXRight = (posX > posX2) ? posX2 : posX; posYLeft = (posY > posY2) ? posY : posY2; posYRight = (posY > posY2) ? posY2 : posY; #else

/* 單點 */

#endif

posXLeft = posX; posXRight = 0; posYLeft = posY; posYRight = 0;

for (size_t b = posXRight; b <= posXLeft; b++) { bitStringMask.set(b); }

/* opp: 複製一個 mask */

bitset<24> bitStringMaskOpp(bitStringMask);

/* 令 opp 反過來, 0 變 1, 1 變 0 */ bitStringMaskOpp.flip();

/* 利用 and 替換 */

bitStringTemp = bitStringMask & bitStringAx;

/* 保留Ａ前半部 和 保留Ｂ後半部, 再用 or 合併 */

bitStringAx = (bitStringMaskOpp & bitStringAx) | (bitStringMask & bitStringBx); bitStringBx = (bitStringMaskOpp & bitStringBx) | bitStringTemp;

/* mask 歸零 */

bitStringMask.reset(); for (size_t b = posYRight; b <= posYLeft; b++) { bitStringMask.set(b); } bitStringMaskOpp = bitStringMask; bitStringMaskOpp.flip(); bitStringTemp = bitStringMask & bitStringAy; bitStringAy = (bitStringMaskOpp & bitStringAy) | (bitStringMask & bitStringBy); bitStringBy = (bitStringMaskOpp & bitStringBy) | bitStringTemp; } Mutation 使用bit inversion或displacement -------------------------------------------------------------------------if ((rand() / (double)(RAND_MAX + 1u)) < pm) { #if defined FLIP

/* mutation - bit inversion */

#else

bitStringAx.flip(rand() % (bits - 1)); bitStringBx.flip(rand() % (bits - 1)); bitStringAy.flip(rand() % (bits - 1)); bitStringBy.flip(rand() % (bits - 1));

/* mutation - displacement */

int posX = rand() % (bits - 1); int posX2 = rand() % (bits - 1); int posY = rand() % (bits - 1); int posY2 = rand() % (bits - 1); bool temp; /* 暫存 0,1 */ temp = bitStringAx[posX2]; bitStringAx[posX2] = bitStringAx[posX]; bitStringAx[posX] = temp; temp = bitStringBx[posX2]; bitStringBx[posX2] = bitStringBx[posX]; bitStringBx[posX] = temp; temp = bitStringAy[posY2]; bitStringAy[posY2] = bitStringAy[posY];

#endif

bitStringAy[posY] = temp; temp = bitStringBx[posY2]; bitStringBy[posY2] = bitStringBy[posY]; bitStringBy[posY] = temp; }

暫存下一代 -------------------------------------------------------------------------xChild[p*2] = bitStringAx.to_ulong(); yChild[p*2] = bitStringAy.to_ulong(); xChild[p*2 + 1] = bitStringBx.to_ulong(); yChild[p*2 + 1] = bitStringBy.to_ulong(); cout << xChild[p*2] / pow(10, prec) - 4.5 << ", " << yChild[p*2] / pow(10, prec) - 4.5 << " f(x,y) = " << f(xChild[p*2] / pow(10, prec) - 4.5, yChild[p*2] / pow(10, prec) - 4.5) << '\n'; cout << xChild[p*2 + 1] / pow(10, prec) - 4.5 << ", " << yChild[p*2 + 1] / pow(10, prec) - 4.5 << " f(x,y) = " << f(xChild[p*2 + 1] / pow(10, prec) - 4.5, yChild[p*2 + 1] / pow(10, prec) - 4.5) << '\n'; } replace parents with children – 輪盤法 -------------------------------------------------------------------------#if defined ROULETTE total = 0;

/* sum of population fitness 欲求 max */

for (int p = 0; p < ps; p++) { probMaintain[p] = 0; keep[p] = false; total=total+ 1 / f(x[p] /pow(10, prec)-4.5, y[p]/pow(10, prec)-4.5); } for (int p = 0; p < ps; p++) { probMaintain[p + ps] = 0; keep[p + ps] = false; total = total + 1 / f(xChild[p] / pow(10, prec) - 4.5, yChild[p] / pow(10, prec) - 4.5); }

/* prob of selection for string */

for (int i = 0; i < ps; i++) { probMaintain[i] = (1 / f(x[i] / pow(10, prec) - 4.5, y[i] / pow(10, prec) - 4.5)) / total; probIntervalEndpointMaintain[i] = (i == 0) ? probMaintain[i] : (probIntervalEndpointMaintain[i-1] + probMaintain[i]); } for (int i = 0; i < ps; i++) { probMaintain[i + ps] = (1 / f(xChild[i] / pow(10, prec) - 4.5, yChild[i] / pow(10, prec) - 4.5)) / total;

probIntervalEndpointMaintain[i + ps] = probIntervalEndpointMaintain[i-1+ps] + probMaintain[i+ps]; } for (int i = 0; i < ps; ) { int index; double r = rand() / (double)(RAND_MAX + 1u); for (index = 0; index < 2*ps; index++) { if (r < probIntervalEndpointMaintain[index]) { break; } } if (keep[index] == false) { i++; keep[index] = true; } } #else replace parents with children – 競爭法 -------------------------------------------------------------------------for (int k = 0; k < 2*ps; k++) { keep[k] = false; } for (int c = 0; c < ps; c++) { double comp; int competitorA, competitorB; double fA, fB; do { comp = rand() % (ps * 2); } while (keep[comp]) competitorA = comp; do { comp = rand() % (ps * 2); } while (keep[comp]) competitorB = comp; fA = (competitorA < ps) ? f(x[competitorA] / pow(10, prec) - 4.5, y[competitorA] / pow(10, prec) - 4.5) : f(xChild[competitorA - ps] / pow(10, prec) - 4.5, yChild[competitorA - ps] / pow(10, prec) - 4.5); fB = (competitorB < ps) ? f(x[competitorB] / pow(10, prec) - 4.5, y[competitorB] / pow(10, prec) - 4.5) : f(xChild[competitorB - ps] / pow(10, prec) - 4.5, yChild[competitorB - ps] / pow(10, prec) - 4.5); keep[competitorA] = (fA < fB) ? true : keep[competitorA]; keep[competitorB] = (fA < fB) ? keep[competitorB] : true; } #endif

初始設定如下表所示，這張表為此次 GA 演算法，較佳的參數設定方法，並且在 後續的實驗中會以此張表格為基礎進行實驗。 表一、初始參數設定 Selection Roulette wheel Single point Crossover Probability = 0.9 Bit flip Mutation Probability =0.1 population size=30 population maintenance mechanism [roulette wheel selection] generation size=50 表二、初始參數實驗所得之結果 (x,y) 第一次 (2.70155, 0.40471) 第二次 (3.36469, 0.57883)

f(x,y) 0.0223028

Generation(g) 47

0.0146283

50

第三次

49 (3.37681, 0.57178) 0.0179724 表二為使用表一所設定之參數進行實驗三次，並求得最佳解。 依照表一所給定之條件，並隨機給定母體，當 generation 疊代接近 50 次時， 可得到較優的解。另一方面，將表一之參數進行修正，仍有機會得更優良的解。 以下實驗，僅改變欲實驗之項目條件，來比較當相同條件下該參數所設不同參數， 對解果有何影響。

壹、若給定相同母體，比較 roulette wheel selection 和 tournament selection （其他條件皆相同） 註：使用相同母體以利比較，故先註解“srand(time(0));” 表三、比較 roulette wheel selection 和 tournament selection 及其結果 Selection Single point Crossover Probability = 0.9 Bit flip Mutation Probability =0.1 population size=30 population maintenance mechanism [roulette wheel selection] generation size=50 selection roulette wheel tournament

(x,y) (3.34868, 0.58065) (3.34876, 0.58064)

f(x,y) 0.0147245 0.0147195

Generation 50 49

由此可知，不管是哪個 selection 方法，都在接近最大 generation（50）才求 得最佳解，且使用 roulette wheel 或 tournament 並沒有影響太多。

貳、若給定相同母體，比較 crossover 之 single point 和 2-point （其他條件皆相同） 表四、比較 crossover 之 single point 和 2-point，及其結果 Selection Roulette wheel Crossover

Probability = 0.9 Bit flip Probability =0.1

Mutation

population size=30 population maintenance mechanism [roulette wheel selection] generation size=50 crossover single point 2-point

(x,y) (3.34868, 0.58065) (3.34844, 0.58064)

f(x,y) 0.0147245 0.014723

Generation 50 40

在相同母體情況下，其他條件不變的情況下，single point 和 2-point 的所求得 之結果沒有太大的差異，唯一稍微有所不同的是 2-point 在 generation＝40 時 就找到最佳解了。

參、若給定相同母體，比較 crossover 之 probability （其他條件皆相同） 表五、比較 crossover 之 probability 三個設定，及其結果 Selection Roulette wheel single point Crossover Probability = Bit flip Mutation Probability =0.1 population size=30 population maintenance mechanism [roulette wheel selection] generation size=50 crossover Probability＝0.9 Probability＝0.7 Probability＝0.3

(x,y) (3.34868, 0.58065) (2.21084, 0.08112) (2.11772, 0.08154)

f(x,y) 0.0147245 0.457881 0.477982

Generation 50 48 34

由表格可知，在相同母體相同條件下，改變 crossover probability，差異頗大， crossover probability＝0.9 時得到的最佳解比 crossover probability＝0.7 和 crossover probability＝0.3 更接近。故 crossover probability 越高越容易得到 較優良的解。 肆、若給定相同母體，比較 Mutation 使用 Bit flip 和 Displacement （其他條件皆相同） 表格六、比較 Mutation 使用 Bit flip 和 Displacement，及其結果 Selection Roulette wheel single point Crossover Probability = 0.9 Mutation

Probability =0.1

population size=30 population maintenance mechanism [roulette wheel selection] generation size=50 Mutation (x,y) f(x,y) Generation Bit flip (3.34868, 0.58065) 0.0147245 50 Displacement (2.21084, 0.08112) 0.457881 48 由表格可知，Mutation 使用 Bit flip 所得到的結果 0.014，遠比 Displacement 所得到之結果 0.457 來的好。

伍、若給定相同母體，比較 Mutation 之 probability （其他條件皆相同） 表七、比較 Mutation 之不同的 probability，及其結果 Selection Roulette wheel single point Crossover Probability = 0.9 Bit flip Mutation Probability = population size=30 population maintenance mechanism [roulette wheel selection] generation size=50 Mutation (x,y) f(x,y) Generation Probability =0.1 (3.34868, 0.58065) 0.0147245 50 Probability =0.2 (2.20204, 0.07378) 0.474377 50 Probability =0.3 (2.21892, 0.08528) 0.448822 48 Probability =0.5 (4.74049, 0.72626) 0.130774 48 Probability =0.7 (4.68168, 0.73371) 0.115084 45 Probability =0.9 (2.9851, 0.49621) 3.62482e-05 44

當 Mutation 的 Probability 越接近 0 或 1 時，都能得到較好的解，Mutation 的機率越大代表變動越大，因為該問題是在有限空間當中，不同於路徑規劃問題， 因此推測當 Probability 接近 1 時，在很高的突變機率情況下，造成求解過程變 動相當大，因次更有利於探索整個解的空間，Probability 越接近 0 解越好，再 基因演算法中，則是一個必然的結果。 陸、若給定相同母體，比較 population size （其他條件皆相同） 表八、比較 population size，及其結果 Selection Roulette wheel single point Crossover Probability = 0.9 Bit flip Mutation Probability =0.1 population size= population maintenance mechanism [roulette wheel selection] generation size=50 population size 5 10 30 50 100 200 350 500

(x,y)

f(x,y)

Generation

(0.23346, -1.86824) (3.3284, 0.58644) (3.34868, 0.58065) (4.67724, 0.73434) (2.23102, 0.07634) (3.03797, 0.50733) (2.99945, 0.49987) (3.00001, 0.5)

9.46182 0.0206779 0.0147245 0.115327 0.471415 0.000312257 4.93958e-08 1.57812e-10

31 50 50 48 44 48 23 8

population size 越大表示協助搜尋解的 Parent 數量越多，不論在何種演算法搜 尋解的群體越大，越能找尋到更好的解，在本次 GA 演算法中很明顯的可以看到 當 population size=500 時得到負 10 次方的解(1.57812e-10)，且只經過 8 代 就找到解

柒、若給定相同母體，比較 population maintenance mechanism （其他條件皆相同） 表九、比較 population maintenance mechanism，及其結果 Selection Roulette wheel single point Crossover Probability = 0.9 Bit flip Mutation Probability =0.1 population size=30 population maintenance mechanism generation size=50 population maintenance (x,y) f(x,y) Generation mechanism roulette wheel (3.34868, 0.58065) 0.0147245 50 tournament (3.34876, 0.58064) 0.0147195 49 不論是用 roulette wheel 或是 tournament，來進行 parent 的選擇，其結果都 沒有明顯的差異，但是 tournament 比 roulette wheel 少一次疊代就找到最佳 解且結果相對好一點。競爭法基本上不同於 roulette wheel 會有機率將較劣的 parent 留下，因此雖然不明顯但是 tournament 是相對較好的方法。 捌、若給定相同母體，比較 generation size （其他條件皆相同） 表十、比較 generation size，及其結果 Selection Roulette wheel single point Crossover Probability = 0.9 Bit flip Mutation Probability =0.1 population size=30 population maintenance mechanism [roulette wheel selection] generation size= generation size 5 10 50 100 200 500

(x,y) (3.00028, 0.58578) (3.00044, 0.58578) (3.34868, 0.58065) (3.3482, 0.58088) (3.34693, 0.57952) (3.3474, 0.57955)

f(x,y) 0.196021 0.19587 0.0147245 0.0148291 0.0142989 0.0143095

Generation 3 8 50 88 176 484

因為是在有限解中找答案，因此當疊代達 50 次找到較佳的解後，後續即使疊代 至 500 次仍沒有得到明顯更優的解。

與其他演算法比較 演算法 最佳解

SA

0.0001

PSO Global best Neighborhood

GA 1.57812e-10