電力網(wǎng)網(wǎng)架結(jié)構(gòu)優(yōu)化模擬退火算法設(shè)計(jì)

1、何秦科技太營課程設(shè)計(jì)說明書課程名稱專業(yè)課程設(shè)計(jì)題目電力網(wǎng)網(wǎng)架結(jié)構(gòu)優(yōu)化模擬退火算法設(shè)計(jì)學(xué) 院農(nóng)業(yè)工程學(xué)院班級(jí) 農(nóng)電112學(xué)生姓名 李翔宇指導(dǎo)教師鄧桂揚(yáng)日期 2015年3月28曰一、設(shè)計(jì)目的熟悉專業(yè)課程設(shè)計(jì)的相關(guān)規(guī)程、規(guī)定，了解電力系統(tǒng)，電網(wǎng)設(shè)計(jì)數(shù)學(xué)模型的基本建立方 法和相關(guān)算法的計(jì)算機(jī)模擬，熟悉相關(guān)電力計(jì)算的內(nèi)容，鞏固已學(xué)習(xí)的相關(guān)專業(yè)課程閃容， 學(xué)習(xí)撰寫工程設(shè)計(jì)說明書，對(duì)電力系統(tǒng)相關(guān)狀態(tài)進(jìn)行模擬，對(duì)電網(wǎng)設(shè)計(jì)相關(guān)參數(shù)計(jì)算機(jī)計(jì)算 設(shè)計(jì)有初步的認(rèn)識(shí)。二、設(shè)計(jì)要求（1）通過對(duì)相應(yīng)文獻(xiàn)的收集、分析以及總結(jié)，給出相應(yīng)項(xiàng)目分析，建立數(shù)學(xué)模型。（2）通過課題設(shè)計(jì)，掌握電力系統(tǒng)計(jì)算機(jī)算法設(shè)計(jì)的方法和設(shè)計(jì)步驟。（3

2、）學(xué)習(xí)按要求編寫課程設(shè)計(jì)報(bào)告書，能正確闡述設(shè)計(jì)方法和計(jì)算結(jié)果。（4）學(xué)生應(yīng)抱著嚴(yán)謹(jǐn)認(rèn)真的態(tài)度積極投入到課程設(shè)計(jì)過程中，認(rèn)真查閱相應(yīng)文獻(xiàn)以及實(shí)現(xiàn)， 給出個(gè)人分析、設(shè)計(jì)以及實(shí)現(xiàn)。三、設(shè)計(jì)任務(wù)（一）設(shè)計(jì)n容1. 了解國內(nèi)外電力網(wǎng)網(wǎng)架結(jié)構(gòu)及其優(yōu)化類算法的發(fā)展水平和主要分析趨勢，弄清該課 題的研宄目的和意義。2. 確定電力網(wǎng)網(wǎng)架結(jié)構(gòu)優(yōu)化的設(shè)計(jì)性能指標(biāo)和總體設(shè)計(jì)方案，規(guī)劃算法步驟。3. 確定電力網(wǎng)網(wǎng)架結(jié)構(gòu)優(yōu)化的算法步驟后，編程實(shí)現(xiàn)算法（實(shí)現(xiàn)算法的語言不限），要 求算法的運(yùn)算速度合理，設(shè)計(jì)網(wǎng)架結(jié)構(gòu)合理，繪制網(wǎng)架結(jié)構(gòu)仿真效果閣，分析對(duì)比兩種以上 網(wǎng)架結(jié)構(gòu)的區(qū)別。4. 對(duì)電力網(wǎng)網(wǎng)架結(jié)構(gòu)進(jìn)行必要的再優(yōu)化，分析算法

3、的弱點(diǎn)，寫出優(yōu)化建議。（二）設(shè)計(jì)任務(wù)1. 建立相關(guān)算法、模型。2. 設(shè)計(jì)說明書，包桮全部設(shè)計(jì)內(nèi)容，對(duì)電力系統(tǒng)相關(guān)狀態(tài)進(jìn)行模擬。3. 總體方案閣，仿真軟件模擬波形圖，計(jì)算相關(guān)參數(shù)。四、設(shè)計(jì)時(shí)間安排查找相關(guān)資料（2天）、確定總體方案，進(jìn)行必要的計(jì)算。（1天）、對(duì)電力系統(tǒng)相關(guān) 狀態(tài)進(jìn)行模擬，計(jì)算相關(guān)參數(shù)，（2天）、使用（matlab）等相關(guān)軟件進(jìn)行電路閣系統(tǒng)閣設(shè)計(jì)與仿真。（2天）、撰寫設(shè)計(jì)報(bào)告（2 天）和答辯（1天）。五、主要參考文獻(xiàn)1 電力工程基礎(chǔ)2 工廠供電，電力系統(tǒng)分析3 相關(guān)設(shè)計(jì)仿真軟件手冊，如（matlab）等。4 數(shù)學(xué)建模算法分析等5 電氣工程設(shè)計(jì)手冊等2圖書館屮文數(shù)據(jù)庫“萬方數(shù)字化期刊

