常用數(shù)學(xué)建模算法

數(shù)學(xué)建模中的常用算法成都信息工程學(xué)院計(jì)算科學(xué)系胡建成

jianchenghu@163.com2009-5-20

2/6/2023數(shù)學(xué)建模競(jìng)賽網(wǎng)上資源CUMCM網(wǎng)站:

MCM和ICM網(wǎng)站:

http://中國(guó)數(shù)學(xué)建模:

中科大建模網(wǎng)站:

http://MATLAB網(wǎng)站:

GOOGLE大學(xué)2/6/2023數(shù)學(xué)建模競(jìng)賽中的算法(1)93A非線性交調(diào)的頻率設(shè)計(jì):擬合、規(guī)劃93B足球隊(duì)排名次:矩陣論、圖論、層次分析法、整數(shù)規(guī)劃94A逢山開(kāi)路:圖論、插值、動(dòng)態(tài)規(guī)劃94B鎖具裝箱問(wèn)題:圖論、組合數(shù)學(xué)95A飛行管理問(wèn)題

:非線性規(guī)劃、線性規(guī)劃95B天車(chē)與冶煉爐的作業(yè)調(diào)度:非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、層次分析法、PETRI方法、圖論方法、排隊(duì)論方法96A最優(yōu)捕魚(yú)策略：微分方程、積分、非線性規(guī)劃2/6/202396B節(jié)水洗衣機(jī)：非線性規(guī)劃97A零件參數(shù)設(shè)計(jì)：微積分、非線性規(guī)劃、隨機(jī)模擬97B截?cái)嗲懈睿航M合優(yōu)化、幾何變換、枚舉、蒙特卡羅、遞歸、最短路98A投資收益與風(fēng)險(xiǎn)：線性規(guī)劃、非線性規(guī)劃98B災(zāi)情巡視：最小生成樹(shù)、Hamilton圈、旅行商問(wèn)題99A自動(dòng)化車(chē)床：積分、概率分布、隨機(jī)模擬、分布擬合度檢驗(yàn)數(shù)學(xué)建模競(jìng)賽中的算法(2)2/6/202399B鉆井布局：幾何變換、最大完全子圖、混合整數(shù)規(guī)劃（0-1規(guī)劃、圖論）00ADNA分類(lèi)：神經(jīng)網(wǎng)絡(luò)、最小二乘擬合、統(tǒng)計(jì)分類(lèi)、模式識(shí)別、Fisher判別00B管道訂購(gòu)：最短路、二次規(guī)劃01A血管的三維重建：數(shù)據(jù)挖掘、曲面重建與擬合01B公交車(chē)調(diào)度：非線性規(guī)劃02A車(chē)燈光源優(yōu)化設(shè)計(jì)：最優(yōu)化02B彩票中的數(shù)學(xué)：概率與優(yōu)化、單目標(biāo)決策數(shù)學(xué)建模競(jìng)賽中的算法(3)2/6/202303A

SARS的傳播：微分方程、差分方程03B露天礦生產(chǎn)的車(chē)輛安排：整數(shù)規(guī)劃、運(yùn)輸問(wèn)題04A奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)：統(tǒng)計(jì)分析、數(shù)據(jù)處理、優(yōu)化04B電力市場(chǎng)的輸電阻塞管理：數(shù)據(jù)擬合、優(yōu)化05A長(zhǎng)江水質(zhì)的評(píng)價(jià)和預(yù)測(cè)：預(yù)測(cè)評(píng)價(jià)、數(shù)據(jù)處理05BDVD在線租賃：隨機(jī)規(guī)劃、整數(shù)規(guī)劃06A出版社資源配置：預(yù)測(cè)評(píng)價(jià)、數(shù)據(jù)處理06B艾滋病療法的評(píng)價(jià)及療效預(yù)測(cè)：隨機(jī)規(guī)劃、整數(shù)規(guī)劃、回歸分析數(shù)學(xué)建模競(jìng)賽中的算法(3)2/6/202307A中國(guó)人口預(yù)測(cè)：微分方程、數(shù)據(jù)處理、優(yōu)化07B公交車(chē)問(wèn)題：多目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論、0-1規(guī)劃08A照相機(jī)定位：非線性方程組、優(yōu)化08B大學(xué)學(xué)費(fèi)標(biāo)準(zhǔn)：數(shù)據(jù)收集和處理、統(tǒng)計(jì)分析、回歸分析09A制動(dòng)器試驗(yàn)臺(tái)的控制方法分析：微元分析法09B眼科病床的合理安排：層次分析法、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃10A儲(chǔ)油罐的變位識(shí)別與罐容表標(biāo)定：非線性規(guī)劃、多元擬合數(shù)學(xué)建模競(jìng)賽中的算法(3)2/6/202310B上海世博會(huì)影響力的定量評(píng)估：數(shù)據(jù)收集和處理，層次分析法、時(shí)間序列分析11A城市表層土壤重金屬污染分析：數(shù)值分析、偏微分方程、數(shù)據(jù)收集處理11B交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度：多目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、0-1規(guī)劃、圖論12A葡萄酒的評(píng)價(jià)：多元回歸分析、數(shù)據(jù)處理12B太陽(yáng)能小屋的設(shè)計(jì)：數(shù)據(jù)處理、非線性規(guī)劃、計(jì)算機(jī)模擬13A車(chē)道被占用對(duì)城市道路通行能力的影響：數(shù)據(jù)得收集與處理、統(tǒng)計(jì)分析13B碎紙片拼接復(fù)原問(wèn)題：數(shù)學(xué)建模競(jìng)賽中的算法(3)2/6/2023

幾何理論

組合概率

統(tǒng)計(jì)（回歸）分析

優(yōu)化方法（規(guī)劃）

圖論與網(wǎng)絡(luò)優(yōu)化

層次分析

插值與擬合

差分方法

