APS算法分析之五基因算法

文章來源：泛普軟件基因算法 GA （Genetic Algorithm)是基于自然系統(tǒng)的進(jìn)化過程，算法創(chuàng)立一初始化方案的人種，基于初始化方案, 算法再產(chǎn)生新的一個人種，通過許多代的連續(xù)過程，方案的質(zhì)量被改善，算法結(jié)束于當(dāng)達(dá)到一特別的中斷規(guī)則 (如. 當(dāng)加工時間已經(jīng)達(dá)到)，它實(shí)際上是隨機(jī)搜尋算法。它已經(jīng)用于許多優(yōu)化問題，如銷售員旅行問題，貨柜包裝問題，排程問題，順序問題，設(shè)施布局問題等。　和本地搜索策略不同的是，GA和 Tabu 搜索 (TS) 在搜索中比較一最較差的目標(biāo)函數(shù)值，接受臨時的方案來克服本地優(yōu)化，找到全局優(yōu)化。然而，因?yàn)?，GA 和TS 是探索法，可能不是最佳的方案，但是，大部分情況下，至少可以找到一個非常好可行的方案。　 GA是隨機(jī)搜尋算法，因?yàn)橛幂^差目標(biāo)函數(shù)值的方案用特別的可能性是可以接受的。因此，用一個一樣的初始方案開始，和一樣的參數(shù)設(shè)置，也可能導(dǎo)致不同的方案。而用確定性搜索算法如TS就會導(dǎo)致同樣的方案。基本概念：人種保持在內(nèi)存為進(jìn)一步改善的一列數(shù)字集，新列數(shù)字使用特別的基因運(yùn)作產(chǎn)生。選擇是根據(jù)它們的適應(yīng)性來選擇出“父代” 基本基因運(yùn)作：

復(fù)制
交叉
變異

一人種的數(shù)字串選擇可以用一特別的數(shù)字串的進(jìn)化函數(shù)產(chǎn)生后一代。進(jìn)化函數(shù)反映染色體的“適應(yīng)”。比如：在車間流水線排序問題

N 任務(wù)必須在 M 機(jī)器排程
每一任務(wù)包含 m 工序
每一工序需要不同的機(jī)器
所有任務(wù)在同樣的加工訂單上處理

特別假設(shè) : 1，所有任務(wù)在零時間可以得到 2，工序的準(zhǔn)備時間包含在加工時間里 3，對所有機(jī)器所有工序的順序已定義 4，目標(biāo): 最小化時間跨度適應(yīng)函數(shù):
對一人種的目標(biāo)函數(shù)值的所有成員，如計算跨度。從這個較低的跨度被決定和得到最高的適應(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)值的商
我們的案例, 我們得到

*概率(13452) = 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ù)制。

交叉

選擇兩個父項(xiàng)結(jié)構(gòu)，從選擇的個體中
產(chǎn)生一二進(jìn)制串m長度
對子項(xiàng) 1: 拿所有父項(xiàng)1的位置，在二進(jìn)制串里用“1”，對子項(xiàng)2：拿所有父項(xiàng)2的位置，在二進(jìn)制串里用“0”
父項(xiàng)1的其它因素被存，作為在父項(xiàng)2里出現(xiàn)時。然后，他們被插入子項(xiàng)1的自由位置。對子項(xiàng)2也是同樣的過程。

例如:

選擇 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. 選擇一個體的父項(xiàng)
2. 選擇隨機(jī)兩個位置，在這個父項(xiàng)排列中
3. 在這個間隔里的新順序值是隨機(jī)產(chǎn)生的。
如
父項(xiàng): 12345
兩個位置: 2 和 4
老的順序 : 2 3 4 -> 新順序: 4 2 3

=> 新排列: 1 4 2 3 5
GA的優(yōu)勢：

基于在排序里的高性能
專注于排程問題(沒有太多的基于限制的約束）

APS的GA: 主要應(yīng)用在生產(chǎn)計劃與詳細(xì)排程，可以產(chǎn)生唯一可行的方案。最小化時間和優(yōu)化排序 (目標(biāo): 最小化沖突）。來源：AMT

發(fā)布：2007-04-22 10:21 編輯：泛普軟件 · xiaona [打印此頁] [關(guān)閉]

相關(guān)欄目：

相關(guān)文章：

上一篇：面向?qū)ο蠊こ棠０鍞?shù)據(jù)模型研究

下一篇：分布式網(wǎng)絡(luò)化制造系統(tǒng)構(gòu)想

哈爾濱OA系統(tǒng)

聯(lián)系方式

成都公司：成都市成華區(qū)建設(shè)南路160號1層9號

重慶公司：重慶市江北區(qū)紅旗河溝華創(chuàng)商務(wù)大廈18樓

咨詢：400-8352-114

加微信，免費(fèi)獲取試用系統(tǒng)

QQ在線咨詢

電話咨詢：
4008352114

QQ在線咨詢

APS算法分析之五基因算法

泛普哈爾濱OA快博其他應(yīng)用