《第五章--物流系統(tǒng)的智能優(yōu)化方法ppt課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《第五章--物流系統(tǒng)的智能優(yōu)化方法ppt課件.ppt（100頁珍藏版）》請在匯文網(wǎng)上搜索。

1、物流系統(tǒng)的智能優(yōu)化方法,2,課程內(nèi)容 模擬退火算法、遺傳算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法課程目標(biāo) 了解智能優(yōu)化的模型結(jié)構(gòu)；理解模擬退火算法的收斂性條件；掌握智能優(yōu)化的流程、操作、算法理論與技術(shù)物流系統(tǒng)優(yōu)化的智能優(yōu)化方法為復(fù)雜物流管理決策問題提供了重要的可行性解決方案。,3,模擬退火算法(Simulated Annealing),1、 基本思想 (1)是基于Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。 (2)結(jié)合爬山法和隨機(jī)行走 注：SA算法最早是由Metropolis等(1953)提出,4,(3)模擬

2、退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。,模擬退火算法(Simulated Annealing),5,2、 物理退火過程和Metropolis準(zhǔn)則簡單而言，物理退火過程由以下三部分組成：加溫過程。其目的是增強(qiáng)粒子的熱運(yùn)動，使其偏離平衡位置。當(dāng)溫度足夠高時，固體將溶解為液體，從而消除系統(tǒng)原先可能存在的非均勻態(tài)，使隨后進(jìn)行的冷卻過程以某一平衡態(tài)為起點(diǎn)。溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。,模擬退火算法(

3、Simulated Annealing),6,等溫過程。物理學(xué)的知識告訴我們，對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時，系統(tǒng)達(dá)到平衡態(tài)。 冷卻過程。目的是使粒子的熱運(yùn)動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。,模擬退火算法(Simulated Annealing),7,Metropolis等在1953年提出了重要性采樣法，即以概率接受新狀態(tài)。具體而言，在溫度t,由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為 ，若 則接受新狀態(tài)j為當(dāng)前狀態(tài)；否則，若概率 大于 區(qū)間內(nèi)的隨機(jī)數(shù)則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài)，若不成立則

4、保留i為當(dāng)前狀態(tài)，其中k為Boltzmann常數(shù)。,模擬退火算法(Simulated Annealing),8,這種重要性采樣過程在高溫下可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)，而在低溫下基本只接受與當(dāng)前能量差較小的新狀態(tài)，而且當(dāng)溫度趨于零時，就不能接受比當(dāng)前狀態(tài)能量高的新狀態(tài)。這種接受準(zhǔn)則通常稱為Metropolis準(zhǔn)則。,模擬退火算法(Simulated Annealing),9,2、 算法步驟標(biāo)準(zhǔn)模擬退火算法的一般步驟可描述如下： 給定初溫 ，隨機(jī)產(chǎn)生初始狀態(tài) ，令 ；Repeat: Repeat 產(chǎn)生新狀態(tài) ；,模擬退火算法(Simulated Annealing),10,Until 抽樣

5、穩(wěn)定準(zhǔn)則滿足； 退溫 ，并 令 ； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。,模擬退火算法(Simulated Annealing),11,3、 算法關(guān)鍵參數(shù)和操作的設(shè)定 從算法流程上看，模擬退火算法包括三函數(shù)兩準(zhǔn)則，即狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則，這些環(huán)節(jié)的設(shè)計將決定SA算法的優(yōu)化性能。此外，初溫的選擇對SA算法性能也有很大影響。,模擬退火算法(Simulated Annealing),12,狀態(tài)產(chǎn)生函數(shù) 設(shè)計狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點(diǎn)應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和

