MATLAB程序設(shè)計(jì) 課件 第7-9章 最優(yōu)化設(shè)計(jì)、智能算法、機(jī)械工程設(shè)計(jì)

尚德敏學(xué)唯實(shí)惟新MATLAB程序設(shè)計(jì)CONTENTS目錄優(yōu)化問題概述MATLAB中的優(yōu)化工具箱優(yōu)化函數(shù)的參數(shù)設(shè)置與定義7.17.27.37.4基于模擬退火算法的極值求解尚德敏學(xué)唯實(shí)惟新7.1優(yōu)化問題概述

在實(shí)際的工程優(yōu)化設(shè)計(jì)過程中，它包含著兩個(gè)方面的內(nèi)容，或者說需要兩個(gè)重要的步驟:

第一步:建立數(shù)學(xué)模型:用數(shù)學(xué)語言來描述最優(yōu)化問題,把實(shí)際問題轉(zhuǎn)換成能夠用數(shù)學(xué)表達(dá)式表示的形式,模型中的數(shù)學(xué)關(guān)系式反映了最優(yōu)化問題的目標(biāo)和各種約束，為我們理論研究打下堅(jiān)實(shí)的基礎(chǔ)。第二步:數(shù)學(xué)求解選擇合理的最優(yōu)化方法進(jìn)行求解。尚德敏學(xué)唯實(shí)惟新1.優(yōu)化問題模型優(yōu)化問題的數(shù)學(xué)標(biāo)準(zhǔn)形式:

其中，X是待求變量，A和b是線性不等式約束的系數(shù)向量，Aeq和beq是線性等式約束的系數(shù)，b和beq是向量，A和Aeq是矩陣，c(X)和ceq(X)是返回向量的函數(shù)，分別是非線性不等式約束和非線性等式約束，lb和u,是變量的上下限。尚德敏學(xué)唯實(shí)惟新1.優(yōu)化問題模型問題一:假設(shè)某種產(chǎn)品有3個(gè)產(chǎn)地A1、A2、A3，他們的產(chǎn)量分別為100、170、200(單位為噸)，該產(chǎn)品有3個(gè)銷售地B1、B2、B3，各地的需求量分別是120、170、180（單位為噸)，把產(chǎn)品從第i個(gè)產(chǎn)地Ai運(yùn)到第j個(gè)銷售地Bj,的單位運(yùn)價(jià)（元/噸）如表7-1所示，問如何安排從Ai到Bj的運(yùn)輸方案，才能滿足各地銷售的需求又能使總運(yùn)費(fèi)最小?B1B2B3產(chǎn)量A1809075100A2608595170A39080110200A4120170180470表7-1產(chǎn)地Ai運(yùn)到第j個(gè)銷售地Bj的單位運(yùn)價(jià)表尚德敏學(xué)唯實(shí)惟新1.優(yōu)化問題模型建立數(shù)學(xué)模型如下:設(shè)從A到B的運(yùn)輸量為xij，顯然總運(yùn)費(fèi)的表達(dá)式為:80x11+90x12+75x13+60x21+85x22+95x23+90x31+80x32+110x33根據(jù)產(chǎn)量要求，則可以建立如式所示的三個(gè)等式，作為上述總運(yùn)費(fèi)的約束式:x11+x12+x13=100x21+x22+x23=170x31+x32+x33=200根據(jù)需求量要求，則可以建立如式所示的三個(gè)等式，作為上述總運(yùn)費(fèi)的另外的約束式:x11+x12+x13=120x21+x22+x23=170x31+x32+x33=180此外，在實(shí)際問題中，運(yùn)輸量不能為負(fù)值，所以有如下約束:xij≥0，i,j=1，2，3尚德敏學(xué)唯實(shí)惟新1.優(yōu)化問題模型綜上所述，此產(chǎn)銷平衡問題的數(shù)學(xué)模型可以寫為如下:minf(x)=80x11+90x12+75x13+60x21+85x22+95x23+90x31+80x32+110x33

