用基于共生遺傳算法的學(xué)習(xí)框架求解柔性作業(yè)調(diào)度問題.pdf

1、車間作業(yè)調(diào)度問題(JSP)是許多實(shí)際問題的簡化模型。尋找求解JSP問題的有效途徑是調(diào)度和優(yōu)化領(lǐng)域的重要課題。但是車間作業(yè)調(diào)度問題是NP難解問題，尋找具有多項(xiàng)式復(fù)雜度的算法幾乎是不可能的。遺傳算法是一種全局隨機(jī)搜索算法，已經(jīng)廣泛的用于求解JSP問題。它把JSP問題的可行解通過編碼從問題的解空間轉(zhuǎn)化到遺傳算法能夠處理的搜索空間。GA的遺傳算子操作能夠通過交叉或變異父個(gè)體生成新個(gè)體的方式來從解空間中搜尋最優(yōu)解。 GA通過交換父個(gè)體中的

2、基因片段或改變某些基因來進(jìn)化進(jìn)而完成搜索。如果在進(jìn)化過程中，我們能夠盡可能的保留父個(gè)體中具有較高適應(yīng)度的優(yōu)秀基因片段，并將其遺傳到下一代中，那么GA可以在最有希望的解空間中搜索，進(jìn)而可以提高搜索效率。 本文中，我們通過用遺傳算法對(duì)一個(gè)JSP實(shí)例多次求解，得到大量最優(yōu)染色體編碼串。經(jīng)過認(rèn)真分析，總結(jié)出代表問題特性的一些概念屬性，并給出一個(gè)新的概念分級(jí)方法。基于這些屬性及分類方法，應(yīng)用數(shù)據(jù)挖掘算法從這些最優(yōu)染色體編碼串中學(xué)習(xí)知識(shí)，得

3、到多組調(diào)度規(guī)則，仿真表明，這些調(diào)度規(guī)則可以有效的調(diào)度作業(yè)。調(diào)度規(guī)則也代表了這些最優(yōu)染色體共有的特征。如果進(jìn)化過程中在這些特征剛剛出現(xiàn)的時(shí)候，我們能夠識(shí)別出來并將其遺傳到后代個(gè)體中，顯然可以改善后代種群的質(zhì)量，進(jìn)而可以提高搜索效率。 在最后部分，借鑒上述思想求解具有操作柔性的車間調(diào)度問題。根據(jù)問題的特點(diǎn)，我們使用共生機(jī)制改進(jìn)了遺傳算法并將其集成到一個(gè)學(xué)習(xí)框架中。提出了相應(yīng)的編碼解碼方法和一組自適應(yīng)概率函數(shù)并改進(jìn)了學(xué)習(xí)框架，使其在進(jìn)