基于自然計算求解作業(yè)車間調度問題.pdf

1、作業(yè)車間調度問題(JSSP)是一個典型的NP-難問題，也是迄今為止所有組合優(yōu)化問題中最難問題之一，同時在工程應用中有著十分重要的意義，因此得到了廣泛的關注。本文在對JSSP進行透徹分析的基礎上，結合已有研究成果，借鑒自然計算的方法，對JSSP求解進行研究。主要工作概括如下：
　　 (1)以多種群遺傳算法(MGA)為基礎，本文提出了基于記憶庫和拉馬克進化機制求解JSSP。該算法針對多種群遺傳算法容易陷入局部最優(yōu)解和局部搜索能力差的

2、缺點，通過引入記憶庫策略，不但使子種群間的個體可以進行信息交換，而且有利于保持整個種群的多樣性；通過構造基于拉馬克進化機制的局部搜索算子來提高多種群遺傳算法中子種群的局部搜索能力。并且由于本文算法采用了全局尋優(yōu)能力較強的模擬退火(SA)算法對記憶庫中的個體進行優(yōu)化，從而緩解了多種群遺傳算法易陷入局部最優(yōu)解的問題，并提高了本文算法求解作業(yè)車間調度問題的性能。
　　 (2)應用克隆選擇(CS)算法求解JSSP時，如果初始種群的分布不

3、夠理想，其收斂速度比較慢，通過G&T算法可以產(chǎn)生較好的初始解，加快收斂速度；CS算法的主要算子是變異算子，因此如何選擇合適的變異算子會對算法的性能有較大的影響。本文利用三種變異算子(交換，倒置，插入)對種群進行優(yōu)化，同時記錄各個變異算子的貢獻，在克隆變異的過程中，通過輪盤賭方法動態(tài)的選擇合適的變異算子。此外，克隆個體的變異強度應該與個體的適應度成反比，即適應度大的個體，應有較小的變異強度；適應度小的個體，應有較大的變異強度，基于這個原因

4、，本文設計了自適應的變異強度算子。
　　 (3)差分進化(DE)算法采用浮點編碼，成功的應用在求解連續(xù)空間上的全局優(yōu)化問題。針對離散空間上的作業(yè)車間調度問題，本文設計了離散差分進化(DDE)算法。該算法采用DE算法的框架，繼承了DE算法的優(yōu)點。通過與克隆選擇和遺傳算法在benchmark標準測試問題上進行仿真對比實驗，結果表明了離散差分進化算法快速收斂的特性。
　　 (4)克隆選擇算法將局部搜索和全局搜索有機的結合起來，

5、使算法具有較好的種群多樣性，但對于作業(yè)車間調度問題，CS的收斂速度比較慢；離散差分進化算法采用差分進化算法的框架，具有快速收斂的優(yōu)點，但相比克隆選擇算法，差分進化算法的種群多樣性較差，容易快速收斂到局部最優(yōu)。本文充分利用CS和DDE算法的優(yōu)點，將兩種算法結合在一起，有效的彌補了各自的不足。通過在benchmark標準測試數(shù)據(jù)上的驗證，證實了算法的有效性。
　　 本文得到了國家教育部博士點基金(No.20060701007)和國家