微分方程

排隊(duì)論數(shù)學(xué)建模方法2/6/2023

模糊數(shù)學(xué)

隨機(jī)決策

對(duì)目標(biāo)決策

隨機(jī)模擬

灰色系統(tǒng)理論

神經(jīng)網(wǎng)絡(luò)

時(shí)間序列

綜合評(píng)價(jià)

機(jī)理分析

數(shù)學(xué)建模方法2/6/2023

MATLAB

Maple

Mathematica

Lindo

Lingo

SAS

SPSS

C&C++

Fortran

Pascal數(shù)學(xué)建模常用軟件2/6/20231.

蒙特卡羅方法(Monte-Carlo方法,MC)數(shù)學(xué)建模競(jìng)賽常用算法(1)

該算法又稱(chēng)計(jì)算機(jī)隨機(jī)性模擬方法，也稱(chēng)統(tǒng)計(jì)試驗(yàn)方法。MC方法是一種基于“隨機(jī)數(shù)”的計(jì)算方法，能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程，解決一些數(shù)值方法難以解決的問(wèn)題。

MC方法的雛型可以追溯到十九世紀(jì)后期的蒲豐隨機(jī)投針試驗(yàn)，即著名的蒲豐問(wèn)題。MC方法通過(guò)計(jì)算機(jī)仿真(模擬)解決問(wèn)題，同時(shí)也可以通過(guò)模擬來(lái)檢驗(yàn)自己模型的正確性，是比賽中經(jīng)常使用的方法。2/6/202397年的A題每個(gè)零件都有自己的標(biāo)定值，也都有自己的容差等級(jí)，而求解最優(yōu)的組合方案將要面對(duì)著的是一個(gè)極其復(fù)雜的公式和108種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機(jī)性模擬搜索最優(yōu)方案就是其中的一種方法，在每個(gè)零件可行的區(qū)間中按照正態(tài)分布隨機(jī)的選取一個(gè)標(biāo)定值和選取一個(gè)容差值作為一種方案，然后通過(guò)蒙特卡羅算法仿真出大量的方案，從中選取一個(gè)最佳的。02年的B題關(guān)于彩票第二問(wèn)，要求設(shè)計(jì)一種更好的方案，首先方案的優(yōu)劣取決于很多復(fù)雜的因素，同樣不可能刻畫(huà)出一個(gè)模型進(jìn)行求解，只能靠隨機(jī)仿真模擬。數(shù)學(xué)建模競(jìng)賽常用算法2/6/202398年美國(guó)賽A題

生物組織切片的三維插值處理94年A題逢山開(kāi)路

山體海拔高度的插值計(jì)算數(shù)學(xué)建模競(jìng)賽常用算法(2)2.數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。與圖形處理有關(guān)的問(wèn)題很多與擬合有關(guān)系。此類(lèi)問(wèn)題在MATLAB中有很多函數(shù)可以調(diào)用，只有熟悉MATLAB，這些方法才能用好。2/6/202398年B題用很多不等式完全可以把問(wèn)題刻畫(huà)清楚數(shù)學(xué)建模競(jìng)賽常用算法(3)3.規(guī)劃類(lèi)問(wèn)題算法此類(lèi)問(wèn)題主要有線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等。競(jìng)賽中很多問(wèn)題都和數(shù)學(xué)規(guī)劃有關(guān)，可以說(shuō)不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問(wèn)題，遇到這類(lèi)問(wèn)題，求解就是關(guān)鍵了。因此列舉出規(guī)劃后用Lindo、Lingo等軟件來(lái)進(jìn)行解決比較方便，所以還需要熟悉這兩個(gè)軟件。2/6/202398年B題、00年B題、95年鎖具裝箱等問(wèn)題體現(xiàn)了圖論問(wèn)題的重要性。數(shù)學(xué)建模競(jìng)賽常用算法(4)4.

圖論問(wèn)題

這類(lèi)問(wèn)題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問(wèn)題。2/6/202392年B題用分枝定界法97年B題是典型的動(dòng)態(tài)規(guī)劃問(wèn)題98年B題體現(xiàn)了分治算法數(shù)學(xué)建模競(jìng)賽常用算法(5)5.計(jì)算機(jī)算法設(shè)計(jì)中的問(wèn)題

計(jì)算機(jī)算法設(shè)計(jì)包括很多內(nèi)容：動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分枝定界等計(jì)算機(jī)算法.

這方面問(wèn)題和ACM程序設(shè)計(jì)競(jìng)賽中的問(wèn)題類(lèi)似，可看一下與計(jì)算機(jī)算法有關(guān)的書(shū)。2/6/202397年A題用模擬退火算法00年B題用神經(jīng)網(wǎng)絡(luò)分類(lèi)算法01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò)美國(guó)89年A題也和BP算法有關(guān)系美國(guó)03年B題伽馬刀問(wèn)題也是目前研究的課題，目前算法最佳的是遺傳算法。數(shù)學(xué)建模競(jìng)賽常用算法(6)6.最優(yōu)化理論的三大非經(jīng)典算法:

