[發(fā)明專利]一種基于信息熵的改進(jìn)進(jìn)化多目標(biāo)優(yōu)化方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201210057877.5
• 申請(qǐng)日: 2012-03-07
• 公開(kāi)（公告）號(hào): CN102622649A
• 公開(kāi)（公告）日: 2012-08-01
• 發(fā)明（設(shè)計(jì)）人: 王堃;王琳琳;暴建民;胡海峰;郭篁;于悅;房碩
• 申請(qǐng)（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號(hào): G06N3/12
• 分類號(hào): G06N3/12
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 葉連生

技術(shù)領(lǐng)域

本發(fā)明是一種基于信息熵的改進(jìn)進(jìn)化多目標(biāo)優(yōu)化方法，屬于進(jìn)化多目標(biāo)優(yōu)化領(lǐng)域。

背景技術(shù)

最近二十年來(lái)，進(jìn)化算法已被成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域，發(fā)展成為一個(gè)相對(duì)較熱的研究方向，即進(jìn)化多目標(biāo)優(yōu)化(evolutionary?multi-objective?optimization，簡(jiǎn)稱EMO)。從第一代進(jìn)化多目標(biāo)優(yōu)化算法的典型代表矢量評(píng)價(jià)遺傳算法(vector-evaluated?genetic?algorithms，簡(jiǎn)稱VEGA)，以及第二代進(jìn)化多目標(biāo)優(yōu)化算法中的PESA算法(The?Pareto?Envelope-based?Selection?Algorithm，PESA)，到當(dāng)前基于粒子群優(yōu)化、蟻群算法、人工免疫系統(tǒng)、分布估計(jì)算法、協(xié)同進(jìn)化算法、密母算法、文化進(jìn)化算法等的新型進(jìn)行多目標(biāo)優(yōu)化算法，都是通過(guò)不同的方法結(jié)合進(jìn)化計(jì)算來(lái)更有效地求解多維多目標(biāo)優(yōu)化問(wèn)題。

這其中，PESA算法充分利用了精英保留策略，設(shè)置了內(nèi)、外部種群，尋找并刪除外部種群中擁擠系數(shù)最大的個(gè)體。PESA算法的經(jīng)典之處在于，采用了網(wǎng)格方法(hyper-grid)將個(gè)體空間劃分成若干個(gè)格子，這樣每個(gè)個(gè)體就與某個(gè)網(wǎng)格相互關(guān)聯(lián)，從而用選擇網(wǎng)格代替?zhèn)€體選擇，利用網(wǎng)格法記錄解集信息。網(wǎng)格法保持種群的多樣性，為判斷解點(diǎn)(solution)是否在存在提供了方便，在一定程度上提高了算法的效率。然而針對(duì)PESA算法，其時(shí)間復(fù)雜度可以表示為O(N×N^*)，其中N為進(jìn)化種群的大小，N^*為外部種群的大小。根據(jù)大O符號(hào)原則(Big?O?notation)，可以看出，隨著解集數(shù)量的增加，PESA算法進(jìn)行進(jìn)化計(jì)算所需的運(yùn)算量、計(jì)算難度及運(yùn)算時(shí)間都將急劇增加，這將給進(jìn)化計(jì)算的進(jìn)行帶來(lái)極大麻煩。

Corne等人對(duì)PESA做了一些改進(jìn)，提出了基于區(qū)域選擇的概念，即PESA-II?(The?Pareto?Envelope-based?Selection?Algorithm?II，PESA-II)算法。與基于個(gè)體選擇的其他多目標(biāo)進(jìn)化算法相比，算法用網(wǎng)格選擇代替?zhèn)€體選擇，在一定程度上提高了算法的效率。但是，PESA-II算法進(jìn)行進(jìn)化計(jì)算所需的運(yùn)算量、計(jì)算難度及運(yùn)算時(shí)間，都將隨著進(jìn)化種群的增加而急劇增加，這將給進(jìn)化計(jì)算的進(jìn)行帶來(lái)極大麻煩。PESA-II算法的時(shí)間復(fù)雜度到達(dá)O(N×N^*)，N為進(jìn)化種群的大小，N^*為外部種群的大小。

Mikkel提出的新算法使得PESA運(yùn)行時(shí)間復(fù)雜度減少到O(GNlog^M-1AloglogA)。但是這些改善主要著眼于優(yōu)化進(jìn)化算法步驟或者算子，側(cè)重了考慮如何提高非支配分類的效率等。操作繁瑣復(fù)雜，難以簡(jiǎn)單便捷地反映了種群進(jìn)化信息，幫助研究者判斷種群進(jìn)化已經(jīng)是否到達(dá)成熟階段，從而盡早結(jié)束PESA算法的優(yōu)化過(guò)程。

發(fā)明內(nèi)容

技術(shù)問(wèn)題：本發(fā)明的目的是提供一種基于信息熵的改進(jìn)進(jìn)化多目標(biāo)優(yōu)化方法，即基于信息熵的改進(jìn)PESA算法(Comentropy-based?PESA，C-PESA)，將信息熵度量指標(biāo)引入到PESA算法中，利用信息熵指標(biāo)在量化度量Pareto解集(帕累托解集，即多目標(biāo)問(wèn)題存在的多個(gè)滿意解的集合)的分布特性，即均勻性、多樣性和收斂性方面的突出表現(xiàn)，及時(shí)考量PESA算法進(jìn)化后種群個(gè)體的進(jìn)化程度。當(dāng)種群進(jìn)化到種群分布均勻多樣之后，及時(shí)結(jié)束PESA算法，避免大量不必要的復(fù)雜進(jìn)化過(guò)程。

技術(shù)方案：本發(fā)明的一種基于信息熵的改進(jìn)進(jìn)化多目標(biāo)優(yōu)化方法，是將信息熵指標(biāo)融入一種進(jìn)化多目標(biāo)優(yōu)化算法PESA算法(PESA，Pareto?Envelope-based?Selection?Algorithm)框架，按照提出的算法步驟及實(shí)際操作方法度量進(jìn)化過(guò)程中的信息熵?cái)?shù)值，根據(jù)信息熵指標(biāo)的變化情況，判斷種群進(jìn)化是否已經(jīng)到達(dá)成熟階段，及時(shí)結(jié)束PESA算法，簡(jiǎn)化算法的時(shí)間復(fù)雜度；

所述的將信息熵指標(biāo)融入PESA算法框架，是在現(xiàn)有PESA算法中添加如下步驟：首先，度量每一次返回的外部種群EP(EP，external?population)進(jìn)化種群的信息熵?cái)?shù)值；其次，與前一次迭代進(jìn)化過(guò)程獲得的信息熵指標(biāo)進(jìn)行對(duì)比；最后，根據(jù)信息熵指標(biāo)的變化情況，判斷PESA算法的進(jìn)化種群是否從逐步發(fā)展乃至已經(jīng)達(dá)到成熟階段；