面向考試時(shí)間表問(wèn)題的啟發(fā)式進(jìn)化算法研究.pdf

1、時(shí)間表優(yōu)化問(wèn)題作為調(diào)度領(lǐng)域的研究熱點(diǎn)問(wèn)題，涉及范圍大到軍事國(guó)防，小到醫(yī)院學(xué)校的時(shí)間安排，在現(xiàn)實(shí)世界中的應(yīng)用領(lǐng)域十分廣泛。開展時(shí)間表優(yōu)化問(wèn)題的高效進(jìn)化算法研究對(duì)國(guó)家、社會(huì)和個(gè)人都具有重大的意義。本論文以考試時(shí)間表問(wèn)題作為研究背景，分析現(xiàn)有解決該問(wèn)題的進(jìn)化算法所面臨的主要問(wèn)題，比如:傳統(tǒng)的直接編碼方式不利于算法的搜索;同樣的進(jìn)化操作算子及適應(yīng)度函數(shù)不利于同時(shí)優(yōu)化硬約束條件和軟約束條件;傳統(tǒng)單目標(biāo)建模方式的運(yùn)算效率較低等。通過(guò)對(duì)超啟發(fā)技術(shù)、協(xié)

2、同進(jìn)化理論、多目標(biāo)優(yōu)化理論的深入研究，本論文提出了多種解決該問(wèn)題的啟發(fā)式進(jìn)化算法，主要成果包括以下五部分內(nèi)容：
　　第一，借鑒超啟發(fā)技術(shù)和進(jìn)化的思想，提出一種基于超啟發(fā)的Memetic算法(Memetic Algorithm based on Hyper-Heuristics，MAHH)用于求解單目標(biāo)考試時(shí)間表優(yōu)化問(wèn)題。MAHH是一種結(jié)合了超啟發(fā)技術(shù)和進(jìn)化策略的混合算法。超啟發(fā)技術(shù)的引入改變了傳統(tǒng)進(jìn)化算法直接對(duì)個(gè)體進(jìn)行搜索的模式，

3、采用一種間接的搜索模式，即通過(guò)傳統(tǒng)進(jìn)化策略搜索啟發(fā)式鏈表的方式尋找潛在個(gè)體。這種搜索方式可有效避免在處理考試時(shí)間表優(yōu)化問(wèn)題時(shí)直接編碼方式對(duì)算法搜索性能的影響。除此之外，一種特殊的鄰域變異方式被用于有效的指導(dǎo)MAHH算法進(jìn)行局部搜索。算法的仿真實(shí)驗(yàn)表明:MAHH的實(shí)驗(yàn)結(jié)果在11個(gè)測(cè)試問(wèn)題中的整體表現(xiàn)較為出色，且3個(gè)測(cè)試問(wèn)題的結(jié)果比其他7種傳統(tǒng)的超啟發(fā)解決方法更加優(yōu)秀。
　　第二，提出一種基于雙進(jìn)化策略的Memetic算法用于求解單目

4、標(biāo)考試時(shí)間表問(wèn)題(Memetic Algorithm based on Double Evolutionary Strategies，MADES)?？荚嚂r(shí)間表中存在兩類需要優(yōu)化的子問(wèn)題，即硬約束條件優(yōu)化和軟約束條件優(yōu)化，兩類子問(wèn)題并不適用于相同的進(jìn)化算子和適應(yīng)度函數(shù)進(jìn)行處理。MADES采用直接編碼方式，在兩個(gè)進(jìn)化空間中分別采用兩種不同的進(jìn)化算子和適應(yīng)度函數(shù)。此外，克隆算子的應(yīng)用能有效改善考試時(shí)間表問(wèn)題中可行個(gè)體不足的情況。MADES的仿

