第四章：遺傳算法

目錄引言GA的基本概念Darwin進(jìn)化論及進(jìn)化系統(tǒng)模型Mendel的遺傳學(xué)說GA的基本概念與術(shù)語GA的原理GA的目的GA的基本原理GA的算法過程第一頁，共一百一十三頁，2022年，8月28日目錄GA的應(yīng)用GA的特點(diǎn)GA應(yīng)用的關(guān)鍵GA在函數(shù)優(yōu)化中的應(yīng)用GA在組合優(yōu)化中的應(yīng)用GA的理論分析GA在智能控制中的應(yīng)用GA的發(fā)展展望參考文獻(xiàn)第二頁，共一百一十三頁，2022年，8月28日4.1引言生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過程,它通過選擇淘汰,突然變異,基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種.例如,在人類的進(jìn)化過程中,通過“物競天擇、適者生存”自然的選擇和淘汰,人類的身、心不斷得到進(jìn)化,逐漸進(jìn)化成為這地球上的具有最高等智慧的主宰者.在這個(gè)進(jìn)化過程中,不僅人的身體得到進(jìn)化,而且人的智慧、智能也在得到進(jìn)化.因此,生物的進(jìn)化過程其實(shí)也是一種智能的進(jìn)化、優(yōu)化過程,也是一種智能行為.“物競天擇、適者生存”中蘊(yùn)涵了智能的光輝、蘊(yùn)涵了優(yōu)化的思想.第三頁，共一百一十三頁，2022年，8月28日遺傳算法(GeneticAlgorithm,GA)就是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種智能理論和方法.它是基于進(jìn)化過程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則的搜索算法,是通過對(duì)生物進(jìn)化的歸納和模擬得到的一種仿生算法.GA在本質(zhì)上是一種不依賴具體問題的直接搜索方法,是一種具有普適性的優(yōu)化方法.GA的發(fā)展歷程為:1965年,Michigan大學(xué)的Holland首次提出了人工遺傳操作的重要性,并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中.1967年在他的論文中首次提出了GA這一術(shù)語與概念,并討論了GA在自動(dòng)博弈中的應(yīng)用.4.1引言第四頁，共一百一十三頁，2022年，8月28日1970年,Cavicchio把GA應(yīng)用于模式識(shí)別中.第一個(gè)把GA應(yīng)用于函數(shù)優(yōu)化的是Hollstien.而GA的理論和方法的系統(tǒng)性研究開始于1975年,這一開創(chuàng)性工作是由所實(shí)行.這一年是GA研究的歷史上十分重要的一年.Holland在他的著名專著《AdaptationinNaturalandArtificialSystems》中系統(tǒng)地闡述了GA的基本理論和方法,并提出了對(duì)GA的理論研究和發(fā)展極為重要的模式理論(schematatheory).該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得隱并行性的重要性.4.1引言第五頁，共一百一十三頁，2022年，8月28日同年,DeJong完成了他的重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》.他在該論文中所做的研究工作可看作是GA發(fā)展過程中的一個(gè)里程碑,這是因?yàn)樗袶olland的模式理論與他的計(jì)算使用結(jié)合起來.1989年Goldberg對(duì)GA從理論上,方法上和應(yīng)用上作了系統(tǒng)的總結(jié).1990年代以來,以GA為代表的進(jìn)化類算法及計(jì)算智能理論和算法得到極大重視.1994年在美國召開了第一屆世界計(jì)算智能大會(huì),欣起了進(jìn)化類算法研究和應(yīng)用的熱潮.4.1引言第六頁，共一百一十三頁，2022年，8月28日GA與其它優(yōu)化方法相比,具有如下特點(diǎn):GA不是直接作用在參變量集上,而是利用參變量集的某種編碼;GA不是從單個(gè)點(diǎn),而是在群體中從多個(gè)點(diǎn)開始搜索;GA利用適應(yīng)值信息,無需導(dǎo)數(shù)或其它輔助信息;因此對(duì)優(yōu)化問題(函數(shù))的限制較弱,靈活,通用性(普適性)強(qiáng),有著較廣泛的應(yīng)用領(lǐng)域.GA利用概率轉(zhuǎn)移規(guī)則,而非確定性規(guī)則.GA在解空間內(nèi)不是盲目的窮舉或完全隨機(jī)測(cè)試，而是一種啟發(fā)式搜索，效率優(yōu)于其它算法。4.1引言第七頁，共一百一十三頁，2022年，8月28日GA的優(yōu)點(diǎn):較容易的和其它方法結(jié)合避免陷入局部最優(yōu)解即使在較短的有限時(shí)間內(nèi),也能獲得較好的次優(yōu)解、滿意解.魯棒性佳對(duì)優(yōu)化問題的初始條件(狀態(tài))依賴性小。抗干擾性強(qiáng)。具有并行計(jì)算的特點(diǎn)，可提高計(jì)算速度4.1引言第八頁，共一百一十三頁，2022年，8月28日GA的不足:NoguaranteeforoptimalsolutionwithinfinitetimeWeaktheoreticalbasisGA能解決的問題:優(yōu)化NP完全高度復(fù)雜的非線性問題4.1引言第九頁，共一百一十三頁，2022年，8月28日近年,GA在各應(yīng)用領(lǐng)域中得到極大重視,并廣泛應(yīng)用于各領(lǐng)域的優(yōu)化、搜索、問題求解中,并在模式識(shí)別、NN、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會(huì)科學(xué)等方面都得到應(yīng)用.4.1引言第十頁，共一百一十三頁，2022年，8月28日當(dāng)前在AI研究中,人們認(rèn)為“GA、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與AI一樣,都是對(duì)今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”.4.1引言第十一頁，共一百一十三頁，2022年，8月28日4.2GA的基本概念GA的基本思想是基于達(dá)爾文(Darwin)進(jìn)化論和門德爾(Mendel)的遺傳學(xué)說的,下面將分別介紹:Darwin進(jìn)化論及進(jìn)化系統(tǒng)模型Mendel的遺傳學(xué)說GA的基本概念與術(shù)語第十二頁，共一百一十三頁，2022年，8月28日4.2.1Darwin進(jìn)化論及進(jìn)化系統(tǒng)模型CharlesDarwinAllenvironmentshavefiniteresources(i.e.,canonlysupportalimitednumberofindividuals)它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境.Darwin(1809-1882,Fatheroftheevolutiontheory)進(jìn)化論最重要的是適者生存(Survivalofthefittest)原理.第十三頁，共一百一十三頁，2022年，8月28日物種每個(gè)個(gè)體的基本特征由后代所繼承,但后代又會(huì)產(chǎn)生一些異于父代的新變化.在環(huán)境變化時(shí),只有那些能適應(yīng)環(huán)境的個(gè)體特征方能保留下來.4.2.1Darwin進(jìn)化論及進(jìn)化系統(tǒng)模型第十四頁，共一百一十三頁，2022年，8月28日4.2.1Darwin進(jìn)化論及進(jìn)化系統(tǒng)模型生物進(jìn)化過程(循環(huán)圖):初始群體淘汰體競爭初始種群繁殖變異新的群體第十五頁，共一百一十三頁，2022年，8月28日自Darwin以來的新進(jìn)化學(xué)說強(qiáng)調(diào):個(gè)體是基本的選擇目標(biāo);隨機(jī)過程在進(jìn)化中起重大作用,遺傳變異大部分是偶然現(xiàn)象;進(jìn)化是在適應(yīng)中變化的,形式多樣,不僅是基因的變化;選擇是概率型的,而不是決定型的.4.2.1Darwin進(jìn)化論及進(jìn)化系統(tǒng)模型第十六頁，共一百一十三頁，2022年，8月28日4.2.2Mendel遺傳學(xué)說GregorMendel它認(rèn)為遺傳以密碼方式存在細(xì)胞中,并以基因形式包含在染色體內(nèi).每個(gè)基因有特殊的位置并控制某種特殊性質(zhì);所以,每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性.Mendel(1822-1884,Fatherofgenetics)遺傳學(xué)說最重要的是基因遺傳原理.第十七頁，共一百一十三頁，2022年，8月28日4.2.2Mendel遺傳學(xué)說基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代.經(jīng)過存優(yōu)去劣的自然淘汰,適應(yīng)性高的基因結(jié)構(gòu)得以保存下來.第十八頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語基于達(dá)爾文的進(jìn)化論與孟德爾的遺傳學(xué)說,可得到如下生物進(jìn)化的原則生物進(jìn)化過程的發(fā)生需要四個(gè)基本條件:存在由多個(gè)生物個(gè)體組成的種群;生物個(gè)體之間存在著差異,或群體具有多樣性;生物能夠自我繁殖;不同個(gè)體具有不同的環(huán)境生存能力,具有優(yōu)良基因結(jié)構(gòu)的個(gè)體繁殖能力強(qiáng),反之則弱.第十九頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語生物群體的進(jìn)化機(jī)制包括三種基本形式:自然選擇雜交突變另外,外界對(duì)生物的評(píng)價(jià)反映了生物的生存價(jià)值和機(jī)會(huì).

