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

1、1,最優(yōu)化理論與方法 （現(xiàn)代優(yōu)化計算方法）,2,內(nèi) 容,概論 遞歸、分治、貪心、回溯 禁忌搜索、爬山算法 模擬退火、蟻群算法 遺傳算法 神經(jīng)網(wǎng)絡 元胞自動機 隨機算法,3,背 景,傳統(tǒng)實際問題的特點 連續(xù)性問題主要以微積分為基礎，且問題規(guī)模較小 傳統(tǒng)的優(yōu)化方法 追求準確精確解 理論的完美結(jié)果漂亮 主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。 傳統(tǒng)的評價方法 算法收斂性（從極限角度考慮） 收斂速度（線性、超線性、二次收斂等）,4,傳統(tǒng)運籌學面臨新挑戰(zhàn),現(xiàn)代問題的特點 離散性問題主要以組合優(yōu)化（針對離散問題，定義見后）理論為基礎 不確定性問題隨機

2、性數(shù)學模型 半結(jié)構或非結(jié)構化的問題計算機模擬、決策支持系統(tǒng) 大規(guī)模問題并行計算、大型分解理論、近似理論 現(xiàn)代優(yōu)化方法 追求滿意近似解 實用性強解決實際問題 現(xiàn)代優(yōu)化算法的評價方法 算法復雜性,5,現(xiàn)代優(yōu)化(啟發(fā)式)方法種類,禁忌搜索（tabu search） 模擬退火（simulated annealing） 遺傳算法（genetic algorithms） 神經(jīng)網(wǎng)絡（neural networks） 蟻群算法（群體（群集）智能，Swarm Intelligence） 拉格朗日松弛算法（lagrangean relaxation）,6,1 現(xiàn)代優(yōu)化計算方法概述,1.1 組合優(yōu)化問題 1.2 算

3、法 1.3 計算復雜性的概念 1.4 啟發(fā)式算法,7,1.1 組合優(yōu)化問題,組合優(yōu)化（combinatorial optimization）:解決離散問題的優(yōu)化問題運籌學分支。通過數(shù)學方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等。 數(shù)學模型：,8,1.1 組合優(yōu)化問題,組合優(yōu)化問題的三參數(shù)表示：,9,1.1 組合優(yōu)化問題,例1 0-1背包問題（0-1 knapsack problem）,10,1.1 組合優(yōu)化問題,11,1.1 組合優(yōu)化問題,例2 旅行商問題（TSP,traveling salesman problem） 管梅谷教授1960年首先提出，國際上稱之為中國郵遞員問題。 問

4、題描述：一商人去n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。,12,1.1 組合優(yōu)化問題,13,1.1 組合優(yōu)化問題,例3 裝箱問題（bin packing） 尺寸為1的箱子有若干個，怎樣用最少的箱子裝下n個尺寸不超過1 的物品，物品集合為： 。,14,1.1 組合優(yōu)化問題,15,1.1 組合優(yōu)化問題,例4 約束機器排序問題（bin packing） n 個加工量為di|i = 1, 2, , n 的產(chǎn)品在一臺機器上加工,機器在第t個時段的工作能力為ct , 求完成所有產(chǎn)品加工的最少時段數(shù)。,16,1.1 組合優(yōu)化問題,17,1.2 算法,評價算法的好壞計算時間的多少、解的偏離程度

5、 先看看算法的基本概念,一個有窮規(guī)則的有序集合稱為一個算法。,1.定義.,2.算法的特征.,輸 入：有零個或多個外部量作為算法的輸入。 輸 出：算法產(chǎn)生至少一個量作為輸出。 確定性：組成算法的每條指令清晰、無歧義。 有限性：算法中每條指令的執(zhí)行次數(shù)有限。 可行性：執(zhí)行每條指令的時間也有限。,1.2 算法,1有窮性 對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即： 算法中的每個步驟都能在有限時間內(nèi)完成；,2確定性 對于每種情況下所應執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；,3可行性 算法中的所有操作都

