亚洲免费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)化電容器配置研究
        久草中文在线这里只有精品 | 96精品在线| 国产区高清在线一区二区三区| 中文字幕亚洲一二三区| 四虎成人精品国产永久免费无码| 久久久久亚洲av无码专区导航| 中文岛国精品亚洲一区| 国产精品久久国产精麻豆| 国产在线无码精品无码| 亚洲日本在线电影| 亚洲人成人99网站| 亚洲码专区亚洲码专区| 内射干少妇亚洲69xxx| 男人边吃奶边做好爽免费视频 | 国产激情视频在线观看大全| 国模雨珍浓密毛大尺度150p| 偷窥村妇洗澡毛毛多| 男女性搞视频网站免费| 在线观看免费日韩精品| 日本丰满熟妇hd| 在线观看亚洲精品国产| 91精品亚洲熟妇少妇| 日日拍夜夜嗷嗷叫国产| 丰满多毛少妇做爰视频| 久久久亚洲日本精品一区| 懂色av一区二区三区尤物| 国产人妻人伦精品1国产盗摄| 日韩欧美国产亚洲中文| 国产精品女同一区二区免| 免费无码精品黄av电影| 免费大片黄在线观看| 国产性感丝袜美女av| 五月开心婷婷六月综合| 亚洲国产激情一区二区三区| 免费va国产高清不卡大片| 北条麻妃在线中文字幕| 中文www新版资源在线| 久久精品亚洲中文无东京热| 一区二区精品天堂亚洲av| 黄桃av无码免费一区二区三区| 国产精品亚洲五月天高清|