国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于最小熵產(chǎn)生選擇策略的遺傳算法研究

2019-10-21 01:09李元香紀(jì)道敏項(xiàng)正龍
關(guān)鍵詞:測(cè)試函數(shù)熱力學(xué)遺傳算法

高 晶 李元香 紀(jì)道敏 項(xiàng)正龍

(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)

0 引 言

遺傳算法是由美國(guó)的Holland教授于1975年首先提出的一種借鑒達(dá)爾文的“優(yōu)勝劣汰,適者生存”生物進(jìn)化理論的隨機(jī)優(yōu)化算法[1]。它是一種啟發(fā)式搜索和優(yōu)化技術(shù),可直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作,不需要對(duì)目標(biāo)函數(shù)的連續(xù)性進(jìn)行限定。主要特點(diǎn)是整個(gè)求解過程從群體出發(fā),具有較高的魯棒性和全局搜索能力,對(duì)優(yōu)化問題的領(lǐng)域沒有局限性,可擴(kuò)展性強(qiáng)[2]。遺傳算法被證明非常適合于高度非線性問題的優(yōu)化,可以在復(fù)雜的多維搜索空間中找到全局最優(yōu)解,在許多問題中都得到了廣泛的應(yīng)用,如背包問題、旅行商TSP問題、n皇后問題[3]等。近年來,從簡(jiǎn)單的PID控制,到復(fù)雜的最優(yōu)控制[4]、自適應(yīng)控制[5]等工程控制問題,遺傳算法都有著較為成功的應(yīng)用案例。現(xiàn)如今,隨著人工智能熱度的上升,遺傳算法再次成為研究的熱點(diǎn),遺傳算法等演化算法和人工智能相結(jié)合,可進(jìn)行自然災(zāi)害的評(píng)估[6]、建立醫(yī)學(xué)藥物劑量預(yù)測(cè)模型[7]、規(guī)劃最優(yōu)路徑[8]等。

遺傳算法雖然應(yīng)用廣泛,但在解決較為復(fù)雜的問題時(shí),由于它本身的隨機(jī)搜索特點(diǎn),依然存在收斂速度慢和過早收斂?jī)煞矫娴睦_[9]。Whitley[10]提出遺傳算法中最重要的兩個(gè)因素是“選擇壓力”和“種群多樣性”。近年來,很多學(xué)者在遺傳算法緩解“選擇壓力”、增加“種群多樣性”上做了很多研究。Alabsi等[11]使用了穩(wěn)態(tài)替換策略來緩解選擇壓力;王麗萍等[12]提出了角度懲罰距離精英選擇策略防止精英選擇產(chǎn)生過大的壓力;Zhang等[13]通過適應(yīng)度共享創(chuàng)造小生境進(jìn)化環(huán)境,以此增加種群多樣性;Li等[14]將遺傳算法中的種群視為一個(gè)動(dòng)力學(xué)系統(tǒng),個(gè)體視為粒子,遺傳操作視為離子的碰撞或移動(dòng),驅(qū)動(dòng)所有粒子盡可能地運(yùn)動(dòng)來保持種群多樣性。已有方法從多個(gè)角度緩解選擇壓力,從而保持種群多樣性,但是,它們大多都是直接將函數(shù)適應(yīng)值作為評(píng)價(jià)函數(shù),這樣很難從根源上緩解選擇壓力從而提高種群多樣性。

