最優(yōu)化理論概括以及差分進(jìn)化算法

差分進(jìn)化算法

DifferentialEvolutionalgorithm人類的一切活動(dòng)都是認(rèn)識(shí)世界和改造世界的過程即：認(rèn)識(shí)世界→ 改造世界 ↓ ↓ (建模)(優(yōu)化)

〇.最優(yōu)化的重要性（1）一切學(xué)科都是建模與優(yōu)化在某個(gè)特定領(lǐng)域中的應(yīng)用

概念模型(定性)→結(jié)構(gòu)模型(圖)→ →數(shù)學(xué)模型→智能模型

〇.最優(yōu)化的重要性（2）目的是求解空間優(yōu)化最優(yōu)化理論的發(fā)展極值理論；運(yùn)籌學(xué)的興起(OperationResearch)；數(shù)學(xué)規(guī)劃：線性規(guī)劃(LP)；非線性規(guī)劃(NLP)；動(dòng)態(tài)規(guī)劃(PP)；馬爾托夫規(guī)劃(MDP)；排隊(duì)輪；決策論；存儲(chǔ)論。最優(yōu)化理論在國(guó)民經(jīng)濟(jì)中的廣泛應(yīng)用 〇.最優(yōu)化的重要性（3）如下面框圖所示選一個(gè)初始解LP:大M，二階段法NLP:任意點(diǎn)或一個(gè)內(nèi)點(diǎn) 一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（1）2、停止判據(jù)——停止規(guī)則最優(yōu)性檢驗(yàn)LP:檢驗(yàn)數(shù) 當(dāng)∏≥0時(shí)有可能減小NLP:一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（2）向改進(jìn)方向移動(dòng)——改進(jìn)解LP:轉(zhuǎn)軸變換(進(jìn)基、退基)NLP:向負(fù)梯度方向移動(dòng)(共軛梯度方向、牛頓方向) 一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（3）停機(jī)選擇一個(gè)初始解停止準(zhǔn)則向改進(jìn)方向移動(dòng)啟動(dòng)YN一.傳統(tǒng)優(yōu)化方法的基本步驟—三步曲（4）對(duì)問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求——有顯式表達(dá)，線性、連續(xù)、可微，且高階可微;2. 只從一個(gè)初始點(diǎn)出發(fā)，難以進(jìn)行并行、網(wǎng)絡(luò)計(jì)算，難以提高計(jì)算效率；

二.傳統(tǒng)優(yōu)化方法的局限性（1）最優(yōu)性達(dá)到的條件太苛刻——問題的函數(shù)為凸，可行域?yàn)橥?；在非雙凸條件下，沒有跳出局部最優(yōu)解的能力。 二.傳統(tǒng)優(yōu)化方法的局限性（2）對(duì)問題的描述要寬松(目標(biāo)和約束函數(shù))——

可以用一段程序來描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式；并不苛求最優(yōu)解——通常滿意解、理想解就可以了；三.實(shí)際問題中對(duì)最優(yōu)化方法的要求（1）計(jì)算快速、高效,可隨時(shí)終止(根據(jù)時(shí)間定解的質(zhì)量)；能夠處理數(shù)據(jù)、信息的不確定性(如數(shù)據(jù)的模糊性，事件的隨機(jī)性)。三.實(shí)際問題中對(duì)最優(yōu)化方法的要求（2）1975年holland提出遺傳算法 (GeneticAlgorithm)1977年Glouer提出禁忌搜索算法 (TabnSearch) 四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（1）1982年Kirkpatrick提出模擬退火算法 (SimulatedAnnealing)人工神經(jīng)元網(wǎng)絡(luò)1995年Dorigo提出蟻群算法(AntColonyOptimization)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（2）1995年Kennedy&Eherhart提出粒子群優(yōu)化(ParticleSwarmOptimization)其它文化算法(CulturalAlgorithm)人工生命算法(Artificial-LifeAlgorithm)四.智能優(yōu)化算法的產(chǎn)生與發(fā)展（3）應(yīng)用前景十分廣闊——國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域局限性——不能保證最優(yōu)解，理論上不完備五.應(yīng)用前景局限性差分進(jìn)化算法差分進(jìn)化算法一.導(dǎo)言二.基本原理三.標(biāo)準(zhǔn)算法四.實(shí)例五.應(yīng)用方向差分進(jìn)化算法(DE)的產(chǎn)生

