哈爾濱OA快博
當(dāng)前位置：工程項目OA系統(tǒng) > 泛普各地 > 黑龍江OA系統(tǒng) > 哈爾濱OA系統(tǒng) > 哈爾濱OA快博
APS算法分析之五基因算法
文章來源：泛普軟件
基因算法 GA （Genetic Algorithm)是基于自然系統(tǒng)的進化過程，算法創(chuàng)立一初始化方案的人種 ，基于初始化方案, 算法再產(chǎn)生新的一個人種，通過許多代的連續(xù)過程，方案的質(zhì)量被改善 ，算法結(jié)束于當(dāng)達(dá)到一特別的中斷規(guī)則 (如. 當(dāng)加工時間已經(jīng)達(dá)到)，它實際上是隨機搜尋算法 。
它已經(jīng)用于許多優(yōu)化問題，如銷售員旅行問題，貨柜包裝問題，排程問題，順序問題，設(shè)施布局問題等。
和本地搜索策略不同的是，GA和 Tabu 搜索 (TS) 在搜索中比較一最較差的目標(biāo)函數(shù)值，接受臨時的方案來克服本地優(yōu)化，找到全局優(yōu)化。然而，因為，GA 和TS 是探索法，可能不是最佳的方案，但是，大部分情況下，至少可以找到一個非常好可行的方案。
GA是隨機搜尋算法，因為用較差目標(biāo)函數(shù)值的方案用特別的可能性是可以接受的。因此，用一個一樣的初始方案開始，和一樣的參數(shù)設(shè)置，也可能導(dǎo)致不同的方案。而用確定性搜索算法如TS就會導(dǎo)致同樣的方案。
基本概念：人種保持在內(nèi)存為進一步改善的一列數(shù)字集 ，新列數(shù)字使用特別的基因運作產(chǎn)生。 選擇是根據(jù)它們的適應(yīng)性來選擇出“父代”
基本基因運作：
對一人種的目標(biāo)函數(shù)值的所有成員，如計算跨度。從這個較低的跨度被決定和得到最高的適應(yīng)值fmax.，從不同的人種結(jié)果中的每一成員的適應(yīng)值到它的前輩的索引清單中的適應(yīng)值。這個作法就保證了為一較低跨度的排程選擇的可能性是高的。縮減規(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ù)制 / 選擇
*概率(12345) = 15/50 = 0.3
*概率(24531) = 10/50 = 0.2
*概率(23541) = 5/50 = 0.1
在下一代里，保留一個復(fù)制操作者選擇的機會。它是成比例列出適應(yīng)。就像排列的選擇如一個孩子一個父親。
用較低跨度排列，比那些用低的適應(yīng)值有一較高生存/選擇可能性。
那么 (0,1)-隨機變量產(chǎn)生，如果低于 0.4, 那么排列選擇 13452，如果在 0.4 和 0.7, 之間，那么 12345 被選擇。如果在0.7 和0.9之間, 那么 24531被選擇，如果大于0.9, 那么排列 23541 被復(fù)制。
交叉
父項 1: 1 - - 4 - ->在父項2 出現(xiàn): 4 - - 1 -
父項2: - 4 5 - 1 -> 在父項1出現(xiàn) 1: - 1 4 - 5
變異
1. 選擇一個體的父項
2. 選擇隨機兩個位置，在這個父項排列中
3. 在這個間隔里的新順序值是隨機產(chǎn)生的。
如
父項: 12345
兩個位置: 2 和 4
老的順序 : 2 3 4 -> 新順序: 4 2 3
=> 新排列: 1 4 2 3 5
GA的優(yōu)勢：
- 復(fù)制
- 交叉
- 變異
- N 任務(wù)必須在 M 機器排程
- 每一任務(wù)包含 m 工序
- 每一工序需要不同的機器
- 所有任務(wù)在同樣的加工訂單上處理
對一人種的目標(biāo)函數(shù)值的所有成員，如計算跨度。從這個較低的跨度被決定和得到最高的適應(yīng)值fmax.，從不同的人種結(jié)果中的每一成員的適應(yīng)值到它的前輩的索引清單中的適應(yīng)值。這個作法就保證了為一較低跨度的排程選擇的可能性是高的。縮減規(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)值的商
- 我們的案例, 我們得到
*概率(12345) = 15/50 = 0.3
*概率(24531) = 10/50 = 0.2
*概率(23541) = 5/50 = 0.1
在下一代里，保留一個復(fù)制操作者選擇的機會。它是成比例列出適應(yīng)。就像排列的選擇如一個孩子一個父親。
用較低跨度排列，比那些用低的適應(yīng)值有一較高生存/選擇可能性。
那么 (0,1)-隨機變量產(chǎn)生，如果低于 0.4, 那么排列選擇 13452，如果在 0.4 和 0.7, 之間，那么 12345 被選擇。如果在0.7 和0.9之間, 那么 24531被選擇，如果大于0.9, 那么排列 23541 被復(fù)制。
交叉
- 選擇兩個父項結(jié)構(gòu)，從選擇的個體中
- 產(chǎn)生一二進制串m長度
- 對子項 1: 拿所有父項1的位置，在二進制串里用“1”，對子項2：拿所有父項2的位置，在二進制串里用“0”
- 父項1的其它因素被存，作為在父項2里出現(xiàn)時。然后，他們被插入子項1的自由位置。對子項2也是同樣的過程 。
- 選擇 12345 (父項 1) 和 24531 (父項 2)
- 二進制字串: 01101
- 子項 1: - 2 3 - 5; 子項 2: 2 - - 3 -
- 子項 1: 4 2 3 1 5; 子項2: 2 1 4 3 5
父項 1: 1 - - 4 - ->在父項2 出現(xiàn): 4 - - 1 -
父項2: - 4 5 - 1 -> 在父項1出現(xiàn) 1: - 1 4 - 5
變異
1. 選擇一個體的父項
2. 選擇隨機兩個位置，在這個父項排列中
3. 在這個間隔里的新順序值是隨機產(chǎn)生的。
如
父項: 12345
兩個位置: 2 和 4
老的順序 : 2 3 4 -> 新順序: 4 2 3
=> 新排列: 1 4 2 3 5
GA的優(yōu)勢：
- 基于在排序里的高性能
- 專注于排程問題(沒有太多的基于限制的約束 ）
相關(guān)欄目：
相關(guān)文章：
- 1企業(yè)服務(wù)器互通的價值
- 2無線局域網(wǎng)的未來
- 3施工項目如何實施風(fēng)險管理
- 4商業(yè)智能行業(yè)化從哪里開始？
- 5從業(yè)務(wù)流程角度理解面向服務(wù)的概念
- 6構(gòu)筑中小企業(yè)內(nèi)部物資配送新模式
- 7銀行業(yè)數(shù)據(jù)倉庫的應(yīng)用
- 8預(yù)測項目結(jié)果的幾種方法
- 9KM實踐：亞信剛性和柔性的平衡
- 10讓業(yè)務(wù)與ERP系統(tǒng)更好的集成
- 11路由器與交換機組網(wǎng)分析比較
- 12供應(yīng)鏈中的“孫子兵法”
- 13選好實施方IT項目成功的最后環(huán)節(jié)
- 14小公司用好IT一樣發(fā)家
- 15IT項目需要足夠重視操作階段
- 16“無線”模式也可繞道快行
- 17IT服務(wù)企業(yè)轉(zhuǎn)型路上勵精圖志
- 18向Linux遷移的用戶移植分析
- 19行業(yè)信息化：車業(yè)精益變革
- 20APS算法之六禁忌搜索TS（上）
- 21MES的技術(shù)架構(gòu)
- 22如何構(gòu)建工程項目中企業(yè)知識管理框架
- 23短期規(guī)劃策動中小企業(yè)IT購買
- 24全球頂級CRM產(chǎn)品的“技術(shù)架構(gòu)”揭密
- 25APS算法分析之五基因算法
- 26漸近式產(chǎn)品生命周期管理變革
- 27ERP需要全程的流程變革
- 28iSCSI技術(shù)發(fā)展及未來展望
- 29思科是怎樣應(yīng)用智能化的信息網(wǎng)絡(luò)
- 30奧克斯集團信息化之路的成功經(jīng)驗
哈爾濱OA系統(tǒng)
聯(lián)系方式
成都公司：成都市成華區(qū)建設(shè)南路160號1層9號
重慶公司：重慶市江北區(qū)紅旗河溝華創(chuàng)商務(wù)大廈18樓