5、真試驗(yàn)表明:MADES中的各算子都對(duì)算法的搜索產(chǎn)生積極的影響;算法的運(yùn)行結(jié)果與其它多種經(jīng)典的考試時(shí)間表問(wèn)題優(yōu)化算法相比具有一定的競(jìng)爭(zhēng)性。
　　第三，借鑒第一章超啟發(fā)與進(jìn)化混合的思想，以及第二章提出的雙進(jìn)化策略，提出一種求解單目標(biāo)考試時(shí)間表問(wèn)題的自適應(yīng)協(xié)同進(jìn)化Memetic算法(AdaptiveCo-evolutionary Memetic Algorithm，ACMA)。ACMA采用啟發(fā)式搜索空間和解空間兩個(gè)進(jìn)化空間，利用基于超啟

6、發(fā)的進(jìn)化策略和傳統(tǒng)的進(jìn)化策略分別進(jìn)行硬約束條件優(yōu)化和軟約束條件優(yōu)化。此外，為了更合理的分配算法的計(jì)算資源，設(shè)計(jì)了一種自適應(yīng)協(xié)同進(jìn)化算子。該算子可根據(jù)種群中個(gè)體的實(shí)際情況，動(dòng)態(tài)控制算法的搜索空間。同時(shí)，兩空間的個(gè)體能夠通過(guò)協(xié)同進(jìn)化策略進(jìn)行協(xié)作。隨后的仿真實(shí)驗(yàn)表明:超啟發(fā)進(jìn)化策略的引入有利于算法更好的處理硬約束條件優(yōu)化，而傳統(tǒng)的進(jìn)化策略則能夠較好的保持種群的多樣性;自適應(yīng)參數(shù)能夠指導(dǎo)算法在更加合適的空間進(jìn)行搜索;協(xié)同進(jìn)化算子則進(jìn)一步減少了因

7、搜索方式的固定搜索易于陷入局部最優(yōu)的可能。與接近20種解決該問(wèn)題的常見算法相比，ACMA的結(jié)果僅次于當(dāng)前效果最好的四種算法，明顯優(yōu)于其他方法。
　　第四，為了給多目標(biāo)考試時(shí)間表問(wèn)題提供高效的進(jìn)化算法，本工作進(jìn)行多目標(biāo)優(yōu)化算法的理論研究，并提出一種新的多目標(biāo)免疫算法(EnhancedMulti-Objective Immune Algorithm，EMIA)。EMIA算法借鑒了經(jīng)典多目標(biāo)優(yōu)化算法NNIA的算法思路，構(gòu)建了一種資源分配

8、模型，并在此模型的基礎(chǔ)上，結(jié)合NNIA的克隆策略，設(shè)計(jì)了一種可動(dòng)態(tài)調(diào)節(jié)不同個(gè)體克隆比例的的新型克隆算子。此外一種新的擁擠距離度量方法的設(shè)計(jì)可有效改善原有方法在處理二目標(biāo)以上問(wèn)題上的不足，同時(shí)輔以擁擠距離動(dòng)態(tài)更新策略，可使個(gè)體分布密度的估計(jì)更為準(zhǔn)確。針對(duì)10個(gè)測(cè)試問(wèn)題，EMIA與三種經(jīng)典的多目標(biāo)進(jìn)化算法NNIA、NSGA-Ⅱ，MOEA/D進(jìn)行比較，其結(jié)果表明EMIA在絕大多數(shù)問(wèn)題中其收斂性和多樣性均好于NNIA、NSGA-Ⅱ，在某些問(wèn)題上

9、EMIA的收斂性比MOEA/D更佳。
　　第五，本工作首先構(gòu)建了一種新的多目標(biāo)考試時(shí)間表模型。隨后根據(jù)此模型的特點(diǎn)，同時(shí)參考之前提出的EMIA算法，設(shè)計(jì)了一種解決該問(wèn)題的EMIA改進(jìn)算法。多目標(biāo)考試時(shí)間表模型是在原有單目標(biāo)時(shí)間表模型的基礎(chǔ)上，增加一個(gè)時(shí)間表長(zhǎng)度最小化的目標(biāo)函數(shù)。EMIA的改進(jìn)算法采用一種混合初始化方法，并且舍棄了EMIA中原有的擁擠距離度量方法，采用一種簡(jiǎn)單的新方法保證種群的多樣性;同時(shí)采用一種特殊的局部搜索方法進(jìn)