尚德敏學(xué)唯實(shí)惟新2.數(shù)學(xué)求解根據(jù)數(shù)學(xué)模型變量的不同，可以把目前的求解方法分為如下兩大類：對(duì)于大部分單變量或者相對(duì)簡(jiǎn)單的數(shù)學(xué)模型，可以采用人工計(jì)算的方式進(jìn)行，根據(jù)是否對(duì)目標(biāo)函數(shù)求導(dǎo)，又可分為直接法和間接法，直接法主要有消去法和多項(xiàng)式近似法。一種典型的消去法是黃金分割法而間接法需要用到目標(biāo)函數(shù)的導(dǎo)數(shù)。多項(xiàng)式近似法。該法用于目標(biāo)函數(shù)比較復(fù)雜的情況，此時(shí)尋找一個(gè)與他近似的函數(shù)代替目標(biāo)函數(shù)，常用的近似函數(shù)為二次和三次多項(xiàng)式。優(yōu)化問題在使用MATLAB軟件求解時(shí)的注意如下：（1）目標(biāo)函數(shù)最小化：一般都要求實(shí)現(xiàn)目標(biāo)函數(shù)的最小值，如果優(yōu)化問題是求最大值，可以通過求原目標(biāo)函數(shù)的負(fù)值的最小化來實(shí)現(xiàn)，即-f(X)最小化來實(shí)現(xiàn)。（2）約束非正：一般都要求不等式約束形式為c(X)<=0，通過對(duì)不等式的取負(fù)可以達(dá)到使大于零的約束形式變?yōu)樾∮诹愕牟坏仁郊s束的形式目的。尚德敏學(xué)唯實(shí)惟新2.數(shù)學(xué)求解問題:邊長為3m的正方形鐵板，在4個(gè)角處減去四個(gè)相等的正方形以制成方形無蓋水槽問如何剪才能使水槽容積最大？根據(jù)題意，上述問題的數(shù)學(xué)模型為：屬于單變量優(yōu)化問題，可以采用直接法進(jìn)行計(jì)算可得：也可以采用MATLAB進(jìn)行計(jì)算，需要將原最大值問題轉(zhuǎn)化成最小值問題，如下：在MATLAB命令行窗口輸入以下命令，回車后運(yùn)行結(jié)果如下所示：尚德敏學(xué)唯實(shí)惟新3.非線性最小二乘優(yōu)化問題非線性最小二乘優(yōu)化也叫無約束極小平方和函數(shù)問題，它是如下無約束極小問題，

程序代碼如下:尚德敏學(xué)唯實(shí)惟新3.非線性最小二乘優(yōu)化問題擬合結(jié)果如下:尚德敏學(xué)唯實(shí)惟新7.2MATLAB中優(yōu)化工具箱（1）工具箱的功能:①求解無約束條件非線性極小值;②求解約束條件下非線性極小值，包括目標(biāo)逼近問題、極大-極小值問題以及半無限極小值問題;③求解二次規(guī)劃、線性規(guī)劃和混合整型線性規(guī)劃問題;④非線性最小二乘逼近和曲線擬合;⑤非線性系統(tǒng)的方程求解;⑥約束條件下的線性最小二乘優(yōu)化;⑦求解復(fù)雜結(jié)構(gòu)的大規(guī)模優(yōu)化問題。尚德敏學(xué)唯實(shí)惟新7.2MATLAB中優(yōu)化工具箱123優(yōu)化函數(shù)具有簡(jiǎn)潔的函數(shù)表達(dá)式，多種優(yōu)化算法可以任意選擇，算法參數(shù)可自由進(jìn)行設(shè)置，使得用戶方便靈活地使用優(yōu)化函數(shù).并行計(jì)算功能集成在了優(yōu)化工具箱的優(yōu)化求解器中，以便用戶在不對(duì)現(xiàn)有程序有大的改變的情況下，在多臺(tái)計(jì)算機(jī)或集群計(jì)算機(jī)上進(jìn)行密集型計(jì)算優(yōu)化問題的求解。提供了定義和求解優(yōu)化問題并監(jiān)視求解進(jìn)度的OptimizationApp，可以方便地打開優(yōu)化工具，進(jìn)行優(yōu)化問題的求解。(2)工具箱的特色:尚德敏學(xué)唯實(shí)惟新7.2MATLAB中優(yōu)化工具箱(3)工具箱的結(jié)構(gòu):尚德敏學(xué)唯實(shí)惟新7.2MATLAB中優(yōu)化工具箱全局優(yōu)化工具箱提供的最優(yōu)化方法:

全局搜索和多起點(diǎn)優(yōu)化

遺傳算法模擬退火

算法模式搜索算法

