Search This Blog

Monday, February 23, 2009

Introduction to Genetic Algorithms with JGAP

Out of interest I am familiarizing myself in genetic algorithms, in short GA. My interest in GA came when I first heard about the JGAP project. As mentioned on the project's site "JGAP (pronounced "jay-gap") is a Genetic Algorithms and Genetic Programming component provided as a Java framework.". For a newcomer I found it difficult to get a good overview about all the concepts introduced in genetic algorithms. Before diving into JGAP, I think it is essential that these concepts are well understood. This post is an introduction to genetic algorithms (GA) with JGAP and is explained with a concrete example. In one of my next posts I will demonstrate solving a problem with genetic programming (GP).

So what is a genetic algorithm? Given is the following definition from John R. Koza:

The genetic algorithm is a probabilistic search algorithm that iteratively transforms a set (called a population) of mathematical objects (typically fixed-length binary character strings), each with an associated fitness value, into a new population of offspring objects using the Darwinian principle of natural selection and using operations that are patterned after naturally occurring genetic operations, such as crossover (sexual recombination) and mutation.

In genetic algorithms, a potential solution is called a chromosome. A chromosome consists of a fixed length of genes. A gene is a distinct component of a potential solution. During the evolution of the genetic algorithm, multiple solutions (chromosomes) are combined (crossover and mutation) to form, potentially, better solutions. The evolution is done over a population of solutions. The population of solutions is called a genotype and consists of a fixed-length of chromosomes. During each evolution, natural selection is applied to determine which solutions (chromosomes) make it to the next evolution. The input criteria for the selection process is the so-called fitness of a potential solution. Solutions with a better fitness value are more likely to appear in the next evolution than solutions with a worse fitness value. The fitness value of a potential solution is determined by a user-supplied fitness function.

Although it is possible to implement the above concepts yourself, JGAP already took care of this. Because the best way to learn is by example, let me first introduce the problem domain which I am going to solve with genetic algorithms. During the example, the concepts mentioned above are further clarified.

Consider a moving company which is specialized in moving boxes (with things in it) from one location to another. These boxes have varying volumes. The boxes are put in vans in which the boxes are moved from location to location. To reduce transport costs, it is crucial for the moving company to use as minimal vans as possible. Problem statement: given a number of boxes of varying volumes, what is the optimal arrangement of the boxes so that a minimal number of vans is needed? The following example shows how to solve this problem with genetic algorithms and JGAP.

First: with the arrangement of the boxes I mean the following: consider 5 boxes with the following volumes (in cubic meters): 1,4,2,2 and 2 and vans with a capacity of 4 cubic meters. When the boxes are put in the vans based on the initial arrangement, the distribution of the boxes in the vans is like this:
VanBoxesSpace wasted
Van 1Box 13
Van 2Box 40
Van 3Box 2, Box 20
Van 4Box 22
Fitness value = 3+2 * 4 = 20. See section fitness function for an explanation of the fitness function for this particular problem.

A total of 4 vans is needed. But when the number of vans needed is calculated, which is the total volume of the boxes divided by the volume of the vans, the optimal number of vans is: 11 / 4 = 2.75. Because no partial vans can be used the optimal number of vans needed is 3. The optimal arrangement of the boxes is the following: 1,2,2,2,4. Based on this arrangement the distribution looks like this:
VanBoxesSpace wasted
Van 1Box 1, Box 21
Van 2Box 2, Box 20
Van 3Box 40
Fitness value of 1 * 3 = 3.

Before implementing the actual solution, the following preparatory steps must be taken. These preparatory steps are always needed if genetic algorithms is used to solve a particular problem.

  1. Define the genetical representation of the problem domain. The boxes which must be put in the vans are represented by an array of Box instances. The genetic algorithm must find the optimal arrangement in the array as how to put the boxes in the vans. A chromosome is a potential solution and consists of a fixed-length of genes. A potential solution in this example consists of a list of indexes where each index represents a Box in the box array. To represent such index, I use an IntegerGene. As mention earlier, a gene is a distinct part of the solution. In this example, a solution (chromosome) consists of as many genes as there are boxes. The genes must be ordered by the genetic program in such a way that it represents a (near) optimal arrangement. For example: if there are 50 boxes, a chromosome with 50 IntegerGene's is constructed, where each gene's value is initialized to an index in the box array, in this case from 0 to 49.
  2. Determine the fitness function. The fitness function determines how good a potential solution is compared to other solutions. In this problem domain, a solution is fitter when fewer vans are needed so less space is wasted.
  3. Determine the parameters used for the run. For the run I use a population size of 50 and a total number of 5000 evolutions. So the genotype (the population) initially consists of 50 chromosomes (potential solutions). These values are chosen based on some experimentation and can vary based on the specific problem.
  4. Determine the termination criteria. The program ends when 5000 evolutions are reached or when the optimal number of vans needed is reached. The optimal number of vans can be calculated by dividing the total volume of the boxes by the capacity of the vans and rounding the result up (because no partial vans can be used).
