Solution to "8 Queens" problem, Genetics Algorithm

8queens.cpp

/*
 * A GENETIC SOLUTION TO 8 QUEENS
 * COMPUTATIONAL INTELLIGENCE COURSE
 * BU-ALI SINA UNIVERSITY 2019
 * 
 * DEVELOPER: MOHAMMAD R. TAYYEBI, B.SC.
 * SUPERVISOR: MOHAMMAD BAMNESHIN
 *
 * =======================
 * WARNING WARNING WARNING
 * =======================
 *
 * THIS CODE IS UNDER CONSTRUCTION
 * AND WROTEN IN NON-OPTIMAL FORM BECAUSE
 * OF TEACHING PORPOSE.
 * DO NOT DEPEND ON THIS ON YOUR PAPERS,
 * "NORMAL PEOPLE"'S PROJECTS, ETC...
 */


#include <iostream>
#include <string.h>
#include <cstdlib>
#include <tgmath.h>
#include <unistd.h>
#include <stdlib.h>
#include <iomanip>

using namespace std;

// function to generate random between 0 to 1
double rand_01_f();

// Data type for chroms
class Chrom_8 {

// Access specifier 
private:

	// == Data Members 
	int chrom [8] = {0}; 

// Access specifier 
public:

	// == Constructor 
	Chrom_8()
	{
		// Generate random population
		for (int i = 0 ; i < 8 ; i ++)
		{
			chrom[i] = random() % 8;
		}
	}

	// == Functions

	// Get value of each segment
	int GetValue (int index)
	{
		return chrom [index];
	}

	// Set value for each segment
	void SetValue (int index, int value)
	{
		chrom [index] = value;
	}

	// Print out the board
	void display_board()
	{
		for (int m = 0 ; m < 8 ; m ++)
		{
			cout << endl;
			for (int n = 0 ; n < 8 ; n ++)
			{
				if (chrom[m] == n)
				{
					cout << "1";
				}
				else
				{
					cout << "0";
				}
				
			}
		}
		cout << endl;
	}

	// Calculate attack
	int calc_attack(bool show_details = false)
	{
		int total_attacks = -1;

		int row_attacks = 0;
		int column_attacks = 0;
		int diameter_attacks = 0;
		int reverse_diameter_attacks = 0;
		int less_or_more_queens = 0;

		// Calculate column attacks
		for (int i = 0 ; i < 8 ; i ++)
			for (int j = i ; j < 8 ; j ++)
				if (chrom[i] == chrom[j] && i != j)
					column_attacks++;

		// Calculate diameter attacks
		for (int i = 0 ; i < 8 ; i ++)
			for (int j = i ; j < 8 ; j ++)
				if (j - i == chrom[j] - chrom[i] && i != j)
					diameter_attacks++;

		// Calculate reverse diameter attacks
		for (int i = 0 ; i < 8 ; i ++)
			for (int j = i ; j < 8 ; j ++)
				if (abs(j - i) == abs(chrom[j] - chrom[i]) && i != j)
					reverse_diameter_attacks++;		

		// Less than 8 queens
		for (int i = 0 ; i < 8 ; i ++)
			if (chrom[i] < 0 || chrom[i] > 8)
				less_or_more_queens++;


		// Sumation of total attacks
		total_attacks = row_attacks + column_attacks + diameter_attacks + reverse_diameter_attacks + less_or_more_queens;

		if (show_details)
		{
			cout << "Row Attacks: " << row_attacks << endl
				<< "Column Attacks: " << column_attacks << endl
				<< "Diam Attacks: " << diameter_attacks << endl
				<< "Diam-1 Attacks: " << reverse_diameter_attacks << endl
				<< "Less or more queens: " << less_or_more_queens << endl;
		}

		return total_attacks;
	}
};

// Fitness function
double calc_fitness(Chrom_8 chrom);

// Fitness function
double sum_of_fitness(double * fitness_values, int population_size);


// Normalization
void normalize_fitness( double * fitness_values, int population_size, double sum_of_fitness );


