Kuang Algorithm Engineer&Data Mining Engineer

TSP问题求解方法

2017-09-01
Kuang

一名旅行商准备前往若干个城市推销他的产品,他想要从驻地出发,经过每个城市恰好一次,最后返回驻地,求满足条件的最短路径。这便是旅行商问题。旅行商问题是一个NP问题,至今尚未有准确的解法,现有的算法只能尽可能减小误差。目前最优的算法能在误差1%范围内估计上百万个城市的问题。

改良圈算法

改良圈算法的思想是首先求出一个哈密顿圈C,然后通过适当地修改哈密顿圈得到具有较小权值的另一个哈密顿圈。设初始圈$C=v_1v_2…v_nv_1$

对于$1\le i<i+1<j\le n$,构造新的哈密顿圈,即删去边$v_iv_{i+1}$和边$v_jv_{j+1}$ ,添加边$v_iv_j$和边$v_{i+1}v_{j+1}$得到的。

若$\omega(v_iv_j)+\omega(v_{i+1}v_{j+1})<\omega(v_iv_{i+1})+\omega(v_j,v_{j+1})$ 则用$C_{ij}$代替$C$,$C_{ij}$称为$C$的改良圈.

重复执行以上操作直至无法改进。

动态规划

动态规划的思想也比较简单,只需要用二进制来存储当前的状态(即当前已经走过的城市),$dp(i,j)$表示状态为$i$,从城市$j$出发的最短路径,转移方程如下

遗传算法

遗传算法是一种启发式算法,适合解决TSP这种不确定性问题,遗传算法的主要步骤概括为$新群体产生\rightarrow 选择 \rightarrow 交叉变异 \rightarrow 群体更新$ ,套用到旅行商问题上关键在于模型的建立,即如何初始化,如何选择(适应性评价方法),如何交叉变异

新群体产生

新群体产生可以随机生成几组1~n的排列,1~n为城市编号。排列1,3,4,2表示从1出发依次经过3,4到达2再返回到1。

选择

遗传算法每一轮选择适应度高的个体,可以使用路径长度的倒数或者相反数来评价个体的适应性。每一轮选择适应度高的个体

交叉

将父代样本两两分组,对染色体的某一段进行交叉,如

​ 9 5 1 3 7 4 2 10 8 6
​ 10 5 4 6 3 8 7 2 1 9

交叉为

​ 9 5 1 6 3 8 7 10 8 6
​ 10 5 4 3 7 4 2 2 1 9

对于有冲突的数字则将非交叉位置的重复数字用原位置的数代替,可以采用逐个交换,逐个代替的方法,如染色体1中的位置4与染色体2的位置4交换,即染色体1上位置4的数字变成6。6在染色体1中在第10位,则只需将染色体1位置4与位置10交换即可,染色体2也进行类似的操作

交叉后两条染色体变成

​ 9 5 1 6 3 8 7 10 4 2
​ 10 5 8 3 7 4 2 6 1 9

变异

变异的过程比较简单,随机选取几条染色体,并对每条染色体随机取两个位置,交换两个位置的数字即可。

进化逆转

随机去两个位置,将这两个位置中间的数反向,保留原染色体和反向后的染色体中适应性较强的染色体。

代码

/*
遗传算法解TSP问题

*/
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) x.size()
#define mp make_pair
#define FI first
#define SE second
using namespace std ;

//g[i][j] 表示i到j的距离
int g[2000][2000] ;

