Implementation of Genetic Algorithm for the Traveling Salesman Problem

We choose the classic case of the genetic algorithm—the Traveling Salesman Problem—to introduce the specific implementation of the genetic algorithm.

Traveling Salesman Problem#

Given a series of cities and the distances between each pair of cities, solve for the shortest route that visits each city once and returns to the starting city.

We will assign a coordinate to each city to calculate the distance between each pair of cities. For graph-related problems, the Floyd algorithm can be used to process the graph to obtain the shortest path between each pair of cities.

Global Constants and Variable Definitions#

const int SIZE = 1000, CNT = 1000; // Population size and maximum generations
using Pos = pair<double, double>; // Coordinate type
using Rst = vector<int>; // Chromosome type
vector<Pos> a; // City coordinate array
double ans = 1e9; // Global optimal solution, initialized to a large length that is impossible to reach
Rst ans_rst; // Chromosome corresponding to this solution
double notans = 1e9; // Current population optimal solution (so it's not the answer)
double geneSum = 0; // Sum of all solutions participating in the binary tournament in the current population
int geneCnt = 0; // Number of individuals participating in the binary tournament in the current population, seems to remain unchanged
// The above two lines are used to calculate the average solution of the population to observe population changes

Utility Functions#

// Get a random float, 0~1
double randf() {
    return static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
}
// Distance between two points
double getDis(Pos p1, Pos p2) {
    return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
}

Main Process#

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        double tx, ty;
        scanf("%lf%lf", &tx, &ty);
        a.push_back(make_pair(tx, ty));
    }
    // The above is the data input part
    // The entire population
    vector<Rst> pool; 
    // Generate random chromosomes
    for (int i = 1; i <= SIZE; ++i)
        pool.push_back(randGene(n));
    // Perform CNT generations of reproduction
    for (int i = 1; i <= CNT; ++i) {
        // Initialize statistics for this round
        notans = 1e9;
        geneSum = 0;
        geneCnt = 0;
        printf("%d ", i);
        // Fitness array
        vector<double> score;
        // New population
        vector<Rst> new_pool;
        for (int i = 1; i <= CNT / 2; ++i) {
            // Select two parents
            auto win1 = choose(pool);
            auto win2 = choose(pool);
            // 20% chance to perform crossover
            if (randf() < 0.2) {
                auto children = oxCross(win1, win2);
                win1 = children.first;
                win2 = children.second;
            }
            // Attempt mutation, 1% chance of mutation
            bianYi(win1);
            bianYi(win2);
            // Insert into the new population
            new_pool.push_back(win1);
            new_pool.push_back(win2);
        }
        // Output results for this round
        printf("%lf %lf %lf\n", ans, notans, geneSum / geneCnt);
        // Population change
        pool = new_pool;
    }
    // Output the chromosome of the optimal solution
    for (int v : ans_rst)
        printf("%d ", v);
    return 0;
}

Gene Encoding and Generation#

We use the order in which the traveling salesman visits the cities as the gene encoding, where the chromosome is a decimal sequence of length equal to the number of cities.

// Randomly generate a chromosome
Rst randGene(int n) {
    Rst ret;
    unordered_map<int, bool> mp;
    for (int i = 1; i <= n; ++i) {
        int newr = rand() % n;
        while (mp[newr])
            newr = rand() % n;
        ret.push_back(newr);
        mp[newr] = true;
    }
    return ret;
}

Fitness Evaluation#

The inverse of the total distance is taken as the fitness. The total fitness produced by this method does not equal 1.

// Total distance traveled
double getValue(Rst &g) {
    int len = g.size();
    double s = 0;
    for (int i = 1; i < len; ++i)
        s += getDis(a[g[i - 1]], a[g[i]]);
    s += getDis(a[g[0]], a[g[len - 1]]);
    if (s < ans) {
        ans = s;
        ans_rst = g;
    }
    if (s < notans)
        notans = s;
    geneSum += s;
    geneCnt++;
    return s;
}

// Fitness
double getShiYingDu(Rst &g) { return 1.0 / getValue(g); }

Selection#

We use a binary tournament selection method, where two individuals are randomly drawn each time, retaining the one with higher fitness. Correspondingly, the method of selecting multiple individuals for comparison is called n-tournament selection.

// Selection, binary tournament
Rst &choose(vector<Rst> &pool) {
    int len = pool.size();
    int i = rand() % len;
    int j = rand() % len;
    int big = getShiYingDu(pool[i]) > getShiYingDu(pool[j]) ? i : j;
    return pool[big];
}

Crossover#

The crossover method we use is a type of order crossover. A segment is randomly selected from individual 2 and placed in front of individual 1, removing any duplicate genes that follow it. The same operation is performed using the same segment from another individual.

For example, from 1 5 4 3 2 and 5 3 2 1 4, randomly selecting positions 1 to 3 results in offspring 2 1 3 5 4 and 5 4 3 2 1.

