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

FlexTool
. Однако возможность 
применения метода рулетки всего лишь для одного класса задач, т.е. только 
для максимизации (или только для минимизации) можно считать его 
несомненным недостатком. Другая слабая сторона этого метода заключается 
в том, что особи с очень малым значением функции приспособленности 
слишком быстро исключаются из популяции, что может привести к прежде-
временной сходимости генетического алгоритма. Для предотвращения 
такого эффекта применяется масштабирование функции приспо-
собленности (п. 3.9.5). 
С учетом отмеченных недостатков метода рулетки созданы и 
используются альтернативные алгоритмы селекции. Один из них называется 
турнирным методом (tournament selection). 
Наряду с методом рулетки и 
ранговым методом он применяется как один из основных алгоритмов 
селекции в программе 
FlexTool. 
Представим эти методы подробнее. 
При турнирной селекции все особи популяции разбиваются на 
подгруппы с последующим выбором в каждой из них особи с наилучшей 
приспособленностью. Различаются два способа такого выбора: 
детерминированный выбор (deterministic tournament selection) 
и 
случайный 
выбор (stochastic tournament selection). 
Детерминированный выбор 
осуществляется с вероятностью, равной 1, а случайный выбор - с 
вероятностью, меньшей 1. Подгруппы могут иметь произвольный размер, 
но чаще всего популяция разделяется на подгруппы по 2 - 3 особи в 
каждой. 
Турнирный метод пригоден для решения задач как максимизации, 
так и минимизации функции. Помимо того, он может быть легко 
распространен на задачи, связанные с многокритериальной оптимизацией, 
т.е. на случай одновременной оптимизации нескольких функций. В 
турнирном методе допускается изменение размера подгрупп, на которые 
подразделяется популяция 
(tournament size). 
Исследования подтверждают, 
что турнирный метод действует эффективнее, чем метод рулетки. 

---

А.Е. Кононюк Дискретно-непрерывная математика 
148 
На рис. 1 представлена схема, которая иллюстрирует метод турнирной 
селекции для подгрупп, состоящих из двух особей. Такую схему легко 
обобщить на подгруппы большего размера. Это одно из возможных 
приложений рассматриваемого алгоритма селекции (оно используется в 
программе