基于高德地图的行程规划-蚁群算法_行程规划算法

问题：项目开发遇到了一个行程规划问题，就是去一个城市几个地点拜访，要求串联的距离最短

思考：这是一个旅行商的问题，不过这个不需要回到起点，只要求到终点就完成拜访，于是百度了很久，最终采用蚁群算法。

介绍：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

思路：

1.设定一个起点，其他的都是需要拜访的点，所有点设为一个数组，循环设置每个点为起点，调用高德api获取这个点与其他各点之间的距离，自身点设为无穷大，获取到的是一个二维数组，为了性能，调用的是高德api的批量接口，防止频繁请求接口。

2.得到的二维数组既是一个点与各个点之间的距离，通过模拟蚁群算法，得到最优解

蚁群算法代码：

蚁群算法中主要有下面几个参数需要设定： 

蚂蚁数量： 
设M表示城市数量，m表示蚂蚁数量。m的数量很重要，因为m过大时，会导致搜索过的路径上信息素变化趋于平均，这样就不好找出好的路径了；m过小时，易使未被搜索到的路径信息素减小到0，这样可能会出现早熟，没找到全局最优解。一般上，在时间等资源条件紧迫的情况下，蚂蚁数设定为城市数的1.5倍较稳妥。

信息素因子： 
信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值过大，蚂蚁选择以前走过的路径概率大，搜索随机性减弱；值过小，等同于贪婪算法，使搜索过早陷入局部最优。实验发现，信息素因子选择[1,4]区间，性能较好。

启发函数因子： 
启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时，虽然收敛速度会加快，但容易陷入局部最优；过小时，容易陷入随机搜索，找不到最优解。实验研究发现，当启发函数因子为[3,4.5]时，综合求解性能较好。

信息素挥发因子： 
信息素挥发因子表示信息素的消失水平，它的大小直接关系到蚁群算法的全局搜索能力和收敛速度。实验发现，当属于[0.2，0.5]时,综合性能较好。

信息素常数： 
这个参数为信息素强度，表示蚂蚁循环一周时释放在路径上的信息素总量，其作用是为了充分利用有向图上的全局信息反馈量，使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。值越大，蚂蚁在已遍历路径上的信息素积累越快，有助于快速收敛。实验发现，当值属于[10,1000]时，综合性能较好。

最大迭代次数： 
最大迭代次数值过小，可能导致算法还没收敛就已结束；过大则会导致资源浪费。一般最大迭代次数可以取100到500次。一般来讲，建议先取200，然后根据执行程序查看算法收敛的轨迹来修改取值。

蚂蚁类：

public class Ant implements Cloneable {
 
	public int[] m_nPath = new int[PublicFun.N_CITY_COUNT];// 蚂蚁走过的路径
	public double m_dbPathLength;// 蚂蚁走过的路径长度
 
	public int[] m_nAllowedCity = new int[PublicFun.N_CITY_COUNT];// 蚂蚁没有去过的城市
	public int m_nCurCityNo;// 当前所在城市的编号
	public int m_nMovedCityCount;// 已经去过的城市数量
 
	/*
	 * 初始化函数,蚂蚁搜索前调用该方法
	 */
	public void Init() {
		for (int i = 0; i < PublicFun.N_CITY_COUNT; i++) {
			m_nAllowedCity[i] = 1;// 设置全部城市没有去过
			m_nPath[i] = 0;// 蚂蚁走过的路径全部设置为0
		}
		m_dbPathLength = 0.0; // 蚂蚁走过的路径长度设置为0
 
		m_nCurCityNo = 0;//选择一个出发点
 
		m_nPath[0] = m_nCurCityNo;// 把出发城市保存的路径数组中
 
		m_nAllowedCity[m_nCurCityNo] = 0;// 标识出发城市已经去过了
 
		m_nMovedCityCount = 1;// 已经去过的城市设置为1;
	}
 
