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