4、”其他相關(guān)網(wǎng)絡(luò)資料指導(dǎo)教師簽字.電力網(wǎng)網(wǎng)架結(jié)構(gòu)優(yōu)化設(shè)計(jì)的模擬退火算法設(shè)計(jì)摘要電力網(wǎng)網(wǎng)架優(yōu)化是一個(gè)多目標(biāo)、多階段、離散的、非線性、受約束的混合整 數(shù)規(guī)劃問題。傳統(tǒng)的優(yōu)化算法已不能滿足規(guī)劃需要，以人工智能技術(shù)為基礎(chǔ)的各 類優(yōu)化算法逐漸成為規(guī)劃的主流算法。該文綜述了近年來電網(wǎng)網(wǎng)架優(yōu)化規(guī)劃領(lǐng)域 的國內(nèi)外研宄成果。針對(duì)輸電網(wǎng)和中低壓配電網(wǎng)的不同特點(diǎn)，分析了相應(yīng)數(shù)學(xué)模 型的建立和基于智能技術(shù)的尋優(yōu)算法研宄中的成果和進(jìn)展。重點(diǎn)探討了中低壓配 電網(wǎng)網(wǎng)架優(yōu)化問題建模和算法研宄屮存在的問題和不足，提出了未來網(wǎng)架優(yōu)化規(guī) 劃研宄中應(yīng)關(guān)注的問題和研宄方向。電力網(wǎng)的網(wǎng)架結(jié)構(gòu)優(yōu)化設(shè)計(jì)是組合最優(yōu)化問題。筆薺用圖論方法把電力網(wǎng)

5、線 路模型化，并運(yùn)用圖論最優(yōu)化理論研究線路優(yōu)化設(shè)計(jì)問題。在電力網(wǎng)運(yùn)行在樹狀 結(jié)構(gòu)的前提下，提出了多邊形變換的新概念，首次將模擬退火方法應(yīng)用于電力網(wǎng) 線路優(yōu)化設(shè)計(jì)中，同時(shí)提出網(wǎng)架優(yōu)化的模擬退火算法，最終得到一個(gè)費(fèi)用最小的 電力網(wǎng)的網(wǎng)架結(jié)構(gòu)。關(guān)鍵詞：電力網(wǎng)，電網(wǎng)規(guī)劃，網(wǎng)架優(yōu)化，模擬退火法目錄第一章緒論1t* 11161 禾n at/、3第三章設(shè)計(jì)原理4§3.1 tsp問題介紹5§3.2 tsp問題介紹5第四章詳細(xì)設(shè)計(jì)步驟7§4.1算法流程7§4.2模擬退火算法實(shí)現(xiàn)步驟如下7第五章設(shè)計(jì)結(jié)果及分析9§5.1 matlab程序?qū)崿F(xiàn)及主函數(shù)9§5

6、.1.1計(jì)算距離矩陣9§5.1.2初始解9§5.1.3生成新解9§5.1.4 metropolis 準(zhǔn)則函數(shù)10§5.1.5畫路線軌跡圖11§5.1.6輸出路徑函數(shù)11§5.1.7可行解路線長度函數(shù)12§5.1.8模擬退火算法的主函數(shù)12主函數(shù)代碼如下：12§5.2仿真結(jié)果及分析14第六章體會(huì)17§6.1關(guān)于matlab的體會(huì)17§6.2關(guān)于基于模擬退火算法的tsp算法的體會(huì)17參考文獻(xiàn)19第一章緒論隨著電力系統(tǒng)的運(yùn)營管理逐步向企業(yè)化和市場化方向發(fā)展，如何在保證電力 安全可靠地輸送到電力負(fù)荷中心

