基于歷史信息的拓?fù)湮锓N分化算法.pdf

1、現(xiàn)實(shí)世界中的大量?jī)?yōu)化問(wèn)題都含有多個(gè)極優(yōu)解（全局最優(yōu)解或局部最優(yōu)解）。面對(duì)這些優(yōu)化問(wèn)題，獲得多個(gè)極優(yōu)解往往比僅獲得一個(gè)全局最優(yōu)解更為有益。多模優(yōu)化（Multimodal Optimization）尋找一個(gè)優(yōu)化問(wèn)題的多個(gè)極優(yōu)解。作為一種通用的黑盒優(yōu)化算法，演化算法（Evolutionary Algorithm，EA）在多模優(yōu)化中應(yīng)用廣泛，并形成了演化多模優(yōu)化這一獨(dú)特的研究分支。物種分化(Speciation)是演化多模優(yōu)化中的一項(xiàng)基礎(chǔ)技術(shù)。

2、通過(guò)將一個(gè)種群劃分成物種(Species)的集合，該技術(shù)使得演化算法能夠工作在較高的物種層次，以物種為單位進(jìn)行操作，而不是局限于單個(gè)個(gè)體。目前，已有大量演化多模優(yōu)化算法依賴(lài)于該技術(shù)。物種分化的效率和質(zhì)量無(wú)疑將對(duì)這些算法的性能表現(xiàn)產(chǎn)生直接影響。因此，研究高性能的物種分化算法具有重要意義。
　　物種分化技術(shù)的關(guān)鍵和難點(diǎn)為判斷兩個(gè)體是否屬于同一物種。目前，主要有基于距離的和基于拓?fù)涞膬深?lèi)算法?；诰嚯x的算法根據(jù)兩個(gè)個(gè)體間的距離判斷它們是

3、否屬于同一物種，依賴(lài)設(shè)置困難的小生境(Niche)半徑參數(shù)，對(duì)目標(biāo)問(wèn)題有較強(qiáng)假設(shè)。其優(yōu)點(diǎn)在于無(wú)需在解空間中采樣新的點(diǎn)，從而沒(méi)有額外的適應(yīng)度評(píng)估開(kāi)銷(xiāo)?；谕?fù)涞乃惴ǜ鶕?jù)適應(yīng)度地形的拓?fù)浣Y(jié)構(gòu)特征來(lái)判斷兩個(gè)個(gè)體是否屬于同一物種，無(wú)需小生境半徑參數(shù)，對(duì)目標(biāo)問(wèn)題假設(shè)較弱。然而，現(xiàn)有拓?fù)湮锓N分化算法都需要采樣新的點(diǎn)以捕獲適應(yīng)度地形的拓?fù)浣Y(jié)構(gòu)特征，從而造成額外的適應(yīng)度評(píng)估開(kāi)銷(xiāo)。適應(yīng)度評(píng)估是演化算法的核心資源。降低物種分化過(guò)程中的適應(yīng)度評(píng)估消耗對(duì)于提升

4、算法的整體性能具有非常積極的作用。
　　本文研究無(wú)需消耗額外適應(yīng)度評(píng)估的拓?fù)湮锓N分化技術(shù)。基于隨機(jī)采樣的演化算法在執(zhí)行過(guò)程中會(huì)產(chǎn)生大量歷史信息。于是，提出僅通過(guò)歷史信息來(lái)捕獲適應(yīng)度地形的拓?fù)浣Y(jié)構(gòu)特征。為此，首先從點(diǎn)序列的全新視角重新闡釋了現(xiàn)有拓?fù)湮锓N分化算法的基本思想，并將新思路的核心問(wèn)題歸結(jié)為構(gòu)造一個(gè)僅由歷史點(diǎn)構(gòu)成的近似序列。將該問(wèn)題形式化為了一個(gè)帶約束的組合優(yōu)化問(wèn)題，并設(shè)計(jì)了一個(gè)專(zhuān)門(mén)的分治算法對(duì)其進(jìn)行高效求解。最后，得到了一個(gè)