Классический генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:
- инициализация, или выбор исходной популяции хромосом;
- оценка приспособленности хромосом в популяции – расчет функции приспособленности для каждой хромосомы;
- проверка условия остановки алгоритма;
- селекция хромосом – выбор тех хромосом, которые будут участвовать в создании потомков для следующей популяции;
- применение генетических операторов – мутации и скрещивания;
- формирование новой популяции;
- выбор «наилучшей» хромосомы.
Блок-схема основного генетического алгоритма изображена на рисунке.
Простой генетический алгоритм случайным образом генерирует начальную популяцию. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении реализуется пропорциональный отбор по приспособленности, скрещивание и мутация.
Простейший пропорциональный отбор – рулетка. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер каждого сектора пропорционален соответствующей величине функции приспособленности. При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью. Далее применяется скрещивание и мутация.
Популяция, полученная после мутации, записывается поверх старой и этим цикл одного поколения завершается. Последующие поколения, полученные в результате работы генетического алгоритма, обрабатываются таким же образом: отбор, скрещивание и мутация.
