第八章-優(yōu)化問(wèn)題

第八章優(yōu)化問(wèn)題1/17/20251MATLAB優(yōu)化問(wèn)題優(yōu)化工具箱概述無(wú)約束最優(yōu)化問(wèn)題有約束最優(yōu)化問(wèn)題多目標(biāo)規(guī)劃最大最小化遺傳算法（GA）模擬退火算法（SA）例：travel-->travelsalesmanproblem

旅行商問(wèn)題——一個(gè)典型的優(yōu)化問(wèn)題1/17/20252一、優(yōu)化工具箱概述在生活和工作中，人們對(duì)于同一個(gè)問(wèn)題往往會(huì)提出多個(gè)解決方案，并通過(guò)各方向的論證從中提取最佳方案。最優(yōu)化方法就是專門研究如何從多個(gè)方案中科學(xué)合理地提取出最佳方案的科學(xué)。優(yōu)化問(wèn)題無(wú)所不在，最優(yōu)化方法的應(yīng)用和研究已經(jīng)深入到生產(chǎn)和科研的各個(gè)領(lǐng)域，如土木、機(jī)械、化工、運(yùn)輸調(diào)度、生產(chǎn)控制、經(jīng)濟(jì)規(guī)劃、管理等，并取得了顯著的經(jīng)濟(jì)效益和社會(huì)效益；用最優(yōu)化方法解決最優(yōu)化問(wèn)題的技術(shù)稱為最優(yōu)化技術(shù)，包含：（1）建立數(shù)學(xué)模型：即用數(shù)學(xué)語(yǔ)言來(lái)描述最優(yōu)化問(wèn)題，模型中的數(shù)學(xué)關(guān)系式反映了最優(yōu)化問(wèn)題所要達(dá)到的目標(biāo)和各種約束條件。（2）數(shù)學(xué)求解數(shù)學(xué)模型建好以后，選擇合理的最優(yōu)化方法進(jìn)行求解。1/17/20253最優(yōu)化方法的發(fā)展很快，已經(jīng)包含有多個(gè)分支，如線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃等；利用MATLAB的優(yōu)化工具箱，可以求解線性規(guī)劃、非線性規(guī)劃和多目標(biāo)規(guī)劃問(wèn)題。包括線性、非線性最小化，最大最小化，二次規(guī)劃，半無(wú)限問(wèn)題，線性、非線性方程組的求解，線性、非線性的最小二乘問(wèn)題，另外，該工具箱還提供了線性、非線性最小化，方程求解、曲線擬合，二次規(guī)劃等問(wèn)題中大型課題的求解方法，為優(yōu)化方法在工程中的實(shí)際應(yīng)用提供了更方便、快捷的途徑。1/17/20254二、無(wú)約束最優(yōu)化問(wèn)題1.單變量最優(yōu)化討論只有一個(gè)變量的最小化問(wèn)題，即一維搜索問(wèn)題，該問(wèn)題在某些情況下可以直接用于求解實(shí)際問(wèn)題，但大多數(shù)情況下它是作為多變量最優(yōu)化方法的基礎(chǔ)，因?yàn)檫M(jìn)行多變量最優(yōu)化要用到一維搜索算法。該問(wèn)題的數(shù)學(xué)模型為

minf(x)x1<x<x21/17/20255Rosenbrock函數(shù)（香蕉函數(shù)）最小值為：x=[1，1]；f（x）=0觀察：在命令窗口鍵入bandemo選擇不同方法觀察對(duì)香蕉函數(shù)的優(yōu)化結(jié)果和過(guò)程。1/17/20256fminbnd

函數(shù)：利用該函數(shù)找到固定區(qū)間內(nèi)單變量函數(shù)的最小值；調(diào)用格式為：

fminbnd(‘f’,x1，x2)返回區(qū)間(x1，x2)上f函數(shù)描述的標(biāo)量函數(shù)的最小值x。注意：

1）目標(biāo)函數(shù)必須是連續(xù)的；

2）fminbnd函數(shù)可能只給出局部最優(yōu)解；

3）只用于實(shí)數(shù)變量。1/17/20257[例]

在區(qū)間（0，2π）上求函數(shù)sin(x)的最小值：x=fminbnd(@sin,0,2*pi)x=4.7124

