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