模擬退火法(SA)、神經(jīng)網(wǎng)絡(luò)(NN)、遺傳算法(GA)近幾年的賽題越來(lái)越復(fù)雜，很多問(wèn)題沒(méi)有什么很好的模型可以借鑒，于是這三類(lèi)算法很多時(shí)候可以派上用場(chǎng)。2/6/202397年A題、99年B題都可以用網(wǎng)格法搜索數(shù)學(xué)建模競(jìng)賽常用算法(7)網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問(wèn)題的窮舉。此類(lèi)算法運(yùn)算量較大。7.網(wǎng)格算法和窮舉算法這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行，還有要用高級(jí)語(yǔ)言來(lái)做，最好不要用MATLAB做網(wǎng)格，否則會(huì)算很久的。2/6/2023很多問(wèn)題都是實(shí)際來(lái)的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只能處理離散的數(shù)據(jù)，因此需要將連續(xù)問(wèn)題進(jìn)行離散化處理后再用計(jì)算機(jī)求解。比如差分代替微分、求和代替積分等思想都是把連續(xù)問(wèn)題離散化的常用方法。數(shù)學(xué)建模競(jìng)賽常用算法(8)8.連續(xù)問(wèn)題離散化的方法2/6/2023數(shù)值分析研究各種求解數(shù)學(xué)問(wèn)題的數(shù)值計(jì)算方法，特別是適合于計(jì)算機(jī)實(shí)現(xiàn)方法與算法。數(shù)學(xué)建模競(jìng)賽常用算法(9)9.數(shù)值分析方法它的主要內(nèi)容包括函數(shù)的數(shù)值逼近、數(shù)值微分與數(shù)值積分、非線性方程的數(shù)值解法、數(shù)值代數(shù)、常微分方程數(shù)值解等。數(shù)值分析是計(jì)算數(shù)學(xué)的一個(gè)重要分支，把理論與計(jì)算緊密結(jié)合,是現(xiàn)代科學(xué)計(jì)算的基礎(chǔ)。

MATLAB等數(shù)學(xué)軟件中已經(jīng)有很多數(shù)值分析的函數(shù)可以直接調(diào)用。2/6/202301年A題中需要你會(huì)讀BMP圖象98年美國(guó)A題需要你知道三維插值計(jì)算03年B題要求更高，不但需要編程計(jì)算還要進(jìn)行處理數(shù)學(xué)建模競(jìng)賽常用算法(10)10.圖象處理算法賽題中有一類(lèi)問(wèn)題與圖形有關(guān)，即使問(wèn)題與圖形無(wú)關(guān)，論文中也會(huì)需要圖片來(lái)說(shuō)明問(wèn)題，這些圖形如何展示以及如何處理就是需要解決的問(wèn)題，通常使用MATLAB進(jìn)行處理。數(shù)模論文中也有很多圖片需要展示，解決這類(lèi)問(wèn)題要熟悉MATLAB圖形圖像工具箱。2/6/2023三個(gè)孩子的年齡(1)兩個(gè)多年未見(jiàn)的朋友相遇，聊了很多事情?！瑼：既然你是數(shù)學(xué)教授，那你幫我算這個(gè)題，今天是個(gè)特殊日子：我三個(gè)兒子都在今天慶祝生日！那么你能算出他們都有多大嗎？B：好，但你得跟我講講他們的情況。A：好的，我給你一些提示，他們?nèi)齻€(gè)年齡之積是36.B：很好，但我還需要更多提示。2/6/2023三個(gè)孩子的年齡(2)A：我的大兒子的眼睛是藍(lán)色的。B考慮了一下說(shuō)，但是，我還有一點(diǎn)信息來(lái)解決你的這個(gè)難題。B：哦，夠了，B給出了正確的答案，即三個(gè)小孩的年齡。A：他們?nèi)齻€(gè)年齡之和等于那幢房子的窗戶個(gè)數(shù)。A指著對(duì)面的一幢房子說(shuō)。2/6/2023三個(gè)孩子的年齡(3)根據(jù)對(duì)話信息，用搜索的方法來(lái)解此問(wèn)題。信息1:三個(gè)小孩年齡之積為36只有以下8種可能，搜索范圍減少至8種情況:第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡111121232/6/2023三個(gè)孩子的年齡(4)信息2:三個(gè)小孩年齡之和等于窗戶數(shù)第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123窗戶數(shù):3821161413131110如果窗戶數(shù)為38、21、16、14、11、10即可得出答案B還需信息，即窗戶數(shù)為13.則可能為(9、2、2)或(6、6、1)信息2:大兒子眼睛是藍(lán)色的得答案：(9、2、2)2/6/2023智能優(yōu)化算法

智能優(yōu)化算法又稱(chēng)為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù),而不是單純憑借專(zhuān)家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。2/6/2023常用的智能優(yōu)化算法

遺傳算法

GeneticAlgorithm，簡(jiǎn)稱(chēng)GA模擬退火算法

SimulatedAnnealing，簡(jiǎn)稱(chēng)SA禁忌搜索算法

TabuSearch，簡(jiǎn)稱(chēng)TS……2/6/2023智能優(yōu)化算法的特點(diǎn)它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問(wèn)題空間，因而具有全局優(yōu)化性能。2/6/2023遺傳算法(GeneticAlgorithm)進(jìn)化算法(EvolutionaryAlgorithm)2/6/2023遺傳算法(GA)Darwin(1859):“物竟天擇，適者生存”JohnHolland(universityofMichigan,1975)

《AdaptationinNaturalandArtificialSystem》遺傳算法作為一種有效的工具，已廣泛地應(yīng)用于最優(yōu)化問(wèn)題求解之中。遺傳算法是一種基于自然群體遺傳進(jìn)化機(jī)制的自適應(yīng)全局優(yōu)化概率搜索算法。它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過(guò)程，采用人工的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。2/6/2023遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。遺傳算法的搜索機(jī)制2/6/2023局部全局遺傳算法(GA)2/6/2023Wehaveadream!!IamatthetopHeightis...Iamnotatthetop.Myhighisbetter!Iwillcontinue遺傳算法(GA)GA-----第0代2/6/2023DeadoneNewone遺傳算法(GA)GA----第1代2/6/2023Notatthetop,ComeUp!!!遺傳算法(GA)GA----第?代2/6/2023IamtheBEST!!!遺傳算法(GA)GA----第N代2/6/2023適者生存(SurvivaloftheFittest)GA主要采用的進(jìn)化規(guī)則是“適者生存”較好的解保留，較差的解淘汰遺傳算法(GA)2/6/2023生物進(jìn)化與遺傳算法對(duì)應(yīng)關(guān)系生物進(jìn)化遺傳算法適者生存適應(yīng)函數(shù)值最大的解被保留的概率最大個(gè)體問(wèn)題的一個(gè)解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據(jù)適應(yīng)函數(shù)選擇的一組解交叉以一定的方式由雙親產(chǎn)生后代的過(guò)程變異編碼的某些分量發(fā)生變化的過(guò)程環(huán)境適應(yīng)函數(shù)2/6/2023遺傳算法的基本操作選擇(selection):

