使用遗传算法解决旅行商问题

旅行商问题 (TSP) 旨在找到连接一系列城市并返回起点的最短路径。由于其组合性质以及随着城市数量增加而呈指数级增长的路径数量，这是一个难题。遗传算法 (GA) 是一种受遗传学启发的启发式算法。它模拟自然选择来有效地解决 TSP 问题。GA 使用路径来表示城市巡游的候选方案。选择、交叉和变异在 GA 中进化种群。选择偏向适应性更高的路径，这表示其质量或接近理想解的程度。变异引入随机修改以探索新的解空间，而交叉则混合来自父路径的遗传信息以产生子代。

使用的方法

  • 遗传算法

遗传算法

强大的启发式遗传算法 (GA) 受到自然选择和遗传学的启发。它模仿进化来有效地解决 TSP 问题。GA 中的每条路径都是一个可能的解决方案。适应度决定了路径的质量和最优性。GA 通过选择、交叉和变异适应度值较高的路径来发展新的种群。

算法

  • 定义城市、最大世代数、种群大小和变异率。

  • 定义一个城市结构，包含 x 和 y 坐标。

  • 定义一个路径结构，包含城市索引向量（路径）和适应度值。

  • 创建一个使用坐标确定城市距离的方法。

  • 创建一个通过交换城市索引来创建随机路径的函数。

  • 创建一个对城市距离求和以计算路径适应度的函数。

  • 创建一个将两条父路径交叉以创建子路径的函数。

  • 通过基于变异率的函数交换城市来变异路径。

  • 实现一个基于适应度的路径查找工具。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

// Define the number of cities
const int NUM_CITIES = 5;

// Define the maximum generations for the GA
const int MAX_GENERATIONS = 100;

// Define the population size for the GA
const int POPULATION_SIZE = 10;

// Define the mutation rate for the GA
const double MUTATION_RATE = 0.1;

// Define a structure to represent a city
struct City {
    int x;
    int y;
};

// Define a structure to represent a route
struct Route {
    vector<int> path;
    double fitness;
};

// Calculate the distance between two cities
double calculateDistance(const City& city1, const City& city2) {
    int dx = city1.x - city2.x;
    int dy = city1.y - city2.y;
    return sqrt(dx*dx + dy*dy);
}

// Generate a random route
Route generateRandomRoute() {
    Route route;
    for (int i = 0; i < NUM_CITIES; ++i) {
        route.path.push_back(i);
    }
    random_shuffle(route.path.begin(), route.path.end());
    return route;
}

// Calculate the fitness of a route (smaller distance is better)
void calculateFitness(Route& route, const vector<City>& cities) {
    double totalDistance = 0.0;
    for (int i = 0; i < NUM_CITIES - 1; ++i) {
        int cityIndex1 = route.path[i];
        int cityIndex2 = route.path[i+1];
        totalDistance += calculateDistance(cities[cityIndex1], cities[cityIndex2]);
    }
    // Add distance from last city back to the starting city
    int lastCityIndex = route.path[NUM_CITIES - 1];
    totalDistance += calculateDistance(cities[lastCityIndex], cities[route.path[0]]);
    route.fitness = totalDistance;
}

// Perform crossover between two parent routes to produce a child route
Route crossover(const Route& parent1, const Route& parent2) {
    Route child;
    int startPos = rand() % NUM_CITIES;
    int endPos = rand() % NUM_CITIES;

    for (int i = 0; i < NUM_CITIES; ++i) {
        if (startPos < endPos && i > startPos && i < endPos) {
            child.path.push_back(parent1.path[i]);
        }
        else if (startPos > endPos && !(i < startPos && i > endPos)) {
            child.path.push_back(parent1.path[i]);
        }
        else {
            child.path.push_back(-1);
        }
    }

    for (int i = 0; i < NUM_CITIES; ++i) {
        if (find(child.path.begin(), child.path.end(), parent2.path[i]) == child.path.end()) {
            for (int j = 0; j < NUM_CITIES; ++j) {
                if (child.path[j] == -1) {
                    child.path[j] = parent2.path[i];
                    break;
                }
            }
        }
    }

    return child;
}

// Mutate a route by swapping two cities
void mutate(Route& route) {
    for (int i = 0; i < NUM_CITIES; ++i) {
        if ((double)rand() / RAND_MAX < MUTATION_RATE) {
            int swapIndex = rand() % NUM_CITIES;
            swap(route.path[i], route.path[swapIndex]);
        }
    }
}

// Find the best route in a population
Route findBestRoute(const vector<Route>& population) {
    double bestFitness = numeric_limits<double>::max();
    int bestIndex = -1;
    for (int i = 0; i < POPULATION_SIZE; ++i) {
        if (population[i].fitness < bestFitness) {
            bestFitness = population[i].fitness;
            bestIndex = i;
        }
    }
    return population[bestIndex];
}

int main() {
    // Define the cities
    vector<City> cities = {
        {0, 0},
        {1, 2},
        {3, 1},
        {4, 3},
        {2, 4}
    };

    // Initialize the population
    vector<Route> population;
    for (int i = 0; i < POPULATION_SIZE; ++i) {
        population.push_back(generateRandomRoute());
        calculateFitness(population[i], cities);
    }

    // Perform the GA iterations
    for (int generation = 0; generation < MAX_GENERATIONS; ++generation) {
        vector<Route> newPopulation;

        // Generate offspring through selection, crossover, and mutation
        for (int i = 0; i < POPULATION_SIZE; ++i) {
            Route parent1 = findBestRoute(population);
            Route parent2 = findBestRoute(population);
            Route child = crossover(parent1, parent2);
            mutate(child);
            calculateFitness(child, cities);
            newPopulation.push_back(child);
        }

        // Replace the old population with the new population
        population = newPopulation;
    }

    // Find the best route
    Route bestRoute = findBestRoute(population);

    // Print the best route
    cout << "Best Route: ";
    for (int i = 0; i < NUM_CITIES; ++i) {
        cout << bestRoute.path[i] << " ";
    }
    cout << endl;

    // Print the total distance of the best route
    cout << "Total Distance: " << bestRoute.fitness << endl;

    return 0;
}

输出

Best Route: 2 3 4 1 0 
Total Distance: 12.1065

结论

最后，遗传算法 (GA) 可以解决旅行商问题 (TSP) 和其他组合优化问题。GA 迭代地搜索可行解的广阔搜索空间，利用遗传学和进化概念改进路径适应度并找到一个良好的解。GA 对 TSP 的处理平衡了探索和利用。通过选择、交叉和变异，GA 促进了更好路径的发展并保持种群多样性。GA 可以有效地搜索解空间并避免局部最优解。

更新于：2023年7月14日

4K+ 浏览量

开启您的职业生涯

完成课程获得认证

开始学习
广告