GeneticAlgorithm/main.cpp at master · Adamsmith6300/GeneticAlgorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

#include <iostream>
#include <fstream>
#include <random>
#include <sstream>
#include <stdlib.h>
#include "City.hpp"
#include "Tour.hpp"
#include "Population.hpp"

using namespace std;

vector<City*> make_citiesList();
Tour crossTours(Tour p1, Tour p2);
void mutateTours(vector<Tour>* crosses);

int main() {
    vector<City*> citiesList = make_citiesList();
    vector<Tour> tours;
    for(int i = 0; i < POPULATION_SIZE; ++i){
        Tour newTour{citiesList};
        newTour.shuffleCities();
        newTour.determineFitness();
        tours.push_back(newTour);
    }
    Population pop{tours};

//Gen Algo Starts
    Tour baseElite = pop.moveBestTourToFront();
    double baseDistance = baseElite.get_fitness();
    double bestDistance = baseDistance;
    srand (time(NULL));
    int count = 0;
    while (bestDistance/baseDistance > IMPROVEMENT_THRESHOLD && count < ITERATIONS){

        Tour elite = pop.moveBestTourToFront();
        vector<Tour> crosses;
        crosses.push_back(elite);
        while(crosses.size() < pop.getTours().size()){
            Population setOne = pop.getParentSet();
            Tour parentOne = setOne.moveBestTourToFront();
            Population setTwo = pop.getParentSet();
            Tour parentTwo = setTwo.moveBestTourToFront();
            Tour mergedTour = crossTours(parentOne, parentTwo);
            crosses.push_back(mergedTour);
        }
        mutateTours(&crosses);
        pop.setTours(crosses);
        bestDistance = pop.evaluateFitness();
        ++count;

        cout << "Iteration: " << count << endl;
        cout << "Distance/Fitness: " << bestDistance << endl;
        if(bestDistance < baseDistance){
            cout << "Improvement achieved" << endl;
        } else {
            cout << "Improvement not achieved" << endl;
        }
        cout << "Improvement factor: " << bestDistance/baseDistance << endl;
    }


    Tour bestRoute = pop.moveBestTourToFront();
    cout << "FINAL RESULTS:" << endl;
    cout << "Number of iterations:" << count << endl;
    cout << "Base Distance:" << baseDistance << endl;
    cout << "Best Distance:" << bestDistance << endl;
    if(bestDistance/baseDistance > IMPROVEMENT_THRESHOLD){
        cout << "Improvement Factor NOT Achieved!" << endl;
    } else {
        cout << "Improvement Factor Achieved!" << endl << endl;
    }
    cout << "Base Route: " << endl;
    cout << baseElite << endl << endl;
    cout << "Best Route Taken: " << endl;
    cout << bestRoute << endl;


    return 0;
}


void mutateTours(vector<Tour>* crosses){
    int randAsInt = (rand() % 10) + 20;
    double randPercent = (double)randAsInt/100.00;
    int mutationCount = randPercent * crosses->size();
    int count = 0;
    while (count < mutationCount){
        int randTourIndex = rand() % crosses->size();
        crosses->at(randTourIndex).mutateTour();
        ++count;
    }
}


Tour crossTours(Tour p1, Tour p2){
    vector<City*> newTourCities;
    vector<City*> p1Cities = p1.getCities();
    vector<City*> p2Cities = p2.getCities();
    int upToFromP1 = rand() % p1Cities.size();
    for(int i = 0; i <= upToFromP1; ++i){
        newTourCities.push_back(p1Cities[i]);
    }
    for(auto it = p2Cities.begin(); it != p2Cities.end(); ++it){
        if(std::find(newTourCities.begin(), newTourCities.end(), *it) == newTourCities.end()) {
            newTourCities.push_back(*it);
        }
    }
    Tour mergedTour{newTourCities};
    return mergedTour;
}


vector<City*> make_citiesList(){
    fstream f{"cities.txt"};
    string line;
    vector<City*> citiesList;
    random_device rd; // obtain a random number from hardware
    mt19937 eng(rd()); // seed the generator
    uniform_int_distribution<> distr(0, MAP_BOUNDARY); // define the range
    for(int i = 0; i < CITIES_IN_TOUR; ++i){
        getline(f,line);
        istringstream iss{line};
        string cityName;
        iss >> cityName;
        int x = distr(eng);
        int y = distr(eng);
        City* newCity = new City(x,y,cityName);
        citiesList.push_back(newCity);
    }
    return citiesList;
}