根據(jù)各個(gè)個(gè)體的適應(yīng)值，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。交叉(crossover):

將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一個(gè)個(gè)體，以某個(gè)概率Pc

(稱(chēng)為交叉概率，crossvoerrate)交換它們之間的部分染色體。變異(mutation):

對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率Pm(稱(chēng)為變異概率，mutationrate)改變某一個(gè)或一些基因座上基因值為其它的等位基因。2/6/2023如何設(shè)計(jì)遺傳算法如何進(jìn)行編碼？如何產(chǎn)生初始種群？如何定義適應(yīng)函數(shù)？如何進(jìn)行遺傳操作(復(fù)制、交叉、變異)？如何產(chǎn)生下一代種群？如何定義停止準(zhǔn)則？2/6/2023編碼(Coding)表現(xiàn)型空間編碼(Coding)解碼(Decoding)基因型空間={0,1}L01110100101000100110010010100100012/6/2023選擇(Selection)選擇(復(fù)制)操作把當(dāng)前種群的染色體按與適應(yīng)值成正比例的概率復(fù)制到新的種群中

主要思想:適應(yīng)值較高的染色體體有較大的選擇(復(fù)制)機(jī)會(huì)實(shí)現(xiàn)1：”輪盤(pán)賭”選擇(Roulettewheelselection)將種群中所有染色體的適應(yīng)值相加求總和，染色體適應(yīng)值按其比例轉(zhuǎn)化為選擇概率Ps產(chǎn)生一個(gè)在0與總和之間的的隨機(jī)數(shù)m從種群中編號(hào)為1的染色體開(kāi)始，將其適應(yīng)值與后續(xù)染色體的適應(yīng)值相加，直到累加和等于或大于m2/6/2023選擇(Selection)設(shè)種群的規(guī)模為Nxi是i為種群中第i個(gè)染色體AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色體xi被選概率2/6/2023選擇(Selection)染色體的適應(yīng)值和所占的比例輪盤(pán)賭選擇2/6/2023選擇(Selection)隨機(jī)數(shù)23491338627所選號(hào)碼262514所選染色體110000001111000011000111010010染色體編號(hào)123456染色體011101100000100100100110000011適應(yīng)度81525128被選概率6適應(yīng)度累計(jì)8

23

2530

42

50染色體被選的概率被選的染色體2/6/2023選擇(Selection)輪盤(pán)上的片分配給群體的染色體，使得每一個(gè)片的大小與對(duì)于染色體的適應(yīng)值成比例從群體中選擇一個(gè)染色體可視為旋轉(zhuǎn)一個(gè)輪盤(pán)，當(dāng)輪盤(pán)停止時(shí)，指針?biāo)傅钠瑢?duì)于的染色體就時(shí)要選的染色體。模擬“輪盤(pán)賭”算法：r=random(0,1)，s=0，i=0；如果s≥r，則轉(zhuǎn)(4)；s=s+p(xi)，i=i+1,轉(zhuǎn)(2)xi即為被選中的染色體，輸出I結(jié)束2/6/2023選擇(Selection)其他選擇法：隨機(jī)遍歷抽樣(Stochasticuniversalsampling)局部選擇(Localselection)截?cái)噙x擇(Truncationselection)競(jìng)標(biāo)賽選擇(Tournamentselection)特點(diǎn)：選擇操作得到的新的群體稱(chēng)為交配池，交配池是當(dāng)前代和下一代之間的中間群體，其規(guī)模為初始群體規(guī)模。選擇操作的作用效果是提高了群體的平均適應(yīng)值(低適應(yīng)值個(gè)體趨于淘汰，高適應(yīng)值個(gè)體趨于選擇)，但這也損失了群體的多樣性。選擇操作沒(méi)有產(chǎn)生新的個(gè)體，群體中最好個(gè)體的適應(yīng)值不會(huì)改變。2/6/2023交叉(crossover,Recombination)遺傳交叉(雜交、交配、有性重組)操作發(fā)生在兩個(gè)染色體之間，由兩個(gè)被稱(chēng)之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個(gè)具有雙親的部分基因的新的染色體，從而檢測(cè)搜索空間中新的點(diǎn)。選擇(復(fù)制)操作每次作用在一個(gè)染色體上，而交叉操作每次作用在從交配池中隨機(jī)選取的兩個(gè)個(gè)體上(交叉概率Pc)。交叉產(chǎn)生兩個(gè)子染色體，他們與其父代不同，且彼此不同,每個(gè)子染色體都帶有雙親染色體的遺傳基因。2/6/2023單點(diǎn)交叉(1-pointcrossover)在雙親的父代染色體中隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)位置在交叉點(diǎn)位置分離雙親染色體互換交叉點(diǎn)位置右邊的基因碼產(chǎn)生兩個(gè)子代染色體交叉概率Pc

一般范圍為(60%,90%)，平均約80%11111111父代1111000000000000子代111100000000000011111111交叉點(diǎn)位置2/6/2023交叉(crossover,Recombination)單點(diǎn)交叉操作可以產(chǎn)生與父代染色體完全不同的子代染色體；它不會(huì)改變父代染色體中相同的基因。但當(dāng)雙親染色體相同時(shí)，交叉操作是不起作用的。假如交叉概率Pc

