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

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

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

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

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