所以區(qū)間（0，2π）上函數(shù)sin(x)的最小值點(diǎn)位于x=4.7124處。最小值處的函數(shù)值為：y=sin(x)y=-1.00001/17/202582.無(wú)約束非線性規(guī)劃問(wèn)題基本數(shù)學(xué)原理無(wú)約束最優(yōu)化問(wèn)題在實(shí)際應(yīng)用中較為常見(jiàn)。許多有約束最優(yōu)化問(wèn)題可以轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題進(jìn)行求解；求解無(wú)約束最優(yōu)化問(wèn)題的方法主要有兩類：直接搜索法（DirectSearchMethod）梯度法（GradientMethod）。直接搜索法適用于目標(biāo)函數(shù)高度非線性，沒(méi)有導(dǎo)數(shù)或?qū)?shù)很難計(jì)算的情況；由于實(shí)際工程中很多問(wèn)題都是非線性的，故直接搜索法不失為一種有效的解決辦法，常用的直接搜索法為單純形法等，其缺點(diǎn)是收斂速度慢。1/17/20259（1）fminunc函數(shù)可求多變量無(wú)約束函數(shù)的最小值。多變量無(wú)約束函數(shù)的數(shù)學(xué)模型為式中，x為矢量，f(x)為函數(shù)，返回標(biāo)量；

fminunc函數(shù)的調(diào)用格式：

fminunc（fun，x0），x0為給定初值，可以是標(biāo)量、矢量或矩陣。1/17/202510例：將下列函數(shù)最小化建立m文件：myfun.mfunctionf=myfun(x)f=3*x(1)^2+2*x(1)*x(2)+x(2)^2然后：x0=[1,1];[x,fval]=fminunc('myfun',x0)%[x,fval]=fminunc(@myfun,x0)%函數(shù)句柄16次迭代后，x=1.0e-008*-0.75120.2479fval=1.3818e-0161/17/202511（2）fminsearch函數(shù)，功能類似于fminunc函數(shù)x0=[1,1];[x,fval]=fminsearch('myfun',x0)%[x,fval]=fminsearch(@myfun,x0)%函數(shù)句柄1/17/202512三、有約束優(yōu)化問(wèn)題線性規(guī)劃有約束極小問(wèn)題非線性有約束最優(yōu)化問(wèn)題1/17/2025131.線性規(guī)劃概述線性規(guī)劃的廣泛應(yīng)用是計(jì)算機(jī)時(shí)代的產(chǎn)物。1902年，J.Farkas

發(fā)表論文，闡述有關(guān)線性規(guī)劃問(wèn)題。1938年，英國(guó)人康德進(jìn)行較詳細(xì)研究。1947年，美國(guó)學(xué)者G.Dantzig（丹茨格）發(fā)明了求解線性規(guī)劃的單純形法（1951年發(fā)表），從而為線性規(guī)劃的推廣奠定了基礎(chǔ)?？梢哉J(rèn)為，求解線性規(guī)劃的單純形算法可與求解線性方程組的高斯消元法相媲美。1/17/202514線性規(guī)劃的數(shù)學(xué)模型有三個(gè)要素，從實(shí)際問(wèn)題提煉成數(shù)學(xué)模型時(shí)，首先尋找需求解的未知量xj(j=1,…,n)，然后列舉三要素：

列寫(xiě)與自變量（未知量）有關(guān)的若干個(gè)線性約束條件（等式或不等式）。列寫(xiě)自變量xj取值限制（xj≥0，xj≤0或不限）。列寫(xiě)關(guān)于自變量的線性目標(biāo)函數(shù)值（極大值或極小值）。其中，前兩條稱為可行條件，最后一條稱為優(yōu)化條件。符合這三個(gè)條件的數(shù)學(xué)模型通常稱為線性規(guī)劃的一般型（general）。1/17/202515問(wèn)題的提出例：某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，該兩種產(chǎn)品均需經(jīng)A、B、C、D四種不同設(shè)備上加工，按生產(chǎn)工藝，在各種不同設(shè)備上的加工時(shí)間及設(shè)備加工能力、單位產(chǎn)品利潤(rùn)如表中所示。問(wèn)：如何安排產(chǎn)品的生產(chǎn)計(jì)劃，才能使企業(yè)獲利最大?

