本文關(guān)鍵詞：面向考試時間表問題的啟發(fā)式進(jìn)化算法研究

  更多相關(guān)文章： 進(jìn)化算法 Memetic算法 單目標(biāo)優(yōu)化 多目標(biāo)優(yōu)化 考試時間表問題

【摘要】：時間表優(yōu)化問題作為調(diào)度領(lǐng)域的研究熱點(diǎn)問題,涉及范圍大到軍事國防,小到醫(yī)院學(xué)校的時間安排,在現(xiàn)實(shí)世界中的應(yīng)用領(lǐng)域十分廣泛。開展時間表優(yōu)化問題的高效進(jìn)化算法研究對國家、社會和個人都具有重大的意義。本論文以考試時間表問題作為研究背景,分析現(xiàn)有解決該問題的進(jìn)化算法所面臨的主要問題,比如：傳統(tǒng)的直接編碼方式不利于算法的搜索；同樣的進(jìn)化操作算子及適應(yīng)度函數(shù)不利于同時優(yōu)化硬約束條件和軟約束條件；傳統(tǒng)單目標(biāo)建模方式的運(yùn)算效率較低等。通過對超啟發(fā)技術(shù)、協(xié)同進(jìn)化理論、多目標(biāo)優(yōu)化理論的深入研究,本論文提出了多種解決該問題的啟發(fā)式進(jìn)化算法,主要成果包括以下五部分內(nèi)容：第一,借鑒超啟發(fā)技術(shù)和進(jìn)化的思想,提出一種基于超啟發(fā)的Memetic算法(Memetic Algorithm based on Hyper-Heuristics, MAHH)用于求解單目標(biāo)考試時間表優(yōu)化問題。MAHH是一種結(jié)合了超啟發(fā)技術(shù)和進(jìn)化策略的混合算法。超啟發(fā)技術(shù)的引入改變了傳統(tǒng)進(jìn)化算法直接對個體進(jìn)行搜索的模式,采用一種間接的搜索模式,即通過傳統(tǒng)進(jìn)化策略搜索啟發(fā)式鏈表的方式尋找潛在個體。這種搜索方式可有效避免在處理考試時間表優(yōu)化問題時直接編碼方式對算法搜索性能的影響。除此之外,一種特殊的鄰域變異方式被用于有效的指導(dǎo)MAHH算法進(jìn)行局部搜索。算法的仿真實(shí)驗表明：MAHH的實(shí)驗結(jié)果在11個測試問題中的整體表現(xiàn)較為出色,且3個測試問題的結(jié)果比其他7種傳統(tǒng)的超啟發(fā)解決方法更加優(yōu)秀。第二,提出一種基于雙進(jìn)化策略的Memetic算法用于求解單目標(biāo)考試時間表問題(Memetic Algorithm based on Double Evolutionary Strategies, MADES)。考試時間表中存在兩類需要優(yōu)化的子問題,即硬約束條件優(yōu)化和軟約束條件優(yōu)化,兩類子問題并不適用于相同的進(jìn)化算子和適應(yīng)度函數(shù)進(jìn)行處理。MADES采用直接編碼方式,在兩個進(jìn)化空間中分別采用兩種不同的進(jìn)化算子和適應(yīng)度函數(shù)。此外,克隆算子的應(yīng)用能有效改善考試時間表問題中可行個體不足的情況。MADES的仿真試驗表明：MADES中的各算子都對算法的搜索產(chǎn)生積極的影響；算法的運(yùn)行結(jié)果與其它多種經(jīng)典的考試時間表問題優(yōu)化算法相比具有一定的競爭性。第三,借鑒第一章超啟發(fā)與進(jìn)化混合的思想,以及第二章提出的雙進(jìn)化策略,提出一種求解單目標(biāo)考試時間表問題的自適應(yīng)協(xié)同進(jìn)化Memetic算法(Adaptive Co-evolutionary Memetic Algorithm, ACMA)。ACMA采用啟發(fā)式搜索空間和解空間兩個進(jìn)化空間,利用基于超啟發(fā)的進(jìn)化策略和傳統(tǒng)的進(jìn)化策略分別進(jìn)行硬約束條件優(yōu)化和軟約束條件優(yōu)化。此外,為了更合理的分配算法的計算資源,設(shè)計了一種自適應(yīng)協(xié)同進(jìn)化算子。該算子可根據(jù)種群中個體的實(shí)際情況,動態(tài)控制算法的搜索空間。同時,兩空間的個體能夠通過協(xié)同進(jìn)化策略進(jìn)行協(xié)作。隨后的仿真實(shí)驗表明：超啟發(fā)進(jìn)化策略的引入有利于算法更好的處理硬約束條件優(yōu)化,而傳統(tǒng)的進(jìn)化策略則能夠較好的保持種群的多樣性；自適應(yīng)參數(shù)能夠指導(dǎo)算法在更加合適的空間進(jìn)行搜索；協(xié)同進(jìn)化算子則進(jìn)一步減少了因搜索方式的固定搜索易于陷入局部最優(yōu)的可能。與接近20種解決該問題的常見算法相比,ACN MA的結(jié)果僅次于當(dāng)前效果最好的四種算法,明顯優(yōu)于其他方法。第四,為了給多目標(biāo)考試時間表問題提供高效的進(jìn)化算法,本工作進(jìn)行多目標(biāo)優(yōu)化算法的理論研究,并提出一種新的多目標(biāo)免疫算法(Enhanced Multi-Objective Immune Algorithm, EMIA)。EMIA算法借鑒了經(jīng)典多目標(biāo)優(yōu)化算法NNIA的算法思路,構(gòu)建了一種資源分配模型,并在此模型的基礎(chǔ)上,結(jié)合NNIA的克隆策略,設(shè)計了一種可動態(tài)調(diào)節(jié)不同個體克隆比例的的新型克隆算子。此外一種新的擁擠距離度量方法的設(shè)計可有效改善原有方法在處理二目標(biāo)以上問題上的不足,同時輔以擁擠距離動態(tài)更新策略,可使個體分布密度的估計更為準(zhǔn)確。針對10個測試問題,EMIA與三種經(jīng)典的多目標(biāo)進(jìn)化算法NNIA、NSGA-Ⅱ, MOEA/D進(jìn)行比較,其結(jié)果表明EMIA在絕大多數(shù)問題中其收斂性和多樣性均好于NNIA、 NSGA-II,在某些問題上EMIA的收斂性比MOEA/D更佳。第五,本工作首先構(gòu)建了一種新的多目標(biāo)考試時間表模型。隨后根據(jù)此模型的特點(diǎn),同時參考之前提出的EMIA算法,設(shè)計了一種解決該問題的EMIA改進(jìn)算法。多目標(biāo)考試時間表模型是在原有單目標(biāo)時間表模型的基礎(chǔ)上,增加一個時間表長度最小化的目標(biāo)函數(shù)。EMIA的改進(jìn)算法采用一種混合初始化方法,并且舍棄了EMIA中原有的擁擠距離度量方法,采用一種簡單的新方法保證種群的多樣性；同時采用一種特殊的局部搜索方法進(jìn)一步優(yōu)化個體。最終的仿真結(jié)果表明：EMIA的改進(jìn)算法在處理多目標(biāo)考試時間表問題時能夠得到多樣性和收斂性較好的非支配解集,并且在大部分問題上,與其它傳統(tǒng)單目標(biāo)優(yōu)化算法的結(jié)果相差不大。
【關(guān)鍵詞】：進(jìn)化算法 Memetic算法 單目標(biāo)優(yōu)化 多目標(biāo)優(yōu)化 考試時間表問題
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TP18
【目錄】：

