遺傳特性算法

1、遺 傳 算 法,Genetic Algorithms,太原理工大學 數(shù)學學院 劉曉峰,數(shù)學建模一般的步驟和方法,層次分析法量綱分析法圖論法微分方程蒙特卡洛法差值擬合法回歸分析法數(shù)學規(guī)劃,2024/4/1,2,概率統(tǒng)計數(shù)值分析,運籌學機器學習,GA與計算機其余相關(guān)學科的關(guān)系,,2024/4/1,3,生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的自適應(yīng)能力。受其啟發(fā)，學者致力于對生物各種生存特性的機理研究

2、和行為進行模擬。 遺傳算法(Genetic Algorithms，GA)就是這種生物行為的計算機模擬中令人矚目的重要成果(人工免疫/人工神經(jīng)網(wǎng)絡(luò))。 基于對生物遺傳和進化過程的計算機模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力；它是模擬達爾文生物進化論的自然選擇和孟德爾遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。 遺傳算法所借鑒的生物學基礎(chǔ)就是

3、生物的遺傳和進化。,遺傳算法的起源,最早由美國密西根大學的J.Holland教授提出，起源于60年代對自然和人工自適應(yīng)系統(tǒng)的研究 1967年，Bagley發(fā)表了關(guān)于遺傳算法應(yīng)用的論文，在其論文中首次使用“遺傳算法（ Genetic Algorithm）”一詞 70年代 De Jong基于遺傳算法的思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗

4、 在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進行歸納總結(jié)，形成了遺傳算法的基本框架,遺傳算法發(fā)展,1. 復(fù)制 生物的主要遺傳方式是復(fù)制。遺傳過程中，父代的遺傳物質(zhì)DNA被復(fù)制到子代。即細胞在分裂時，遺傳物質(zhì) DNA 通過復(fù)制而轉(zhuǎn)移到新生的細胞中，新細胞就繼承了舊細胞的基因。 2. 交叉 有性生殖生物在繁殖下一代時，兩個同源染色體之間通過交叉(Crossover) 而重

5、組，即在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合而形成兩個新的染色體。 3. 變異 在進行細胞復(fù)制時，雖然概率很小，僅僅有可能產(chǎn)生某些復(fù)制差錯，從而使 DNA 發(fā)生某種變異 (Mutation)，產(chǎn)生出新的染色體。這些新的染色體表現(xiàn)出新的性狀。 如此這般，遺傳基因(或染色體)在遺傳的過程中由于各種各樣的原因而發(fā)生變化。,生物的遺傳方式,遺傳算法的進化形式和單位,生物的進化是以集團的形式共同進

6、行的，這樣的一個團體稱為群體/種群(Population)組成群體的單個生物體稱為個體(Individual)/染色體(Chromosome)，每一個個體對其生存環(huán)境都有不同的適應(yīng)能力，這種適應(yīng)能力稱為個體的適應(yīng)度(Fitness) ———— 物競天擇個體的基因(Gene)是遺傳的基本單位遺傳基因在染色體中所占據(jù)的位置稱為基因座同一基因座可能有的全部基因稱為等位基因(Allele),2024/4/1,遺傳算法的簡單原理,遺傳算法

7、將問題域中的可能解看做是群體的一個個體或染色體，并將所有個體編碼成符號串形式模擬達爾文的遺傳選擇和自然淘汰的生物進化過程，對群體反復(fù)進行基于遺傳學的操作（選擇、交叉和變異），根據(jù)預(yù)定的目標適應(yīng)度函數(shù)對每個個體進行評價依據(jù)適者生存、優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解,2024/4/1,8,遺傳算法是模擬生物在自然環(huán)境下的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化