一般線性規(guī)劃問(wèn)題及數(shù)學(xué)模型1/17/202516建立模型：設(shè)產(chǎn)品的產(chǎn)量甲

x1件，乙

x2件，則Max z=2x1+3x2

2x1+2x212 x1+2x284

x116 4

x2

12x10，

x20目標(biāo)(object)：限制條件(subjectto)：1/17/202517線性規(guī)劃有約束極小問(wèn)題

用命令x=linprog(C,A,b,Aeq,beq,lb)例：求x使f(x)最小

f(x)=-5x1-4x2-6x3約束條件：

x1-x2+x3≦203x1+2x2+4x3≦423x1+2x2≦300≦x1,0≦x2,0≦x31/17/202518Matlab程序：clearC=[-5;-4;-6];A=[1-11;324;320];b=[20;42;30];lb=zeros(3,1);linprog(C,A,b,[],[],lb)輸出結(jié)果：x=0.000015.00003.00001/17/2025192．非線性規(guī)劃有約束極小問(wèn)題

用命令x=fmincon

(‘f’,x0,A,b)早期版本用constr(‘f’,x0)，只針對(duì)不等式約束。例：求f(x)=-x1x2x3的最小值，x0=[10;10;10]

s.t.-x1-2x2-2x3≤0,x1+2x2+2x3≤72,1/17/202520建立m文件：functionf=myfun1(x)f=-x(1)*x(2)*x(3);MATLAB程序：

x0=[10,10,10];A=[-1-2-2;122];b=[0;72];x=fmincon('myfun1',x0,A,b)輸出結(jié)果：x=24.000012.000012.00001/17/202521四、二次規(guī)劃如果某非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，約束條件全是線性函數(shù)，就稱這種規(guī)劃為二次規(guī)劃。其數(shù)學(xué)模型為：1/17/202522用quadprog(H,f,A,b,Aeq,beq,lb)若無(wú)等式約束條件，則采用

