What are good examples of genetic algorithms/genet

Question

Genetic algorithms (GA) and genetic programming (GP) are interesting areas of research.

I'd like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn't roll your own.

Questions:

• What problems have you used GA/GP to solve?
• What libraries/frameworks did you use?

I'm looking for first-hand experiences, so please do not answer unless you have that.

Answer 1

I used a GA to optimize seating assignments at my wedding reception. 80 guests over 10 tables. Evaluation function was based on keeping people with their dates, putting people with something in common together, and keeping people with extreme opposite views at separate tables.

I ran it several times. Each time, I got nine good tables, and one with all the odd balls. In the end, my wife did the seating assignments.

My traveling salesman optimizer used a novel mapping of chromosome to itinerary, which made it trivial to breed and mutate the chromosomes without any risk of generating invalid tours.

Update: Because a couple people have asked how ...

Start with an array of guests (or cities) in some arbitrary but consistent ordering, e.g., alphabetized. Call this the reference solution. Think of a guest's index as his/her seat number.

Instead of trying to encode this ordering directly in the chromosome, we encode instructions for transforming the reference solution into a new solution. Specifically, we treat the chromosomes as lists of indexes in the array to swap. To get decode a chromosome, we start with the reference solution and apply all the swaps indicated by the chromosome. Swapping two entries in the array always results in a valid solution: every guest (or city) still appears exactly once.

Thus chromosomes can be randomly generated, mutated, and crossed with others and will always produce a valid solution.

Answer 2

Several years ago I used ga's to optimize asr (automatic speech recognition) grammars for better recognition rates. I started with fairly simple lists of choices (where the ga was testing combinations of possible terms for each slot) and worked my way up to more open and complex grammars. Fitness was determined by measuring separation between terms/sequences under a kind of phonetic distance function. I also experimented with making weakly equivalent variations on a grammar to find one that compiled to a more compact representation (in the end I went with a direct algorithm, and it drastically increased the size of the "language" that we could use in applications).

More recently I have used them as a default hypothesis against which to test the quality of solutions generated from various algorithms. This has largely involved categorization and different kinds of fitting problems (i.e. create a "rule" that explains a set of choices made by reviewers over a dataset(s)).

Answer 3

A couple of weeks ago, I suggested a solution on SO using genetic algorithms to solve a problem of graph layout. It is an example of a constrained optimization problem.

Also in the area of machine learning, I implemented a GA-based classification rules framework in c/c++ from scratch.
I've also used GA in a sample project for training artificial neural networks (ANN) as opposed to using the famous backpropagation algorithm.

In addition, and as part of my graduate research, I've used GA in training Hidden Markov Models as an additional approach to the EM-based Baum-Welch algorithm (in c/c++ again).

Answer 4

First off, "Genetic Programming" by Jonathan Koza (on amazon) is pretty much THE book on genetic and evolutionary algorithm/programming techniques, with many examples. I highly suggest checking it out.

As for my own use of a genetic algorithm, I used a (home grown) genetic algorithm to evolve a swarm algorithm for an object collection/destruction scenario (practical purpose could have been clearing a minefield). Here is a link to the paper. The most interesting part of what I did was the multi-staged fitness function, which was a necessity since the simple fitness functions did not provide enough information for the genetic algorithm to sufficiently differentiate between members of the population.

Answer 5

I once used a GA to optimize a hash function for memory addresses. The addresses were 4K or 8K page sizes, so they showed some predictability in the bit pattern of the address (least significant bits all zero; middle bits incrementing regularly, etc.) The original hash function was "chunky" - it tended to cluster hits on every third hash bucket. The improved algorithm had a nearly perfect distribution.

Answer 6

I once tried to make a computer player for the game of Go, exclusively based on genetic programming. Each program would be treated as an evaluation function for a sequence of moves. The programs produced weren't very good though, even on a rather diminuitive 3x4 board.

I used Perl, and coded everything myself. I would do things differently today.