APS算法分析之五基因算法

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

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

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

4、的所有成員，如計(jì)算跨度。從這個(gè)較低的跨度被決定和得到最高的適應(yīng)值fmax.,從不同的人種結(jié)果中的每一成員的適應(yīng)值到它的前輩的索引清單中的適應(yīng)值。這個(gè)作法就保證了為一較低跨度的排程選擇的可能性是高的?？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* 整個(gè)人種的適應(yīng)值：50(在人種里的所有個(gè)體的適應(yīng)合計(jì))復(fù)制/選擇大部分公用的復(fù)制/選擇概率是給定的。是排列的適應(yīng)值和共計(jì)種群的適應(yīng)值的商*我們的案例，我們得到* 概率（134

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

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