遺傳算法在求解復(fù)雜函數(shù)給定區(qū)間上最值中的應(yīng)用

1、計算智能導(dǎo)論大作業(yè) -遺傳算法在求解復(fù)雜函數(shù)給定區(qū)間上最值中的應(yīng)用一、遺傳算法簡介遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色

2、體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度（fitness）大小選擇（selection）個體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作

3、為問題近似最優(yōu)解，對于各種通用問題都可以使用1.1術(shù)語說明由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個算法中會用到很多生物遺傳學(xué)知識，下面是一些常用術(shù)語的說明：染色體染色體又可以叫做基因型個體(individuals),一定數(shù)量的個體組成了群體(population),群體中個體的數(shù)量叫做群體大小?；蚧蚴谴械脑?，基因用于表示個體的特征。例如有一個串S=1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alleles)。基因位點基因位點在算法中表示一個基因在串中的位置稱為基因位置(Gene Position)，有時也簡稱基因位?；蛭恢糜纱?/p>

4、左向右計算，例如在串 S=1101 中，0的基因位置是3。特征值在用串表示整數(shù)時，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。適應(yīng)度各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。 這個函數(shù)是計算個體在群體中被使用的概率。1.2傳算法的實現(xiàn) (1)編碼遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個體。這一轉(zhuǎn)換操作就叫做編碼，也可以稱作(問題的)表示(represe

5、ntation)。而二進(jìn)制編碼是目前遺傳算法中最常用的編碼方法。即是由二進(jìn)制字符集0,1產(chǎn)生通常的0,1字符串來表示問題空間的候選解。它具有以下特點：a)簡單易行b)符合最小字符集編碼原則c)便于用模式定理進(jìn)行分析，因為模式定理就是以基礎(chǔ)的。(2)適應(yīng)度函數(shù)進(jìn)化論中的適應(yīng)度，是表示某一個體對環(huán)境的適應(yīng)能力，也表示該個體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評價函數(shù)，是用來判斷群體中的個體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的。遺傳算法在搜索進(jìn)化過程中一般不需要其他外部信息，僅用評估函數(shù)來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此

6、基礎(chǔ)上計算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。由此可見，在不少場合，將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的。適應(yīng)度函數(shù)的設(shè)計主要滿足以下條件：a）單值、連續(xù)、非負(fù)、最大化b) 合理、一致性c）計算量小d）通用性強(qiáng)。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而定。適應(yīng)度函數(shù)設(shè)計直接影響到遺傳算法的性能。(3)初始群體選取遺傳算法中初始群體中的個體是隨機(jī)產(chǎn)生的。一般來講，初始群體的設(shè)定可采取如下的策略:a)根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。b)先隨機(jī)生成一定數(shù)目的個體，然后從中挑出最好的個體加到

7、初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)達(dá)到了預(yù)先確定的規(guī)模。1.3運算過程遺傳算法的基本運算過程如圖1，其中各步完成的工作如下 a)初始化：設(shè)置進(jìn)化代數(shù)計數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個個體作為初始群體P(0)。b)個體評價：計算群體P(t)中各個個體的適應(yīng)度。c)選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。d)交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。e)變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因

8、值作變動。群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t+1)。f)終止條件判斷:若t=T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。圖1.遺傳算法流程圖1.4特點及應(yīng)用遺傳算法還具有以下幾方面的特點：(1)遺傳算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。(2)遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。(3)遺傳算法基本上不用搜