7、的前提下，盡可能降低電網(wǎng)的建設(shè)投資和運(yùn)行成 木己成為電力企業(yè)關(guān)注的核心問題。電網(wǎng)規(guī)劃的任務(wù)就是遵照上述原則確定一段 時(shí)期內(nèi)（一般為5年）的分年度電網(wǎng)網(wǎng)架結(jié)構(gòu)、建設(shè)項(xiàng)目和投資費(fèi)用安排。其中， 一旦負(fù)荷發(fā)展水平確定，進(jìn)行各年度fi標(biāo)網(wǎng)架優(yōu)化就成為電網(wǎng)規(guī)劃的核心問題和 難點(diǎn)，它直接決定了一個(gè)電網(wǎng)的建設(shè)成本、運(yùn)行可靠性和經(jīng)濟(jì)性。網(wǎng)架優(yōu)化是一 個(gè)多0標(biāo)、多階段、包括大量不確定因素的離散、非線性受約束的混合整數(shù)規(guī)劃 問題。由于電網(wǎng)規(guī)劃方案需要配合一段時(shí)期內(nèi)的負(fù)荷漸進(jìn)發(fā)展來確定各年度電網(wǎng) 網(wǎng)架，既要求在規(guī)劃期內(nèi)所奮年度均滿足負(fù)荷和可靠性需求，又要使整個(gè)規(guī)劃期 的綜合動(dòng)態(tài)投資額最小、目標(biāo)網(wǎng)架最合理，因此現(xiàn)有的

8、網(wǎng)架結(jié)構(gòu)優(yōu)化規(guī)劃模型原 則上又可分為靜態(tài)（單階段）模型和動(dòng)態(tài)（多階段）電網(wǎng)規(guī)劃模型。其中，靜態(tài)電網(wǎng) 規(guī)劃只規(guī)劃某一負(fù)荷水平年的電網(wǎng)接線，不考慮方案的過渡問題;動(dòng)態(tài)電網(wǎng)規(guī)劃 則將規(guī)劃期劃分若干個(gè)水平年并考慮丫方案的過渡問題。從優(yōu)化求解算法上看，傳統(tǒng)的運(yùn)籌學(xué)方法，如線性規(guī)劃法、整數(shù)規(guī)劃法、混 合整數(shù)規(guī)劃法、動(dòng)態(tài)規(guī)劃法等雖原理嚴(yán)格;但在解決電網(wǎng)規(guī)劃問題時(shí)經(jīng)常遇到搜 索方向錯(cuò)誤、迭代發(fā)散等問題;當(dāng)變量和約束條件增多時(shí)，往往會(huì)陷入所謂的“組 合爆炸”;并且隨著電網(wǎng)規(guī)模的增大，這些方法（除少數(shù)線性規(guī)劃模型）很難在合理 的時(shí)間內(nèi)得到問題的優(yōu)化方案。以人工智能技術(shù)為基礎(chǔ)的各類優(yōu)化算法正逐步成 為網(wǎng)架優(yōu)化問題求

9、解的主流算法。而各類人工智能方法往往只提供了一種尋優(yōu)框 架，具體的尋優(yōu)策略還需要根據(jù)實(shí)際問題進(jìn)行分析和設(shè)計(jì)，整個(gè)理論體系仍在不 斷發(fā)展和完善之屮。另一方面，對(duì)電力網(wǎng)來說，不同電壓等級(jí)的電網(wǎng)在網(wǎng)架和優(yōu) 化的數(shù)學(xué)模型上又有著顯著的差別。對(duì)輸電網(wǎng)和高壓配電網(wǎng)來說，網(wǎng)架優(yōu)化的fi標(biāo)是在給定的高、低壓變電站之 間確定線路連接方式和回?cái)?shù)。由于變電站個(gè)數(shù)相對(duì)較少，位置明確而且人多數(shù)在 城市外圍，線路走廊和長度估計(jì)較易實(shí)現(xiàn)。而中低壓配電網(wǎng)不但負(fù)荷點(diǎn)眾多，而 且線路走廊直接受到城市建筑和街道布置的約束。合理的布線和線路長度的估測 成為配電網(wǎng)建設(shè)成本計(jì)算的重點(diǎn)和難點(diǎn)。如何考慮線路走向、分散負(fù)荷點(diǎn)歸屬、 輻射性約束

