MATLAB遺傳算法在函數(shù)優(yōu)化問(wèn)題中的應(yīng)用

劉光亞

應(yīng)用研究

MATLAB遺傳算法在函數(shù)優(yōu)化問(wèn)題中的應(yīng)用

劉光亞

（武漢東湖學(xué)院機(jī)電學(xué)院，武漢 430212）

本文介紹了遺傳算法理論及運(yùn)算流程，運(yùn)用MATLAB語(yǔ)言進(jìn)行了程序設(shè)計(jì)。結(jié)合典型的三角測(cè)試函數(shù)，在MATLAB 環(huán)境下有效地解決了用遺傳算法求解函數(shù)優(yōu)化問(wèn)題，驗(yàn)證了 MATLAB 遺傳算法在函數(shù)優(yōu)化中應(yīng)用的有效性和靈活性。

遺傳算法 MATLAB 函數(shù)優(yōu)化 有效性

0 引言

20世紀(jì)70年代，美國(guó)密執(zhí)安大學(xué)的 Holland 教授[1]提出了遺傳算法，它包含了進(jìn)化和自然選擇原理，它借鑒了達(dá)爾文的進(jìn)化論和孟爾德的遺傳學(xué)，模仿了自然界的生物進(jìn)化機(jī)制，并發(fā)展成為一種隨機(jī)全局搜索和優(yōu)化方法，是一種全局、并行、高效的搜索方法[2]。它能在搜索過(guò)程中自主獲取和積累有關(guān)搜索空間的信息，并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解。遺傳算法提供了一種求解非線性、多模型、多目標(biāo)等復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題所屬的具體領(lǐng)域，已廣泛應(yīng)用于函數(shù)優(yōu)化、自動(dòng)控制、圖像處理、機(jī)器學(xué)習(xí)、人工生命與智能等領(lǐng)域[3]。

MATLAB是一種用于算法開(kāi)發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析及數(shù)值計(jì)算的高級(jí)技術(shù)計(jì)算語(yǔ)言和交互式環(huán)境，具有計(jì)算功能強(qiáng)大、圖形展示功能強(qiáng)大、工具箱功能強(qiáng)大和幫助功能完整等特點(diǎn)。MATLAB遺傳算法提供了對(duì)各種優(yōu)化問(wèn)題的一個(gè)完整的解決方案[4]。它具有函數(shù)表達(dá)簡(jiǎn)潔、遺傳操作靈活、可任意選擇多種編碼方式和優(yōu)化算子、算法參數(shù)設(shè)置自由等特點(diǎn)而受到用戶的青睞，并為應(yīng)用和研究遺傳算法提供了穩(wěn)定可靠、結(jié)構(gòu)靈活、可擴(kuò)展的開(kāi)發(fā)平臺(tái)。

函數(shù)優(yōu)化問(wèn)題是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例[5]。

1 遺傳算法原理與運(yùn)算流程

在自然進(jìn)化的過(guò)程中，生物通過(guò)遺傳與變異來(lái)適應(yīng)外部環(huán)境。這就意味著，只有那些擁有更加優(yōu)良特性和更適應(yīng)自然環(huán)境的生物才能生存與繁衍；同時(shí)，那些沒(méi)有優(yōu)良特性的生物體最終將會(huì)消亡。這也就是所謂的“適者生存”。遺傳算法模擬了上述的自然進(jìn)化現(xiàn)象，它將搜索空間映射到遺傳空間，也就是說(shuō)將每個(gè)有可能的解經(jīng)基因編碼成一個(gè)染色體。

遺傳算法模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，隨機(jī)產(chǎn)生一初始種群，通過(guò)復(fù)制、交叉、變異等操作，產(chǎn)生適應(yīng)度更高的個(gè)體，使群體進(jìn)行到搜索空間中越來(lái)越好的區(qū)域，如此一代代進(jìn)化，最后收斂到一群適應(yīng)度最好的個(gè)體中，進(jìn)而求得問(wèn)題的最優(yōu)解。

遺傳算法流程可用圖1來(lái)描述：

圖1 遺傳算法流程圖

2 應(yīng)用實(shí)例

示例函數(shù)采用典型的如下三角測(cè)試函數(shù)：

求其函數(shù)于自變量x在定義域中的最大值，遺傳算法優(yōu)化程序[6]如下：

