車間作業(yè)調(diào)度jobshopscheduling講解-閱讀頁
2025-06-01 13:26本頁面
【正文】 0世紀(jì) 60年代末期到 70年代初期，主要由美國 Michigan大學(xué)的 John Holland與其同事、學(xué)生們研究形成了一個(gè)較完整的理論和方法，從試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過程入手，模擬生物進(jìn)化的機(jī)制來構(gòu)造人工系統(tǒng)的模型。 遺傳算法概述 ?從 1985年在美國卡耐基 遺傳算法基本概念和術(shù)語 ?遺傳算法是模擬前述生物進(jìn)化過程的計(jì)算模型。 ?染色體 (chromosome)：具有遺傳性質(zhì)基因序列。該集合內(nèi)個(gè)體數(shù)稱為群體的大小。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對較少，甚至逐漸滅絕。一般而言，選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程。這個(gè)過程又稱基因重組（ rebination），俗稱“雜交”。 基本遺傳算法的實(shí)現(xiàn)方法 ?各種不同的遺傳算法都有相同的的特點(diǎn)，即通過對生物遺傳和進(jìn)化過程中選擇、交叉、變異機(jī)理的模仿，來完成對問題最優(yōu)解的自適應(yīng)搜索過程。 SGA只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。 遺傳算法解決 Job shop的幾個(gè)重要構(gòu)成要素 （ 1）染色體編碼方法 {1 2 3 ； 3 1 2 ； 2 3 1} 基本遺傳算法的構(gòu)成要素 （ 2）交叉過程 下面是一種基于最長公共子序列的交叉算符，對兩個(gè)父親個(gè)體的每個(gè)機(jī)器都進(jìn)行如下操作，產(chǎn)生兩個(gè)子代個(gè)體： 遺傳算法的幾個(gè)重要構(gòu)成要素 （ 3）適應(yīng)度評價(jià)函數(shù) 函數(shù)的主要部分是基于最大完工時(shí)間(Makespan)。特例：兩個(gè)解相同個(gè)體的后代和父代的解也相同。 Step3. 根據(jù)適應(yīng)度函數(shù)，對種群進(jìn)行維護(hù)，淘汰掉適應(yīng)度低的個(gè)體。利用Memetic Algorithm在解決 Job – Shop時(shí)，可以取得非常好的效果。 Hybrid Evolution AlgorithmMemetic 部分算例的解 : 謝謝大家
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1