Initialization
The Box class has a volume. In this example 125 boxes are created with varying volumes between 0.25 and 3.00 cubic meters. The boxes are stored in an array. The following code creates the boxes:
Random r = new Random(seed);
this.boxes = new Box[125];
for (int i = 0; i < 125; i++) {
Box box = new Box(0.25 + (r.nextDouble() * 2.75));
box.setId(i);
this.boxes[i] = box;
}

Before we configure JGAP we must first implement a fitness function. The fitness function is the most important part in genetic algorithms as it determines which populations potentially make in to the next evolution. The fitness function for this problem looks like this:
package nl.jamiecraane.mover;

import org.jgap.FitnessFunction;
import org.jgap.IChromosome;

/**
* Fitness function for the Mover example. See this
* {@link #evaluate(IChromosome)} for the actual fitness function.
*/
public class MoverFitnessFunction extends FitnessFunction {
private Box[] boxes;
private double vanCapacity;

public void setVanCapacity(double vanCapacity) {
this.vanCapacity = vanCapacity;
}

public void setBoxes(Box[] boxes) {
this.boxes = boxes;
}

/**
* Fitness function. A lower value value means the difference between the
* total volume of boxes in a van is small, which is better. This means a
* more optimal distribution of boxes in the vans. The number of vans needed
* is multiplied by the size difference as more vans are more expensive.
*/
@Override
protected double evaluate(IChromosome a_subject) {
double wastedVolume = 0.0D;

double sizeInVan = 0.0D;
int numberOfVansNeeded = 1;
for (int i = 0; i < boxes.length; i++) {
int index = (Integer) a_subject.getGene(i).getAllele();
if ((sizeInVan + this.boxes[index].getVolume()) <= vanCapacity) {
sizeInVan += this.boxes[index].getVolume();
} else {
// Compute the difference
numberOfVansNeeded++;
wastedVolume += Math.abs(vanCapacity - sizeInVan);
// Make sure we put the box which did not fit in this van in the next van
sizeInVan = this.boxes[index].getVolume();
}
}
// Take into account the number of vans needed. More vans produce a higher fitness value.
return wastedVolume * numberOfVansNeeded;
}
}

The above fitness function loops through all the genes in the supplied potential solution (where each gene in the chromosome represents an index in the box array) and calculates how many vans are needed for this arrangement of boxes to fit in the vans. The fitness value is based on the space wasted in every van when a new van is needed, called the wasted volume. The total volume wasted is multiplied by the number of vans needed. This is done to create a much worse fitness value when more vans are needed. In the above, simplified, example the fitness value of the first solution is 20 and the fitness value of the second, optimal, solution is 3. One term deserves more explanation and that is allele. In the above code the getAllele method on the gene is called. Allele is just another word for the value of the gene. Because all genes all IntegerGene's, the value of each gene is of type Integer.