為了解決直接將函數(shù)適應(yīng)值作為評(píng)價(jià)函數(shù)而導(dǎo)致的選擇壓力過大問題,本文將函數(shù)適應(yīng)值通過種群中的個(gè)體密度轉(zhuǎn)化為群體熵產(chǎn)生,通過驅(qū)使群體熵產(chǎn)生最小從而求得最優(yōu)的函數(shù)適應(yīng)值。本文將遺傳算法中的種群視為被外界強(qiáng)加固定壓力的非孤立系統(tǒng),種群在進(jìn)化的每一代都看成非平衡定態(tài)。將物理學(xué)中最小熵產(chǎn)生[15]的概念引入到遺傳算法中,利用非孤立系統(tǒng)在非平衡定態(tài)[16]下遵循最小熵增原理,對(duì)傳統(tǒng)遺傳算法的選擇策略進(jìn)行改進(jìn),提出了一種基于最小熵增原理的選擇策略。在該策略中,采用個(gè)體密度來衡量種群多樣性,用精英策略驅(qū)動(dòng)種群朝熵產(chǎn)生[17]最小的方向快速下降。最后在背包問題和數(shù)值優(yōu)化問題上驗(yàn)證了這種選擇策略的有效性。

1 遺傳算法和最小熵增原理

1.1 遺傳算法

遺傳算法是一種啟發(fā)式算法,來源于達(dá)爾文的生物學(xué)原理,最早是由John Holland 引入的,為了解釋自然系統(tǒng)的適應(yīng)性過程,以及在類似基礎(chǔ)上產(chǎn)生的人工系統(tǒng)。在自然界中,新生物通過進(jìn)化來適應(yīng)環(huán)境,遺傳算法用類似的方式演化出給定問題的解。

為了得到優(yōu)化問題的解決方案,遺傳算法的流程如下:

1) 確定編碼方式,初始化n個(gè)隨機(jī)編碼染色體的種群;

2) 計(jì)算種群中每個(gè)個(gè)體的目標(biāo)函數(shù),對(duì)個(gè)體進(jìn)行評(píng)價(jià);

3) 根據(jù)個(gè)體適應(yīng)值,從種群中選擇個(gè)體(一般適應(yīng)值越好被選中的可能性越大)進(jìn)行繁殖;

4) 交叉操作;

5) 變異操作;

6) 產(chǎn)生m個(gè)新個(gè)體;

7) 從m+n個(gè)個(gè)體中選擇適應(yīng)值最優(yōu)的n個(gè)個(gè)體作為下一代種群;

8) 當(dāng)滿足最后的終止條件時(shí),輸出整個(gè)過程中找到的最優(yōu)解,沒達(dá)到終止條件時(shí),重復(fù)2—7。

遺傳算法以生物進(jìn)化為原型,和傳統(tǒng)的優(yōu)化方法(枚舉、啟發(fā)式等)相比,整個(gè)求解過程從群體出發(fā),具有較高的魯棒性和全局搜索能力,能并行搜索多個(gè)峰值;求解過程和最終結(jié)果和問題領(lǐng)域以及初始化無關(guān);使用概率機(jī)制進(jìn)行迭代,具有隨機(jī)性;算法具有較強(qiáng)的可擴(kuò)展性,能靈活地和其他算法和策略進(jìn)行融合,適合于求解復(fù)雜的優(yōu)化問題。

1.2 最小熵增原理

一個(gè)孤立的熱力學(xué)體系,隨著內(nèi)部粒子的自由運(yùn)動(dòng),不論其初始處于何種狀態(tài),最終總會(huì)達(dá)到平衡狀態(tài)。達(dá)到平衡狀態(tài)后,體系的熵為極大值,最終體系中可以引起熵增的所有熱力學(xué)流和熱力學(xué)力均為零。但如果不是孤立體系,環(huán)境對(duì)體系施加某種限制。如保持一定的溫度差或濃度差等,這時(shí),體系不可能達(dá)到熱力學(xué)平衡態(tài)。如果外界施加的條件是固定的,如一定的溫度差或一定的濃度差,體系開始會(huì)因外界的限制條件而發(fā)生變化,但最后會(huì)達(dá)到一種相對(duì)穩(wěn)定的狀態(tài),這種狀態(tài)被稱為非平衡定態(tài)。

熵產(chǎn)生是非平衡態(tài)熱力學(xué)中非常重要的物理變量,在Prigogine等[18]提出的耗散結(jié)構(gòu)中,把熱力學(xué)第二定律由封閉體系推廣到了敞開體系,把熵變分為了兩個(gè)部分:(1) 由體系與環(huán)境的相互作用(物質(zhì)和能量交換)而引起的,稱為熵流;(2) 由體系內(nèi)部的不可逆過程產(chǎn)生的,稱為熵產(chǎn)生。熵產(chǎn)生的表達(dá)式為:

