最優(yōu)化理論與方法第一章

1最優(yōu)化理論與方法（現(xiàn)代優(yōu)化計算方法）2內容概論遞歸、分治、貪心、回溯禁忌搜索、爬山算法模擬退火、蟻群算法遺傳算法神經(jīng)網(wǎng)絡元胞自動機隨機算法3背景傳統(tǒng)實際問題的特點連續(xù)性問題——主要以微積分為基礎，且問題規(guī)模較小傳統(tǒng)的優(yōu)化方法追求準確——精確解理論的完美——結果漂亮主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。傳統(tǒng)的評價方法算法收斂性（從極限角度考慮）收斂速度（線性、超線性、二次收斂等）4傳統(tǒng)運籌學面臨新挑戰(zhàn)現(xiàn)代問題的特點離散性問題——主要以組合優(yōu)化（針對離散問題，定義見后）理論為基礎不確定性問題——隨機性數(shù)學模型半結構或非結構化的問題——計算機模擬、決策支持系統(tǒng)大規(guī)模問題——并行計算、大型分解理論、近似理論現(xiàn)代優(yōu)化方法追求滿意——近似解實用性強——解決實際問題現(xiàn)代優(yōu)化算法的評價方法算法復雜性5現(xiàn)代優(yōu)化(啟發(fā)式)方法種類禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡（neuralnetworks）蟻群算法（群體（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangeanrelaxation）61現(xiàn)代優(yōu)化計算方法概述1.1組合優(yōu)化問題1.2算法1.3計算復雜性的概念1.4啟發(fā)式算法71.1組合優(yōu)化問題組合優(yōu)化（combinatorialoptimization）:解決離散問題的優(yōu)化問題——運籌學分支。通過數(shù)學方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等。數(shù)學模型：81.1組合優(yōu)化問題組合優(yōu)化問題的三參數(shù)表示：

91.1組合優(yōu)化問題例10-1背包問題（0-1knapsackproblem）101.1組合優(yōu)化問題111.1組合優(yōu)化問題例2旅行商問題（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，國際上稱之為中國郵遞員問題。問題描述：一商人去n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。121.1組合優(yōu)化問題131.1組合優(yōu)化問題例3裝箱問題（binpacking）尺寸為1的箱子有若干個，怎樣用最少的箱子裝下n個尺寸不超過1的物品，物品集合為：。

141.1組合優(yōu)化問題151.1組合優(yōu)化問題例4約束機器排序問題（binpacking）

n個加工量為{di|i=1,2,?,n}的產品在一臺機器上加工,機器在第t個時段的工作能力為ct,求完成所有產品加工的最少時段數(shù)。

161.1組合優(yōu)化問題171.2算法評價算法的好壞——計算時間的多少、解的偏離程度先看看算法的基本概念一個有窮規(guī)則的有序集合稱為一個算法。1.定義.2.算法的特征.輸入：有零個或多個外部量作為算法的輸入。輸出：算法產生至少一個量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限。可行性：執(zhí)行每條指令的時間也有限。1.2算法1．有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間內完成；

2．確定性

對于每種情況下所應執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；3．可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；4．有輸入作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中；

5．有輸出它是一組與“輸入”與確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。二、算法設計的原則設計算法時，通常應考慮達到以下目標：1．正確性2.可讀性3．健壯性4．高效率與低存儲量需求1．正確性首先，算法應當滿足以特定的“規(guī)格說明”方式給出的需求。

其次，對算法是否“正確”的理解有四個層次：a．程序中不含語法錯誤；b．程序對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果；

c．程序對于精心選擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結果；通常以第

c層意義的正確性作為衡量一個算法是否合格的標準。

d．程序對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結果；2.可讀性

算法主要是為了人的閱讀與交流，其次才是為計算機執(zhí)行。因此算法應該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試；3．健壯性

當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。4．高效率與低存儲量需求