受到生物進(jìn)化過程的啟迪,模擬生物進(jìn)化的優(yōu)化方法—GA得到重視并迅速發(fā)展.第二十頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語由于GA是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法,故而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念.這些概念如下:串群體群體規(guī)模基因與基因位置基因特征值適應(yīng)度第二十一頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語A.串(String)它是個(gè)體(Individual)的基因表示形式,本質(zhì)為如何表示解.在算法中常采用給定長度的二進(jìn)制串,其特點(diǎn)操作簡便.根據(jù)具體問題也可采用特定的適宜于問題處理的編碼方式,如實(shí)數(shù)編碼D進(jìn)制,D=3,8,16,…序列編碼:例如TSP的路徑表達(dá)自適應(yīng)編碼-長度可調(diào)節(jié)第二十二頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語B.群體(Population)個(gè)體的集合稱為群體,串是群體的元素.Apopulationisasetofpossiblesolutions.GA之所以具有良好的優(yōu)化性能和智能行為,除開交叉和變異等遺傳操作具有獨(dú)到的優(yōu)化能力,正是由于其優(yōu)化過程是針對(duì)群體而非僅僅針對(duì)單個(gè)個(gè)體進(jìn)行.對(duì)群體的優(yōu)化除保證子代群體能夠繼承父代群體的優(yōu)勢(shì)特征之外,重要的其在一定程度上保證所搜索到的解具有某種全局性.群體進(jìn)化行為在一定程度上可避免個(gè)體進(jìn)化和優(yōu)化的局部性、非單調(diào)性等.第二十三頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語C.群體規(guī)模(PopulationSize)群體規(guī)模指群體中個(gè)體的數(shù)量.由于GA的優(yōu)化是針對(duì)群體進(jìn)行的,因此群體規(guī)模是非常重要的一個(gè)參數(shù)Manyresearcherssuggestpopulationsizesbetween25and100.

第二十四頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語D.基因(Gene)與基因位置(GenePosition)基因是串中的元素,基因用于表示個(gè)體的特征.基因位置是指一個(gè)基因在串中的位置,有時(shí)也簡稱基因位.基因位置對(duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus).例如有一個(gè)串S=1011,則其中的1,0,1,1這4個(gè)元素分別稱為基因.基因位置由串的左向右計(jì)算,例如在串S=1011中,0的基因位置是2.第二十五頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語E.基因特征值(GeneFeature)在用串表示整數(shù)時(shí),基因的特征值與二進(jìn)制數(shù)的權(quán)一致;例如在串S=1011中,基因位置3中的1,它的基因特征值為2;基因位置1中的1,它的基因特征值為8.第二十六頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語F.適應(yīng)度(Fitness)表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度,是GA進(jìn)行優(yōu)化的指標(biāo)函數(shù).在優(yōu)化過程中,通過適應(yīng)度可以進(jìn)行個(gè)體優(yōu)劣的比較,可以進(jìn)行個(gè)體的篩選,以產(chǎn)生子代群體,或選擇個(gè)體參加交叉和變異等遺傳操作.一般,適應(yīng)度函數(shù)定義為[0,1]之間的實(shí)數(shù).適應(yīng)度函數(shù)值越大,表示該個(gè)體越適應(yīng)環(huán)境(問題),就越優(yōu).因此GA是對(duì)適應(yīng)度函數(shù)求極大優(yōu)化.第二十七頁，共一百一十三頁，2022年，8月28日4.2.3GA的基本概念與術(shù)語GA還有一些其它的概念,這些概念在介紹GA的原理和執(zhí)行過程時(shí),再進(jìn)行說明.第二十八頁，共一百一十三頁，2022年，8月28日4.3GA的原理GA把問題的解表示成“染色體”,在算法中也即是以二進(jìn)制編碼的串.并且,在執(zhí)行GA之前,給出一群“染色體”,也即是假設(shè)解.然后,把這些假設(shè)解置于問題的“環(huán)境”中,并按適者生存的原則,從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制,再通過交叉,變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群.這樣,一代一代地進(jìn)化,最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上,它就是問題的最優(yōu)解.第二十九頁，共一百一十三頁，2022年，8月28日4.3GA的原理下面分別介紹:GA的目的GA的基本原理GA的算法過程第三十頁，共一百一十三頁，2022年，8月28日4.3.1GA的目的典型的遺傳算法(canonicalgeneticalgorithm,CGA)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題:考慮對(duì)于一群長度為L的二進(jìn)制編碼bi,i=1,2,…,n;有bi∈{0,1}L