＝50%,則交配池中50%的染色體(一半染色體)將進(jìn)行交叉操作，余下的50%的染色體進(jìn)行選擇(復(fù)制)操作。GA利用選擇和交叉操作可以產(chǎn)生具有更高平均適應(yīng)值和更好染色體的群體2/6/2023變異(Mutation)以變異概率Pm改變?nèi)旧w的某一個(gè)基因,當(dāng)以二進(jìn)制編碼時(shí)，變異的基因由0變成1，或者由1變成0。變異概率Pm一般介于1/種群規(guī)模與1/染色體長(zhǎng)度之間，平均約1-2%11010100父代01010101子代變異基因變異基因2/6/2023變異(Mutation)比起選擇和交叉操作，變異操作是GA中的次要操作，但它在恢復(fù)群體中失去的多樣性方面具有潛在的作用。

在GA執(zhí)行的開(kāi)始階段，染色體中一個(gè)特定位上的值1可能與好的性能緊密聯(lián)系，即搜索空間中某些初始染色體在那個(gè)位上的值1可能一致產(chǎn)生高的適應(yīng)值。因?yàn)樵礁叩倪m應(yīng)值與染色體中那個(gè)位上的值1相聯(lián)系，選擇操作就越會(huì)使群體的遺傳多樣性損失。等到達(dá)一定程度時(shí)，值0會(huì)從整個(gè)群體中那個(gè)位上消失，然而全局最優(yōu)解可能在染色體中那個(gè)位上為0。如果搜索范圍縮小到實(shí)際包含全局最優(yōu)解的那部分搜索空間，在那個(gè)位上的值0就可能正好是到達(dá)全局最優(yōu)解所需要的。2/6/2023適應(yīng)函數(shù)(FitnessFunction)GA在搜索中不依靠外部信息，僅以適應(yīng)函數(shù)為依據(jù)，利用群體中每個(gè)染色體(個(gè)體)的適應(yīng)值來(lái)進(jìn)行搜索。以染色體適應(yīng)值的大小來(lái)確定該染色體被遺傳到下一代群體中的概率。染色體適應(yīng)值越大，該染色體被遺傳到下一代的概率也越大；反之，染色體的適應(yīng)值越小，該染色體被遺傳到下一代的概率也越小。因此適應(yīng)函數(shù)的選取至關(guān)重要，直接影響到GA的收斂速度以及能否找到最優(yōu)解。群體中的每個(gè)染色體都需要計(jì)算適應(yīng)值適應(yīng)函數(shù)一般由目標(biāo)函數(shù)變換而成2/6/2023適應(yīng)函數(shù)(FitnessFunction)適應(yīng)函數(shù)常見(jiàn)形式：直接將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)函數(shù)若目標(biāo)函數(shù)為最大化問(wèn)題：

Fitness(f(x))=f(x)若目標(biāo)函數(shù)為最小化問(wèn)題：

Fitness(f(x))=-f(x)缺點(diǎn):(1)可能不滿足輪盤(pán)賭選擇中概率非負(fù)的要求

(2)某些代求解的函數(shù)值分布上相差很大，由此得到的評(píng)價(jià)適應(yīng)值可能不利于體現(xiàn)群體的評(píng)價(jià)性能，影響算法的性能。2/6/2023適應(yīng)函數(shù)(FitnessFunction)界限構(gòu)造法

目標(biāo)函數(shù)為最大化問(wèn)題其中Cmin為f(x)的最小估計(jì)值目標(biāo)函數(shù)為最小化問(wèn)題其中Cmaxn為f(x)的最大估計(jì)值2/6/2023停止準(zhǔn)則(TerminationCriteria)種群中個(gè)體的最大適應(yīng)值超過(guò)預(yù)設(shè)定值種群中個(gè)體的平均適應(yīng)值超過(guò)預(yù)設(shè)定值種群中個(gè)體的進(jìn)化代數(shù)超過(guò)預(yù)設(shè)定值2/6/2023基本步驟(StepbyStep)(1)隨機(jī)產(chǎn)生初始種群;(2)計(jì)算種群體中每個(gè)個(gè)體的適應(yīng)度值,判斷是否滿足停止條件，若不滿足，則轉(zhuǎn)第(3)步,否則轉(zhuǎn)第(6)步;(3)按由個(gè)體適應(yīng)值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體;(4)按交叉概率Pc進(jìn)行交叉操作,生產(chǎn)新的個(gè)體;(5)按變異概率Pm進(jìn)行變異操作,生產(chǎn)新的個(gè)體;(6)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。2/6/2023流程圖(FlowChart)2/6/2023基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms,簡(jiǎn)稱(chēng)SGA）是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。2/6/2023SGA偽碼描述ProcedureGeneticAlgorithm

begint=0;初始化P(t);計(jì)算P(t)的適應(yīng)值;while(不滿足停止準(zhǔn)則)dobegint=t+1;

從P(t-1)中選擇P(t);%selection

重組P(t);%crossoverandmutation

計(jì)算P(t)的適應(yīng)值;end

end2/6/2023遺傳算法的應(yīng)用函數(shù)優(yōu)化

函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能測(cè)試評(píng)價(jià)的常用算例。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴(lài)于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類(lèi)有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面列舉一些遺傳算法的主要應(yīng)用領(lǐng)域。2/6/2023遺傳算法的應(yīng)用組合優(yōu)化

遺傳算法是尋求組合優(yōu)化問(wèn)題滿意解的最佳工具之一，實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化問(wèn)題中的NP完全問(wèn)題非常有效。例如，遺傳算法已經(jīng)在求解旅行商問(wèn)題(TravelingSalesmanProblem,TSP)、背包問(wèn)題(KnapsackProblem)、裝箱問(wèn)題(BinPackingProblem)等方面得到成功的應(yīng)用。生產(chǎn)調(diào)度問(wèn)題

