【文章內(nèi)容簡(jiǎn)介】 圖像處理等多個(gè)領(lǐng)域得到廣泛應(yīng)用，被認(rèn)為是21世紀(jì)有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。調(diào)度問(wèn)題屬于NPplete問(wèn)題，很難建立準(zhǔn)確的數(shù)值模型，由于調(diào)度規(guī)則是基于經(jīng)驗(yàn)，故沒(méi)有普遍適用的規(guī)則存在，某一規(guī)則只能運(yùn)用于一定的場(chǎng)合，應(yīng)用調(diào)度規(guī)則求得的解也只是問(wèn)題的近優(yōu)解，很難保證其解的有效性。經(jīng)過(guò)幾十年的發(fā)展，遺傳算法已經(jīng)在數(shù)據(jù)挖掘、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、圖象處理等領(lǐng)域得到成功的應(yīng)用，并顯示出其良好的性能，特別是在求解復(fù)雜優(yōu)化問(wèn)題上的巨大潛力，使得幾乎所有領(lǐng)域的研究人員都嘗試過(guò)遺傳算法在各自專業(yè)領(lǐng)域的應(yīng)用，如:人工生命、神經(jīng)網(wǎng)絡(luò)、組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、系統(tǒng)辨識(shí)等等。調(diào)度問(wèn)題的多目標(biāo)優(yōu)化問(wèn)題的，還有很多設(shè)計(jì)、工藝等方面的約束必須考慮，從而使多數(shù)的優(yōu)化方法在此問(wèn)題前失效，然而遺傳算法由于其自然數(shù)序號(hào)的編碼方式串與調(diào)度方案的表現(xiàn)形式不謀而合，都是數(shù)字串，盡管還不完整，但也較容易地就解決了調(diào)度問(wèn)題解空間與染色體編碼串空間的映射問(wèn)題，另外，遺傳算法的特點(diǎn)也使它很適合于解算各種制造系統(tǒng)的調(diào)度問(wèn)題。遺傳算法作為一種快捷、簡(jiǎn)便、容錯(cuò)性強(qiáng)的算法，在各類結(jié)構(gòu)對(duì)象的優(yōu)化過(guò)程中顯示出明顯的優(yōu)勢(shì)。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點(diǎn):(1)搜索過(guò)程不直接作用在變量上，而是在參數(shù)集進(jìn)行了編碼的個(gè)體。(2)搜索過(guò)程是從一組解迭代到另一組解，采用同時(shí)處理群體中多個(gè)個(gè)體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并行化。這使的遺傳算法能以較少的計(jì)算獲得較大的收益。(3)遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的，從而增加了其搜索過(guò)程的靈活性。采用概率的變遷規(guī)則來(lái)指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。(4)對(duì)搜索空間沒(méi)有任何特殊要求(如連通性、凸性等)，只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其他輔助信息，適應(yīng)范圍更廣。 遺傳算法的自組織、自適應(yīng)和自學(xué)習(xí)性(智能性)決定遺傳算法可求解復(fù)雜問(wèn)題。(5)黑箱式結(jié)構(gòu)。應(yīng)用遺傳算法時(shí)，根據(jù)具體問(wèn)題的特性，進(jìn)行編碼與適應(yīng)度設(shè)計(jì)之后，其余操作按常規(guī)算子自動(dòng)運(yùn)行即可，只等最后輸出最優(yōu)解個(gè)體，而不必關(guān)心求解的實(shí)際過(guò)程，所以遺傳算法非常便于處理那些輸入輸出之間因果關(guān)系復(fù)雜的問(wèn)題?；谶z傳算法以上的特點(diǎn)，本文選用遺傳算法作為求解優(yōu)化問(wèn)題的有效方法。 遺傳算法簡(jiǎn)介 遺傳算法概述遺傳算法是基于自然選擇，在計(jì)算機(jī)上模擬生物進(jìn)化機(jī)制的尋優(yōu)搜索算法。由于遺傳算法是自然遺傳學(xué)與計(jì)算機(jī)科學(xué)相互結(jié)合滲透的產(chǎn)物，因此在遺傳算法中借用了許多自然進(jìn)化的概念。這些概念如下所示：1. 串（String）：串是個(gè)體（Individual）的形式，在算法中為字符串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體（Chromosome）。2. 群體（Population）：一定數(shù)量的個(gè)體組成了群體，或叫種群。串是群體中的元素。3. 群體規(guī)模（Population Size）：群體中個(gè)體的數(shù)目成為群體個(gè)數(shù)，也稱為群體規(guī)?；蛉后w大小。4. 基因（Gene）：基因是串中的元素，基因用于表示個(gè)體的特征。例如，有一個(gè)串 S = 1001，則其中的元素 1，0，0，1 分別稱為基因。它們的值稱為等位基因（Alleles）。5. 串結(jié)構(gòu)空間 SS：在串中，基因任意組合所構(gòu)成的串的集合?；虿僮魇窃诖Y(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對(duì)應(yīng)于遺傳學(xué)中的基因型（Genotype）的集合。6. 參數(shù)空間 SP：這是串空間在物理系統(tǒng)中的映射，它對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型（Phenotype）的集合。7. 適應(yīng)度（Fitness）函數(shù)：適應(yīng)度表示某個(gè)體對(duì)于環(huán)境的適應(yīng)程度。對(duì)于優(yōu)化問(wèn)題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，遺傳算法對(duì)于適應(yīng)度函數(shù)并不要求可導(dǎo)等條件，只要求適應(yīng)度函數(shù)為可加以比較的非負(fù)函數(shù)。8. 編碼、解碼操作：遺傳算法必須包含兩個(gè)必需的數(shù)據(jù)轉(zhuǎn)換操作，即把搜索空間中的參數(shù)或解轉(zhuǎn)換成遺傳空間中的染色體或個(gè)體，稱為編碼操作，反之，稱為譯碼操作。9. 選擇(Selection) ：以一定的概率從種群中選擇若干個(gè)體的操作。(crossover) ：有性生殖生物在繁殖下一代時(shí)兩個(gè)同源染色體之間通過(guò)交叉而重組，即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。在遺傳算法中為通過(guò)交配原則產(chǎn)生一組新解的過(guò)程。(Mutation)：在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生新的染色體，這些新的染色體表現(xiàn)出新的性狀。 遺傳算法基本過(guò)程遺傳進(jìn)化開(kāi)始于隨機(jī)選擇遺傳種群，然后通過(guò)應(yīng)用遺傳算子，即繁殖算子，交叉算子和變異算子朝著優(yōu)化的方向進(jìn)化。下面對(duì)關(guān)鍵參數(shù)與操作的設(shè)計(jì)做簡(jiǎn)單介紹。①編碼將問(wèn)題的潛在解用一些參數(shù)表示，這些參數(shù)(基因)排列在一起形成一個(gè)特定的編碼(染色體)，代表一個(gè)個(gè)體，從而將問(wèn)題的狀態(tài)空間與遺傳算法的碼空間相對(duì)應(yīng)，這很大程度上依賴于問(wèn)題的性質(zhì)，并將影響遺傳操作的設(shè)計(jì)。針對(duì)優(yōu)化問(wèn)題的編碼技術(shù)主要有二進(jìn)制編碼、十進(jìn)制編碼、實(shí)數(shù)編碼等。二進(jìn)制編碼將問(wèn)題的解用一個(gè)二進(jìn)制0和1字符串來(lái)表示，十進(jìn)制編碼將問(wèn)題的解用一個(gè)十進(jìn)制串來(lái)表示。實(shí)數(shù)編碼將問(wèn)題的解用一個(gè)實(shí)數(shù)來(lái)表示。實(shí)數(shù)編碼解決了二進(jìn)制和十進(jìn)制編碼對(duì)算法精度和存儲(chǔ)量的影響，同時(shí)便于優(yōu)化中引入問(wèn)題的相關(guān)信息，譬如梯度信息。實(shí)數(shù)編碼直接在解的表現(xiàn)型上進(jìn)行遺傳操作，目前在高維復(fù)雜優(yōu)化問(wèn)題中得到廣泛應(yīng)用，并取得了較好效果。鑒于組合優(yōu)化問(wèn)題本身的性質(zhì)，其編碼方式需要特殊設(shè)計(jì)。②適值函數(shù)即個(gè)體空間S到正實(shí)數(shù)空間的映射，適值函數(shù)f為 f:S→R+遺傳算法在搜索進(jìn)化過(guò)程中一般不需要其它外部信息，僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。根據(jù)求解問(wèn)題特性來(lái)定義反應(yīng)個(gè)體對(duì)問(wèn)題環(huán)境適應(yīng)能力和優(yōu)劣程度的測(cè)定函數(shù)。③選擇選擇即是在一個(gè)種群中選擇一個(gè)個(gè)體，它是隨機(jī)映射Ts:SN→S選擇操作的目的是為了避免當(dāng)前群體中有效基因的損失，使高性能的個(gè)體得以更大的概率生存，從而提高全局收斂性和計(jì)算效率。選擇操作按照個(gè)體的適值進(jìn)行，適值高的個(gè)體擁有更多的被選中機(jī)會(huì)，因而有更大的存活概率，并將其優(yōu)良特性傳遞給后代。通常有以下的算法可供選擇:輪盤(pán)賭選擇(roulette wheel selection)記種群規(guī)模為n，個(gè)體Vi的適值為(fvi)，則個(gè)體Vi被選擇的概率為然后，根據(jù)這些概率構(gòu)造一個(gè)轉(zhuǎn)輪，旋轉(zhuǎn)轉(zhuǎn)輪n次，每次選一個(gè)染色體加入新的種群。隨機(jī)遍歷抽樣((stoehastic universal sampling)。局部選擇(local selection)。截?cái)噙x擇(truncation selection)。錦標(biāo)賽選擇(tournament selection)。④交叉交叉算子是母體空間到個(gè)體空間的映射，記作Tc:S2→S交叉是最主要的遺傳運(yùn)算，它同時(shí)對(duì)兩個(gè)染色體操作，交叉操作用于結(jié)合來(lái)自父染色體和母染色體的特征來(lái)產(chǎn)生新的子個(gè)體，在解空間中進(jìn)行有效搜索，同時(shí)降低對(duì)有效模式的破壞概率。點(diǎn)式交叉算子分為單點(diǎn)交叉和多點(diǎn)交叉。單點(diǎn)交叉即首先在雙親的染色體上隨機(jī)地選一個(gè)交叉位置，將交換位置的右段互相交換，從而形成兩個(gè)新的后代。實(shí)數(shù)編碼遺傳算法的交叉操作類似于二進(jìn)制編碼遺傳算法。以下以離散交叉為例介紹實(shí)數(shù)編碼的交叉方式。為了便于解釋，下面設(shè)解向量s1= (v1（1），v2(1)，…，vm（1）)和s1=( v1（2），v2（2），…，vm（2）)是兩個(gè)父解向量，sz={ s1 s2，…sm }和sw=( s1 ，s2，…sn)是通過(guò)雜交獲得的兩個(gè)后代。與二進(jìn)制編碼單點(diǎn)交叉不同在于交換的對(duì)象的差異，前者是二進(jìn)制串，后者是實(shí)空間的向量。如若選擇交換第k個(gè)分量以后的所有分量，則兩個(gè)后代為sz =( v1（1），v2(1)，…，vk（1），vk+1（2），…vm（2）)sw =( v1（2），v2(2)，…，vk（2），vk+1（1），…vm（1）)組合優(yōu)化中的置換編碼遺傳算法通常采用部分映射交叉、次序交叉、循環(huán)交叉、基于位置的交叉，群交叉等操作。⑤變異變異是一種基本運(yùn)算，它在染色體上自發(fā)地產(chǎn)生隨機(jī)的變化。一種簡(jiǎn)單的變異方法是替換一個(gè)或多個(gè)基因。在遺傳算法中，變異可以提供初始種群中不含有的基因，或找回選擇過(guò)程中丟失的基因，為種群提供新的內(nèi)容。Vl=[l0010011]在給定點(diǎn)變異后變?yōu)?V1*=[10011011]在遺傳操作中需注意的幾點(diǎn)問(wèn)題:1. 參數(shù)及其選取種群規(guī)模記為Pop_Size，即種群中個(gè)體(染色體)的個(gè)數(shù)。種群規(guī)模選擇較大時(shí)，可以同時(shí)處理更多的解，因而容易找到全局最優(yōu)解，其缺點(diǎn)是增加了每次迭代所需要的時(shí)間。迭代代數(shù)，即算法進(jìn)化代數(shù)，代數(shù)的大小直接關(guān)系到解的質(zhì)量和計(jì)算速度。叉率(記為Pc)定義為各代中交叉產(chǎn)生的后代數(shù)與種群中的個(gè)體數(shù)(Pop_Size)的比。較高的交叉率可達(dá)到更大的解空間，但會(huì)因搜索不必要的解空間而耗費(fèi)大量的計(jì)算時(shí)間，從而降低停在非最優(yōu)解上的機(jī)會(huì)。 變異率(記為Pm)定義為種群中變異基因數(shù)中的百分比。變異率控制了新基因?qū)敕N群的比例。若變異率太低，一些有用的基因就不能進(jìn)入選擇，若太高，既隨機(jī)的變化太多，那么后代就可能失去雙親繼承下來(lái)的好特性，這樣算法就會(huì)失去從過(guò)去的搜索中學(xué)習(xí)的能力。2. 終止規(guī)則遺傳算法的終止準(zhǔn)則通常有三種，一種是將某一個(gè)固定的最大代數(shù)作為停止算法的標(biāo)準(zhǔn)。另一種是把算法的運(yùn)行時(shí)間作為停止準(zhǔn)則。第三種準(zhǔn)則有一定的自適應(yīng)性，例如根據(jù)算法的評(píng)價(jià)的一些規(guī)則。當(dāng)由此監(jiān)控得到算法再進(jìn)化己無(wú)法改進(jìn)解的性能，此時(shí)停止計(jì)算。 遺傳算法執(zhí)行策略遺傳算法在執(zhí)行策略方面的下面幾方面工作值得注意:模擬退火（Simulated Annealing)是一種基于熱力學(xué)理論的優(yōu)化方法，并有著完善的全局收斂理論。在遺傳算法中以各種形式融入模擬退火思想，從而使得遺傳算法在理論上具有全局收斂性，是一個(gè)有意義的研究方向。把遺傳算法與局部搜索方法有機(jī)結(jié)合起來(lái)，是改進(jìn)遺傳算法性能的一個(gè)卓有成效的方法。這種混合型遺傳算法不但模擬了生物種群的學(xué)習(xí)過(guò)程，而且事實(shí)上還模擬了種群的個(gè)體在其生命周期內(nèi)具有學(xué)習(xí)行為這一生物現(xiàn)象。這在生物學(xué)中被稱為為L(zhǎng)amarckian evolution和Baldwin effect。(Parallel Genetic Algorithm)并行遺傳算法是在遺傳算法的實(shí)施中加入自然生物種群中的空間結(jié)構(gòu)因素，它的目的是可以在大規(guī)模并行機(jī)上運(yùn)行，即使是序列式實(shí)施并行遺傳算法，也可克服經(jīng)典遺傳算法性能上的不足，從而提高算法的效率。并行遺傳算法大致分為兩種，一種是島模型(Island Model)，稱為粗粒并行遺傳算法(Coarse Grained PGA)。島模型的實(shí)施方法是在幾個(gè)獨(dú)立按經(jīng)典遺傳算法方式運(yùn)行的種群(稱為子種群)中加入遷移(Migration) )因素。而細(xì)胞模型的實(shí)施則是在一個(gè)單一種群中，通過(guò)對(duì)經(jīng)典整體性選擇與雜交機(jī)制的局部化來(lái)達(dá)到并行化目的。島模型考慮的是種群的空間結(jié)構(gòu)，而細(xì)胞模型考慮的是一種群中個(gè)體的空間結(jié)構(gòu)。(Messy Genetic Algorithm)混亂遺傳算法是由Goldberg提出的，它的目的是解決經(jīng)典遺傳算法中所謂的連接問(wèn)題，即經(jīng)典遺傳算法很容易破壞定義位置較遠(yuǎn)的模式問(wèn)題。在混亂遺傳算法中，個(gè)體由其每個(gè)分量的位置與取值共同表示，位置可以不按次序排列，也并不是所有分量都在個(gè)體的表示中出現(xiàn)。事實(shí)上，混亂遺傳算法直接操作的對(duì)象既有個(gè)體，也有空間結(jié)構(gòu)，這自然使它喪失了只操作個(gè)體的經(jīng)典遺傳算法所具有的隱含并行性。混亂遺傳算法的理論基礎(chǔ)、算法設(shè)計(jì)及實(shí)驗(yàn)比較，均是有待探討的課題。4 車間作業(yè)調(diào)度的建模 車間作業(yè)調(diào)度問(wèn)題描述不失一般性，設(shè)n個(gè)作業(yè)m 臺(tái)機(jī)器的車間作業(yè)調(diào)度問(wèn)題（表示為：n/m JSP）滿足以下約束條件：（1）每個(gè)工件包含若干道工序；（2）各工件必須按工藝路線以指定的次序在機(jī)器上加工；（3）任何一個(gè)工件的前一道工序加工完成后，方能進(jìn)行后一道工序的加工，在同一臺(tái)機(jī)器上一個(gè)加工任務(wù)完成之后，方能開(kāi)始另一個(gè)加工任務(wù)。(4）每道工序從開(kāi)始到結(jié)束，不會(huì)被另外的工序所中斷。(5) 不考慮工件加工的優(yōu)先權(quán)，不考慮加工準(zhǔn)備時(shí)間。(6) 一個(gè)工件同一時(shí)間只能在一臺(tái)機(jī)器上加工，一臺(tái)機(jī)器同一時(shí)間只能加工一個(gè)工件，加工的開(kāi)始時(shí)間為O。則n/m JSP 問(wèn)題可描述如下：（1）設(shè)m個(gè)工件的集合為G，G={Gi︱i=（1，2，……，n）}；（2）設(shè)p臺(tái)機(jī)器的集合為J，J= {Ji︱i=（1，2，……，p）}；（3）工序（i，j）表示工件Gi的第j道工序，工序（i，j 1）稱為工序（i，j）的前道工序，工序（i，j +1）稱為工序（i，j）的后繼工序，ki表示工件Gi的總工序數(shù)，記k=max（k1，k2，……，km）；（4）矩陣Q=（gij）nxk為執(zhí)行工序的機(jī)器序號(hào)陣，gi表示執(zhí)行工序（i，j）的機(jī)器序號(hào)，當(dāng)jki時(shí)，gi =0；（5）矩陣W=（wij）nxk為工序的工時(shí)陣，wij表示執(zhí)行工序（i，j）的耗時(shí)，當(dāng)jki時(shí)，wi 0，一個(gè)矩陣對(duì)（Q，W）就可以完全描述一個(gè)車間