At the forefront of Artificial Intelligence

Home » Articles » Genetic Algorithms » Projects

Box Optimization Project

Don't know how to use calculus to solve an optimization problem? The classic problem is optimizing a surface area of material to produce the maximum volume possible. I call this the 'box optimization' problem.

Outline

The chromosomes will consist of three floating-point values x, y, and z. Allow the user to enter in the value of the surface of initial material (80m², for example). To calculate the chromosomes use the following steps:

Look at the diagram to the right, from there you can figure that the equation for the box (no top) is: 2(xz) + 2(yz) + xy = surface area.
Generate two random numbers ([x,y] [y,z] or [x,z]).
Solve the above equation for the remaining variable.
Repeat until you complete your population.

The GA you use is up to you, experiment! See the guidelines for a few pointers.

Guidelines

Since genetic algorithms come in a huge range of varieties, it can be a daunting task to choose want you want. Probably the best advice I can give is not to choose a model, instead design one. Choose your reproduction method carefully since it will often make-or-break your GA.

For this problem, the reproduction method should probably use will take two values from high fitness chromosomes and generate the third value itself. Melanie Mitchell recommends use of elitism (save the highest fitness chromosomes for the next generation).

The population size is up to you, you can go fairly big since the chromosomes generated will all be valid (see below) and since it an optimization problem, you want to have a decent range.

Remember, that this project is supposed to teach you the basics of genetic algorithm theory - do not bother trying to optimize your GA since that often creates some additional behaviour that requires ironing out. For the moment, be happier with a working, slow algorithm than a fast, non-functional one!

Solutions

box-sibanc.zip (3Kb)	Solution submitted by Rok Sibanc. Good STL/C++ solution.
box-baker.zip (5Kb)	Solution submitted by Nathan Baker. Nice, neat C++ solution using a steady-state GA. Includes short write-up too.

Last Updated: 14/07/2003

Article Toolbar

BibTeX entry