生產(chǎn)調(diào)度問(wèn)題在很多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解也會(huì)因簡(jiǎn)化得太多而使求解結(jié)果與實(shí)際相差太遠(yuǎn)。現(xiàn)在遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問(wèn)題的有效工具。2/6/2023遺傳算法的應(yīng)用自動(dòng)控制

遺傳算法已經(jīng)在自動(dòng)控制領(lǐng)域中得到了很好的應(yīng)用，例如基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等。機(jī)器人智能控制

機(jī)器人是一類(lèi)復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制自然成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。

2/6/2023遺傳算法的應(yīng)用圖象處理和模式識(shí)別

圖像處理和模式識(shí)別是計(jì)算機(jī)視覺(jué)中的一個(gè)重要研究領(lǐng)域。在圖像處理過(guò)程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺(jué)達(dá)到實(shí)用化的重要要求，遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面得到了很好的應(yīng)用。人工生命

人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)。2/6/2023遺傳算法的應(yīng)用遺傳程序設(shè)計(jì)

Koza發(fā)展了遺傳程序設(shè)計(jì)的概念，他使用了以LISP語(yǔ)言所表示的編碼方法，基于對(duì)一種樹(shù)形結(jié)構(gòu)所進(jìn)行的遺傳操作來(lái)自動(dòng)生成計(jì)算機(jī)程序。

機(jī)器學(xué)習(xí)

基于遺傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。例如基于遺傳算法的機(jī)器學(xué)習(xí)可用來(lái)調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可以用于人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)。分類(lèi)器系統(tǒng)在多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。2/6/2023SGA實(shí)例1：函數(shù)最值SGA參數(shù):編碼方式:二進(jìn)制碼

e.g.000000;0110113;1111131種群規(guī)模:4隨機(jī)初始群體“轉(zhuǎn)盤(pán)賭”選擇一點(diǎn)雜交,二進(jìn)制變異

求函數(shù)f(x)=x2的最大值，x為自然數(shù)且0≤x≤31.手工方式完成演示SGA過(guò)程2/6/2023SGA實(shí)例1maxx2:選擇操作2/6/2023SGA實(shí)例1maxx2:交叉操作2/6/2023SGA實(shí)例1maxx2:變異操作2/6/2023SGA實(shí)例2:連續(xù)函數(shù)最值求下列函數(shù)的最大值：2/6/2023SGA實(shí)例2:編碼高精度

編碼

[x,y]{0,1}L

必須可逆(一個(gè)表現(xiàn)型對(duì)應(yīng)一個(gè)基因型)

解碼算子：:{0,1}L

[x,y]

染色體長(zhǎng)度L決定可行解的最大精度長(zhǎng)染色體(慢進(jìn)化)

實(shí)數(shù)問(wèn)題：變量z為實(shí)數(shù)，如何把{a1,…,aL}

{0,1}Lz∈[x,y]2/6/2023SGA實(shí)例2:編碼設(shè)定求解精確到6位小數(shù)，因區(qū)間長(zhǎng)度位2-(-1)=3,則需將區(qū)間分為3X106等份。因2097152＝221<3X106≤222＝4194304。故編碼的二進(jìn)制串長(zhǎng)L=22。將一個(gè)二進(jìn)制串(b21b20…b0)轉(zhuǎn)化為10進(jìn)制數(shù)：e.g.<0000000000000000000000>-1;<1111111111111111111111>2<1110000000111111000101>1.6278881.627888=-1+3x(1110000000111111000101)2

/(222-1)=-1+3x3674053/(222-1)2/6/2023SGA實(shí)例2:初始化種群、適應(yīng)函數(shù)隨機(jī)初始化種群適應(yīng)函數(shù)本實(shí)例目標(biāo)函數(shù)在定義域內(nèi)均大于0，且是求函數(shù)最大值，故直接引用目標(biāo)函數(shù)作為適應(yīng)函數(shù)：

f(s)=f(x)

其中二進(jìn)制串s對(duì)于變量x的值。

e.g.s1=<0000001110000000010000>x1=-0.958973

適應(yīng)值:f(s1)=f(x1)=1.078878

s2=<1110000000111111000101>x2=1.627888

適應(yīng)值:f(s2)=f(x2)=3.2506502/6/2023SGA實(shí)例2:遺傳操作選擇操作(“輪盤(pán)賭”選擇)交叉操作(單點(diǎn)交叉)

交叉前(父):

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

交叉后(子):

s’1=<00000|

00000111111000101>s’2=<11100|

01110000000010000>

適應(yīng)值:f(s’1)=f(-0.998113)=1.940865f(s’2)=f(1.666028)=3.459245

s’2的適應(yīng)值比其雙親個(gè)體的適應(yīng)值高。2/6/2023SGA實(shí)例2:遺傳操作變異操作

變異前(父):

s2=<1110000000111111000101>

變異后(子):

s’2=<1110100000111111000101>

適應(yīng)值

f(s’2)=f(1.721638)=0.917743

比f(wàn)(s2)小

變異前(父):

s2=<1110000000111111000101>

變異后(子):

s”2=<1110000001111111000101>

適應(yīng)值

f(s”2)=f(1.630818)=3.343555比f(wàn)(s2)大變異操作有”擾動(dòng)”作用，同時(shí)具有增加種群多樣性的效果。2/6/2023SGA實(shí)例2:模擬結(jié)果遺傳算法的參數(shù):

種群規(guī)模:50

染色體長(zhǎng)度:L=22

最大進(jìn)化代數(shù):150

交叉概率:Pc=0.25

變異概率:Pm=0.01

