遺傳算法理論（課堂PPT）

1、數學建模工作室數學建模工作室2022-2-27 第1頁 mecca_數學建模工作室數學建模工作室2022-2-27 第2頁 mecca_非線性規(guī)劃的基本概念非線性規(guī)劃的基本概念 定義定義 如果目標函數或約束條件中至少有一個是非線性函數時的最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃問題 一般形式一般形式: （1） 其中 ， 是定義在 En 上的實值函數，簡記: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情況其它情況: 求目標函數的最大值或約束條件為小于等于零的情

2、況，都可通過取其相反數化為上述一般形式數學建模工作室數學建模工作室2022-2-27 第3頁 mecca_ 非線性規(guī)劃的求解一般要比線性規(guī)劃的求解困難的多，不像線性規(guī)劃那樣有適應于一般情況的單純形法。 我們知道線性規(guī)劃的可行域一般是個凸集，其最優(yōu)解在可行域的邊界上達到；而非線性規(guī)劃問題的可行域一般不是凸集，最優(yōu)解也不一定在邊界上達到。 現在的各種各樣的算法都是針對各自特定的適用范圍的，這也是正處在研究發(fā)展中的學科領域。數學建模工作室數學建模工作室2022-2-27 第4頁 mecca_ 罰函數法罰函數法 罰函數法罰函數法基本思想是通過構造罰函數把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約