• 摘要5-7
• ABSTRACT7-13
• 符號對照表13-14
• 縮略語對照表14-19
• 第一章 緒論19-31
• 1.1 研究背景與意義19-20
• 1.2 進(jìn)化算法的分類和基本框架20-22
• 1.2.1 進(jìn)化算法的分類20-22
• 1.2.2 進(jìn)化算法的基本框架22
• 1.3 進(jìn)化算法的最新進(jìn)展22-25
• 1.3.1 免疫進(jìn)化算法23
• 1.3.2 量子進(jìn)化算法23
• 1.3.3 Memetic算法23-24
• 1.3.4 群智能算法24
• 1.3.5 協(xié)同進(jìn)化算法24-25
• 1.4 考試時間表問題25
• 1.5 考試時間表問題相關(guān)技術(shù)的最新進(jìn)展25-29
• 1.5.1 圖啟發(fā)技術(shù)25-26
• 1.5.2 基于局部搜索的技術(shù)26-27
• 1.5.3 基于種群的技術(shù)27-28
• 1.5.4 超啟發(fā)方法28-29
• 1.6 本論文的主要工作29-31
• 第二章 求解考試時間表問題的MAHH算法31-47
• 2.1 引言31
• 2.2 考試時間表問題的數(shù)學(xué)描述31-32
• 2.3 MAHH的算法設(shè)計32-38
• 2.3.1 算法框架與主要流程32-33
• 2.3.2 超啟發(fā)編碼方式33-36
• 2.3.3 種群初始化方法36-37
• 2.3.4 局部搜索算子設(shè)計37-38
• 2.4 實(shí)驗結(jié)果與分析38-45
• 2.4.1 實(shí)驗設(shè)置38-39
• 2.4.2 測試數(shù)據(jù)39
• 2.4.3 初始化方法的性能分析39-41
• 2.4.4 不同圖啟發(fā)算法的性能分析41-42
• 2.4.5 局部搜索算子的性能分析42-44
• 2.4.6 算法最終結(jié)果的對比分析44-45
• 2.5 本章小結(jié)45-47
• 第三章 求解考試時間表問題的MADES算法47-59
• 3.1 引言47
• 3.2 MADES的算法設(shè)計47-52
• 3.2.1 算法框架與流程47-48
• 3.2.2 適應(yīng)度值評價函數(shù)48-49
• 3.2.3 初始化方法49
• 3.2.4 交叉操作和變異操作49-50
• 3.2.5 局部搜索算子(第一進(jìn)化空間)50-51
• 3.2.6 局部搜索算子(第二進(jìn)化空間)51-52
• 3.3 實(shí)驗結(jié)果與分析52-58
• 3.3.1 第二進(jìn)化空間種群規(guī)模n的設(shè)定52-53
• 3.3.2 操作算子的性能分析53-56
• 3.3.3 算法最終結(jié)果對比與分析56-58
• 3.4 小結(jié)58-59
• 第四章 求解考試時間表問題的ACMA算法59-73
• 4.1 引言59
• 4.2 ACMA的算法設(shè)計59-64
• 4.2.1 算法框架與流程59-60
• 4.2.2 進(jìn)化策略分析60-62
• 4.2.3 自適應(yīng)協(xié)同進(jìn)化策略62-64
• 4.3 實(shí)驗結(jié)果與分析64-71
• 4.3.1 算法性能評價64-66
• 4.3.2 自適應(yīng)協(xié)同進(jìn)化策略性能分析66-69
• 4.3.3 局部搜索策略的性能分析69-71
• 4.4 小結(jié)71-73
• 第五章 一種改進(jìn)的多目標(biāo)免疫算法73-103
• 5.1 引言73
• 5.2 多目標(biāo)優(yōu)化問題的數(shù)學(xué)描述73-74
• 5.3 三種經(jīng)典的進(jìn)化多目標(biāo)優(yōu)化算法74-79
• 5.3.1 NSGA-Ⅱ74-76
• 5.3.2 MOEA/D76-77
• 5.3.3 NNIA77-79
• 5.4 EMIA的算法設(shè)計79-85
• 5.4.1 算法框架與流程79
• 5.4.2 一種新型的克隆算子79-83
• 5.4.3 一種新的擁擠距離度量方法83-84
• 5.4.4 重組操作與變異操作84-85
• 5.4.5 算法復(fù)雜度分析85
• 5.5 實(shí)驗結(jié)果與分析85-101
• 5.5.1 測試問題85-87
• 5.5.2 性能評價指標(biāo)87-88
• 5.5.3 擁擠距離算子的性能測試88-91
• 5.5.4 算法收斂性結(jié)果分析91-99
• 5.5.5 擴(kuò)展性實(shí)驗分析99-101
• 5.6 本章小結(jié)101-103
• 第六章 求解多目標(biāo)考試時間表問題的EMIA改進(jìn)算法103-121
• 6.1 引言103
• 6.2 多目標(biāo)考試時間表問題103
• 6.3 EMIA改進(jìn)算法的算法設(shè)計103-108
• 6.3.1 算法初始化104-105
• 6.3.2 局部搜索算子105-107
• 6.3.3 交叉和變異操作107-108
• 6.4 實(shí)驗結(jié)果與分析108-119
• 6.4.1 實(shí)驗設(shè)置108-109
• 6.4.2 初始化方法性能測試109-112
• 6.4.3 克隆操作算子的性能指標(biāo)112-114
• 6.4.4 局部搜索算子的性能分析114-116
• 6.4.5 算法最終結(jié)果分析116-119
• 6.5 小結(jié)119-121
• 第七章 結(jié)論和展望121-123
• 7.1 總結(jié)與討論121-122
• 7.2 進(jìn)一步研究展望122-123
• 參考文獻(xiàn)123-135
• 致謝135-137
• 作者簡介137-138

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 葛磊;武芳;王鵬波;張冬林;;3維建筑綜合中基于最小特征的面平移算法[J];測繪科學(xué)技術(shù)學(xué)報;2009年02期

