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

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

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

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