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

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

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

=

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

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

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

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