Genetic-Algorithm-Solving-Knapsack-Problem-With-Cpp/genetic_algorithm.h at main · NFUChen/Genetic-Algorithm-Solving-Knapsack-Problem-With-Cpp · 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
135
136
137
138
139
140
141
142
143
144
145
146
#ifndef GENETICALGORITHM_H
#define GENETICALGORITHM_H
#include <iostream>
#include <cmath>
#include "PyDataType/list.h"
#include "product.h"
#include "cart.h"

template <typename T>
T &choose_max(T &x, T &y)
{
    if (x > y)
        return x;

    return y;
}

class GeneticAlgorithm
{
private:
    void intialize_population()
    {
        while (m_current_population.length() < m_population_size)
        {
            Cart one_solution(m_available_products, m_space_limit);
            m_current_population.append(one_solution);
        }
        m_current_population.sort();
        m_current_best_solution = m_current_population[-1];
        m_global_best_solution = m_current_best_solution;
    }

    double get_total_fitness_of_population()
    {
        double total_fitness = 0;
        for (const Cart &cart : m_current_population.values())
        {
            total_fitness += cart.fitness();
        }
        return total_fitness;
    }

    Cart select_a_parent()
    {
        double total_fitness = get_total_fitness_of_population();

        if (total_fitness == 0)
        {
            Cart random_parent = randomly_select_a_parent();
            return random_parent;
        }

        double random_val = uniform_random<double>(0, 1);
        double check_sum = 0;
        int selected_idx = 0;
        while (check_sum < (random_val * total_fitness) && selected_idx <= (m_population_size - 1))
        {
            check_sum += m_current_population[selected_idx].fitness();
            selected_idx += 1;
        }

        return m_current_population[selected_idx - 1];
    }
    Cart randomly_select_a_parent()
    {
        int random_idx = floor(uniform_random<double>(0, 1) * m_current_population.length());

        return m_current_population[random_idx];
    }

    List<Cart> crossover_two_parents()
    {
        Cart parent_x = select_a_parent();
        Cart parent_y = select_a_parent();

        List<Cart> children = parent_x.crossover(parent_y);

        return children;
    }

    List<Cart> mutate_two_children(List<Cart> children)
    {
        for (Cart &cart : children.values())
        {
            cart.mutate(m_mutation_prob);
        }

        return children;
    }
    void update_population_info(List<Cart> &new_population)
    {
        m_current_population = new_population;
        m_current_population.sort();
        m_current_best_solution = m_current_population[-1];
        m_global_best_solution = choose_max(m_global_best_solution, m_current_best_solution);
    }

    void visualize_current_generation()
    {
        std::cout << "Generation: " << m_current_generation << "\n";
    }

public:
    int m_population_size;
    double m_mutation_prob;
    int m_number_of_generation;
    List<Product> m_available_products;
    double m_space_limit;

    List<Cart> m_current_population;
    int m_current_generation = 0;
    Cart m_current_best_solution;
    Cart m_global_best_solution;
    GeneticAlgorithm(int population_size, double mutation_prob, int number_of_generation, const List<Product> &available_products, double space_limit)
        : m_population_size(population_size),
          m_mutation_prob(mutation_prob),
          m_number_of_generation(number_of_generation),
          m_available_products(available_products),
          m_space_limit(space_limit)
    {
    }

    void solve()
    {
        intialize_population();
        visualize_current_generation();
        m_current_generation = 1;

        for (int generation = 0; generation < m_number_of_generation; generation++)
        {
            List<Cart> new_population;
            while (new_population.length() < m_population_size)
            {
                List<Cart> children = crossover_two_parents();
                List<Cart> mutated_children = mutate_two_children(children);
                new_population.extend(mutated_children);
            }
            update_population_info(new_population);
            visualize_current_generation();

            m_current_generation += 1;
        }
    }
};

#endif