10、等問題使配電網(wǎng)優(yōu)化較輸電網(wǎng)更加復(fù)雜。本文綜述了近年來電網(wǎng)網(wǎng)架 優(yōu)化規(guī)劃領(lǐng)域的國內(nèi)外研究成果，分別針對(duì)對(duì)輸電網(wǎng)和中低壓配電網(wǎng)的網(wǎng)架優(yōu)化 問題，從優(yōu)化模型的構(gòu)造（包括h標(biāo)函數(shù)和約束條件的構(gòu)成）和優(yōu)化算法兩方面進(jìn) 行了分析和評(píng)述，指出了已取得的主要成果和存在的問題，并探討未來研宂方向。模擬退火算法是80年代初期發(fā)展起來的一種求解大規(guī)模組合優(yōu)化問題的隨 機(jī)性方法。它以優(yōu)化問題的求解與物理系統(tǒng)退火過程的相似性為基礎(chǔ)，利用 metropolis算法并適當(dāng)?shù)目刂茰囟鹊南陆颠^程實(shí)現(xiàn)模擬退火，從而達(dá)到求解全局 優(yōu)化問題的目的。它具有描述簡單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受 初始條件限制等優(yōu)點(diǎn)。模擬退火算

11、法在搜索策略上與傳統(tǒng)的隨機(jī)搜索方法不同， 它不僅引入了適當(dāng)?shù)碾S機(jī)因素，而且還引入了物理系統(tǒng)退火過程的自然機(jī)理。這 種自然機(jī)理的引入使模擬退火算法在迭代過程中不僅接受使目標(biāo)函數(shù)值變“好” 的試探點(diǎn)，而且還能夠以一定的概率接受使fi標(biāo)函數(shù)值變“差”的試探點(diǎn)，接受概 率隨著溫度的卜降逐漸減小。模擬退火算法的這種搜索策略有利于避免搜索過程 因陷入局部最優(yōu)解而無法自拔的弊端，奮利于提高求得全局最優(yōu)解的可靠性。本 文提出了一種求解上述模型的改進(jìn)模擬退火算法，數(shù)據(jù)結(jié)果表明該算法計(jì)算效率 高，穩(wěn)定性好。第二章設(shè)計(jì)目的和意義旅行商問題是組合優(yōu)化領(lǐng)域里的一個(gè)典型的、易于描述卻難以處理的np 難題，其可能的路徑數(shù)目

12、與城市數(shù)目是呈指數(shù)型增l的，求解非常困難。首先介 紹了旅行商問題，給出了其數(shù)學(xué)描述以及實(shí)際應(yīng)用，進(jìn)而給出解決tsp的一種比 較精確的算法一一模擬退火算法。然后闡述了模擬退火算法的基本原理，重點(diǎn)說 明了其基木思想及關(guān)鍵技術(shù)。最后運(yùn)用matlab語言實(shí)現(xiàn)了該算法，并將其運(yùn)用 到解決旅行商問題的優(yōu)化之中。數(shù)值仿真的結(jié)果表明了該方法能夠?qū)?shù)據(jù)進(jìn)行全 局尋優(yōu)，有效克服了基于導(dǎo)數(shù)的優(yōu)化算法容易陷入局部最優(yōu)的問題。了解模擬退火算法的tsp算法的基木思路及原理，并應(yīng)用matlab實(shí)現(xiàn)仿真, 熟練掌握matlab的操作方式及應(yīng)用，能正確書寫報(bào)告。第三章設(shè)計(jì)原理§3.1模擬退火算法的基本原理模擬退火算法

13、足20世紀(jì)80年代初提出的一種基于蒙特卡羅(mente carlo) 迭代求解策略的啟發(fā)式隨機(jī)優(yōu)化算法。它通過metropolis接受準(zhǔn)則概率接受劣化 解并以此跳出局部最優(yōu)，通過溫度更新函數(shù)的退溫過程進(jìn)行趨化式搜索并最終進(jìn) 入全局最優(yōu)解集。其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一搬的組合優(yōu)化 問題之間的相似性。模擬退火法是一種通用的優(yōu)化算法，其物理退火過程由以下 三部分組成。(1) 加溫過程。其目的是增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度 足夠高時(shí)，固體將熔為液體，從而消除系統(tǒng)原先存在的非均勻狀態(tài)。(2) 等溫過程。對(duì)于與周圍環(huán)境交換熱量而溫度不變的密封系統(tǒng)，系統(tǒng)狀 態(tài)的自發(fā)變化總是朝自