全局搜索和多起點(diǎn)優(yōu)化方法產(chǎn)生若干起始點(diǎn)，然后它們用局部求解器去找到起始點(diǎn)吸引盆處的最優(yōu)點(diǎn)。遺傳算法（GA）用一組起始點(diǎn)（稱為種群)，通過迭代從種群中產(chǎn)生更好的點(diǎn)，只要初始種群覆蓋幾個(gè)盆，GA就能檢查幾個(gè)盆。模擬退火完成一個(gè)隨機(jī)搜索，通常模擬退火算法接受一個(gè)點(diǎn)，只要這個(gè)點(diǎn)比前面那個(gè)好，它也偶而接受—個(gè)比較糟的點(diǎn)，目的是轉(zhuǎn)向不同的盆。模式搜索算法在接受一個(gè)點(diǎn)之前要看看其附近的一組點(diǎn)。假如附近的某些點(diǎn)屬于不同的盆模式搜索算法本質(zhì)上是同時(shí)搜索若干個(gè)盆。尚德敏學(xué)唯實(shí)惟新7.3優(yōu)化函數(shù)的參數(shù)設(shè)置與定義MATLAB優(yōu)化工具箱的主要函數(shù)尚德敏學(xué)唯實(shí)惟新7.3優(yōu)化函數(shù)的參數(shù)設(shè)置與定義優(yōu)化函數(shù)輸入?yún)?shù)定義尚德敏學(xué)唯實(shí)惟新7.3優(yōu)化函數(shù)的參數(shù)設(shè)置與定義常用的options參數(shù)中常用的幾個(gè)參數(shù)如下：①Display：結(jié)果顯示方式，取值為off時(shí)，不顯示任何結(jié)果；取值為iter時(shí)，顯示每次迭代的信息；取值為final時(shí)，顯示最終結(jié)果，默認(rèn)值為final；取值為notify時(shí)，只有當(dāng)求解不收斂的時(shí)候才顯示結(jié)果。②MaxFunEvals：允許進(jìn)行函數(shù)計(jì)算的最大次數(shù)，取值為正整數(shù)。③MaxIter：允許進(jìn)行迭代的最大次數(shù)，取值為正整數(shù)。④TolFun：函數(shù)值(計(jì)算結(jié)果）的精度，取值為正數(shù)。⑤TolX：自變量的精度，取值為正數(shù)。尚德敏學(xué)唯實(shí)惟新7.3優(yōu)化函數(shù)的參數(shù)設(shè)置與定義MATLAB優(yōu)化函數(shù)的輸出參數(shù)尚德敏學(xué)唯實(shí)惟新7.3優(yōu)化函數(shù)的參數(shù)設(shè)置與定義

尚德敏學(xué)唯實(shí)惟新7.3優(yōu)化函數(shù)的參數(shù)設(shè)置與定義第一步:建立目標(biāo)函數(shù)文件，命名為my_fun1.m第二步:調(diào)用函數(shù)fmincon，在命令行窗口輸入如下命令，其結(jié)果如下所示:尚德敏學(xué)唯實(shí)惟新7.4基于模擬退火算法的極值求解

尚德敏學(xué)唯實(shí)惟新7.4基于模擬退火算法的極值求解231Meteopolis準(zhǔn)則溫度退火進(jìn)度表這是一個(gè)重要的參數(shù)，它隨著算法的迭代逐步下降，以模擬固體退火過程中的降溫過程。一方面，溫度用于限制SA產(chǎn)生的新解與當(dāng)前解之間的距離，即SA的搜索范圍;另一方面，溫度決定了SA以多大的概率接受目標(biāo)函數(shù)值比當(dāng)前解的目標(biāo)函數(shù)值差的新解。

是指溫度隨算法迭代的下降速度。退火過程越緩慢，SA找到全局最優(yōu)解的機(jī)會(huì)就越大。退火進(jìn)度表包括初始溫度及溫度更新函數(shù)的參數(shù)。尚德敏學(xué)唯實(shí)惟新7.4基于模擬退火算法的極值求解在MATLAB中，提供了模擬退火算法的simulannealbnd函數(shù)，用于求解目標(biāo)函數(shù)的最小值，在使用時(shí)可以直接調(diào)用，其格式如下:[xfval]=simulannealbnd(fun,x0,lb,ub,options)說明:options是對(duì)模擬退火算法進(jìn)行參數(shù)設(shè)置，其格式下:options=saoptimset('param1'value1,'param2',value2...)參數(shù)param是設(shè)定的參數(shù)，如最大迭代次數(shù)、初始溫度、繪圖函數(shù)等;value是param

的具體值。尚德敏學(xué)唯實(shí)惟新7.4基于模擬退火算法的極值求解

MATLAB程序設(shè)計(jì)第八章智能算法目錄8.1粒子群算法8.2遺傳算法8.3混合蛙跳算法8.1粒子群算法ParticleSwarmOptimization，簡(jiǎn)稱PSO;粒子群優(yōu)化算法（PSO）是一種進(jìn)化計(jì)算技術(shù)（EvolutionaryComputation）,由Eberhart(電子工程學(xué)博士)和Kennedy

(社會(huì)心理學(xué)博士)于1995年源于對(duì)鳥群捕食的行為研究。粒子群優(yōu)化算法的基本思想是通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解．PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒有許多參數(shù)的調(diào)節(jié)。目前已被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。

肯尼迪對(duì)鳥群行為的模擬：Reynolds、Heppner和Grenader提出鳥群行為的模擬。他們發(fā)現(xiàn)，鳥群在行進(jìn)中會(huì)突然同步的改變方向，散開或者聚集等。那么一定有某種潛在的能力或規(guī)則保證了這些同步的行為。這些科學(xué)家都認(rèn)為上述行為是基于不可預(yù)知的鳥類社會(huì)行為中的群體動(dòng)態(tài)學(xué)。在這些早期的模型中僅僅依賴個(gè)體間距的操作，也就是說，這中同步是鳥群中個(gè)體之間努力保持最優(yōu)的距離的結(jié)果。PSO的產(chǎn)生背景對(duì)魚群行為的研究：生物社會(huì)學(xué)家E.O.Wilson對(duì)魚群進(jìn)行了研究。提出：“至少在理論上，魚群的個(gè)體成員能夠受益于群體中其他個(gè)體在尋找食物的過程中的發(fā)現(xiàn)和以前的經(jīng)驗(yàn)，這種受益超過了個(gè)體之間的競(jìng)爭(zhēng)所帶來的利益消耗，不管任何時(shí)候食物資源不可預(yù)知的分散?！边@說明，同種生物之間信息的社會(huì)共享能夠帶來好處。這是PSO的基礎(chǔ)。群體協(xié)作-獲取信息、共享信息示意算法介紹設(shè)想這樣一個(gè)場(chǎng)景：一群鳥在隨機(jī)的搜索食物。在這個(gè)區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里。但是它們知道自己當(dāng)前的位置距離食物還有多遠(yuǎn)。那么，找到食物的最優(yōu)策略是什么？最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO示意圖每個(gè)鳥抽象為一個(gè)無質(zhì)量，無體積的“粒子”每個(gè)粒子有一個(gè)適應(yīng)度函數(shù)以模擬每只鳥與食物的距離每個(gè)粒子有一個(gè)速度決定它的飛行方向和距離，初始值可以隨機(jī)確定每一次單位時(shí)間的飛行后，所有粒子分享信息，下一步將飛向自身最佳位置和全局最優(yōu)位置的加權(quán)中心初始化為一群隨機(jī)粒子，通過迭代找到最優(yōu)。每次迭代中，粒子通過跟蹤“個(gè)體極值（pbest）”和“全局極值(gbest)”來更新自己的位置。粒子速度和位置的更新

假設(shè)在D維搜索空間中，有m個(gè)粒子；其中第i個(gè)粒子的位置為矢量其飛翔速度也是一個(gè)矢量，記為第i個(gè)粒子搜索到的最優(yōu)位置為整個(gè)粒子群搜索到的最優(yōu)位置為第i個(gè)粒子的位置和速度更新為：注意：上式為PSO的一般形式。其中，c1和c2為兩個(gè)正的常系數(shù)，稱為加速（學(xué)習(xí)）因子。第d（1≤d≤D）維的位置X變化范圍為[lbd,ubd]，速度V變化范圍為[V_lbd,V_ubd]，迭代中若位置和速度超過邊界范圍則取邊界值。

KennedyJ，EberhartR．Particleswarmoptimization．ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks．1995．1942~1948.從社會(huì)學(xué)的角度來看，公式(1)的第一部分稱為記憶項(xiàng)，表示上次速度大小和方向的影響；公式第二部分稱為自身認(rèn)知項(xiàng)，是從當(dāng)前點(diǎn)指向粒子自身最好點(diǎn)的一個(gè)矢量，表示粒子的動(dòng)作來源于自己經(jīng)驗(yàn)的部分；公式的第三部分稱為群體認(rèn)知項(xiàng)，是一個(gè)從當(dāng)前點(diǎn)指向種群最好點(diǎn)的矢量，反映了粒子間的協(xié)同合作和知識(shí)共享。粒子就是通過自己的經(jīng)驗(yàn)和同伴中最好的經(jīng)驗(yàn)來決定下一步的運(yùn)動(dòng)。該成果以會(huì)議論文的形式發(fā)表?！皯T性部分”，對(duì)自身運(yùn)動(dòng)狀態(tài)的信任程度“認(rèn)知部分”，對(duì)粒子本身的思考，即來源于自己經(jīng)驗(yàn)的部分“社會(huì)部分”，粒子間的信息共享，來源于群體中的其它優(yōu)秀微粒的經(jīng)驗(yàn)1998年shi等人在進(jìn)化計(jì)算的國際會(huì)議上發(fā)表了一篇論文《Amodifiedparticleswarmoptimizer》對(duì)前面的公式中的第一項(xiàng)通過引入慣性權(quán)重因子進(jìn)行了修正，形成了現(xiàn)在公認(rèn)的PSO的標(biāo)準(zhǔn)形式。慣性權(quán)重w

使粒子保持運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。表示微粒對(duì)當(dāng)前自身運(yùn)動(dòng)狀態(tài)的信任，依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)。較大的w有利于跳出局部極值，而較小的w有利于算法收斂。初始時(shí)，shi將w取為常數(shù)，后來實(shí)驗(yàn)發(fā)現(xiàn)，動(dòng)態(tài)w能夠獲得比固定值更好的尋優(yōu)結(jié)果。動(dòng)態(tài)w可以在PSO搜索過程中線性變化，也可根據(jù)PSO性能的某個(gè)測(cè)度函數(shù)動(dòng)態(tài)改變。目前，采用較多的是shi建議的線性遞減權(quán)值(linearlydecreasingweight,LDW)策略Gk為最大進(jìn)化代數(shù)，