通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關。算法的描述方法.（1）自然語言（2）流程圖（3）程序設計語言例.求正整數(shù)m、n的最大公因數(shù)。解一.（1）求余數(shù)：用m除以n，得余數(shù)r(0≤r﹤n)。（2）判斷余數(shù)：若余數(shù)r=0，輸出n，結束。否則，轉（3）。（3）更新被除數(shù)和除數(shù)：m←n，n←r，轉(1)。解二.開始輸入m、nr=m%nr=0?m←n，n←r輸出n是否解三.Euclid(intm,intn){intr;while(n!=0){r=m%n;

m=n;

n=r;

}printf(“%d”,m)}341.3計算復雜性的概念評價算法的好壞——計算時間的多少、解的偏離程度例非對稱距離TSP問題的算法實現(xiàn)：所有路徑枚舉。計算時間：n個城市，固定1個為起終點需要(n-1)!個枚舉，設計算機1秒能完成24個城市的枚舉，則城市數(shù)與計算時間的關系如下表：351.3計算復雜性的概念城市數(shù)2425262728293031計算時間1sec24sec10min4.3hour4.9day136.5day10.8year325year隨城市增多，計算時間增加很快。到31個城市時，要計算325年。361.3計算復雜性的概念描述算法的好壞——計算復雜性——討論計算時間與問題規(guī)模之間的關系以目前二進制計算機中的存儲和計算為基礎，以理論的形式系統(tǒng)描述，是評估算法性能的基礎。371.3計算復雜性的概念問題（problem）：要回答的一般性提問，通常含有若干個滿足一定條件的參數(shù)（或自由變量）?？梢詮膬煞矫婷枋觯海?）對所有參數(shù)的一般性描述；（2）答案（或解）必須滿足的性質。實例（instance）:給問題的所有參數(shù)指定具體值，得到問題的一個實例。這些具體值稱為數(shù)據(jù)；這些數(shù)據(jù)輸入計算機所占的空間稱為實例的長度（size）.381.3計算復雜性的概念一類最優(yōu)化問題是由一些類似的具體問題（實例）組成的，每一個具體問題可表達成二元組（F,C）.F為可行解集合;C是費用函數(shù)，是由F到R（實數(shù)集）的映像。問題是在F中找到一個點f*，使對F中任意的f，有C(f*)C(f),稱f*為這一具體問題的最優(yōu)解（或全局最優(yōu)解）.391.3計算復雜性的概念算法計算量的度量：加、減、乘、除、比較的總運算次數(shù)與實例的計算機計算時的二進制輸入數(shù)據(jù)的大小關系。正整數(shù)x的二進制位數(shù)是:(整數(shù)到二進制的轉換)

如何估算算法的時間復雜度？算法=控制結構+原操作

算法的執(zhí)行時間

=元操作(i)的執(zhí)行次數(shù)×元操作(i)的執(zhí)行時間

從算法中選取一種對于所研究的問題來說是基本操作

的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則。431.3計算復雜性的概念算法計算量的度量之例——TSP枚舉法計算量的統(tǒng)計：441.3計算復雜性的概念實例的輸入長度：實例的輸入長度是n的多項式函數(shù)枚舉法的基本計算量是n的階乘函數(shù)，隨n的增加，比指數(shù)函數(shù)增加得還快.451.3計算復雜性的概念461.3計算復雜性的概念定義多項式算法給定問題P，算法A，對一個實例I，存在多項式函數(shù)g(x)，使（XX）成立，稱算法A對實例I是多項式算法；若存在多項式函數(shù)g(x)，使（XX）對問題P的任意實例I都成立，稱算法A為解決該問題P的多項式算法.當g(x)為指數(shù)函數(shù)時，稱A為P的指數(shù)時間算法。471.3計算復雜性的概念利用復雜性分析對組合優(yōu)化問題歸類。定義多項式問題給定一個組合優(yōu)化問題，若存在一個多項式算法，稱該問題為多項式時間可解問題，或簡稱多項式問題(或P問題).所有多項式問題的集合記為P.481.3計算復雜性的概念迄今為止,對許多的組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法,因此,比多項式問題更廣泛的一類問題是非多項式確定(nondeterministicpolynomial,簡記NP)問題。例一兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲矩陣元素，c為a和b的乘積

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作時間復雜度:

O(n3)

常用的時間復雜度有如下的關系：O(1)<=O(log2n)<=O(n)<=O(nlog2n)<=O(n2)<=O(2n)<=O(n!)四、算法的存儲空間需求算法的空間復雜度定義為:

表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))算法的存儲量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間；3．輔助變量所占空間。531.3計算復雜性參考書計算復雜性,

作者：Christos，Papadimitriou

清華大學出版社，2004年9月第1版計算復雜性導論，作者：堵丁柱等，高等教育出版社，2002年8月第1版

鄰域概念

對于組合優(yōu)化問題(D,F,f),D上的一個映射：N:SDN(S)2D稱為一個鄰域映射，其中2D表示D的所有子集構成的集合，N(S)稱為S的鄰域。鄰域的構造依賴于問題決策變量的表示，鄰域的結構在現(xiàn)代化優(yōu)化算法中起重要作用。1.4啟發(fā)式算法鄰域概念例如TSP問題解的另一種表示法為D={S=(i1,i2,…,in)是1,2,…,n的一個排列}可以定義它的鄰域映射為2-opt，即S中的兩個元素對換。1.4啟發(fā)式算法鄰域概念1.4啟發(fā)式算法

如4個城市的TSP問題，當S=(1,2,3,4)時，N(S)={(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}.類似可定義k-opt(k2)局部最優(yōu)與全局最優(yōu)1.4啟發(fā)式算法

若s*滿足f(s*)()f(s),其中sN(s*)F,則稱s*為f在F上的局部(local)最小（最大）解。若s*滿足f(s*)()f(s),其中sF,則稱s*為f在F上的全局(global)最?。ㄗ畲螅┙狻?81.4啟發(fā)式算法啟發(fā)式算法（heuristicalgorithm）定義1.基于直觀或經(jīng)驗構造的算法，在可接受的花費（時間、空間）下，給出待解組合優(yōu)化問題的每個實例的一個可行解，該可行解與最優(yōu)解偏差事先不一定可以預計.定義2.啟發(fā)式算法是一種技術，在可接受的計算費用內尋找最好解，但不保證該解的可行性與最優(yōu)性，無法描述該解與最優(yōu)解的近似程度。特點（與傳統(tǒng)優(yōu)化方法不同）：憑直觀和經(jīng)驗給出算法；不考慮所得解與最優(yōu)解的偏離程度.近似算法定義

記問題A的任何一個實例I的最優(yōu)解和啟發(fā)式算法H解的目標值分別為zopt(I)和zH(I),若對某個正數(shù)0，有|zH(I)-zopt(I)||zopt(I)|，IA則稱H是A的近似算法。1.4啟發(fā)式算法601.4啟發(fā)式算法

優(yōu)點：（1）有可能比簡化數(shù)學模型解的誤差??；（2）對有些難題，計算時間可接受；（3）可用于某些最優(yōu)化算法（如分支定界算法）之中的估界；（4）直觀易行；（5）速度較快；（6）程序簡單，易修改。611.4啟發(fā)式算法不足：（1）不能保證求得全局最優(yōu)解；（2）解的精度不穩(wěn)定，有時好有時壞；（3）算法設計與問題、設計者經(jīng)驗、技術有關，缺乏規(guī)律性；（4）不同算法之間難以比較。

背包問題的貪婪算法1）將物品以ci/ai（單位體積的價值）由大到小的順序排列，不妨把排列記為{1,2,…,n},k:=1;2）若，則xk=1;否則xk=0,k:=k+1;3)當k=n+1時，停止；否則，轉2).(x1,x2,…,xn)為貪婪算法所得解，單位體積的價值越大越先放入是貪婪算法的原則。1.4啟發(fā)式算法

簡單的鄰域搜索算法給定組合優(yōu)化問題，假設其鄰域結構已確定，算法為1）任選一個初始解s0F;2)在N(s0)中按某一規(guī)則選一s；若f(s)<f(s0),則s0s；否則，N(s0)N(s0)-s;3)若N(s0)=,停止；否則，返回2).1.4啟發(fā)式算法算法停止時得到點的性質依賴算法初始解的選取、鄰域的結構.只要選好初始點，就一定可以求到最優(yōu)解。對NP-hard的組合最優(yōu)化問題，確定這樣的初始點非常困難。如何選初始點和如何跳出局部最優(yōu)值點以達到全局最優(yōu)點是許多算法的關鍵。1.4啟發(fā)式算法651.4