GENETIC ALGORITHMS FOR SIMULATION OPTIMIZATION

GENETIC ALGORITHMS

Physics, Biology, Economy or Sociology often have to deal with the classical problem of optimization. Economy particularly has become specialist of that field1. Generally speaking, a large part of mathematical development during the XVIIIth century dealt with that topic (remember those always repeated problems where you had to obtain the derivative of a function to find its extremes). Purely analytical methods widely proved their efficiency.

EVOLUTION AND OPTIMIZATION

The Basilosaurus was quite a prototype of a whale. It was about 15 meters long for 5 tons. It still had a quasi-independent head and posterior paws. He moved using undulatory movements and hunted small preys3. Its anterior members were reduced to small flippers with an elbow articulation. Movements in such a viscous element (water) are very hard and require big efforts. People concerned must have enough energy to move and control its trajectory. The anterior members of basilosaurus were not really adapted to swimming. To adapt them, a double phenomenon must occur : the shortening of the "arm" with the locking of the elbow articulation and the extension of the fingers which will constitute the base structure of the flipper.

 

The image shows that two fingers of the common dolphin are hypertrophied to the detriment of the rest of the member. The basilosaurus was a hunter, he had to be fast and precise. Through time, subjects appeared with longer fingers and short arms. They could move faster and more precisely than before, and therefore, live longer and have many descendants. Meanwhile, other improvements occurred concerning the general aerodynamic like the integration of the head to the body, improvement of the profile, strengthening of the caudal fin ... finally producing a subject perfectly adapted to the constraints of an aqueous environment. This process of adaptation, this morphological optimization is so perfect that nowadays, the similarity between a shark, a dolphin or a submarine is striking. 

Darwinian mechanism hence generate an optimization process, Hydrodynamic optimization for fishes and others marine animals, aerodynamic for pterodactyls, birds or bats. This observation is the basis of genetic algorithms

EVOLUTION AND GENETIC ALGORITHMS

To improve the understanding of natural adaptation process, and to design artificial systems having properties similar to natural systems The basic idea is as follow : the genetic pool of a given population potentially contains the solution, or a better solution, to a given adaptive problem. This solution is not "active" because the genetic combination on which it relies is split between several subjects. Only the association of different genomes can lead to the solution. Simplistically speaking, we could by example consider that the shortening of the paw and the extension of the fingers of our basilosaurus are controlled by 2 "genes". No subject has such a genome, but during reproduction and crossover, new genetic combination occur and, finally, a subject can inherit a "good gene" from both parents : his paw is now a flipper. Holland method is especially effective because he not only considered the role of mutation (mutations improve very seldom the algorithms), but he also utilized genetic recombination, (crossover). These recombination, the crossover of partial solutions greatly improve the capability of the algorithm to approach, and eventually find, the optimum.

FUNCTIONING OF A GENETIC ALGORITHM

As an example, we're going to enter a world of simplified genetic. The "chromosomes" encode a group of linked features. "Genes" encode the activation or deactivation of a feature. Let us examine the global genetic pool of four basilosaurus belonging to this world. We will consider the "chromosomes" which encode the length of anterior members. The length of the "paw" and the length of the "fingers" are encoded by four genes : the first two encode the "paw" and the other two encode the fingers. In our representation of the genome, the circle on blue background depict the activation of a feature, the cross on green background depict its deactivation.