wini為初始慣性權(quán)值，

wend為迭代至最大代數(shù)時(shí)慣性權(quán)值。典型取值

wini＝0.9，wend＝0.4。

w的引入使PSO算法性能有了很大提高，針對(duì)不同的搜索問題，可以調(diào)整全局和局部搜索能力，也使得PSO算法能成功的應(yīng)用于很多實(shí)際問題LDW策略加速常數(shù)c1和c2

代表將粒子推向pbest和gbest位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)重。表示粒子的動(dòng)作來源于自己經(jīng)驗(yàn)的部分和其它粒子經(jīng)驗(yàn)的部分。較小的值允許粒子在被拉回之前可以在目標(biāo)區(qū)域外徘徊，而較大的值則導(dǎo)致粒子突然沖向或越過目標(biāo)區(qū)域。

方程中pbest和gbest分別表示微粒群的局部和全局最優(yōu)位置，當(dāng)C1＝0時(shí)，則粒子沒有了認(rèn)知能力，變?yōu)橹挥猩鐣?huì)的模型(social-only):被稱為全局PSO算法.粒子有擴(kuò)展搜索空間的能力，具有較快的收斂速度，但由于缺少局部搜索，對(duì)于復(fù)雜問題比標(biāo)準(zhǔn)PSO更易陷入局部最優(yōu)。當(dāng)C2＝0時(shí)，則粒子之間沒有社會(huì)信息，模型變?yōu)橹挥姓J(rèn)知(cognition-only)模型：被稱為局部PSO算法。由于個(gè)體之間沒有信息的交流，整個(gè)群體相當(dāng)于多個(gè)粒子進(jìn)行盲目的隨機(jī)搜索，收斂速度慢，因而得到最優(yōu)解的可能性小。加速常數(shù)c1和c2

