優(yōu)化原理與方法12

優(yōu)化原理與方法第12講§6離散變量優(yōu)化與遺傳算法§6.1概述

Di為第i個設(shè)計變量xi可取的離散值集合。設(shè)計變量也可以一部分是連續(xù)變量，另一部分是離散變量。離散變量優(yōu)化也稱為組合優(yōu)化，其算法為非多項式算法，屬NP類問題?！?離散變量優(yōu)化與遺傳算法組合方法:隱枚舉法,分枝定界法,動態(tài)規(guī)劃法搜索方法:整數(shù)梯度法等變換方法：0-1變量技術(shù)，擬離散法模擬方法:模擬退火方法,遺傳算法,神經(jīng)元網(wǎng)絡(luò)求解方法概述§6離散變量優(yōu)化與遺傳算法算法策略松弛：暫時去除變量的離散約束，形成松弛問題分枝：若松弛問題的解不滿足規(guī)定的離散值要求，增加兩個約束以構(gòu)造兩個分枝問題定界：所有分枝的松弛解之最小值為原問題解的下界，它隨著迭代的進(jìn)行逐漸增加；已獲得的可行解的最小值構(gòu)成原問題解的上界，它隨著迭代的進(jìn)行逐漸減小剪枝策略：①分枝無解；②分枝松弛解大于“上界”定解，某分枝所獲的解滿足離散值條件且等于“下界”§6.2分枝定界法012012340123456§6離散變量優(yōu)化與遺傳算法（一）仿生學(xué)方法概述§6.4仿生算法§6離散變量優(yōu)化與遺傳算法模擬退火算法前一迭代點為xl，當(dāng)前獲得的新點為x，按接受概率exp(-△f/Tj)接受該點作為下一迭代點。其中△f

=

f(x)-f(xl)，Tj為退火溫度。§6.4遺傳算法§6離散變量優(yōu)化與遺傳算法神經(jīng)元網(wǎng)絡(luò)

§6.4遺傳算法x1wi1x2wi2θ1yis1μf(μ)μf(μ)神經(jīng)元模型§6離散變量優(yōu)化與遺傳算法神經(jīng)元網(wǎng)絡(luò)

§6.4遺傳算法神經(jīng)元網(wǎng)絡(luò)輸出層隱含層輸入層黑箱反饋§6離散變量優(yōu)化與遺傳算法（二）遺傳算法GA的基本方法五要素：參數(shù)編碼，初始群設(shè)定，評估函數(shù)設(shè)計，遺傳操作，算法控制參數(shù)的選擇。參數(shù)編碼：最簡單的是用二值編碼表示一維染色體。也有浮點編碼等種群規(guī)模：n=2L/2,L為編碼長度。代溝G：nG參與遺傳操作，其余名額擇優(yōu)直接保存到下代中。

G=1時，為非重疊群體。初始種群：隨機(jī)生成+適當(dāng)優(yōu)選。適應(yīng)度函數(shù)：非負(fù)，方案優(yōu)則適應(yīng)度高，由目標(biāo)和約束函數(shù)變換而得。對適應(yīng)度進(jìn)行定標(biāo)，避免優(yōu)秀個體競爭力過強(qiáng)或競爭力太均化?！?.4遺傳算法§6離散變量優(yōu)化與遺傳算法（二）遺傳算法GA的基本方法遺傳操作：選擇、交叉、變異。選擇：適應(yīng)度比例法（賭輪選擇或蒙特卡羅選擇）；最佳個體保留法（最佳個體直接復(fù)制保留至下一代）；期望值法（被選中參加遺傳操作的，其適應(yīng)度值減去期望值的一半后，參與保留至下代的競爭；未被選中參加遺傳操作的，其適應(yīng)度值減去期望值后，參與保留至下代的競爭）交叉：依交叉概率進(jìn)行交叉操作一點交叉：一致交叉：二點交叉：變異：隨機(jī)確定基因座，以變異概率對其變異取反?！?.4遺傳算法浮點編碼染色體的交叉線性交叉交叉公式子個體＝父個體1＋F×(父個體2-父個體1)F為[0,1]間的均勻分布隨機(jī)數(shù)變量1變量2浮點編碼染色體的交叉中間交叉交叉公式子個體i＝父個體1i＋Fi×(父個體2i— 父個體1i)Fi為[0,1]間的均勻分布隨機(jī)數(shù)浮點編碼染色體的變異浮點編碼變異GA的框圖產(chǎn)生初始群體是否滿足終