Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Схема ГА
6.6. 
Примеры генетического алгоритма 
Приводится разъяснение условий установки опций для генетического 
алгоритма. 
Для того, что бы получить наилучшие результаты, как правило, обычно 
проводят расчеты с различными значениями опций. Выбор наилучшего 
вида значений опций основан на методе проб и ошибок. В данном 
разделе приводятся определенные приемы выбора опций с целью 
улучшения полученных результатов. Полное описание опций можно 
найти в разделе Опции генетического алгоритма. 
6.6.1. Масштаб пригодности
Операция с масштабом пригодности определенным способом 
стягивает, при помощи функции пригодности, множества 
необработанных значений пригодности в некий диапазон, который 

---

А.Е. Кононюк Дискретно-непрерывная математика 
380 
является приемлемым для действий функции отбора. Функция отбора 
использует отмасштабированные значения пригодности для отбора 
родительских значений для следующего поколения. Функция отбора 
назначает более высокую вероятность выбора тем 
индивидуализированным объектам, которые имеют более высокие 
отмасштабированные значения. 
Величина диапазона отмасштабированных значений оказывает 
влияние на эффективность работы Генетического алгоритма. Если 
отмасштабированные значения изменятся в широком диапазоне, то 
индивидуализированные объекты с наибольшими значениями 
отмасштабированных значений воспроизводятся достаточно быстро и 
также быстро формируется генетическая совокупность наследственных 
факторов данной популяции. Такая ситуация предотвращает 
генетический алгоритм от поиска по другим областям пространства 
решений. С другой стороны, если отмасштабированные значения 
изменяются достаточно мало, то все индивидуализированные объекты 
имеют примерно одну и ту же вероятность участия в воспроизводстве 
и поиске решения, что заметно замедляет процесс решения. 
Принимаемая по умолчанию функция масштабирования значений 
пригодности, Rank, масштабирует необработанные множества на 
основе определенного ранга для каждого индивидуализированного 
объекта вместо значений этого множества. Рангом 
индивидуализированного объекта является его позиция в 
отсортированном множестве: ранг наибольшей пригодности 
индивидуализированного объекта равен 1, ранг следующей 
наибольшей пригодности равен 2 и так далее. Функция 
масштабирования ранга приписывает отмасштабированные значения 
таким образом, что бы: 
1.
Отмасштабированное значение индивидуализированного 
объекта с рангом 
n
прямо пропорционально 
.
2.
Сумма отмасштабированных значений по всему пространству 
семейств равна числу родителей, необходимых для создания 
следующего поколения.

---

А.Е. Кононюк Дискретно-непрерывная математика 
381 
Далее на графике представлены необработанные множества типичного 
семейства из 20 индивидуализированных объектов, отсортированных 
по порядку увеличения. 
Следующий график представляет отмасштабированные значения 
необработанных множеств согласно рангу масштабирования. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
382 
Поскольку в данном алгоритме минимизируется функция пригодности, 
то менее обработанные значения множеств имеют более высокие 
отмасштабированные значения. А так же, поскольку операция 
вычисления ранга придает значения, которые зависят только от ранга 
индивидуализированного объекта, то отмасштабированные значения, 
как это показано, есть те же самые как для любого семейства размера 
20, так и для числа родителей равного 32.