	/*
	 * 覆盖Object中的clone()方法 实现对象的复制
	 */
	protected Object clone() throws CloneNotSupportedException {
		return super.clone();
	}
 
	/*
	 * 选择下一个城市 返回值为城市编号
	 */
	public int ChooseNextCity() {
 
		int nSelectedCity = -1;// 返回结果,初始化为-1
 
		// 计算当前城市和没去过城市的信息素的总和
		double dbTotal = 0.0;
		double[] prob = new double[PublicFun.N_CITY_COUNT];// 用来保存各个城市被选中的概率
 
		for (int i = 0; i < PublicFun.N_CITY_COUNT; i++) {
			if (m_nAllowedCity[i] == 1)// 城市没去过
			{
				// 该城市和当前城市的信息素，随着迭代次数增加，城市之间的信息素会随之变化
				prob[i] = Math.pow(PublicFun.g_Trial[m_nCurCityNo][i], PublicFun.ALPHA)				
						* Math.pow(1.0 / PublicFun.g_Distance[m_nCurCityNo][i], PublicFun.BETA);
				dbTotal = dbTotal + prob[i];// 累加信息素
			} else// 如果城市去过了 则被选中的概率为0;
			{
				prob[i] = 0.0;
			}
 
		}
 
		// 进行轮盘选择，信息素值大的选中的概率就会大，选择下一个城市
		double dbTemp = 0.0;
		if (dbTotal > 0.0)// 如果总的信息素大于0
		{
			dbTemp = PublicFun.rnd(0.0, dbTotal);// 取一个随机数
 
			for (int i = 0; i < PublicFun.N_CITY_COUNT; i++) {
				if (m_nAllowedCity[i] == 1)// 城市没有去过
				{
					dbTemp = dbTemp - prob[i];// 相当于轮盘
 
					if (dbTemp < 0.0)// 轮盘停止转动,记下城市编号,跳出循环
					{
						nSelectedCity = i;
						break;
					}
				}
 
			}
		}
 
		/*
		 * 如果城市间的信息素非常小 ( 小到比double能够表示的最小的数字还要小 ) 那么由于浮点运算的误差原因，上面计算的概率总和可能为0
		 * 会出现经过上述操作，没有城市被选择出来 出现这种情况，就把第一个没去过的城市作为返回结果
		 */
		if (nSelectedCity == -1) {
			for (int i = 0; i < PublicFun.N_CITY_COUNT; i++) {
				if (m_nAllowedCity[i] == 1)// 城市没有去过
				{
					nSelectedCity = i;
					break;
				}
			}
		}
		return nSelectedCity;
	}
 
	/*
	 * 蚂蚁在城市间移动
	 */
	public void Move() {
		int nCityNo = ChooseNextCity();// 选择下一个城市
		m_nPath[m_nMovedCityCount] = nCityNo;// 保存蚂蚁走过的路径
		m_nAllowedCity[nCityNo] = 0;// 把这个城市设置为已经去过了
		m_nCurCityNo = nCityNo;// 改变当前城市为选择的城市
		m_nMovedCityCount++;// 已经去过的城市加1
	}
 
	/*
	 * 蚂蚁进行一次搜索
	 */
	public void Search() {
		Init();// 蚂蚁搜索前,进行初始化
 
		// 如果蚂蚁去过的城市数量小于城市数量,就继续移动
		while (m_nMovedCityCount < PublicFun.N_CITY_COUNT) {
			Move();// 移动
		}
		// 完成搜索后计算走过的路径长度
		CalPathLength();
	}
 
	/*
	 * 计算蚂蚁走过的路径长度
	 */
	public void CalPathLength() {
		m_dbPathLength = 0.0;// 先把路径长度置0
		int m = 0;
		int n = 0;
 
		for (int i = 1; i < PublicFun.N_CITY_COUNT; i++) {
			m = m_nPath[i];
			n = m_nPath[i - 1];
			m_dbPathLength = m_dbPathLength + PublicFun.g_Distance[m][n];
		}
		m_dbPathLength = (Math.round(m_dbPathLength * 100)) / 100.0;
	}
 
}

