模擬退火算法（TSP問題）

模擬退火算法解決TSP問題

算法思想

模擬退火算法（Simulate Anneal，SA）是一種通用概率演算法，用來在一個大的搜尋空間內找尋命題的最優解

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

設計思路

  1. 初始化溫度T，初始解狀態S，每個溫度t下的迭代次數L；

  2. 當k = 1，2，……，L時，進行3~6；

  3. 對當前解進行變換得到新解S’（例如對某些解中的元素進行互換，置換）；

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

  5. 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/(KT))接受S′作為新的當前解(k為玻爾茲曼常數，數值為：K=1.3806505(24) × 10^-23 J/K）；

  6. 如果滿足終止條件則輸出當前解作為最優解，結束程序；

  7. 減小T，轉到第2步，直到T小于初始設定的閾值。

程序代碼（TSP問題）

第一種

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include<time.h>
#include<math.h>
#define N 109
#define big 9999999
using namespace std;double nowDist(double d[N][N],int temp[N],int m){//計算當前temp路線組合距離double dist=0;for(int i=1;i<m;i++)dist+=d[temp[i]][temp[i+1]];dist+=d[temp[m]][temp[1]];return dist;
}int main(){double d[N][N];//距離矩陣int temp[N];//臨時地點排列順序表double dist=0;//最小距離int n,m;//n為輸入行數,m為地點個數int res[N];double mostdist=big;//數據輸入freopen("input.txt","r",stdin);cin>>m>>n;while(n-->0){int i,j;double k;cin>>i>>j>>k;d[i][j]=d[j][i]=k;}for(int i=1;i<=m;i++){d[i][i]=big;temp[i]=i;if(i!=m) dist+=d[i][i+1];}dist+=d[m][1];cout<<"初始距離: "<<dist<<endl;int count=40;while(count--){//取count次迭代的最小結果double T=1;//初始溫度double a=0.999;//退火率double low=1e-30;//最低溫度long ct=0;//迭代步數long ctj=0;//有效迭代步數srand(time(0));//隨機數種子long all=300000;//最大迭代次數while(T>low){int t1=rand()%m+1,t2=rand()%m+1;//隨機獲得兩個位置if(t1!=t2){swap(temp[t1],temp[t2]);//交換兩位置double ndist=nowDist(d,temp,m);//交換后的路線總距離double df=(ndist-dist);if(df<0){//當前解更優dist=ndist;ctj++;}else if(exp(-df/T)>(rand()%100)/100.0){//大于dist=ndist;ctj++;}else{swap(temp[t1],temp[t2]);}T*=a;//降溫}ct++;if(ct>all)break;}cout<<"當前最短距離:"<<dist<<endl;if(dist<mostdist){mostdist=dist;for(int i=1;i<=m;i++)res[i]=temp[i];}}cout<<"最短距離:"<<mostdist<<endl<<"路線:";for(int i=1;i<=m;i++){cout<<res[i]<<" ";}return 0;
}

第二種

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include<time.h>
#include<math.h>#include<fstream>
#include<algorithm>
#include<memory.h>
using namespace std;const int num = 1000;//city number
const int width = 100;
const int height = 100;typedef struct node {int x;int y;
}city;
city citys[num];//citys
double dic[num][num];//distance from two citys;
bool visit[num];//visited
int N;//real citys
int seq[num];//最優路徑序列
double answer;//最優路徑長度
const int tempterature = 1000;//初始溫度
const double u = 0.998;//成功降溫因子
const double v = 0.999;//失敗降溫因子
int k = 100;//對每個溫度迭代次數
void init() {//set N&&x-yN = 51;citys[0].x = 37; citys[0].y = 52;citys[1].x = 49; citys[1].y = 49;citys[2].x = 52; citys[2].y = 64;citys[3].x = 20; citys[3].y = 26;citys[4].x = 40; citys[4].y = 30;citys[5].x = 21; citys[5].y = 47;citys[6].x = 17; citys[6].y = 63;citys[7].x = 31; citys[7].y = 62;citys[8].x = 52; citys[8].y = 33;citys[9].x = 51; citys[9].y = 21;citys[10].x = 42; citys[10].y = 41;citys[11].x = 31; citys[11].y = 32;citys[12].x = 5; citys[12].y = 25;citys[13].x = 12; citys[13].y = 42;citys[14].x = 36; citys[14].y = 16;citys[15].x = 52; citys[15].y = 41;citys[16].x = 27; citys[16].y = 23;citys[17].x = 17; citys[17].y = 33;citys[18].x = 13; citys[18].y = 13;citys[19].x = 57; citys[19].y = 58;citys[20].x = 62; citys[20].y = 42;citys[21].x = 42; citys[21].y = 57;citys[22].x = 16; citys[22].y = 57;citys[23].x = 8; citys[23].y = 52;citys[24].x = 7; citys[24].y = 38;citys[25].x = 27; citys[25].y = 68;citys[26].x = 30; citys[26].y = 48;citys[27].x = 43; citys[27].y = 67;citys[28].x = 58; citys[28].y = 48;citys[29].x = 58; citys[29].y = 27;citys[30].x = 37; citys[30].y = 69;citys[31].x = 38; citys[31].y = 46;citys[32].x = 46; citys[32].y = 10;citys[33].x = 61; citys[33].y = 33;citys[34].x = 62; citys[34].y = 63;citys[35].x = 63; citys[35].y = 69;citys[36].x = 32; citys[36].y = 22;citys[37].x = 45; citys[37].y = 35;citys[38].x = 59; citys[38].y = 15;citys[39].x = 5; citys[39].y = 6;citys[40].x = 10; citys[40].y = 17;citys[41].x = 21; citys[41].y = 10;citys[42].x = 5; citys[42].y = 64;citys[43].x = 30; citys[43].y = 15;citys[44].x = 39; citys[44].y = 10;citys[45].x = 32; citys[45].y = 39;citys[46].x = 25; citys[46].y = 32;citys[47].x = 25; citys[47].y = 55;citys[48].x = 48; citys[48].y = 28;citys[49].x = 56; citys[49].y = 37;citys[50].x = 30; citys[50].y = 40;
}
void set_dic() {//set distancefor (int i = 0; i<N; ++i) {for (int j = 0; j<N; ++j) {dic[i][j] = sqrt(pow(citys[i].x - citys[j].x, 2) + pow(citys[i].y - citys[j].y, 2));}}
}
double dic_two_point(city a, city b) {return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double count_energy(int* conf) {double temp = 0;for (int i = 1; i<N; ++i) {temp += dic_two_point(citys[conf[i]], citys[conf[i - 1]]);}temp += dic_two_point(citys[conf[0]], citys[conf[N - 1]]);return temp;
}
bool metro(double f1, double f2, double t) {if (f2 < f1)return true;//else//  return false;double p = exp(-(f2 - f1) / t);int bignum = 1e9;if (rand() % bignum<p*bignum)return true;return false;
}
void generate(int* s) {//隨機產生一組新解bool v[num];memset(v, false, sizeof(v));for (int i = 0; i<N; ++i) {s[i] = rand() % N;while (v[s[i]]) {s[i] = rand() % N;}v[s[i]] = true;}
}
void generate1(int* s) {//隨機交換序列中的一組城市順序int ti = rand() % N;int tj = ti;while (ti == tj)tj = rand() % N;for (int i = 0; i<N; ++i)s[i] = seq[i];swap(s[ti], s[tj]);
}
void generate2(int* s) {//隨機交換序列中的兩組城市順序int ti = rand() % N;int tj = ti;int tk = ti;while (ti == tj)tj = rand() % N;while (ti == tj || tj == tk || ti == tk)tk = rand() % N;for (int i = 0; i<N; ++i)s[i] = seq[i];swap(s[ti], s[tj]);swap(s[tk], s[tj]);
}
void generate3(int* s) {//隨機選序列中的三個城市互相交換順序int ti = rand() % N;int tj = ti;int tm = rand() % N;int tn = ti;while (ti == tj)tj = rand() % N;while (tm == tn)tn = rand() % N;for (int i = 0; i<N; ++i)s[i] = seq[i];swap(s[ti], s[tj]);swap(s[tm], s[tn]);
}
void generate0(int* s) {//以上三種交換方式等概率選擇int temp = rand() % 3;if (temp == 0)generate1(s);else if (temp == 1)generate2(s);else if (temp == 2)generate3(s);
}
void moni() {double t = tempterature;int seq_t[num];for (int i = 0; i<N; ++i) {//初始化當前序列seq[i] = seq_t[i] = i;}double new_energy = 1, old_energy = 0;while (t>1e-9&&fabs(new_energy - old_energy)>1e-9) {//溫度作為控制變量int t_k = k;int seq_tt[num];while (t_k--&&fabs(new_energy - old_energy)>1e-9) {//迭代次數作為控制變量generate1(seq_tt);new_energy = count_energy(seq_tt);//newold_energy = count_energy(seq_t);//oldif (metro(old_energy, new_energy, t))for (int i = 0; i < N; ++i)seq_t[i] = seq_tt[i];}new_energy = count_energy(seq_t);//newold_energy = answer;//oldif (metro(old_energy, new_energy, t)) {for (int i = 0; i < N; ++i)seq[i] = seq_t[i];answer = count_energy(seq);t *= u;//接受新狀態降溫因子0.98}elset *= v;//不接受新狀態降溫因子0.99}answer = count_energy(seq);
}
void output() {cout << "the best road is : \n";for (int i = 0; i < N; ++i) {cout << seq[i];if (i == N - 1)cout << endl;elsecout << " -> ";}cout << "the length of the road is " << answer << endl;
}
void test() {ifstream ifile("data.txt");if (!ifile) {cout << "open field\n";return;}while (!ifile.eof()) {int te = 0;ifile >> te;ifile >> citys[te - 1].x >> citys[te - 1].y;}
}
int main() {srand(time(0));int t;while (cin >> t) {//僅作為重啟算法開關使用，無意義init();//使用程序內置數據使用init()函數，//test();//使用文件讀取數據使用test()函數，set_dic();//計算每個城市之間的距離moni();//退火output();//輸出}return 0;
}

測試例
第一種，通過以下代碼生成數據集文件

import random as rd
n=eval(input('城市數量:'))
res=[]
for i in range(1,n):for j in range(i+1,n+1):res.append((i,j,rd.random()*100))
f=open('input.txt','w')
f.write(str(n)+' '+str(len(res))+'\n')
for i in res:f.write(str(i[0])+" "+str(i[1])+" "+str(i[2])+"\n")
f.close()
input('結束')

第二種

1 37 52
2 49 49
3 52 64
4 20 26
5 40 30
6 21 47
7 17 63
8 31 62
9 52 33
10 51 21
11 42 41
12 31 32
13 5 25
14 12 42
15 36 16
16 52 41
17 27 23
18 17 33
19 13 13
20 57 58
21 62 42
22 42 57
23 16 57
24 8 52
25 7 38
26 27 68
27 30 48
28 43 67
29 58 48
30 58 27
31 37 69
32 38 46
33 46 10
34 61 33
35 62 63
36 63 69
37 32 22
38 45 35
39 59 15
40 5 6
41 10 17
42 21 10
43 5 64
44 30 15
45 39 10
46 32 39
47 25 32
48 25 55
49 48 28
50 56 37
51 30 40

運行結果
第一種

初始距離: 587.205
當前最短距離:264.036
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:213.825
當前最短距離:232.311
當前最短距離:278.578
當前最短距離:232.311
當前最短距離:213.825
當前最短距離:216.204
當前最短距離:219.469
當前最短距離:258.466
當前最短距離:219.469
當前最短距離:213.825
當前最短距離:232.311
當前最短距離:278.578
當前最短距離:232.311
當前最短距離:213.825
當前最短距離:216.204
當前最短距離:219.469
當前最短距離:258.466
當前最短距離:219.469
當前最短距離:213.825
當前最短距離:232.311
當前最短距離:278.578
最短距離:213.825
路線:10 2 1 5 8 6 9 7 4 3

第二種

the best road is :
13 -> 24 -> 22 -> 23 -> 50 -> 4 -> 48 -> 9 -> 32 -> 44 -> 38 -> 29 -> 33 -> 20 -> 28 -> 34 -> 35 -> 2 -> 21 -> 27 -> 30 -> 19 -> 1 -> 49 -> 37 -> 8 -> 15 -> 31 -> 10 -> 0 -> 7 -> 25 -> 42 -> 6 -> 47 -> 26 -> 5 -> 45 -> 36 -> 14 -> 43 -> 41 -> 18 -> 39 -> 40 -> 12 -> 16 -> 3 -> 46 -> 11 -> 17

分析
模擬退火算法具有以下優缺點；
1.迭代搜索效率高，并且可以并行化；
2.算法中有一定概率接受比當前解較差的解，因此一定程度上可以跳出局部最優；
3.算法求得的解與初始解狀態S無關，因此有一定的魯棒性；
4.具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優解的全局優化算法。

參考
https://blog.csdn.net/daaikuaichuan/article/details/81381875
https://blog.csdn.net/wordsin/article/details/79915328
https://blog.csdn.net/chenlnehc/article/details/51933802

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/536113.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/536113.shtml
英文地址，請注明出處：http://en.pswp.cn/news/536113.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

2-docker 安裝

2-docker 安裝

2-docker 安裝 Ubuntu 安裝 由于 apt 源使用 HTTPS 以確保軟件下載過程中不被篡改。因此&#xff0c;我們首先需要添加使用 HTTPS 傳輸的軟件包以及 CA 證書。 $ sudo apt-get update$ sudo apt-get install \apt-transport-https \ca-certificates \curl \gnupg-agent \sof…
閱讀更多...
U-Net++粗略解釋

U-Net++粗略解釋

Paper&#xff1a;UNet: A Nested U-Net Architecture for Medical Image Segmentation u-net網絡的基本拓撲結構 目前最先進的圖像分割模型是各種個同樣的 encoder-decoder架構&#xff0c;他們具有一個關鍵的相似性&#xff1a;skip connections&#xff0c;它可以將編碼器…
閱讀更多...
Spring中的組合模式

Spring中的組合模式

組合模式是一種對象設計模式&#xff0c;它允許你將對象組合成樹形結構以表示“部分-整體”的層次結構&#xff0c;使得客戶端以統一的方式處理單個對象和對象的組合。在Spring框架中&#xff0c;組合模式被廣泛應用&#xff0c;讓我們深入分析一下。 在Spring中&#xff0c;組…
閱讀更多...
Docker+Nginx部署Angular

Docker+Nginx部署Angular

DockerNginx部署Angular 在部署Angular生產環境之前&#xff0c;需要電腦已經安裝docker。 添加Dockerfile 在已經完成的Angular項目的項目根目錄下添加Dockerfile文件。 Dockerfile文件內容&#xff1a; FROM nginx:1.11-1.11-alpine COPY index.html /usr/share/nginx/ht…
閱讀更多...
U-net網絡詳解

U-net網絡詳解

U-net網絡 簡單說一下網絡圖中各項所代表的內容&#xff1a; 藍/白色框表示feature map(特征圖) 藍色箭頭表示3x3卷積&#xff0c;主要用于特征提取 灰色箭頭表示skip-connection&#xff08;跳躍連接&#xff0c;通常用于殘差網絡中&#xff09;,在這里是用于用于特征融合&…
閱讀更多...
Angular Web App部署Ubuntu Nginx

Angular Web App部署Ubuntu Nginx

Angular Web App部署Ubuntu Nginx 當我們想發布Angular Web App的時候，我們想在開發的時候部署測試，那么這篇文章使用Nginx來部署我們的Angular 系統環境 lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.4 LTS Rele…
閱讀更多...
遺傳算法-01背包

遺傳算法-01背包

遺傳算法 算法思想 遺傳算法&#xff08;Genetic Algorithm, GA&#xff09;是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型&#xff0c;是一種通過模擬自然進化過程搜索最優解的方法。 其主要特點是直接對結構對象進行操作&#xff0c;不存在求導和函…
閱讀更多...
Angular Web App部署Linux Nginx Https

Angular Web App部署Linux Nginx Https

Angular Web App部署Linux Nginx Https 提示：這篇文章是基于內網的 互聯網就開始將 WEB 服務從 HTTP 遷移到 HTTPS，而現在為了更快的推進 HTTPS 的普及，Chrome 將從 2018 年 7 月起標記所有的 HTTP 網站為不安全鏈接。 HTTPS 會逐漸成為 WEB 服務的標配，最最重要的是，它能…
閱讀更多...
SOLO算法簡讀

SOLO算法簡讀

論文鏈接&#xff1a;https://arxiv.org/abs/1912.04488 代碼鏈接&#xff1a;https://github.com/WXinlong/SOLO 摘要 提出一種新的實例分割方法。與語義分割等其他密集預測任務相比&#xff0c;實例分割的難度要大得多。為了預測每個實例的掩碼&#xff0c;主流方法要么遵…
閱讀更多...
Rxjs的flatMap使用

Rxjs的flatMap使用

Rxjs的flatMap使用 flatMap是Rxjs比較繞的一個概念&#xff0c;這里我們只是講解如何使用。在Rxjs 4.0版本時叫flatMap,在Rxjs 5.0時被更名為margeMap,現在flatMap作為margeMap的別名使用&#xff0c;這是考慮向下兼容。 官方flatMap的定義&#xff1a; Projects each sourc…
閱讀更多...
關于Loss的簡單總結

關于Loss的簡單總結

Dice Loss 參考&#xff1a;https://blog.csdn.net/l7H9JA4/article/details/108162188 Dice系數&#xff1a; 是一種集合相似度度量函數&#xff0c;通常用于計算兩個樣本的相似度&#xff0c;取值范圍為[0,1]。 s2∣X∩Y∣∣X∣∣Y∣s \frac{2|X ∩ Y|}{|X||Y|} s∣X∣∣Y…
閱讀更多...
Angular_PWA使用+Demo

Angular_PWA使用+Demo

Angular_PWA使用+Demo 什么是PWA PWA（Progressive Web App）利用TLS，webapp manifests和service workers使應用程序能夠安裝并離線使用。 換句話說，PWA就像手機上的原生應用程序，但它是使用諸如HTML5，JavaScript和CSS3之類的網絡技術構建的。 如果構建正確，PWA與原生應…
閱讀更多...
SOLOv2論文簡讀

SOLOv2論文簡讀

論文&#xff1a;SOLOv2: Dynamic, Faster and Stronger 代碼&#xff1a;https://github.com/WXinlong/SOLO 摘要 主要提出了作者在SOLOv2中實現的優秀的實例分割方法&#xff0c;旨在創建一個簡單、直接、快速的實例分割框架&#xff1a; 通過提出動態學習對象分割器的mas…
閱讀更多...
Angular6_PWA

Angular6_PWA

Angular6_PWA Angular正式發布了V6.0，我們已經可以利用對應的@angular/cli V6.0來直接開發PWA應用了。 第一步：安裝@angular/cli V6.0 如果你機器上有老版本，請先卸載。 打開你的終端，執行： npm install -g @angular/cli 或 cnpm install -g @angular/cli 安裝成功…
閱讀更多...
Ubuntu18.04 關于使用vnc的踩坑

Ubuntu18.04 關于使用vnc的踩坑

由于種種原因&#xff0c;手上多了一臺可使用的桌面版Ubuntu&#xff0c;正好用來測試代碼&#xff0c;方便調試。因為只能遠程&#xff0c;所以需要配置遠程連接。因此就打算使用vnc進行遠程連接&#xff0c;誰料一路坎坷&#xff0c;特此記錄。 安裝 設置桌面共享 需要注意…
閱讀更多...
App_Shell模型

App_Shell模型

App_Shell模型 App Shell 架構是構建 Progressive Web App 的一種方式，這種應用能可靠且即時地加載到您的用戶屏幕上，與本機應用相似。 App shell是支持用戶界面所需的最小的 HTML、CSS 和 JavaScript，如果離線緩存，可確保在用戶重復訪問時提供即時、可靠的良好性能。這意…
閱讀更多...
Angular6_服務端渲染SSR

Angular6_服務端渲染SSR

Angular6_服務端渲染 在使用服務端渲染之前，需要安裝最新版本的Angular。 npm install -g @angular/cli 或 cnpm install -g @angular/cli github項目 創建項目 ng new PWCat --routing 為項目添加universalng g universal --client-project=PWCat 或
閱讀更多...
Jenkins自定義主題教程

Jenkins自定義主題教程

Jenkins自定義主題 由于Jenkins自帶的樣式比較丑陋&#xff0c;所以有很多第三方的樣式庫&#xff0c;這里針對jenkins-material-theme樣式庫做一個安裝教程。 下載樣式庫 下載連接 Select your color 選擇一個你喜歡的主題顏色。Choose your company logo 上傳你自定義的…
閱讀更多...
IndexedDB_Web 離線數據庫

IndexedDB_Web 離線數據庫

IndexedDB_Web 離線數據庫 本文會從頭剖析一下 IndexedDB 在前端里面的應用的發展。 indexedDB 目前在前端慢慢得到普及和應用。它正朝著前端離線數據庫技術的步伐前進。以前一開始是 manifest、localStorage、cookie 再到 webSQL&#xff0c;現在 indexedDB 逐漸被各大瀏覽器認…
閱讀更多...
Angular 單元測試講解

Angular 單元測試講解

Angular_單元測試 測試分類 按開發階段劃分按是否運行劃分按是否查看源代碼劃分其他ATDD,TDD,BDD,DDD ATDDTDDBDDDDDAngular單元測試 Karma的介紹jasmine介紹單元測試的好處使用jasmine和karma創建一個Angular項目Karma配置Test.ts文件測試體驗測試Form測試服務service常用斷言…
閱讀更多...
最新文章

Copyright @ 2022~2023