(1)

式中:Jk表示第k種不可逆過程的流;Xk表示第k種不可逆過程的推動(dòng)力。

非平衡定態(tài)具有一些特殊的性質(zhì),Prigogine在1945年提出了非平衡定態(tài)的最小熵增原理:在接近平衡的條件下,與外界強(qiáng)加的限制相適應(yīng)的非平衡定態(tài)的熵產(chǎn)生具有極小值。

2 最小熵增原理在遺傳算法上的應(yīng)用

2.1 熱力學(xué)系統(tǒng)與遺傳算法

借鑒熱力學(xué)系統(tǒng)在趨于非平衡定態(tài)的過程中熵產(chǎn)生的變化規(guī)律,將遺傳算法中的種群類比為加了固定壓力差的熱力學(xué)系統(tǒng),兩者之間的對(duì)應(yīng)關(guān)系如表 1所示。

表1 熱力學(xué)系統(tǒng)與遺傳算法對(duì)應(yīng)關(guān)系

2.2 改進(jìn)的遺傳算法

2.2.1原理描述

基本的遺傳算法通過選擇、交叉和變異從父代中生成子代,直接選取適應(yīng)值最好的個(gè)體作為下一代種群。本文提出基于最小熵增原理的遺傳算法(Minimum Entropy Production Genetic Algorithm, MEPGA)就是把非平衡定態(tài)下的熵產(chǎn)生最小的原理應(yīng)用到遺傳算法中新種群的選取中,以保證種群的多樣性。其基本原理如下:用個(gè)體密度衡量種群多樣性,當(dāng)種群的多樣性過低時(shí),利用貪婪選擇策略,從新產(chǎn)生的子代和父代個(gè)體中選擇使群體熵產(chǎn)生最小的新種群作為下一代種群,以此來保證種群多樣性,從而有利于跳出局部最優(yōu)。

改進(jìn)的遺傳算法MEPGA的基本流程如下:

1) 確定編碼方式,產(chǎn)生初始種群,設(shè)置種群大小N、進(jìn)化代數(shù)、交叉變異概率等。

2) 對(duì)種群中的個(gè)體進(jìn)行評(píng)估(計(jì)算個(gè)體的適應(yīng)度值、計(jì)算個(gè)體的密度)。

3) 采用輪盤賭方法從父代種群中選擇產(chǎn)生子代的個(gè)體。

4) 對(duì)選出的個(gè)體進(jìn)行交叉、變異操作,產(chǎn)生M個(gè)子代。

5) 對(duì)M+N個(gè)個(gè)體先使用精英保留策略選取n′個(gè)適應(yīng)度值最好的個(gè)體,然后對(duì)剩下的個(gè)體使用貪婪選擇機(jī)制,逐個(gè)往n′個(gè)個(gè)體中加入剩下的個(gè)體,直到個(gè)體數(shù)達(dá)到N,始終保持種群的熵產(chǎn)生最小。

6) 判斷是否達(dá)到迭代終止條件,迭代結(jié)束輸出最優(yōu)解個(gè)體和最優(yōu)解值,否則重復(fù)2—5。

求解流程如圖 1所示。

圖1 改進(jìn)的MEPGA流程圖

2.2.2個(gè)體密度和群體熵

群體熵產(chǎn)生計(jì)算公式最終可轉(zhuǎn)化為密度變化的計(jì)算,因此首先需要對(duì)群體中個(gè)體的密度進(jìn)行定義。

定義1(絕對(duì)適應(yīng)值)設(shè)S為搜索空間,f:S→R為目標(biāo)函數(shù),Xi是種群中的第i個(gè)個(gè)體。當(dāng)求解的是最大優(yōu)化問題時(shí),e(Xi)=-f(Xi);當(dāng)求解的是最小優(yōu)化問題時(shí),e(Xi)=f(Xi)。