Next it is time to setup JGAP:
private Genotype configureJGAP() throws InvalidConfigurationException {
Configuration gaConf = new DefaultConfiguration();
// Here we specify a fitness evaluator where lower values means a better fitness
Configuration.resetProperty(Configuration.PROPERTY_FITEVAL_INST);
gaConf.setFitnessEvaluator(new DeltaFitnessEvaluator());

// Only use the swapping operator. Other operations makes no sense here
// and the size of the chromosome must remain constant
gaConf.getGeneticOperators().clear();
SwappingMutationOperator swapper = new SwappingMutationOperator(gaConf);
gaConf.addGeneticOperator(swapper);

// We are only interested in the most fittest individual
gaConf.setPreservFittestIndividual(true);
gaConf.setKeepPopulationSizeConstant(false);

gaConf.setPopulationSize(50);
// The number of chromosomes is the number of boxes we have. Every chromosome represents one box.
int chromeSize = this.boxes.length;
Genotype genotype;

// Setup the structure with which to evolve the solution of the problem.
// An IntegerGene is used. This gene represents the index of a box in the boxes array.
IChromosome sampleChromosome = new Chromosome(gaConf, new IntegerGene(gaConf), chromeSize);
gaConf.setSampleChromosome(sampleChromosome);
// Setup the fitness function
MoverFitnessFunction fitnessFunction = new MoverFitnessFunction();
fitnessFunction.setBoxes(this.boxes);
fitnessFunction.setVanCapacity(VOLUME_OF_VANS);
gaConf.setFitnessFunction(fitnessFunction);

// Because the IntegerGenes are initialized randomly, it is neccesary to set the values to the index. Values range from 0..boxes.length
genotype = Genotype.randomInitialGenotype(gaConf);
List chromosomes = genotype.getPopulation().getChromosomes();
for (Object chromosome : chromosomes) {
IChromosome chrom = (IChromosome) chromosome;
for (int j = 0; j < chrom.size(); j++) {
Gene gene = chrom.getGene(j);
gene.setAllele(j);
}
}

return genotype;
}



In the above code we setup the JGAP library. The provided Javadoc should be self-explanatory. A population (genotype) of 50 potential solutions (chromosomes) is created where every chromosome consists of the same number of genes as there are boxes. Because in this example a lower fitness value is better, theDeltaFitnessEvaluator is used.

Next, it is time to evolve the population. The population is evolved 5000 times. When the optimal amount of vans is reached earlier, the run ends. The following code demonstrates the evolution of the problem solution:
private void evolve(Genotype a_genotype) {
int optimalNumberOfVans = (int) Math.ceil(this.totalVolumeOfBoxes / VOLUME_OF_VANS);
LOG.info("The optimal number of vans needed is [" + optimalNumberOfVans + "]");

double previousFittest = a_genotype.getFittestChromosome().getFitnessValue();
numberOfVansNeeded = Integer.MAX_VALUE;
for (int i = 0; i < NUMBER_OF_EVOLUTIONS; i++) {
if (i % 250 == 0) {
LOG.info("Number of evolutions [" + i + "]");
}
a_genotype.evolve();
double fittness = a_genotype.getFittestChromosome().getFitnessValue();
int vansNeeded = this.numberOfVansNeeded(a_genotype.getFittestChromosome().getGenes()).size();
if (fittness < previousFittest && vansNeeded < numberOfVansNeeded) {
this.printSolution(a_genotype.getFittestChromosome());
previousFittest = fittness;
numberOfVansNeeded = vansNeeded;
}

// No more optimal solutions
if (numberOfVansNeeded == optimalNumberOfVans) {
break;
}
}
IChromosome fittest = a_genotype.getFittestChromosome();

List<Van> vans = numberOfVansNeeded(fittest.getGenes());
printVans(vans);
this.printSolution(fittest);
}

Because we set the preserveFittest property on the JGAP configuration object to true, we have access to the most fittest chromosome with the getFittestChromosome() method. The fittest chromosome consists of 125 genes, the indexes of the boxes in the array, in the arrangement of how to put the boxes in the vans. The actual evolution is performed by JGAP. The fitness value determines which populations have the highest chance to make it to the next evolution. Eventually a (near) optimal solution is formed. This indicates the importance of a well chosen fitness function as it is used in the selection process of the chromosomes. Below is the output of a sample run:
The total volume of the [125] boxes is [210.25989987666645] cubic metres.
The optimal number of vans needed is [49]
Number of evolutions [0]
Fitness value [4123.992085987977]
The total number of vans needed is [63]
Fitness value [3458.197333300851]
The total number of vans needed is [61]
Fitness value [3138.2899569572887]
The total number of vans needed is [60]
Fitness value [2865.5105375433063]
The total number of vans needed is [59]
Fitness value [2562.282028584251]
The total number of vans needed is [58]
Fitness value [2267.7135196251966]
The total number of vans needed is [57]
Fitness value [1981.8050106661412]
The total number of vans needed is [56]
Fitness value [1704.5565017070858]
The total number of vans needed is [55]
Fitness value [1479.769464870246]
The total number of vans needed is [54]
Number of evolutions [250]
Fitness value [1215.9278601031112]
The total number of vans needed is [53]
Fitness value [1002.6487336510297]
The total number of vans needed is [52]
Number of evolutions [500]
Fitness value [774.5352329142294]
The total number of vans needed is [51]
Number of evolutions [750]
Number of evolutions [1000]
Fitness value [535.1696373214758]
The total number of vans needed is [50]
Number of evolutions [1250]
Number of evolutions [1500]
Number of evolutions [1750]
Number of evolutions [2000]
Number of evolutions [2250]
Fitness value [307.8713731063958]
The total number of vans needed is [49]
Van [1] has contents with a total volume of [4.204196540671411] and contains the following boxes:
Box:0, volume [2.2510465109421443] cubic metres.
Box:117, volume [1.9531500297292665] cubic metres.
Van [2] has contents with a total volume of [4.185233471369987] and contains the following boxes:
Box:17, volume [1.0595047801111055] cubic metres.
Box:110, volume [0.5031165156303853] cubic metres.
Box:26, volume [2.6226121756284955] cubic metres.
Van [3] has contents with a total volume of [4.312990612147265] and contains the following boxes:
Box:91, volume [1.8897555340430203] cubic metres.
Box:6, volume [2.423235078104245] cubic metres.
...Further output omitted