(1)給定目標(biāo)函數(shù)f,有f(bi),并且0<f(bi)<求滿足下式max{f(bi)|bi∈{0,1}L}

(2)的bi.第三十一頁，共一百一十三頁，2022年，8月28日4.3.1GA的目的很明顯,GA是一種最優(yōu)化方法,它通過進(jìn)化和遺傳機(jī)理,從給出的原始解群中,不斷進(jìn)化產(chǎn)生新的解,最后收斂到一個(gè)特定的串bi處,即求出最優(yōu)解.第三十二頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理長度為L的n個(gè)二進(jìn)制串bi(i=1,2,…,n)組成了GA的初解群,也稱為初始群體.在每個(gè)串中,每個(gè)二進(jìn)制位就是個(gè)體染色體的基因.根據(jù)進(jìn)化術(shù)語,對(duì)群體執(zhí)行的操作有三種:選擇與再生重組與交叉變異第三十三頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理A.選擇(Selection)與再生(Reproduction)選擇是根據(jù)適者生存原則從群體中選擇出較適應(yīng)環(huán)境的個(gè)體組成子代.在選擇時(shí),以適應(yīng)度為選擇原則.適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存,不適應(yīng)者淘汰的自然法則.這些選中的個(gè)體用于繁殖下一代.故有時(shí)也稱這一操作為再生(reproduction).由于在選擇用于繁殖下一代的個(gè)體時(shí),是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的,故而有時(shí)也稱為非均勻再生(differentialreproduction).第三十四頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理早期的GA產(chǎn)生的新一代均是從父代的個(gè)體經(jīng)交叉與變異產(chǎn)生的子代中由基于選擇概率的選擇算子選擇產(chǎn)生的.這種選擇策略使得進(jìn)化過程可能似的優(yōu)化的解被丟棄,產(chǎn)生退化.實(shí)踐證明使用保留父代群體中最佳個(gè)體模型至子代的GA比基本GA的性能有明顯的改進(jìn),該GA成為保留最優(yōu)個(gè)體遺傳算法.第三十五頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理下面主要討論基于適應(yīng)度函數(shù)產(chǎn)生的選擇概率來選擇的方法--Proportionate-basedselection一般在GA的選擇中,由個(gè)體的適應(yīng)度函數(shù)值計(jì)算相應(yīng)的選擇概率,并按照輪盤賭的方式選擇需要進(jìn)行遺傳運(yùn)算的個(gè)體(參加遺傳操作的父親和母親).設(shè)目標(biāo)函數(shù)為f,則f(bi)稱為個(gè)體bi的適應(yīng)度.相應(yīng)地,個(gè)體bi的選擇概率為選擇概率一般用于選擇下一代(子代)群體,以及參加交叉和變異操作的個(gè)體.在選擇參加交叉和變異操作的個(gè)體時(shí)采用輪盤賭的方式,如下圖所示第三十六頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理圖2隨機(jī)選擇遺傳操作的輪盤賭第三十七頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理選擇方法:（a）從適應(yīng)度大小出發(fā)(四舍五入概念).

定義:選擇概率,選擇的個(gè)數(shù):n*.(b)從相對(duì)適應(yīng)度出發(fā)選擇.

定義:相對(duì)適應(yīng)度,平均適應(yīng)度,

分析:

直接從相對(duì)適應(yīng)度出發(fā),四舍五入取整選擇.第三十八頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理顯然,從式(3)可知:A.

適應(yīng)度較高的個(gè)體,繁殖下一代的數(shù)目較多.反之適應(yīng)度較小的個(gè)體,繁殖下一代的數(shù)目較少;甚至被淘汰.B.

適應(yīng)度較高的個(gè)體有較多的機(jī)會(huì)參與交叉和變異等遺傳操作.這樣,就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代.對(duì)于問題求解角度來講,就是選擇出和最優(yōu)解較接近的中間解.第三十九頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理B.重組(Recombination)與交叉(Crossover)這是在選中用于繁殖下一代的個(gè)體中,對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換,從而產(chǎn)生新的個(gè)體.第四十頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理對(duì)于選中用于繁殖下一代的個(gè)體,按選擇概率以輪盤賭的方式隨機(jī)地選擇兩個(gè)個(gè)體作為父代,并隨機(jī)選取相同的基因位置,按交叉概率Pc,在選中的位置實(shí)行交換.這個(gè)過程反映了隨機(jī)信息交換;目的在于產(chǎn)生新的基因組合,也即產(chǎn)生新的個(gè)體.交叉時(shí),可實(shí)行單點(diǎn)交叉、多點(diǎn)交叉及一致交叉(UniformCrossover).從理論上講,多點(diǎn)交叉可以由多次單點(diǎn)交叉實(shí)現(xiàn).對(duì)于多點(diǎn)交叉算子,隨著交叉點(diǎn)數(shù)的增加會(huì)降低GA的性能第四十一頁，共一百一十三頁，2022年，8月28日例如有2個(gè)父代個(gè)體S1=100|101S2=010|111若隨機(jī)選擇它們的左邊3位進(jìn)行交叉操作,則產(chǎn)生的子代為S1=010|101S2=100|1114.3.2GA的基本原理下面介紹具體的交叉算子算法:(1)二進(jìn)制單點(diǎn)交叉算子.