借鑒等級(jí)熵[19]的劃分方式,對(duì)活躍窗口和等級(jí)進(jìn)行如下定義:

定義2(活躍窗口)設(shè)Pt=(X1,X2,…,XN)∈SN為基于最小熵增原理遺傳算法的第t代種群,Ot=(XN+1,XN+2,…,XN+M)表示由第t代種群產(chǎn)生的M個(gè)子代個(gè)體。第t代種群的活躍窗口wt由如下規(guī)則生成:1)w0=[l0,u0],l0是初始種群中絕對(duì)適應(yīng)值的下限,u0是初始種群中的上限。2)wt=[lt,ut]表示第t代的活躍窗口,wt+1=[lt+1,ut+1]表示第t+1代活躍窗口,其中l(wèi)t+1=min(lt,min(e(Xj))),j∈(N+1,N+M),ut+1=max(ut,max(e(Xj))),j∈(N+1,N+M)。

本文提出的基于最小熵增原理的遺傳算法直接對(duì)活動(dòng)窗口進(jìn)行固定的均勻劃分,劃分份數(shù)為常數(shù)K,則種群在第t代第j個(gè)區(qū)間的范圍可表示為:

根據(jù)Prigogine對(duì)熱力學(xué)第二定律的推廣,非孤立系統(tǒng)的熵產(chǎn)生是系統(tǒng)內(nèi)各種流和產(chǎn)生這種流所對(duì)應(yīng)力的乘積之和。對(duì)于一個(gè)兩組分體系,在體系兩端保持一定的溫度差,由于熱擴(kuò)散現(xiàn)象,會(huì)引起體系的濃度差,此時(shí)體系中同時(shí)存在兩種力:X熱與X擴(kuò),和兩種相應(yīng)的流:J熱流和J擴(kuò)散流,所以熵產(chǎn)生可表示為:σ=J熱流X流+J擴(kuò)散流X擴(kuò)。

當(dāng)本文討論的體系達(dá)到不隨時(shí)間變化的非平衡定態(tài)時(shí),熱流J熱流等于零,因此熵產(chǎn)生可表示為:σ=J擴(kuò)散流X擴(kuò),擴(kuò)散流的產(chǎn)生源于體系粒子密度的變化,壓力導(dǎo)致密度差,因此對(duì)群體的熵產(chǎn)生可定義如下:

(2)

式中:ρi表示個(gè)體Xi的密度;ρ0是初始種群的個(gè)體密度均值;k是熱力學(xué)中的常量。

2.2.3基于最小熵增原理的貪婪熱力學(xué)替換

從父代種群Pt=(X1,X2,…,XN)的N個(gè)個(gè)體與產(chǎn)生的M個(gè)子代種群Ot=(XN+1,XN+2,…,XN+M),共N+M個(gè)體中挑選出N個(gè)個(gè)體組成下一代種群Pt+1,使其具有的熵產(chǎn)生σ(Pt+1)最小。

按照貪婪的策略[22]逐個(gè)往下一代種群中填充使臨時(shí)種群熵產(chǎn)生最小的個(gè)體,具體的算法實(shí)現(xiàn)如算法1所示。

算法1基于最小熵增的貪婪熱力學(xué)替換

輸入:第t代父種群Pt,第t代子種群Ot

輸出:第t+1代種群Pt+1

1) 將父種群Pt和子種群Ot合并得到大小為N+M的中間種群P′t + 1

2) fori=1 toN

//采用貪婪策略逐個(gè)往Pt+1中填充個(gè)體,直到N個(gè)

3) forj=1 toN+M-i

//尋找本輪最優(yōu)的個(gè)體

4) 計(jì)算將P′t + 1中的第j個(gè)個(gè)體加到Pt+1后的熵產(chǎn)生σ(Pt+1∪P′t+1[j])

5) 記錄本次循環(huán)中使熵產(chǎn)生最小的個(gè)體Xj