As seen in the above output, the optimal number of vans is reached between 2250 and 2500 evolutions. The program also outputs the distribution of the boxes in the vans. The complete source code of the above example can be downloaded from http://code.google.com/p/jc-examples/. The down-loadable artifact is called ga-moving-example-1.0.jar.

Conclusion
Genetic algorithms and programming is an exciting technology but with a lot of concepts which are hard to grasp if you are new to the field. This post is an introduction of the concepts for genetic algorithms and showed how to implement a GA solution with JGAP. In one of my next posts, genetic programming is explained with a concrete example.

The silver bullet rule applies to genetic algorithms as well. To give you an impression, the following problems are good candidates to solve with GA:
  • Problems where it is hard to find a solution but once a solution is found, measure how good this particular solution is.
  • Problems where the search space is very large, complex or poorly understood.
  • Problems where a near optimal solution is acceptable.
  • Problems where no mathematical analysis is available.
Although I am not an expert on the subject, feel free to ask your questions and I will try to answer them as best as possible.

46 comments:

kusi said...

It was a nice introduction to someone familiar with general awareness of GA. You might want to make references to Bin Packing or Knapsack problem, which are both NP Hard.

jcraane said...

Thanks for the suggestion. I updated the resources section to include references to these problems. The bin packing problem is quite similar to the problem I demonstrate in my post.

Anonymous said...

Great article and explanation!

Please consider setting the link to JGAP in your link section: http://jgap.sf.net

In some place you wrote GAP or JGap instead of JGAP, maybe you may want to correct this.

jcraane said...

The link to JGap apparently did not work properly. I fixed this. I Also changed GAP to genetic algorithms.

Nachiket said...

Good article Jamie,
I am looking for solution to specific problem, and i read JGap introduction few months ago. And i think i'll be able to solve the problem ,and i got link to your blog article from JGap website...

I need help in understanding whether it is possible to use GA or not?? (i think it is not)...

Here is my problem..

Same set of events (crane movement-start & movement-stopped) is recorded by 2 different type of devices, My list of events will be like..

1: StartTime,StopTime, MOVING
2: StartTime,StopTime, STOPPED
3: StartTime,StopTime, MOVING

I'll have list for both devices which are running on difference computers..Now it is possible that one device is malfunctioning, and i want to align list of events based on data.. So i can know that event 33 of Device_A is aligned with event 66 of Device_B and then i can take time difference from aligned event and find out actual event.. (user wants to find that what is the position on crane at given time)

I want to use GA to find out possible aligned event..

Please ask more, if you have any doubt or need more information..

Regards,
Nachiket

jcraane said...

Hello Nachiket,

As I understand it correctly you have two different lists with the same type of events generated by two different devices. The event indicates the start- and stoptime of a specific action. I presume the moving speed is constant. Is this correct?

Just for my understanding: do the two computers operate different devices?

Can you show me a small example of the list of events. Based on this data can you give me an example of how to manually find the aligned event in some small amount of data? Maybe we can then figure out if we can represent this solution genetically and how to define a fitness function which determines how good this solution is. If it is not possible to define a genetical representation than GA might not be applicable for this particular problem.

Regards,
Jamie

Nachiket said...