quadprog(H,f,A,b)例：1/17/202523目標(biāo)函數(shù)寫(xiě)成矩陣形式：MATLAB程序：clearH=[1-1;-12];f=[-2;-6];A=[11;-12;21];b=[2;2;3];lb=zeros(2,1);[x,fval,exitflag]=quadprog(H,f,A,b,[],[],lb)1/17/202524五、多目標(biāo)規(guī)劃前面介紹的最優(yōu)化方法只有一個(gè)目標(biāo)函數(shù)，是單目標(biāo)最優(yōu)化方法。但是，在許多實(shí)際工程問(wèn)題中，往往希望多個(gè)指標(biāo)都達(dá)到最優(yōu)值，所以就有多個(gè)目標(biāo)函數(shù)，這種問(wèn)題稱為多目標(biāo)最優(yōu)化問(wèn)題。數(shù)學(xué)模型為式中，F(xiàn)(x)為目標(biāo)函數(shù)矢量。1/17/202525由于多目標(biāo)最優(yōu)化問(wèn)題中各目標(biāo)函數(shù)之間往往是不可公度的，往往沒(méi)有唯一解，此時(shí)須引進(jìn)非劣解的概念(非劣解又稱為有效解或帕累托解）。定義：若x*（x*∈Ω）的鄰城內(nèi)不存在Δx，使得（x*+Δx

）∈Ω，且則稱x*為非劣解。

1/17/202526多目標(biāo)規(guī)劃有許多解法，常用的有：1．權(quán)和法該法將多目標(biāo)矢量問(wèn)題轉(zhuǎn)化為所有目標(biāo)的加權(quán)求和的標(biāo)量問(wèn)題，即加權(quán)因子的選取方法很多，有專家打分法等。該問(wèn)題可以用標(biāo)準(zhǔn)的無(wú)約束最優(yōu)化算法進(jìn)行求解。1/17/2025272．ε約束法對(duì)目標(biāo)函數(shù)矢量中的主要目標(biāo)函數(shù)Fp進(jìn)行最小化，其它目標(biāo)用不等式約束的形式，即1/17/2025283．目標(biāo)達(dá)到法目標(biāo)函數(shù)系列為對(duì)應(yīng)地有其目標(biāo)值系列允許目標(biāo)函數(shù)有正負(fù)偏差，偏差的大小由加權(quán)系數(shù)矢量ω={ω1,ω2,…,ωm

}控制，問(wèn)題可以表達(dá)為標(biāo)準(zhǔn)的最優(yōu)化問(wèn)題1/17/202529應(yīng)用實(shí)例某化工廠擬生產(chǎn)兩種新產(chǎn)品A和B，其生產(chǎn)設(shè)備投資分別為：A，2萬(wàn)元／噸；B，5萬(wàn)元／噸。這兩種產(chǎn)品均會(huì)造成環(huán)境污染，設(shè)由公害所造成的損失可折算為：A，4萬(wàn)元／噸；B，1萬(wàn)元／噸。由于條件限制，工廠生產(chǎn)產(chǎn)品A和B的最大生產(chǎn)能力各為每月5噸和6噸，而市場(chǎng)需要這兩種產(chǎn)品的總量每月不少于7噸。試問(wèn)工廠如何安排生產(chǎn)計(jì)劃，在滿足市場(chǎng)需要的前提下，使設(shè)備投資和公害損失均達(dá)最小。工廠決策認(rèn)為：這兩個(gè)目標(biāo)中環(huán)境污染應(yīng)優(yōu)先考慮，設(shè)備投資的目標(biāo)值為20萬(wàn)元，公害損失的目標(biāo)為12萬(wàn)元。1/17/202530設(shè)工廠每月生產(chǎn)產(chǎn)品A為x1噸，B為x2噸，設(shè)備投資費(fèi)為f1(x)，公害損失費(fèi)為f2(x)，則這個(gè)問(wèn)題可表達(dá)為多目標(biāo)優(yōu)化問(wèn)題：1/17/202531首先需要編寫(xiě)目標(biāo)函數(shù)的M文件opt1.m，返回目標(biāo)計(jì)算值

functionf=opt1(x)f(1)=2*x(1)+5*x(2);f(2)=4*x(1)+x(2);給定目標(biāo)，權(quán)重按目標(biāo)比例確定，給出初值

goal=[2012];weight=[2012];x0=[25];%給出約束條件的系數(shù)

A=[10;01;-1-1];b=[56-7];lb=zeros(2,1);[x,fval,attainfactor,exitflag]=...fgoalattain(@opt1,x0,goal,weight,A,b,[],[],lb,[])1/17/202532六、最大最小化通常我們遇到的都是目標(biāo)函數(shù)的最大化和最小化問(wèn)題，但是在某些情況下，則要求使最大值最小化才有意義。例如城市規(guī)劃中需要確定急救中心、消防中心的位置，可取的目標(biāo)函數(shù)應(yīng)該是到所有地點(diǎn)最大距離的最小值，而不是到所有目的地的距離和為最小。這是兩種完全不同的準(zhǔn)則，在控制理論、逼近論、決策論中也使用最大最小化原則。1/17/202533最大最小化問(wèn)題的數(shù)學(xué)模型為式中，x,b,beq,lb,andub為矢量，

A、Aeq為矩陣，c(x),ceq(x),F(x)為函數(shù)，返回矢量。F(x),c(x),ceq(x)可以是非線性函數(shù)。MATLAB優(yōu)化工具箱中采用序列二次規(guī)劃法求解最大最小化問(wèn)題。1/17/202534[例]求解下列最優(yōu)化問(wèn)題，使下面各目標(biāo)函數(shù)中的最大值最?。菏紫染帉?xiě)一個(gè)計(jì)算x處五個(gè)函數(shù)的M文件opt2.m。functionf=opt2(x)f(1)=2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304;f(2)=-x(1)^2-3*x(2)^2;f(3)=x(1)+3*x(2)-18;f(4)=-x(1)-x(2);f(5)=x(1)+x(2)-8;然后調(diào)用優(yōu)化過(guò)程：x0=[0.1;0.1];%初值[x,fval]=fminimax(@opt2,x0)得到問(wèn)題的解x=4.00004.0000fval=0.0000-64.0000-2.0000-8.0000-0.00001/17/202535例：定位問(wèn)題：設(shè)某城市有某種物品的10個(gè)需求點(diǎn)，第i個(gè)需求點(diǎn)Pi的坐標(biāo)為(ai，bi)，道路網(wǎng)與坐標(biāo)軸平行，彼此正交。現(xiàn)打算建一個(gè)該物品的供應(yīng)中心，且由于受到城市某些條件的限制，該供應(yīng)中心只能設(shè)在x界于[5，8]，y界于[5，8]的范圍內(nèi)。問(wèn)該中心應(yīng)建在何處為好?

