蚁群算法

C++版本的蚁群算法

话不多说，先上源码

#include <graphics.h>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <limits>
#include <thread>
#include <random>
#include <windows.h> // 用于 GetAsyncKeyState

const int CITY_NUM = 50;
const int ANT_NUM = 50;
const double ALPHA = 1.0;
const double BETA = 2.0;
const double RHO = 0.5;
const double Q = 100.0;
const int WIDTH = 800;
const int HEIGHT = 600;

std::vector<int> distance_x = { 178, 272, 176, 171, 650, 499, 267, 703, 408, 437, 491, 74, 532, 416, 626, 42, 271, 359,
                                163, 508, 229, 576, 147, 560, 35, 714, 757, 517, 64, 314, 675, 690, 391, 628, 87, 240, 
                                705, 699, 258, 428, 614, 36, 360, 482, 666, 597, 209, 201, 492, 294 };

std::vector<int> distance_y = { 170, 395, 198, 151, 242, 556, 57, 401, 305, 421, 267, 105, 525, 381, 244, 330, 395, 169,
                                141, 380, 153, 442, 528, 329, 232, 48, 498, 265, 343, 120, 165, 50, 433, 63, 491, 275, 
                                348, 222, 288, 490, 213, 524, 244, 114, 104, 552, 70, 425, 227, 331 };

//距离
//长：CITY_NUM, 宽：CITY_NUM,存储的0.0
std::vector<std::vector<double>> distance_graph(CITY_NUM, std::vector<double>(CITY_NUM, 0.0));

//信息素
std::vector<std::vector<double>> pheromone_graph(CITY_NUM, std::vector<double>(CITY_NUM, 1.0));


class Ant {
public:
    Ant(int ID) : ID(ID) 
    {
        clean_data();
    }

    void search_path() 
    {
        clean_data();
        while (move_count < CITY_NUM) 
        {
            int next_city = choice_next_city();
            move(next_city);
        }

        cal_total_distance();
    }

    double get_total_distance() const 
    {
        return total_distance;
    }

    const std::vector<int>& get_path() const 
    {
        return path;
    }

private:
    void clean_data() {
        path.clear();                   // 清空路径向量，通常用于存储访问过的城市或节点序列
        total_distance = 0.0;           //总距离重置为0
        move_count = 0;                 //重置移动计数为0
        current_city = -1;              //当前城市重置为-1，即未选择任何城市
        open_table_city.assign(CITY_NUM, true);//所有城市设为可访问状态

        int city_index = rand() % CITY_NUM;
        current_city = city_index;      //任选一个城市作为起点
        path.push_back(city_index);
        open_table_city[city_index] = false;
        move_count = 1;                 //移动计数加1
    }

    int choice_next_city() {
        int next_city = -1;

        std::vector<double> select_citys_prob(CITY_NUM, 0.0);//选择城市的概率

        double total_prob = 0.0;

        for (int i = 0; i < CITY_NUM; ++i) {
            if (open_table_city[i]) {
                select_citys_prob[i] = pow(pheromone_graph[current_city][i], ALPHA) 
                    * pow((1.0 / distance_graph[current_city][i]), BETA);
                total_prob += select_citys_prob[i];
            }
        }

        //用轮盘赌算法选择下一个城市
        if (total_prob > 0.0) {
            double temp_prob = (double)rand() / RAND_MAX * total_prob;//temp_prob在[0,total_prob]

            //每个城市的选择概率正比于其在总概率中所占的比例，所以每个城市被选中的概率与其选择概率一致
            for (int i = 0; i < CITY_NUM; ++i) {
                if (open_table_city[i]) 
                {
                    temp_prob -= select_citys_prob[i];
                    
                    if (temp_prob < 0.0) {
                        next_city = i;
                        break;
                    }
                }
            }
        }

        //如果未选择城市，则随机选择一个城市，直到选到可以访问的为止
        if (next_city == -1) {
            do 
            {
                next_city = rand() % CITY_NUM;
            } while (!open_table_city[next_city]);
        }

        return next_city;
    }

    void move(int next_city) 
    {
        path.push_back(next_city);
        open_table_city[next_city] = false;
        total_distance += distance_graph[current_city][next_city];
        current_city = next_city;
        move_count++;
    }