6、必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；,4有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中；,5有輸出 它是一組與“輸入”與確 定關系的量值，是算法進行信息加工后得到的結(jié)果，這種確定關系即為算法的功能。,二、算法設計的原則,設計算法時，通常應考慮達到以下目標：,1正確性,2. 可讀性,3健壯性,4高效率與低存儲量需求,1正確性,首先，算法應當滿足以特定的“規(guī)格說明”方式給出的需求。,其次，對算法是否“正確”的理解有四個層次：,a程序中不含語法錯誤；,b程序?qū)τ趲捉M輸入數(shù)據(jù)能

7、夠得出滿足要求的結(jié)果；,c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；,通常以第 c 層意義的正確性作為衡量一個算法是否合格的標準。,d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；,2. 可讀性,算法主要是為了人的閱讀與交流， 其次才是為計算機執(zhí)行。因此算法應該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試；,3健壯性,當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。,4高效率與低存儲

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

9、) ,34,1.3 計算復雜性的概念,評價算法的好壞計算時間的多少、解的偏離程度 例 非對稱距離TSP問題的算法實現(xiàn)：所有路徑枚舉。 計算時間：n個城市，固定1個為起終點需要(n-1)!個枚舉，設計算機1秒能完成24個城市的枚舉，則城市數(shù)與計算時間的關系如下表：,35,1.3 計算復雜性的概念,隨城市增多，計算時間增加很快。到31個城市時，要計算325年。,36,1.3 計算復雜性的概念,描述算法的好壞計算復雜性 討論計算時間與問題規(guī)模之間的關系 以目前二進制計算機中的存儲和計算為基礎，以理論的形式系統(tǒng)描述，是評估算法性能的基礎。,37,1.3 計算復雜性的概念,問題（problem）：要回答

10、的一般性提問，通常含有若干個滿足一定條件的參數(shù)（或自由變量）?？梢詮膬煞矫婷枋觯?（1）對所有參數(shù)的一般性描述； （2）答案（或解）必須滿足的性質(zhì)。 實例（instance）:給問題的所有參數(shù)指定具體值，得到問題的一個實例。這些具體值稱為數(shù)據(jù)；這些數(shù)據(jù)輸入計算機所占的空間稱為實例的長度（size）.,38,1.3 計算復雜性的概念,一類最優(yōu)化問題是由一些類似的具體問題（實例）組成的，每一個具體問題可表達成二元組（F,C）. F為可行解集合;C是費用函數(shù)，是由F到R（實數(shù)集）的映像。 問題是在F中找到一個點f*，使對F中任意的f，有C(f*) C(f),稱f*為這一具體問題的最優(yōu)解（或全局最優(yōu)解

11、）.,39,1.3 計算復雜性的概念,算法計算量的度量： 加、減、乘、除、比較的總運算次數(shù)與實例的計算機計算時的二進制輸入數(shù)據(jù)的大小關系。 正整數(shù)x的二進制位數(shù)是:(整數(shù)到二進制的轉(zhuǎn)換),如何估算 算法的時間復雜度？,算法 = 控制結(jié)構 + 原操作,算法的執(zhí)行時間 = 元操作(i)的執(zhí)行次數(shù)元操作(i)的執(zhí)行時間,從算法中選取一種對于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復執(zhí)行的次數(shù) 作為算法運行時間的衡量準則。,43,1.3 計算復雜性的概念,算法計算量的度量之例TSP枚舉法,計算量的統(tǒng)計：,44,1.3 計算復雜性的概念,實例的輸入長度：,實例的輸入長度是n的多項

12、式函數(shù) 枚舉法的基本計算量是n的階乘函數(shù)， 隨n的增加，比指數(shù)函數(shù)增加得還快.,45,1.3 計算復雜性的概念,46,1.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ù)時間算法。,47,1.3 計算復雜性的概念,利用復雜性分析對組合優(yōu)化問題歸類。 定義多項式問題 給定一個組合優(yōu)化問題，若存在一個多項式算法，稱該問題為多項式時間可解問題，或簡稱多項