單點(diǎn)交叉過程可圖示如下:第四十二頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理單點(diǎn)交叉算子的過程為:BeginRepeat{產(chǎn)生的子代個(gè)體數(shù)=n}從父代群體中根據(jù)各個(gè)體的選擇概率，采用輪盤賭方式選擇2個(gè)參與交叉的父代個(gè)體產(chǎn)生（0，1）間的隨機(jī)數(shù)s若s小于等于交叉概率Pc,則隨機(jī)產(chǎn)生交叉位Lc對(duì)2個(gè)父代個(gè)體在交叉位Lc進(jìn)行交叉操作,生成2個(gè)子代個(gè)體EndEnd第四十三頁，共一百一十三頁，2022年，8月28日例如有2個(gè)父代個(gè)體S1=10010101S2=01110100若屏蔽字為1101110,則產(chǎn)生的子代為S1=101101004.3.2GA的基本原理(2)二進(jìn)制一致(UniformCrossover)交叉算子.

所謂一致交叉,即對(duì)給定的屏蔽字,若屏蔽字的某位為1,則子代的該位繼承父親;若為0,則子代的該位繼承母親.屏蔽字交叉過程可圖示如下:第四十四頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理對(duì)選擇算子選作交叉的父代,是否進(jìn)行交叉運(yùn)算,以交叉概率Pc決定。一般而言,交叉概率Pc取值為0.25~0.75.第四十五頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理C.變異(Mutation)變異是根據(jù)生物遺傳中基因變異的原理,按選擇概率以輪盤賭的方式隨機(jī)地選擇一個(gè)個(gè)體作為父代,并隨機(jī)選取基因位置以變異概率Pm對(duì)某些個(gè)體的某些基因位執(zhí)行異向轉(zhuǎn)化.在變異時(shí),對(duì)執(zhí)行變異的串的對(duì)應(yīng)基因位求反.產(chǎn)生變異時(shí)就是把它變成0;反亦反之.變異概率Pm與生物變異極小的情況一致,所以,Pm的取值較小,一般取0.01~0.2.第四十六頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理下面介紹具體的變異算子算法:二進(jìn)制變異算子.變異過程可圖示如下:例如有父代個(gè)體S=101011對(duì)其的第1,4位置的基因進(jìn)行變異,則有S'=001111第四十七頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理變異算子的過程為:BeginRepeat{對(duì)所有交叉算子產(chǎn)生的新子代的個(gè)體數(shù)}產(chǎn)生（0，1）間的隨機(jī)數(shù)s若s小于等于變異概率Pm,則隨機(jī)產(chǎn)生變異位Lm對(duì)個(gè)體i在變異位Lm進(jìn)行變異操作,生成新子代個(gè)體EndEnd第四十八頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理對(duì)變異算子的作用,有如下討論單靠變異不能在求解中得到好處.但是,它能保證算法過程不會(huì)產(chǎn)生無法進(jìn)化的單一群體.在所有的個(gè)體趨向一樣時(shí),交叉是無法產(chǎn)生新的個(gè)體的,這時(shí)只能靠變異產(chǎn)生新的個(gè)體,以保持群體的多樣性,避免早熟.也就是說,變異增加了全局優(yōu)化的特質(zhì).雖然變異概率的增大也會(huì)增加群體的多樣性,但它卻降低了GA的性能,并且隨著變異概率的增大,GA的性能越來越接近于隨機(jī)搜索算法的性能.第四十九頁，共一百一十三頁，2022年，8月28日4.3.2GA的基本原理除前面討論的變異算子外,還有如下常用的變異算子多點(diǎn)變異隨機(jī)變異區(qū)間內(nèi)均勻隨機(jī)取第五十頁，共一百一十三頁，2022年，8月28日4.3.3GA的算法過程基于上述GA的原理和基因操作,可總結(jié)出GA的基本過程.GA的算法流程如右圖所示；其相應(yīng)的算法如下所示.第五十一頁，共一百一十三頁，2022年，8月28日4.3.3GA的算法過程GA算法{chooseanintialpopulationdeterminethefitnessofeachindividualperformselectionrepeatperformcrossoveratcrossoverprobabilityPcperformmutationatcrossoverprobabilityPmdeterminethefitnessofeachindividualperformselectionuntilsomestoppingcriterionapplies}第五十二頁，共一百一十三頁，2022年，8月28日4.3.3GA的算法過程在GA的初始化過程,主要的工作為決定GA的各參數(shù)與初始群體.需確定的GA的主要參數(shù)有:群體規(guī)模交叉概率變異概率對(duì)初始群體,通常以隨機(jī)方法產(chǎn)生.為保證群體的多樣性,以及不遺漏某些基因的遺傳因子,初始群體的離散度應(yīng)較大.問題的最優(yōu)解將通過這些初始假設(shè)解進(jìn)化而求出.第五十三頁，共一百一十三頁，2022年，8月28日4.3.3GA的算法過程選擇、交叉和變異是GA的三種基本操作.群體正是在者三種操作的交替運(yùn)行過程中,得到進(jìn)化(優(yōu)化),提升智能.群體進(jìn)化的結(jié)束的標(biāo)志是群體的某種性能指標(biāo)達(dá)到預(yù)先定義的某種結(jié)束準(zhǔn)則.這里所指的某種結(jié)束準(zhǔn)則一般是指個(gè)體的適應(yīng)度達(dá)到給定的閾值;或者個(gè)體的適應(yīng)度的變化率為零.下圖顯示出選擇、交叉和變異這三種運(yùn)算是如何交替迭代進(jìn)行的.第五十四頁，共一百一十三頁，2022年，8月28日4.3.3GA的算法過程圖3GA原理第五十五頁，共一百一十三頁，2022年，8月28日4.3.3GA的算法過程當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閾值,或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí),則算法的迭代過程收斂、算法結(jié)束.否則,用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體,并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行.圖3中表示了GA的執(zhí)行過程.第五十六頁，共一百一十三頁，2022年，8月28日4.4GA的應(yīng)用GA在很多領(lǐng)域都得到應(yīng)用,如函數(shù)優(yōu)化、NN學(xué)習(xí)、方程求解、控制工程、系統(tǒng)工程、計(jì)算機(jī)科學(xué)等領(lǐng)域.在GA應(yīng)用中,應(yīng)先明確其特點(diǎn)和關(guān)鍵問題,才能對(duì)這種算法深入了解,靈活應(yīng)用,以及進(jìn)一步研究開發(fā).下面分別介紹:GA的特點(diǎn)GA應(yīng)用的關(guān)鍵GA在函數(shù)優(yōu)化中的應(yīng)用GA在組合優(yōu)化中的應(yīng)用第五十七頁，共一百一十三頁，2022年，8月28日4.4.1GA的特點(diǎn)4.1遺傳算法的特點(diǎn)GA在求解優(yōu)化問題中的特點(diǎn)為:群體性與全局性普適性容錯(cuò)性隨機(jī)性下面加以簡單介紹.第五十八頁，共一百一十三頁，2022年，8月28日4.4.1GA的特點(diǎn)(1)群體性與全局性GA從問題解的串集開始嫂索,而不是從單個(gè)解開始.這是GA與傳統(tǒng)優(yōu)化算法的極大區(qū)別.傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的,容易誤入局部最優(yōu)解.GA從串集開始搜索,覆蓋面大,利于全局擇優(yōu),具有較好的全局性.第五十九頁，共一百一十三頁，2022年，8月28日4.4.1GA的特點(diǎn)(2)普適性GA求解時(shí)使用特定問題的信息極少,對(duì)優(yōu)化問題的限制也相應(yīng)較少,容易形成通用算法程序.由于GA使用適應(yīng)值這一信息進(jìn)行搜索,并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息.GA只需適應(yīng)值和串編碼等通用信息,故幾乎可處理任何問題.第六十頁，共一百一十三頁，2022年，8月28日4.4.1GA的特點(diǎn)(3)容錯(cuò)性GA有極強(qiáng)的容錯(cuò)能力GA的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息;通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串;這是一個(gè)強(qiáng)烈的濾波過程;并且是一個(gè)并行濾波機(jī)制.故而,GA有很高的容錯(cuò)能力.第六十一頁，共一百一十三頁，2022年，8月28日4.4.1GA的特點(diǎn)(4)隨機(jī)性GA中的選擇、交叉和變異都是隨機(jī)操作,而不是確定的精確規(guī)則.這說明GA是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索,選擇體現(xiàn)了向最優(yōu)解迫近,交叉體現(xiàn)了最優(yōu)解的產(chǎn)生,變異體現(xiàn)了全局最優(yōu)解的覆蓋.第六十二頁，共一百一十三頁，2022年，8月28日GA在應(yīng)用中最關(guān)鍵的問題有如下3個(gè):(1)串的編碼方式這本質(zhì)是問題編碼.一般把問題的各種參數(shù)用二進(jìn)制編碼,構(gòu)成子串;然后把子串拼接構(gòu)成“染色體”串.串長度及編碼形式對(duì)算法收斂影響極大.4.4.2GA的應(yīng)用關(guān)鍵第六十三頁，共一百一十三頁，2022年，8月28日(2)適應(yīng)函數(shù)的確定適應(yīng)函數(shù)(fitnessfunction)也稱目標(biāo)函數(shù)(objectfunction),這是問題求解品質(zhì)的測(cè)量函數(shù);往往也稱為問題的“環(huán)境”.一般可以把問題的模型函數(shù)作為對(duì)象函數(shù)，但有時(shí)需要另行構(gòu)造.4.4.2GA的應(yīng)用關(guān)鍵第六十四頁，共一百一十三頁，2022年，8月28日(3)GA自身參數(shù)設(shè)定GA自身參數(shù)有3個(gè),即群體大小n、交叉概率Pc和變異概率Pm.群體大小n太小時(shí)難以求出最優(yōu)解,太大則增長收斂時(shí)間.一般n=30~160.交叉概率Pc太小時(shí)難以向前搜索,太大則容易破壞高適應(yīng)值的結(jié)構(gòu).一般取Pc=0.25~.2GA的應(yīng)用關(guān)鍵第六十五頁，共一百一十三頁，2022年，8月28日(3)GA自身參數(shù)設(shè)定變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu),太大使GA成了單純的隨機(jī)搜索.一般取Pm＝0.01~0.2.終止規(guī)則

