59.2. Генетические алгоритмы
Генетический алгоритм (ГА) реализует метод эвристической оптимизации, построенный на случайном поиске. В данном контексте множество возможных решений проблемы оптимизации называется популяцией особей. Степень адаптации особи к среде определяет функция приспособленности.
Координаты особи в пространстве поиска представляются хромосомами, которые по сути являются символьными строками. Фрагмент хромосомы, кодирующий значение одного оптимизируемого параметра, называется геном. Обычно ген кодируется в виде двоичного или целочисленного значения.
В результате симуляции эволюционных операций (скрещивания, мутации и селекции) данный алгоритм формирует новые поколения особей, у которых приспособленность в среднем будет выше, чем у их предшественников.
Как сказано в ответах на вопросы в группе comp.ai.genetic, нельзя не отметить, что ГА реализует не чисто случайный поиск решения проблемы. В ГА происходят вероятностные процессы, но результат явно оказывается не случайным (лучше случайного).
Рисунок 59.1. Диаграмма структуры генетического алгоритма
| P(t) | поколение предков на момент t |
| P''(t) | поколение потомков на момент t |
+=========================================+
|>>>>>>>>>>> Алгоритм ГА <<<<<<<<<<<<<<|
+=========================================+
| ИНИЦИАЛИЗАЦИЯ t := 0 |
+=========================================+
| ИНИЦИАЛИЗАЦИЯ P(t) |
+=========================================+
| вычислить ПРИСПОСОБЛЕННОСТЬ P(t) |
+=========================================+
| пока не выполняется УСЛОВИЕ ОСТАНОВКИ |
| +-------------------------------------+
| | P'(t) := СКРЕЩИВАНИЕ{P(t)} |
| +-------------------------------------+
| | P''(t) := МУТАЦИЯ{P'(t)} |
| +-------------------------------------+
| | P(t+1) := СЕЛЕКЦИЯ{P''(t) + P(t)} |
| +-------------------------------------+
| | вычислить ПРИСПОСОБЛЕННОСТЬ P''(t) |
| +-------------------------------------+
| | t := t + 1 |
+===+=====================================+59.2. Genetic Algorithms
The genetic algorithm (GA) is a heuristic optimization method which operates through randomized search. The set of possible solutions for the optimization problem is considered as a population of individuals. The degree of adaptation of an individual to its environment is specified by its fitness.
The coordinates of an individual in the search space are represented by chromosomes, in essence a set of character strings. A gene is a subsection of a chromosome which encodes the value of a single parameter being optimized. Typical encodings for a gene could be binary or integer.
Through simulation of the evolutionary operations recombination, mutation, and selection new generations of search points are found that show a higher average fitness than their ancestors.
According to the comp.ai.genetic FAQ it cannot be stressed too strongly that a GA is not a pure random search for a solution to a problem. A GA uses stochastic processes, but the result is distinctly non-random (better than random).
Figure 59.1. Structured Diagram of a Genetic Algorithm
| P(t) | generation of ancestors at a time t |
| P''(t) | generation of descendants at a time t |
+=========================================+
|>>>>>>>>>>> Algorithm GA <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0 |
+=========================================+
| INITIALIZE P(t) |
+=========================================+
| evaluate FITNESS of P(t) |
+=========================================+
| while not STOPPING CRITERION do |
| +-------------------------------------+
| | P'(t) := RECOMBINATION{P(t)} |
| +-------------------------------------+
| | P''(t) := MUTATION{P'(t)} |
| +-------------------------------------+
| | P(t+1) := SELECTION{P''(t) + P(t)} |
| +-------------------------------------+
| | evaluate FITNESS of P''(t) |
| +-------------------------------------+
| | t := t + 1 |
+===+=====================================+