8、概率搜索方法。,袋鼠與珠穆朗瑪峰的假想實驗,在遺傳算法中，假設(shè)將很多只袋鼠降落到喜馬拉雅山脈的任意地方，這些袋鼠并不知道它們被設(shè)想尋找珠穆朗瑪峰，休閑地活著。但每過幾年，就在海拔較低的一些地方射殺一些袋鼠，并希望存活下來的那些是多產(chǎn)的，并在那里生兒育女。這個實驗進行N年之后……,2024/4/1,9,,,2024/4/1,10,對求函數(shù)最大值的優(yōu)化問題（或最小值），可描述為下述數(shù)學規(guī)劃模型：

9、 max f(X) (1-1) s.t. X?R (1-2) R?U (1-3) 其中： X＝[x1,x2,…,xn]T為決策變量， f(X)為目標函數(shù)， 式(1-2)、(1-3)為約束條件，

10、 U是基本空間， R是U的一個子集。 滿足約束條件的解X稱為可行解；集合R表示由所有滿足約束條件的解所組成的一個集合，叫做可行解集合。,,優(yōu)化問題,遺傳算法在函數(shù)優(yōu)化中的應(yīng)用,例：利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值，x為自然數(shù)。將每一個自然數(shù)看成一個生命體，通過進化，看誰能生存下來，誰就是所尋找的數(shù)字，即問題的解。,y=x2,,31 X,Y,,,,0,2024/4/1

11、,12,求解過程,將每一個數(shù)作為一個生命體，就必須給其賦予一定的基因，這個過程叫做編碼?？梢詫⒆兞縳編碼成5位長的二進制無符號整數(shù)表達形式，例如：x=13 (01101), 即數(shù)13的基因為 01101。,編碼,,1,,2,2024/4/1,13,解的編碼,2024/4/1,14,求解過程,將每一個數(shù)作為一個生命體，就必須給其賦予一定的基因，這個過程叫做編碼。可以將變量x編碼成5位長的二進制無符號整數(shù)表達形式，例如：x=13 (0110

12、1), 即數(shù)13的基因為 01101。 由于遺傳的需要，必須設(shè)定一些初始的生物群體，讓其作為生物繁殖的第一代。為了保證生物的多樣性和競爭的公平性，初始種群的所有個體都是通過隨機方法產(chǎn)生的。,編碼,,1,,,,2,初始種群的生成,2024/4/1,15,,,2024/4/1,16,,生物的進化服從適者生存、優(yōu)勝劣汰的規(guī)則。因此必須規(guī)定什么樣的基因是“優(yōu)”的，什么樣的基因是“劣”的，稱為適應(yīng)度函數(shù)。顯然，定義

13、 為適應(yīng)度函數(shù)，然后計算所有個體的適應(yīng)度值。,適應(yīng)度計算,,,3,4,2024/4/1,17,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,解碼,計算適應(yīng)度,2024/4/1,18,,生物的進化服從適者生存、優(yōu)勝劣汰的規(guī)則。因此必須規(guī)定什么樣的基因是“優(yōu)”的，什么樣的基因是“劣”的，稱為適應(yīng)度函數(shù)。顯然，定義 為適應(yīng)度函數(shù)，然后計算

14、所有個體的適應(yīng)度值。 選擇運算就是優(yōu)勝劣汰的過程，把當前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中，一般適應(yīng)度較高的個體將有更多的機會遺傳到下一代群體中。 選擇是一個概率選擇的過程，基因差的不一定會被淘汰。,適應(yīng)度計算,,,選擇,,3,,4,2024/4/1,19,,為了產(chǎn)生新的個體，種群中進行交叉繁殖。以某一概率選出兩個個體，相互交換一部分基因，就形成了兩個新的個體。,交叉,,5,,2024/4/1,20,,,

15、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,交叉位,Pcross,cross,父代個體,,,,,,,,,,,,,,,,,,,,,,,,,,,,,子代個體,,交叉概率,,,,,,,,,,,連續(xù)改變個體多個基因位上的遺傳信息,1,2,1,2,2024/4/1,21,,為了產(chǎn)生新的個體，種群中進行交叉繁殖。以某一概率選出兩個個體，相互交換一部分基因，就形成了兩個新的個體。 變異運算是將個體基因中的某一位以一定的小概率發(fā)