    void cal_total_distance() 
    {
        total_distance = 0.0;

        for (int i = 1; i < CITY_NUM; ++i) {
            int start = path[i - 1];
            int end = path[i];
            total_distance += distance_graph[start][end];
        }

        // 添加路径上最后一个城市到第一个城市的距离，形成闭合路径
        total_distance += distance_graph[path.back()][path.front()];
    }

    int ID;
    std::vector<int> path;
    double total_distance;
    int move_count;
    int current_city;
    std::vector<bool> open_table_city;
};

class TSP {
public:
    TSP() : best_ant(-1), iter(1) 
    {
        best_ant.search_path();
        calculate_distance_graph();
    }

    void search_path() {
        while (running) 
        {
            for (auto& ant : ants) 
            {
                ant.search_path();

                if (ant.get_total_distance() < best_ant.get_total_distance()) {
                    best_ant = ant;
                }
            }

            update_pheromone_graph();
            std::cout << "Iteration: " << iter << " Best Distance: " << best_ant.get_total_distance() << std::endl;
            iter++;
        }
    }

    void draw() 
    {
        cleardevice();

        for (size_t i = 0; i < CITY_NUM; ++i) 
        {
            setfillcolor(RGB(51, 255, 250));
            fillcircle(distance_x[i], distance_y[i], 5);
        }

        const auto& path = best_ant.get_path();

        for (size_t i = 1; i < CITY_NUM; ++i) 
        {
            setcolor(RGB(255, 255, 0));
            setfillcolor(RGB(255, 255, 0));
            line(distance_x[path[i - 1]], distance_y[path[i - 1]], distance_x[path[i]], distance_y[path[i]]);
        }

        line(distance_x[path.back()], distance_y[path.back()], distance_x[path.front()], distance_y[path.front()]);

        setcolor(RGB(255, 0, 0));
        setfillcolor(RGB(255, 0, 0));
        fillcircle(distance_x[path.front()], distance_y[path.front()], 5);  // 起始点
        fillcircle(distance_x[path.back()], distance_y[path.back()], 5);    // 终点

        FlushBatchDraw();
    }

    void start() {
        running = true;
        ants = std::vector<Ant>(ANT_NUM, Ant(0));//指定ant个数
        best_ant = Ant(-1);
        best_ant.search_path();
        search_thread = std::thread(&TSP::search_path, this);
    }

    void stop() {
        running = false;
        if (search_thread.joinable()) 
        {
            search_thread.join();
        }
    }

private:
    //初始化distcance_graph
    void calculate_distance_graph() 
    {
        for (int i = 0; i < CITY_NUM; ++i) {
            for (int j = 0; j < CITY_NUM; ++j) {
                double temp_distance = std::sqrt(std::pow(distance_x[i] - distance_x[j], 2) 
                    + std::pow(distance_y[i] - distance_y[j], 2));
                distance_graph[i][j] = temp_distance;
            }
        }
    }

    //更新信息素图
    void update_pheromone_graph() {
        std::vector<std::vector<double>> temp_pheromone(CITY_NUM, std::vector<double>(CITY_NUM, 0.0));

        for (const auto& ant : ants) {
            for (size_t i = 1; i < CITY_NUM; ++i) 
            {
                int start = ant.get_path()[i - 1];
                int end = ant.get_path()[i];
                temp_pheromone[start][end] += Q / ant.get_total_distance();
                temp_pheromone[end][start] = temp_pheromone[start][end];
            }
        }

        for (int i = 0; i < CITY_NUM; ++i) 
        {
            for (int j = 0; j < CITY_NUM; ++j) 
            {
                pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j];
            }
        }
    }

    std::vector<Ant> ants;
    Ant best_ant;
    int iter;
    bool running = false;
    std::thread search_thread;
};

int main() {
    srand(static_cast<unsigned int>(time(nullptr)));//用时间设置随机数种子
    initgraph(WIDTH, HEIGHT);
    BeginBatchDraw();

    TSP tsp;
    tsp.start();

    while (true) 
    {
        if (GetAsyncKeyState('Q') & 0x8000) 
        { // 检测 'Q' 键是否被按下
            tsp.stop();
            break;
        }

        tsp.draw();
        Sleep(10);
    }

    EndBatchDraw();
    closegraph();
    return 0;
}

“怎么那么多啊!?”
“请看图”