2/6/2023SGA實(shí)例2:模擬結(jié)果(最佳個(gè)體進(jìn)化情況)世代數(shù)染色體編碼變量x適應(yīng)值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.8502742/6/2023最優(yōu)化問(wèn)題(OptimizationProblem)最優(yōu)化問(wèn)題:組合優(yōu)化問(wèn)題(CombinatorialOptimizationProblem):最優(yōu)化問(wèn)題中的解空間X或S由離散集合構(gòu)成。其中很多問(wèn)題是NP完全(NondeterministicPolynomialCompleteness)問(wèn)題.2/6/2023最優(yōu)化問(wèn)題算法傳統(tǒng)的優(yōu)化方法(局部?jī)?yōu)化方法)

共軛梯度法、牛頓法、單純形方法等特點(diǎn):

1)依賴(lài)于初始條件。2)與求解空間有緊密關(guān)系，促使較快地收斂到局部解，但同時(shí)對(duì)解域有約束，如連續(xù)性或可微性。利用這些約束，收斂快。3)有些方法，如Davison-Fletcher-Powell直接依賴(lài)于至少一階導(dǎo)數(shù)；共軛梯度法隱含地依賴(lài)于梯度。2/6/2023最優(yōu)化問(wèn)題算法全局優(yōu)化方法

下降軌線法、Monte-Carlo隨機(jī)試驗(yàn)法、模擬退火法、GA等特點(diǎn)：1)不依賴(lài)于初始條件；2)不與求解空間有緊密關(guān)系,對(duì)解域無(wú)可微或連續(xù)的要求;容易實(shí)現(xiàn)，求解穩(wěn)健。3)但收斂速度慢,能獲得全局最優(yōu);適合于求解空間不知的情況。4)GA可應(yīng)用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等全局優(yōu)化問(wèn)題;求解速度和質(zhì)量遠(yuǎn)超過(guò)常規(guī)方法。2/6/2023無(wú)約束最優(yōu)化問(wèn)題GA編碼：X=(x1,x2,…,xn)的各個(gè)變量可以按二進(jìn)制編碼方法分別編碼。對(duì)于變量xi的上、下限約束li≤xi≤

ui(i=1,2,…,n)，依據(jù)解的精度要求(有效位數(shù))求得各個(gè)變量X=(x1,x2,…,xn)的二進(jìn)制碼位數(shù)(m1,m2,…,mn)(確定方法類(lèi)似于SGA實(shí)例2)，因此將n個(gè)二進(jìn)制位串順序連接起來(lái)，構(gòu)成一個(gè)個(gè)體的染色體編碼，編碼的總位數(shù)m＝m1+m2+…+mn。無(wú)約束最優(yōu)化問(wèn)題:2/6/2023無(wú)約束最優(yōu)化問(wèn)題GA解碼：解碼時(shí)仍按各個(gè)變量的編碼順序分別實(shí)現(xiàn)常規(guī)的二進(jìn)制編碼解碼方法。二進(jìn)制遺傳編碼示意圖如下：2/6/2023約束最優(yōu)化問(wèn)題常規(guī)解法：(1)把約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題，在用無(wú)約束問(wèn)題方法求解，如罰函數(shù)法(2)改進(jìn)無(wú)約束問(wèn)題的方法，再用于約束問(wèn)題，如梯度投影法、廣義簡(jiǎn)約梯度法約束最優(yōu)化問(wèn)題:2/6/2023約束最優(yōu)化問(wèn)題遺傳算法求解關(guān)鍵:約束條件的處理等式約束可以包含到適應(yīng)函數(shù)，僅考慮不等式約束。假設(shè)按無(wú)約束問(wèn)題那樣求解，在搜索過(guò)程中計(jì)算目標(biāo)函數(shù)值，并檢查是否有約束違反。如果沒(méi)有違反，則表明是可行解，就根據(jù)目標(biāo)函數(shù)指定一適應(yīng)值；否則，就是不可行解，因而沒(méi)有適應(yīng)值(適應(yīng)值為0)。這樣的處理實(shí)際不可行，因?yàn)檎业揭粋€(gè)可行解幾乎與找到最優(yōu)解一樣困難。2/6/2023一般解法：通過(guò)引入罰函數(shù)，從不可行解中得到一些信息。將罰函數(shù)包含到適應(yīng)函數(shù)中。關(guān)鍵是如何設(shè)計(jì)罰函數(shù)；不同問(wèn)題需要設(shè)計(jì)不同的罰函數(shù)；對(duì)一般的約束處理，通常很困難。約束最優(yōu)化問(wèn)題2/6/2023組合最優(yōu)化問(wèn)題典型問(wèn)題：巡回旅行商問(wèn)題(TravelingSalesmanProblem)作業(yè)調(diào)度問(wèn)題(JobShopSchedulingProblem)背包問(wèn)題(KnapsackProblem)圖著色問(wèn)題………很多組合最優(yōu)化問(wèn)題是NP難問(wèn)題或NP完全問(wèn)題2/6/2023巡回旅行商問(wèn)題(TSP)TSP，也稱(chēng)貨郎擔(dān)問(wèn)題，是一個(gè)NP完全問(wèn)題。TSP描述：圖論:設(shè)圖G=(V,E),其中V是頂點(diǎn)集，E是邊集。設(shè)C=(cij)是與E相聯(lián)系的距離矩陣。尋找一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過(guò)一次的最短距離回路(Hamilton回路)。實(shí)際應(yīng)用中，C也可解釋為費(fèi)用或旅行時(shí)間矩陣。實(shí)際:一位推銷(xiāo)員從自己所在城市出發(fā)，必須遍訪所有城市之后又回到原來(lái)的城市，求使其旅行費(fèi)用最少的路徑。2/6/2023巡回旅行商問(wèn)題(TSP)中國(guó)貨郎擔(dān)問(wèn)題:城市數(shù):40城市編號(hào)1,2,…,40尋找一條最短路徑2/6/2023TSP復(fù)雜性搜索空間龐大TSP涉及求多個(gè)變量的函數(shù)的最小值，求解很困難。其可能的路徑條數(shù)隨著城市數(shù)目n成指數(shù)增長(zhǎng)，如，5個(gè)城市對(duì)應(yīng)12條路徑；10個(gè)城市對(duì)應(yīng)181440條路徑；100個(gè)城市對(duì)應(yīng)4.6663X10155條路徑。如此龐大的搜索空間，常規(guī)解法和計(jì)算工具都遇到計(jì)算上的困難。只能尋找近似解法，如神經(jīng)網(wǎng)絡(luò)方法、模擬退火法、遺傳算法等。2/6/2023TSP編碼:路徑表示染色體表示成所有城市的一個(gè)排列，若有n個(gè)城市，一條可能路徑編碼為長(zhǎng)度為n的整數(shù)向量(i1,i2,…,in),其中ik表示第ik個(gè)城市。例如:路徑編碼向量(517894623)直接表示一條旅行路程(5->1->7->8->9->4->6->2->3)。此向量是1到n的一個(gè)排列，即從1到n的每個(gè)整數(shù)在這個(gè)向量中正好出現(xiàn)一次,不能有重復(fù)。這樣，基本遺傳算法的基因操作生成的個(gè)體不能滿足這一約束條件，需尋求其他遺傳操作。2/6/2023TSP交叉需其他方式的交叉(重組)操作,如部分匹配交叉(PartiallyMatchedCrossover,PMX)、順序交叉(OrderedCrossover,OX)、循環(huán)交叉(CycleCrossover,CX)、邊重組(EdgeRecombination)。12345543211232154345一般的交叉操作會(huì)產(chǎn)生不合適的解，如2/6/2023TSP交叉1:部分匹配交叉(PMX)雙親P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn)，得到一個(gè)匹配段,根據(jù)交叉點(diǎn)中間段給出映射關(guān)系。123456789937826514xxx4567xxxxx8265xxP1P2映射關(guān)系：48、52、75c1c2交換兩個(gè)交叉點(diǎn)之間的編碼,(X表示未定碼)2/6/2023TSP交叉1:部分匹配交叉(PMX)子個(gè)體C1，C2分別從其父?jìng)€(gè)體中繼承未映射城市碼12345678993782651493x45671x1x38265x9P1P2c1c2映射關(guān)系：48、52、75932456718173826549c1c2

