13,094,001 members (53,928 online)
alternative version

#### Stats

202.6K views
132 bookmarked
Posted 8 Nov 2006

# AI - Simple Genetic Algorithm (GA) to solve a card problem

, 8 Nov 2006
 Rate this:
A simple Genetic Algorithm (GA) to solve a card problem.

## Introduction

### So what is the problem domain we are trying to solve?

Well, GAs can be used to solve many problems. In fact, GAs have been used to grow new mathematical syntax trees, train multi-layer neural networks, to name but a few instances.

However, for this example, I have used a simple card splitting excercise, which is as detailed here:

• You have 10 cards numbered 1 to 10
• You have to divide them into two piles so that:
• The sum of the first pile is as close as possible to 36.
• And the product of all in the second pile is as close as possible to 360.

Now, I am not saying that this could not be done by hand, using old fashioned brain juice, it's just better suited to a GA, as it could take 100s or even 1000s of different combinations to get the correct result. Well, probably not that many for this simple problem, but it certainly could take a lot of combinations for a more difficult problem. Suffice to say, it is just good fun to do it with a GA. So, let's carry on.

### So what is a Genetic Algorithm?

Well, Wikipedia says this:

A genetic algorithm is a search technique used in computing, to find true or approximate solutions to optimization and search problems, and is often abbreviated as GA. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).

Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes or the genotype or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves towards better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals, and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly mutated) to form a new population. The new population is then used in the next iteration of the algorithm.

Follow that?? If not, let's try a diagram. (Note that this is a Microbial GA, there are lots of GA types, but I just happen to like this one, and it's the one this article uses.)

I prefer to think of a GA as a way of really quickly (well, may be quite slow, depending on the problem) trying out some evolutionary programming techniques, that mother nature has always had.

### So how does this translate into an algorithm (this article uses a Microbial GA, but there are many other varieties)?

The basic operation of the Microbial GA training is as follows:

• Pick two genotypes at random
• Compare Scores (Fitness) to come up with a Winner and Loser
• Go along genotype, at each locus (Point)

That is:

• With some probability (randomness), copy from Winner to Loser (overwrite)
• With some probability (randomness), mutate that locus of the Loser

So only the Loser gets changed, which gives a version of Elitism for free, this ensures that the best in the breed remains in the population.

That's it. That is the complete algorithm.

But there are some essential issues to be aware of, when playing with GAs:

1. The genotype will be different for a different problem domain
2. The Fitness function will be different for a different problem domain

These two items must be developed again, whenever a new problem is specified.

For example, if we wanted to find a person's favourite pizza toppings, the genotype and fitness would be different from that which is used for this article's problem domain.

