超啟發(fā)式算法是一種啟發(fā)式算法的啟發(fā)式搜索方法,它通過啟發(fā)式策略,可以動態(tài)選擇、組合或生成一系列啟發(fā)式算法來解決問題規(guī)模巨大的搜索難題。超啟發(fā)式算法框架由頂層策略層與底層算法層構(gòu)成,策略層提供了管理和操控不同算法的方法,而算法層則是由針對特定問題的多個算法構(gòu)成。目前已有很多頂層策略層的研究,但是對于超啟發(fā)式算法的底層算法層,通常是采用固定數(shù)目的同類算法來構(gòu)建算法庫,針對算法數(shù)量、多種類算法共存等問題尚缺乏深入的研究。作為超啟發(fā)式算法重要的組成部分,底層算法庫的構(gòu)建方法對超啟發(fā)式算法的性能有重要的影響。一方面來說,底層算法庫中算法數(shù)量的增加可以使超啟發(fā)式算法解決不同問題的能力增強,但與此同時,也會給頂層策略的調(diào)度帶來壓力,影響超啟發(fā)式算法的性能;另一方面來說,同種類型算法在解決特定問題上具有相同的優(yōu)缺點,例如全局優(yōu)化算法雖然可以找到全局近似最優(yōu)解,但是由于面向的是全部搜索空間,導致它的搜索效率較慢。是否可以通過融合不同類別的算法來構(gòu)造算法庫,克服單一類型算法的局限性,進而提升超啟發(fā)式算法的性能,成為一個亟待解決的問題。基于以上兩部分內(nèi)容,本文對底層算法庫的構(gòu)建方法進行了充分的研究。本課題從... 

【文章來源】：北京化工大學北京市 211工程院校 教育部直屬院校

【文章頁數(shù)】：62 頁

【學位級別】：碩士

【圖文】：

圖１－１超啟發(fā)式算法框架??Ｆｉｇ．?１－１?Ｔｈｅ?ｆｒａｍｅｗｏｒｋ?ｏｆ?ｔｈｅ?Ｈｙｐｅｒ－ｈｅｕｒｉｓｔｉｃ?ａｌｇｏｒｉｔｈｍ??

表示。其中算法庫中每一個算法都具有一??個層次分布值，通過算法每次迭代過程中的表現(xiàn)來對層次分布值進行更新，對于頂層??策略層來說，每次調(diào)度算法時根據(jù)決策向量中每個算法的層次分布值的大小，來進行??算法的選齲??ｆｉ?－?■??＾?ｐｒｅｓｅｎｔ?ｉｎｄｉｖｉｄｕａｌｓ??Ｆｒｏｎｔ?Ｈ?〇?Ｌａｓｔ?ｉｎｄｉｖｉｄｕａｌｓ??Ｆｒｏｎｔ?Ｈ－ｌ?＇Ｏ??、、、、?ｎＨ??Ｆｒｏｎｔ?１?．?．?ＮＨ??°－＇－〇?＊??＼?Ｎｈ．，???＾＾??圖２－１兩個目標下的層次分布策略??Ｆｉｇ．２－１?Ｈｉｅｒａｒｃｈｙ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｓｔｒａｔｅｇｙ?ｆｏｒ?ｔｗｏ?ｏｂｊｅｃｔｉｖｅ?ｏｐｔｉｍｉｚａｔｉｏｎ?ｐｒｏｂｌｅｍ??對于層次分布值的具體描述可見圖２－１。在圖２－１中，層次分布策略使用了上文??中提到的非支配排序，來對狀態(tài)解進行了非支配排序。如圖所示，其中ｆｌ和ｆ２代表??了兩個優(yōu)化目標，圖中每個點代表了一個測試用例序列在兩個目標上的取值，根據(jù)不??同個體間的支配情況，可以分成若干層。由于超啟發(fā)式算法是通過不斷迭代的過程來??找尋最優(yōu)解，那么如何評價每個算法在當前執(zhí)行階段的好壞，就成為了如何進行算法??評價的核心。??層次分布策略通過將當前種群中的個體，與上一代種群中的個體進行非支配排??序，對個體進行分層。對應到圖上，假設ｆｌ和ｆ２的值都是越大越好，那么最外層Ｆｒｏｎｔ??Ｈ代表了當前的Ｐａｒｅｔｏ前沿，這一層可以支配剩下的所有層。在每一層中，黑色的點??代表了當前算法產(chǎn)生的個體，而白色代表了上一個算法產(chǎn)生的個體。關于層次分布值??具體的計算公式為：??１１?

過采用單種元啟發(fā)式算法結(jié)合不同的交叉算子和多種元啟發(fā)式算??法結(jié)合不同交叉算子來構(gòu)建超啟發(fā)式算法庫，以此來形成復雜性不同的算法庫。??ＨＨ－ＮＳＧＡ：?ＮＳＧＡ－Ｈ?＋?６種交叉算子??，算雜＇??／???＼?ＨＨ－ＳＰＥＡ?：?ＳＰＥＡ２?＋?６種交叉算子??Ｉ???ＨＳＡ２?Ｉ??Ｉ?）?ｈｈ－ｔａｅａ：?ＴＡＥＡ?＋?６?種交叉算子??＼?ＰｉＳ＂］?／??＼?Ｖ???／?ＨＨ－ＡＬＬ?：?ＮＳＧＡ－ＩＩ，?ＳＰＥＡ２＞?ＴＡＥＡ??＋?６種交叉算子??圖３－１四種不同復雜性的超啟發(fā)式算法庫??Ｆｉｇ．３－１?Ｆｏｕｒ?ｄｉｆｆｅｒｅｎｔ?ｃｏｍｐｌｅｘ?Ｈｙｐｅｒ－ｈｅｕｒｉｓｔｉｃ?ａｌｇｏｒｉｔｈｍ?ｌｉｂｒａｒｙ??目前已經(jīng)有非常多的算法來解決測試用例優(yōu)先排序問題，常見的有ＮＳＧＡ－ＩＩ，??ＳＰＥＡ，ＳＰＥＡ２，?ＴＡＥＡ等算法，本文通過這些元啟發(fā)式算法結(jié)合不同交叉算子來擴充??算法庫中算法的數(shù)目。通過這種方式，本文提出了四種不同復雜性的算法庫，用來證??明本文提出的觀點，如圖３－１所示。四種算法庫分別為ＨＨ－ＮＳＧＡ，ＨＨ－ＳＰＥＡ，??ＨＨ－ＴＡＥＡ和ＨＨ－ＡＬＬ。其中ＨＨ－ＮＳＧＡ是由ＮＳＧＡ－ＩＩ算法結(jié)合六種不同交叉算子形??成的由六種算法構(gòu)成的算法庫；ＨＨ－ＳＰＥＡ是由ＳＰＥＡ２算法結(jié)合六種不同交叉算子形??成的算法庫；ＨＨ－ＴＡＥＡ是由ＴＡＥＡ算法結(jié)合六種不同交叉算子形成的算法庫；??ＨＨ－ＡＬＬ是由ＮＳＧＡ－ＩＩ，ＳＰＥＡ２和ＴＡＥＡ三種算法分別結(jié)合六種交叉算子形成的由十??八種算法構(gòu)成的算法庫。前三種不同復雜性的算法庫雖然算法數(shù)目相同，但是由于算??法的實現(xiàn)原理并不相


本文編號：3210372