常量类：

public class PublicFun {
	public static final double ALPHA = 2.0;//信息素因子
	public static final double BETA = 3.0;// 启发函数因子, 城市间距离的重要程度
	public static final double ROU = 0.5;//信息素挥发因子
 
	public static int N_IT_COUNT = 200;// 迭代次数
	public static int N_CITY_COUNT = 15;// 城市数量
	public static int N_ANT_COUNT = N_CITY_COUNT*2;// 蚂蚁数量
 
	public static final double DBQ = 100.0;// 总信息素
	public static final double DB_MAX = Math.pow(10, 9);// 一个标志数,用来初始化一个比较大的最优路径
 
	// 两两城市间的信息量
	public static double[][] g_Trial;
 
	// 两两城市间的距离
	public static Double[][] g_Distance;
 
	// 返回指定范围内的随机整数
	public static int rnd(int nLow, int nUpper) {
		return (int) (Math.random() * (nUpper - nLow) + nLow);
	}
 
	// 返回指定范围内的随机浮点数
	public static double rnd(double dbLow, double dbUpper) {
		return Math.random() * (dbUpper - dbLow) + dbLow;
	}
}

算法核心类：

public class Tsp {
	
	//蚂蚁数组  
    public Ant[] m_antAry=new Ant[PublicFun.N_ANT_COUNT];  
    public Ant[] m_betterAnts=new Ant[PublicFun.N_IT_COUNT];//定义一组蚂蚁,用来保存每一次搜索中较优结果,不参与搜索  
    public Ant m_bestAnt;//定义一个蚂蚁变量,用来保存最终最优结果,不参与搜索  
    
	/* 
     * 初始化数据 
     */  
    public void InitData() throws CloneNotSupportedException  
    {  
        //初始化所有蚂蚁  
          
        PublicFun.g_Trial=new double[PublicFun.N_CITY_COUNT][PublicFun.N_CITY_COUNT];  
        m_bestAnt=new Ant();  
        for (int i = 0; i <PublicFun.N_ANT_COUNT; i++)  
        {  
            m_antAry[i]=new Ant();  
        }  
        for (int i = 0; i < PublicFun.N_IT_COUNT; i++)  
        {  
            m_betterAnts[i]=new Ant();  
            m_betterAnts[i].m_dbPathLength=PublicFun.DB_MAX;//把较优蚂蚁的路径长度设置为一个很大值  
        }  
          
        //先把最优蚂蚁的路径长度设置为一个很大值  
        m_bestAnt.m_dbPathLength=PublicFun.DB_MAX;  
          
        //初始化信息素  
        for(int i=0;i<PublicFun.N_CITY_COUNT;i++)  
        {  
            for(int j=0;j<PublicFun.N_CITY_COUNT;j++)  
            {  
                PublicFun.g_Trial[i][j]=1.0;  
            }  
        }  
          
        Iterator();//开始迭代  
          
    }  
      
    /* 
     * 更新环境信息素 
     */  
      