Pi點(diǎn)的坐標(biāo)為ai：1435912620178

bi：2108181451089該供應(yīng)中心的位置為（x，y），要求它到最遠(yuǎn)需求點(diǎn)的距離盡可能小。由于此處應(yīng)采用沿道路行走的距離，可知用戶Pi到該中心的距離為|x－ai|+|y－bi|，從而可得目標(biāo)函數(shù)

1/17/202536首先,編寫(xiě)一個(gè)計(jì)算x處10個(gè)目標(biāo)函數(shù)的M文件opt3.m；functionf=opt3(x)a=[1435912620178];b=[2108181451089];

%輸入各個(gè)點(diǎn)的坐標(biāo)值f(1)=abs(x(1)-a(1))+abs(x(2)-b(1));f(2)=abs(x(1)-a(2))+abs(x(2)-b(2));f(3)=abs(x(1)-a(3))+abs(x(2)-b(3));f(4)=abs(x(1)-a(4))+abs(x(2)-b(4));f(5)=abs(x(1)-a(5))+abs(x(2)-b(5));f(6)=abs(x(1)-a(6))+abs(x(2)-b(6));f(7)=abs(x(1)-a(7))+abs(x(2)-b(7));f(8)=abs(x(1)-a(8))+abs(x(2)-b(8));f(9)=abs(x(1)-a(9))+abs(x(2)-b(9));f(10)=abs(x(1)-a(10))+abs(x(2)-b(10));clear;x0=[6;6];%初值A(chǔ)A=[-10;10;0-1;01];bb=[-5;8;-5;8];%約束條件的系數(shù)[x,fval]=fminimax(@opt2,x0,AA,bb)運(yùn)行結(jié)果：

x=88fval=13651388514911/17/202537七、遺傳算法（GA）生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過(guò)程，它通過(guò)選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。1967年Bagley最早提出遺傳算法的概念；1975年Michigan大學(xué)的J.H.Holland開(kāi)始遺傳算法的理論和方法的系統(tǒng)性、開(kāi)創(chuàng)性研究。遺傳算法簡(jiǎn)稱GA(GeneticAlgorithm)，在本質(zhì)上是一種不依賴具體問(wèn)題的直接搜索方法。遺傳算法在模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、結(jié)構(gòu)優(yōu)化、自適應(yīng)控制、生物科學(xué)、社會(huì)科學(xué)等方面都得到應(yīng)用。在人工智能研究中，現(xiàn)在人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與人工智能一樣，都是對(duì)今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”。1/17/2025381．遺傳算法的基本概念遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說(shuō)的。Darwin進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來(lái)越適應(yīng)環(huán)境。物種每個(gè)個(gè)體的基本特征由后代所繼承，但后代又會(huì)產(chǎn)生一些異于父代的新變化。在環(huán)境變化時(shí)，只有那些能適應(yīng)環(huán)境的個(gè)體特征方能保留下來(lái)。Mendel遺傳學(xué)說(shuō)最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性?；蛲蛔兒突螂s交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過(guò)存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來(lái)。1/17/202539由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法，因而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念。這些概念如下：（1）串(String)

它是個(gè)體(Individual)的形式，在算法中為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體(Chromosome)。（2）群體(Population)

個(gè)體的集合稱為群體，串是群體的元素（3）群體大小(PopulationSize)

在群體中個(gè)體的數(shù)量稱為群體的大小。（4）基因(Gene)