3、束最優(yōu)化方法去求解這類方法稱為序列無約束最小化方法序列無約束最小化方法簡稱為SUMTSUMT法法 其一為SUMTSUMT外點法外點法，其二為SUMTSUMT內點法內點法數學建模工作室數學建模工作室2022-2-27 第5頁 mecca_ )2( , 0min,1212ljjmiiXhMXgMXfMXT可設：)3( ,min 1MXTnEX）轉化為無約束問題：將問題（ 其中T(X,M)稱為罰函數罰函數，M稱為罰因子罰因子，帶M的項稱為罰項罰項，這里的罰函數只對不滿足約束條件的點實行懲罰：當 時，滿足各 ，故罰項=0，不受懲罰當 時，必有 的約束條件，故罰項0，要受懲罰DX 0, 0XhXgiiD

4、X 00XhXgii或SUTMSUTM外點法外點法 ) 1 ( .,.,2 , 1 0 m;1,2,., 0. . min ljXhiXgtsXfji對一般的非線性規(guī)劃：數學建模工作室數學建模工作室2022-2-27 第6頁 mecca_) 1 (,.,2 , 10. .min i mXgtsXfi考慮問題： 所有嚴格內點的集合。是可行域中，設集合00, 2 , 1, 0|DmiXgXDi 為障礙因子為障礙項，或其中稱或：構造障礙函數rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii11111 ln1)(),( ln, ）（得值問題：）就轉化為求一系列極這樣問題（kk

5、kDXrXrXI ,min10SUTMSUTM內點法（內點法（障礙函數法）數學建模工作室數學建模工作室2022-2-27 第7頁 mecca_遺傳算法傳統(tǒng)的優(yōu)化方法（局部優(yōu)化） 共軛梯度法、擬牛頓法、單純形方法全局優(yōu)化方法 漫步法（Random Walk）、模擬退火法、GA關于優(yōu)化問題比較：傳統(tǒng)的優(yōu)化方法 1）依賴于初始條件。 2）與求解空間有緊密關系，促使較快地收斂到局部 解，但同時對解域有約束，如可微或連續(xù)。利用這些約束，收斂快。 3）有些方法，如Davison-Fletcher-Powell直接依賴于至少一階導數； 共軛梯度法隱含地依賴于梯度。數學建模工作室數學建模工作室2022-2-2

6、7 第8頁 mecca_全局優(yōu)化方法1）不依賴于初始條件；2）不與求解空間有緊密關系，對解域，無可微或連續(xù)的要求。求 解穩(wěn)健，但收斂速度慢。能獲得全局最優(yōu)。適合于求解空間不知的情況數學建模工作室數學建模工作室2022-2-27 第9頁 mecca_ 選擇運算 交換操作 變異遺傳算法的基本運算遺傳算法基本原理 模擬自然界優(yōu)勝劣汰的進化現象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量染色體，向量的每個元素稱為基因。 通過不斷計算各染色體的適應值，選擇最好的染色體，獲得最優(yōu)解。數學建模工作室數學建模工作室2022-2-27 第10頁 mecca_選擇運算 從舊的種群中選擇適應度高的染色體，放

7、入匹配集（緩沖區(qū)），為以后染色體交換、變異，產生新的染色體作準備。選擇方法適應度比例法（轉輪法）按各染色體適應度大小比例來決定其被選擇數目的多少。某染色體被選的概率：Pc)()(iicxfxfPxi 為種群中第i個染色體，數學建模工作室數學建模工作室2022-2-27 第11頁 mecca_具體步驟1）計算各染色體適應度值2）累計所有染色體適應度值，記錄中間累加值S - mid 和最 后累加值 sum = f(xi)3） 產生一個隨機數 N，0 N sum 4） 選擇對應中間累加值S - mid 的第一個染色體進入交換集 5） 重復（3）和（4），直到獲得足夠的染色體。(首個=N的S-mid所

8、對應的染色體被選中)舉例：具有6個染色體的二進制編碼、適應度值、Pc累計 值。數學建模工作室數學建模工作室2022-2-27 第12頁 mecca_染色體的 適應度和所占的比例用轉輪方法進行選擇數學建模工作室數學建模工作室2022-2-27 第13頁 mecca_染色體編號 1 2 3 4 5 6 7 8 9 10適應度 8 217 7 212117 3 7被選概率0.10.02 0.220.090.020.160.140.090.030.09適應度累計 8 10 27 34 36 48 59 66 6976隨機數23497613 1 2757所選染色體號碼 3 710 3 1 3 7染色體被

9、選的概率被選的染色體個數10個染色體種群按比例的選擇過程數學建模工作室數學建模工作室2022-2-27 第14頁 mecca_交換操作 方法:隨機選擇二個染色體(雙親染色體),隨機指定一點或多點, 進行交換,可得二個新的染色體(子輩染色體).新的子輩染色體: A 11010|001 B 01011|110模擬生物在自然界環(huán)境變化,引起基因的突變.在染色體二進制編碼中,1變成0;或0變成1.突變產生染色體的多樣性,避免進化中早期成熟,陷入局部極值點,突變的概率很低.變異復制不能創(chuàng)新,交換解決染色體的創(chuàng)新數學建模工作室數學建模工作室2022-2-27 第15頁 mecca_GA的流程數學建模工作室

10、數學建模工作室2022-2-27 第16頁 mecca_簡單遺傳算法（GA）的基本參數種群規(guī)模 P: 參與進化的染色體總數.代溝G: 二代之間不相同的染色體數目,無重疊G = 1; 有重疊 0 G 1選擇方法: 轉輪法,精英選擇法,競爭法.交換率: Pc 一般為60100%.變異率: Pm 一般為0.110%舉例:變異概率取0.001數學建模工作室數學建模工作室2022-2-27 第17頁 mecca_初始種群和它的適應度值染色體的交換操縱數學建模工作室數學建模工作室2022-2-27 第18頁 mecca_舉例：數學建模工作室數學建模工作室2022-2-27 第19頁 mecca_步驟1）編

11、碼：確定二進制的位數；組成個體（染色體）位的二進制的值，的第是相應于。和分別為和的最大值和最小值。是和或是，精度二進制位數取決于運算nqbqqqqqyxqqbqqqqqnNnnnnn08 , 212 12 minmaxminmax10minminmaxminmax步驟2）選擇種群數P 和初始個體，計算適應度值， P = 20；數學建模工作室數學建模工作室2022-2-27 第20頁 mecca_數學建模工作室數學建模工作室2022-2-27 第21頁 mecca_GA Genetic algorithm solver. X = GA(FITNESSFCN,NVARS) finds the mi

12、nimum of FITNESSFCN using GA. NVARS is the dimension (number of design variables) of the FITNESSFCN. FITNESSFCN accepts a vector X of size 1-by-NAVRS, and returns a scalar evaluated at X. X = GA(FITNESSFCN,NAVRS,OPTIONS) finds the minimum for FITNESSFCN with the default optimization parameters repla

13、ced by values in the structure OPTIONS. OPTIONS can be created with the GAOPTIMSET function.數學建模工作室數學建模工作室2022-2-27 第22頁 mecca_X = GA(PROBLEM) finds the minimum for PROBLEM. PROBLEM is a structure that has the following fields: fitnessfcn: nvars: options: randstate: randnstate: X, FVAL = GA(FITNESSF

14、CN, .) returns FVAL, the value of the fitness function FITNESSFCN at the solution X. X,FVAL,REASON = GA(FITNESSFCN, .) returns the REASON for stopping. 數學建模工作室數學建模工作室2022-2-27 第23頁 mecca_X,FVAL,REASON,OUTPUT = GA(FITNESSFCN, .) returns a structure OUTPUT with the following information: randstate: ra

15、ndnstate: generations: funccount: message: X,FVAL,REASON,OUTPUT,POPULATION = GA(FITNESSFCN, .) returns the final POPULATION at termination. X,FVAL,REASON,OUTPUT,POPULATION,SCORES = GA(FITNESSFCN, .) returns the SCORES of the final POPULATION.數學建模工作室數學建模工作室2022-2-27 第24頁 mecca_ 函數： function y = two_m

16、in(x) if x20 y = -exp(-(x/20).2); else y = -exp(-1)+(x-20)*(x-22); end數學建模工作室數學建模工作室2022-2-27 第25頁 mecca_數學建模工作室數學建模工作室2022-2-27 第26頁 mecca_ options = gaoptimset; options. PopulationType=doubleVector; options. PopulationSize=100; options.StallGenLimit=inf; options.StallTimeLimit=inf; options.PlotFcn

17、s=gaplotbestf; options.Generations=50; x, fval, reason=ga(two_min, 1, options)數學建模工作室數學建模工作室2022-2-27 第27頁 mecca_ x = -0.0014 fval = -1.0000 reason = Optimization terminated: maximum number of generations exceeded.數學建模工作室數學建模工作室2022-2-27 第28頁 mecca_數學建模工作室數學建模工作室2022-2-27 第29頁 mecca_數學建模工作室數學建模工作室20

18、22-2-27 第30頁 mecca_options = PopulationType: doubleVector PopInitRange: 2x1 double PopulationSize: 100 EliteCount: 2 CrossoverFraction: 0.8000 MigrationDirection: forward MigrationInterval: 20 MigrationFraction: 0.2000 Generations: 50 TimeLimit: Inf FitnessLimit: -Inf StallGenLimit: Inf StallTimeLim

19、it: Inf InitialPopulation: InitialScores: PlotInterval: 1 CreationFcn: gacreationuniform FitnessScalingFcn: fitscalingrank SelectionFcn: selectionstochunif CrossoverFcn: crossoverscattered MutationFcn: mutationgaussian HybridFcn: Display: final PlotFcns: gaplotbestf OutputFcns: Vectorized: off數學建模工作室數學建模工作室2022-2-27 第31頁 mecca_ options.PopInitRange=-11;26 options. PopulationSize=300;擴大人口 x, fval, reason=ga(two_min, 1, options)數學建模工作室數學建模工作室2022-2-27 第32頁 mecca_數學建模工作室數學建模工作室2022-2-27 第33頁 mecca_數學建模工作室數學建模工作室2022-2-27 第34頁 mecca_ GATOOL Gen