Практические соображения
Как следует из примера, сами генетические алгоритмы обладают набором параметрам. К ним относятся:
- Правило скрещивания генотипов: сколько генотипов участвует в скрещивании, как и какие характеристики "родителей" передаются следующему поколению, какие именно генотипы будут допущены до создания следующего поколения (все или часть, каков критерий отбора);
- Какова вероятность и величина мутации. Может ли мутация затрагивать несколько (сколько) характеристик генотипа. Какова величина отклонения при мутации для каждой характеристики.
- Какие генотипы, полученные на двух предыдущих шагах допускаются в следующее поколение, каков критерий отбора;
- Могут ли генотипы предыдущего поколения претендовать на место в следующем или новое поколение принципиально формируется только из новых генотипов.
- Сколько поколений достаточно для получения приемлемого (возможно, не самого оптимального, но, тем не менее приемлемого для данной задачи) решения.
Скажем сразу, что универсального ответа на эти вопросы не существует. Под универсальным ответом мы подразумеваем такие настройки параметров генетического алгоритма, которые одинаково хорошо (по оптимальности результата и скорости его получения) работали бы на всех классах задач, существующих в природе.
Далее приведем неполный перечень подходов к каждому из шагов. Каждый из подходов имеет плюсы и минусы в зависимости от типа задачи, типа и формы целевой функции.
Этап отбора (селекция)
Полный список методов, на которых может быть основана селекция приведен в специальной литературе. Приведем всего два примера:
Турнирная селекция заключается в том, что из N генотипов случайным образом отбирается k представителей. Среди них отбирается один или несколько с наименьшим значением целевой функции (среди k претендентов проводится турнир), которые попадают в следующее поколение.
Метод ранжирования. Генотипы сортируются по возрастанию целевой функции. Затем судьба каждого генотипа решается случайным образом. При этом вероятность попадания генотипа в следующее поколение должна быть обратно пропорциональна номеру этого генотипа в отсортированном списке (чем дальше от начала, тем меньше вероятность, что этот генотип попадет в следующее поколение, тем не менее такая вероятность есть).
Этап скрещивания (размножение)
Панмиксия - каждый генотип имеет равные шансы быть избранным для скрещивания. Исходные генотипы (обычно два) выбираются случайным образом.
Выбор на основе функции приспособленности (фитнес-функции). В этом случае, помимо целевой функции, для генотипов вводится функция приспособленности - некая числовая характеристика (изначально распределенная случайным образом), приписанная каждому генотипу и от которой будет зависеть вероятность попадания в следующее поколение. Эта характеристика может наследоваться и подвергаться мутациям. Вероятность того, что генотип будет отобран для скрещивания, также пропорциональна функции приспособленности.