再根據(jù)映射關(guān)系，對(duì)以上未定碼，使用最初雙親碼，得到子個(gè)體的對(duì)應(yīng)碼。映射關(guān)系存在傳遞關(guān)系，則選擇未定碼交換。2/6/2023TSP交叉2:順序交叉(OX)雙親P1,P2隨機(jī)選取兩個(gè)交叉點(diǎn)123456789937826514P1P2xxx4567xxxxx8265xxc1c2

兩個(gè)交叉點(diǎn)間的中間段保存不變

子個(gè)體C1的未定碼的確定需要父?jìng)€(gè)體P2的未選定城市碼，子個(gè)體C2的未定碼的確定需要父?jìng)€(gè)體P1的未選定城市碼。2/6/2023TSP交叉2:順序交叉(OX)記取父?jìng)€(gè)體P2從第二個(gè)交叉點(diǎn)開(kāi)始城市碼的排列順序，當(dāng)?shù)竭_(dá)表尾時(shí)，返回表頭繼續(xù)記錄，直到第二個(gè)交叉點(diǎn)。937826514P2xxx4567xxc1382456719c1347826591c2

得到父?jìng)€(gè)體P2的排列順序1-4-9-3-7-8-2-6-5,并將C1已有城市碼4,5,6,7從中去掉，得到排列順序1-9-3-8-2，再將此順序復(fù)制到C1，復(fù)制點(diǎn)也是從第二個(gè)交叉點(diǎn)開(kāi)始，得到C1。同理的C2，2/6/2023TSP交叉3:循環(huán)交叉(CX)CX操作中子個(gè)體中的城市碼順序根據(jù)任一父?jìng)€(gè)體產(chǎn)生確定循環(huán)編碼復(fù)制循環(huán)編碼到子個(gè)體2/6/2023TSP變異InsertMutation隨機(jī)選取個(gè)體中兩個(gè)編碼，然后把第二個(gè)編碼放在第一個(gè)編碼之后，其他編碼順次調(diào)節(jié)位置。

Swapmutation隨機(jī)選取個(gè)體中兩個(gè)編碼，然后交換它們的位置。2/6/2023TSP變異Inversionmutation隨機(jī)選取個(gè)體中一段編碼，然后顛倒這段編碼的順序。

Scramblemutation隨機(jī)選取個(gè)體上一段編碼,然后打亂這段編碼的順序。選取的編碼不一定是鄰接編碼2/6/2023TSP的GA過(guò)程從N個(gè)隨機(jī)起點(diǎn)開(kāi)始產(chǎn)生N條路徑，N為種群的規(guī)模;利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解;選擇交叉對(duì)使在平均性能之上的個(gè)體得到更多的子代;交叉和變異;搜索每條路徑得到其極小解，如果不收斂，則回到第3步；否則，停止。2/6/2023GA的MATLAB實(shí)現(xiàn)軟件平臺(tái)(SoftwarePlatforms):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox

2.0.1

MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美國(guó)NorthCarolinaStateUniversity開(kāi)發(fā)MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox英國(guó)TheUniversityofSheffield開(kāi)發(fā)《MATLAB遺傳算法工具箱及應(yīng)用》(雷英杰等,西安電子科技大學(xué)出版社,2005)基于此工具箱

2/6/2023GAOT工具箱核心函數(shù)：[pop]=initializega(num,bounds,eevalFN,eevalOps,options)------初始種群的生成函數(shù)【輸出參數(shù)】pop-----生成的初始種群【輸入?yún)?shù)】num-----種群中的個(gè)體數(shù)目

bounds-----代表變量的上下界的矩陣

eevalFN-----適應(yīng)度函數(shù)