亚洲免费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)化電容器配置研究
        成全视频高清免费| 国产高清成人在线观看视频| 国产精品无码一区二区三区| 国产精品久久久久电影网| 天堂在线观看av一区二区三区| 国产免费一区二区三区在线观看| 色综合久久中文字幕综合网| 亚洲色无码国产精品网站可下载 | 欧美人成人亚洲专区中文字幕| 亚洲乱色视频在线观看| 与最丰满美女老师爱爱视频| 99久久精品免费观看国产| 亚洲国产中文在线二区三区免| 一区二区三区在线视频免费观看| 婚外情长久的相处之道| 亚洲av永久无码精品三区在线| 一本一本久久a久久精品| 日韩精品成人一区二区三区久久久| 自拍偷自拍亚洲一区二区| 高潮又爽又无遮挡又免费| 国产女人精品视频国产灰线| 久久夜色精品国产三级| 亚洲图片自拍偷图区| 狠狠色综合网站久久久久久久| www.五月激情| 青青草视频在线观看入口| 国产精品成人va在线观看| 国产精选免在线观看| 精品蜜桃在线观看一区二区三区| 成人免费播放视频777777| 一本大道无码av天堂| 2021最新久久久视精品爱| 亚洲av人片在线观看| 成人午夜性a级毛片免费| 国产一级免费黄片无码AV| 日韩一区二区中文字幕| 精品+无码+在线观看| 精品无码国产污污污免费网站| 亚洲av影片一区二区三区| 久久精品一区午夜视频| 人妻少妇精品视频一区二区三区|