Hi Jamie,
Yes, most of your understanding is correct.

Speed is not constant,
but one of the device (Laser) which provides data in Millimeter precision of Crane's current position, data output speed is 1 sec. So you assume that i have data for each second about position of crane.

One device is connected to Server, and other device is connected to Crane computer. These device produce data (like Mouse,Computer) ..

Let me explain it with example.
First list:
1-> (10:30:05, 10:30:55, MOVING) 50
2-> (10:30:55, 10:31:20, STEADY) 25
3-> (10:31:20, 10:32:20, MOVING) 60
4-> (10:32:20, 10:33:00, STEADY) 40
5-> (10:33:00, 10:34:30, MOVING) 90

Second list:
1-> (11:15:05, 11:15:25, MOVING) 20
1-> (11:15:25, 11:15:30, STEADY) 5
1-> (11:15:30, 11:15:55, MOVING) 25
2-> (11:15:55, 11:16:18, STEADY) 23
3-> (11:16:18, 11:16:27, MOVING) 9
3-> (11:16:27, 11:16:31, STEADY) 4
3-> (11:16:31, 11:17:22, MOVING) 51
4-> (11:17:23, 11:18:06, STEADY) 44
5-> (11:18:06, 11:19:28, MOVING) 88

In second list, No of events are more, but it covers same time gap (Yes few seconds different can be there),

Some events are not generated in list 1, as One device is more sensitive and sophisticated, but still i cannot rely on any of the device for taking data as a master.

If i want to make a normal algorithm, it is going to be very complicated like No of events can be more or less, or few seconds difference can be there.

I hope it helped in understanding my problem better,

Cheers,
Nachiket

jcraane said...

Hi Nachiket,

After some further thoughts I don't think this is a suitable problem for solving by genetic algorithms. With this problem you have two (fixed) lists which you want to align. Even if we could form this problem to use GA, GA not always find the optimal solution. I think in this case you would want the optimal solution. Correct me if I am wrong.

Maybe you can try a graphical approach by drawing both lists on a timescale and see where they overlap.

Regards,
Jamie

Nachiket said...

Hi jamie,
You are right,
Problem we are trying to solve is having a single and specific solution, it is not optimization. And GA make sense when we have to select between this way or that way.. right?

Thanks for your support. [& i learned a bit more about GA. :) ]

Regards,
Nachiket

Kurt Junshean Espinosa said...

Hi Jamie!

Thanks for the article. I need your advice.Basically, I have a spectrum of values, say from 2.2 - 5.8. Now, I would like to find out how many times should I divide the spectrum of values so that I could maximize the accuracy. Can I use GA to find out the optimal boundary values, say if there for example 3 intermediate values (e.g. 3.6, 4.2, 5.2)?

Thank you very much.

jcraane said...

Hi Kurt,

I do not understand your problem completely. Can you give me a short, but complete, example of the problem you are trying to solve and I will have a look at it.

I may be a good candidate for GA.

Regards,
Jamie

Kurt Junshean Espinosa said...

Thanks for your reply. Here is an example of the problem:
I want to implement a gender classification. Given is a list of speakers say speaker 1 to speaker 100. Each speaker has a certain value, for example their pitch. However in a gender say for males, we have a range of pitch, lowest to highest; and same for females. With that observation, I'd would like to create groups-low, med, high-for each gender. Now, I'd like GA to give me the boundary values of pitch for each group with the maximum classification accuracy. A specific example maybe this:
One of the possible range values would be:
Low: 0.2 - 1.5
Med: 1.51 - 3.7
High: 3.71 - 5.6

Can you suggest a way how to use GA to optimize these boundary values?

Thanks!

Kurt Junshean Espinosa said...

Hi Jamie,


In addition to my question, I'd like to know how I could set the range of the number of genes in JGAP?

Thanks a lot!

Kurt

jcraane said...

Hi Kurt,

As I understand it correctly the bounds must be chosen so that there are an equal number of speakers in each bound? Is this correct? Because I find this an interesting problem I created a little sample application with JGAP that finds those optimum bounds for a given number of speakers with a variety of pitches. This application should get you started on your problem. Please note that this is not production quality code, just an indication of how you can solve this specific problem with JGAP. You may need to adapt this example based on your specific needs.

The source code of the example can be found here: http://code.google.com/p/jc-examples/source/browse/#svn/trunk/pitch-classification-boundary/src

