Python Genetic Algorithm

[Steven D'Aprano]

On Mon, 28 Jan 2008 00:35:51 +0100, Wildemar Wildenburger wrote:

> Max wrote:
>> In GAs, you operate on a Population of solutions. Each Individual from
>> the Population is a potential solution to the problem you're
>> optimizing, and Individuals have what's called a chromosome - a
>> specification of what it contains. For example, common chromosomes are
>> bit strings, lists of ints/floats, permutations...etc. I'm stuck on how
>> to implement the different chromosomes. I have a Population class,
>> which is going to contain a list of Individuals. Each individual will
>> be of a certain chromosome. I envision the chromosomes as subclasses of
>> an abstract Individual class, perhaps all in the same module. I'm just
>> having trouble envisioning how this would be coded at the population
>> level. Presumably, when a population is created, a parameter to its
>> __init__ would be the chromosome type, but I don't know how to take
>> that in Python and use it to specify a certain class.
>> 
> I'm not sure I'm following you here. So a "chromosome" is bit of
> functionality, right? So basically it is a function. So my advice would
> be to write these functions and store it to the "indivuals"-list like
> so:

No, a chromosome is a bit of *data*: a noun, not a verb. Read these bits 
again:

"Individuals HAVE what's called a chromosome - a SPECIFICATION of what it 
contains. For example, common chromosomes are BIT STRINGS, ..."

Emphasis added. Sorry for the shouting.

Some background which may help you understand what the OP is asking for.

Genetic Algorithms simulate biological genetic process for problem 
solving. The basic idea is this: suppose you can find a way to encode 
possible solutions to a problem as a sequence in some sense. e.g. a 
sequence of Yes/No decisions might be 011001. That's the "Chromosome" the 
OP is talking about. Furthermore, suppose you can mutate such a solution: 
011001 might become 011011. Then, so long as some relatively common 
assumptions hold, you can zero in on a good solution by starting with a 
bad solution and incrementally improving it:

* start with a lot of bad or mediocre solutions
* pick the best solution in the population
* make lots of copies
* mutate the copies slightly
* now pick the best solution of them

Repeat until done.

The analogy is with the process of evolution, only very much simplified.

Such GAs are capable of finding solutions which people have never thought 
of. Sometimes those solutions are baroque and virtually unintelligible. 
Sometimes they're amazingly simple.

In one famous case, a hardware GA actually found a working electrical 
circuit which was not only smaller than any similar circuit that human 
engineers had found, but according to a naive understanding of 
electronics, it shouldn't have worked at all! It contained an open 
circuit, but removing the open circuit stopped the rest from working.


-- 
Steven