Function optvalue=opt(n, maxgen, xmin, xmax, pc_min, pc_max,pm_min, pm_max, l) % n-染色體規(guī)模；maxgen-最大進(jìn)化代數(shù)；xmin-自變量最小值；xmax-自變量最大值；pc_min-最小交叉概率；pc_max-最大交叉概率；pm_min-最小突變概率； pm_max-最大突變概率；l-二進(jìn)制碼串長(zhǎng)度；

gen=1;group=round(rand(n,l));

while gen<=maxgen % 判斷終止條件

x=decode(group,xmin,xmax,l);

fit=x.^2.*sin(2*x)+2*cos(5*x)+x; % 求適應(yīng)度值

for i=1:n % 適應(yīng)度值預(yù)處理

if fit(i)<0

fit(i)=0;

end

end

prob1=fit/sum(fit);prob1=cumsum(prob1);

prob2=sort(rand(n,1)); i=1;j=1;

while i<=n %利用輪盤(pán)賭選擇法來(lái)進(jìn)行選擇操作

if prob2(i)

newgroup(i,:)=group(j,:); i=i+1;

else

j=j+1;

end

end

group=newgroup; x=decode(group,xmin,xmax,l);

fit=x.^2.*sin(2*x)+2*cos(5*x)+x; avgfit=mean(fit);

for i=1:2:n-1 %隨機(jī)生成交叉點(diǎn)，并進(jìn)行交叉操作

a=[fit(i) fit(i+1)];

if max(a)>avgfit

pc=pc_max-(pc_max-pc_min)*gen/maxgen;

else

pc=pc_max;

end

if rand

cross=round(rand*l)+1;

if cross>l

cross=cross-1;

end

newgroup(i,:)=[group(i,1:cross) ;

group(i+1,cross+1:end)];

newgroup(i+1,:)=[group(i+1,1:cross); group(i,cross+1:end)];

x2=decode(newgroup(i:i+1,:),xmin,xmax,l);

fit2=x2.^2.*sin(2*x2)+2*cos(5*x2)+x2;

for j=0:1

if fit(i+j)>=fit2(j+1)

newgroup(i+j,:)=group(i+j,:);

end

end

else

newgroup(i,:)=group(i,:);

newgroup(i+1,:)=group(i+1,:);

end

end

group=newgroup;

for i=1:n % 隨機(jī)生成變異點(diǎn)，并進(jìn)行變異操作

x3=decode(group,xmin,xmax,l);

fit3=x3.^2.*sin(2*x3)+2*cos(5*x3)+x3;

avgfit3=mean(fit3);

if fit3(i)>avgfit3

pm=pm_max-(pm_max-pm_min)*gen/maxgen;

else

pm=pm_min;

end

if rand

mutation=round(rand*l)+1;

if mutation>l

mutation=mutation-1;

end

newgroup(i,:)=group(i,:);

if newgroup(i,mutation)==0

newgroup(i,mutation)=1;

else

newgroup(i,mutation)=0;

end

x4=decode(newgroup(i,:),xmin,xmax,l);

fit4=x4.^2.*sin(2*x4)+2*cos(5*x4)+x4;

if fit3(i)>fit4

newgroup(i,:)=group(i,:);

end

else

newgroup(i,:)=group(i,:);

end

end

x=decode(newgroup,xmin,xmax,l);

fit=x.^2.*sin(2*x)+2*cos(5*x)+x;

[gmax(gen) index]=max(fit);r(gen)=x(index);

meanvalue=mean(fit);meanfit(gen)=meanvalue; group=newgroup;gen=gen+1;

end

figure(1);fplot('x.^2.*sin(2*x)+2*cos(5*x)+x',[xmin,xmax]);

hold on; plot(r,gmax,'r*');xlabel('x');ylabel('f(x)')

figure(2); plot(gmax); hold on; plot(meanfit,'r:');

xlabel('generations');ylabel('f(x)');hold off;

[gmax index]=max(gmax); optvalue=[r(index) gmax];

Function x=decode(group, xmin, xmax, l) %子函數(shù)實(shí)現(xiàn)二進(jìn)制-十進(jìn)制的解碼操作

group=fliplr(group);s=size(group);

a=0:1:l-1;a=ones(s(1),1)*a;

