Genetic algorithms

I spent the weekend, again, studying. In addition to economics problems and reading and linear programming problems and reading, I've read 5 scholarly articles about genetic algorithms. This is the second optimization method we've studied; the first was simulated annealing. For example: A company is building a manufacturing plant and needs to decide how to physically place the stages of assembly on the plant floor. They know the overall size of the plant floor and each stage that needs to be placed on the floor. They also know how much interaction needs to take place between each stage and the amount of floor space that should be between each stage. The task is to design the plant floor so that it optimizes the interaction and distance between the stages. A similar example involves chip layout...how to put all of the components on a silicon chip so that they fit and the amount of wire needed to connect them appropriately is minimized. There are many similar problems in many different circumstances. This is called a quadratic assignment problem and is notoriously difficult to solve, particular when the size of the problem is large--hundreds of manufacturing stages or components. Both simulated annealing and genetic algorithms have been used to optimize these problems.

A genetic algorithm is based on the biology of genetics. Very simply--parent chromosomes (feasible solutions to the problem) combine to create children with different chromosomes (additional feasible solutions to the problem). The population is tested for fitness (how well the solutions optimize) and some members of the population are eliminated. There are different ways for the parents to mate, ways to mutate offspring, different ways to assess fitness and many other parameters that are manipulated to better ensure an optimal solution.

It is quite interesting. Now, I have the challenge of writing a computer program to use this strategy to solve a particular problem. This homework is due February 16. One of the things I'm trying to re-learn is budgeting my time so that I don't fall behind in anything. Unfortunately, I am finding that Allan's right, I'm not very good at budgeting!