13、式問題(或P問題). 所有多項式問題的集合記為P.,48,1.3 計算復雜性的概念,迄今為止, 對許多的組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法, 因此, 比多項式問題更廣泛的一類問題是非多項式 確定( nondeterministic polynomial, 簡記NP) 問題。,例 一 兩 個 矩 陣 相 乘,void mult(int a, int b, int /for /mult,基本操作: 乘法操作,時間復雜度: O(n3),常用的時間復雜度有如下的關系： O(1)=O(log2n)=O(n) =O(nlog2n)=O(n2)=O(2n) =O(n!),四、算法的存儲空間需求,

14、算法的空間復雜度定義為:,表示隨著問題規(guī)模 n 的增大， 算法運行所需存儲量的增長率 與 g(n) 的增長率相同。,S(n) = O(g(n),算法的存儲量包括:,1輸入數(shù)據(jù)所占空間,2程序本身所占空間；,3輔助變量所占空間。,53,1.3 計算復雜性參考書,計算復雜性, 作者：Christos，Papadimitriou 清華大學出版社，2004年9月第1版 計算復雜性導論，作者：堵丁柱等， 高等教育出版社，2002年8月第1版,鄰域概念 對于組合優(yōu)化問題(D,F,f),D上的一個映射： N:SD N(S)2D 稱為一個鄰域映射，其中2D表示D的所有子集構成的集合，N(S)稱為S的鄰域。 鄰

15、域的構造依賴于問題決策變量的表示，鄰域的結(jié)構在現(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

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

17、與最優(yōu)解的偏離程度.,1.4 啟發(fā)式算法,60,1.4 啟發(fā)式算法,優(yōu)點： （1）有可能比簡化數(shù)學模型解的誤差小； （2）對有些難題，計算時間可接受； （3）可用于某些最優(yōu)化算法（如分支定界算 法）之中的估界； （4）直觀易行； （5）速度較快； （6）程序簡單，易修改。,61,1.4 啟發(fā)式算法,不足： （1）不能保證求得全局最優(yōu)解； （2）解的精度不穩(wěn)定，有時好有時壞； （3）算法設計與問題、設計者經(jīng)驗、技術 有關，缺乏規(guī)律性； （4）不同算法之間難以比較。,背包問題的貪婪算法 1）將物品以ci/ai（單位體積的價值）由大到小的順序排列，不妨把排列記為1,2,n,k:=1; 2）若 ，則x

18、k=1;否則xk=0,k:=k+1; 3) 當k=n+1時，停止；否則，轉(zhuǎn)2). (x1,x2,xn)為貪婪算法所得解，單位體積的價值越大越先放入是貪婪算法的原則。,1.4 啟發(fā)式算法,簡單的鄰域搜索算法 給定組合優(yōu)化問題，假設其鄰域結(jié)構已確定，算法為 1）任選一個初始解s0F; 2) 在N(s0)中按某一規(guī)則選一s；若f(s)f(s0),則s0s；否則，N(s0) N(s0)-s; 3) 若N(s0)=,停止；否則，返回2).,1.4 啟發(fā)式算法,算法停止時得到點的性質(zhì)依賴算法初始解的選取、鄰域的結(jié)構. 只要選好初始點，就一定可以求到最優(yōu)解。對NP-hard的組合最優(yōu)化問題，確定這樣的初始點非常困難。如何選初始點和如何跳出局部最優(yōu)值點以達到全局最優(yōu)點是許多算法的關鍵。,1.4 啟發(fā)式算法,65,1.4 啟發(fā)式算法,（1）一步算法 （2）改進算法（迭代算法） （3） 數(shù)學規(guī)劃算法 （4） 解空間松弛法 （5）現(xiàn)代優(yōu)化