從遺傳算法的觀點來看,解的進化主要是靠選擇機制和交叉策略來完成,變異只是產生
新個體的輔助方法, 它決定了遺傳算法的局部搜索能力。交叉算子和變異算子相互配合,
***同完成對搜索空間的全局搜索和局部搜索, 從而使遺傳算法能夠以良好的搜索性能完成
最優化問題的尋優過程,變異概率壹般取為0.0001~0.1。變異算子壹般采用旋轉變異或位置
變異,設要排放的零件總數為n。
旋轉變異的思想是產生[1,n]之間的壹個隨機數num,將該數取其相反數。
例如:產生的隨機數 num=5
染色體為:A={ -3 , 5 , 7 ,-1 , 6 , 8 ,-2 , 4}
變異後的結果為:A’={ -3 , 5 , 7 ,-1 ,-6, 8 ,-2 , 4}
位置變異的思想是產生[1,n]之間的兩個隨機數num1、num2,將兩個位置顛倒。
例如:產生的隨機數 num1=3,num2=6
染色體為:A={ -3 , 5 , 7 ,-1 , 6 , 8 ,-2 , 4}
變異後的結果為:A’={ -3 , 5 , 8 ,-1 ,6,7 ,-2 , 4}
2. 6 適應度函數
適應度函數定義的好壞對問題的求解效果有很大影響。常見的定義適應度函數的方法有
兩種:壹種從排樣圖的最大高度方面考慮,要求盡量使排樣圖的最大高度值小,壹般用最大
高度值的倒數來表示。另壹種是從廢料再利用的角度進行考慮的,要求盡可能的提高可再利
用廢料的利用率(可再利用廢料是指處於排樣圖最高輪廓線和排樣圖最大高度水平線之間的
部分)。針對板材的兩種情況,分別定義了不同的適應度函數,假設排入的矩形件的總面積
為area1[4]。
(1) 定寬無限長的板材情況
對於定寬無限長的板材,壹般用排樣高度來評價排樣的優劣,適應度函數如下:
Fitness area1
h w
=
×
其中,h 為排樣圖的最大高度,w 為板材的寬度。
(2) 定寬定長的板材情況
這種情況下的適應度函數如下:
1
2
Fitness area
area h w
=
+ ×
其中,area2 為去掉最後壹張板材的總面積,h 為最後壹張板材的排樣圖的最大高度,w 為
- 5 -
最後壹張板材的寬度。
這裏適應度函數 Fitness 的物理意義就是板材的利用率。
2. 7 選擇算子
在生物的遺傳和自然進化過程中,對生存環境適應程度較高的物種將有更多的機會遺傳
到下壹代;而對生存環境適應程度較低的生物遺傳到下壹代的機會就相對較小。模仿這個過
程,遺傳算法使用選擇算子(或稱復制算子,Reproduction Operator)來對群體中的個體進
行優勝劣汰操作:適應度較高的個體被遺傳到下壹代群體的概率較大;適應度較低的個體被
遺傳到下壹代群體的概率較小。遺傳算法中的選擇操作就是用來確定如何從父代群體中按某
種方法選取哪些個體遺傳到下壹代群體中的壹種遺傳運算。
選擇算子采用最優保存策略[3],即把當前群體中適應度最高的個體不