RainerStorn和KennethPrice在1996年為求解切比雪夫多項(xiàng)式而提出;2.DE是一種隨機(jī)的并行直接搜索算法,它可對(duì)非線性不可微連續(xù)空間函數(shù)進(jìn)行最小化,以其易用性、穩(wěn)健性和強(qiáng)大的全局尋優(yōu)能力在多個(gè)領(lǐng)域取得成功。

一.導(dǎo)言（1）差分進(jìn)化算法(DE)的起源歷程：

DE算法始于遺傳退火算法的思想一.導(dǎo)言（2）實(shí)數(shù)編碼二進(jìn)制串編碼算術(shù)向量操作邏輯操作遺傳退火算法Price.K修改切比雪夫多項(xiàng)式求解

Differentialmutationdiscreterecombinationpairwiseselection二.基本原理求解非線性函數(shù)f(x1,x2,?,xn)的最小值問題,xi滿足：

令

是第t代的第i個(gè)染色體,則其中,n是染色體的長(zhǎng)度,即變量的個(gè)數(shù),M為群體規(guī)模,

是最大的進(jìn)化代數(shù)。二.基本原理1.生成初始種群

在n維空間里隨機(jī)產(chǎn)生滿足約束條件的M個(gè)染色體,實(shí)施措施如下:二.基本原理2.變異操作從群體中隨機(jī)選擇3個(gè)染色體，，且(i≠p1≠p2≠p3),則

為差異化向量,為縮放因子。二.基本原理——差分變異

交叉操作是為了增加群體的多樣性,具體操作如下:

是在[0,1]之間的隨機(jī)小數(shù),CR為交叉概率,CR∈[0,1],rand(i)在[1,n]之間的隨機(jī)整數(shù),這種交叉策略可確保xi(t+1)至少有一分量由vij(t+1)的相應(yīng)分量貢獻(xiàn)。

二.基本原理——交叉操作

為了確定

是否成為下一代的成員,比較向量

和目標(biāo)向量

的評(píng)價(jià)函數(shù):反復(fù)執(zhí)行(2)至(4)操作,直至達(dá)到最大的進(jìn)化代數(shù)tmax。二.基本原理——選擇操作

三.DE算法的多種擴(kuò)展模式DE算法的多種變形形式常用符號(hào)DE/x/y/z以示區(qū)分,其中:X——限定當(dāng)前被變異的向量是“隨機(jī)的”或“最佳的”;Y——是所利用的差向量的個(gè)數(shù);Z——指示交叉程序的操作方法。四.試驗(yàn)——MATLAB四.試驗(yàn)——JAVA差異演化算法主要涉及群體規(guī)模M、縮放因子F以及交叉概率CR三個(gè)參數(shù)的設(shè)定。M：一般介于5×n與10×n之間,但不能少于4,否則無法進(jìn)行變異操作;F：一般在[0,2]之間選擇,通常取0.5;CR：一般在[0,1]之間選擇,比較好的選擇應(yīng)在0.3左右,CR大些收斂速度會(huì)加快,但易發(fā)生早熟現(xiàn)象。五.差異演化算法的參數(shù)選取差分進(jìn)化算法的優(yōu)缺點(diǎn)和其它進(jìn)化算法相比,差分進(jìn)化具有以下優(yōu)點(diǎn):差分進(jìn)化在求解非凸、多峰、非線性函數(shù)優(yōu)化問題表現(xiàn)極強(qiáng)的穩(wěn)健性。在同樣的精度要求下,差分進(jìn)化算法收斂的速度快。差分進(jìn)化算法尤其擅