基于鏈結(jié)學(xué)習(xí)的子群體進(jìn)化算法求解多目標(biāo)調(diào)度問題.pdf

1、多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem，MOP)的本質(zhì)是在某種約束條件下實現(xiàn)多個目標(biāo)函數(shù)的均衡，多目標(biāo)置換流水車間調(diào)度問題(Permutation Flow Shop Scheduling Problem，PFSP)是其應(yīng)用之一，因PFSP自身復(fù)雜程度高、不同目標(biāo)之間的沖突、多目標(biāo)測試數(shù)據(jù)不統(tǒng)一等使求解算法極具挑戰(zhàn)性。
　　本文基于子群體進(jìn)化算法(Sub-population Ev

2、olutionary Algorithm，SPEA)、分群、切比雪夫權(quán)重分割法(Chebyshev’s Partition Method)和鏈接學(xué)習(xí)技術(shù)(Linkage Learning technique， LLT)等提出基于鏈接學(xué)習(xí)的子群體進(jìn)化算法(Sub-population Evolutionary Algorithm based on Linkage Learning， SEABLL)，以求解多目標(biāo)置換流水車間調(diào)度問題，經(jīng)總結(jié)

3、做出以下改善工作：
　　（1）考慮子群體再接空間的分布，透過H劃分群體盡可能實現(xiàn)解空間上的均勻分布，利用切比雪夫方法調(diào)控權(quán)重，從而能夠找到更好的解。
　?。?）在子群體進(jìn)化算法中，利用以概率為核心的二元變量概率模型進(jìn)行區(qū)塊挖掘和區(qū)塊競爭，構(gòu)建區(qū)塊后暫存數(shù)據(jù)庫供LLT組合人造解(artificial chromosome，AC)并注入演化過程，提高解的質(zhì)量，交叉方法同時進(jìn)行，利用子群體篩選后的非支配解與優(yōu)質(zhì)支配解進(jìn)行交叉，非支

4、配解進(jìn)行變異，并設(shè)置一定數(shù)量的進(jìn)行交叉與變異以便找更廣泛的解以供篩選。
　　為比較算法的性能，在Taillard標(biāo)準(zhǔn)例題測試，首先對比切比雪夫和線性權(quán)重所求的有效解的數(shù)量(number of efficient solutions，NES)和與參考集(reference set，RS)的平均距離(average distance, Dav)，證明切比雪夫的優(yōu)越性。其次，為證明雙變量概率模型的有效性，設(shè)置代數(shù)100和200及其與子群

5、體遺傳算法Ⅱ(sub-population genetic algorithmⅡ，SPGAⅡ)在例題ta010、ta020、ta050、ta060、ta080上的解的分布的對比，證明所提SEABLL分布較好。最后在ta001-ta092上39個標(biāo)準(zhǔn)測試?yán)}中比較SEABLL與SPGAⅡ兩種算法所求非支配解數(shù)量(number of non-dominated solutions，NNDS)、證明92％的例題優(yōu)于SPGAⅡ，且規(guī)模較大的優(yōu)勢