將c1和c2統(tǒng)一為一個(gè)控制參數(shù)，φ=c1+c2

如果φ很小，粒子群運(yùn)動(dòng)軌跡將非常緩慢；如果φ很大，則微粒位置變化非?？欤粚?shí)驗(yàn)表明，當(dāng)φ=4.1（通常c1=2.05，c2=2.05）時(shí)，具有很好的收斂效果。粒子數(shù)

一般取20～40，對(duì)較難或特定類別的問題可以取

100～200。最大速度vmax

決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)定為粒子的范圍寬度。終止條件

最大循環(huán)數(shù)以及最小錯(cuò)誤要求。基本粒子群算法的尋優(yōu)示意4647MATLAB中調(diào)用PSOPso現(xiàn)在已作為MATLAB優(yōu)化工具箱中的基本函數(shù)。其格式如下：[xfval]=particleswarm(fun,nars,lb,ub)各參數(shù)含義與前述規(guī)定基本相同488.2遺傳算法遺傳算法（Geneticalgorithm，GA）是應(yīng)用最廣泛的一種演化算法，為典型代表。

一切生物都具有產(chǎn)生變異的特性。在生存斗爭(zhēng)中，具有有利變異的個(gè)體，容易在生存斗爭(zhēng)中獲勝而生存下去。反之，具有不利變異的個(gè)體，則容易在生存斗爭(zhēng)中失敗而死亡。此過程叫做自然選擇。

自然選擇過程是一個(gè)長期的、緩慢的、連續(xù)的過程。由于生存斗爭(zhēng)不斷地進(jìn)行，因而自然選擇也是不斷地進(jìn)行，通過一代代的生存環(huán)境的選擇作用，物種變異被定向地向著一個(gè)方向積累，于是性狀逐漸和原來的祖先不同了，可以說物種也因此得到優(yōu)化了。50（一）背景CharlesRobertDarwin1859年，達(dá)爾文（CharlesRobertDarwin）出版的《物種起源》，提出進(jìn)化學(xué)說51遺傳以密碼方式存在細(xì)胞內(nèi)，并以基因形式包含在染色體內(nèi)，每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)，所以每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性?；蛲蛔兒突螂s交可以產(chǎn)生更適應(yīng)于環(huán)境的后代，經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來1865年，孟德爾（GregorJohannMendel)

發(fā)現(xiàn)遺傳定律52生物進(jìn)化是指一個(gè)種群經(jīng)過漫長的時(shí)間所發(fā)生的累積變化，這些變化是由于生物體的基因變異或者繁殖期間以不同方式重組基因所產(chǎn)生的，而且這些變化可以被遺傳到生物體的后代。從本質(zhì)上說，它是一個(gè)優(yōu)勝劣汰的自然過程，也是一個(gè)優(yōu)化過程。優(yōu)化的結(jié)果是產(chǎn)生能夠很好地適應(yīng)環(huán)境的生物體。此過程也可以看成是在眾多可能性中搜索“解”的一種方法。遺傳算法（GeneticAlgorithms,GA）是模擬生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。53GA的發(fā)展歷程20世紀(jì)60年代中期，美國的Michigan(密歇根)大學(xué)的J.H.Holland借鑒生物自然遺傳的基本原理（自然選擇、適者生存）提出的一種搜索尋優(yōu)算法，用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)。1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法”一詞。1975年，Holland出版了著名的“AdaptationinnaturalandArtificialSystems”，標(biāo)志著遺傳算法的正式誕生。（一）產(chǎn)生過程20世紀(jì)50年代到60年代，生物學(xué)家Fraser試圖通過計(jì)算的方法來模擬生物界“遺傳與選擇”的進(jìn)化過程,