(a)選定一個(gè)總的遺傳代數(shù):(b)自適應(yīng)終止規(guī)則:保留每一代最好的解,

若干代后,當(dāng)最優(yōu)解的變化不明顯,則停止。4.4.2GA的應(yīng)用關(guān)鍵第六十六頁，共一百一十三頁，2022年，8月28日考慮如下實(shí)函數(shù)的優(yōu)化命題4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用其中x為n維優(yōu)化變量向量.在利用GA對(duì)式(4)所示的函數(shù)優(yōu)化命題進(jìn)行運(yùn)算時(shí),需考慮的問題是:適應(yīng)度函數(shù)由于上述函數(shù)優(yōu)化命題為求極小,因此,在轉(zhuǎn)換成適應(yīng)度函數(shù)時(shí),可采取以下兩種方法.第六十七頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用1）轉(zhuǎn)化成最大化問題,且保證非負(fù)性。

(目標(biāo)函數(shù))C為人為設(shè)定的足夠大的正數(shù)。

2）若能保證g(x)是正的,則

注意：若問題本身是最大化,但不能保證g(x)非負(fù)性第六十八頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用個(gè)體編碼對(duì)該優(yōu)化命題,可采用二進(jìn)制編碼或?qū)崝?shù)編碼.若采用實(shí)數(shù)編碼,則可將變量向量x的每一變量分量變換成0~2L-1間的二進(jìn)制數(shù)(其中L為每個(gè)變量分量對(duì)應(yīng)的二進(jìn)制串的長度).然后將各變量分量所對(duì)應(yīng)的二進(jìn)制串按次序或某種規(guī)則排列策劃功能成GA中的串.第六十九頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用群體規(guī)模、交叉和變異概率對(duì)如何選取群體規(guī)模、交叉和變異概率這些GA所需要的參數(shù),目前還沒有能得到非常具體的選取方法,只有一些經(jīng)驗(yàn)性質(zhì)的指導(dǎo)原則.針對(duì)具體的優(yōu)化問題,需要作具體分析,以及還要依賴于使用者的所掌握的經(jīng)驗(yàn)和技巧.對(duì)交叉和變異概率的選取,有研究人員提出一些自適應(yīng)選取策略,在一定程度上有助于GA的應(yīng)用.但是在GA的優(yōu)化機(jī)理缺乏嚴(yán)格研究的情況下,自適應(yīng)策略的效果也未有嚴(yán)格的分析和證明.第七十頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用下面簡單討論2個(gè)函數(shù)優(yōu)化的GA算例.算例1

