自適應差分進化算法解決多目標有限緩沖車間調(diào)度問題研究.pdf

1、流水車間調(diào)度問題(flow shop scheduling problem，F(xiàn)SSP)是優(yōu)化組合問題的一個重要分支，對該問題的研究有利于實現(xiàn)有限資源的優(yōu)化配置和合理利用。但因該問題為NP-hard(non-deterministic polynomial-hard)，人工智能算法如今正逐漸代替數(shù)學方法，并取得了一定的成果。FSSP有多種類型，而帶有限緩沖的FSSP(FSSP with limited buffers，F(xiàn)SSPWLB)因更

2、接近實際生產(chǎn)狀況而受到廣泛重視，對緩沖大小的探討在實際生產(chǎn)應用中也具有重要的經(jīng)濟價值。此外，求解多目標FSSP，可幫助決策者制定折中策略，在滿足客戶需求的前提下實現(xiàn)經(jīng)濟最大化等其他生產(chǎn)指標。因此研究多目標帶有限緩沖的FSSP就顯得尤為重要。
　　差分進化(differential evolution，DE)算法因其良好的特性而大量運用于連續(xù)問題優(yōu)化中。該算法的參數(shù)對所優(yōu)化的問題具有敏感性，通常要根據(jù)反復實驗的結(jié)果或經(jīng)驗來設(shè)置，因此

3、造成計算資源的額外開銷，同時受到先驗經(jīng)驗的制約。于是對自適應差分進化算法的研究不斷涌現(xiàn)，其應用領(lǐng)域也不斷拓寬。在使用DE對FSSPWLB進行優(yōu)化時，因其測試實例規(guī)模不同，更需要自適應機制的參與。
　　綜上所述，本文提出了一種自適應差分進化算法及其若干變體，來解決多目標FSSPWLB。目前看來，使用自適應差分進化算法優(yōu)化多目標FSSPWLB尚屬首例。
　　首先，本文使用最大順序值(largest order value，LOV

4、)規(guī)則完成DE個體與工件排序的映射，為設(shè)計合理的自適應機制，分析了DE個體、工件排序以及目標值差異之間的關(guān)系，研究參數(shù)F和CR對目標值的影響。在此基礎(chǔ)上提出了一種參數(shù)CR的自適應差分進化算法，以適應對算法不同的搜索需求。同時為保證初始種群的質(zhì)量，使用啟發(fā)式算法構(gòu)造了兩個特殊個體。
　　其次，為加強算法局部搜索性能，除選擇插入算子(Insert)外，還設(shè)計了一種基于概率模型的局部搜索算子(local search based on

5、probability model，LSbPM)，目的在于挖掘非支配解集中的優(yōu)質(zhì)子序列信息，并加以利用。引入次解保留概念，將其嵌入Insert中，保留多次插入過程中產(chǎn)生的次解，充分運用搜索結(jié)果，在一定程度上補償隨即拋棄被支配解而造成的計算浪費。
　　接著，為驗證本文所提出算法的各項性能的優(yōu)劣，設(shè)計了其他兩種變體，分別去除了LSbPM算子和次解保留機制，三種算法分別記為MPADE1、MPADE2和MPADE3，且與HDE做對比。選取

6、三種不同基準集中的12個實例，以多項評價指標為參考，通過實驗對比三種算法與 HDE。實驗表明，次解保留機制在算法中發(fā)揮了重要作用，使得MPADE1和MPADE3在性能上超越MPADE2和HDE。而 LSbPM的效果并不理想，只有在評價次數(shù)較大時才能起到改善作用。整體來說，MPADE3是最好的算法，能夠獲得更多的非支配解，保證其質(zhì)量，在分布性上也比其他算法好。
　　最后，MPADE3用以研究與HDE收斂特性的差別，并分析不同緩沖區(qū)容