These two essential elements of a GA (for this article's problem domain) are specified below.

### 1. The Geneotype

```//the genes array, 30 members, 10 cards each
private int[,] gene = new int[30, 10];```

Well, for this article, the problem domain states that we have 10 cards. So, I created a two dimensional genes array, which is a 30*10 array. The 30 represents a population size of 30. I picked this. It could be any size, but should be big enough to allow some dominant genes to form.

### 2. The Fitness Function

Remembering that the problem domain description stated the following:

• You have 10 cards numbered 1 to 10
• You have to divide them into two piles so that:
• The sum of the first pile is as close as possible to 36.
• And the product of all in the second pile is as close as possible to 360.

Well, all that is being done is the following :

• Loop through the population member's genes
• If the current gene being looked at has a value of 0, the gene is for the sum pile (pile 0), so add to the running calculation
• If the current gene being looked at has a value of 1, the gene is for the product pile (pile 1), so add to the running calculation
• Calculate the overall error for this population member. If this member's geneotype has an overall error of 0.0, then the problem domain has been solved
```//evaluate the the nth member of the population
//@param n : the nth member of the population
//@return : the score for this member of the population.
//If score is 0.0, then we have a good GA which has solved
//the problem domain
private double evaluate(int n)
{
//initialise field values
int sum = 0, prod = 1;
double scaled_sum_error, scaled_prod_error, combined_error;
//loop though all genes for this population member
for (int i = 0; i < LEN; i++)
{
//if the gene value is 0, then put it in the sum (pile 0),
//and calculate sum
if (gene[n,i] == 0)
{
sum += (1 + i);
}
//if the gene value is 1, then put it in the product (pile 1),
//and calculate sum
else
{
prod *= (1 + i);
}
}
//work out how food this population member is, based on an overall error
//for the problem domain
//NOTE : The fitness function will change for every problem domain.
scaled_sum_error = (sum - SUMTARG) / SUMTARG;
scaled_prod_error = (prod - PRODTARG) / PRODTARG;
combined_error = Math.Abs(scaled_sum_error) + Math.Abs(scaled_prod_error);

return combined_error;
}            ```

## Using the code

The demo project attached actually contains a Visual Studio 2005 solution, with the following two classes.

#### Program class

Is the main entry point into the Simple_GeneticAlgorithm application. All this class does is create a new `Simple_GeneticAlgorithm` object and call its `run()` method.

```using System;
using System.Collections.Generic;
using System.Text;

namespace Simple_GeneticAlgorithm
{
class Program
{
//main access point
static void Main(string[] args)
{
//create a new Microbial GA
Simple_GeneticAlgorithm GA = new Simple_GeneticAlgorithm();
GA.run();
//read a line, to stop the Console window closing
}
}
}            ```

#### Simple_GeneticAlgorithm class

Runs the GA to solve the problem domain.

```using System;
using System.Collections.Generic;
using System.Text;

namespace Simple_GeneticAlgorithm
{
public class Simple_GeneticAlgorithm
{
//population size
private int POP = 30;
//geneotype
private int LEN = 10;
//mutation rate, change it have a play
private double MUT = 0.1;
//recomination rate
private double REC = 0.5;
//how many tournaments should be played
private double END = 1000;
//the sum pile, end result for the SUM pile
//card1 + card2 + card3 + card4 + card5, MUST = 36 for a good GA
private double SUMTARG = 36;
//the product pile, end result for the PRODUCT pile
//card1 * card2 * card3 * card4 * card5, MUST = 360 for a good GA
private double PRODTARG = 360;
//the genes array, 30 members, 10 cards each
private int[,] gene = new int[30, 10];
//used to create randomness (Simulates selection process in nature)
//randomly selects genes
Random rnd = new Random();

//empty constructor
public Simple_GeneticAlgorithm()
{
}

//Runs the Microbial GA to solve the problem domain
//Where the problem domain is specified as follows
//
//You have 10 cards numbered 1 to 10.
//You have to divide them into 2 piles so that:
//
//The sum of the first pile is as close as possible to 36
//And the product of all in second pile is as close as poss to 360
public void run()
{
//declare pop member a,b, winner and loser
int a, b, Winner, Loser;
//initialise the population (randomly)
init_pop();
//start a tournament
for (int tournamentNo = 0; tournamentNo < END; tournamentNo++)
{
//pull 2 population members at random
a = (int)(POP * rnd.NextDouble());
b = (int)(POP * rnd.NextDouble());
//have a fight, see who has best genes
if (evaluate(a) < evaluate(b))
{
Winner = a;
Loser = b;
}
else
{
Winner = b;
Loser = a;
}
//Possibly do some gene jiggling, on all genes of loser
//again depends on randomness (simulating the
//natural selection
//process of evolutionary selection)
for (int i = 0; i < LEN; i++)
{
//maybe do some recombination
if (rnd.NextDouble() < REC)
gene[Loser, i] = gene[Winner, i];
//maybe do some muttion
if (rnd.NextDouble() < MUT)
gene[Loser, i] = 1 - gene[Loser, i];
//then test to see if the new population member
//is a winner
if (evaluate(Loser) == 0.0)
display(tournamentNo, Loser);
}
}
}

//Display the results. Only called for good GA which has solved
//the problem domain
//@param tournaments : the current tournament loop number
//@param n : the nth member of the population.
private void display(int tournaments, int n)
{
Console.WriteLine("\r\n==============================\r\n");
Console.WriteLine("After " + tournaments +
" tournaments, Solution sum pile " +
"(should be 36) cards are : ");
for (int i = 0; i < LEN; i++) {
if (gene[n,i] == 0) {
Console.WriteLine(i + 1);
}
}
Console.WriteLine("\r\nAnd Product pile " +
"(should be 360)  cards are : ");
for (int i = 0; i < LEN; i++) {
if (gene[n,i] == 1) {
Console.WriteLine(i + 1);
}
}
}

//evaluate the the nth member of the population
//@param n : the nth member of the population
//@return : the score for this member of the population.
//If score is 0.0, then we have a good GA which has solved
//the problem domain
private double evaluate(int n)
{
//initialise field values
int sum = 0, prod = 1;
double scaled_sum_error, scaled_prod_error, combined_error;
//loop though all genes for this population member
for (int i = 0; i < LEN; i++)
{
//if the gene value is 0, then put it in
//the sum (pile 0), and calculate sum
if (gene[n,i] == 0)
{
sum += (1 + i);
}
//if the gene value is 1, then put it in
//the product (pile 1), and calculate sum
else
{
prod *= (1 + i);
}
}
//work out how food this population member is,
//based on an overall error
//for the problem domain
//NOTE : The fitness function will change
//       for every problem domain.
scaled_sum_error = (sum - SUMTARG) / SUMTARG;
scaled_prod_error = (prod - PRODTARG) / PRODTARG;
combined_error = Math.Abs(scaled_sum_error) +
Math.Abs(scaled_prod_error);

return combined_error;
}

//initialise population
private void init_pop()
{
//for entire population
for (int i = 0; i < POP; i++)
{
//for all genes
for (int j = 0; j < LEN; j++)
{
//randomly create gene values
if (rnd.NextDouble() < 0.5)
{
gene[i,j] = 0;
}
else
{
gene[i,j] = 1;
}
}
}
}
}
}```

### The results

Taking the last good population member results found, let's test it out.

```2 + 7 + 8 + 9 + 10 = 36 in Pile 0, this is all good
1 * 3 * 4 * 5 * 6 = 360 in Pile 1, this is all good```

## Points of Interest

I hope this article has demonstrated how to write a simple GA to solve a problem that we as humans would probably find hard to do manually. Remember this is a simple problem. what would happen if we upped the problem domain? A GA really is the way to go.

I will very shortly publish an article on a GA training a multi layer neural network to solve some logic problems. So if your'e into this sort of stuff, watch this space.

## History

• v1.0 - 08/11/06.

A list of licenses authors might use can be found here

## Share

 Software Developer (Senior) United Kingdom
I currently hold the following qualifications (amongst others, I also studied Music Technology and Electronics, for my sins)

- MSc (Passed with distinctions), in Information Technology for E-Commerce
- BSc Hons (1st class) in Computer Science & Artificial Intelligence

Both of these at Sussex University UK.

Award(s)

I am lucky enough to have won a few awards for Zany Crazy code articles over the years

• Microsoft C# MVP 2016
• Codeproject MVP 2016
• Microsoft C# MVP 2015
• Codeproject MVP 2015
• Microsoft C# MVP 2014
• Codeproject MVP 2014
• Microsoft C# MVP 2013
• Codeproject MVP 2013
• Microsoft C# MVP 2012
• Codeproject MVP 2012
• Microsoft C# MVP 2011
• Codeproject MVP 2011
• Microsoft C# MVP 2010
• Codeproject MVP 2010
• Microsoft C# MVP 2009
• Codeproject MVP 2009
• Microsoft C# MVP 2008
• Codeproject MVP 2008
• And numerous codeproject awards which you can see over at my blog

## You may also be interested in...

 First Prev Next
 Selection of certain criteria Member 1138386215-May-15 11:36 Member 11383862 15-May-15 11:36
 Wow, I learned so much!! mellertson23-Mar-14 20:59 mellertson 23-Mar-14 20:59
 Re: Wow, I learned so much!! Sacha Barber24-Mar-14 2:54 Sacha Barber 24-Mar-14 2:54
 I love You so much Eduardo Herrera Chávez13-Jun-13 23:47 Eduardo Herrera Chávez 13-Jun-13 23:47
 Re: I love You so much Sacha Barber24-Mar-14 2:53 Sacha Barber 24-Mar-14 2:53
 Project Tulasi 201215-Mar-12 18:18 Tulasi 2012 15-Mar-12 18:18
 How to use this GA to solve XOR Donald Allen2-Oct-11 15:08 Donald Allen 2-Oct-11 15:08
 very powerful darkking12321-Apr-11 20:43 darkking123 21-Apr-11 20:43
 5 stars sanjozko2-Feb-11 7:45 sanjozko 2-Feb-11 7:45
 Problem Domain kamal mahdavi17-Apr-10 17:20 kamal mahdavi 17-Apr-10 17:20
 I Got The Result In 30th trial By My Coding ashoks_cse29-Feb-08 21:44 ashoks_cse 29-Feb-08 21:44
 Re: I Got The Result In 30th trial By My Coding Sacha Barber29-Feb-08 21:50 Sacha Barber 29-Feb-08 21:50
 Re: I Got The Result In 30th trial By My Coding ashoks_cse29-Feb-08 23:00 ashoks_cse 29-Feb-08 23:00
 Re: I Got The Result In 30th trial By My Coding Sacha Barber29-Feb-08 23:50 Sacha Barber 29-Feb-08 23:50
 No result? zlyaksa20-Feb-08 16:02 zlyaksa 20-Feb-08 16:02
 Re: No result? qinjuan19858-Sep-11 23:34 qinjuan1985 8-Sep-11 23:34
 [Message Deleted] Danny Rodriguez27-Jan-08 9:09 Danny Rodriguez 27-Jan-08 9:09
 337 jinn_hnnl4-Sep-07 23:17 jinn_hnnl 4-Sep-07 23:17
 Re: 337 jinn_hnnl4-Sep-07 23:18 jinn_hnnl 4-Sep-07 23:18
 How chage program for solve SUM 60? Petersy13-Apr-07 6:35 Petersy 13-Apr-07 6:35
 Re: How chage program for solve SUM 60? Sacha Barber13-Apr-07 6:44 Sacha Barber 13-Apr-07 6:44
 Re: How chage program for solve SUM 60? Petersy14-Apr-07 23:02 Petersy 14-Apr-07 23:02
 Re: How chage program for solve SUM 60? Sacha Barber21-Apr-07 1:34 Sacha Barber 21-Apr-07 1:34
 thanks for clarification of GA ujjwalkmr17-Jan-07 5:34 ujjwalkmr 17-Jan-07 5:34
 Re: thanks for clarification of GA Sacha Barber17-Jan-07 6:13 Sacha Barber 17-Jan-07 6:13
 is this suitable to search large amount of data? f216-Dec-06 7:13 f2 16-Dec-06 7:13
 Re: is this suitable to search large amount of data? Sacha Barber16-Dec-06 9:48 Sacha Barber 16-Dec-06 9:48
 Possible generalization? narsyseth10-Nov-06 9:13 narsyseth 10-Nov-06 9:13
 Re: Possible generalization? Sacha Barber10-Nov-06 21:27 Sacha Barber 10-Nov-06 21:27
 Re: Possible generalization? narsyseth13-Nov-06 5:31 narsyseth 13-Nov-06 5:31
 Re: Possible generalization? Sacha Barber13-Nov-06 5:51 Sacha Barber 13-Nov-06 5:51
 Re: Possible generalization? narsyseth14-Nov-06 6:56 narsyseth 14-Nov-06 6:56
 Re: Possible generalization? [modified] Sacha Barber14-Nov-06 22:15 Sacha Barber 14-Nov-06 22:15
 Re: Possible generalization? narsyseth15-Nov-06 5:48 narsyseth 15-Nov-06 5:48
 Re: Possible generalization? Sacha Barber15-Nov-06 6:56 Sacha Barber 15-Nov-06 6:56
 Re: Possible generalization? narsyseth15-Nov-06 8:09 narsyseth 15-Nov-06 8:09
 Re: Possible generalization? Sacha Barber15-Nov-06 21:35 Sacha Barber 15-Nov-06 21:35
 Re: Possible generalization? margiex14-Dec-06 3:56 margiex 14-Dec-06 3:56
 Some suggestions ttliu8-Nov-06 16:33 ttliu 8-Nov-06 16:33
 Re: Some suggestions Sacha Barber8-Nov-06 21:21 Sacha Barber 8-Nov-06 21:21
 Re: Some suggestions Sacha Barber11-Dec-06 10:02 Sacha Barber 11-Dec-06 10:02
 Source code is missing TBermudez8-Nov-06 4:44 TBermudez 8-Nov-06 4:44
 Re: Source code is missing Sacha Barber8-Nov-06 5:07 Sacha Barber 8-Nov-06 5:07
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Aug-17 3:26 Refresh 1