用CGA求解如下函數(shù)優(yōu)化問題在該算例中,為簡單便于說明起見,選擇:個(gè)體編碼長度為5位二進(jìn)制群體個(gè)數(shù)為4適應(yīng)度函數(shù)直接為函數(shù)值交叉概率1.0,變異概率0.75(通常變異概率應(yīng)非常小)GA計(jì)算結(jié)果為第七十一頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用初始群體與第一次選擇編號(hào)群體變量函數(shù)值x2選擇百分比期望復(fù)制數(shù)目實(shí)際復(fù)制數(shù)目1234011011100001000100111324819169576643610.14440.49230.05470.30850.57781.96920.21881.23421201和平均值最大值1170292.557610.25000.4923411.9692412第七十二頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用第一次交叉編號(hào)交配池交配對(duì)交配位置新的群體變量函數(shù)值x212340110|111|0001100|010|011{1,3}{2,4}420110011001110111000012252716144625729256和平均值最大值(隨機(jī)產(chǎn)生)(隨機(jī)產(chǎn)生)1754439729第七十三頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用第一次變異編號(hào)交配池變異位置新的群體變量函數(shù)值x212340110|0110|01110111|000043無10111011101110110000014292701968417290和平均值最大值(隨機(jī)產(chǎn)生)1766441.5841第七十四頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用第二次選擇編號(hào)群體變量函數(shù)值x2選擇百分比期望復(fù)制數(shù)目實(shí)際復(fù)制數(shù)目123401110111011101100000142927019684172900.11100.47620.412800.44391.90481.651200220和平均值最大值1766441.584110.25000.4762411.9048412第七十五頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用第二次交叉編號(hào)交配池交配對(duì)交配位置新的群體變量函數(shù)值x21234111|011|1101110|111|1011{1,3}{2,4}311111111101110011101131292527961841625729和平均值最大值(隨機(jī)產(chǎn)生)(隨機(jī)產(chǎn)生)3156789961第七十六頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用算例2用保留最優(yōu)個(gè)體的GA求解如下“peaks”函數(shù)優(yōu)化問題在該算例中,為簡單便于說明起見,選擇:個(gè)體編碼長度為16位二進(jìn)制群體個(gè)數(shù)為40交叉概率0.90,變異概率0.01GA計(jì)算結(jié)果為第七十七頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用函數(shù)的3維圖第七十八頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用Initialpopulation第七十九頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用5thgeneration10thgeneration第八十頁，共一百一十三頁，2022年，8月28日4.4.3GA在函數(shù)優(yōu)化中的應(yīng)用Performanceprofile第八十一頁，共一百一十三頁，2022年，8月28日4.4.4GA在組合優(yōu)化中的應(yīng)用組合優(yōu)化問題大多是一些NP-hard問題,難于求解全局優(yōu)化解.由于GA在具有較好的求取全局解的特性,因此其在組合優(yōu)化中的應(yīng)用非常廣.GA在應(yīng)用于組合優(yōu)化問題時(shí),要注意根據(jù)具體組合優(yōu)化問題的特點(diǎn),因此設(shè)計(jì)如何表示可行解的適宜編碼方案,以及設(shè)計(jì)能產(chǎn)生可行解的遺傳算子(交叉與變異算子)是成功的關(guān)鍵.第八十二頁，共一百一十三頁，2022年，8月28日背包問題的提法：已知n個(gè)物品的容積和價(jià)值分別為wi(>0)和ci(>0)(i=1,2,…,n)，背包的總?cè)萘考僭O(shè)為v(v>0)，如何選擇哪些物品裝入背包使得所裝物品價(jià)值最大？該問題的模型可表示為如下的0-1規(guī)劃問題：背包問題是個(gè)典型的NP完全問題，目前還不存在多項(xiàng)式時(shí)間的算法。4.4.4GA在組合優(yōu)化中的應(yīng)用第八十三頁，共一百一十三頁，2022年，8月28日編碼格式：例如x=1100000000表示僅裝第1和第2種物品適應(yīng)度度量：選擇算子：賭盤選擇（與適應(yīng)值成比例選擇）交叉算子：混合單點(diǎn)交叉變異算子：混合點(diǎn)變異進(jìn)化參數(shù)：{種群規(guī)模，終止進(jìn)化代數(shù)，交叉概率，變異概率}={50，500，0.6，0.05}4.4.4GA在組合優(yōu)化中的應(yīng)用第八十四頁，共一百一十三頁，2022年，8月28日4.4.4GA在組合優(yōu)化中的應(yīng)用其它如8皇后問題,即在n*n格的國際象棋棋盤上放置n個(gè)皇后,使得任意兩個(gè)皇后不能互相攻擊,即任何行、列、對(duì)角線上不得有兩個(gè)或兩個(gè)以上的皇后.這樣的格局稱為問題的一個(gè)解.第八十五頁，共一百一十三頁，2022年，8月28日4.4.4GA在組合優(yōu)化中的應(yīng)用還有前面提到得TSP組合優(yōu)化問題。注意非法解的解決。第八十六頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析GA源于自然選擇和生物遺傳學(xué),相對(duì)于其鮮明的生物基礎(chǔ),GA的理論基礎(chǔ)公認(rèn)是不完善的.GA的基礎(chǔ)理論主要以收斂性分析為主,即群體收斂到優(yōu)化問題的全局最優(yōu)解的概率.理論分析主要是基于模式理論的收斂性分析,稱之為GA的進(jìn)化動(dòng)力學(xué)理論.第八十七頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析

