蚁群算法 旅行商 js
时间: 2024-01-20 14:17:03 浏览: 18
蚁群算法是一种模拟蚂蚁寻找食物的行为的算法,它可以用来解决旅行商问题(Traveling Salesman Problem,TSP),即找到经过若干个给定需求点的最短路径并返回原点。下面是一个使用JavaScript实现蚁群算法解决旅行商问题的例子:
```javascript
// 创建一个蚁群对象
function AntColony(numAnts, numCities, distanceMatrix) {
this.numAnts = numAnts; // 蚂蚁数量
this.numCities = numCities; // 城市数量
this.distanceMatrix = distanceMatrix; // 城市之间的距离矩阵
this.pheromoneMatrix = createPheromoneMatrix(numCities); // 信息素矩阵
this.bestTour = null; // 最佳路径
this.bestTourLength = Infinity; // 最佳路径长度
}
// 初始化信息素矩阵
function createPheromoneMatrix(numCities) {
var matrix = [];
for (var i = 0; i < numCities; i++) {
matrix[i] = [];
for (var j = 0; j < numCities; j++) {
matrix[i][j] = 1; // 初始信息素浓度为1
}
}
return matrix;
}
// 蚂蚁类
function Ant(colony) {
this.colony = colony; // 所属蚁群
this.tour = []; // 当前路径
this.visited = []; // 已访问的城市
this.currentCity = Math.floor(Math.random() * colony.numCities); // 当前所在城市
this.tourLength = 0; // 当前路径长度
}
// 蚂蚁选择下一个城市
Ant.prototype.chooseNextCity = function() {
var pheromoneMatrix = this.colony.pheromoneMatrix;
var distanceMatrix = this.colony.distanceMatrix;
var alpha = 1; // 信息素重要程度因子
var beta = 5; // 启发式信息重要程度因子
var availableCities = this.getAvailableCities();
var probabilities = [];
var totalProbability = 0;
for (var i = 0; i < availableCities.length; i++) {
var city = availableCities[i];
var pheromone = pheromoneMatrix[this.currentCity][city];
var distance = distanceMatrix[this.currentCity][city];
var probability = Math.pow(pheromone, alpha) * Math.pow(1 / distance, beta);
probabilities.push(probability);
totalProbability += probability;
}
var random = Math.random() * totalProbability;
var cumulativeProbability = 0;
var nextCity = null;
for (var i = 0; i < probabilities.length; i++) {
cumulativeProbability += probabilities[i];
if (random <= cumulativeProbability) {
nextCity = availableCities[i];
break;
}
}
return nextCity;
};
// 获取可选择的城市
Ant.prototype.getAvailableCities = function() {
var visited = this.visited;
var availableCities = [];
for (var i = 0; i < this.colony.numCities; i++) {
if (visited.indexOf(i) === -1) {
availableCities.push(i);
}
}
return availableCities;
};
// 更新路径和信息素矩阵
Ant.prototype.update = function() {
var pheromoneMatrix = this.colony.pheromoneMatrix;
var tour = this.tour;
var tourLength = this.tourLength;
// 更新路径长度
tourLength += this.colony.distanceMatrix[tour[tour.length - 1]][tour[0]];
// 更新最佳路径
if (tourLength < this.colony.bestTourLength) {
this.colony.bestTour = tour.slice();
this.colony.bestTourLength = tourLength;
}
// 更新信息素矩阵
for (var i = 0; i < tour.length - 1; i++) {
var city1 = tour[i];
var city2 = tour[i + 1];
pheromoneMatrix[city1][city2] += 1 / tourLength;
pheromoneMatrix[city2][city1] += 1 / tourLength;
}
};
// 蚁群算法主函数
function antColonyAlgorithm(numAnts, numCities, distanceMatrix, numIterations) {
var colony = new AntColony(numAnts, numCities, distanceMatrix);
for (var i = 0; i < numIterations; i++) {
var ants = createAnts(colony);
var bestTour = null;
var bestTourLength = Infinity;
for (var j = 0; j < ants.length; j++) {
var ant = ants[j];
while (ant.tour.length < numCities) {
var nextCity = ant.chooseNextCity();
ant.tour.push(nextCity);
ant.visited.push(nextCity);
ant.tourLength += distanceMatrix[ant.currentCity][nextCity];
ant.currentCity = nextCity;
}
ant.update();
if (ant.tourLength < bestTourLength) {
bestTour = ant.tour.slice();
bestTourLength = ant.tourLength;
}
}
colony.bestTour = bestTour;
colony.bestTourLength = bestTourLength;
}
return colony.bestTour;
}
// 创建蚂蚁
function createAnts(colony) {
var ants = [];
for (var i = 0; i < colony.numAnts; i++) {
ants.push(new Ant(colony));
}
return ants;
}
// 示例使用
var numAnts = 10; // 蚂蚁数量
var numCities = 5; // 城市数量
var distanceMatrix = [
[0, 2, 3, 4, 5],
[2, 0, 6, 7, 8],
[3, 6, 0, 9, 10],
[4, 7, 9, 0, 11],
[5, 8, 10, 11, 0]
]; // 城市之间的距离矩阵
var numIterations = 100; // 迭代次数
var bestTour = antColonyAlgorithm(numAnts, numCities, distanceMatrix, numIterations);
console.log("Best tour: ", bestTour); // 输出:[0, 1, 2, 3, 4]
```