6) end

7) 將個(gè)體Xj填充到Pt+1中,同時(shí)將其從中間種群P′t + 1中移除

8) end

2.2.4基于最小熵增原理的遺傳算法

以上個(gè)體密度、群體熵產(chǎn)生和基于最小熵增原理的替換規(guī)則是本文改進(jìn)遺傳算法的主要構(gòu)成部分。它們保證了種群能在保持一定多樣性的前提下快速向群體熵產(chǎn)生最小的方向進(jìn)化。本文提出的算法稱為基于最小熵產(chǎn)生的熱力學(xué)遺傳算法,算法2給出了本文算法的主要流程。

算法2基于最小熵增原理的遺傳算法(MEPGA)

輸入:搜索空間和目標(biāo)函數(shù)

輸出:最優(yōu)解

1) 確定個(gè)體編碼,設(shè)置交叉和變異概率Pc和Pm,區(qū)間劃分等級(jí)數(shù)K,迭代次數(shù)T

2) 隨機(jī)生成N個(gè)個(gè)體作為初始種群P0,對(duì)P0中的個(gè)體進(jìn)行評(píng)估

3) 計(jì)算初始活躍窗口w0

4) fori=0 toT

5) 通過輪盤賭從Pi中選擇父代個(gè)體進(jìn)行交叉、變異產(chǎn)生M個(gè)子個(gè)體

6) 評(píng)估M個(gè)子個(gè)體

7) 更新活躍窗口得到wi+1

8) 計(jì)算種群中個(gè)體的密度分布狀況

9) 利用基于最小熵增的貪婪熱力學(xué)選擇機(jī)制,從N+M個(gè)個(gè)體中選擇N個(gè)個(gè)體作為Pi+1

10) end

11) 將迭代過程中得到的使目標(biāo)函數(shù)最優(yōu)的個(gè)體作為最優(yōu)解輸出

上述算法中初始化時(shí)需要設(shè)置的參數(shù)和基于模擬退火的遺傳算法[20]相比減少了溫度,從而在迭代過程中也就不需要設(shè)置相關(guān)的冷卻進(jìn)度表[21],簡(jiǎn)化了進(jìn)化過程中參數(shù)的設(shè)置。為了平衡“選擇壓力”和“種群多樣性”之間的關(guān)系,本文算法使用了種群中個(gè)體密度的分布對(duì)種群多樣性進(jìn)行度量,只有當(dāng)種群多樣性較低時(shí)才使用基于最小熵增的貪婪熱力學(xué)選擇機(jī)制進(jìn)行后代的篩選,控制群體向熵產(chǎn)生最小的方向進(jìn)化,以保證種群的多樣性。

3 實(shí) 驗(yàn)

為了驗(yàn)證基于最小熵增原理遺傳算法的適用性,并且希望通過實(shí)驗(yàn)獲得該方法的進(jìn)一步改進(jìn)和推廣思路,本文選取了幾個(gè)典型的測(cè)試問題進(jìn)行了實(shí)驗(yàn)驗(yàn)證,主要包括0-1背包問題和數(shù)值優(yōu)化問題。除了本文提出的算法,主要對(duì)比的算法有簡(jiǎn)單遺傳算法(Genetic algorithm, GA)、穩(wěn)態(tài)遺傳算法(Steady state genetic algorithm, SSGA)和小生境遺傳算法(Niche genetic algorithm, NGA)。

3.1 測(cè)試函數(shù)和參數(shù)設(shè)置

數(shù)值優(yōu)化問題選取了8個(gè)數(shù)值優(yōu)化測(cè)試函數(shù),分別是經(jīng)典的測(cè)試函數(shù)Sphere函數(shù)、Rosenbrock函數(shù)、Rastrigin函數(shù)和Ackley函數(shù),以及CEC 2013測(cè)試函數(shù)集[23]中的9、15、25和26號(hào)函數(shù),分別記為f2、f3、f4、f5、f6、f7、f8、f9,這其中有單峰函數(shù)、多峰函數(shù)、多模函數(shù)和組合函數(shù)。表2為8個(gè)數(shù)值測(cè)試函數(shù)的表達(dá)式/名稱和變量取值范圍。

