Genetic Algorithm approach to the Knapsack problem in C++

ga_knapsack.cpp

#include <bits/stdc++.h>
using namespace std;

char** create_pop(int pop_size, int numberOfObj) {	
	char** population = (char**) malloc(pop_size * sizeof(char*));
	
	// creates a 'numOfObj' sized string for each position in the population vector
	for(int i = 0; i < pop_size; i++) {
		population[i] = (char*) malloc((numberOfObj + 1) * sizeof(char));
	}
	
	srand(time(NULL));
	for(int i = 0; i < pop_size; i++) {
		
		// randomly decides which letter will be in a determined position
		for(int j = 0; j < numberOfObj; j++) {
			// letter may be either 0 or 1
			// 1 means the object was taken
			char letter = (rand() % 2) + '0';
			population[i][j] = letter;
		}

		// adds string terminator in the end of each individual (don't know if this is necessary)
		population[i][numberOfObj] = '\0';
	}

	return population;
}

void evaluate(char** population, int pop_size, int numberOfObj, int maxWeight, const vector< pair<int, int> >& objects, int** fitness) {
	
	// for each individual
	for(int i = 0; i < pop_size; i++) {
		int fit = 0;
		int weight = 0;

		for(int j = 0; j < numberOfObj; j++) {
			if(population[i][j] == '1') {

				// add up the fit and weight of the correspondent object
				fit += objects[j].first;
				weight += objects[j].second;
			}
		}

		// sets fitness to 0 if weight is above maximum
		if (weight > maxWeight) (*fitness)[i] = 0;
		else (*fitness)[i] = fit;
	}

}

void crossover(char*** population, int pop_size, int numberOfObj, char* best, int bestIdx) {
	char letter;

	for(int i = 0; i < pop_size; i++) {
		
		// making sure we don't change the best individual
		if (i == bestIdx) {
			continue;
		}

		// a gene may come from the best individual or from the individual we're crossovering now
		for(int j = 0; j < numberOfObj; j++) {
			int choose = rand() % 2;
			// if choose equal 0, gene comes from the best
			// otherwise, gene comes from the current individual
			if(choose == 0) {
				letter = best[j];
			} else {
				letter = (*population)[i][j];
			}

			// changes the current letter into the chosen one
			(*population)[i][j] = letter;
		}

		(*population)[i][numberOfObj] = '\0';
	}
}

void mutation(char*** population, int pop_size, int numberOfObj, int bestIdx, int mutationTax) {
	int numOfChanges = (mutationTax / 100) * numberOfObj;
	if (numOfChanges == 0) {
		numOfChanges = 1;
	}

	for(int i = 0; i < pop_size; i++) {
		// making sure we don't mutate the best individual
		if(i == bestIdx) continue;

		// the 'numOfChanges' is based on the 'mutationTax' but is at least 1
		for(int j = 0; j < numOfChanges; j++) {
			// randomly chooses a letter to invert
			int choose = rand() % numberOfObj;
			if( (*population)[i][choose] == '1') (*population)[i][j] = '0';
			else (*population)[i][choose] = '1';
		}
	}
}

// this function kills all the individuals with 0 fitness and generate a random one in its place
void genocide(char*** population, int pop_size, int numberOfObj, int* fitness) {
	for(int i = 0; i < pop_size; i++) {
		if (fitness[i] == 0) {
			for(int j = 0; j < numberOfObj; j++) {
			char letter = (rand() % 2) + '0';
			(*population)[i][j] = letter;
			}	

			(*population)[i][numberOfObj] = '\0';
		}
	}
}

void free_all(char*** pop, int pop_size, int numberOfObj, int** fitness) {	
	for(int i = 0; i < pop_size; i++) {
		free((*pop)[i]);
	}
	free(*pop);
	free(*fitness);
}

int main() {
	vector< pair<int,int> > objects;	// stores all values and weights of objects
	char** population; 			// contains strings of 0s and 1s representing each individual
	int value, weight; 			// stores value and weight of a object
	int mutationTax = 5;			// hardcoded mutation tax
	int numberOfObj;			// stores number of objects (also size of string)
	int maxWeight; 				// stores the maximum capacity of the backpack
	int* fitness; 				// will store the fitness of each individual
	int pop_size;				// stores population size
	int bestIdx;				// stores the index of the best individual
	char* best;				// stores the string that represents the best individual

	printf("Enter population size: ");
	scanf("%d", &pop_size);

	printf("Enter maximum weight: ");
	scanf("%d", &maxWeight);	

	printf("Enter the number of objects: ");
	scanf("%d", &numberOfObj);

	printf("Write all the objects below (value, weight):\n");
	for(int i = 0; i < numberOfObj; i++) {
		cin >> value >> weight;
		objects.push_back(make_pair(value, weight));
	}

	// creates first population
	population = create_pop(pop_size, numberOfObj);

	// creates fitness vector
	fitness = (int*) malloc(pop_size * sizeof(int));

	int stuck = 0;				// used to check since when the best fitness is stuck
	int dynamicMut = 0;			// used to change mutation tax after being stuck for a while
	bool mutationFlag = false;		// used to decide if we're going to increase or decrease the mutation tax
	int lastFit = 0;			// used to compare fitness and increase 'stuck'
	while(true) {

		evaluate(population, pop_size, numberOfObj, maxWeight, objects, &fitness);
		bestIdx = max_element(fitness, fitness + pop_size) - fitness;
		best = population[bestIdx];
		int bestFit = fitness[bestIdx];

		// if we are stuck, increase dynamicMut and 'stuck'
		// and if the fitness has changed, set 'stuck' and 'dynamicMut' to 0
		if(bestFit == lastFit) {
			dynamicMut++;
			stuck++;
		} else {
			dynamicMut = 0;
			stuck = 0;
		}

		printf("The current mutation tax is: %d\n", mutationTax);
		printf("The best pick is %s | Fitness: %d\n", best, bestFit);

		for(int i = 0; i < pop_size; i++) {
			printf("Individual %d: %s | Fitness: %d\n", i+1, population[i], fitness[i]);
		}

		printf("\n");

		crossover(&population, pop_size, numberOfObj, best, bestIdx);

		// the block of code below can be changed to achieve better results
		if(dynamicMut > 50 and mutationFlag == false) {
			mutationTax = 25;
			mutationFlag = true;
			dynamicMut = 0; 	// after changing the mutation tax we set only 'dynamicMut' back to 0, not 'stuck'
		} else if(dynamicMut > 150 and mutationFlag == true) {
			mutationTax = 5;
			mutationFlag = false;
			dynamicMut = 0;
		} else if(stuck > 500) break;

		mutation(&population, pop_size, numberOfObj, bestIdx, mutationTax);
		genocide(&population, pop_size, numberOfObj, fitness);

		// saving fitness of current generation
		lastFit = fitness[bestIdx];

	} 
		
	free_all(&population, pop_size, numberOfObj, &fitness);
}

test1.in

10
6404180
24 
825594 382745
1677009 799601
1676628 909247
1523970 729069
943972 467902
97426 44328
69666 34610
1296457 698150
1679693 823460
1902996 903959
1844992 853665
1049289 551830
1252836 610856
1319836 670702
953277 488960
2067538 951111
675367 323046
853655 446298
1826027 931161
65731 31385
901489 496951
577243 264724
466257 224916
369261 169684

test2.in

10
170
7
442 41
525 50
511 49
593 59
546 55
564 57
617 60