16、生變化，也可以產(chǎn)生新的個體。,交叉,,5,,,,6,變異,2024/4/1,22,,,,,,,,,,,,,,,,,變異位,Pmutate,mutate,父代個體,,,,,,,,,,,,,,,子代個體,變異概率,,,,,2024/4/1,23,,為了產(chǎn)生新的個體，種群中進行交叉繁殖。以某一概率選出兩個個體，相互交換一部分基因，就形成了兩個新的個體。 變異運算是將個體基因中的某一位以一定的小概率發(fā)生變化，也可以產(chǎn)生新的個體。,交叉

17、,,5,,,,6,變異,,這樣就經(jīng)過了一代進化，通過上述步驟不斷地循環(huán)進化，種群中的個體基因便逐漸地趨向最優(yōu)。,2024/4/1,24,,,,Y,,,,,,2024/4/1,25,,,,遺傳算法流程圖,2024/4/1,26,步1 在搜索空間U上定義一個適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc 和變異率Pm，代數(shù)T；,基本遺傳算法步驟,步2 隨機產(chǎn)生U中的N個個體s1, s2, …, sN，組成初始種群S={s1, s2, …,

18、sN}，置代數(shù)計數(shù)器 t=1；　 步3 計算S 中每個個體的適應(yīng)度 f( ) ；　　步4 若終止條件滿足，則取S中適應(yīng)度最大的個體作為所求結(jié)果，算法結(jié)束。,步5 否則，按選擇概率P(xi)所決定的選中機會，每次從S 中隨機選定1個個體并將其染色體復(fù)制，共做 N 次，然后將復(fù)制所得的 N 個染色體組成群體 S1 ；,步7 按變異率Pm所決定的變異次數(shù)m，從S2中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，

19、得群體S3；　　步8 將群體S3作為新一代種群，即用S3代替S，t = t+1，轉(zhuǎn)步3。,步6 按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c 個染色體，配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體 S2 ；,基本遺傳算法步驟,基本遺傳算法的運行參數(shù),M：群體大小，群體規(guī)模POP，即群體中所含個體的數(shù)量，一般取為20-100T：遺傳運算的終止進化代數(shù)，一般取為100-500pc：交叉概率(crosso

20、ver rate)，就是參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例，記為Pc，一般取為0.5-0.9pm：變異概率(mutation rate)，是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，一般取為 0.0001-0.1[說明]：這4個運行參數(shù)對遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范

21、圍。,適應(yīng)度收斂曲線,,遺傳算法工具箱,遺傳算法的工具箱有很多種：Genetic Algorithm Tool 簡稱GATOOL->GADS Genetic Algorithm Optimization Tool 簡稱GAOT Genetic Algorithm Toolbox 簡稱GATBX Simple Genetic Algorithm 1002 簡稱SGA1002 …………Main functio

22、n Comparation Of Genetic Algorithm Toolbox base Matlab,gatbx工具箱版本查看,>> v=ver('gatbx')v = Name: 'Genetic Algorithm Toolbox' Version: '1.2' Release: '' Da

23、te: '15-Apr-94',遺傳算法與直接搜索工具箱GADS,GADS工具箱是一系列函數(shù)的集合，它們擴展了優(yōu)化工具箱和MATLAB數(shù)值計算環(huán)境的性能。使得用戶能夠求解那些標準優(yōu)化工具箱范圍之外的各種優(yōu)化問題。,所有的工具箱函數(shù)都是m文件，可以使用 type function name 查看函數(shù)代碼 也可以通過編寫自己的m文件來實現(xiàn)和擴展GAD

24、S工具箱的性能。遺傳算法、直接搜索工具箱和優(yōu)化工具箱是緊密結(jié)合在一起的。用戶可以用GADS工具箱來尋找最佳起始點，然后利用優(yōu)化工具箱或其它程序來進一步尋找最優(yōu)解。,Matlab自帶遺傳算法工具箱GADS,工具箱具有兩種使用方式：(1)以命令行方式調(diào)用遺傳算法函數(shù)ga。(2)通過圖形用戶界面使用遺傳算法工具箱。,命令行方式：[x fval]=ga(@fitnessfun, nvars, options)@fitnessfun是求最

