readme.txt

LinPacker是一个优化矩形布局的工具

Copyright 2001 by RG Software Corporation

http://www.rgsoftware.com


What is a Genetic Algorithm?

A Genetic Algorithm is solution that is used to estimate various
mathematical blackbox problems. In this example we use a Visual
Basic function named "BlackBox" (see frmMain). This function
accepts multiple parameters and after these numeric arguments
are added, subtracted, multiplied or divided, the BlackBox
function outputs a number. The Genetic Algorithm will attempt
to find out what goes on inside the function using evolutionary
techniques. Each solution is encoded in a bit string, which we
refer to as a chromosome. For instance, a chromosome consisting
of 32-bits (i.e. 11010010110101101010010110101110) can encode
genetic information about the solution. There are three major
processes in genetic algorithms:

1) Initialization
This process builds a few random chromosomes to start the population.

2) Fitness Calculation
In this process, the entire population of chromosomes are evaluated.
Each bit string is decoded from binary numbers into integers and then
these numbers are passed into the user-defined function for evaluation
(the "BlackBox" function) If the absolute value between the blackbox
function output and the chromosome is minimal, that chromosome is
rewarded with a higher chance of being a parent to other child chromosomes.

3) Crossover and mutation
After all chromosomes have been evaluated, it is time to randomly
select a mother and father. Crossover is the process in which two
randomly chosen chromosomes are swapped at a random point. For example:

Randomly chosen father chromosome: 11001010
Randomly chosen mother chromosome: 00101101
Randomly chosen point of crossover: 4
New child chromosome:    11001101

The child may undergo mutation, where a randomly chosen bit in the
chromosome is swapped with another randomly chosen bit.

In this example we are using a one-point crossover
(mother and father), however, many genetic algorithms exist that
have multiple crossovers.

It is important to note that not all chromosomes have an equal
chance of reproducing. Chromosomes which are more fit than others
have the highest probability of becoming a parent. (this is called
"roulette wheel" selection).

I hope you've enjoyed this short little story about genetic algorithms.

References:

The Genetic Algorithm Newsgroup
news://com.ai.genetic

The Genetic Algorithm F.A.Q.s
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/html/faqs/ai/genetic/top.html