面向考試時間表問題的啟發(fā)式進化算法研究.pdf

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

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

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

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

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

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

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

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

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