Travelling Salesman Problem

Lab4-TSP.c++

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std;

// constant
const int NUM_OF_GENE = 5;
const int POPULATION_SIZE = 2;
//const char CITIES[NUM_OF_GENE] = { 'A', 'B', 'C', 'D', 'E' };
const int CITIES[NUM_OF_GENE] = {0, 1, 2, 3, 4};

// chromosome structure
int chromosome[POPULATION_SIZE][NUM_OF_GENE];
double fitnessValue[POPULATION_SIZE];

// a map of distances between cities
const int DISTANCE[5][5] = {
    {0, 2, 7, 12, 10},
    {2, 0, 4, 8, 9},
    {7, 4, 0, 3, 3},
    {12, 8, 3, 0, 10},
    {10, 9, 3, 10, 0}
};

// function prototypes
int generateSeed(int i);
int * randPerm();
void initializeChromosome();
void evaluateChromosome();
void printChromosome();


int main(int argc, const char * argv[]) {
    auto start_time = chrono::system_clock::now();
    srand ( unsigned ( time(0) ) );
    
    initializeChromosome();
    evaluateChromosome();
    printChromosome();
    
    auto end_time = chrono::system_clock::now();
    chrono::duration<double> elapsed_time = end_time - start_time;
    cout << "This program took " << elapsed_time.count() << "s to run\n";
    return 0;
}

// seed generator
int generateSeed(int i) {
    return rand() % i;
}

// return a randomly permutated array
int * randPerm() {
    static int arr[NUM_OF_GENE];
    
    vector<int> myVector;
    
    for (int i=0; i<NUM_OF_GENE; i++) {
        myVector.push_back(i);
    }
    
    random_shuffle(myVector.begin(), myVector.end());
    random_shuffle(myVector.begin(), myVector.end(), generateSeed);
    copy(myVector.begin(), myVector.end(), arr);
    
    return arr;
}

void initializeChromosome() {
    for (int i=0; i<POPULATION_SIZE; i++) {
        int * randArr = randPerm();
        
        // allocate cities (in char) into the chromosome array
        for (int j=0; j<NUM_OF_GENE; j++) {
            chromosome[i][j] = CITIES[randArr[j]];
        }
    }
}

void evaluateChromosome() {
    for (int i=0; i < POPULATION_SIZE; i++) {
        int totalDistance = 0;
        for (int j=0; j < NUM_OF_GENE; j++) {
            int startCoordinate = chromosome[i][j];
            int endCoordinate = chromosome[i][j+1];
            if (j == 4) endCoordinate = chromosome[i][0];
            totalDistance += DISTANCE[startCoordinate][endCoordinate];
        }
        fitnessValue[i] = totalDistance;
    }
}

void printChromosome() {
    for (int i=0; i<POPULATION_SIZE; i++) {
        for (int j=0; j<NUM_OF_GENE; j++) {
            cout << chromosome[i][j] << " ";
        }
        cout << fitnessValue[i] << "\n";
    }
}