In JGAP you can specify a chromosome size which specifies the number of genes in a chromosome.

Regards,
Jamie

Kurt Junshean Espinosa said...

Hi Jamie,

Thank you very much for taking time to even code a sample app:)
Well, regarding the bounds, it is not necessary that the number of speakers be equal, rather that the accuracy of gender classification be maximum.
Regarding the second one,what I'd like also to know about JGAP genes is how to control the range of the number of genes being randomized. I had an experiment before where my chromosome size was 54; I only got between 25 - 35 number of genes in a chromosome. Is there a way to increase the range, for instance, 1-54 number of genes?

Thanks again.

Cheers!

Kurt

jcraane said...

Hi Kurt,

The size of the population can be set with the following statement:
gaConf.setPopulationSize(35);
which creates 35 chromosomes. The statement:
gaConf.setKeepPopulationSizeConstant(true);
specifies that the number of chromosomes stays fixed on 35.

To specify the number of genes in each chromosome you create your chromosomes as follows:
IChromosome sampleChromosome = new Chromosome(gaConf, new IntegerGene(gaConf), 50);
which creates chromosomes with 50 genes.

Hope this helps.

Regards,
Jamie

Ricidleiv said...

A corretion:
"Fitness value = 3+2 * 4 = 20 [...]"

the correct is:

"Fitness value = (3+2) * 4 = 20 [..]"

by the way, thanks for your post!!

Sandra said...

Hola,

Puedes porfavor enviarme un correo diciendome si podemos hblar de JGAP.
Gracias

Unknown said...

porfavor te puedes poner es contacto conmigo para realizarte unas preguntas de la herramineta JGAP, lo que sucede es que estoy tratando de implementar el problema TSP en JGAP y hay pasos que no entiendo.

Gracias
sandra.pachon@gmail.com
savipabe@hotmail.com

Unknown said...

Please, someone programmed the knapsack problem with API JGAP, I am having problems with KnapsackFitnessFunction. Please, if someone did, send me the e-mail --> mariocajuru@yahoo.com.br.

I am very grateful.

Mario Lucio.
Brazil.

Nachiket said...

Hi Jamie,
I got another opportunity to use JGAP :),
I have completed most of implementation of my application.

But, I wonder, if you have solution for following scenario...
In our application, There are some constraints which should not be broken in any case... and others are desired (i.e. less space wasting in each truck). Is there anyway to achieve this??

Right now i am giving too much higher value to constraints which should not be broken.. and lower values to constraints which are desired...

Cheers,

jcraane said...

Hi Nachiket,

Can you again give me a small example (or even some sample code) of what you are trying to achieve?

Regards,
Jamie

Nachiket said...

Hi Jamie, Its long.. sorry :)

We are developing system for stacking Circle Cylinder shape items on containers. (Like coin stack..)

And this problem have many constraints based on container type. (i.e Weight, Diameter, Type, Color)

We have defined these constraints into two categories . Hard and Soft (From analogy of JBoss Drools Solver, I tried it before JGAP)

Hard constraints are compulsory. If it does not fulfills then solution cannot be determined.
Soft constraints are constraints which should be optimized (I have set to Lower score means better score)

And Input will be “List of Containers” and “List of Cylinders”. Usual input will be 10 to 30 Cylinders and 4 to 8 containers
And Output should be filling up all the containers + [remaining unassigned cylinders] OR using all the cylinders
[AND Hard constraints must be adhered and soft constrains should be near to optimum]


Right now, I am giving Hard constraint much higher fitness then soft constraint. So if ONE hard constraint is broken then fitness will be say 30000, and if ONE soft constraint is broken then fitness will be 2500

Let me give you a hypothetical example for better understanding.
Circles:
C1[height: 5,diameter:6,group-A],
C2[height: 7,diameter:4,group-B] ,
C3[height: 3,diameter:3,group-D],
C4[height: 4,diameter:8,group-C],
C5[height: 2,diameter:6,group-A],
C6[height: 8,diameter:9,group-A],
C7[height: 3,diameter:2,group-D]
C8[height: 6,diameter:2,group-B]

Containers:
CON1[max-diameter:5, height: 10, max-capacity:3],
CON2[max-diameter:5, height: 10, max-capacity:3],
CON3[max-diameter:10, height: 8, max-capacity:3],
CON4[max-diameter:10, height: 8, max-capacity:3],