基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S＝1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因(Alletes)。1/17/202540（5）基因位置(GenePosition)——一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡(jiǎn)稱基因位?；蛭恢糜纱淖笙蛴矣?jì)算，例如在串S＝1101中，0的基因位置是3?；蛭恢脤?duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus)。（6）基因特征值(GeneFeature)——在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。（7）串結(jié)構(gòu)空間SS——在串中，基因任意組合所構(gòu)成的串的集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對(duì)應(yīng)于遺傳學(xué)中的基因型(Genotype)的集合。（8）參數(shù)空間SP——這是串空間在物理系統(tǒng)中的映射，它對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型(Phenotype)的集合。（9）非線性——它對(duì)應(yīng)遺傳學(xué)中的異位顯性(Epistasis)（10）適應(yīng)度(Fitness)——表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度。1/17/2025412．遺傳算法的原理遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問(wèn)題的最優(yōu)解。（1）遺傳算法的目的典型的遺傳算法通常用于解決下面這一類的靜態(tài)最優(yōu)化問(wèn)題：考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼xi，i＝1，2，…，n；有xi∈{0,1}L；給定目標(biāo)函數(shù)f，有f(xi)，并且0<f(xi)<∞；同時(shí)f(xi)≠f(xi+1)

求滿足：max{f(xi)|xi∈{0,1}L}

的xi

。顯然，遺傳算法是一種最優(yōu)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串xi處，即求出最優(yōu)解。1/17/202542（2）遺傳算法的基本原理長(zhǎng)度為L(zhǎng)的n個(gè)二進(jìn)制串xi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。根據(jù)進(jìn)化術(shù)語(yǔ)，對(duì)群體執(zhí)行的操作有三種：1．選擇(Selection)

這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differentialreproduction)。2．交叉(Crossover)

這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。3．變異(Mutation)

這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串xi中，如果某位基因?yàn)?，產(chǎn)生變異時(shí)就是把它變成0；反亦反之。1/17/202543（3）遺傳算法的步驟和意義a．初始化選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合x(chóng)i，i=1，2，...n。這個(gè)初始的群體也就是問(wèn)題假設(shè)解的集合。一般取n＝30~160。通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合x(chóng)i,i＝1，2，...n。問(wèn)題的最優(yōu)解將通過(guò)這些初始假設(shè)解進(jìn)化而求出。b．選擇根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。給出目標(biāo)函數(shù)f，則f(xi)稱為個(gè)體xi的適應(yīng)度。顯然：(i)適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。

(ii)適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問(wèn)題求解角度來(lái)講，就是選擇出和最優(yōu)解較接近的中間解。1/17/202544c．交叉

對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。例如有個(gè)體S1=100101，選擇左邊3位進(jìn)行交叉操作，則S1=010101S2=010111S2=100111

一般而言，交叉概率P常取為0.25—0.75。d．變異根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm一般取值較小，一般取0.01-0.2。例如有個(gè)體S=101011，對(duì)其的第1，4位置的基因進(jìn)行變異，則有

S'=001111單靠變異不能在求解中得到好處。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。1/17/202545e．全局最優(yōu)收斂當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過(guò)程收斂、算法結(jié)束。否則，用經(jīng)過(guò)選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。1/17/202546簡(jiǎn)單遺傳算法框圖1/17/2025473．遺傳算法的手工計(jì)算示例考慮下列一元函數(shù)求最大值的優(yōu)化問(wèn)題：極值點(diǎn)滿足：1/17/202548下面用遺傳算法求解上述簡(jiǎn)單優(yōu)化問(wèn)題：（1）編碼變量x作為實(shí)數(shù)，可視為遺傳算法的表現(xiàn)型形式，從表現(xiàn)型到基因型的映射稱為編碼。通常用二進(jìn)制串編碼形式，串長(zhǎng)度取決于求解精度。若需要達(dá)到6位小數(shù)，則需將區(qū)間[-1，2]分為3×106等份，因?yàn)?/p>

2097152=221<3×106

≤222=4194304所以二進(jìn)制串長(zhǎng)度需要22位

1/17/202549將一個(gè)22位二進(jìn)制串（b21b20…b0）化為十進(jìn)制數(shù)在區(qū)間[-1，2]內(nèi)，x’對(duì)應(yīng)的實(shí)數(shù)為：例：二進(jìn)制串s1=<1000101110110101000111>

表示實(shí)數(shù)0.637197

x’=（1000101110110101000111）2=2288967

二進(jìn)制串<0000000000000000000000>和<1111111111111111111111>

