APS算法分析之五基因算法

1、APS算法分析之五基因算法基因算法GA(GeneticAlgorithm)是基于自然系統(tǒng)的進(jìn)化過程，算法創(chuàng)立一初始化方案的人種，基于初始化方案，算法再產(chǎn)生新的一個人種，通過許多代的連續(xù)過程，方案的質(zhì)量被改善，算法結(jié)束于當(dāng)達(dá)到一特別的中斷規(guī)則(如.當(dāng)加工時間已經(jīng)達(dá)到)，它實際上是隨機(jī)搜尋算法。它已經(jīng)用于許多優(yōu)化問題，如銷售員旅行問題，貨柜包裝問題，排程問題，順序問題，設(shè)施布局問題等。和本地搜索策略不同的是，GAnTabu搜索(TS)在搜索中比較一最較差的目標(biāo)函數(shù)值，接受臨時的方案來克服本地優(yōu)化，找到全局優(yōu)化。然而，因為，GA和TS是探索法，可能不是最佳的方案，但是，大部分情況下，至少可以找到一個

2、非常好可行的方案。GA是隨機(jī)搜尋算法，因為用較差目標(biāo)函數(shù)值的方案用特別的可能性是可以接受的。因此，用一個一樣的初始方案開始，和一樣的參數(shù)設(shè)置，也可能導(dǎo)致不同的方案。而用確定性搜索算法如TS就會導(dǎo)致同樣的方案?；靖拍睿喝朔N保持在內(nèi)存為進(jìn)一步改善的一列數(shù)字集，新列數(shù)字使用特別的基因運作產(chǎn)生。選擇是根據(jù)它們的適應(yīng)性來選擇出“父代”基本基因運作： 復(fù)制 交叉 變異一人種的數(shù)字串選擇可以用一特別的數(shù)字串的進(jìn)化函數(shù)產(chǎn)生后一代。進(jìn)化函數(shù)反映染色體的“適應(yīng)”。比如：在車間流水線排序問題 N任務(wù)必須在M機(jī)器排程 每一任務(wù)包含m工序 每一工序需要不同的機(jī)器 所有任務(wù)在同樣的加工訂單上處理特別假設(shè)：1 ,所有任務(wù)

3、在零時間可以得到2 ,工序的準(zhǔn)備時間包含在加工時間里3 ,對所有機(jī)器所有工序的順序已定義4 ，目標(biāo)：最小化時間跨度GR-案例2個任務(wù)，5T工序和7臺機(jī)器：- 圖不：123452345(12024£«1012- 準(zhǔn)備時間和加工時間用方格的長度來表示.如,在第2臺機(jī)器，工序1和工序4有W小時;工序2,3,和工序5杳1小時- 總時間跨度是口2345）：12小時GA-案例初始化人(第一代)：-4排列 1W452Q跨度11 12345整度12 24531跨度：13 23541-=跨度：15 選擇:選擇那一事仁科例)用作犍代.=二適應(yīng)函數(shù)二適度值排列的范圍適應(yīng)函數(shù)：對一人種的目標(biāo)函數(shù)值

4、的所有成員，如計算跨度。從這個較低的跨度被決定和得到最高的適應(yīng)值fmax.,從不同的人種結(jié)果中的每一成員的適應(yīng)值到它的前輩的索引清單中的適應(yīng)值。這個作法就保證了為一較低跨度的排程選擇的可能性是高的?？s減規(guī)模d影響到選擇的可能性。必須的條件是：fmin>0.適應(yīng)值(用fmax=20,d=5=>fmin=5):* f(13452)=20* f(12345)=15* f(24531)=10* f(23541)=5* 整個人種的適應(yīng)值：50(在人種里的所有個體的適應(yīng)合計)復(fù)制/選擇大部分公用的復(fù)制/選擇概率是給定的。是排列的適應(yīng)值和共計種群的適應(yīng)值的商*我們的案例，我們得到* 概率（134

5、52）=20/50=0.4* 概率（12345）=15/50=0.3* 概率（24531）=10/50=0.2* 概率（23541）=5/50=0.1在下一代里，保留一個復(fù)制操作者選擇的機(jī)會。它是成比例列出適應(yīng)。就像排列的選擇如一個孩子一個父親。用較低跨度排列，比那些用低的適應(yīng)值有一較高生存/選擇可能性。那么（0,1）-隨機(jī)變量產(chǎn)生，如果低于0.4,那么排列選擇13452,如果在0.4和0.7,之間，那么12345被選擇。如果在0.7和0.9之間，那么24531被選擇，如果大于0.9,那么排列23541被復(fù)制。交叉 選擇兩個父項結(jié)構(gòu)，從選擇的個體中 產(chǎn)生一二進(jìn)制串m長度 對子項1:拿所有父項1

6、的位置，在二進(jìn)制串里用“1”，對子項2:拿所有父項2的位置，在二進(jìn)制串里用“0” 父項1的其它因素被存，作為在父項2里出現(xiàn)時。然后，他們被插入子項1的自由位置。對子項2也是同樣的過程。例如： 選擇12345（父項1）和24531（父項2） 二進(jìn)制字串：01101 子項1:-23-5;子項2:2-3- 子項1:42315;子項2:21435有許多不同交叉操作者。這里，“基于同樣訂單的交叉”被顯示。父項1:1-4->在父項2出現(xiàn)：4-1-父項2:-45-1->在父項1出現(xiàn)1:-14-51 .選擇一個體的父項2 .選擇隨機(jī)兩個位置，在這個父項排列中3 .在這個間隔里的新順序值是隨機(jī)產(chǎn)生的。如父項:12345兩個位置：2和4老的順序：234->新順序：423=>新排列J:14235GA.總結(jié)Ooo°OOOOOO00- k代- 在k代里為復(fù)制選擇排冽- 在k代里為交叉選擇排列- 在k代里為變異選擇排列- 在k代里不選擇排列,中止條件：