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

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

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

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

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

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