// Order crossover
pair<Rst, Rst> oxCross(Rst &r1, Rst &r2) {
    int len = r1.size();
    int i = rand() % len, j = i + rand() % (len - i);
    Rst s1, s2;
    unordered_map<int, bool> mp1, mp2;
    for (int p = i; p <= j; ++p) {
        s1.push_back(r2[p]);
        mp1[r2[p]] = 1;
        s2.push_back(r1[p]);
        mp2[r1[p]] = 1;
    }
    for (int p = 0; p < len; ++p) {
        if (!mp1[r1[p]]) {
            s1.push_back(r1[p]);
            mp1[r1[p]] = 1;
        }
        if (!mp2[r2[p]]) {
            s2.push_back(r2[p]);
            mp2[r2[p]] = 1;
        }
    }
    return {s1, s2};
}

Mutation#

With a certain probability, two genes are randomly selected for swapping.

// Mutation
void bianYi(Rst &r) {
    double rd = randf();
    if (rd < 0.01) {
        int len = r.size();
        int i = rand() % len;
        int j = rand() % len;
        int t = r[i];
        r[i] = r[j];
        r[j] = t;
    }
}

Running Test#

We randomly generated a set of test data containing 174 city coordinates. The following figure shows the optimal solution (red) and the average solution of the population (green) after 1000 generations of reproduction.
Data: https://gist.github.com/zhufengning/3a617fc3f3765cd192d42fb27ee374d0

Complete Code#

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

const int SIZE = 1000, CNT = 1000;
using Pos = pair<double, double>;
using Rst = vector<int>;

vector<Pos> a;
double ans = 1e9;
double notans = 1e9;
double geneSum = 0;
int geneCnt = 0;
Rst ans_rst;

// Get a random float, 0~1
double randf() {
    return static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
}

// Randomly generate a solution
Rst randGene(int n) {
    Rst ret;
    unordered_map<int, bool> mp;
    for (int i = 1; i <= n; ++i) {
        int newr = rand() % n;
        while (mp[newr])
            newr = rand() % n;
        ret.push_back(newr);
        mp[newr] = true;
    }
    return ret;
}

// Distance between two points
double getDis(Pos p1, Pos p2) {
    return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
}

// Total distance traveled
double getValue(Rst &g) {
    int len = g.size();
    double s = 0;
    for (int i = 1; i < len; ++i) {
        s += getDis(a[g[i - 1]], a[g[i]]);
    }
    s += getDis(a[g[0]], a[g[len - 1]]);
    if (s < ans) {
        ans = s;
        ans_rst = g;
    }

    if (s < notans)
        notans = s;

    geneSum += s;
    geneCnt++;
    return s;
}

// Fitness
double getShiYingDu(Rst &g) { return 1.0 / getValue(g); }

// Selection, binary tournament
Rst &choose(vector<Rst> &pool) {
    int len = pool.size();
    int i = rand() % len;
    int j = rand() % len;
    int big = getShiYingDu(pool[i]) > getShiYingDu(pool[j]) ? i : j;
    return pool[big];
}

// Order crossover
pair<Rst, Rst> oxCross(Rst &r1, Rst &r2) {
    int len = r1.size();
    int i = rand() % len, j = i + rand() % (len - i);
    Rst s1, s2;
    unordered_map<int, bool> mp1, mp2;
    for (int p = i; p <= j; ++p) {
        s1.push_back(r2[p]);
        mp1[r2[p]] = 1;
        s2.push_back(r1[p]);
        mp2[r1[p]] = 1;
    }
    for (int p = 0; p < len; ++p) {
        if (!mp1[r1[p]]) {
            s1.push_back(r1[p]);
            mp1[r1[p]] = 1;
        }
        if (!mp2[r2[p]]) {
            s2.push_back(r2[p]);
            mp2[r2[p]] = 1;
        }
    }
    return {s1, s2};
}

// Mutation
void bianYi(Rst &r) {
    double rd = randf();
    if (rd < 0.01) {
        int len = r.size();
        int i = rand() % len;
        int j = rand() % len;
        int t = r[i];
        r[i] = r[j];
        r[j] = t;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        double tx, ty;
        scanf("%lf%lf", &tx, &ty);
        a.push_back(make_pair(tx, ty));
    }
    // The above is the data input part
    // The entire population
    vector<Rst> pool; 
    // Generate random chromosomes
    for (int i = 1; i <= SIZE; ++i)
        pool.push_back(randGene(n));
    // Perform CNT generations of reproduction
    for (int i = 1; i <= CNT; ++i) {
        // Initialize statistics for this round
        notans = 1e9;
        geneSum = 0;
        geneCnt = 0;
        printf("%d ", i);
        // Fitness array
        vector<double> score;
        // New population
        vector<Rst> new_pool;
        for (int i = 1; i <= CNT / 2; ++i) {
            // Select two parents
            auto win1 = choose(pool);
            auto win2 = choose(pool);
            // 20% chance to perform crossover
            if (randf() < 0.2) {
                auto children = oxCross(win1, win2);
                win1 = children.first;
                win2 = children.second;
            }
            // Attempt mutation, 1% chance of mutation
            bianYi(win1);
            bianYi(win2);
            // Insert into the new population
            new_pool.push_back(win1);
            new_pool.push_back(win2);
        }
        // Output results for this round
        printf("%lf %lf %lf\n", ans, notans, geneSum / geneCnt);
        // Population change
        pool = new_pool;
    }
    // Output the chromosome of the optimal solution
    for (int v : ans_rst)
        printf("%d ", v);
    return 0;
}