9、索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。(4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時，適應(yīng)度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。(6)算法本身也可以采用動態(tài)自適應(yīng)技術(shù)，在進(jìn)化過程中自動調(diào)整算法控制參數(shù)和編碼精度，比如使用模糊自適應(yīng)法。由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計算時不依賴于梯度信息或其它輔助知識，而只需要影響

10、搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于函數(shù)優(yōu)化和組合優(yōu)化，車間調(diào)度等方面。二、用遺傳算法求解復(fù)雜函數(shù)的在給定區(qū)間上的最值下面用遺傳算法求函數(shù)f(x)的最大值 f(x)=10*sin(5x)+7*cos(x) x0,10，分辨率為0.012.1編碼我們采用最常用的二進(jìn)制編碼形式進(jìn)行編碼，考慮到分辨率的要求，我們需要采用轉(zhuǎn)換的方式進(jìn)行浮點數(shù)的編碼將 x 的值用一個10位的二值形式表示為二值問題，一個10位的二值數(shù)提供的分辨率是每為 (10-0)/(210-1)0.01 。 %將變量

11、域 0,10 離散化為二值域 0,1023, x=0+10*b/1023, 其中 b 是 0,1023 中的一個二值數(shù)。2.2適應(yīng)度函數(shù)選取直接將目標(biāo)函數(shù)取為適應(yīng)度函數(shù)，同時考慮到f(x)存在小于零的情況，此時，需將適應(yīng)度函數(shù)值取為0.即2.3仿真結(jié)果最佳編碼序列為：0 0 0 0 1 0 0 0 0 0對應(yīng)x的取值為: 0.31281第 8 次迭代達(dá)到最大值求得最大值為 16.目標(biāo)函數(shù)最優(yōu)值隨迭代次數(shù)變化如下圖：圖2.函數(shù)最大值隨迭代次數(shù)變化曲線可以看出，目標(biāo)函數(shù)值隨著迭代次數(shù)增加到8次即達(dá)到穩(wěn)定狀態(tài)，算法具有快速性和較強(qiáng)的全局尋優(yōu)能力。2.4下面對求解結(jié)果的準(zhǔn)確性進(jìn)行檢查在區(qū)間0,10上以

12、0.01的步長進(jìn)行搜索得到函數(shù)的最優(yōu)值；可得：x=0.32時函數(shù)取得最大值為ymax =16.5591隨著x值的變化，對應(yīng)的y值為：圖3.目標(biāo)函數(shù)隨x值的變化曲線顯然，采用遺傳算法得到的結(jié)果比定步長的結(jié)果更好，且運算次數(shù)更少，達(dá)到了大于0.01的目標(biāo)。2.5方法的推廣本方法通過映射關(guān)系使遺傳算法可以解決函數(shù)在浮點數(shù)范圍內(nèi)的函數(shù)最值問題，擴(kuò)展了遺傳算法的應(yīng)用范圍。此外，如果把一個個體的編碼劃分為幾節(jié)，分別對應(yīng)不同自變量的編碼，其余操作基本不變，則可以把遺傳算法推廣到多變量目標(biāo)函數(shù)在給定區(qū)間上的最值的求取，并在結(jié)果精度和求解時間上均有較大提高。附1、原程序代碼%參數(shù)的初始化,種群規(guī)模、染色體長度，

13、交叉和變異概率；種群迭代次數(shù)；popsize=10;chromlength=10;pc=0.5;pm=0.04;circle=30;maxindividual=zeros(1,circle);bestcode=zeros(circle,chromlength);%對問題進(jìn)行編碼initpop=round(rand(popsize,chromlength);pop=initpop;times=0;while timescircle%對問題解碼,即將2進(jìn)制轉(zhuǎn)化為10進(jìn)制；decimal=zeros(1,popsize);for ii=1:popsize for jj=1:chromlength d

14、ecimal(ii)=decimal(ii)+pop(ii,jj)*2.(chromlength-jj); end decimal(ii)=10*decimal(ii)/1023;end%計算個體的適應(yīng)度值；for i=1:popsize individual(i)=10*sin(5*decimal(i)+7*cos(decimal(i).2); if(individual(i)bdindividual(j) j=j+1; end newpop(i,:)=pop(j,:);end %個體間進(jìn)行交叉操作,pcps(交叉位置）；pop=newpop;for i=1:2:popsize rn2=ra

15、nd; if(rn2pc) pcps=round(chromlength*rn2); if(pcps=0) pcps=1; end newpop(i,pcps:chromlength)=pop(i+1,pcps:chromlength); newpop(i+1,pcps:chromlength)=pop(i,pcps:chromlength); endend%對種群進(jìn)行變異操作；for i=1:popsize for j=1:chromlength if(randpm) newpop(i,j)=1-newpop(i,j); end endendpop=newpop;times=times+1;endmaxall,index=max(maxindividual);allindex=bestcode(index,:);value=0; for jj=1:chromlength value=value+allindex(jj)*2.(chromlength-jj); end value=10*value/1023; fprintf(最佳編碼序列為：);disp(allindex);disp(n); fprintf(對應(yīng)x的取值為:%8.5fn,value); fprintf(第 %d 次迭代達(dá)到最大值n,index); fprintf(求得最