這是遺傳算法的最早雛形。5570年代初，Holland提出了“模式定理”（SchemaTheorem），一般認(rèn)為是“遺傳算法的基本定理”，從而也奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國召開了第一屆遺傳算法國際會(huì)議，并且成立了國際遺傳算法學(xué)會(huì)（ISGA,InternationalSocietyofGeneticAlgorithms）；1989年，他的學(xué)生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，系統(tǒng)的總結(jié)了遺傳算法的主要研究成果，全面完整地論述了GA的基本原理和應(yīng)用；1991年，L.Davis出版了“HandbookofGeneticAlgorithms”，介紹了GA在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)等領(lǐng)域中的大量應(yīng)用實(shí)例，為推廣和普及GA的應(yīng)用起到了重要的指導(dǎo)作用；（二）發(fā)展ProcedureGeneticAlgorithmProcedureEA遺傳算法的基本步驟：第1步.根據(jù)由問題確定的編碼規(guī)則，隨機(jī)產(chǎn)生初始群體；第2步.計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度值；第3步.如果解滿足要求或遺傳代數(shù)超過指定代數(shù)，則結(jié)束；否則繼續(xù)執(zhí)行第4步；第4步.根據(jù)適應(yīng)值進(jìn)行選擇復(fù)制產(chǎn)生新一代；第5步.根據(jù)事先確定的交叉和變異概率選擇部分個(gè)體進(jìn)行交叉和變異，轉(zhuǎn)第2步；

GA的流程圖遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。

（二）基本遺傳算法的計(jì)算過程遺傳算法的基本思想：在求解問題時(shí)從多個(gè)解開始，然后通過一定的法則進(jìn)行逐步迭代以產(chǎn)生新的解（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)

編碼遺傳算法（GA）通過某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串?；具z傳算法（SGA）使用二進(jìn)制串進(jìn)行編碼。1000101110110101000111

染色體基因

編碼示例求下列一元函數(shù)的最大值：其中x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。（1）二進(jìn)制編碼要求取多少位？（2）十進(jìn)制實(shí)數(shù)與二進(jìn)制編碼之間應(yīng)滿足怎樣的數(shù)學(xué)關(guān)系？？

編碼示例的分析區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因?yàn)?21<3×106<222

，所以二進(jìn)制編碼長度至少需要22位。編碼過程實(shí)質(zhì)是將區(qū)間[-1，2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20b19b18…b1b0）。101010111111……101011000

一個(gè)問題對(duì)于x∈[-1,2]，結(jié)果精確到6位小數(shù)，十進(jìn)制實(shí)數(shù)與二進(jìn)制編碼之間應(yīng)滿足怎樣的數(shù)學(xué)關(guān)系？

編碼(二進(jìn)制)與實(shí)數(shù)(十進(jìn)制)的轉(zhuǎn)換(1000101110110101000111)2

編碼與實(shí)數(shù)的轉(zhuǎn)換(1000101110110101000111)20.637197基因型與表現(xiàn)型基因型：1000101110110101000111表現(xiàn)型：0.637197

編碼解碼個(gè)體（染色體）基因初始種群基本遺傳算法（SGA）采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。初始種群中個(gè)體的數(shù)量稱為種群規(guī)模。

適應(yīng)度函數(shù)遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，適應(yīng)度函數(shù)值越大（或越?。?，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。選擇算子遺傳算法使用選擇運(yùn)算對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰操作。適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是從父代群體中選取一些個(gè)體，遺傳到下一代群體?；具z傳算法（SGA）中選擇算子采用輪盤賭選擇方法。一等獎(jiǎng)二等獎(jiǎng)三等獎(jiǎng)四等獎(jiǎng)輪盤賭選擇方法(RouletteWheelSelection)輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。設(shè)群體大小為N，個(gè)體xi

的適應(yīng)度為f(xi)，則個(gè)體xi的選擇概率為：輪盤賭選擇法可用如下過程模擬來實(shí)現(xiàn)：(1)在［0,1］內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。(2)若r≤q1,則染色體x1被選中。(3)若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi

(i=1,2,…,n)的積累概率,其計(jì)算公式為輪盤賭選擇方法積累概率實(shí)例：

輪盤賭選擇方法0.140.490.060.3100.140.630.691q1q2

q3

q4

積累概率q選擇概率P輪盤賭選擇方法輪盤賭選擇方法的實(shí)現(xiàn)步驟:（1）計(jì)算群體中所有個(gè)體的適應(yīng)度值；（2）計(jì)算每個(gè)個(gè)體的選擇概率P；（3）計(jì)算積累概率q；（4）采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個(gè)個(gè)體遺傳到下一代群體的概率進(jìn)行匹配）來確定各個(gè)個(gè)體是否遺傳到下一代群體中。輪盤賭選擇方法例如，有染色體

s1=13(01101)

s2=24(11000)

s3=8(01000)

s4=19(10011)

假定適應(yīng)度函數(shù)為f(s)=s2

，則

f(s1)=f(13)=132=169

f(s2)=f(24)=242=576

f(s3)=f(8)=82=64

f(s4)=f(19)=192=361染色體的選擇概率為染色體的累計(jì)概率為

例如，從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù):

