APS算法分析之五基因算法

1、APS算法分析之五基因算法基因算法 GA （Genetic Algorithm)是基于自然系統(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)題等。 和本地搜索策略不同的是，GA和 Tabu 搜索 (TS) 在搜索中比較一最較差的目標(biāo)函數(shù)值，接受臨時(shí)的方案來(lái)克服本地優(yōu)化，找到全局優(yōu)化。然而，因?yàn)?，GA 和TS 是探索法，可能不是最佳的方案，但是

2、，大部分情況下，至少可以找到一個(gè)非常好可行的方案。 GA是隨機(jī)搜尋算法，因?yàn)橛幂^差目標(biāo)函數(shù)值的方案用特別的可能性是可以接受的。因此，用一個(gè)一樣的初始方案開(kāi)始，和一樣的參數(shù)設(shè)置，也可能導(dǎo)致不同的方案。而用確定性搜索算法如TS就會(huì)導(dǎo)致同樣的方案。 基本概念：人種保持在內(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ē)間流水線(xiàn)排序問(wèn)題 N 任務(wù)必須在 M 機(jī)器排程 每一任務(wù)包含 m 工序 每一工序需要不同的機(jī)器

3、所有任務(wù)在同樣的加工訂單上處理 特別假設(shè) : 1，所有任務(wù)在零時(shí)間可以得到 2，工序的準(zhǔn)備時(shí)間包含在加工時(shí)間里 3，對(duì)所有機(jī)器所有工序的順序已定義 4，目標(biāo): 最小化時(shí)間跨度 適應(yīng)函數(shù):對(duì)一人種的目標(biāo)函數(shù)值的所有成員，如計(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)

4、= 10*f(23541) = 5*整個(gè)人種的適應(yīng)值: 50 (在人種里的所有個(gè)體的適應(yīng)合計(jì))復(fù)制 / 選擇 大部分公用的復(fù)制/選擇概率是給定的。是排列的適應(yīng)值和共計(jì)種群的適應(yīng)值的商 我們的案例, 我們得到*概率(13452) = 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

5、.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的位置，在二進(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: - 2 3 - 5; 子項(xiàng) 2: 2 - - 3 - 子項(xiàng) 1: 4 2 3 1 5; 子項(xiàng)2: 2 1 4 3 5有許多不同交叉操作者。這里，“基于同樣訂單的交叉”被顯示。 父項(xiàng) 1: 1 - - 4 - -在父項(xiàng)2 出現(xiàn): 4 - - 1 - 父項(xiàng)2: - 4 5 - 1 - 在父項(xiàng)1出現(xiàn) 1: - 1 4 - 5變異1. 選擇一個(gè)體的父項(xiàng) 2. 選擇隨機(jī)兩個(gè)位置，在這個(gè)父項(xiàng)排列中 3. 在這個(gè)間隔里的新順序值是隨機(jī)產(chǎn)生的。 如父項(xiàng): 12345兩個(gè)位置: 2 和 4老的順序 : 2 3 4 - 新順序: 4 2 3= 新排列: 1 4 2 3 5GA的優(yōu)勢(shì)：