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

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

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

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

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

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

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

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

8、量需求,通常，效率指的是算法執(zhí)行 時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程 中所需的最大存儲(chǔ)空間。兩者都與 問(wèn)題的規(guī)模有關(guān)。,算法的描述方法.,（1）自然語(yǔ)言,（2）流程圖,（3）程序設(shè)計(jì)語(yǔ)言,例.,求正整數(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 計(jì)算復(fù)雜性的概念,評(píng)價(jià)算法的好壞計(jì)算時(shí)間的多少、解的偏離程度 例 非對(duì)稱(chēng)距離TSP問(wèn)題的算法實(shí)現(xiàn)：所有路徑枚舉。 計(jì)算時(shí)間：n個(gè)城市，固定1個(gè)為起終點(diǎn)需要(n-1)!個(gè)枚舉，設(shè)計(jì)算機(jī)1秒能完成24個(gè)城市的枚舉，則城市數(shù)與計(jì)算時(shí)間的關(guān)系如下表：,35,1.3 計(jì)算復(fù)雜性的概念,隨城市增多，計(jì)算時(shí)間增加很快。到31個(gè)城市時(shí)，要計(jì)算325年。,36,1.3 計(jì)算復(fù)雜性的概念,描述算法的好壞計(jì)算復(fù)雜性 討論計(jì)算時(shí)間與問(wèn)題規(guī)模之間的關(guān)系 以目前二進(jìn)制計(jì)算機(jī)中的存儲(chǔ)和計(jì)算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評(píng)估算法性能的基礎(chǔ)。,37,1.3 計(jì)算復(fù)雜性的概念,問(wèn)題（problem）：要回答

10、的一般性提問(wèn)，通常含有若干個(gè)滿(mǎn)足一定條件的參數(shù)（或自由變量）。可以從兩方面描述： （1）對(duì)所有參數(shù)的一般性描述； （2）答案（或解）必須滿(mǎn)足的性質(zhì)。 實(shí)例（instance）:給問(wèn)題的所有參數(shù)指定具體值，得到問(wèn)題的一個(gè)實(shí)例。這些具體值稱(chēng)為數(shù)據(jù)；這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱(chēng)為實(shí)例的長(zhǎng)度（size）.,38,1.3 計(jì)算復(fù)雜性的概念,一類(lèi)最優(yōu)化問(wèn)題是由一些類(lèi)似的具體問(wèn)題（實(shí)例）組成的，每一個(gè)具體問(wèn)題可表達(dá)成二元組（F,C）. F為可行解集合;C是費(fèi)用函數(shù)，是由F到R（實(shí)數(shù)集）的映像。 問(wèn)題是在F中找到一個(gè)點(diǎn)f*，使對(duì)F中任意的f，有C(f*) C(f),稱(chēng)f*為這一具體問(wèn)題的最優(yōu)解（或全局最優(yōu)解

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

12、式函數(shù) 枚舉法的基本計(jì)算量是n的階乘函數(shù)， 隨n的增加，比指數(shù)函數(shù)增加得還快.,45,1.3 計(jì)算復(fù)雜性的概念,46,1.3 計(jì)算復(fù)雜性的概念,定義 多項(xiàng)式算法 給定問(wèn)題P，算法A，對(duì)一個(gè)實(shí)例I，存在多項(xiàng)式 函數(shù)g(x)，使（XX ）成立，稱(chēng)算法A對(duì)實(shí)例I是 多項(xiàng)式算法； 若存在多項(xiàng)式函數(shù)g(x)，使（XX ）對(duì)問(wèn)題P的任 意實(shí)例I都成立，稱(chēng)算法A為解決該問(wèn)題P的多項(xiàng) 式算法. 當(dāng)g(x)為指數(shù)函數(shù)時(shí)，稱(chēng)A為P的指數(shù)時(shí)間算法。,47,1.3 計(jì)算復(fù)雜性的概念,利用復(fù)雜性分析對(duì)組合優(yōu)化問(wèn)題歸類(lèi)。 定義多項(xiàng)式問(wèn)題 給定一個(gè)組合優(yōu)化問(wèn)題，若存在一個(gè)多項(xiàng)式算法，稱(chēng)該問(wèn)題為多項(xiàng)式時(shí)間可解問(wèn)題，或簡(jiǎn)稱(chēng)多項(xiàng)

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

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

15、域的構(gòu)造依賴(lài)于問(wèn)題決策變量的表示，鄰域的結(jié)構(gòu)在現(xiàn)代化優(yōu)化算法中起重要作用。,1.4 啟發(fā)式算法,鄰域概念 例如,TSP問(wèn)題解的另一種表示法為 D=S=(i1,i2,in)是1,2,n的一個(gè)排列 可以定義它的鄰域映射為2-opt，即S中的兩個(gè)元素對(duì)換。,1.4 啟發(fā)式算法,鄰域概念,1.4 啟發(fā)式算法,如4個(gè)城市的TSP問(wèn)題，當(dāng)S=(1,2,3,4)時(shí)，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). 類(lèi)似可定義k-opt(k2),局部最優(yōu)與全局最優(yōu),1.4 啟發(fā)式算法,若s*滿(mǎn)足 f(s*)()f(s),其中sN

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

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

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