// 比较函数
bool cmp(pair<vector<int>,int> a ,pair<vector<int>,int> b)
{
    return a.SE<b.SE ;
}
int main()
{
    int t = 10;
    //随机数
	srand((unsigned)time(NULL));
    int n,m;
    while(cin>>n>>m){

		memset(g,0x3f,sizeof g);
		//输入u到v的距离w
		for(int i = 0 ;i<m ;i++){
			int u,v,w ;
			scanf("%d%d%d",&u,&v,&w);
			g[u][v] = g[v][u] = min(w,g[u][v]);
		}
        while(t--){
            int num[1000];
            for(int i = 0 ;i<n ;i++){
                num[i] = i +1;
            }
            pair<vector<int>,int> ans[1000] ;
            //生成10*n个初始序列
            int cnt =  1;
            do{
                double r = (rand()%n)/(1.0*n) ;
                if(r<0.3){
                    ans[cnt].FI.pb(0) ;
                    for(int j=0;j<n;j++){
                        ans[cnt].FI.pb(num[j]) ;
                    }
                    ans[cnt].FI.pb(num[0]);
                    cnt++;
                }
                if(cnt==10*n+1){
                    break ;
                }
            }while(next_permutation(num,num+n));
            cout<<cnt<<endl;
            //改良圈产生初始染色体
            for(int i =1 ;i<=10*n;i++){
                int flag = 1;
                while(flag){
                    flag = 0 ;
                    for(int u = 1;u<sz(ans[i].FI)-2;u++){
                        for(int v = u+1;v<=sz(ans[i].FI)-2;v++){
                            if(g[(ans[i].FI)[u]][(ans[i].FI)[u+1]]+g[(ans[i].FI)[v]][(ans[i].FI)[v+1]] > g[(ans[i].FI)[u]][(ans[i].FI)[v]]+g[(ans[i].FI)[u+1]][(ans[i].FI)[v+1]]){
                                swap((ans[i].FI)[u+1],(ans[i].FI)[v]) ;
                                flag = 1;
                            }
                        }
                    }
                }
            }
            //算法遗传100代
            //交叉
            //先将染色体按照适应度排序
            double hundun1 = (rand()%n)/(1.0*n) ;
            double hundun2 = (rand()%n)/(1.0*n) ;
            for(int i = 1 ;i<=100 ;i++){

                for(int j = 1 ;j<=10*n ;j++){
                    int len  = 0 ;
                    for(int k = 1 ; k<sz(ans[j].FI)-1;k++){
                        len+=g[(ans[j].FI)[k]][(ans[j].FI)[k+1]];
                    }
                    ans[j].SE = len ;
                }
                sort(ans+1,ans+10*n+1,cmp);
                //将交叉点1和交叉点2之间的基因交换
                //如果有n个点,则交叉点应该在2~n
                int jiaochadian1 = hundun1*(n-1)+2 ;
                int jiaochadian2 = hundun2*(n-1)+2 ;
                for(int j = 1 ;j<=10*n ;j++){
                    ans[10*n+j] = ans[j];
                }
                for(int j = 1 ;j<=10*n;j+=2){

                    if(jiaochadian2<jiaochadian1){
                        swap(jiaochadian1,jiaochadian2) ;
                    }
                    for(int k = jiaochadian1;k<=jiaochadian2;k++){
                        int l1 ;
                        for(l1 = 2 ; l1<sz(ans[10*n+j].FI);l1++){
                            if((ans[10*n+j].FI)[l1] == (ans[10*n+j+1].FI)[k]){
                                break ;
                            }
                        }
                        if(l1 == sz(ans[10*n+j].FI)-1){
                            continue ;
                        }
                        int x = (ans[10*n+j].FI)[l1] ;
                        swap((ans[10*n+j].FI)[l1],(ans[10*n+j].FI)[k]) ;
                        int l2 ;
                        for(l2 = 2 ;l2<sz(ans[10*n+j+1].FI) ; l2++){
                            if((ans[10*n+j+1].FI)[l2] == x ){
                                break ;
                            }
                        }
                        if(l2 == sz(ans[10*n+j+1].FI)-1){
                            continue ;
                        }
                        swap((ans[10*n+j+1].FI)[l2],(ans[10*n+j+1].FI)[k]);
                    }
                }
                //变异

                //交换变异点上的基因
                double bianyilv = 0.85;
                for(int j = 1 ;j<= 20*n ;j++){
                    double aaa = (rand()%n)/(1.0*n);
                    if(aaa>bianyilv){
                        int bianyidian1 = (rand()%n)/(1.0*n) * (n-1)+2 ;
                        int bianyidian2 = (rand()%n)/(1.0*n) * (n-1)+2 ;
                        swap((ans[j].FI)[bianyidian1] , (ans[j].FI)[bianyidian2]) ;
                    }
                }
                //选择
                for(int j = 1 ;j<=20*n ;j++){
                    int len  = 0 ;
                    for(int k = 1 ; k<sz(ans[j].FI)-1;k++){
                        len+=g[(ans[j].FI)[k]][(ans[j].FI)[k+1]];
                    }
                    ans[j].SE = len ;
                }
                sort(ans+1,ans+20*n+1,cmp) ;
                //更新混沌值
                hundun1 = hundun1*4*(1-hundun1) ;
                hundun2 = hundun2*4*(1-hundun2) ;
            }
            for(int j = 1 ;j<=20*n ;j++){
                    int len  = 0 ;
                    for(int k = 1 ; k<sz(ans[j].FI)-1;k++){
                        len+=g[(ans[j].FI)[k]][(ans[j].FI)[k+1]];
                    }
                    ans[j].SE = len ;
             }
             sort(ans+1,ans+20*n+1,cmp);
             for(int i = 1 ; i<sz(ans[1].FI);i++){
                cout<<(ans[1].FI)[i]<<" ";
             }
             cout<<endl;
             cout<<ans[1].SE<<endl;
        }
    }
    return 0 ;
}

/*
10 45
1 2 8
1 3 5
1 4 9
1 5 12
1 6 14
1 7 12
1 8 16
1 9 17
1 10 22
2 3 9
2 4 15
2 5 17
2 6 8
2 7 11
2 8 18
2 9 14
2 10 22
3 4 7
3 5 9
3 6 11
3 7 7
3 8 12
3 9 12
3 10 17
4 5 3
4 6 17
4 7 10
4 8 7
4 9 15
4 10 18
5 6 8
5 7 10
5 8 6
5 9 15
5 10 15
6 7 9
6 8 14
6 9 8
6 10 16
7 8 8
7 9 6
7 10 11
8 9 11
8 10 11
9 10 10
*/


Comments