基于NNIA的多目標(biāo)時間表調(diào)度問題研究.pdf

1、多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem, MOP)在今年來得到了學(xué)者的廣泛關(guān)注。然而采用進(jìn)化算法處理多目標(biāo)優(yōu)化問題也是進(jìn)化計算領(lǐng)域的一個研究熱點(diǎn)。調(diào)度問題自上世紀(jì)中后期便得到了大量學(xué)者的重視,其中考試時間表調(diào)度問題是指把一系列有沖突的考試安排到有限的時間段(有最大時間段限制)和教室(有座位容量限制)中,盡可能多的滿足軟約束條件。考試時間表調(diào)度問題的難度就在于有大量的約束限制,本文以人工免

2、疫多目標(biāo)優(yōu)化模型為基準(zhǔn),針對加快算法收斂速度和高效的多樣性保持策略進(jìn)行了深入的研究。以基于人工免疫系統(tǒng)的多目標(biāo)優(yōu)化算法,即非支配鄰域免疫算法(Nondominated Neighbor Immune Algorithm, NNIA)為基礎(chǔ),提出改進(jìn)的免疫多目標(biāo)優(yōu)化算法并將其成功應(yīng)用于考試時間表調(diào)度問題。本文的主要工作包括:
　　(1)在考試時間表調(diào)度問題中,當(dāng)時間段比較大的時候,時間表內(nèi)的考試之間的相互平均沖突數(shù)就會變小,相反,當(dāng)

3、時間段比較小的時候,時間表內(nèi)的考試之間的相互平均沖突數(shù)就會比較大。所以,這符合多目標(biāo)優(yōu)化算法的目標(biāo)沖突性的前提條件。本文針對無座位容量限制的考試時間表調(diào)度問題依據(jù)非支配鄰域免疫算法框架來進(jìn)行解決。算法的初始化采用超啟發(fā)式初始化進(jìn)行,用到的啟發(fā)式信息有LD,LWD,以及SD。接著是交叉變異,非支配排序以及克隆策略。
　　(2)由于非支配解的個數(shù)也就是解集的多樣性直接影響到多目標(biāo)進(jìn)化算法的好壞,包括還有達(dá)到最優(yōu)解的速度也是考慮的問題之

4、一。為此,本文提出改進(jìn)的NNIA來解決多目標(biāo)時間表調(diào)度問題,主要提出兩個策略分別是局部搜索策略以及多樣性保持策略。多樣性保持策略主要是為了解決在局部搜索中出現(xiàn)個體被支配掉的情況。本文中的局部搜索策略主要是依次在兩個方向即人均沖突數(shù)和時間段數(shù)來進(jìn)行優(yōu)化。
　　(3)最后針對提出的算法,我們采用多倫多數(shù)據(jù)集進(jìn)行測試,選了其中的八組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析。第一大部分實(shí)驗(yàn)主要為了說明,我們采用NNIA框架來研究多目標(biāo)時間問題是合理的。第二大部