14、由能減少的方向進(jìn)行的，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到 平衡狀態(tài)。(3) 冷卻過程。使粒子熱運(yùn)動(dòng)減弱，系統(tǒng)能量下降，得到晶體結(jié)構(gòu)。其中，加熱過程對(duì)應(yīng)算法的設(shè)定初溫，等溫過程對(duì)應(yīng)算法的metropolis抽樣過程，冷卻過程對(duì)應(yīng)控制參數(shù)的下降。這里能量的變化就是目標(biāo)函數(shù)，要得 到的最優(yōu)解就是能量最低態(tài)。metropolis準(zhǔn)則是sa算法收斂于全局最優(yōu)解的關(guān) 鍵所在，metropolis準(zhǔn)則以一定的概率接受惡化解，這樣就使算法跳離局部最 優(yōu)的陷阱。模擬退火算法為求解傳統(tǒng)方法難處理的tsp問題提供了一個(gè)有效的途徑和 通用框架，并逐漸發(fā)展成一種迭代自適應(yīng)啟發(fā)式概率性搜索算法。模擬退火算法 可以用以求解不同的

15、非線性問題，對(duì)不可微甚至不連續(xù)的函數(shù)優(yōu)化，能以較大的 概率求的全局有化解，該算法還具有較強(qiáng)的魯棒性、全局收斂性、隱含并行性及 廣泛的適應(yīng)性，并且能處理不同類型的優(yōu)化設(shè)計(jì)變量(離散的、連續(xù)的和混合型 的)，不需要任何的輔助信息，對(duì)目標(biāo)函數(shù)和約朿函數(shù)沒有任何要求。利用 metropolis算法并適當(dāng)?shù)目刂茰囟认陆颠^程，在優(yōu)化問題中具有很強(qiáng)的競爭力， 此設(shè)計(jì)即為基于模擬退火算法的tsp算法。sa算法實(shí)現(xiàn)過程如下(以最小化問題為例)：(1)初始化：取初始溫度t。足夠大，令t=t。，任取初始解s,，確定每個(gè)t吋的迭代 次數(shù)，即metropolis鏈長lo（2）對(duì)當(dāng)前溫度t和k=l，2,，1,重復(fù)步驟（3

16、）（6）。（3）對(duì)當(dāng)前31隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解s2.（4）計(jì)算s2的增量df=f （s2） -f （sd其中f為s#j代價(jià)函數(shù)。（5）若df<0 ，則接受s2作為新的當(dāng)前解，即si=s2;否則計(jì)算么的接受概 率exp （-df/t）,即隨機(jī)產(chǎn)生（0，1）區(qū)間上均分布的隨機(jī)數(shù)rand,若exp（-df/t） >rand也接受s2作為新的當(dāng)前解，ss,；否則保留當(dāng)前解s，。（6）如果滿足終止條件stop,則輸出當(dāng)前解si為最優(yōu)解，結(jié)束程序。終止 條件stop通常為：在連續(xù)若干個(gè)metropolis鏈中新解s2都沒有被接受時(shí)終止 算法，或是設(shè)定結(jié)束溫度。否則按衰減函數(shù)衰減t后返回步驟（2

17、）。以上步驟成為metropolis過程。逐漸降低控制溫度，重復(fù)metropolis 過程，直至滿足結(jié)束準(zhǔn)則stop,求出最優(yōu)解。（§3.2 tsp問題介紹旅行商問題（traveling salesman problem,簡稱tsp）又名貨郎擔(dān)問題，是 威廉哈密爾頓爵士和英國數(shù)學(xué)家克克曼（t。p。kirkman）于19世紀(jì)初提出的一 個(gè)數(shù)學(xué)問題，也是著名的組合優(yōu)化問題。問題是這樣描述的：一名商人要到若干 城市去推銷商品，己知城市個(gè)數(shù)和各城市間的路程（或旅費(fèi)），要求找到一條從 城市1出發(fā)，經(jīng)過所有城市ii每個(gè)城市只能訪問一次，最后冋到城市1的路線， 使總的路程（或旅費(fèi)）最小。tsp剛提

18、出吋，不少人認(rèn)為這個(gè)問題很簡單。后來 人們才逐步意識(shí)到這個(gè)問題只是表述簡單，易于為人們所理解，而其計(jì)算復(fù)雜性 卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當(dāng)難解的問題。這個(gè)問題數(shù)學(xué)描述為： 假設(shè)有n個(gè)城市，并分別編號(hào)，給定一個(gè)完全無向圖g=（v, e）, v=1, 2, n, n>k其每一邊（i，j）ee有一非負(fù)整數(shù)耗費(fèi)cid（即上的權(quán)記為cid, i, jev）。 g的一條巡冋路線是經(jīng)過v中的每個(gè)頂點(diǎn)恰好一次的冋路。一條巡冋路線的耗 費(fèi)是這條路線上所冇邊的權(quán)值之和。tsp問題就是要找出g的最小耗費(fèi)冋路。人們在考慮解決這個(gè)問題吋，一般首先想到的最原始的一種方法就是:列出 每一條可供選擇的路線（即

