自適應(yīng)差分進(jìn)化算法解決多目標(biāo)有限緩沖車間調(diào)度問(wèn)題研究.pdf

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

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

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

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

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

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