蚁群算法_谛听-的博客-程序员宅基地

技术标签: 优化  

TSP问题要求:
1、路径限制:每个城市只能访问一次。
2、最后要回到出发的城市。
3、求得的路径为所有路径中最小的路径。

原理:
http://max.book118.com/html/2016/0421/40996215.shtm

代码:
http://blog.sina.com.cn/s/blog_6bb1b4b001016pt0.html

//蚁群算法关于简单的TSP问题求解//

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>

#define M 13        //蚂蚁的数量
#define N 144       //城市的数量
#define R 1000      //迭代次数
#define IN 1        //初始化的信息素的量
#define MAX 0x7fffffff //定义最大值

struct coordinate
{
    char city[15];  //城市名
    int x;          //城市相对横坐标
    int y;          //城市相对纵坐标
}coords[N];

double graph[N][N];  //储存城市之间的距离的邻接矩阵,自己到自己记作MAX
double phe[N][N];    //每条路径上的信息素的量
double add[N][N];    //代表相应路径上的信息素的增量
double yita[N][N];   //启发函数,yita[i][j]=1/graph[i][j]
int vis[M][N];       //标记已经走过的城市
int map[M][N];       //map[K][N]记录第K只蚂蚁走的路线
double solution[M];  //记录某次循环中每只蚂蚁走的路线的距离
int bestway[N];      //记录最近的那条路线
double bestsolution=MAX;
int NcMax;           //代表迭代次数,理论上迭代次数越多所求的解更接近最优解,最具有说服力
double alpha;        //信息素的相对重要性
double beta;         //启发素的相对重要性
double rou;          //小于1的常数,表示信息的持久性
double Q;            //常数

void Initialize();   //信息初始化
void Inputcoords(FILE *fp);   //将文件中的坐标信息读入
void GreateGraph();  //根据坐标信息建图
double Distance(int *p);      //计算蚂蚁所走的路线的总长度
void Result();       //将结果保存到out.txt中

void Initialize()
{
    alpha = 2; 
    beta = 2; 
    rou = 0.7; 
    Q = 5000;
    NcMax = R;
    return ;
}

void Inputcoords(FILE *fp)
{
    int i;
    int number;
    if(fp==NULL)
    {
        printf("Sorry,the file is not exist\n");
        exit(1);
    }
    else
    {
        for(i=0; i<N; ++i)
        {
            fscanf(fp,"%d%s", &number, coords[i].city);
            fscanf(fp,"%d,%d", &coords[i].x, &coords[i].y);
        }
    }
}

void GreateGraph( )
{
    int i,j;
    double d;
    for(i=0; i<N-1; ++i)
    {
        graph[i][i]=MAX;   //自己到自己标记为无穷大
        for(j=i+1; j<N; ++j)
        {
            d = (double)((coords[i].x-coords[j].x) * (coords[i].x-coords[j].x)
                + (coords[i].y-coords[j].y) * (coords[i].y-coords[j].y));
            graph[j][i] = graph[i][j] = sqrt(d);
        }
    }
    graph[N-1][N-1] = MAX;
    return ;
}

double Distance(int *p)
{
    double d=0;
    int i;
    for(i=0; i<N-1; ++i)
    {
        d += graph[*(p+i)][*(p+i+1)];
    }
    d += graph[*(p+i)][*(p)];
    return d;
}

void Result()
{
    FILE *fl;
    int i;
    fl = fopen("out.txt","a");  //将结果保存在out.txt这个文件里面
    fprintf(fl,"%s\n", "本次算法中的各参数如下:");
    fprintf(fl,"alpha=%.3lf, beta=%.3lf, rou=%.3lf, Q=%.3lf\n",alpha,beta,rou,Q);
    fprintf(fl,"%s %d\n", "本次算法迭代次数为:",NcMax);
    fprintf(fl,"%s %.4lf\n", "本算法得出的最短路径长度为:",bestsolution);
    fprintf(fl,"%s\n", "本算法求得的最短路径为:");
    for(i=0; i<N; ++i)
        fprintf(fl,"%s →  ", coords[bestway[i]].city);
    fprintf(fl,"%s", coords[bestway[0]].city);
    fprintf(fl, "\n\n\n");
    fclose(fl);
    return;
}

