Genetic Algorithm

A simple genetic algorithm, It follows the Inman Harvey's microbial genetic algorithm.

Problem:

You have 10 cards numbered from 1 to 10. You have to choose a way of dividing them into 2 piles, so that the cards in Pile_0 *sum* to a number as close as possible to 36, and the remaining cards in Pile_1 *multiply* to a number as close as possible to 360.


Solution:


// CardProblembyGA.cpp : Defines the entry point for the console application.
#include "stdafx.h"
//#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <conio.h>

#define POP 1000
#define LEN 10
#define REC 0.5
#define MUT 0.1
#define END 1000

#define TARGET_SUM 36
#define TARGET_PROD 360

#define RANDOM_NUM ((float)rand()/(RAND_MAX+1))

void init_pop(char gene[POP][LEN]);
double evaluate(char gene[LEN]);
void display(char gene[LEN]);

int _tmain(int argc, _TCHAR* argv[])
{
char gene[POP][LEN];
int Winner, Loser, temp1, temp2;
bool WinnerFound = false;

srand((int)time(NULL));
init_pop(gene);
for(int t=0;t<END && !WinnerFound;t++){
temp1 = (int) (POP * RANDOM_NUM);
temp2 = (int) (POP * RANDOM_NUM);
if(evaluate(gene[temp1]) < evaluate(gene[temp2])){
Winner = temp1;
Loser = temp2;
}
else {
Winner = temp2;
Loser = temp1;
}

for(int i=0;i<LEN;i++){
if(RANDOM_NUM < REC)
gene[Loser][i] = gene[Winner][i];
if(RANDOM_NUM < MUT)
gene[Loser][i] = gene[Loser][i]=='1' ? '0':'1';

if(evaluate(gene[Loser]) == 0.0){
printf("\nIdeal condtion found on %d tournaments...", t);
//WinnerFound = true;
display(gene[Loser]);
break;
}
}
}
/*if(!WinnerFound)
printf("Unable to find ideal condtion on %d tournaments...", END);*/
getche();
return 0;
}

void init_pop(char gene[POP][LEN])
{
for(int i = 0; i<POP; i++){
for(int j = 0; j<LEN; j++){
if(RANDOM_NUM > 0.5f)
gene[i][j] = '1';
else
gene[i][j] = '0';
}
}
}

double evaluate(char gene[LEN])
{
int sum = 0, prod = 1;
double sum_deviation, prod_deviation, combined_deviation;

for(int i=0;i<LEN;i++){
if(gene[i]=='1')
prod *=(i+1);
else
sum +=(i+1);
}
sum_deviation = ((double)(sum-TARGET_SUM))/TARGET_SUM;
prod_deviation = ((double)(prod-TARGET_PROD))/TARGET_PROD;
combined_deviation = abs(sum_deviation) + abs(prod_deviation);
return combined_deviation;
}

void display(char gene[LEN])
{
int x = 0;
printf("\n Product pile elements:");
for(int i=0;i<LEN;i++){
if(gene[i]=='1')
printf(" %d",i+1);
}
printf("\n Sum pile elements:");
for(int i=0;i<LEN;i++)
{
if(gene[i]=='0')
printf(" %d",i+1);
}
}