25、小值的適應(yīng)度函數(shù)句柄；nvars是適應(yīng)度函數(shù)的獨立變量的個數(shù)；options是一個包含遺傳算法選項設(shè)置、屬性參數(shù)的結(jié)構(gòu)，如果沒有特別改寫，則ga使用它本身的默認選項值；可以通過函數(shù)gaoptimset修改設(shè)置； x—最終值到達的點； fval—適應(yīng)度函數(shù)的最終值,Rastrigin函數(shù),測試函數(shù)： Rastrigin 定義為： Ras(x)=20+x1*x1+x2*x2- 10(cos(2*pi*x1)+(cos(2*pi*x

26、2)) -5.12<=x1,x2<=5.12,圖形顯示具有多個局部最小值和一個全局最小值，出現(xiàn)在點[0,0]處，函數(shù)值為0。在任何不同于[0,0]的局部最小點處，Rastrigin函數(shù)的值均大于0。局部最小處距原點越遠，該點處Rastrigin函數(shù)的值越大。 之所以選它為測試函數(shù)，因為它有許多局部最小點，具有很強的欺騙性，使得用標準的、基于梯度的查找全局最小的方法十分困難。,命令行方式調(diào)用遺傳

27、算法函數(shù)ga,句柄為@rastriginsfcn 有2個變量>> [x fval]=ga(@rastriginsfcn,2)Optimization terminated: average change in the fitness value less than options.FunctionTolerance.x = 0.0015 -0.0166fval = 0.0553,遺傳算

28、法求解函數(shù)ga的一般用法,函數(shù)gaoptimset的語法格式為options=gaoptimset('PropertyName1','PropertyValue1','PropertyName 2',' PropertyValue2','PropertyName3','PropertyValue3'......)gaoptimset實現(xiàn)

29、功能為設(shè)置遺傳算法的參數(shù)和句柄函數(shù)由于遺傳算法本質(zhì)上是一種啟發(fā)式的隨機運算，算法程序經(jīng)常重復(fù)運行多次才能得到理想結(jié)果。鑒于此，可以將前一次運行得到的最后種群作為下一次運行的初始種群，如此操作會得到更好的結(jié)果。,遺傳算法求解函數(shù)ga的一般用法,[x,fval,reason,output,final_pop]=ga(@fitnessfun,nvars,options);reason為算法停止原因；最后一個輸出變量final_pop返回的

30、就是本次運行得到的最后種群，再將final_pop作為ga的初始種群，語法格式為：options=gaoptimset（'InitialPopulation',final_pop);[x,fval,reason,output,final_pop2]=ga(@fitnessfun,nvars,options);,函數(shù)ga處理自變量范圍問題,如果有約束條件（包括自變量的取值范圍），對于求解函數(shù)的最小值問題，可以使用如下

31、語法格式：function f=fitnessfcn(x) if(x3) % x3 %表示有約束x>-1和x<=3，其他約束條件類推 f=inf; else f=f(x); end,遺傳算法函數(shù)ga——帶約束條件,[x,fval]=ga(@fitnessfun,nvars,A,b,Aeq,beq,LB,UB,@nonlcon,options)

32、其中，A是不等式約束AX<=b的系數(shù)矩陣；b是不等式約束AX<=b的常數(shù)項；Aeq是等式約束AeqX=beq的系數(shù)矩陣；beq是等式約束AeqX=beq的常數(shù)項；LB是X的下限;UB是X的上限；@nonlcon是非線性約束函數(shù)。,函數(shù)ga——帶線性約束條件,適應(yīng)度函數(shù)另存為：fun_1.m在當前目錄function y=fun_1(x); %x為自變量行向量c=[2 4 6]; % c為目標函數(shù)系數(shù)y=c*x‘

