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

1、6.1 概述概述 Di為第為第i個設計變量個設計變量xi可取的離散值集合?？扇〉碾x散值集合。 設計變量也可以一部分是連續(xù)變量，另一部分是設計變量也可以一部分是連續(xù)變量，另一部分是離散變量。離散變量。 離散變量優(yōu)化也稱為組合優(yōu)化，其算法為非多項離散變量優(yōu)化也稱為組合優(yōu)化，其算法為非多項式算法，屬式算法，屬NP類問題。類問題。niDxmjxglrxhfiijr,.,2 , 1,.,2 , 10)(,.,2 , 10)(s.t.)(.minx6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法組合方法組合方法: 隱枚舉法隱枚舉法,分枝定界法分枝定界法, 動態(tài)規(guī)劃法動態(tài)規(guī)劃法搜索方法搜索方法: 整數梯

2、度法等整數梯度法等變換方法：變換方法：0-1變量技術，擬離散法變量技術，擬離散法模擬方法模擬方法: 模擬退火方法模擬退火方法, 遺傳算法遺傳算法, 神經元網絡神經元網絡求解方法概述求解方法概述6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法算法策略算法策略松弛松弛 ：暫時去除變量的離散約束，形成松弛問題：暫時去除變量的離散約束，形成松弛問題分枝：若松弛問題的解不滿足規(guī)定的離散值要求，增加分枝：若松弛問題的解不滿足規(guī)定的離散值要求，增加兩個約束以構造兩個分枝問題兩個約束以構造兩個分枝問題定界：所有分枝的松弛解之最小值為原問題解的下界，定界：所有分枝的松弛解之最小值為原問題解的下界，它隨著迭代

3、的進行逐漸增加；已獲得的可行解的最小值它隨著迭代的進行逐漸增加；已獲得的可行解的最小值構成原問題解的上界，它隨著迭代的進行逐漸減小構成原問題解的上界，它隨著迭代的進行逐漸減小剪枝策略：分枝無解；分枝松弛解大于剪枝策略：分枝無解；分枝松弛解大于“上界上界”1.定解，某分枝所獲的解滿足離散值條件且等于定解，某分枝所獲的解滿足離散值條件且等于“下界下界”6.2 分枝定界法分枝定界法3 , 2 , 1 053832s.t.437)(.min321321321ixxxxxxxxxxxfi且為整數01232x42x5132114)(05/195/2xfxxx)(15)(xff x01232x42x17)(

4、15)(xff x2/29)(2/132/1321xfxxx3411x01x17)(230321xfxxx18)(3/52)(3/130321xxffxxx15)(xf( )17fx3 , 2 , 1 053832s.t.437)(.min321321321ixxxxxxxxxxxfi且為整數01232x42x17)(15)(xff x3411x01x)(15)(250*321xxffxxx17)(xf18)(xf501x611x3/43)(3/143/1321xfxxx6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法（一）仿生學方法概述（一）仿生學方法概述6.4 仿生算法仿生算法：神經元

5、網絡算法模仿自然界結構的算法模擬退火算法演化算法進化算法遺傳算法模仿自然界過程的算法6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法模擬退火算法模擬退火算法 前一迭代點為前一迭代點為xl，當前獲得的新點為，當前獲得的新點為x，按接，按接受概率受概率exp(- -f/Tj) 接受該點作為下一迭代點。接受該點作為下一迭代點。其中其中 f = f(x)-f(xl)，Tj 為退火溫度。為退火溫度。6.4 遺傳算法遺傳算法6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法神經元網絡神經元網絡 6.4 遺傳算法遺傳算法x1wi1x2wi21yi)(1iinjiijijifysxws1f()f()神經

6、元模型神經元模型ef11)(6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法神經元網絡神經元網絡 6.4 遺傳算法遺傳算法神經元網絡神經元網絡輸出層隱含層輸入層黑箱黑箱反饋反饋6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法（二）遺傳算法（二）遺傳算法GA的基本方法的基本方法 五要素：參數編碼，初始群設定，評估函數設計，遺傳操作，算五要素：參數編碼，初始群設定，評估函數設計，遺傳操作，算法控制參數的選擇。法控制參數的選擇。參數編碼：參數編碼：最簡單的是用二值編碼表示一維染色體。也有浮點編碼等最簡單的是用二值編碼表示一維染色體。也有浮點編碼等種群規(guī)模：種群規(guī)模：n=2L/2,L為編碼長度

7、。為編碼長度。代溝代溝G：nG參與遺傳操作，其余名額擇優(yōu)直接保存到下代中。參與遺傳操作，其余名額擇優(yōu)直接保存到下代中。 G=1時，為非重疊群體。時，為非重疊群體。 初始種群：初始種群：隨機生成隨機生成+適當優(yōu)選。適當優(yōu)選。適應度函數：適應度函數：非負，方案優(yōu)則適應度高，由目標和約束函數變換而得。非負，方案優(yōu)則適應度高，由目標和約束函數變換而得。 對適應度進行定標，避免優(yōu)秀個體競爭力過強或競爭力太均化。對適應度進行定標，避免優(yōu)秀個體競爭力過強或競爭力太均化。6.4 遺傳算法遺傳算法6 6 離散變量優(yōu)化與遺傳算法離散變量優(yōu)化與遺傳算法（二）遺傳算法（二）遺傳算法GA的基本方法的基本方法遺傳操作：遺

8、傳操作：選擇、交叉、變異。選擇、交叉、變異。選擇：選擇：適應度比例法（賭輪選擇適應度比例法（賭輪選擇 或或 蒙特卡羅選擇）；蒙特卡羅選擇）； 最佳個體保留法（最佳個體直接復制保留至下一代）；最佳個體保留法（最佳個體直接復制保留至下一代）； 期望值法（被選中參加遺傳操作的，其適應度值減去期望值的一期望值法（被選中參加遺傳操作的，其適應度值減去期望值的一半后，參與保留至下代的競爭；未被選中參加遺傳操作的，其適應半后，參與保留至下代的競爭；未被選中參加遺傳操作的，其適應度值減去期望值后，參與保留至下代的競爭）度值減去期望值后，參與保留至下代的競爭）交叉：依交叉概率進行交叉操作交叉：依交叉概率進行交叉

9、操作一點交叉：一點交叉： 一致交叉：一致交叉：二點交叉：二點交叉：變異：變異：隨機確定基因座，以變異概率對其變異取反。隨機確定基因座，以變異概率對其變異取反。6.4 遺傳算法遺傳算法 00 | 110 | 00 11 | 010 |1000 | 010 | 00 11 | 110 | 10 BABA新個體新個體個體個體 111 |0011 000 | 0110000 | 1100 111 | 0110 BABA新個體新個體個體個體 101101 011110010101 111100 001111 BABA新個體新個體屏蔽字個體個體浮點編碼染色體的交叉線性交叉交叉公式子個體父個體1F(父個體2-父個體1)F為0,1間的均勻分布隨機數變量1變量2浮點編碼染色體的交叉中間交叉交叉公式子