結合熱力學遺傳算法的多目標優化方法
2023-06-04 06:20:36
專利名稱：結合熱力學遺傳算法的多目標優化方法
技術領域：
本發明屬於多目標優化技術領域，涉及一種多目標優化方法，尤其涉及一種結合熱力學遺傳算法的多目標優化方法。
背景技術：
在實際生活中，多目標優化(Multobjective Optimization，簡稱M0)是工程應用中常見的難題。傳統的數學規劃方法在問題複雜、非線性時無能為力。近幾年，人們開始將注意力投向利用遺傳算法(Genetic Algorithm，簡稱GA)來解決多目標優化，期望這種全局並行搜索技術能找到一個較好的Pareto優集，作為MO問題的一個解集。國際上這方面的研究剛剛開始，提出了一些解決方法。但到目前為止，解決MO 問題做得較好的是利用遺傳算法和Pareto排序相結合的技術，這種技術的優點是可以在 Pareto集的全部區域上探測，不足是所求的Pareto優集分布不均勻，包含的Pareto最優解較少，導致的根本原因就是遺傳算法的「未成熟收斂」性。此外，模擬退火(Simulated Annealing，簡稱SA)是一種能達到全局極優的方法， 將SA與GA結合克服GA未成熟收斂的工作已有一些，如Mahfoud等人的工作。但目前這些方法主要都是將SA與GA混合，即在優化過程中交替使用SA和GA0還很少有工作研究如何將SA的全局收斂性導入到GA中，構造GA與SA的結合，使GA在選擇個體時，不僅考慮到適應度，還考慮到SA的自由能。現有解決MO問題的方法中，測試例子中的解不能準確落在Pareto優集上的原因在於現有的算法在選擇優良個體時，個體是否會被選中生存下來，是與前面已經生存下來的個體有關的。即，如果已經被選中的個體中有比較差的(算法不保證不選差的個體，只需個體和已入選的個體之間沒有支配關係，並且在入選後群體熵最大就可被選中)，而這些差的個體有可能支配那些優良的個體，從而抑制優良個體的入選。
發明內容
本發明所要解決的技術問題是提供一種結合熱力學遺傳算法的多目標優化方法，可以獲得一個較好的Pareto優集。為解決上述技術問題，本發明採用如下技術方案一種結合熱力學遺傳算法的多目標優化方法，所述方法包括如下步驟步驟Si、初始化群體大小Np、進化的代數Ng、溫度T ；步驟S2、令t = 0，生成初始群體P (t = 0)；步驟S3、在P(t)中選擇一個個體作為精英elite保留；步驟S4、將群體P(t)中的個體隨機配對，應用交叉算子於所有配對個體對得到Np 個子代個體；然後對Np個父代個體和Np個子代個體進行變異操作，得到一個包含2Np個個體的中間群體F (t)；步驟S5、令 i = l，P(t+l) = {elite}；
步驟S6、令P(t+1，i，h)表示已選好的屬於P(t+1)的i_l個個體，以及屬於中間群體P、(t)的第h個個體；計算群體P(t+l，i，h)的自由能F，其中h= 1，2，···，2Νρ;
F={E)-T ^Η『{Ε)-Τ《Η々,Η)；
k k=\其中，Hk(i，h)= -Pk (i，h) Iogpk(i，h)；pk(i，h)是群體F (t)中第h個個體和群體P(t+1)的第k個個體之間海明碼距與個體編碼長度的比值；在群體F (t)尋找h使得自由能F，F達到最小，並將此第h個個體加入P(t+1)，作為群體P(t+1)的第i個個體；允許選擇相同的個體；步驟S7、令i = i+Ι，如果i < Np，跳轉到步驟S6 ；否則轉至步驟S8 ；步驟S8、令t = t+Ι，如果t <Ng，跳轉到步驟S3，否則結束。作為本發明的一種優選方案，所述步驟S2具體為令t = 0，隨機生成初始群體 P(t = 0)。所述方法作為圖像識別方法的一部分，或者作為語音識別方法的一部分，或者作為數據挖掘方法的一部分，或者作為機器人控制方法的一部分。本發明的有益效果在於本發明提出的結合熱力學遺傳算法的多目標優化方法， 引入熵和溫度的概念來實現適應度共享，最終可以獲得一個較好的Pareto優集。本發明在研究方法上進行了更新，將熱力學中熵的概念引入多目標優化問題，發揮了熱力學中熵的優越性，有效利用了樣本集本身的內在的知識，避免了部分優良個體的落選問題；能夠保證優良個體最終能夠生存。本發明具有一定的通用性，採用本發明方法，面對不同類型的多目標優化問題，都能迅速較多的優良個體。本發明應用面較廣，可以應用在圖像識別、語音識別、數據挖掘、機器人研究等方面。
圖1為本發明方法的流程圖。
具體實施例方式下面結合附圖詳細說明本發明的優選實施例。實施例一本方法從一個新的角度上分析了多目標優化問題與遺傳算法結合的問題。提出應用結合熱力學中熵的概念來改進的遺傳算法解決多目標優化問題的新思路，最終可以獲得一個較好的Pareto優集，解決了如何在選擇時保證優良個體最終能夠生存的問題。1、MO 問題和 Pareto 排序1. IMO 問題以最小化問題為例，MO問題描述如下minxi F / (χ), /2 (χ) ,L , /Μ (χ)(1)其中(χ)，f2(x)，L，fM(x)是要最小化的目標函數，χ是自變量，F是可行解空間。為了精確描述問題的解，首先給出兩個相關概念的定義。定義1 如果存在一個可行解χ*，使得對任何χ e F,m= l，2，L，M，fm(x*) ￡fffl(x),則稱χ*是MO問題的一個最優解。χ*只是一個理論上的最優解，在一般情形下，有時某個解既有較大的分量，也有較小的分量，此時是沒有理論上最優解的。因此，在MO問題中就引入了 Pareto最優解這一概
O定義2 設有兩個可行解X1, X2，若對任何m = 1,2, L, M，有fm(Xl) ￡fm(x2)成立， 且存在某個m滿足fm(Xl) < fffl(x2)，則稱X1支配X20如果一個可行解\沒有被任何χ e F 所支配，就稱\為Pareto最優解。由所有Pareto最優解組成的集合稱之為Pareto優集。 Pareto最優解\只是一個可被接受的最優解，有時稱之為非劣解。解決MO問題的實際目標就是要獲得整個Pareto優集。2、Pareto 排序如何表示多個目標之間的關聯是MO問題求解的一個難點，目前最常用的方法是採用Goldberg提出的Pareto排序算法。算法描述如下(1)令序號計數器k = 1.(2)找到群體P中所有未被支配的個體(解)所形成的集合A，並將集合A中的全部個體的序號設為k (Pareto優先度).(3)從群體P中刪去在A中的個體.(4)如果群體P為空，則算法結束.(5)令 k = k+Ι，轉到 1.Pareto的排序實質上就是對群體中全部個體進行一種分類。這種分類有一個特點就是同一類(有相同Pareto優先度)的個體相互之間不存在支配關係。這正是Pareto優集的一個重要性質。當進一步將適應度納入考慮範圍，就可以選擇其中一類作為所要求解的Pareto優集。本發明在下面提出的算法正是結合了這一點。3、最小自由能原理與遺傳算法的結合在熱力學中，一個系統的自由能F定義為F = -HT(2)其中是此熱力學系統的平均能量，H是系統的熵值，T為系統溫度。若這個系統處於穩定狀態，則系統的自由能F最小，這是熱力學中的最小自由能原理，SA就是基於它提出的。對最小優化問題，如果將遺傳算法中的群體看成是一個熱力學系統，"看成是群體的適應度，那麼要求群體的最小自由能，也就是要在最大化群體的適應度_和最大化群體的多樣性(群體的熵)之間取得一種平衡。_就是經Pareto排序後群體所有個體的Pareto優先度(個體的序號)的均值。3. 1熵值的設定熵是一個系統混亂程度的度量，一般將熵定義為普通的信息熵。本發明提出了利用個體間的海明距(採用二進位編碼)來定義和計算一個系統(群體)的熵值設有一個群體P，其中Pk (i，h)表示群體P中選定的第h個個體和群體P的第k個個體之間海明距diff與個體編碼長度1的比值diff/Ι。該比值作為群體P中各個個體以概率P1, P2,... Pn發出的η個消息，且每個消息是相互獨立的。則平均信息量既熵值H由各消息的信息量的加權平均求和得到，即下述表達式!-1孖=^其中 Hk(i，h) = _pk(i，h)log pk(i，h)熵值越大表明群體的多樣性維持得越好，但如果太大，群體將會徹底無序，變成不收斂。溫度用來與熵值一起作用，控制群體的多樣性。由於考慮問題時可以將-當作常數-1看待，所以當HT > 1/NP時，群體收斂的結果不具備個體間不相互支配這一性質，即群體中的個體不是同屬於一個Pareto集。溫度T太大將導致這種情形的出現，故T應該滿足關係式T d(d為常數)時，i，j才進行交叉，以期得到多樣化的子代，防止遺傳算法的「未成熟收斂」和「遺傳漂移」。請參閱圖1，下面是本發明給出的熱力學遺傳算法求解MO問題的算法包括如下步驟步驟Si、初始化群體大小Np、進化的代數Ng、溫度T ；步驟S2、令t = 0，隨機生成初始群體P (t = 0)；步驟S3、在P(t)中選擇一個個體作為精英elite保留；步驟S4、將群體P (t)中的個體隨機配對，應用交叉算子於所有配對個體對得到Np 個子代個體；然後對Np個父代個體和Np個子代個體進行變異操作，得到一個包含2Np個個體的中間群體F (t)；步驟S5、令 i = l，P(t+l) = {elite}；步驟S6、令P(t+1，i，h)表示已選好的屬於P (t+1)的i_l個個體，以及屬於中間群體P、(t)的第h個個體；計算群體P(t+l，i，h)的自由能F，其中h= 1，2，···，2Νρ;
F,-T H,-T《Hk(i,h、；(4)
k k=\其中，Hk(i，h)=_pk(i，h)log pk(i, h)；pk(i，h)是群體F (t)中第h個個體和群體P (t+1)的第k個個體之間海明碼距與個體編碼長度的比值；在群體F (t)尋找h使得自由能F，(4)式達到最小，並將此第h個個
6體加入P(t+1)，作為群體P(t+1)的第i個個體；允許選擇相同的個體；步驟S7、令i = i+Ι，如果i < Np，跳轉到步驟S6 ；否則轉至步驟S8 ；步驟S8、令t = t+Ι，如果t <Ng，跳轉到步驟S3，否則結束。本發明應用面較廣，可以應用在圖像識別、語音識別、數據挖掘、機器人研究等方 這裡本發明的描述和應用是說明性的，並非想將本發明的範圍限制在上述實施例中。這裡所披露的實施例的變形和改變是可能的，對於那些本領域的普通技術人員來說實施例的替換和等效的各種部件是公知的。本領域技術人員應該清楚的是，在不脫離本發明的精神或本質特徵的情況下，本發明可以以其它形式、結構、布置、比例，以及用其它組件、 材料和部件來實現。在不脫離本發明範圍和精神的情況下，可以對這裡所披露的實施例進行其它變形和改變。
權利要求
1.一種結合熱力學遺傳算法的多目標優化方法，其特徵在於，所述方法包括如下步驟步驟Si、初始化群體大小Np、進化的代數Ng、溫度T ；步驟S2、令t = 0，生成初始群體P (t = 0)；步驟S3、在P (t)中選擇一個個體作為精英elite保留；步驟S4、將群體P (t)中的個體隨機配對，應用交叉算子於所有配對個體對得到Np個子代個體；然後對Np個父代個體和Np個子代個體進行變異操作，得到一個包含2Np個個體的中間群體F (t)；步驟 S5、令 i = l，P(t+l) = {elite}；步驟S6、令P(t+1，i，h)表示已選好的屬於P(t+1)的i_l個個體，以及屬於中間群體 P、(t)的第h個個體；計算群體P(t+l，i，h)的自由能F，其中h = l，2，...，2Np;F={E)-T ^Η『{Ε)-Τ《Η々,Η)；k k=\其中，Hk (i, h) = -pk(i, h) log pk(i, h)；Pk(i，h)是群體F (t)中第h個個體和群體P(t+1)的第k個個體之間海明碼距與個體編碼長度的比值；在群體F (t)尋找h使得自由能F，F達到最小，並將此第h個個體加入 P(t+1)，作為群體P(t+1)的第i個個體；允許選擇相同的個體；步驟S7、令i = i+Ι，如果i < Np，跳轉到步驟S6 ；否則轉至步驟S8 ； 步驟S8、令t = t+Ι，如果t <Ng，跳轉到步驟S3，否則結束。
2.根據權利要求1所述的多目標優化方法，其特徵在於所述步驟S2具體為令t = 0，隨機生成初始群體P (t = 0)。
3.根據權利要求1所述的多目標優化方法，其特徵在於所述方法作為圖像識別方法的一部分，或者作為語音識別方法的一部分，或者作為數據挖掘方法的一部分，或者作為機器人控制方法的一部分。
全文摘要
本發明揭示了一種結合熱力學遺傳算法的多目標優化方法，當一個個體佔優或此個體鄰域的其他個體數目較多，則按一定的策略降低此個體的適應度。即，位於比較擁擠的區域的個體其子代的數量將會相對減少，這樣使得群體的分布能夠較均勻地覆蓋Pareto優集。在本發明給出的算法中，為了降低適應度，利用了熱力學中的熵和溫度的概念。本發明引入熵和溫度的概念來實現適應度共享，最終可以獲得一個較好的Pareto優集。本發明在研究方法上進行了更新，將熱力學中熵的概念引入多目標優化問題，發揮了熱力學中熵的優越性，有效利用了樣本集本身的內在的知識，避免了部分優良個體的落選問題；能夠保證優良個體最終能夠生存。
文檔編號G06N3/12GK102360456SQ20111031284
公開日2012年2月22日 申請日期2011年10月14日 優先權日2011年10月14日
發明者胡靜 申請人:上海電機學院