19、對(duì)給定的城市進(jìn)行排列組合），計(jì)算出每條路線的總里 程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個(gè)城市分別為a、b、c 和d,各城市之間的耗費(fèi)為己知數(shù)，如圖1所示。我們可以通過一個(gè)組合的狀態(tài) 空間圖來表示所冇的組合，如圖圖2 tsp問題的解空間樹從圖中不難看出，可供選擇的路線共有6條，從中很快可以選出一條總耗費(fèi)最短 的路線：頂點(diǎn)序列為（a，c，b，d，a）。由此推算，若設(shè)城市數(shù)目為n時(shí)，那么組合 路徑數(shù)則為（n-1）!。很顯然，當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不難， 但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級(jí)數(shù)規(guī)律急劇增長，以至達(dá)到 無法計(jì)算的地步，這就是所謂的“組合爆炸問題”。假

20、設(shè)現(xiàn)在城市的數(shù)目增為20 個(gè)，組合路徑數(shù)則為（20-1爐1。216xl017,如此龐大的組合數(shù)目，若計(jì)算機(jī)以每 秒檢索1000萬條路線的速度計(jì)算，也需要花上386年的時(shí)間16。第四章詳細(xì)設(shè)計(jì)步驟§4.1算法流程模擬退火算法求解流程框圖如圖1所示。圖3模擬退火算法求解流程框圖§4.2模擬退火算法實(shí)現(xiàn)步驟如下(1) 控制參數(shù)的設(shè)置需要設(shè)置的主要控制參數(shù)有降溫速率q、初始溫度to、結(jié)束溫度tend以及 鏈長l。(2) 初始解對(duì)于n個(gè)城市tsp問題，得到的解就是對(duì)1n的一個(gè)排序，其中每個(gè)數(shù) 字為對(duì)應(yīng)城市的編號(hào)，如對(duì)10個(gè)城市的tsp問題1，2,3,4,5,6,7,8,9，10，貝i

21、j |1|10|2|4|5|6|8|7|9|3就是一個(gè)合法的解，采用產(chǎn)生隨機(jī)排列的方法產(chǎn)生一個(gè)初始解 so(3) 解變換生成新解通過對(duì)當(dāng)前解si進(jìn)行變換，產(chǎn)生新的路徑數(shù)組即新解，這里采用的變換 是產(chǎn)生隨機(jī)數(shù)的方法來產(chǎn)生將要交換的兩個(gè)城市，用二鄰域變換法產(chǎn)生新的路 徑，即新的可行解s2。例如n=io時(shí)，產(chǎn)生兩個(gè)范圍內(nèi)的隨機(jī)整數(shù)rjnr2,確定兩個(gè)位置， 將其對(duì)換位置，如0=4, r2=7951638710 42得到的新解為951738610 42(4) metropolis 準(zhǔn)則若路徑長度函數(shù)為,(s),新解的路徑為(s2)，路徑差為= / (s2) (si)，則 metropolis 準(zhǔn)則為1

22、，辦<0p= dfl exp(-),#>0t如果df<0,則以概率1接受新路線，否則以概率exp(-df/t)接受新路線。(5) 降溫利用降溫速率q進(jìn)行降溫，即t=qt，若t小于結(jié)束溫度，則停止迭代輸 出當(dāng)前狀態(tài)，否則繼續(xù)迭代。第五章設(shè)計(jì)結(jié)果及分析§5.1 matlab程序?qū)崿F(xiàn)及主函數(shù)§5.1.1計(jì)算距離矩陣?yán)媒o出的n個(gè)城市的坐標(biāo)，算出n個(gè)城市的兩兩之間的距離，得到距離矩 陣(nxn)o計(jì)算函數(shù)為distance,得到初始群種。程序如下function d=distanse（a）%計(jì)算兩兩城市之間的距離 %輸入a各城市的位置坐標(biāo) %輸出d兩兩城市之間的距