6、候選解產(chǎn)生的概率分布。,模擬退火算法(Simulated Annealing),13,狀態(tài)接受函數(shù) 狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計狀態(tài)接受概率，應(yīng)該遵循以下原則：在固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)值上升的候選解的概率；,模擬退火算法(Simulated Annealing),14,隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減??；當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)值下降的解。狀態(tài)接受函數(shù)的引入是SA算法實(shí)現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min1,exp(-C/t)作為狀態(tài)接受函數(shù)。,模擬退火算法(S

7、imulated Annealing),15,初溫 初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則通常被稱為退火歷程(annealing schedule)。實(shí)驗(yàn)表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計算時間將增加。因此，初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括：,模擬退火算法(Simulated Annealing),16,均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差 ，然后依據(jù)差值，利用一定的函數(shù)確定初溫。譬如 ，其中 為初始接受概率。利用經(jīng)驗(yàn)公式給出。,模擬退火算法(Simulated Annealing),1

8、7,溫度更新函數(shù)溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。目前，最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù)，即，其中且其大小可以不斷變化。,模擬退火算法(Simulated Annealing),18,內(nèi)循環(huán)終止準(zhǔn)則 內(nèi)循環(huán)終止準(zhǔn)則，或稱Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。在非時齊SA算法理論中，由于在每個溫度下只產(chǎn)生一個或少量候選解，所以不存在選擇內(nèi)循環(huán)終止準(zhǔn)則的問題。,模擬退火算法(Simulated Annealing),19,而在時齊SA算法理論中，收斂條件要求在每個溫度下產(chǎn)生候選解的數(shù)目趨于無窮大，以使相應(yīng)的馬氏鏈達(dá)到平穩(wěn)概率分布，顯然在實(shí)際

9、應(yīng)用算法時這是無法實(shí)現(xiàn)的。常用的抽樣準(zhǔn)則包括： 檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； 連續(xù)若干步的目標(biāo)值變化較小； 按一定的步數(shù)抽樣。,模擬退火算法(Simulated Annealing),20,外循環(huán)終止準(zhǔn)則 外循環(huán)終止準(zhǔn)則，即算法終止準(zhǔn)則，用于決定算法何時結(jié)束。設(shè)置溫度終值是一種簡單的方法。SA算法的收斂性理論中要求溫度終值趨于零，這顯然不合實(shí)際。通常的做法是： 設(shè)置終止溫度的閾值； 設(shè)置外循環(huán)迭代次數(shù)； 算法搜索到的最優(yōu)值連續(xù)若干步保持不變； 檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。,模擬退火算法(Simulated Annealing),21,小結(jié),由于算法的一些環(huán)節(jié)無法在實(shí)際設(shè)計算法時實(shí)現(xiàn)，因此SA算法往往得

10、不到全局最優(yōu)解，或算法結(jié)果存在波動性。目前，SA算法參數(shù)的選擇仍依賴于一些啟發(fā)式準(zhǔn)則和待求問題的性質(zhì)。SA算法的通用性很強(qiáng)，算法易于實(shí)現(xiàn)，但要真正取得質(zhì)量和可靠性高、初值魯棒性好的效果，克服計算時間較長、效果較低的缺點(diǎn)，并適用于規(guī)模較大的問題，尚需進(jìn)行大量的研究工作。,22,1、基本概念 模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。,遺傳算法,23,2、基本思想 對于一個求函數(shù)最大值的優(yōu)化問題，一般可描述為下述數(shù)學(xué)規(guī)劃模型：,遺傳算法,24,式中， 為決策變量，f(X)為目標(biāo)函數(shù)，U是基本空間，R是U的一個子集。遺傳算法中，將n維決策向量用n個記號所組成的符號串

11、X來表示：,遺傳算法,25,把每一個 看作一個遺傳基因，它的所有可能取值稱為等位基因，這樣，X就可看作是由n個遺傳基因所組成的一個染色體。染色體的長度可以是固定的，也可以是變化的。等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是記號。最簡單的等位基因是由0和1這兩個整數(shù)組成的，相應(yīng)的染色體就可表示為一個二進(jìn)制符號串。,遺傳算法,26,這種編碼所形成的排列形式X是個體的基因型，與它對應(yīng)的X值是個體的表現(xiàn)型。染色體X也稱為個體X，對于每一個個體X，要按照一定的規(guī)則確定出其適應(yīng)度。個體的適應(yīng)度與其對應(yīng)的個體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點(diǎn)，其適應(yīng)度越大；反之，其適應(yīng)度

