knapsack-genetic-algorithm/Population.cpp at main · lilys01/knapsack-genetic-algorithm · 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
#include <queue>
#include <tuple>
#include <random>
#include <limits>

using namespace std;

#include "GeneticCode.h"
#include "Population.h"
#include "Knapsack.h"


unsigned int Population::newGeneration(unsigned int bitsPerCrossover){
	vector<unsigned int> parentGen = this->geneticCodes.back();
	vector<unsigned int> n(this->size);
	unsigned int parentA;
	unsigned int parentB;

  	// Fandom number generator
	default_random_engine generator(random_device{}());
	uniform_int_distribution<unsigned int> randTournament(0, parentGen.size()-1);
	uniform_int_distribution<unsigned char> randParent(0, 1);
	uniform_real_distribution<double> randMutation(0.0, 1.0);

	while(n.size() < this->size){

    	// Tournament selection for 2 parents
		for(unsigned char i = 0; i < 2; i++){

			priority_queue<tuple<unsigned int, unsigned int>> pq;

      		// Add codes for tournament to pq
			for(unsigned int j = 0; j < this->tournamentSize; j++){
				unsigned int index = randTournament(generator);
				unsigned int fitness = this->knapsack.evaluateCode(parentGen[index]);

				pq.push(make_tuple(fitness, parentGen[index]));
			}

      		// Add most fit code from the tournament to be a parent
      		if(i == 0) {
				parentA = get<0>(pq.top());
      		} else {
      			parentB = get<0>(pq.top());
      		}
		}

    	// Make new generation from parents
		for(unsigned int i = 0; i < 2; i++){

			unsigned int child = 0;


			unsigned int parent;
			if(randParent(generator) == 0) {
				parent = parentA;
			} else {
				parent = parentB;
			}
			for(unsigned int j = 0; j < 32; j++){

        		// Crossover
        		if(j%bitsPerCrossover == 0) {
					if(randParent(generator) == 0) {
						parent = parentA;
					} else {
						parent = parentB;
					}
				}

				unsigned int trait = GeneticCode::readBit(parent, j);

        		// Mutation
				if(randMutation(generator) < this->mutationRate){
					trait = trait ^ 1;
				}

				GeneticCode::writeBit(child, j, trait);
			}

			n.push_back(child);
		}
	}

	geneticCodes.push_back(n);

	// Updating the best code
	unsigned int bestFitness = this->knapsack.evaluateCode(this->bestCode);

	unsigned int fitness;
	for(unsigned int i: n) {
		fitness = this->knapsack.evaluateCode(i);

		if(fitness > bestFitness) {
			bestFitness = fitness;
			this->bestCode = i;
		}
	}

	return this->bestCode;
}


Population::Population(Knapsack knapsack, unsigned int popSize, unsigned int tournamentSize, double mutationRate):
					knapsack(knapsack), size(popSize), tournamentSize(tournamentSize), mutationRate(mutationRate), bestCode(0) {

	// Random number generator
	default_random_engine generator(random_device{}());
	uniform_int_distribution<unsigned int> randCode(0, numeric_limits<unsigned int>::max());

	// Keeping track of the best code for the initial generation
	unsigned int bestFitness = 0;
	unsigned int fitness;

	// Generating first set of random codes
	vector<unsigned int> newGen;
	for(unsigned int i = 0; i < this->size; i++) {
		newGen.push_back(randCode(generator));

		// Max fitness
		fitness = this->knapsack.evaluateCode(newGen.back());
		if(fitness > bestFitness) {
			bestFitness = fitness;
			this->bestCode = newGen.back();
		}
	}

	this->geneticCodes.push_back(newGen);
}