23、離 row=size（a，l）;d=zeros（row，row）; for i=l:rovvfor j=i+l:rowd（i，j）=（a（i，1 ）-a（j，1 ）a2+（a（i，2）-ag，2）r2）a0。5; d（j，i）=d（i，j）; endend§5.1.2初始解初始解的產(chǎn)生直接使用matlab自帶的函數(shù)randperm,如城市格式為n 個(gè)，則產(chǎn)生初始解：sl=randperm (n)；%隨機(jī)產(chǎn)生一個(gè)初始路線§5.1.3生成新解解變換牛.成新解函數(shù)為newanswer,程序代碼如下:function s2=newanswer(s 1)%輸入 %sk當(dāng)前解 %輸出

24、% s2：新解 n=length(sl);s2=s1;a=round(rand(l，2)*(n-l)+l); %產(chǎn)生兩個(gè)隨機(jī)位置用來交換 w=s2(a(l);s2(a(l)=s2(a(2);s2(a(2)=w;%得到一個(gè)新路線§5.1.4 metropolis 準(zhǔn)則函數(shù)metropolis準(zhǔn)則函數(shù)為metropolis,程序代碼如下:function s，r=metropolis(sl，s2，d，t)%輸入 % s1： 當(dāng)前解 % s2: 新解%d:距離矩陣(兩兩城市的之間的距離)%t:當(dāng)前溫度%輸出%s：下一個(gè)當(dāng)前解%r：下一個(gè)當(dāng)前解的路線距離%rl=pathlength(d,sl

25、); % 計(jì)算路線長度 n=lcngth(sl);%得到城市的個(gè)數(shù)r2=pathlength(d,s2); %計(jì)算路線長度 dc=r2-rl;%計(jì)算能力之差ifdc<0%如果能力降低接受新路線s=s2;r=r2;elseif exp(-dc/t)>=rand%以 exp(-dc/t)概率接受新路線s=s2;r=r2;else%不接受新路線s=s1;r=r1;end§5.1.5畫路線軌跡圖畫出給的路線的軌跡圖函數(shù)為drawpath,程序代碼如下:function drawpath(chrom,x)%畫路徑函數(shù) %輸入% chrom待畫路徑%x各城市坐標(biāo)位罝r=chrom(l

26、,:) chrom(l,l); %-個(gè)隨機(jī)解(個(gè)體)figure;hold onplot(x(:，l)，x(:，2)/o，color，0。5,0。5,0。5) plot(x(chrom( 1，1 )，1 )，x(chrom( 1，1 ),2)；rv',markersize,20) for i=l:size(x，l)text(x(i，l)+0。05，x(i，2)+0。05，num2str(i)，color，l，0,0); enda=x(r,:); row=size(a, 1); for i=2:rowarrowx,arrowy = dsxy2figxy(gca,a(i- l:i,l ),

27、a(i-l:i, 2);% 坐標(biāo)轉(zhuǎn)換 annotation(textarrow，arrowx，arrowy，'headwidth，8，'color'，0,0,l); endhold off xlabelf橫坐標(biāo)) ylabelc縱坐標(biāo)) titlef軌跡圖) box on§5.1.6輸出路徑函數(shù)將得到的路徑輸出顯示在command window中，函數(shù)名為outputpathofunction p=outputpath(r)%輸出路徑函數(shù) %輸入：r路徑 r=r，r;n=lcngth(r); p=num2str(r( 1); for i=2:np=p，一，nu

28、m2str(r(i); enddisp(p)§5.1.7可行解路線長度函數(shù)計(jì)算可行解的路線長度函數(shù)為pathlength ,程序代碼如卜*:function len=pathlength(d，chrom) %計(jì)算各個(gè)體的路徑長度 %輸入：%d 兩兩城市之間的距離 % chrom個(gè)體的軌跡 row,col=size(d); nind=size(chrom, 1); len=zeros(nind, 1); for i=l:nindp=chrom(i,:) chrom(i,l );il=p(l:end-l);i2=p(2:end);len(i, 1 )=sum(d(i 1 -1 )*col

29、+i2); end§5.1.8模擬退火算法的主函數(shù)模擬退火算法參數(shù)設(shè)置如表一所列。表一參數(shù)設(shè)定降溫速率q初始溫度to結(jié)束溫度tcnd鏈長loo 910000。001200主函數(shù)代碼如下:clc;clear;close all;%tict0=1000;%初始溫度tend=le-3; %終止溫度l=500;%各溫度下的迭代次數(shù)（鏈長）q=0。9; %降溫速率%加載數(shù)據(jù)load citypositionl;temp=zeros(l,n+1); for k=l:l%產(chǎn)生新解 s2=newanswer(s 1);% metropolis法則判斷是否接受新解 si，r=metropolis(s

30、1，s2，d，t0); metropolis 抽樣算法 temp(k,:)=sl r;%記錄下一路線的及其路程end%記錄每次迭代過程的最優(yōu)路線 do,indcx=min(tcmp(:,end); %找出當(dāng)前溫度下最優(yōu)路線 ifcount=l | do<obj(count-l)obj(count)=do;%如果當(dāng)前溫度下最優(yōu)路程小于上一路程則記錄當(dāng)前路程elseobj(count)=obj(count-l);%如果當(dāng)前溫度下最優(yōu)路程大丁上一路程則記錄上一路程 endtrack(count,:)=temp(index, 1: end-1); %記錄當(dāng)前溫度的最優(yōu)路線 t0=q*t0;% 降

31、溫fprintf( 1 ；%dncount) %輸出當(dāng)前迭代次數(shù) end%優(yōu)化過程迭代圖 figureplot( 1:count,obj) xlabelc迭代次數(shù)) ylabelc 距離') titlec優(yōu)化過程)%最優(yōu)解的路徑圖 drawpath(track(end,:),x)%輸出最優(yōu)解的路線和總距離 disp(最優(yōu)解:')s=track(end,:);p=outputpath(s);disp(總距離：',num2str(pathlength(d,s);disp(')toe§5.2仿真結(jié)果及分析優(yōu)化前的一個(gè)隨機(jī)路線圖如圖4所示:芘恤。lt回區(qū)ffi

32、le edit vie* insert tools desktop window help軌跡圖9216 18 20 22 橫坐標(biāo)24269998976 5 9 9949314圖4總路線距離約為57。00優(yōu)化以后的最優(yōu)解路線如下圖5:figure 3回si file edit view insert tools desktop window helpibiq dl h |: o ® zs | 92軌跡圖16 18 20 22 橫坐標(biāo)24269998979695949314圖5該優(yōu)化路徑的總路程近似為30。00，已為最優(yōu)解。模擬退火算法進(jìn)化過程圖如下圖6:回®file edi

33、t vieiw insert tools desktop window help1 an ®x s 口figure 2由閣可以看出，優(yōu)化前后路徑長度得到很大改進(jìn)，變?yōu)樵瓉淼?2。4%, 65代以 后路徑長度己經(jīng)保持不變了，可以認(rèn)為己經(jīng)是最優(yōu)解了。上閣為用模擬退火算法解決tsp的gui （graphics user interface,閣形用戶界 面）。這是由14個(gè)城市構(gòu)成的一個(gè)對(duì)稱tsp實(shí)例，利用上述算法對(duì)該實(shí)例進(jìn)行 模擬退火求解，設(shè)定初始溫度tn=1000,冷卻速率為0。9,經(jīng)過仿真得到的最優(yōu) 解與己知最優(yōu)解非常接近，所需時(shí)間也令人滿意。第六章體會(huì)使用matiab對(duì)求解tsp問題的

34、模擬退火算法程序進(jìn)行了仿真。平均結(jié)果 表明，首先該算法能夠找到tsp問題的最優(yōu)解，說明算法的正確性。其次算法 對(duì)tsp問題的求解時(shí)間并不呈指數(shù)增長，說明了算法的有效性。§6.1關(guān)于matlab的體會(huì)matlab是當(dāng)今科學(xué)界最具影響力、也是最具活力的軟件，它起源于矩 陣運(yùn)算，并已經(jīng)發(fā)展成一種高度集成的計(jì)算機(jī)語言。然后，了解到了 matlab 軟件的功能。它提供了強(qiáng)大的科學(xué)運(yùn)算、靈活的程序設(shè)計(jì)流程、高質(zhì)量的圖形可 視化與界面設(shè)計(jì)、便捷的與其他程序和語言接口的功能。我們應(yīng)該熟練掌握其使 用方法。§6.2關(guān)于基于模擬退火算法的tsp算法的體會(huì)模擬退火算法是依據(jù)metropolis準(zhǔn)則接受新解，該準(zhǔn)則除了接受優(yōu)化解外, 還在一定的限定范圍內(nèi)接受劣解，這正是模擬退火算法與局部搜索法的本質(zhì)區(qū) 別，在避