当前位置：首页 > JavaScript

蚁群算法js实现

2026-01-31 01:53:19JavaScript

蚁群算法简介

蚁群算法（Ant Colony Optimization, ACO）是一种模拟蚂蚁觅食行为的启发式算法，常用于解决组合优化问题（如旅行商问题TSP）。蚂蚁通过信息素（pheromone）标记路径，其他蚂蚁倾向于选择信息素浓度高的路径，最终找到最优解。

蚁群算法核心步骤

初始化参数
- 蚂蚁数量、迭代次数、信息素挥发系数、信息素重要程度因子（α）、启发函数重要程度因子（β）。
- 初始化信息素矩阵和距离矩阵。
构建路径
- 每只蚂蚁根据信息素浓度和启发式信息（如距离倒数）选择下一个节点，直到完成完整路径。
更新信息素
- 信息素挥发：所有路径的信息素按一定比例减少。
- 信息素增强：蚂蚁在其经过的路径上释放信息素，路径越短释放越多。
迭代优化
- 重复构建路径和更新信息素，直到达到最大迭代次数或收敛。

JavaScript实现示例（以TSP为例）

class AntColonyOptimization {
  constructor(distanceMatrix, antsCount = 10, iterations = 100, alpha = 1, beta = 2, evaporation = 0.5) {
    this.distanceMatrix = distanceMatrix; // 城市间距离矩阵
    this.antsCount = antsCount;          // 蚂蚁数量
    this.iterations = iterations;        // 迭代次数
    this.alpha = alpha;                  // 信息素重要程度
    this.beta = beta;                    // 启发式信息重要程度
    this.evaporation = evaporation;      // 信息素挥发率
    this.pheromone = Array(distanceMatrix.length).fill()
      .map(() => Array(distanceMatrix.length).fill(1)); // 初始化信息素矩阵
  }

  // 蚂蚁选择下一个城市
  selectNextCity(ant, visited) {
    const currentCity = ant.path[ant.path.length - 1];
    const unvisited = this.distanceMatrix.map((_, i) => i)
      .filter(i => !visited.has(i));

    // 计算转移概率
    const probabilities = unvisited.map(city => {
      const pheromone = Math.pow(this.pheromone[currentCity][city], this.alpha);
      const distance = 1 / this.distanceMatrix[currentCity][city];
      const heuristic = Math.pow(distance, this.beta);
      return pheromone * heuristic;
    });

    // 轮盘赌选择
    const sum = probabilities.reduce((a, b) => a + b, 0);
    const normalized = probabilities.map(p => p / sum);
    let random = Math.random();
    let index = 0;
    while (random > normalized[index]) {
      random -= normalized[index];
      index++;
    }
    return unvisited[index];
  }

  // 单次迭代
  runIteration() {
    const ants = Array(this.antsCount).fill().map(() => ({ path: [Math.floor(Math.random() * this.distanceMatrix.length)] }));
    let bestPath = null;
    let bestLength = Infinity;

    // 每只蚂蚁构建路径
    ants.forEach(ant => {
      const visited = new Set(ant.path);
      while (visited.size < this.distanceMatrix.length) {
        const nextCity = this.selectNextCity(ant, visited);
        ant.path.push(nextCity);
        visited.add(nextCity);
      }
      // 计算路径长度
      const length = ant.path.reduce((sum, city, i) => 
        sum + (i === 0 ? 0 : this.distanceMatrix[ant.path[i - 1]][city]), 0);
      if (length < bestLength) {
        bestLength = length;
        bestPath = [...ant.path];
      }
    });

    // 更新信息素
    this.pheromone = this.pheromone.map(row => row.map(val => val * this.evaporation));
    ants.forEach(ant => {
      const length = ant.path.reduce((sum, city, i) => 
        sum + (i === 0 ? 0 : this.distanceMatrix[ant.path[i - 1]][city]), 0);
      const pheromoneDelta = 1 / length;
      for (let i = 1; i < ant.path.length; i++) {
        const from = ant.path[i - 1];
        const to = ant.path[i];
        this.pheromone[from][to] += pheromoneDelta;
        this.pheromone[to][from] += pheromoneDelta; // 对称路径
      }
    });

    return { bestPath, bestLength };
  }

  // 主函数
  solve() {
    let globalBestPath = null;
    let globalBestLength = Infinity;
    for (let i = 0; i < this.iterations; i++) {
      const { bestPath, bestLength } = this.runIteration();
      if (bestLength < globalBestLength) {
        globalBestLength = bestLength;
        globalBestPath = bestPath;
      }
    }
    return { path: globalBestPath, length: globalBestLength };
  }
}

// 示例：4个城市的TSP问题
const distanceMatrix = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
];
const aco = new AntColonyOptimization(distanceMatrix);
const result = aco.solve();
console.log("最优路径:", result.path, "长度:", result.length);