亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        用模擬退火算法求解TSP

        2011-10-28 00:58:16朱靜麗
        湖北開放大學(xué)學(xué)報 2011年9期
        關(guān)鍵詞:控制參數(shù)模擬退火函數(shù)

        朱靜麗

        (英德廣播電視大學(xué),廣東 英德 513000)

        用模擬退火算法求解TSP

        朱靜麗

        (英德廣播電視大學(xué),廣東 英德 513000)

        貨郎擔(dān)問題,即TSP(Travelling Salesman Problem),是一個組合優(yōu)化問題。具有NPC計算復(fù)雜性。本文分析了模擬退火算法模型,研究了用模擬退火算法求解TSP算法的可行性,并給出了用模擬退火算法求解TSP問題的具體實現(xiàn)方法。

        模擬退火原理;算法;TSP

        一、貨郎擔(dān)問題

        貨郎擔(dān)問題,即TSP(Travelling Salesman Problem),也叫旅行商問題,是數(shù)學(xué)領(lǐng)域中著名問題之一。其一般提法為:假設(shè)有一個旅行商人要拜訪n個城市,他必須選擇所要走的路徑,路經(jīng)的限制是每個城市只能拜訪一次,而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。如圖1所示,顯然左邊的路程要小于右邊的路程。

        圖1 TSP的示意圖

        貨郎擔(dān)問題(TSP問題)是一個組合優(yōu)化問題。具有NPC計算復(fù)雜性。因此,任何能使該問題的求解得以簡化的方法,都將受到高度的評價和關(guān)注。一個最容易想到的方法是利用排列組合的方法把所有的路徑都計算出來,并逐一比較,選出最小的路徑。雖然該方法在理論上是可行的,但路徑的個數(shù)與城市的個數(shù)成指數(shù)增長,當(dāng)城市個數(shù)較大時,該方法的求解時間是難以忍受的,甚至是不可能完成的。以每秒1億次的計算速度來估算,如果TSP問題包含20個城市時,求解時間長達(dá)350年;如果要處理30個城市,則求解時間更長達(dá)1+10e16年。如此長的時間,在實際中完成是不現(xiàn)實的。基于模擬退火算法在處理全局優(yōu)化、離散變量優(yōu)化等困難問題中,具有傳統(tǒng)優(yōu)化算法無可比擬的優(yōu)勢。嘗試用模擬退火算法求解。

        二、模擬退火算法

        (一)模擬退火算法原理

        模擬退火算法原理來源于固體退火:將固體加溫至充分高,再讓其徐徐冷卻,加溫時,固體內(nèi)部粒子隨溫升變?yōu)闊o序狀,內(nèi)能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達(dá)到平衡態(tài),最后在常溫時達(dá)到基態(tài),內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則,粒子在溫度T時趨于平衡的概率為e-ΔE/(kT),其中E為溫度T時的內(nèi)能,ΔE為其改變量,k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題,將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法:由初始解i和控制參數(shù)初值t開始,對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代,并逐步衰減t值,算法終止時的當(dāng)前解即為所得近似最優(yōu)解,這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制,包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。

        (二)模擬退火算法的模型

        模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。

        模擬退火的基本思想:

        1.初始化:初始溫度T(充分大),初始解狀態(tài)S(是算法迭代的起點),每個T值的迭代次數(shù)L

        2.對k=1,……,L做第(3)至第6步:

        3.產(chǎn)生新解S′

        4.計算增量Δt′=C(S′)-C(S),其中 C(S)為評價函數(shù)

        5.若Δt′〈0則接受S′作為新的當(dāng)前解,否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解.

        6.如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解,結(jié)束程序。

        終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。

        7.T逐漸減少,且T-〉0,然后轉(zhuǎn)第2步。

        三、模擬退火算法求解TSP

        求解TSP的模擬退火算法模型描述如下:

        解空間:解空間 S是遍訪每個城市恰好一次的所有路經(jīng),解可以表示為{w1,w2 ,…, wn},w1, …, wn是1,2,…,n的一個排列,表明w1城市出發(fā),依次經(jīng)過w2, …, wn城市,再返回w1城市。初始解可選為(1,…, n) ;

        目標(biāo)函數(shù):目標(biāo)函數(shù)為訪問所有城市的路徑總長度;要求的最優(yōu)路徑為目標(biāo)函數(shù)為最小值時對應(yīng)的路徑。新路徑的產(chǎn)生:隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m,不妨假設(shè)k〈m,則將原路徑

        (w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn)

        變?yōu)樾侣窂剑?/p>

        (w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述變換方法就是將k和m對應(yīng)的兩個城市在路徑序列中交換位置,稱為2-opt映射。

        四、代碼實現(xiàn)

        UINT SACompution(LPVOID pParam)

        以上程序在Windows XP Professional、Visual C++ 6.0、STLport 4.6.2環(huán)境下調(diào)試完成。模擬退火算法一種新的隨機(jī)搜索方法,經(jīng)實驗研究,能有效解決組合優(yōu)化問題,與以往的近似算法相比,模擬退火算法具有使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受到初始條件約束等優(yōu)點。

        [1] 劉曉禹,張洪強(qiáng). 基于模擬退火算法的城市公交線路鋪設(shè)分析[J]. 交通科技與經(jīng)濟(jì),2010,5.

        [2] 朱振方,劉培玉,張洪軍,王美方. 基于退火遺傳算法的網(wǎng)絡(luò)信息過濾系統(tǒng)研究[J]. 計算機(jī)工程與設(shè)計,2009,2.

        [3] 徐俊杰. 利用微正則退火算法求解車輛路徑問題[J]. 安慶師范學(xué)院學(xué)報(自然科學(xué)版),2009,2 .

        Simulated annealing algorithm for TSP

        ZHU Jing-li

        Traveling salesman problem, that TSP (Travelling Salesman Problem), is a combinatorial optimization problem. Computational complexity with the NPC. This paper analyzes the simulated annealing algorithm model to study the simulated annealing algorithm for TSP of the algorithm, and gives the simulated annealing algorithm for TSP on the specific implementation.

        Simulated annealing principles; algorithms; TSP

        TP3

        A

        1008-7427(2011)09-0159-02

        2011-07-20

        猜你喜歡
        控制參數(shù)模擬退火函數(shù)
        高超聲速飛行器滑??刂茀?shù)整定方法設(shè)計*
        飛控與探測(2022年6期)2022-03-20 02:16:14
        二次函數(shù)
        第3講 “函數(shù)”復(fù)習(xí)精講
        二次函數(shù)
        函數(shù)備考精講
        Birkhoff系統(tǒng)穩(wěn)定性的動力學(xué)控制1)
        模擬退火遺傳算法在機(jī)械臂路徑規(guī)劃中的應(yīng)用
        基于PI與準(zhǔn)PR調(diào)節(jié)的并網(wǎng)逆變器控制參數(shù)設(shè)計
        黑龍江電力(2017年1期)2017-05-17 04:25:08
        基于模糊自適應(yīng)模擬退火遺傳算法的配電網(wǎng)故障定位
        SOA結(jié)合模擬退火算法優(yōu)化電容器配置研究
        摸丰满大乳奶水www免费| 4444亚洲人成无码网在线观看 | 色偷偷亚洲第一成人综合网址 | 免费又黄又爽又猛的毛片| 第十色丰满无码| 中文字幕文字幕视频在线 | 无码国产精品一区二区免费式芒果| 四虎影视在线影院在线观看| 久久精品一区二区免费播放| 国产一区二区三区免费精品| 国产精品女主播在线播放| 亚洲成av人片在线观看| 蜜臀av无码人妻精品| 亚洲国产精品福利片在线观看 | 东京热加勒比无码少妇| 亚洲AV色无码乱码在线观看| 亚洲成a∨人片在线观看无码| 日韩字幕无线乱码免费| 国产91成人精品高潮综合久久 | 久久一本日韩精品中文字幕屁孩| 无码人妻丰满熟妇区bbbbxxxx| 大伊香蕉在线精品视频75| 午夜无码亚| 人妖国产视频一区二区| 国产网红主播无码精品| 91伊人久久| 丝袜美腿亚洲综合久久| 男人吃奶摸下挵进去啪啪软件| 97久久香蕉国产线看观看| 国产美女精品aⅴ在线| 国产目拍亚洲精品二区| 香蕉视频在线观看亚洲| 丰满熟女人妻中文字幕免费| 国产精品乱子伦一区二区三区| 亚洲黑寡妇黄色一级片| 人妻夜夜爽天天爽三区丁香花 | 好大好深好猛好爽视频免费| 国产av无码专区亚洲草草| 亚洲国产精品国自拍av| 日本午夜精品理论片a级app发布| 成黄色片视频日本秘书丝袜|