GeneticAlgorithm/algorithm.cpp at master · AmyHong0502/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
//
// Created by Amy Hong on 2018-11-24.
//

#include "algorithm.hpp"

void algorithm::run() {
    init();
    sort();

    int iteration_counter = 0;
    double improvement = 1;
    tour prev;
    while (iteration_counter < ITERATIONS || improvement < IMPROVEMENT_FACTOR) {
        ++iteration_counter;
        prev = population.front();

        crossover();
        sort();

        mutate();
        sort();

        improvement = evaluate(prev);

        report(improvement);
    }
}

void algorithm::init() {
    tour t = rand.generate_tour();
    population.push_back(t);

    for (unsigned long i = 0; i < POPULATION_SIZE; i++) {
        tour temp(t);
        temp.shuffle_cities();

        population.push_back(temp);
    }
}

void algorithm::crossover() {
    std::vector<tour> new_population;
    new_population.push_back(population.at(0));

    tour parents[NUMBER_OF_PARENTS];
    for (auto &parent : parents) {
        parent = choose_parent();
    }

    while (new_population.size() < POPULATION_SIZE) {
        new_population.push_back(parents[0].crossover(parents[1]));
    }

    population = new_population;
}

tour algorithm::choose_parent() {
    std::vector<tour> parent;
    parent.reserve(PARENT_POOL_SIZE);
    for (int i = 0; i < PARENT_POOL_SIZE; i++) {
        parent.push_back(population.at(
                static_cast<unsigned long>(
                        rand.generate_random_int(NUMBER_OF_ELITES,
                                                 POPULATION_SIZE - 1)
                )));
    }

    std::sort(parent.begin(), parent.end());
    return parent.at(0);
}

void algorithm::sort() {
    std::sort(population.begin(), population.end());
}

void algorithm::report(double improvement) {
    double best = population.front().determine_fitness();
    double worst = population.at(population.size() - 1).determine_fitness();
    std::cout
            << std::setw(12) << "BEST"
            << std::setw(12) << best * 100000
            << std::setw(12) << "WORST"
            << std::setw(12) << worst * 100000
            << std::setw(12) << "IMPROVEMENT"
            << std::setw(12) << improvement << std::endl;
}

void algorithm::print() {
    for (const auto &i : population) {
        std::cout << i;
    }
    std::cout << std::endl;
}

void algorithm::mutate() {
    for (unsigned long i = NUMBER_OF_ELITES; i < population.size(); i++) {
        if (rand.generate_random_int(0, MUTATION_RATE) == MUTATION_RATE) {
            population.at(i).mutate();
        }
    }
}

double algorithm::evaluate(tour prev) {
    double before = prev.determine_fitness();
    double after = population.front().determine_fitness();

    return (after - before) * 100000;
}