int main()
{
    int NC = 0;
    int i,j,k;
    int s;
    double drand, pro, psum;
    FILE *fp;
    Initialize();
    fp = fopen("coords.txt","r+");
    Inputcoords(fp);
    GreateGraph();
    fclose(fp);
    for(i=0; i<N; ++i)
    {
        for(j=0; j<N; ++j)
        {
            phe[i][j] = IN; //信息素初始化
            if(i != j)
                yita[i][j] = 100.0 / graph[i][j];  //期望值,与距离成反比
        }
    }
    memset(map, -1, sizeof(map));   //把蚂蚁走的路线置空
    memset(vis, 0, sizeof(vis));    //0表示未访问,1表示已访问
    srand(time(NULL));
    while(NC++ <= NcMax)
    { 
        for(k=0; k<M; ++k)
        {
            map[k][0] = (k+NC) % N;  //给每只蚂蚁分配一个起点,并且保证起点在N个城市里
            vis[k][map[k][0]] = 1;   //将起点标记为已经访问
        }
        s = 1;
        while(s < N)
        {
            for(k=0; k<M; ++k)
            {
                psum = 0;
                for(j=0; j<N; ++j)
                {
                    if(vis[k][j] == 0)
                    {
                        // 转移概率的分母
                        psum += pow(phe[ map[k][s-1] ][j], alpha) * pow(yita[ map[k][s-1] ][j], beta);
                    }
                }
                drand = (double)(rand() % 5000);
                drand /= 5000.0;  //生成一个小于1的随机数
                pro = 0;
                for(j=0; j<N; ++j)
                {
                    if(vis[k][j] == 0)
                    {
                        // 转移概率:
                        // phe[i][j]表示边(i,j)上的信息素浓度
                        // yita[i][j]是启发信息,与距离成反比,表示城市j相对城市i的可见度
                        pro += pow(phe[map[k][s-1]][j], alpha) * pow(yita[map[k][s-1]][j], beta) / psum;
                    }
                    if(pro > drand)
                        break;
                }
                vis[k][j] = 1;  //将走过的城市标记起来
                map[k][s] = j;  //记录城市的顺序
            }
            s++;
        }
        memset(add, 0, sizeof(add));
        for(k=0; k<M; ++k)      //计算本次中的最短路径
        {
            solution[k] = Distance(map[k]);  //蚂蚁k所走的路线的总长度
            if(solution[k] < bestsolution)
            {
                bestsolution = solution[k];
                for(i=0; i<N; ++i)
                    bestway[i] = map[k][i];
            }
        }

        // 进行信息素更新
        for(k=0; k<M; ++k)
        {
            for(j=0; j<N-1; ++j)
            {
                add[ map[k][j] ][ map[k][j+1] ] += Q/solution[k];
            }
            add[N-1][0] += Q/solution[k];
        }
        for(i=0; i<N; ++i)
        {
            for(j=0; j<N; ++j)
            {
                // rou为小于1的常数,表示信息的持久性
                phe[i][j] = phe[i][j]*rou + add[i][j];
                if(phe[i][j] < 0.0001)   //设立一个下界
                    phe[i][j] = 0.0001;
                else if(phe[i][j] > 20)  //设立一个上界,防止启发因子的作用被淹没
                    phe[i][j] = 20;
            }
        }
        memset(vis,0,sizeof(vis));
        memset(map,-1,sizeof(map));
    }
    Result();
    printf("Result is saved in out.txt\n");
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u012319493/article/details/70139610

智能推荐

企业知识管理专家:KMaster知识管理平台简介_deform0032的博客-程序员宅基地

KMaster知识管理平台简介什么是知识管理?知识管理(Knowledge Management,简称KM)是协助企业,围绕各种来源的知识内容,利用信息技术,实现知识的生产、分享、应用以及创新,并在企业内产生价值的过程。简单地说,就是使企业从知识中产生价值的过程。任何企业都在不同程度上依赖于一定的技术和知识才可以生存与发展,尤其当今已经进入了知识经济的时代,现代企业之...

ubuntu终端中上下左右变成ABCD_野生蘑菇菌的博客-程序员宅基地

不得不说,卸载重装也是个好的选择。sudo apt-get remove vim-commonsudo apt-get updatesudo apt-get install vim

keil4程序从JLINK8下载后,不能运行,需要重启的原因_会飞行的小蜗牛的博客-程序员宅基地

keil4  ->  Options for target -> utilities  -> Flash Download -> Reset and run(选中这个)

【从小项目学图片处理】#1 答题卡识别_天真的和感伤的想象家的博客-程序员宅基地

说明:项目皆来源于网上,代码也会大部分参考原文。仅用于学习和练习图像处理操作。项目原文: Bubble sheet multiple choice scanner and test grader using OMR, Python and OpenCV问题描述:...

C++ STL 常用函数_Mr.bei的博客-程序员宅基地_c++stl常用函数

C++ STL 常用函数vector 数组vector 可以被看成一个“超级数组” ,不会和C语言数组一样被限制长度,它既可以和C语言的数组一样用下标访问,也可以像链表一样动态改变长度。#include&lt;vector&gt; //头文件vector&lt;int&gt; arr1(100);int arr2[100]; //该定义类似C语言数组vector&lt;int&gt; list;list.push_back(1);list.push_back(2);....

# 2014年蓝桥杯真题CC++B组_碑无名的博客-程序员宅基地

2014年蓝桥杯真题C/C++B组1.啤酒和饮料题目描述啤酒每罐2.3元,饮料每罐1.9元,小明买了若干啤酒和饮料,一共花了82.3元。我们还知道她买的啤酒比饮料的数量多,请你计算他买了几罐啤酒。注意:答案是一个整数。请通过浏览器提交答案。不要书写任何多余的内容(例如:写了饮料的数量,添加文字说明等)。解题思路这题直接暴力一下就可以了注意题目的要求,暴力没问题题解#include&lt;stdio.h&gt;int main(){ for(int i = 1; i &lt; 40;

随便推点

GPS格式标准_dengdun6257的博客-程序员宅基地

GPS接收机串行通信标准摘要参考NMEA-0183美国国家海洋电子协会(NMEA—The NationalMarine Electronics Association) 为了在不同的GPS导航设备中建立统一的RTCM(海事无线电技术委员会)标准,先后制定了NMEA-0180、0182和0183三个标准。0183可以认为是前两种的升级,也是目前使用最为广泛的一种。目前广泛采用的是V...

Spring配置-- Bean节点中property标签中name和ref__明月的博客-程序员宅基地_bean property标签

 本文未完待续......      参考文章:1、spring 的配置 bean&amp;gt;&amp;gt;property&amp;gt;&amp;gt;name属性 2、Spring配置文件中配置property标签的name和ref的区别   ...

android.content.res.Resources$NotFoundException_dengjia1978的博客-程序员宅基地

http://www.blogjava.net/anchor110/articles/355670.html转载于:https://www.cnblogs.com/leiqun123/p/4594865.html

Redis+Django(Session,Cookie、Cache)的用户系统_dechen6073的博客-程序员宅基地

转自http://www.cnblogs.com/BeginMan/p/3890761.html一.Django authenticationdjango authentication提供了一个便利的user api接口,无论在py中request.user,参见Request and response objects.还是模板中的{{user}}都能随时随地使用,...

python 随机划分图片数据集_dear_zhoubi的博客-程序员宅基地_数据集随机划分

一个随机划分图片数据集的方法。任务描述:我的所有图片保存在同一个文件夹里,需要随机划分为训练集和测试集。处理过程:读取文件列表,将列表打乱,截取列表一部分import osimport randomimport shutildef get_imlist(path): return [os.path.join(path, f) for f in os.listdir(...

win网络编程-列出IP地址_deepfuture的博客-程序员宅基地

 #include &quot;../common/InitSock.h&quot;#include &amp;lt;stdio.h&amp;gt;CInitSock initSock;//初始化Winsock库void main(){char szHost[256];// 取得本地主机名称::gethostname(szHost, 256);// 通过主机名得到地址信息hostent *pHost = ::gethos...

推荐文章

热门文章

相关标签