// The OS favorite function!
int main(int argc, char *argv[]) { 

	// Show help function
	if (!strcmp(argv[1], "help"))
	{
		cout << "1- Crossover rate; 2- Mutation rate; 3- Max generation; 4- Population size";
		return 0;
	}

	// Initialize random seed
	srand((unsigned)time(NULL));

	// Set decimal points on cout
	cout << fixed ;
	cout << setprecision(2);

	
	// TEST : A Solution
	cout << "== TEST== " << endl;
	Chrom_8 ch ;
	ch.SetValue(0, 2);
	ch.SetValue(1, 5);
	ch.SetValue(2, 7);
	ch.SetValue(3, 0);
	ch.SetValue(4, 3);
	ch.SetValue(5, 6);
	ch.SetValue(6, 4);
	ch.SetValue(7, 1);
	ch.calc_attack(true);
	cout << "Fitness value: " << calc_fitness(ch);
	ch.display_board();
	cout << endl;

	// Get input params from terminal
	int crossover_rate = (atoi(argv[1]) > 100 || atoi(argv[1]) < 0) ? 10 : atoi(argv[1]); 
	int mutation_rate = (atoi(argv[2]) > 100 || atoi(argv[2]) < 0) ? 1 : atoi(argv[2]); 
	int max_generation = atoi(argv[3]);
	int population_size = atoi(argv[4]);

	// Statistics:
	float max_fitness_val = 0.0;

	// Welcome message
	cout << "Launching with parameters:" << endl
		<< "Crossover Rate (of 100): " << argv[1] << endl
		<< "Mutation Rate (of 100): " << argv[2] << endl
		<< "Max Generation: " << argv[3] << endl
		<< "Population Size: " << argv[4] << endl
		<< endl;

	// Initial Population
	Chrom_8 chrom_8s [population_size];

	// Generations loop
	int g = 0;
	while (g <= max_generation)
	{

		// Calculate fitness function
		double fitness_values [population_size] = { -1.0 };
		for (int i = 0  ; i  < population_size ; i ++)
		{
			// Calculate Attacks
			fitness_values[i] = calc_fitness(chrom_8s[i]);
			if (fitness_values[i] >= max_fitness_val)
			{
				max_fitness_val = fitness_values[i];
				cout << "Fitness function for child " << i << ": " << fitness_values[i] << ", from gen: " << g << endl;
			}

			// In case of success
			if (fitness_values[i] >= 0.5)
			{
				cout << "Good one: child " << i << ", from generation " << g << ", with " << chrom_8s[i].calc_attack() << " attacks.";
				chrom_8s[i].display_board();
				chrom_8s[i].calc_attack(true);
				
				// Terminate
				if (fitness_values[i] >= 1)
					return 0;
			}
		}

		// ======== NEW GENERATION CALCULATIONS ========
		g++;

		// sleep(0.1);
		// cout << endl << "=== " << "Generation " << g << " ===" << endl ;

		// Calculate sumation of fitness function returned values
		double sum_of_fit = sum_of_fitness(fitness_values, population_size);

		// Normaliztion
		normalize_fitness(fitness_values, population_size, sum_of_fit);

		// Selection
		int selected_parents [population_size] = { -1 };
		for (int i = 0 ; i < population_size ; i++) {

			double wheel_spin = rand_01_f();
						
			// Roulette wheel
			int w = 1;
			for ( ; w < population_size ; w ++)
			{
				if (wheel_spin <= fitness_values[w] && wheel_spin >= fitness_values[w - 1])
					break;
			}
			
			selected_parents[i] = w;
		}

		// Sort selected parents for recreation
		for(int i = 0 ; i < population_size ; i ++)
		{		
			for(int j = i+1 ; j < population_size ; j++)
			{
				if(selected_parents[i] > selected_parents[j])
				{
					int temp = selected_parents[i];
					selected_parents[i] = selected_parents[j];
					selected_parents[j] = temp;
				}
			}
		}

		// Recreate new generation
		for(int i = 0 ; i < population_size ; i ++)
		{
			
			// Only keep parents with good chance
			chrom_8s[i] = chrom_8s[ selected_parents[i] ];

			// Do mutation
			if (random() % 100 < mutation_rate)
			{
				chrom_8s[i].SetValue(random() % 8, random() % 8);
			}

			// Do crossover
			if (i % 2) // We need two parents for crossover!
				if (random() % 100 < crossover_rate)
				{
					// We need two points for crossover
					int p1 = random() % 8, p2 = random() % 8;
					
					if (p1 > p2)
					{
						p1 = p1 + p2; // a = 15 = 05 + 10    
						p2 = p1 - p2; // b = 05 = 15 - 10
						p1 = p1 - p2; // a = 10 = 15 - 05
					}

					int delta = p2 - p1;

					// Crossover function
					int temp = -1;
					for (int k = p1 ; k < p2 ; k ++)
					{
						temp = chrom_8s[i].GetValue(k);
						chrom_8s[i].SetValue(k, chrom_8s[i-1].GetValue(k));
						chrom_8s[i-1].SetValue(k, temp);
					}
				}
		}

	}

	// The end
	cout << endl;

	// Ces fini
	return 0;
}

// Random 01 double function described
double rand_01_f() {
	return  random() / (RAND_MAX + 1.);
}

// Fitness function
double calc_fitness(Chrom_8 chrom) {
	int attacks = chrom.calc_attack();
	double calculated_fitness = 1 / double(attacks + 1);
	return calculated_fitness;
}

// Fintness sigma
double sum_of_fitness(double * fitness_values, int population_size) {
	double sum_of_fitness = 0.0;
	for ( int i = 0 ; i < population_size ; i ++)
	{
		sum_of_fitness += fitness_values[i];
	}
	return sum_of_fitness;
}

// Normalization
void normalize_fitness( double * fitness_values, int population_size, double sum_of_fitness ){
	fitness_values[0] = fitness_values[0] / sum_of_fitness;
	for ( int i = 1 ; i < population_size ; i ++)
	{
		fitness_values[i] = fitness_values[i-1] + (fitness_values[i] / sum_of_fitness);
	}
}