粒子群優(yōu)化算法預(yù)備知識

1、粒子群優(yōu)化算法 （particle swarm optimizer, pso） 基于群智能方法的演化計算技術(shù) 預(yù)備知識無約束最優(yōu)化問題 其中 ，通常稱變量為決策變量(decision variables)，稱 為目標(biāo)函數(shù)(objective function) 。)(minrxnxfntnrxxx),(21xnxxx,21)(xf預(yù)備知識 一般約束非線性優(yōu)化問題的數(shù)學(xué)模型為： 可行集（域） njirxxljxhmixgtsxf, 2 , 1, 0)(, 2 , 1, 0)(. .)(minljxhmixgxsji, 2 , 1, 0)(;, 2 , 1, 0)(預(yù)備知識 為等式約束， 為不等式

2、約束，等式約束和不等式約束統(tǒng)稱為約束條件(constraint condition)。 為英文“subject to”的縮寫，表示“受限制于”0)(xih0)(xjgs.t.基本概念 若有 使得 ，均有 ，則稱 為最優(yōu)化問題 的（全局）最優(yōu)解(global optimal solution)（點）或全局極小點。 若 使得 ，均有 ，則稱為最優(yōu)化問題 的嚴(yán)格全局極小點。 nr*xnrx)(*)(xxff*x)(minrxnxfnr *x*,xxrxn)(*)(xxff)(minrxnxf基本概念 若存在 的一個鄰域 使得 均有 ，則稱為最優(yōu)化問題 的（局部）最優(yōu)解(local optimal s

3、olution)（點）或局部極小點(local minimum point)，其中 而 為向量的模。 若 使得 ，均有 則稱 為最優(yōu)化問題 的嚴(yán)格局部極小點 點 稱為最優(yōu)解，其所對應(yīng)的目標(biāo)函數(shù)值 稱為最優(yōu)值，通常用 表示。 *x)*,(xn0),*,(xrxnn)(*)(xxff)(minrxnxf0*)*,(xxxxnnr *x*),*,(xxxrxnn)(*)(xxff*x)(minrxnxf*x*f最優(yōu)化算法的一般結(jié)構(gòu) 定理定理（一階必要條件） 若 具有一階連續(xù)偏導(dǎo)數(shù)， 是最優(yōu)化問題 的局部極小值點（局部最優(yōu)解），則必有 迭代法的基本思想是：首先給出 最優(yōu)解的一個初始估計點（稱為初始點）

4、 然后按照某一迭代規(guī)則得到一個點列 ，使得當(dāng)該點列是有窮點列時，其最后一個點是最優(yōu)化問題 的最優(yōu)解；當(dāng)該點列是無窮點列時， 有極限點，且其極限點是該最優(yōu)化問題的最優(yōu)解。如何得到迭代點列呢？即在得到點 后，如何確定點 。我們這樣考慮：因為 是一個向量，而向量由其方向和長度來確定，即 ，其中 是向量（稱為搜索方向），是正實數(shù)，稱為步長。當(dāng)它們確定后，由 可確定 ，這樣就可以得到一個點列 ，從而確定一個算法。 )(xf*x)(minrxnxf0 x*)(f)(xf)0(x)(kx)(minrxnxf)(kx)(kx)1( kx)()1(kkxx)()()1(kkkksxx)(ksk)(kx)1( k

5、x)(kx優(yōu)化問題的分類 根據(jù)最優(yōu)化問題是否有約束條件，可分為約束最優(yōu)化問題和無約束最優(yōu)化問題。 若目標(biāo)函數(shù)和約束條件中出現(xiàn)的函數(shù)均為線性函數(shù)，稱該最優(yōu)化問題為線性規(guī)劃（linear programming）問題，否則稱為非線性規(guī)劃（nonlinear programming）問題,即目標(biāo)函數(shù)和約束條件中出現(xiàn)的函數(shù)至少有一個不是線性函數(shù)，稱該最優(yōu)化問題為非線性規(guī)劃問題。 優(yōu)化問題的分類 若目標(biāo)函數(shù)為二次函數(shù)，而約束條件為線性函數(shù)，稱該最優(yōu)化問題為二次規(guī)劃（quadratic programming）問題，顯然二次規(guī)劃是最簡單的一種非線性規(guī)劃問題。 若優(yōu)化變量只能取整數(shù)值時，稱該最優(yōu)化問題為整數(shù)

6、規(guī)劃（integer programming）問題，特別地，若整數(shù)規(guī)劃問題中的優(yōu)化變量只能取值為0或1，稱之為0-1規(guī)劃。 當(dāng)目標(biāo)函數(shù)不是數(shù)量函數(shù)而是向量函數(shù)時，稱之為多目標(biāo)函數(shù)，等等。 最優(yōu)化問題舉例 例1曲線擬合問題假設(shè)熱敏電阻r是溫度的函數(shù)，函數(shù)關(guān)系如下其中 是待定參數(shù)。通過實驗測定 和r的15組數(shù)據(jù)如表1：確定參數(shù) 使曲線盡可能地靠近所有的實驗點。 )exp(321xtxxr321,xxxt321,xxx最優(yōu)化問題舉例 利用最小二乘法原理求解，即確定參數(shù)的一組值，使其偏差的平方和 最小。 即2151321)exp(iiixtxxrs2151321)exp(miniiixtxxr最優(yōu)化問

7、題舉例 例2 生產(chǎn)安排問題某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，每件產(chǎn)品所消耗的材料、工時、盈利見表2 已知該工廠每天的材料消耗不超過600千克，工時不超過1400小時，問每天生產(chǎn)甲、乙、丙三種產(chǎn)品各多少事的盈利最大？ 最優(yōu)化問題舉例 設(shè)每天生產(chǎn)甲、乙、丙三種產(chǎn)品分別為 件，因此盈利 ，其相應(yīng)的材料限制為工時限制為再考慮自然限制因此生產(chǎn)安排問題就是在上述限制條件下，使其盈利達到最大。其數(shù)學(xué)表達式為： 321,xxx321637xxx600544321xxx1400324321xxx0, 0, 0321xxx0, 0, 01400324600544 s.t.637)(max321321321321xxxxxxxxxxxxf x最優(yōu)化問題舉例 例3 投資決策問題設(shè)在一段時間（比如三年）內(nèi)，有b億元的基金可用于投資，有m個項目 可供挑選。若對項目 進行投資，需花費 億元，可獲益 億元，試確定最佳的投資方案。引入變量 則需滿足的條件為最佳的投資方案應(yīng)該為：投資少，收益大。若要投資少，則 ；若要收益大，則 。 maaa,21iaiaic不投資，若對投資若對iiiaax0, 1mi, 2 , 1 miixbxamiiii, 2 , 1,1 , 0,1miiixa1minmiiixc1max測試函數(shù) 常見的測試函數(shù)見附件約束最優(yōu)化問題 約束最優(yōu)化問題是實際應(yīng)用中經(jīng)常遇到的一