    public void UpdateTrial()  
    {  
        //临时数组,保存各只蚂蚁在两两城市间新留下的信息素  
        double[][] dbTempAry=new double[PublicFun.N_CITY_COUNT][PublicFun.N_CITY_COUNT];  
          
        //全部设置为0;  
        for (int i = 0; i <PublicFun.N_CITY_COUNT; i++)  
        {  
            for (int j = 0; j < PublicFun.N_CITY_COUNT; j++)  
            {  
                dbTempAry[i][j]=0.0;  
            }  
        }  
        //计算新增加的信息素,保存到临时变量  
        int m=0;  
        int n=0;  
        for(int i=0; i<PublicFun.N_ANT_COUNT;i++)  
        {  
            for (int j = 1; j < PublicFun.N_CITY_COUNT; j++)  
            {  
                m=m_antAry[i].m_nPath[j];  
                n=m_antAry[i].m_nPath[j-1];  
                dbTempAry[n][m]=dbTempAry[n][m]+PublicFun.DBQ/m_antAry[i].m_dbPathLength;  
                dbTempAry[m][n]=dbTempAry[n][m];  
            }  
              
            //最后城市与开始城市之间的信息素  
//            n=m_antAry[i].m_nPath[0];  
//            dbTempAry[n][m]=dbTempAry[n][m]+PublicFun.DBQ/m_antAry[i].m_dbPathLength;  
//            dbTempAry[m][n]=dbTempAry[n][m];  
        }  
          
        //更新环境信息素  
        for (int i = 0; i < PublicFun.N_CITY_COUNT; i++)  
        {  
            for (int j = 0; j < PublicFun.N_CITY_COUNT; j++)  
            {  
                //最新的环境信息素 = 留存的信息素 + 新留下的信息素    
                PublicFun.g_Trial[i][j]=PublicFun.g_Trial[i][j]*PublicFun.ROU+dbTempAry[i][j];  
            }  
        }  
    }  
      
      
    /* 
     * 迭代 
     */  
    public void Iterator() throws CloneNotSupportedException  
    {  
        //迭代次数内进行循环  
  
        for (int i = 0; i < PublicFun.N_IT_COUNT; i++)  
        {  
            //每只蚂蚁搜索一遍  
            for(int j=0;j<PublicFun.N_ANT_COUNT;j++)  
            {  
                m_antAry[j].Search();  
            }  
              
            //保存较优结果  
            for(int j=0;j<PublicFun.N_ANT_COUNT;j++)  
            {  
                if (m_antAry[j].m_dbPathLength < m_betterAnts[i].m_dbPathLength)  
                {  
                    m_betterAnts[i] = (Ant) m_antAry[j].clone();  
                }  
            }  
            UpdateTrial();  
        }  
  
        //找出最优蚂蚁  
        for(int k=0;k<PublicFun.N_IT_COUNT;k++)  
        {  
            if(m_betterAnts[k].m_dbPathLength<m_bestAnt.m_dbPathLength)  
            {  
                m_bestAnt=m_betterAnts[k];  
            }  
        }  
          
    //  getBetterAnt();//输出每次的较优路径  
//      getBestAnt();//输出最佳路径  
          
    }  
    /* 
     * 输出最佳路径到控制台.(暂不使用,但保留) 
     */  
    public void getBestAnt()  
    {  
        System.out.println("最佳路径:");  
        System.out.println( "路径:"+getAntPath(m_bestAnt)+"长度:"+getAntLength(m_bestAnt));  
    }  
      
    /* 
     * 输出每次的较优路径到控制台.(暂不使用,但保留) 
     */  
    public void getBetterAnt()  
    {  
        System.out.println("每一次的较优路径:");  
        for (int i = 0; i < m_betterAnts.length; i++)  
        {  
             System.out.println("("+i+") 路径:"+getAntPath(m_betterAnts[i])+"长度:"+getAntLength(m_betterAnts[i]));  
        }  
    }  
  
    /* 
     * 返回蚂蚁经过的路径 
     */  
    public String getAntPath(Ant ant)  
    {  
        String s="";  
        for(int i=0;i<ant.m_nPath.length;i++)  
        {  
            s+=ant.m_nPath[i]+"-";  
        }  
        s+=ant.m_nPath[0];  //蚂蚁最后要回到开始城市  
        return s;  
    }  
    /* 
     * 返回蚂蚁经过的长度 
     */  
    public double getAntLength(Ant ant)  
    {  
        return ant.m_dbPathLength;  
    }  
      
 
}

代码转载：https://blog.csdn.net/wuchuanpeng/article/details/51583829

流程图：