表2 數(shù)值優(yōu)化測(cè)試問題

本文實(shí)驗(yàn)中運(yùn)用第2節(jié)中描述的基于最小熵增原理的遺傳算法,交叉概率Pc=0.9,變異概率Pm=0.2。對(duì)0-1背包問題f1分別選取50和100個(gè)物品個(gè)數(shù)進(jìn)行實(shí)驗(yàn)驗(yàn)證。對(duì)數(shù)值測(cè)試函數(shù)分別在10維和20維下進(jìn)行測(cè)試。每個(gè)測(cè)試問題都在上述參數(shù)設(shè)置下獨(dú)立運(yùn)行50次,取每次運(yùn)行結(jié)果的平均值作為最終求解結(jié)果。

3.2 實(shí)驗(yàn)結(jié)果分析

將四種算法在相同參數(shù)下對(duì)不同的測(cè)試問題、不同的測(cè)試問題維度,獨(dú)立運(yùn)行50次,分別從最優(yōu)解均值和最優(yōu)解方差兩個(gè)方面來對(duì)這兩種算法的性能進(jìn)行對(duì)比,最終的統(tǒng)計(jì)結(jié)果如表3所示。

表3 算法在背包問題上的結(jié)果統(tǒng)計(jì)

可以看出,MEPGA算法所求的最優(yōu)解均值和方差在這四個(gè)算法中都占據(jù)優(yōu)勢(shì),可見算法在尋找簡(jiǎn)單背包問題的求解上有一定改進(jìn)效果。

表4為四種算法在數(shù)值函數(shù)問題中的測(cè)試結(jié)果,分析統(tǒng)計(jì)結(jié)果可知,MEPGA算法在所測(cè)的大多數(shù)數(shù)值函數(shù)問題上最優(yōu)解的均值和方差都能得到較好的結(jié)果,在少數(shù)多峰多模問題上結(jié)果和改進(jìn)的遺傳算法(SSGA、NGA)沒有明顯優(yōu)勢(shì),但比簡(jiǎn)單遺傳算法(GA)所得結(jié)果好。所選測(cè)試問題覆蓋范圍廣、有一定代表性,因此可以說明本文算法改進(jìn)策略的有效性。

表4 算法在數(shù)值函數(shù)測(cè)試的結(jié)果統(tǒng)計(jì)

續(xù)表4

通過多次運(yùn)行后的統(tǒng)計(jì)結(jié)果分析,本文中提出的算法在離散問題、數(shù)值優(yōu)化問題(包括單峰、多模、組合函數(shù)等)上大多都能獲得較好的結(jié)果,相較簡(jiǎn)單遺傳算法(GA)而言,結(jié)果有了很大的改善。在少數(shù)測(cè)試函數(shù)上的處理結(jié)果和改善后的穩(wěn)態(tài)遺傳算法(SSGA)、小生境遺傳算法(NGA)不分伯仲,但多數(shù)情況下還是比這兩種算法效果要理想。由此可見,本文提出的選擇策略在一定程度上能改善種群在進(jìn)化過程中的選擇壓力,從而能夠找到更好的解。

以下隨機(jī)選取了實(shí)驗(yàn)過程中比較有代表性的幾個(gè)測(cè)試問題在不同緯度下的收斂曲線圖。圖 2中分別是GA、SSGA、NGA和MEPGA在物品數(shù)n=50和n=100時(shí)的最優(yōu)點(diǎn)的變化趨勢(shì)。

圖2 f1 最優(yōu)點(diǎn)變化趨勢(shì)

由圖2中最優(yōu)點(diǎn)的變化趨勢(shì)來看,不管物品數(shù)是50還是100,MEPGA算法找到的最優(yōu)解和其他三種算法相比更有優(yōu)勢(shì),說明基于最小熵增原理的遺傳算法在改進(jìn)背包問題上是可行的而且能保持較好的種群多樣性,能有效地跳出局部最優(yōu)解從而搜索到全局最優(yōu)解。