33、 % y為適應(yīng)度函數(shù)值，求兩向量的數(shù)量積,函數(shù)ga——帶線性約束條件,A=[1 0 -1;-1 -2 0;-1 0 0]; % A為AX<=b的系數(shù)矩陣 b=[10;-1;0]; % b為AX<=b的常數(shù)項 Aeq=[0 1 1]; %AeqX=beq的系數(shù)矩陣beq=12; %

34、AeqX=beq的常數(shù)項,函數(shù)ga——帶線性約束條件,>> [x,y]=ga(@fun_1,3,A,b,Aeq,beq,[],[]);>> [x,y]=ga(@fun_1,3,A,b,Aeq,beq); % 或,x = -0.0010 22.0010 -10.0020y = 27.9900,函數(shù)ga——帶非線性約束條件,適應(yīng)度函數(shù)另存為：fun_2.m在當前目錄function y=

35、fun_1(x); %x為自變量行向量temp=[1 2 5]*x'+[3 0 1]*x'.^2;y=-temp; % 轉(zhuǎn)換為求最小值,function [budengshi,dengshi]=yueshu(x);%非線性約束 budengshi=[4*x(1)^2+2*x(2)^2+x(3)-46; x(1)+x(1)^2+x(2)^2-5*x(3)-34; 3*

36、x(1)+2*x(1)^2+x(2)+3*x(3)-67];dengshi=x(1)+x(3)^2-13;,函數(shù)ga——帶非線性約束條件,A=[-2 -4 -6; -1 0 0; 0 1 0]; % A為AX<=b的系數(shù)矩陣 b=[-10; 0; 10]; % b為AX<=b的常數(shù)項,函數(shù)ga——帶非線性約束條件,>>[x,y]=ga(@fun_2,3,

37、A,b,[],[],[],[],@yueshu)>>y=-y,x = 2.5310 2.9274 3.2356y = -54.2512y = 54.2512,函數(shù)ga——帶非線性約束條件,通過GUI方式使用遺傳算法,圖形用戶界面打開命令：gatool,,,,,,,注意事項,遺傳算法工具箱眾多，如不了解選GADS即可。遺傳算法的參數(shù)不少，如不了解選默認即可。運行遺傳算法時，因為是使用隨機

38、數(shù)據(jù)來進行初始化和搜索，所以每一次運行后所得到的結(jié)果可能會稍微不同。為了得到遺傳算法的最好結(jié)果，一般需要以不同的參數(shù)試驗，通過不斷試驗，選擇針對問題的最佳參數(shù)，或者對結(jié)果取加權(quán)平均處理。針對某些具體模型問題，無法直接使用工具箱，必須自己動手編寫程序。,2024/4/1,53,遺傳算法的特點,遺傳算法是一種自適應(yīng)全局優(yōu)化概率搜索方法區(qū)別于傳統(tǒng)的搜索方式，模擬自然界生物進化過程，采用人工進化的方式對目標空間進行隨機化搜索其主要特點是

39、群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，搜索不依賴于初始點，基本上不用搜索空間的知識或其它輔助信息，不與求解空間有緊密關(guān)系，也就是說具有通用性,2024/4/1,54,推薦教材,作者：雷英杰、張善文、李續(xù)武、周創(chuàng)明 出版社：西安電子科技大學出版社,www.ilovematlab.cn,http://www.madio.net/forum.php?gid=716,2013B 碎紙片的拼接復(fù)原,2024/4/1,58

40、,破碎文件的拼接在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。請討論以下問題：1.對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進

41、行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時間節(jié)點。復(fù)原結(jié)果以圖片形式及表格形式表達。,2013B 碎紙片的拼接復(fù)原,2024/4/1,59,2.對于碎紙機既縱切又橫切的情形，請設(shè)計碎紙片拼接復(fù)原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時間節(jié)點。復(fù)原結(jié)果表達要求同上。3.上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