x1=sum((group.*2.^a)'); x=xmin+(xmax-xmin)*x1./2^l-1;

3 仿真結(jié)果

按照上述算法，令n=50，maxgen=80，x_min=0，x_max=9，pc_min=0.1，pc_max=0.9，pm_min=0.01，pm_max=0.4，l=22；圖2代表了初始種群的位置分布；圖3指出了經(jīng)過(guò)80次迭代后的最終尋優(yōu)結(jié)果；圖4說(shuō)明了隨著代數(shù)的增長(zhǎng)，最優(yōu)值與平均函數(shù)值的變化趨勢(shì)；輸出結(jié)果為：

X=7.1928，y=57.0137.

4 結(jié)語(yǔ)

遺傳算法作為一種快速、簡(jiǎn)單、容錯(cuò)性強(qiáng)的算法，是一類可應(yīng)用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的魯棒搜索算法，相較于傳統(tǒng)優(yōu)化算法，它有如下特點(diǎn)：

1）遺傳算法不是從一點(diǎn)出發(fā)沿一條直線尋優(yōu)，而是同時(shí)在整個(gè)解空間進(jìn)行尋優(yōu)操作，具備全局尋優(yōu)能力。

2）遺傳算法直接作用于變量的編碼上，而非變量本身。通過(guò)編碼操作，可以直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。

3）遺傳算法對(duì)搜索空間沒(méi)有任何特殊要求，只以變量的編碼作為操作對(duì)象，無(wú)需導(dǎo)數(shù)等其它輔助信息，可處理無(wú)數(shù)值概念或者很難有數(shù)值概念的優(yōu)化問(wèn)題。

圖2 染色體的初始位置

4）本文實(shí)驗(yàn)結(jié)果驗(yàn)證了 MATLAB 遺傳算法能有效、靈活地求解復(fù)雜函數(shù)的優(yōu)化問(wèn)題，而且所求解能達(dá)到或以相當(dāng)高的精度逼近最優(yōu)解。

圖3 染色體的最終位置

圖4 最優(yōu)、平均函數(shù)值變化趨勢(shì)

[1] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Ann Arbor: University of Michigan Press, 1975.

[2] Rodés J P, Pérez-Gracia V, Martínez-Reguero A.Evaluation of the GPR frequency spectra in asphalt pavement assessment[J]. Constr Build Mater, 2015, 96: 181-188.

[3] 周勇, 胡中功. 改進(jìn)的快速遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J]. 現(xiàn)代電子技術(shù), 2018, 41(17): 153-157.

[4] 殷銘, 張興華, 戴先中. 基于MATLAB的遺傳算法實(shí)現(xiàn)[J]. 電子技術(shù)應(yīng)用, 2000, 26(1): 9-11.

[5] 曹巖. MATLAB R2008數(shù)學(xué)和控制實(shí)例教程[M]. 北京: 化學(xué)工業(yè)出版社, 2009.

[6] 由睿鵬.計(jì)算機(jī)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中遺傳算法的原理及應(yīng)用[J]. 電子技術(shù)與軟件工程, 2020(20): 14-15.

[7] 李曉葉, 張京麗, 于妍. 動(dòng)態(tài)圖表展現(xiàn)遺傳算法基本原理[J]. 電腦編程技巧與維護(hù), 2017(12): 80-81, 94.

[8] 萬(wàn)勇, 萬(wàn)莉, 戴永壽. 基于C與MATLAB混合編程的管道缺陷類型識(shí)別實(shí)驗(yàn)系統(tǒng)軟件開(kāi)發(fā)[J]. 實(shí)驗(yàn)技術(shù)與管理, 2020, 37(5): 52-57.

Application of MATLAB genetic algorithm in the function optimization problem

Liu Yaguang

(School of Mechanical and Electronic, Wuhan Donghu University, Wuhan 430212, China)

TP18

A

1003-4862（2022）12-0050-04

2022-08-09

國(guó)家自然科學(xué)基金資助項(xiàng)目（12101468、61573002）

劉光亞（1959-），男，工學(xué)博士，研究員級(jí)高工、教授（二級(jí)）。研究方向：檢測(cè)技術(shù)及自動(dòng)化系統(tǒng)，動(dòng)力（核）與電氣工程。E-mail：648069538@qq.com