基于某種具體運(yùn)算形式的GA的進(jìn)化行為分析構(gòu)成了進(jìn)化動(dòng)力學(xué)理論的基本內(nèi)容.由Holland提出的模式(Schema,又譯圖式)定理可以稱為GA進(jìn)化動(dòng)力學(xué)的基本定理.模式定理構(gòu)成了求解優(yōu)化問題時(shí)GA具備發(fā)現(xiàn)全局最優(yōu)解的充分條件,也是分析GA的進(jìn)化行為的基本理論,也稱為模式理論.第八十八頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析通過基于模式理論的進(jìn)化動(dòng)力學(xué)分析,我們可以發(fā)現(xiàn)GA所能求解的問題的范圍,找出GA的不足之處,進(jìn)而可能對(duì)其進(jìn)行改進(jìn).第八十九頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析遺傳算法的理論基礎(chǔ)是遺傳算法的二進(jìn)制表達(dá)式及模式的含義。下面簡單介紹模式的概念及模式定理.它的有關(guān)內(nèi)容如下:模式概念模式的階和長度復(fù)制對(duì)群體適應(yīng)值的影響交叉對(duì)模式的影響變異對(duì)模式的影響Holland模式定理第九十頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析A.模式概念定義模式的好處是使我們?nèi)菀酌枋龃南嗨菩?。一個(gè)基因串用符號(hào)集{0,1,*}表示,則稱為一個(gè)模式;其中*是通配符,可以是0或1.即模式是含有通配符(*)的一類字符串的通式表達(dá),例如:H=1**0**是一個(gè)模式.模式*10101110與以下兩個(gè)字符串匹配:010101110110101110而模式*1010＊110與以下四個(gè)字符串匹配:010100110010101110110100110110101110第九十一頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析B.模式的階和長度模式中0和1的個(gè)數(shù)稱為模式的階,并用o(H)表示.模式中第1位數(shù)字(非通配符*)和最后位數(shù)字間的距離稱為模式的長度,并用(H)表示.對(duì)于模式H=1**0**,有o(H)=2,(H)=4.對(duì)于模式H=*0**1*0*,有o(H)=3,(H)=6.第九十二頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析C.復(fù)制對(duì)群體適應(yīng)值的影響假定在給定的時(shí)間步t,一個(gè)特定的模式s在群體P(t)中包含m個(gè)代表串,記為m=m(s,t)。首先,我們暫不考慮交叉和變異操作。每個(gè)串根據(jù)適應(yīng)值的大小獲得不同的復(fù)制概率。串i的復(fù)制概率為:第九十三頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析則在群體P(t+1)中,模式s的代表串的數(shù)量的期望值為:其中

(s,t)表示模式s在t時(shí)刻的所有代表串的適應(yīng)值的均值,稱為模式s的適應(yīng)值。

(t)表示群體P(t)中所有個(gè)體的適應(yīng)值的平均值。上式表明,模式s的代表串的數(shù)目隨時(shí)間增長的幅度正比于模式s的適應(yīng)值與群體平均適應(yīng)值的比值。即:適應(yīng)值高于群體平均值的模式在下一代的代表串?dāng)?shù)目將會(huì)增加,而適應(yīng)值低于群體平均值的模式在下一代的代表串?dāng)?shù)目將會(huì)減少。第九十四頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析假設(shè)模式的適應(yīng)值為(1+c)(t),其中c是一個(gè)常數(shù),則上式可寫為:上式表明,在平均適應(yīng)值之上(之下)的模式,將會(huì)按指數(shù)增長(衰減)的方式被復(fù)制。第九十五頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析復(fù)制的結(jié)果并沒有生成新的模式。因而,為了探索搜索空間中的未搜索部分,需要利用交叉和變異操作。下面分別探索交叉和變異對(duì)模式的影響。第九十六頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析D.交叉對(duì)模式的影響考慮模式s1=“*1****0”和s2=“***10**”間的交叉,可以發(fā)現(xiàn)交叉會(huì)改變模式的一部分,模式的長度越長,被破壞的概率越大。第九十七頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析假定模式s在交叉后不被破壞的概率為ps,則:若交叉概率為pc,則s不被破壞的概率為所以,在考慮交叉時(shí),模式s在群體P(t+1)中的數(shù)目m(s,t+1)的期望值為:第九十八頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析E.變異對(duì)模式的影響變異算子以概率pm隨機(jī)地改變個(gè)體某一位的值。只有當(dāng)o(s)個(gè)確定位(即確定為0或1,而非通配符*)的值不被破壞時(shí),模式s才不被破壞。模式s在變異后不被破壞的概率:Pm<<1,可近似地表示為第九十九頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析因此,考慮交叉和變異時(shí),模式s在群體P(t+1)中的數(shù)目m(s,t+1)的期望值為上式忽略了一項(xiàng)較小的交叉相乘項(xiàng)。由此我們得到一個(gè)關(guān)于GA優(yōu)化性能的重要定理--模式定理(SchemaTheorem)。第一百頁，共一百一十三頁，2022年，8月28日4.5GA的理論分析Holland模式定理模式定理低階,短長度,高適應(yīng)值的模式在群體遺傳過程中將會(huì)按指數(shù)規(guī)律增加.根據(jù)模式定理，隨著遺傳算法的再生、交叉、變異等操作一代接一代地進(jìn)行，那些短的，低階的，高適應(yīng)值的模式將越來越多，最后得到的串即是這些模式的組合。因而可期望算法性能越來越得到改善，并最終向全局的最優(yōu)點(diǎn)發(fā)展。第一百零一頁，共一百一十三頁，2022年，8月28日遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化：在神經(jīng)網(wǎng)絡(luò)用于系統(tǒng)建模和控制時(shí)，它要利用神經(jīng)網(wǎng)絡(luò)的函數(shù)估計(jì)及分類功能。設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)的關(guān)鍵是如何確定神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和連接權(quán)系數(shù)。它實(shí)質(zhì)上也是一個(gè)優(yōu)化問題，其優(yōu)化的目標(biāo)是使得所設(shè)計(jì)的神經(jīng)網(wǎng)絡(luò)功能具有盡可能好的函數(shù)估計(jì)及分類功能。遺傳算法可以用于神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)。