2 駱雯,孫延明,陳振威,陳錦昌;判斷點(diǎn)與封閉多邊形相對關(guān)系的改進(jìn)算法[J];機(jī)械;1999年03期

3 李林;盧顯良;;一種基于切割映射的規(guī)則沖突消除算法[J];電子學(xué)報;2008年02期

4 劉巧玲;張紅英;林茂松;;一種簡單快速的圖像去霧算法[J];計算機(jī)應(yīng)用與軟件;2013年07期

5 林亞平,楊小林;快速概率分析進(jìn)化算法及其性能研究[J];電子學(xué)報;2001年02期

6 章郡鋒;吳曉紅;黃曉強(qiáng);何小海;;基于暗原色先驗去霧的改進(jìn)算法[J];電視技術(shù);2013年23期

7 楊鐵軍;靳婷;;一種動態(tài)整周模糊值求解算法及其仿真分析[J];系統(tǒng)工程與電子技術(shù);2007年01期

8 周秀玲;郭平;陳寶維;王靜;;幾種計算超體積算法的比較研究[J];計算機(jī)工程;2011年03期

9 吳一戎,胡東輝,彭海良;Chirp Scaling SAR成象算法及其實(shí)現(xiàn)[J];電子科學(xué)學(xué)刊;1995年03期