圖3和圖4是本文提出的算法和GA、SSGA、NGA分別在10維和20維的f6~f9數(shù)值測(cè)試函數(shù)上最優(yōu)值的收斂軌跡。可以看出,MEPGA在數(shù)值測(cè)試問題上也有較明顯的效果,而且比簡(jiǎn)單遺傳算法(GA)、改進(jìn)遺傳算法(SSGA、NGA)搜索到的最優(yōu)值更好。

圖3 f6 ~f7測(cè)試函數(shù) 問題維數(shù)n=10

圖4 f8 ~f9測(cè)試函數(shù) 問題維數(shù)n=20

從整體的實(shí)驗(yàn)效果來看,MEPGA在組合優(yōu)化問題,單峰、多峰、多模、組合等數(shù)值優(yōu)化問題上都有一定的適用性。從統(tǒng)計(jì)結(jié)果中四個(gè)算法運(yùn)行的最優(yōu)值均值可以看出,本文算法在大多測(cè)試函數(shù)上都能找到比其他算法更優(yōu)的解,這很好地說明了本文的改進(jìn)在一定程度上緩解了種群在進(jìn)化過程中的選擇壓力,從而能更好跳出局部最優(yōu)找到更優(yōu)的解。統(tǒng)計(jì)結(jié)果中的最優(yōu)值方差則反映了本文的改進(jìn)策略具有更高的魯棒性。

4 結(jié) 語

針對(duì)遺傳算法在搜索過程中由于選擇壓力過大導(dǎo)致種群多樣性喪失,從而容易陷入局部最優(yōu)的問題,本文將熱力學(xué)非平衡定態(tài)下的最小熵增原理應(yīng)用到遺傳算法的選擇策略中,提出了一種基于最小熵產(chǎn)生的選擇策略,能在種群快速收斂的同時(shí)保持種群的多樣性,進(jìn)而跳出局部最優(yōu)。實(shí)驗(yàn)表明,改進(jìn)后的算法MEPGA在0-1背包問題和單峰、多峰數(shù)值優(yōu)化問題上均能得到比GA和改進(jìn)的遺傳算法更好的結(jié)果。這說明基于最小熵增原理的選擇策略在緩解選擇壓力、保證種群平穩(wěn)進(jìn)化上是有一定效果的。由于本文使用的是貪婪選擇機(jī)制,因此計(jì)算時(shí)間復(fù)雜度比較高。本文的后續(xù)工作將著重研究算法計(jì)算效率的改進(jìn),對(duì)基于最小熵產(chǎn)生原理選擇策略做進(jìn)一步完善。同時(shí)本文只是將基于最小熵增原理應(yīng)用于簡(jiǎn)單的遺傳算法,驗(yàn)證該策略的可行性,后續(xù)將嘗試將該策略推廣到其他演化算法,進(jìn)一步驗(yàn)證本文中所提出改進(jìn)策略的普適性。

猜你喜歡
測(cè)試函數(shù)熱力學(xué)遺傳算法
了解固體和液體特性 掌握熱力學(xué)定律內(nèi)容
解信賴域子問題的多折線算法
一種基于精英選擇和反向?qū)W習(xí)的分布估計(jì)算法
熱力學(xué)第一定律易混易錯(cuò)剖析
基于遺傳算法的高精度事故重建與損傷分析
基于自適應(yīng)調(diào)整權(quán)重和搜索策略的鯨魚優(yōu)化算法
基于遺傳算法的模糊控制在過熱汽溫控制系統(tǒng)優(yōu)化中的應(yīng)用
基于遺傳算法的智能交通燈控制研究
具有收縮因子的自適應(yīng)鴿群算法用于函數(shù)優(yōu)化問題
基于改進(jìn)多島遺傳算法的動(dòng)力總成懸置系統(tǒng)優(yōu)化設(shè)計(jì)