Genetic Algorithm

Comment:

All of the following are related to Genetic Algorithms (GAs).

• How to ensure that a better solution can always be found in the next generation?
• How does a computer evaluate the “fitness” of a chromosome?
• Depending on the encoding scheme chosen (e.g., using a bit string to represent whether or not a link is selected in a path), it is possible that a lot of invalid solutions are included in the chromosome population. Will this actually decrease the efficiency of the GA?

Follow-up:

First of all, there is no way we can guarantee a better solution to be found in a new generation. In a sense, the crossover and mutation operators serve as “random” searching tools in a vast solution space. With luck we might be able to derive a better solution; otherwise, we will end up getting worse solutions in a new generation. Then, using the selection step, the newly obtained worse solutions might get weeded out. Thus, in a practical GA, we usually employ the “elitism” policy, i.e., although the currently best solution is still subject to crossover and mutation, it will be explicitly “protected” in that a copy of it will be retained for the next generation.

The “fitness” of a chromosome is really just the metric we define for a potential solution. For instance, in the case of the shortest path problem, we can define the fitness of a chromosome to be the length of the path (if it is a valid path).

Yes including a lot of invalid solutions can possibly decrease the efficiency (in terms of the

convergence time) to find the best possible solution. However, doing so could also help the “exploratory” side of the GA because the invalid solutions might also contain some “good

components” (i.e., good genes in a bad chromosome) so that through crossover, such good components might get passed on to some valid solutions in new generations.

I have also enclosed a research paper that I co-authored many years ago about using a GA for multiprocessor task scheduling. Hope you would be able to find time to glance through it to see another example of encoding scheme, the design of crossover and mutation operators, and most importantly, the performance of the GA.