12、越小。,遺傳算法,27,遺傳算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體X的搜索過程來進(jìn)行的，從而由所有的染色體X就組成了問題的搜索空間。 生物的進(jìn)化是以集團(tuán)為主體的。與此相對應(yīng)，遺傳算法的運(yùn)算對象是由M個個體所組成的集合，稱為群體。,遺傳算法,28,與生物一代一代的自然進(jìn)化過程相似，遺傳算法的運(yùn)算過程也是一個反復(fù)迭代過程，第t代群體記做P(t),經(jīng)過一代遺傳和進(jìn)化后，得到第t+1代群體，它們也是由多個個體組成的集合，記做P(t+1)。這個群體不斷地經(jīng)過遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個體更多地遺傳到下一代，這樣最終在群體中將會得到一個優(yōu)良的

13、個體X，它所對應(yīng)的表現(xiàn)型X將達(dá)到或接近于問題的最優(yōu)解 。,遺傳算法,29,生物的進(jìn)化過程主要是通過染色體之間的交叉和染色體的變異來完成的。遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個進(jìn)化過程，使用所謂的遺傳算子(genetic operators)作用于群體P(t)中，進(jìn)行下述遺傳操作，從而得到新一代群體P(t+1)。,遺傳算法,30,選擇(selection):根據(jù)各個個體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中。 交叉(crossover):將群體P(t)內(nèi)的各個個體隨機(jī)搭配成對，對每一個個體，以某個概率(稱為交叉概率，cros

14、sover rate)交換它們之間的部分染色體。,遺傳算法,31,變異(mutation):對群體P(t)中的每一個個體，以某一概率(稱為變異概率，mutation rate)改變某一個或一些基因座上基因值為其它的等位基因。,遺傳算法,32,3、 特點(diǎn)遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計算的魯棒搜索算法，與其他一些優(yōu)化算法相比，主要有下述幾個特點(diǎn)：遺傳算法以決策變量的編碼作為運(yùn)算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身進(jìn)行優(yōu)化計算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對象，從而可以很方便地引入和應(yīng)用遺傳操作算子。,遺傳算法,33,遺傳算法直接以目標(biāo)函

15、數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法往往不只需要目標(biāo)函數(shù)值，還需要目標(biāo)函數(shù)的導(dǎo)數(shù)等其它信息。這樣對許多目標(biāo)函數(shù)無法求導(dǎo)或很難求導(dǎo)的函數(shù)，遺傳算法就比較方便。,遺傳算法,34,遺傳算法同時進(jìn)行解空間的多點(diǎn)搜索。傳統(tǒng)的優(yōu)化算法往往從解空間的一個初始點(diǎn)開始搜索，這樣容易陷入局部極值點(diǎn)。遺傳算法進(jìn)行群體搜索，而且在搜索的過程中引入遺傳運(yùn)算，使群體又可以不斷進(jìn)化。這些是遺傳算法所特有的一種隱含并行性。,遺傳算法,35,遺傳算法使用概率搜索技術(shù) 。遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。實(shí)踐和理論都已證明了在一定條件下遺傳算法總是

16、以概率1收斂于問題的最優(yōu)解。,遺傳算法,36,3、 應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面列舉一些遺傳算法的主要應(yīng)用領(lǐng)域。,遺傳算法,37,組合優(yōu)化：遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實(shí)踐證明，遺傳算法對于組合優(yōu)化問題中的NP完全問題非常有效。,遺傳算法,38,生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解也會因簡化得太多而使求解結(jié)果與實(shí)際相差太遠(yuǎn)。現(xiàn)在遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問題的有效工具。,遺傳算法,39,自動控制：遺傳算法已經(jīng)在自動控制領(lǐng)域中得到了很好的應(yīng)用，例如基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等。,遺傳算法,40,機(jī)器人學(xué)：機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人學(xué)自然成為遺傳算法的一個重要應(yīng)用領(lǐng)域。,遺傳算法,41,圖象處理：圖像處