【文章內(nèi)容簡(jiǎn)介】 于該生物的適應(yīng)性強(qiáng)不強(qiáng)。如果適應(yīng)性強(qiáng)，那么，此生物就能繁殖下一代延續(xù)下去而不被自然界淘汰，相反，不能適應(yīng)自然界環(huán)境就是絕種。我們運(yùn)用這種思想來(lái)說(shuō)明遺傳算法問(wèn)題，對(duì)所求問(wèn)題的某種初始種群能不能被遺傳下去，最后求出最優(yōu)或次優(yōu)解。這時(shí)適應(yīng)度高的個(gè)體最有可能遺傳下一代，適應(yīng)度低的個(gè)體就有可能被淘汰。適應(yīng)度低的個(gè)體不一定被淘汰，一般可通過(guò)交叉、變異操作來(lái)增加它的適應(yīng)性。1 選擇操作在遺傳操作時(shí)，希望把好的個(gè)體(適應(yīng)度高的個(gè)體)保留下來(lái)，組成下一代種群個(gè)體，不好的個(gè)體要么淘汰要么變異(提出編碼多樣性)。選擇好的個(gè)體留下來(lái)的方法叫選擇操作。一般情況下，我們?cè)谶M(jìn)行算子設(shè)計(jì)時(shí)，把選擇操作作為第一步。選擇操作的選取在遺傳算法中是很重要的一個(gè)環(huán)節(jié)，它決定父代種群中哪些個(gè)體，以及它們能以多大的可能性被挑選來(lái)復(fù)制或遺傳到下一代的進(jìn)化操作，它模擬的是“優(yōu)勝劣汰”的自然進(jìn)化原理。選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)上，其主要目的是為遺傳算法的搜索提供導(dǎo)向，使算法能夠快速搜索到問(wèn)題的最優(yōu)解。下面介紹幾種常用的選擇操作[18]：（1）轉(zhuǎn)輪法選擇選擇方法是目前遺傳算法中最常用的選擇方法，它也叫賭輪或蒙特卡羅選擇?；舅枷胧菑呐f的種群中選擇適應(yīng)度高的染色體，放入匹配集(緩沖區(qū))，為以后染色體交換、變異，產(chǎn)生新的染色體作準(zhǔn)備。按各染色體適應(yīng)度大小比例來(lái)決定其被選擇數(shù)目的多少。某染色體被選的概率:Pc=f(xi)f(xi)xi為種群中第i個(gè)染色體，f(xi)為第i個(gè)染色體的適應(yīng)度值，f(xi)為種群中所有染色體適應(yīng)度之和。具體步驟如下:1）計(jì)算各染色體適應(yīng)度值2）累計(jì)所有染色體適應(yīng)度值，記錄中間累加值Smid和最后累加值sum=f(xi)3）產(chǎn)生一個(gè)隨機(jī)數(shù)N，0Nsum4）選擇對(duì)應(yīng)中間累加值Smid的第一個(gè)染色體進(jìn)入交換集5）重復(fù)(3)和(4)，直到獲得足夠的染色體。（2）最佳個(gè)體保留選擇思想是：在進(jìn)行遺傳算法時(shí)，通過(guò)交叉和變異操作會(huì)使適應(yīng)性低的個(gè)體提高適應(yīng)度值以增加群體的多樣性。但同時(shí)，好的個(gè)體的適應(yīng)度有可能被交叉和變異操作變得壞了，這是我們不希望看到的。最佳個(gè)體保留選擇即當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用它來(lái)替換掉本代群體中經(jīng)過(guò)先按賭盤(pán)選擇機(jī)制執(zhí)行遺傳算法的選擇功能，然后把群體中適應(yīng)度最高的個(gè)體不進(jìn)行交叉和變異而直接復(fù)制到下一代中。采用這種選擇方法的優(yōu)點(diǎn)是，進(jìn)化過(guò)程中某一代的最優(yōu)解可不被交叉和變異操作破壞。缺點(diǎn)是局部最優(yōu)個(gè)體的數(shù)里可能會(huì)急速增加而使進(jìn)化陷于局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象。另外，最佳個(gè)體保留選擇方法還可以加以推廣，即在每一代的進(jìn)化過(guò)程中保留多個(gè)最優(yōu)個(gè)體不參加交叉和變異操作，而直接將它們復(fù)制到下一代群體中。這種選擇方法稱為穩(wěn)態(tài)復(fù)制。（3）排序選擇對(duì)全體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)體被選中的概率。適應(yīng)度越高的個(gè)體，其選擇概率越大?？梢苑乐埂霸缡臁爆F(xiàn)象和停滯現(xiàn)象的出現(xiàn)，缺點(diǎn)是選擇標(biāo)準(zhǔn)有可能過(guò)于偏離個(gè)體的適應(yīng)度，延緩優(yōu)化進(jìn)程。還有一些其它選擇，比如錦標(biāo)賽選擇、EP選擇等，在這里就不再敘述。2 交叉操作遺傳算法中的交叉操作，指的是在兩個(gè)染色體中隨機(jī)選擇要交換的部分進(jìn)行交換而形成兩個(gè)新的染色體。交叉操作是遺傳算法的一個(gè)重要特征，交叉操作在遺傳算法中有重要作用，遺傳算法主要通過(guò)交叉操作來(lái)產(chǎn)生下一代。（1）單點(diǎn)交叉在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新的個(gè)體。例如圖所示：（2）兩點(diǎn)交叉是指在個(gè)體編碼串中隨機(jī)設(shè)置了二個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。例如圖所示：（3）均勻交叉均勻交叉是指兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。均勻交叉實(shí)際上可歸屬于多點(diǎn)交叉的范圍，其具體運(yùn)算可通過(guò)設(shè)置屏蔽字來(lái)確定新個(gè)體的各個(gè)基因如何由哪一個(gè)父代個(gè)體來(lái)提供。（4）次序交叉(Order Crossover，OX)方法是首先隨機(jī)確定兩個(gè)交叉位置，并交換交叉點(diǎn)之間的片段，并從第2交叉位置起在原先父代個(gè)體中刪除將從另一父代個(gè)體交換過(guò)來(lái)的基因，然后從第2交叉位置后開(kāi)始填入剩余基因。（5）單位置次序交叉設(shè)有父代p1和父代p2，單位置交叉只產(chǎn)生一個(gè)交叉位置，然后保留父代個(gè)體p1交叉位置前的基因片段，并在另一父代個(gè)體p2中刪除p1中保留的基因，進(jìn)而將剩余基因片段填入p1的交叉位置后來(lái)得到后代個(gè)體q1。（6）基于位置的交叉(positionbased Crossover，PX)基于位置的交叉的步驟是隨機(jī)選取一些位置，然后交換被選中位置上的基因，并在原先父代個(gè)體中刪除從另一父代個(gè)體交換過(guò)來(lái)的基因，接著從第1個(gè)基因位置起依次在未選中位置填入剩余基因。（7）循環(huán)交叉cycle crossover，CX)循環(huán)交叉將另一個(gè)父代個(gè)體作為參照，以對(duì)當(dāng)前父代個(gè)體中的位置進(jìn)行重組。先與另一父代個(gè)體實(shí)現(xiàn)一個(gè)循環(huán)鏈，并將對(duì)應(yīng)位置的基因填入相應(yīng)的位置。循環(huán)組成后再將另一個(gè)父代個(gè)體各位置的基因填入相同的位置。3 變異操作遺傳算法的變異操作是指將原來(lái)染色體的某位置的基因按照一定的轉(zhuǎn)換規(guī)律轉(zhuǎn)變成其它基因，進(jìn)而生成一個(gè)新的染色體。變異算子的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。變異操作能夠改善遺傳算法的局部搜索能力、維持群體的多樣性、防止出現(xiàn)早熟現(xiàn)象。（1）互換位置變異 即在個(gè)體中隨機(jī)交換兩個(gè)不同位置上的基因。例如，父代個(gè)體為p=345735891將位置7的基因進(jìn)行交換，得q=348735591（2）均勻變異 均勻變異操作是指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。均勻變異的具體操作過(guò)程是：1）依次指定個(gè)體編碼串產(chǎn)中的每個(gè)基因座為變異點(diǎn)。2）對(duì)每一個(gè)變異點(diǎn)，以某一變異概率從對(duì)應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)來(lái)替代原有基因值。（3）插入變異 即將個(gè)體中某一位置上的基因(或某一段位置上的基因串)插入到另一位置之前或之后。例如，父代個(gè)體為p=1356735891將位置7的基因插入到位置3后，得q=2656873591對(duì)于變異操作還有很多工作要做，這里提供的變異操作不止這些，任何能夠做到改變個(gè)體的鄰域操作都可認(rèn)為是變異操作。遺傳算法運(yùn)行參數(shù)的選取都是根據(jù)多次的實(shí)驗(yàn)得到的能夠達(dá)到最優(yōu)或次優(yōu)效果的參數(shù)，我們?cè)谠O(shè)計(jì)遺傳算法時(shí)，除了需要針對(duì)具體問(wèn)題選擇適當(dāng)?shù)木幋a方法及相應(yīng)的遺傳操作外，運(yùn)行參數(shù)的選擇對(duì)算法的性能也有較大的影響。遺傳算法中需要選擇的運(yùn)行參數(shù)主要有個(gè)體編碼串長(zhǎng)度L，群體大小P，交叉概率Pc，變異概率Pm，終止代數(shù)T等：①種群規(guī)模P: 參與進(jìn)化的染色體總數(shù)，建議20~100。②代溝G: 二代之間不相同的染色體數(shù)目，無(wú)重疊G=1；有重疊0G1。③終止代數(shù)T: 一般建議范圍為100~1000。④交換率: Pc一般為60~100%。⑤變異率: ~10%。第3章 Job Shop調(diào)度的遺傳算法操作模型解決一個(gè)實(shí)際問(wèn)題的遺傳算法通常包括以下四個(gè)步驟：（1）將一個(gè)求解問(wèn)題模型化為符合遺傳算法的結(jié)構(gòu)框架，即如何對(duì)染色體編碼來(lái)表示要解決的問(wèn)題；（2）定義遺傳操作算子，如交叉準(zhǔn)則和變異準(zhǔn)則等；（3）定義適應(yīng)度評(píng)價(jià)函數(shù)；（4）確定算法結(jié)束的條件以及算法運(yùn)行的初始參數(shù)，如進(jìn)化的最大代數(shù)和種群規(guī)模，復(fù)制、交叉、變異的概率等。同樣用遺傳算法求解JobShop調(diào)度問(wèn)題也需要解決這些問(wèn)題，下面將對(duì)這些問(wèn)題作詳細(xì)的討論。 Job shop調(diào)度問(wèn)題描述及數(shù)學(xué)模型Job shop是研究企業(yè)生產(chǎn)車間n個(gè)工件按照每個(gè)工件的加工次序，在m臺(tái)機(jī)床上加工的問(wèn)題。已知每個(gè)工件在各個(gè)機(jī)器上的加工次序和每個(gè)工價(jià)的各個(gè)工序的加工時(shí)間，要求確定與工藝約束條件相容的各機(jī)器上所有工件的加工開(kāi)始時(shí)刻、完成時(shí)刻、加工次序，使加工性能指標(biāo)達(dá)到最優(yōu)。生產(chǎn)調(diào)度過(guò)程要滿足以下約束：（1）在整個(gè)加工過(guò)程中，每個(gè)工件只能被所有的機(jī)器都加工并且只加工一次；（2）各個(gè)工件必須按工藝路線以指定的次序在機(jī)器上加工；（3）加工過(guò)程不能間斷；（4）每一時(shí)刻每一臺(tái)機(jī)器只能加工一個(gè)工件。為了便于理解，先作如下假定:（1）設(shè)J為工件的集合，J={i},i=1,……,n。這里n表示第n個(gè)工件，同時(shí)也表示工件總數(shù)為n個(gè)。（2）設(shè)M為機(jī)器的集合，M={k}，k=1,2，……，m。這里m表示第m臺(tái)機(jī)器，同時(shí)還表示機(jī)器總數(shù)為m臺(tái)。（3）設(shè)JOi為工件i包含的工序集合，JOi={j}，j=1,2，……，ni。這里ni表示工件i有ni道工序，且ni還表示是工件i的最后一道工序。（4）設(shè)V為所有工件的工序集合，v為任意工件的任意工序，記v=（i，j）。（5）設(shè)stij為工件i的第j道工序加工開(kāi)始時(shí)間。（6）etij為工件i的第j道工序加工結(jié)束時(shí)間。（7）ptij為工件i的第j道工序加工持續(xù)時(shí)間。（8）設(shè)Sk為所有在機(jī)器k上加工的加工工序的一種排序，記vk（l）為在Sk中第l位置上的加工工序，則Sk=（vk（l），……vk（l），vk（lk）），其中：vk（l）∈V；l=1，……，lk；k=1，…，m。（9）設(shè)Job shop調(diào)度問(wèn)題的解為s，則s=（s1，…，sk，…，sm），k=1，…,m。Job shop調(diào)度問(wèn)題通常以最小化最大完成時(shí)間（makespan）為目標(biāo)函數(shù)。以最小化最大完成時(shí)間為目標(biāo)函數(shù)是在可行解的解空間中，找出一個(gè)解，該解的所有工件的最大結(jié)束時(shí)間與其它所有可行解相比為最小，用數(shù)學(xué)表示為：C*=minCmax（s）=min(max(etoi))=min(max(stoi+ptoi)),i∈J (31)Job Shop調(diào)度問(wèn)題的求解就是要找到一個(gè)合理的安排使每個(gè)工件都能在滿足工藝約束的條件下在各臺(tái)機(jī)器上加工，使得總的加工時(shí)間最短。在上一小節(jié)已經(jīng)定義過(guò)，設(shè)etij為工件i的第j道工序加工結(jié)束時(shí)間，設(shè)ptij為工件i的第j道工序加工持續(xù)時(shí)間。如果機(jī)器h先于機(jī)器k加工工件i，則應(yīng)滿足如下約束： etikptiketih 如果機(jī)器k先于機(jī)器h加工公家i，則應(yīng)滿足如下約束： etihptihetik定義變量xtihk,則：xtihk=1，機(jī)器h先于機(jī)器k加工工件i0，否則則上述可表達(dá)為：etikptik+L(1－etihk)≥etihi=1,2,…,n。 h, k=1,2,…,m其中L為一足夠大的正數(shù)。對(duì)于在機(jī)器k上加工的工件i和j，如果工件i先于工件j在機(jī)器k上加工，則應(yīng)滿足如下約束：etjketikptjketiketjkptik定義變量ytijk，則：ytijk=1，機(jī)器i先于機(jī)器j在機(jī)器k上加工0，否則則上述約束可表述為：etjketik+L(1－ytijk)≥ptjki，j=1,2,…,n。 k=1,2,…,m因此一個(gè)n/m/G/ETmax Cmax（n表示工件數(shù)，m表示機(jī)器數(shù)，G表示Jobshop調(diào)度問(wèn)題，ETmax表示性能指標(biāo)為最大完成時(shí)間）的Jobshop調(diào)度問(wèn)題的數(shù)學(xué)模型可描述如下：F=min{max[max[etik ] ] } JobShop調(diào)度問(wèn)題的染色體編碼在用遺傳算法解決 JobShop問(wèn)題時(shí)，首先要考慮的就是遺傳編碼的設(shè)置，這也是基本遺傳算法的第一步，和它相對(duì)應(yīng)的是解碼。在編碼時(shí)，我們必須考慮“染色體”的合法性、可行性、有效性以及對(duì)解空間表征的完全性，如果不考慮以上的因素，那么編寫(xiě)出來(lái)的編碼在用遺傳算法解決時(shí)，會(huì)直接影響遺傳算法的效率，甚至不能產(chǎn)生最優(yōu)或次優(yōu)解。由于 JobShop是一類組合優(yōu)化問(wèn)題，而且在進(jìn)行遺傳操作的時(shí)候要考慮工藝約束性、染色體的Lamarkian特性、解碼的復(fù)雜性、編碼的空間特性和存儲(chǔ)量的需求是設(shè)計(jì)遺傳算法編碼通常要考慮的問(wèn)題。（1）染色體的Lamarkian特性此特性是指在進(jìn)行遺傳操作時(shí)一些具有較高適應(yīng)度值的染色體是否可以順利被遺傳的下一代形成新一代種群。下一代種群中的個(gè)體還能繼承父代種群中適應(yīng)度值高的優(yōu)點(diǎn)，這時(shí)稱染色體編碼具有Lamarkian特性。而下一代種群中的個(gè)體只繼承部分父代種群的片段，則稱所采用的編碼具有半Lamarkian特性。（2）解碼的復(fù)雜性遺傳算法在通過(guò)編碼、遺傳操作后產(chǎn)生最終的優(yōu)秀個(gè)體，這些個(gè)體需要我們把它轉(zhuǎn)化成與生產(chǎn)車間相對(duì)應(yīng)的生產(chǎn)調(diào)度。我們希望GA搜索用的編碼能夠解碼成生產(chǎn)調(diào)度，如果最終的染色體編碼不需要解碼就能生成與生產(chǎn)調(diào)度一一對(duì)應(yīng)的操作，稱0類復(fù)雜性解碼。最終的染色體編碼要通過(guò)簡(jiǎn)單映射關(guān)系才能生成車間的生產(chǎn)調(diào)度叫1類復(fù)雜性解碼；最終的染色體編碼要通過(guò)簡(jiǎn)單啟發(fā)式方法才能生成車間的調(diào)度叫2類復(fù)雜性；只能復(fù)雜啟發(fā)式方法才能生成車間的生產(chǎn)調(diào)度解碼叫3類復(fù)雜性解碼。（3）編碼的空間特性對(duì)于車間調(diào)度問(wèn)題，編碼的設(shè)計(jì)還要考慮是否能夠表征n工件在m臺(tái)機(jī)器上加工的約束性即編碼是否可行、是否有冗余。（4）存儲(chǔ)量需求對(duì)于車間調(diào)度問(wèn)題，存儲(chǔ)量需求是指編碼的長(zhǎng)度=工件數(shù)x機(jī)器數(shù)，這叫標(biāo)準(zhǔn)碼長(zhǎng)，但在編碼設(shè)計(jì)時(shí)有時(shí)為了操作和解碼方便，可以設(shè)計(jì)編碼長(zhǎng)度超過(guò)這個(gè)標(biāo)準(zhǔn)長(zhǎng)度或低于標(biāo)準(zhǔn)長(zhǎng)度的編碼。車間生產(chǎn)調(diào)度的編碼設(shè)計(jì)分為直接編碼和間接編碼。直接編碼將調(diào)度作為狀態(tài)，一般包括基于工件對(duì)關(guān)系、工件、操作、完成時(shí)間、隨機(jī)鍵編碼等。間接編碼將一組工件的分配處理規(guī)則作為狀態(tài)，結(jié)果是一組最佳的分配規(guī)則序列構(gòu)造的調(diào)度。一般包括基于優(yōu)先權(quán)規(guī)則、機(jī)器