|
基于改进蚁群算法求解TSP问题
1.算法思想2.算法设计3. 详细代码4. 测试结果测试数据测试结果各取10次中最好结果进行分析取10次结果的平均进行分析
结果分析
5.结论参考文献：
1.算法思想
蚂蚁沿不同的路径出去寻找食物，找到食物就马上返回。这样短路径的蚂蚁来回一次时间短，单位时间内走过的蚂蚁数目就多，洒下的信息素自然会多，从而吸引更多蚂蚁，洒下更多信息素。而长路径恰好相反。因此，越来越多的蚂蚁会聚集到短路径上来，从而找到最短路径。即问题的找到问题的近似最优解。
2.算法设计
对于蚁群算法求解TSP问题，很容易陷入局部最优的情况，求解的结果经度低。为了改进这一缺点，通过查阅参考文献，找到了一些方法去提升全局搜索能力，有效规避蚁群算法陷入局部最优。 对于 TSP问题，设蚁群中蚂蚁的数量为m,城市的数量为n,结点i与结点j之间的欧式距离为 dij(t) ，t时刻结点i与结点j之间相连接的路径上的信息素浓度为τij,启发因子为ηij,信息素权重因子为α=1，启发因子β=5。初始时刻，蚂蚁放置在不同结点里，且各结点连接路径上的信息素浓度相同，然后蚂蚁按一定的概率选择路线。不妨将 Pkij(t) 设为 t时刻蚂蚁k从结点i转移到结点j的概率。“蚂蚁TSP”策略收到两方面的左右，首先是访问某结点的概率，这个概率的大小依赖于其他蚂蚁释放的信息素浓度。所以定义：  Jk(i)表示城市i可以直接到达的且又不在蚂蚁访问的城市系列里的城市的集合，算法实验开始之前找到了31个城市的坐标信息，构造出蚁群算法所要求解的问题，根据坐标信息计算出两两城市之间的距离信息dij（t），然后初始化蚂蚁数量m=50并根据距离信息初始化信息素分布，将蚂蚁随机并尽可能均匀地分配在各个城市，找到信息素发散点[1]增强信息素的挥发性以及增加量，信息素发散点即是一段时间最优解没有发生变化的时刻，如果一段时间最优解依然没有发生变化，重置信息素矩阵。传统的蚁群算法使得各个路径上的信息素浓度都相等，这很容易造成信息素的浓度不具有指导性，让算法陷入局部最优，改进后的初始信息素浓度和重置信息素浓度的具体表达式为：  信息素发散点之后信息素的更新策略公式为：  其中ρ为信息素的挥发率，a，b为常数，控制当时间t过了信息素发散点之后的增加量和挥发量。 整个算法的流程图如下：
图 1 ：算法执行流程图 
3. 详细代码
import javafx.scene.shape.SVGPath;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
/**
* @author Jiao Tiancai
* @version 2.0
* @description: 优化信息素更新策略, 每次重置矩阵
* @date 2021-4-18 09:56
*/
public class ACO_TSP {
private float a = 1.0f;//α信息素权重，通常为1
private float b = 5.0f;//路径权重，通常为2-5
private float C = 0f;//经过贪心算法求得的一条路径的长度
private float t0 = 0.0f;//t0所有边上的信息素初始浓度为t0，根据AS的随机比例规则对信息素浓度初始化的值
private ArrayList t;//t储存信息素浓度
private float p = 0.1f;//挥发因子
private int m = 50;//蚂蚁数量
private int Q = 100;//信息素增强因子
private float Ta = 0.002f;//信息素变化率增加的系数
private float pb = 0.002f;//信息素挥发率增加的系数
private int T = 0;
private int TMax = 50;//一段时间没有变化后，就是信息素的发散点，当一段时间没有变化，那么重置
private int T0 = 0;//信息素发散点
private ArrayList citys;//城市坐标
private ArrayList distance;//两两城市之间的距离
private Random random = new Random();
private int iterMax = 800;//最大迭代次数
private int iter = 0;//迭代次数
private ArrayList antHistory = new ArrayList();
ArrayList dis;//每一个蚂蚁走的总距离
private ArrayList plotPath = new ArrayList(); //记录迭代800次后的最短距离的结果
private ArrayList antStart = new ArrayList(); ///所有蚂蚁起始位置的设置
private ArrayList pathBest = new ArrayList();
private boolean faSan = false;
private ArrayList routerBest;
private ArrayList times = new ArrayList();//用于储存十次的最短距离
private ArrayList avgIterMinDis = new ArrayList();//用于计算10次或更多结果
public ACO_TSP(float a, float b, float p, int m, int Q, ArrayList citys) {
this.a = a;//信息素因子
this.b = b;//启发因子
this.p = p;//挥发因子
this.m = m;//蚂蚁数量
this.Q = Q;//信息素增强因子
this.citys = citys;
}
public ACO_TSP(ArrayList citys) {
this.citys = citys;
}
/**
* @description: 更新城市坐标信息
* @param: [citys]
* @return: void
* @author Jiao Tiancai
* @date: 2021-4-9 22:07
*/
public static void updateLoc(List citys) throws IOException {
File file = new File("src/data/citys.txt");
if (!file.exists())
throw new RuntimeException("Not File!");
BufferedReader br = new BufferedReader(new FileReader(file));
String str = ""; //读取每一行的值
String[] Location;//每一个城市的坐标
ArrayList Loc;
while ((str = br.readLine()) != null) {
Loc = new ArrayList();
Location = str.split("\\s+");
Loc.add(Integer.parseInt(Location[0]));
Loc.add(Integer.parseInt(Location[1]));
citys.add(Loc);
}
}
/**
* @description: 贪心算法初始化一条路径, 目前已经优化成用距离的倒数乘以信息素增强因子表示信息素初始浓度
* @param: []
* @return: void
* @author Jiao Tiancai
* @date: 2021-4-9 22:39
*/
private void t_init() {
/*int firstCity = random.nextInt(citys.size());
int cityLength = citys.size();
t= new ArrayList();
ArrayList visited = new ArrayList();
visited.add(firstCity);
int j = 0;
C=0;
Float min = 9999999f;
int minIndex = firstCity;
while (visited.size() < cityLength) {//不断扩充访问到的城市
for (int i = 0; i < cityLength; i++) {//不断尝试下一个城市是不是很短
if (!visited.contains(i)) {
if (distance.get(visited.get(j)).get(i) < min) {
min = distance.get(visited.get(j)).get(i);
minIndex = i; //记录最小的城市
}
}
if (i == cityLength - 1) {
min = 99999999f;
j = j + 1;
visited.add(minIndex);
}
}
}
for (int i = 0; i < cityLength; i++) {
C += distance.get(visited.get(i)).get(visited.get((i + 1) % cityLength));
}
t0 = Q / C;*/
t = new ArrayList();
ArrayList rawT0;
for (int i = 0, cityLength = citys.size(); i
if (i == k) {
t0 = 0;
} else {
t0 = Q / distance.get(i).get(k);
}
rawT0.add(t0);
}
t.add(rawT0);
}
}
/**
* @description: 更新两两城市之间距离
* @param: []
* @return: void
* @author Jiao Tiancai
* @date: 2021-4-9 22:23
*/
private void updateDis() {
ArrayList rowDis;
distance = new ArrayList();
for (int i = 0, length = citys.size(); i
rowDis.add((float) Math.sqrt((citys.get(i).get(0) - citys.get(j).get(0))
* (citys.get(i).get(0) - citys.get(j).get(0)) +
(citys.get(i).get(1) - citys.get(j).get(1))
* (citys.get(i).get(1) - citys.get(j).get(1))));//逐行获取两两城市之间的距离
}
distance.add(rowDis);//将获取完的距离信息添加到数组中去
}
}
/**
* @description: ACO解TSP
* @param: []
* @return: void
* @author Jiao Tiancai
* @date: 2021-4-9 22:13
*/
private void solve() {
float minDis = 999999;//用于更新最短距离
updateDis();//更新城市两点之间的距离信息
t_init();//信息素浓度初始化
ArrayList antVisited; //用于记录每个蚂蚁走过的路径
ArrayList betCity;//存访问的下一个城市
ArrayList bet;//存访问下一个城市的概率
Float lastMinDis = 0f;//记录上一次的距离，用于判断最优解有多节没有更新了
plotPath = new ArrayList();
while (iter //蚂蚁（随机）或者均匀地分布在各个城市
if (i
antStart.add(random.nextInt(31));
}
}
for (int i = 0, length = citys.size(); i
betCity = new ArrayList();//存放城市j和概率p的键值对
bet = new ArrayList();
for (int j = 0; j //选择没有访问过的城市
double p = (Math.pow(t.get(antVisited.get(antVisited.size() - 1)).get(j), a)
* Math.pow(1 / distance.get(antVisited
.get(antVisited.size() - 1)).get(j), b));//计算概率
betCity.add(j);//添加城市
bet.add(p);//添加概率
}
if (j == length - 1) {
if (bet.size() == 0) {
break;
}
Double sum = 0.0;
for (int k = 0; k
bet.set(k, bet.get(k) / sum);
}
int nextCity = betCity.get(0);//轮盘赌方法选择下一个城市
if (bet.size() > 1) {
nextCity = selectNextByBet(betCity, bet);
}
antVisited.add(nextCity);
}
}
}
antHistory.add(antVisited);//m个蚂蚁构建成功
}
updateInft(antHistory, iter, T0);//更新信息素
int minIndex = 0;
boolean updataDisFlag = false;
for (int i = 1, disLength = dis.size(); i
minDis = dis.get(i);
minIndex = i;
updataDisFlag = true;
}
}
if (updataDisFlag) {
routerBest = new ArrayList();
routerBest = antHistory.get(minIndex);
}
if (lastMinDis
T++;//记录特定次数下最优路径没有更新
}
lastMinDis = minDis;
if (faSan) {
if (T > TMax) {//记录发散之后多少次解依然没变化的话，那么就重置信息素矩阵
T = 0;
faSan = false;
t_init();
p = 0.1f;
}
}
if (T > TMax) {// 次数大于指定值即到了信息素的发散点
T = 0;
T0 = iter;
p =0.1f;
faSan = true;
}
plotPath.add(minDis);
}
float sum = 0f;
for(int i=0;i
float k = 0.0f;
if (faSan) {
//k = iter - t0;
} else {
k = 0;
}
p = (pb * k + 1) * p;
if (p > 0.9) {
p = 0.9f;
}
//信息素挥发
for (int i = 0, length = citys.size(); i
t.get(i).set(j, t.get(i).get(j) * (1 - p));
}
}
dis = new ArrayList();
for (int i = 0; i
for (int j = 0, length = citys.size(); j
//System.out.println(ans);
Float dis = 0f;
int i, length;
for (i = 0, length = citys.size(); i
Double betP = Double.valueOf(random.nextFloat());
int i = 0;
int returnCity = -1;
if (bet.size() == 1) {
return betCity.get(0);
}
for (i = 0; i
returnCity = betCity.get(i);
break;
} else {
betP -= bet.get(i);
}
}
return returnCity;
}
/**
* @description: 找到最好的一条路径
* @param: [antHistory]
* @return: java.util.ArrayList
* @author Jiao Tiancai
* @date: 2021-4-17 13:00
*/
private ArrayList getBestRouter(ArrayList antHistory) {
float min = getRouteDis(antHistory.get(0));
int minIndex = 0;
float dis = 0.0f;
for (int i = 1; i
min = dis;
minIndex = i;
}
}
return antHistory.get(minIndex);
}
public static void main(String[] args) throws IOException {
//创建一个空的城市
ArrayList citys = new ArrayList();
//读取城市位置信息
ACO_TSP.updateLoc(citys);
//初始化城市距离信息
ACO_TSP aco_tsp = new ACO_TSP(1.0f, 5.0f, 0.1f, 50, 100, citys);
long startTime = System.currentTimeMillis(); //程序开始记录时间
System.out.println("正在求解~~~");
for(int i=0;i
aco_tsp.iter = 0;
aco_tsp.solve();
aco_tsp.times.add(aco_tsp.getRouteDis(aco_tsp.routerBest));
}
for (int i =0;i |