The way
genetic algorithms work is not accidentally similar to the phenomenon of
biological evolution, since it is biology where the creator of the algorithms
John Henry Holland found his inspiration. Genetic
algorithm works on population of units: where: n
is the number of the population, whereas R stands for its size. Genetic
algorithms in their classic form do not in any way use the knowledge on the the problem solved. It is the fact that the better units
from the previuos generation get to every next
population, and that genetic operators exchange information included in the units,thus creating new, potantially better solutions, that the algorithms find the
solutions. The process of creating of a new population is depicted below.
- systems of adaptation / adaptative
systems -> Genetic Algorithms
Michalewicz
( ‘Genetic
algorithms + data structures = evolution programmes’ Buller (ATR, Kioto, Japan) Sztuczny mózg. To już nie fantazje”
Genetic
algorithms are used to solve problems connected with optimalization,
recognizing images, predicting movements on the stock exchange, creating
computer graphic as well as projects of buildings and machines.
**Chromosome**– it’s for example a string of bits. Every bit is representing single “gene” for example Women Man**Recombination**(or**crossover**) – it’s random operation witch cuts two of chromosomes which are recombinating in the same point and switch the parts of cut chromosomes. It’s important that “kids” are taking parents place.
11010010 ↓↑ - recombination 00100101 ↓↓ -Two New chromosomes: 11010101 00100010 **Mutating**– inverting one or more random bit.
↓ - mutation 10010111 10110111 – chromosome after mutation. **Selection****to crossover is random****Roulette weel method -**which are selecting the probability of choosing every chromosome. The method is based on one function.**Line rank –**this method is almost similar than the above but the function is different to every chromosome**Tournament –**much different than the other two methods, it’s based on random selection from all the population few chromosomes and from this group selected is the most valuable unit. The all tournament is needed to be repeated until new population is made.
·
·
In the Travelling
Salesman Problem, the goal is to find the shortest distance between N different
cities. Testing every possibility for an N city tour would be N! math additions. A 30 city tour would be 2.65 X 1032 additions. Assuming 1 billion additions per second, this would take over 8,000,000,000,000,000 years. Adding one more city would cause the number of additions to increase by a factor of 31. Obviously, this is an impossible solution. A genetic algorithm can be used to find a solution is much less time. Although it probably will not find the best solution, it can find a near perfect solution in less than a minute. There are two basic steps to solving the travelling salesman problem using a GA. First, create a group of many random tours in what is called a population. These tours are stored as a sequence of numbers. Second, pick 2 of the better (shorter) tours parents in the population and combine them, to create 2 new solutions children in the hope that they create an even better solution. The idea of Genetic Algorithms is to simulate the way nature uses evolution. The good solutions reproduce to form new and hopefully better solutions in the population, while the bad solutions are removed. The difficulty in the TSP using a GA is encoding the solutions. The encoding cannot simply be the list of cities in the order they are travelled. As shown below, the crossover operation will not work. The crossover point is the 3rd number
As you can see, the city 1 is used twice and
city 5 is missing in child ReferencesDavid E. „Algorytmy genetyczne i ich zastosowania” M. J. Kasperski, „Sztuczna Inteligencja. Droga do myślących maszyn” Simon Haykin "Neural Networks A Comprehensive Foundation, New Jersey 1999 Adnrzej Kos, Wykład "Przemysłowe zastosowania sztucznej inteligencji", 2003/2004 |
||||||||||

Maciej Misiak Krzysztof Nalepka mgr inż. Adam Gołda Katedra Elektroniki AGH |