r1=0.450126,r2=0.110347

r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001交叉算子交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率Pc

按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他演化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法?；具z傳算法（SGA）中交叉算子采用單點(diǎn)交叉算子。單點(diǎn)交叉運(yùn)算交叉前：01000|0111000000001000011100|00000111111000101交叉后：01000|00000111111000101（孩子1）11100|01110000000010000（孩子2）交叉點(diǎn)變異算子變異運(yùn)算，是指改變個(gè)體編碼串中的某些基因值，從而形成新的個(gè)體。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，決定遺傳算法的局部搜索能力，保持種群多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索?；具z傳算法（SGA）中變異算子采用基本位變異算子?；咀儺愃阕踊疚蛔儺愃阕邮侵笇?duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則將其變?yōu)?；反之，若原有基因值為1，則將其變?yōu)??；疚蛔儺愂纠儺惽埃?00001110000000010000變異后：000001110001000010000變異點(diǎn)已知x為整數(shù)，利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY遺傳算法的應(yīng)用舉例

[分析]

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。個(gè)體：［0,31］中的任意點(diǎn)x

適應(yīng)度：函數(shù)值f(x)=x2

解空間：區(qū)間［0,31］這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。[解]

(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù),取適應(yīng)度函數(shù)

f(x)=x2(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度（評(píng)價(jià)個(gè)體性能）,并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體，即31（11111）出現(xiàn)為止。

首先計(jì)算種群S1中各個(gè)體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應(yīng)度f(si),容易求得

f(s1)=f(13)=132=169

f(s2)=f(24)=242=576

f(s3)=f(8)=82=64f(s4)=f(19)=192=361評(píng)價(jià)個(gè)體的適應(yīng)度值再計(jì)算種群S1中各個(gè)體的選擇概率。

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31再計(jì)算種群S1中各個(gè)體的積累概率

選擇-復(fù)制：設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù):r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）

被選中兩次交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。

設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。

s1’=11000（24）,s2’=01101（13）

s3’=11000（24）,s4’=10011（19）分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

變異

設(shè)變異率pm=0.001。

這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

第二代種群S2中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

s1’’=11100（28）,s2’’

=01001（9）

s3’’

=11000（24）,s4’’

=10011（19）

這一輪仍然不會(huì)發(fā)生變異。

于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代種群S3中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會(huì)發(fā)生變異。被選中兩次

于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）出現(xiàn)了最優(yōu)解！

顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體（11111）作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。

將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。

YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度剛剛產(chǎn)生四代種群及其適應(yīng)度。你知道這四代種群之間有何發(fā)展規(guī)律嗎？四代種群的發(fā)展規(guī)律就是適應(yīng)度的整體水平越來越好，直到最優(yōu)解出現(xiàn)！105遺傳算法在MATLAB中如何應(yīng)用？遺傳算法的基本流程Step1：對(duì)運(yùn)行參數(shù)賦值；Step2：建立區(qū)域描述器；

Step3：初始化種群，并評(píng)估個(gè)體好壞；Step4：進(jìn)行選擇操作Step5：按交叉概率進(jìn)行交叉操作Step6：按變異概率進(jìn)行變異操作Step7：執(zhí)行新個(gè)體保存策略，形成新種群Step8：判斷是否滿足結(jié)束條件根據(jù)定義編程調(diào)用函數(shù)ga使用優(yōu)化工具箱√X√最優(yōu)化問題的標(biāo)準(zhǔn)型106A和b是線性不等式約束的系數(shù)Aeq和beq是線性等式約束的系數(shù)c是非線性不等式約束ceq是非線性等式約束lb和ub是變量的上下限107ga函數(shù)的基本格式[xfval]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)fun：待求的目標(biāo)函數(shù)nvars:變量的個(gè)數(shù)nonlcon:非線性約束的表達(dá)式，匿名函數(shù)形式options：遺傳算法的參數(shù)設(shè)置（較復(fù)雜）fval:最優(yōu)個(gè)體的函數(shù)值一、調(diào)用函數(shù)ga《MATLAB程序設(shè)計(jì)》108minf(x)=-x(3-2x)2

