- 代码
- Ant蚂蚁类
- AntColonyOptimization_TSP蚁群算法类
- 运行结果
代码 Ant蚂蚁类
import lombok.Data;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
@Data
public class Ant implements Cloneable {
// 禁忌表
private HashMap tabu;
// 允许搜索的城市
private List allowedCities;
// 信息素变化矩阵
private double[][] delta;
// 距离矩阵
private double[][] distance;
private double alpha;
private double beta;
// 路径长度
private int tourLength;
// 城市数量
private int cityNum;
// 起始城市
private int firstCity;
// 当前城市
private int currentCity;
// 构造函数
public Ant(int cityNum) {
this.cityNum = cityNum;
this.tourLength = 0;
}
// 初始化
public void initAnt(double[][] distance, double a, double b) {
alpha = a;
beta = b;
// 初始允许搜索的城市集合
allowedCities = new ArrayList<>();
// 初始禁忌表
tabu = new HashMap<>();
// 初始距离矩阵
this.distance = distance;
// 初始信息数变化矩阵为0
delta = new double[cityNum][cityNum];
for (int i = 0; i < cityNum; i++) {
Integer integer = i;
allowedCities.add(integer);
for (int j = 0; j < cityNum; j++) {
delta[i][j] = 0.f;
}
}
// 设置起始城市
Random random = new Random(System.currentTimeMillis());
firstCity = random.nextInt(cityNum); // 随机选取第一个城市
// 允许搜索的城市集合中移除起始城市
for (Integer i : allowedCities) {
if (i == firstCity) {
allowedCities.remove(i);
break;
}
}
// 将起始城市添加至禁忌表
tabu.put(tabu.size(), firstCity);
// 当前城市为起始城市
currentCity = firstCity;
}
//选择下一个城市
public void selectNextCity(double[][] pheromone) {
double[] p = new double[cityNum];
double sum = 0d;
// 计算分母部分
for (Integer i : allowedCities) {
sum += Math.pow(pheromone[currentCity][i], alpha)
* Math.pow(1.0 / distance[currentCity][i], beta);
}
// 计算概率矩阵
for (int i = 0; i < cityNum; i++) {
boolean flag = false;
for (Integer j : allowedCities) {
if (i == j) {
p[i] = (double) (Math.pow(pheromone[currentCity][i], alpha) * Math
.pow(1.0 / distance[currentCity][i], beta)) / sum;
flag = true;
break;
}
}
if (!flag) {
p[i] = 0.f;
}
}
// 轮盘赌选择下一个城市
Random random = new Random();
double sleectP = random.nextDouble();
int selectCity = 0;
double sum1 = 0d;
for (int i = 0; i < cityNum; i++) {
sum1 += p[i];
if (sum1 >= sleectP) {
selectCity = i;
break;
}
}
// 从允许选择的城市中去除select city
for (Integer i : allowedCities) {
if (i == selectCity) {
allowedCities.remove(i);
break;
}
}
// 在禁忌表中添加select city
tabu.put(tabu.size(), selectCity);
// 将当前城市改为选择的城市
currentCity = selectCity;
}
//计算路径长度
public double calculateTourLength() {
double len = 0.0;
//禁忌表tabu最终形式:起始城市,城市1,城市2...城市n,起始城市
for (int i = 0; i < cityNum; i++) {
len += distance[this.tabu.get(i)][this.tabu.get(i + 1)];
}
return len;
}
//获取路径长度
public double getTourLength() {
return calculateTourLength();
}
}
AntColonyOptimization_TSP蚁群算法类
import lombok.Data;
import java.util.Arrays;
import java.util.List;
@Data
public class AntColonyOptimization_TSP {
public Ant[] ants; // 蚂蚁数组
public int antNum = 15; // 蚂蚁数量
public int cityNum; // 城市数量
public int MAX_GEN = 500; // 运行代数
public double[][] pheromone; // 信息素矩阵
public double[][] distance; // 距离矩阵
public double bestLength; // 最佳长度
public int[] bestTour; // 最佳路径
public int bestT; //最佳迭代数
public List locationList;
// 三个参数
private double alpha = 1; //信息素重要程度
private double beta = 5; //启发式因子重要程度
private double rho = 0.5; //信息素挥发速率
//构造函数
public AntColonyOptimization_TSP(List locationList) {
this.locationList = locationList;
cityNum = locationList.size();
ants = new Ant[antNum];
}
//外部调用窗口
public void solve() {
initVar();
solver();
}
//
public void solver() {
// 迭代MAX_GEN次
for (int g = 0; g < MAX_GEN; g++) {
// antNum只蚂蚁
for (int i = 0; i < antNum; i++) {
// i这只蚂蚁走cityNum步,完整一个TSP
for (int j = 1; j < cityNum; j++) {
ants[i].selectNextCity(pheromone);
}
// 把这只蚂蚁起始城市加入其禁忌表中
// 禁忌表最终形式:起始城市,城市1,城市2...城市n,起始城市
ants[i].getTabu().put(ants[i].getTabu().size(), ants[i].getFirstCity());
// 查看这只蚂蚁行走路径距离是否比当前距离优秀
if (ants[i].getTourLength() < bestLength) {
// 比当前优秀则拷贝优秀TSP路径
bestLength = ants[i].getTourLength();
for (int k = 0; k < cityNum + 1; k++) {
bestTour[k] = ants[i].getTabu().get(k);
}
bestT = g;
}
// 更新这只蚂蚁的信息数变化矩阵,对称矩阵
for (int j = 0; j < cityNum; j++) {
ants[i].getDelta()[ants[i].getTabu().get(j)][ants[i]
.getTabu().get(j + 1)] = (double) (1.0 / ants[i]
.getTourLength());
ants[i].getDelta()[ants[i].getTabu().get(j + 1)][ants[i]
.getTabu().get(j)] = (1.0 / ants[i]
.getTourLength());
}
}
// 更新信息素
updatePheromone();
// 重新初始化蚂蚁
for (int i = 0; i < antNum; i++) {
ants[i].initAnt(distance, alpha, beta);
}
}
// 输出结果
System.out.println("最佳迭代次数:" + bestT);
System.out.println("最短路程为:" + bestLength);
int[] bestPath = new int[cityNum + 1];
System.arraycopy(bestTour, 0, bestPath, 0, bestTour.length);
bestPath[cityNum] = bestPath[0];
System.out.println("最佳路径为:" + Arrays.toString(bestPath));
}
//初始化
public void initVar() {
//初始化距离矩阵
distance = new double[cityNum][cityNum];
for (int i = 0; i < cityNum; i++) {
for (int j = i; j < cityNum; j++) {
if (i == j) {
distance[i][j] = 0.0;
} else {
distance[i][j] = getDistance(locationList.get(i), locationList.get(j));
distance[j][i] = distance[i][j];
}
}
}
//初始化信息素矩阵
pheromone = new double[cityNum][cityNum];
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
pheromone[i][j] = 0.1; // 初始化为0.1
}
}
bestLength = Integer.MAX_VALUE;
bestTour = new int[cityNum + 1];
// 放置蚂蚁
for (int i = 0; i < antNum; i++) {
ants[i] = new Ant(cityNum);
ants[i].initAnt(distance, alpha, beta);
}
}
// 更新信息素
private void updatePheromone() {
// 信息素挥发
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
pheromone[i][j] = pheromone[i][j] * (1 - rho);
}
}
// 信息素更新
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
for (int k = 0; k < antNum; k++) {
pheromone[i][j] += ants[k].getDelta()[i][j];
}
}
}
}
//计算两点之间的距离(如果使用伪欧氏距离,可以减少计算量)
public double getDistance(double[] place1, double[] place2) {
//伪欧氏距离在根号内除以了一个10
return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2))/10.0);
// return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)));
}
}
运行结果
蚁群算法求解tsp问题:48个城市... 最佳迭代次数:156 最短路程为(伪欧氏距离):11107.778186984036 最佳路径为:[46, 12, 24, 13, 22, 10, 11, 14, 45, 32, 19, 16, 42, 26, 18, 36, 5, 29, 35, 27, 6, 17, 43, 30, 37, 7, 0, 8, 39, 2, 21, 15, 40, 33, 47, 4, 28, 1, 25, 3, 34, 44, 9, 41, 23, 31, 38, 20, 46] 求解用时:2.885 s ------------------------------------------------------------------------- 蚁群算法求解tsp问题:48个城市... 最佳迭代次数:44 最短路程为(欧氏距离):35156.69540961502 最佳路径为:[39, 8, 37, 30, 43, 17, 6, 27, 35, 29, 5, 36, 18, 26, 42, 16, 19, 32, 45, 14, 11, 10, 22, 13, 24, 12, 46, 20, 31, 38, 47, 4, 41, 9, 23, 44, 34, 3, 25, 1, 28, 40, 33, 2, 21, 15, 0, 7, 39] 求解用时:2.781 s -------------------------------------------------------------------------
补充:以上使用的是tsplib上的数据att48,这是一个对称TSP问题,城市规模为48,其最优值为10628(伪欧氏距离)。tsplib地址:http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/