4.6遺傳算法在智能控制中的應(yīng)用第一百零二頁，共一百一十三頁，2022年，8月28日將神經(jīng)網(wǎng)絡(luò)中所有神經(jīng)元的連接權(quán)值編碼成二進(jìn)制碼串或?qū)崝?shù)碼串表示的個(gè)體，隨機(jī)生成這些碼串的初始群體，即可進(jìn)行常規(guī)的遺傳算法優(yōu)化計(jì)算。每進(jìn)行一代計(jì)算后，將碼串解碼為權(quán)值構(gòu)成新的神經(jīng)網(wǎng)絡(luò)，通過對(duì)所有訓(xùn)練樣本進(jìn)行計(jì)算得到神經(jīng)網(wǎng)絡(luò)輸出的均方誤差從而確定每個(gè)個(gè)體的適應(yīng)度。經(jīng)過若干代計(jì)算，神經(jīng)網(wǎng)絡(luò)將進(jìn)化到誤差全局最小。4.6遺傳算法在智能控制中的應(yīng)用第一百零三頁，共一百一十三頁，2022年，8月28日例4.1倒立擺的遺傳神經(jīng)網(wǎng)絡(luò)控制。設(shè)被控對(duì)象為圖示的單倒立擺系統(tǒng)其動(dòng)力學(xué)方程為4.6遺傳算法在智能控制中的應(yīng)用第一百零四頁，共一百一十三頁，2022年，8月28日6.4遺傳算法在智能控制中的應(yīng)用控制系統(tǒng)采用下圖所示結(jié)構(gòu)，其中NNC為神經(jīng)網(wǎng)絡(luò)控制器，該控制器的輸入為θ、、x、，輸出為控制量u?？刂破鞑捎?層前饋神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)，為了避免陷入局部極小，采用遺傳算法確定網(wǎng)絡(luò)的權(quán)值。

第一百零五頁，共一百一十三頁，2022年，8月28日1）神經(jīng)網(wǎng)絡(luò)控制器的結(jié)構(gòu)設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)輸入層有4個(gè)節(jié)點(diǎn)，分別對(duì)應(yīng)于4個(gè)輸入分量θ、、x、；輸出層設(shè)1個(gè)節(jié)點(diǎn)，對(duì)應(yīng)于控制量u；隱層設(shè)10個(gè)節(jié)點(diǎn)。6.4遺傳算法在智能控制中的應(yīng)用2）遺傳算法訓(xùn)練對(duì)神經(jīng)網(wǎng)絡(luò)的所有權(quán)值和閾值采用10進(jìn)制編碼，每個(gè)參數(shù)的變化范圍為[-10，10]，種群規(guī)模為n=50，交叉概率為=0.9，變異概率為=0.03。遺傳算法的適配值取倒立擺系統(tǒng)的穩(wěn)定時(shí)間T（系統(tǒng)穩(wěn)定指擺角不超過±15o）。第一百零六頁，共一百一十三頁，2022年，8月28日遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化，其具體過程如下：(1)采用某種編碼方案對(duì)每個(gè)權(quán)值進(jìn)行編碼，隨機(jī)產(chǎn)生一組權(quán)值編碼；(2)計(jì)算神經(jīng)網(wǎng)絡(luò)的誤差函數(shù)，確定其適應(yīng)度的函數(shù)值，誤差值越大，適配值越??；(3)選擇若干適配值大的個(gè)體直接遺傳給下一代，其余按適配值確定的概率遺傳；(4)利用交叉、變異等操作處理當(dāng)前種群，產(chǎn)生下一代種群；(5)重復(fù)(2)～(3)，直到取得滿意解。

6.4遺傳算法在智能控制中的應(yīng)用第一百零七頁，共一百一十三頁，2022年，8月28日4.7GA的發(fā)展展望GA從60年代末至今已經(jīng)有30余年的發(fā)展歷程,在理論分析、遺傳策略、算法設(shè)計(jì)及應(yīng)用上都取得巨大成就,成為近年在智能理論與優(yōu)化理論領(lǐng)域的一個(gè)非常重要的方法,促進(jìn)了智能理論與優(yōu)化理論領(lǐng)域的發(fā)展.第一百零八頁，共一百一十三頁，2022年，8月28日4.7GA的發(fā)展展望GA所追求的是當(dāng)前群體產(chǎn)生比現(xiàn)有個(gè)體更好個(gè)體的能力,即GA的可進(jìn)化性或稱群體可進(jìn)化性.因此,GA的理論和方法研究也就圍繞著這一目標(biāo)展開.關(guān)于下面五個(gè)問題的回答,就成為GA理論研究的主要方向:GA如何更好地模擬復(fù)雜系統(tǒng)的適應(yīng)性過程和進(jìn)化行為?GA在優(yōu)化問題求解中怎樣才能具備全局收斂性?GA的搜索效率如何評(píng)價(jià)?遺傳策略的設(shè)計(jì)和參數(shù)控制的理論基礎(chǔ)是什么?GA與其他算法如何結(jié)合?第一百零九頁，共一百一十三頁，2022年，8月28日參考文獻(xiàn)[B1]B?ck,T.“EvolutionaryAlgorithmsinTheoryandPractice”O(jiān)xfordUniversityPress,NewYork,1996[B2]B?ck,T.,Hammel,U.,andSchwefel,H.-P.(1997).“EvolutionaryComputation:CommentsontheHistoryandCurrentState,”IEEETransactionsonEvolutionaryComputation,VOL.1,NO.1,April1997.[B2]MaartenBoerlijstandPaulineHogeweg(1991).Spiralwavestructureinpre-bioticevolution:Hypercyclesstableagainstparasites.PhysicaD,48:17-28.*[B4]SethBullockandDaveCliff(1997).Theroleof‘hiddenpreferences’intheartificialco-evolutionofsymmetricalsignals,ProceedingsoftheRoyalSocietyofLondon,SeriesB,264:505-511.[C1]DaveCliffandGeoffreyMiller(1995).TrackingtheRedQueen:Measurementsofadaptiveprogressinco-evolutionarysimulations.InF.Morán,A.Moreno,J.J.MoreloandP.Chacón(Eds.),Proceedingsofthe3rdEuropeanConferenceonArtificialLife,pp.200-218.Springer.[D1]RichardDawkinsandJohnKrebs(1979).Armsracesbetweenandwithinspecies.ProceedingoftheRoyalSocietyofLondonB,205:489-511.*第一百一十頁，共一百一十三頁，2022年，8月28日參考文獻(xiàn)[E1]MagnusEnquistandAnthonyArak(1994).Symmetry,Beauty,andEvolution,Nature,372:169-172.[F1]Freeman,ScottandHerron,Jon.C.EvolutionaryAnalysis2ndedition,Prentice-Hall2001.Goodbookonevolution.[G1]Gold