x=fminbnd(@(x)-x*(3-2*x)^2,0,1.5)方法1：MATLAB命令行窗口輸入以下命令：例1-無約束問題方法2：調(diào)用ga函數(shù)步驟一：建立目標(biāo)函數(shù)文件：functiony=my_fun(x)y=-x*(3-2*x)^2;步驟二：調(diào)用x=ga(@my_fun,1,[],[],[],[],0,1.5)基于內(nèi)部映射牛頓法fminsearch?例2-線性約束問題109步驟一：建立目標(biāo)函數(shù)文件：functiony=my_fun2(x)y=0.5*x(1)^2+x(2)^2-x(1)*x(2)-2*x(1)-6*x(2);步驟二：調(diào)用A=[11;-12;21];b=[2;2;3];lb=[0;0];x=ga(@my_fun2,2,A,b,[],[],lb)110例3-非線性約束問題步驟一：建立目標(biāo)函數(shù)文件：functiony=my_fun3(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2;function[cceq]=my_fun3_con(x)c=[1.5+x(1)*x(2)+x(1)-x(2);10-x(1)*x(2);];ceq=[];步驟二：建立非線性約束文件：步驟三：調(diào)用lb=[0;0];

ub=[1;13];x=ga(@my_fun3,2,[],[],[],[],lb,ub,@my_fun3_con)111二、使用優(yōu)化工具箱MATLAB系統(tǒng)中帶有一個(gè)優(yōu)化工具箱，其調(diào)用方式有兩種：在命令行輸入命令：optimtool

或點(diǎn)擊APP標(biāo)簽，選擇optimization點(diǎn)擊112113遺傳算法工具箱problemsetupandresults說明：注意事項(xiàng)：1）需要單獨(dú)寫適應(yīng)度函數(shù)和變量個(gè)數(shù)2）各約束參數(shù)含義與前述相同3）integervariableindices的含義是“整型變量標(biāo)記約束”114遺傳算法工具箱Options說明(1)：1）群體（Population）（1）編碼類型(populationtype)實(shí)數(shù)編碼（doublevector）二進(jìn)制編碼（bitstring）自定義（custom）（2）種群規(guī)模(populationtype)115遺傳算法工具箱Options說明(2)：2）選擇（Selection）算子隨機(jī)均勻分布（stochasticuniform）殘余（remainder）均勻（uniform）聯(lián)賽選擇（

tournament）輪盤賭（

roulette）

自定義（custom）116

沒有這兩個(gè)參數(shù)，由交叉函數(shù)和變異函數(shù)來確定，這也是和基本遺傳算法的區(qū)別之處。交叉比例(crossoverfraction)：由交叉產(chǎn)生的個(gè)體占父代中非精英個(gè)體數(shù)的比例遺傳算法工具箱Options說明(3)：3）復(fù)制（再生、繁殖）算子4）交叉概率和變異概率精英數(shù)(elitecount)：直接傳到下一代的個(gè)體數(shù)《MATLAB程序設(shè)計(jì)》117屬于算法停止標(biāo)準(zhǔn)，除此之外主要有時(shí)間限制(timelimit)和適應(yīng)值限制(fitnesslimit)

遺傳算法工具箱Options說明(3)：5）迭代次數(shù)（generations）6）結(jié)果可視化繪制最佳適應(yīng)度值(bestfitness)和最佳個(gè)體(bestindividual)隨迭代次數(shù)的變化曲線118例2-線性約束問題119例4-非線性約束問題functiony=my_fun4(x)y=-(2*x(1)+3*x(1)^2+3*x(2)+x(2)^2+x(3));function[cceq]=my_fun4_con(x)c=[x(1)+2*x(1)^2+x(2)+2*x(2)^2+x(3)-10;x(1)+x(1)^2+x(2)+x(2)^2-x(3)-50;2*x(1)+x(1)^2+2*x(2)+x(3)-40];ceq=[x(1)^2+x(3)-2];步驟一：轉(zhuǎn)換目標(biāo)函數(shù)為標(biāo)準(zhǔn)型步驟二：編寫目標(biāo)函數(shù)步驟三：編寫非線性約束函數(shù)120設(shè)置一：目標(biāo)函數(shù)及約束條件如圖所示：設(shè)置二：遺傳算法的參數(shù)如圖所示，具體如下：種群規(guī)模：100選擇策略：輪盤賭精英數(shù)：8交叉比例：0.6迭代次數(shù)：200其它參數(shù)采用默認(rèn)值遺傳算法屬于隨機(jī)搜索算法，對(duì)于復(fù)雜、多模態(tài)函數(shù)問題，每一次的計(jì)算結(jié)果不完全一致，屬于正常情況，需要對(duì)算法本身的參數(shù)反復(fù)調(diào)試，直到結(jié)果誤差在允許范圍內(nèi)優(yōu)化工具箱和調(diào)用ga函數(shù)，其核心算法和內(nèi)核是一樣的，不同之處在于，當(dāng)你想對(duì)遺傳算法的參數(shù)進(jìn)行設(shè)置時(shí)，建議使用優(yōu)化工具箱，因?yàn)榉奖阋讓W(xué)。Matlab采用的是現(xiàn)代遺傳算法，上一節(jié)講的是基本（簡(jiǎn)單）遺傳算法，二者基本內(nèi)容是一致的121總結(jié)：MATLAB程序設(shè)計(jì)CONTENTS目錄連桿機(jī)構(gòu)設(shè)計(jì)7.1平面連桿機(jī)構(gòu)運(yùn)動(dòng)分析7.3平面機(jī)構(gòu)優(yōu)化設(shè)計(jì)7.2尚德敏學(xué)唯實(shí)惟新9.1連桿機(jī)構(gòu)設(shè)計(jì)