Hard Constraints
1. Container height
2. Container diameter
3. Max capacity

Soft Constraints
1. Minimum capacity wastage of containers
2. Lower diameter circle cannot be placed on higher diameter circle (i.e C3 on layer-1 and C2 on layer-2 should be avoided)
3. Circles with group [A,B] or [C,D] should be kept in one base. (i.e. rather than putting C1,C3 together prefer, C1,C5 together)

So in above detail, Input is CIRCLES + CONTAINERS and output should be (it’s just a representation, not a proper solution);
CON1 [0:C1, 1:C5,2:C6], (0,1,2 denotes layers)
CON2 [0:C2, 1:C4,2:C7],
CON3 [0:C3, 1:C5]
CON4 []

In this result, CON4 will be empty.. as there are no Circles available.
Sometimes in input number of circles are more around 30 and number of Containers are lesser (like 3 or 4) so, in that case.. elements list will remain unassigned.


So please suggest better options for my settings. Here is my configuration.
##I have used similar approach from your box loading problem.
Configuration gaConf = new DefaultConfiguration();
Configuration.resetProperty(Configuration.PROPERTY_FITEVAL_INST);
gaConf.setFitnessEvaluator(new DeltaFitnessEvaluator());
gaConf.getGeneticOperators().clear();
MutationOperator swapper = new SwappingMutationOperator(gaConf);
gaConf.addGeneticOperator(swapper);
gaConf.setPreservFittestIndividual(true);
gaConf.setKeepPopulationSizeConstant(false);
gaConf.setPopulationSize(getSizeOfPopulation());

IChromosome sampleChromosome = new Chromosome(config, new IntegerGene(config), chromozomeSize);
config.setSampleChromosome(sampleChromosome);
config.setFitnessFunction(getFitnessFunction());
Genotype genotype = Genotype.randomInitialGenotype(config);
List chromosomes = genotype.getPopulation().getChromosomes();
for (Object chromosome : chromosomes) {
IChromosome chrom = (IChromosome) chromosome;
for (int j = 0; j < chrom.size(); j++) {
Gene gene = chrom.getGene(j);
gene.setAllele(j);
}
}

Please provide your view and suggest other things also,
I am giving 1500 NUMBER_OF_EVOLUTION and 250 SIZE_OF_POPULATION..
But after 120 to 150 number of evolutions.. I do not get better fitness chromosome.

Regards,

jcraane said...

Hi Nachiket,

Thanks for the information. I'll try to look into it this or next week.

Regards,
Jamie

Anonymous said...

thanks for sharing this site. download lots of ebook from here

http://feboook.blogspot.com

Unknown said...

This was a great introduction to GA's. Futhermore I appreciate the
optimization example utilizing
boxes.

While reviewing the code, I noticed that there is a 'van' object that consistently is left out of the list when invoking
numberOfVansNeeded()...When # of boxes = 7, I have noticed this situation. The following method appears to resolve the problem:

private List numberOfVansNeeded(Gene[] genes) {
List vans = new ArrayList();
Van van = new Van(VOLUME_OF_VANS);
//A new van is needed
vans.add(van);
for (Gene gene : genes)
{
int index = (Integer) gene.getAllele();
if (!van.addBox(this.boxes[index]))
{
//At capatcity; create a new van!
van = new Van(VOLUME_OF_VANS);
van.addBox(this.boxes[index]);
}
if (!vans.contains(van))
{
vans.add(van);
}
}
return vans;
}

Please advise. I welcome your feeback!

Kostis said...

Hello Jamie,

I would like if it possible to give me some guide lines for creating a time schedule with genetic algorithms for a school.

Really looking forward to hearing from you.

Unknown said...

December 5, 2009
Margaritis
Hello Jamie
I am trying to compile and run GaHelloWold in Eclipce. I have created a project with name: helloworld, and under directory helloworld\ have created bin\ and src\ folders. Where and how must I put source files (two java files)from nl\jamiecraane\gahelloworld folder and the jgap.jar, log4j.jar files from lib\ folder?
Thanks

Kurt Junshean Espinosa said...

Hi,

I've been using JGAP for a time already. My question is about the number of genes generated for every chromosome. How does JGAP generates these numbers? For example, I have 54 genes but during the run I only see between 20-35 genes in every chromosome; nothing 1-20 or 35-50. Is it possible to modify the range of distribution?
Hope anyone could enlighten me on this.

