Hello,
This is a GA implemented in c-script, and demonstrates solving a hard bin packing problem. For more information on Genetic Algorithms and the problem i attempt to solve,
read here.
Before downloading this, i would advise to learn a bit about GAs first, or none of this would make much sense. Do NOT attempt to learn how Genetic Algorithms work just by looking at my source code as this is the wrong way to learn.
If you've already done your research, and the following paragraphs makes some sense to you, you may now
download this program
Genetic Algorithms Supported:
Encoding
--------
k-ary
Algorithms
---------
steady-state
Hillclimbing
Selection
---------
k-ary tournament
replace-worst
Mutation operators
------------------
Single-gene new-allele
M-random-gene new-allele
probabilistic
Crossover operators
-------------------
one-point
two-point
uniform
The program is configured to run with steady-state binary tournament selection and replace-worst. It runs for 100,000 evaluations, with population size 10, single-new-allele mutation and uniform crossover, which has been proven to be the best configuration for the bin problem. The Fitness function is: (Heaviest Container - Lightest Container) + (Number of invalid type pairs * Total Weight of all items together(TW) )
While you run the program, you'll get a lousy screen like this, since i didn't had time to work on an interface (the whole thing took me a day)
After the GA is completed (100,000 evaluations will take a few minutes, reduce them if you're in a hurry), the program will shut down and you'll be able to see the results from the generated output files:
"Chromosome.txt"
"Containers.txt"
"ContainerWeights.txt"
Code:
ContainerWeights.txt
CONTAINER #0
Items: 15
Weight: 11977
CONTAINER #1
Items: 16
Weight: 11989
CONTAINER #2
Items: 21
Weight: 12077
CONTAINER #3
Items: 19
Weight: 11883
...
Again, don't bother on this unless you've a basic understanding of GAs, or none of this will make much sense. This contribution is to help people implement their own GAs to c-script, or even use my code for their own GA directed problems.
Cheers,
Aris