表示區(qū)間[-1，2]的兩個(gè)端點(diǎn)值1/17/202550（2）產(chǎn)生初始種群一個(gè)個(gè)體由串長(zhǎng)為22的隨機(jī)產(chǎn)生的二進(jìn)制串組成染色體的基因碼，可以產(chǎn)生一定數(shù)目的個(gè)體組成種群，種群的大小就是群中的個(gè)體數(shù)目；（3）計(jì)算適應(yīng)度直接引用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)：

f(s)=f(x)

如：s1=<1000101110110101000111>s2=<0000001110000000010000>f(s1)=f(x1)=2.586345f(s2)=f(x2)=1.078878顯然，兩個(gè)個(gè)體中，s1的適應(yīng)度大，個(gè)體s1優(yōu)于個(gè)體s21/17/202551

(4)遺傳操作介紹交叉和變異這兩個(gè)遺傳操作的工作過(guò)程：下面是經(jīng)過(guò)選擇操作(輪盤(pán)賭選擇方法)的兩個(gè)個(gè)體，先執(zhí)行單點(diǎn)交叉，如

s1=<00000|01110000000010000>s2=<11100|00000111111000101>隨機(jī)選擇一個(gè)交叉點(diǎn)，例如第5位與第6位之間的位置，交叉后產(chǎn)生新的子個(gè)體

s1’=<00000|00000111111000101>s2’=<11100|01110000000010000>

這兩個(gè)子個(gè)體的適應(yīng)度分別為：

f(s1’)=f(-0.998113)=1.940865f(s2’)=f(1.666028)=3.459245適應(yīng)度高于兩個(gè)父?jìng)€(gè)體的適應(yīng)度1/17/202552下面考察變異操作：假設(shè)以一小概率選擇了s2的第5個(gè)遺傳因子(即第5位)變異，遺傳因子由原來(lái)的0變?yōu)?，產(chǎn)生新的個(gè)體為

s2’’=<1110100000111111000101>

計(jì)算該個(gè)體的適應(yīng)度：

f(s2’’)=f(1.721638)=0.917743發(fā)現(xiàn)個(gè)體s2’’的適應(yīng)度比其父?jìng)€(gè)體的適應(yīng)度減少了，但如果選擇第10個(gè)遺傳因子變異，產(chǎn)生新的個(gè)體為：

s2’’’=<1110100001111111000101>適應(yīng)度：f(s2’’’)=f(1.630818)=3.343555個(gè)體s2’’’的適應(yīng)度比其父?jìng)€(gè)體的適應(yīng)度改善了，這說(shuō)明了變異操作的”擾動(dòng)”作用。1/17/202553(5)模擬結(jié)果設(shè)定種群大小為50，交叉概率為0.25，變異概率為0.01，按照上述基本遺傳算法（SGA），在運(yùn)行到89代時(shí)獲得最佳個(gè)體：

smax=<1101001111110011001111>

xmax=1.850549，

f（xmax）=3.850274這個(gè)個(gè)體對(duì)應(yīng)的解與其它方法預(yù)計(jì)最優(yōu)解的情況吻合，可以作為問(wèn)題的近似最優(yōu)解。1/17/2025544．Matlab遺傳算法與直接搜索工具箱

（TheGeneticAlgorithmandDirectSearchToolbox）%定義一個(gè)簡(jiǎn)單的適應(yīng)度函數(shù)，即目標(biāo)函數(shù)functiony=simple_fitness(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2;%開(kāi)始搜索clearFitnessFunction=@simple_fitness;numberOfVariables=2;[x,fval]=ga(FitnessFunction,numberOfVariables)1/17/202555%定義simple_objective.m

functiony=simple_objective(x)y=(4-2.1*x(1)^2+x(1)^4/3)*x(1)^2+x(1)*x(2)+...(-4+4*x(2)^2)*x(2)^2;%開(kāi)始搜索ObjectiveFunction=@simple_objective;X0=[0.50.5];%Startingpoint[x,fval]=patternsearch(ObjectiveFunction,X0)1/17/202556八、模擬退火算法（SA）模擬退火算法工具箱

satools

模擬退火算法（SimulatedAnnealingAlgorithm，簡(jiǎn)稱為SA算法）的基本思想最早由Metropolis等人于1953年提出，用于模擬固體在給定溫度下的