全局路径算法-蚁群算法

算法简介

蚁���算法模拟了自然界中蚂蚁的觅食行为。

蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知到其他蚂蚁的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。

通常，蚂蚁会以比较大的概率优先选择信息素浓度较高的路径，并且释放一定量的信息素，以增强该条路径上的信息素浓度，从而形成一种正反馈。最终蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短的路径。

算法流程

1、路径构建

蚂蚁对于每条路径的选择概率由以下公式计算：

对于每只蚂蚁k，路径记忆向量R^k按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。J_k(i)表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列中的城市集合。η(i, j)是一个启发式信息，通常由η (i, j)=1/d_ij直接计算。т(i, j)表示边(i, j)上的信息素量。

长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。a和b是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当a=0时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当b=0时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕。

2、信息素更新

在算法初始化时，问题空间中所有的边上的信息素都被初始化为t0。

算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。

蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。

迭代（2），直至算法终止。

算法示例

轮盘赌法：

比方说，现在A占比为0.2，B占比为0.5，C占比为0.3。

则当你随机值大小位于为0-0.2时，选A，大小位于0.2-0.7时，选B，大小位于0.7-1.0时，选C

代码实现

#include #include #include #include #include // 代表城市的结构体struct City {    int x, y; // 坐标};// 计算两个城市之间的距离double distance(const City& city1, const City& city2) {    int dx = city1.x - city2.x;    int dy = city1.y - city2.y;    return std::sqrt(dx * dx + dy * dy);}// 蚂蚁类class Ant {private:    std::vector tour; // 巡回路径    std::vector visited; // 记录已访问的城市    int currentCity; // 当前所在城市    double tourLength; // 巡回路径长度public:    Ant(int numCities) : visited(numCities, false), tourLength(0.0), currentCity(0) {        tour.push_back(0); // 初始城市为0        visited[0] = true; // 标记城市0为已访问    }    // 返回当前城市    int getCurrentCity() const {        return currentCity;    }    // 返回巡回路径长度    double getTourLength() const {        return tourLength;    }    // 返回巡回路径    const std::vector& getTour() const {        return tour;    }    // 选择下一个城市    void chooseNextCity(const std::vector& cities, const std::vector& pheromone, double alpha, double beta) {        double totalProbability = 0.0;        std::vector probabilities(cities.size(), 0.0);        // 计算每个未访问城市的选择概率        for (int i = 0; i = randomValue) {                tour.push_back(i);                tourLength += distance(cities[currentCity], cities[i]);                visited[i] = true;                currentCity = i;                break;            }        }    }    // 计算巡回路径长度    void computeTourLength(const std::vector& cities) {        tourLength += distance(cities[currentCity], cities[0]); // 返回起始城市    }};// 更新信息素void updatePheromone(std::vector& pheromone, const std::vector& ants, double evaporationRate, double Q) {    // 信息素挥发    for (auto& row : pheromone) {        for (double& val : row) {            val *= (1 - evaporationRate);        }    }    // 信息素增加    for (const auto& ant : ants) {        const std::vector& tour = ant.getTour();        double tourLength = ant.getTourLength();        for (int i = 0; i