Thanks,
Kurt

Unknown said...

Using JGAP I wish to have a fixed e.g 70% x-over of population. Please let me know if a double value crossoverRatePercent = 1.2 is corresponding to 1 / 1.2 = 0.833 that is 83,3% of population is crossovered ?
Also an integer value crossoverRate = 3 is corresponding to 1 / 3 = 0.33, that is 33,3% of population is crossovered ?
Thanks in advance

Unknown said...

Using JGAP I wish to have a fixed e.g 70% x-over of population. Please let me know if a double value crossoverRatePercent = 1.2 is corresponding to 1 / 1.2 = 0.833 that is 83,3% of population is crossovered ?
Also an integer value crossoverRate = 3 is corresponding to 1 / 3 = 0.33, that is 33,3% of population is crossovered ?
Thanks in advance

Anonymous said...

Thank you for your great article, that goes beyond the salesman problem :) with another real world example.

viagra online said...
This comment has been removed by a blog administrator.
Unknown said...

Nice introduction to someone not familiar with GA. I have a question.
Suppose my chromosome is an array of integer like
int [] schedules = {1,1,1,2,2,2,3,3,3,3};

i have a population of 100 and schedules are randomly shuffled, i.e {2,1,3,1,3,2,1,3,2,3}.... etc

for each schedule i calculate a fitness value.

Could you please show me how to setup the genotype?

jcraane said...

Hi Adit,

I think you can use the same algorithm as in my example with the boxes. So create a random initial genotype and alter the values of the gene's to set these to the values of your schedule.

Does that help?

Regards,
Jamie

happyuk said...

Interesting post. I am interested in applying Genetic Algorithms to all kinds of optimization problems encountered in telecoms.

See here for an example:

http://andyuk2010.blogspot.com/2011/06/genetic-algorithm-based-routing.html

maxim said...

Genetic programming axample for snake evolution:
http://www.youtube.com/watch?v=eEvPD0pPvrk

Anonymous said...

Thank you for your helpful post...
I am new to the subject so it is a bit overwhelming...but it's a good start...=)

Anonymous said...

Hi,

I have a question...

A typical problem has an objective function and a set of constraints..

For example
Min wasted volume
Subject to
the boxes fit in the van

I am a bit confused where to put the constraints, specially that I want the population in each evolution to abide to those constraints and produce feasible solutions...

So Do I put the constraints in the fitness evaluate function, or while setting up my initial chromosome or in the evolution...

I also need the cross over and mutation operators to produce legitimate solutions...so please where do I put the constraints?

Thank you =)

jcraane said...

Hi,

The fitness function defines how good a particular solution is compared to other solutions. In my example, the less space wasted, the better the solution.

In my example, to produce legitimate solutions, I only use the swapping operator. The genes in a solution represent an index in the array. Since the values of the genes are randomly initialized, I set the values of the genes to the array indices when I set up my initial genotype.

So to conclude: I have some constraints during the initial setup of the genotype. The fitness function evaluates the fitness of the solution. No additional constraints are implemented by the fitness function.

Hope this helps.

Regards,
Jamie

Bellevue Mall said...

cool stuff This words resonate with power and hope. Excellent! Keep it up: )

Viagra said...

This was a wonderful introduction to algorithms.

Anonymous said...

Hello Jamie,

Maybe nice to tell you that I referred to your blog a few times on a java-forum (http://www.java-forums.org/advanced-java/61552-using-jgap-evolve-music.html).

"Jodokus"

jcraane said...

Hi Jodokus,

Thanks for the referral. I saw that the corresponding post was about generating music with GA. Have you seen my other post: http://jcraane.blogspot.nl/2009/06/melody-composition-using-genetic.html where I use simple music theory to generate a melody with GA?

Regarding the fitness function. If you want some unit input I was thinking of let the user decide which generated melodies sound good and base new populations on them.

Or maybe use a neural network to train the fitness function based on existing music.

Regards,
Jamei

شركة دجلة بالمز said...

المجموعة الدولية
شركة مكافحة حشرات بجدة
شركة عزل خزانات بجدة

Blite said...

Nice post I actually had a question myself regarding this. I currently have a function and I want to minimze the function based on binary encoding for a range of x values. Could you pls maybe help me out if its is possible to do it the same way as you did and how would the selection and crossover and mutation processes look like.