10 王貴竹;一種產(chǎn)生單向分解值的算法[J];安徽大學(xué)學(xué)報(自然科學(xué)版);2001年03期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 尹冀鋒;;一種新的圖象自適應(yīng)增強(qiáng)算法[A];四川省通信學(xué)會一九九二年學(xué)術(shù)年會論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計算機(jī)輔助增強(qiáng)、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價值[A];中華醫(yī)學(xué)會第十次全國超聲醫(yī)學(xué)學(xué)術(shù)會議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進(jìn)[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實(shí)現(xiàn)[A];中國光學(xué)學(xué)會2010年光學(xué)大會論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國青年通信學(xué)術(shù)會議論文集（上）[C];2008年

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標(biāo)TBD算法[A];第十四屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集[C];2008年

7 周磊;張衛(wèi)華;王曉奇;張軍;;基于流水算法的智能路障機(jī)器人設(shè)計[A];2011年全國電子信息技術(shù)與應(yīng)用學(xué)術(shù)會議論文集[C];2011年

8 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

9 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測算法[A];第六屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會議（NCMT2010）、第6屆全國人機(jī)交互學(xué)術(shù)會議（CHCI2010）、第5屆全國普適計算學(xué)術(shù)會議（PCC2010）論文集[C];2010年

10 楊任爾;陳懇;勵金祥;;基于棱邊方向檢測的運(yùn)動自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 國泰君安資產(chǎn)管理部;“算法交易”是道指暴跌罪魁禍?zhǔn)?[N];上海證券報;2010年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 馮輝;網(wǎng)絡(luò)化的并行與分布式優(yōu)化算法研究及應(yīng)用[D];復(fù)旦大學(xué);2013年

2 許玉杰;云計算環(huán)境下海量數(shù)據(jù)的并行聚類算法研究[D];大連海事大學(xué);2014年

3 李琰;基于貓群算法的高光譜遙感森林類型識別研究[D];東北林業(yè)大學(xué);2015年

4 陳加順;海洋環(huán)境下聚類算法的研究[D];南京航空航天大學(xué);2014年

5 王洋;基于群體智能的通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘算法研究[D];太原理工大學(xué);2015年

6 雷雨;面向考試時間表問題的啟發(fā)式進(jìn)化算法研究[D];西安電子科技大學(xué);2015年

7 張冬麗;人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用研究[D];燕山大學(xué);2014年

8 徐悅竹;機(jī)會發(fā)現(xiàn)算法及其應(yīng)用研究[D];哈爾濱工程大學(xué);2010年

9 王征;分布式互斥算法的研究與實(shí)現(xiàn)[D];電子科技大學(xué);2007年

10 王艷嬌;人工蜂群算法的研究與應(yīng)用[D];哈爾濱工程大學(xué);2013年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 姚鑫宇;EMD去噪與MUSIC算法在DOA估計中的聯(lián)合應(yīng)用[D];昆明理工大學(xué);2015年

2 陸進(jìn);面向含噪數(shù)據(jù)聚類相關(guān)算法的研究[D];復(fù)旦大學(xué);2014年

3 李家昌;基于能量約束的超聲圖像自動分割算法[D];華南理工大學(xué);2015年

4 陳堅;基于密度和約束的數(shù)據(jù)流聚類算法研究[D];蘭州大學(xué);2015年

5 高健;基于Zynq7000平臺的去霧算法研究及實(shí)現(xiàn)[D];南京理工大學(xué);2015年

6 顧磊;基于Hadoop的聚類算法的數(shù)據(jù)優(yōu)化及其應(yīng)用研究[D];南京信息工程大學(xué);2015年

7 楊燕霞;基于Hadoop平臺的并行關(guān)聯(lián)規(guī)則挖掘算法研究[D];四川師范大學(xué);2015年

8 王羽;基于MapReduce的社區(qū)發(fā)現(xiàn)算法的設(shè)計與實(shí)現(xiàn)[D];南京理工大學(xué);2015年

9 許振佳;流式數(shù)據(jù)的并行聚類算法研究[D];曲阜師范大學(xué);2015年

10 董琴;人工蜂群算法的改進(jìn)與應(yīng)用[D];大連海事大學(xué);2015年

，

本文編號：632895