Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
6. Методы селекции хромосом в модификациях классического генетического алгоритма: виды, механизмы реализации, преимущества и недостатки, детерминированный и случайный подходы.
Модификации классического генетического алгоритма
В классическом генетическом алгоритме используется двоичное представление хромосом, селекция методом колеса рулетки и точечное скрещивание (с одной точкой скрещивания). Для повышения эффективности его работы создано множество модификаций основного алгоритма. Они связаны с применением других методов селекции, с модификацией генетических операторов (в первую очередь оператора скрещивания), с преобразованием функции приспособленности (путем ее масштабирования), а также с иными способами кодирования параметров задачи в форме хромосом. Существуют также версии генетических алгоритмов, позволяющие находить не только глобальный, но и локальные оптимумы. Это алгоритмы, использующие так называемые ниши, введенные в генетические алгоритмы по аналогии с природными экологическими нишами. Другие версии генетических алгоритмов служат для многокритериальной оптимизации, т.е. для одновременного поиска оптимального решения для нескольких функций. Встречаются также специальные версии генетического алгоритма, созданные для решения проблем малой размерности, не требующих ни больших популяций, ни длинных хромосом. Их называют генетическими микроалгоритмами.
Методы селекции
Основанный на принципе колеса рулетки метод селекции, считается для генетических алгоритмов основным методом отбора особей для родительской популяции с целью последующего их преобразования генетическими операторами, такими как скрещивание и мутация. Несмотря на случайный характер процедуры селекции, родительские особи выбираются пропорционально значениям их функций приспособленности, т.е. согласно вероятности селекции, определяемой по формуле
Каждая особь получает в родительском пуле такое количество своих копий, какое устанавливается выражением
e(chi) = ps(chi)*N,
где N - количество хромосом chi, i = 1, 2, … N в популяции, a ps(chi) - вероятность селекции хромосомы chi, рассчитываемая по формуле выше. Строго говоря, количество копий данной особи в родительском пуле равно целой части от e(chi). При использовании обеих формул необходимо обращать внимание на то, что e(chi) = F(chi) / ‾F‾,
где ‾F‾ - среднее значение функции приспособленности в популяции. Очевидно, что метод рулетки можно применять тогда, когда значения функции приспособленности положительны. Этот метод может использоваться только в задачах максимизации функции (но не минимизации).
Очевидно, что проблему минимизации можно легко свести к задаче максимизации функции и обратно. В некоторых реализациях генетического алгоритма метод рулетки применяется для поиска минимума функции (а не максимума). Это результат соответствующего преобразования, выполняемого программным путем для удобства пользователей, поскольку в большинстве прикладных задач решается проблема минимизации (например, затрат, расстояния, погрешности и т.п.). В качестве примера такой реализации можно назвать программу FlexTool. Однако возможность применения метода рулетки всего лишь для одного класса задач, т.е. только для максимизации (или только для минимизации) можно считать его несомненным недостатком. Другая слабая сторона этого метода заключается в том, что особи с очень малым значением функции приспособленности слишком быстро исключаются из популяции, что может привести к преждевременной сходимости генетического алгоритма. Для предотвращения такого эффекта применяется масштабирование функции приспособленности.
С учетом отмеченных недостатков метода рулетки созданы и используются альтернативные алгоритмы селекции. Один из них называется турнирным методом (tournament selection). Различаются два способа такого выбора: детерминированный выбор (deterministic tournament selection) и случайный выбор (stochastic tournament selection). Детерминированный выбор осуществляется с вероятностью, равной 1, а случайный выбор - с вероятностью, меньшей 1. Подгруппы могут иметь произвольный размер, но чаще всего популяция разделяется на подгруппы по 2 - 3 особи в каждой.
Турнирный метод пригоден для решения задач, как максимизации, так и минимизации функции. Помимо того, он может быть легко распространен на задачи, связанные с многокритериальной оптимизацией, т.е. на случай одновременной оптимизации нескольких функций. В турнирном методе допускается изменение размера подгрупп, на которые подразделяется популяция (tournament size). Исследования подтверждают, что турнирный метод действует эффективнее, чем метод рулетки.
На рис. 5. представлена схема, которая иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей. Такую схему легко обобщить на подгруппы большего размера. Это одно из возможных приложений рассматриваемого алгоритма селекции.
Рис. 5. Схема турнирной селекции для подгрупп, состоящих из двух особей.
При ранговой селекции (ranking selection) особи популяции ранжируются по значениям их функции приспособленности. Это можно представить себе как отсортированный список особей, упорядоченных по направлению от наиболее приспособленных к наименее приспособленным (или наоборот), в котором каждой особи приписывается число, определяющее ее место в списке и называемое рангом (rank). Количество копий М(k) каждой особи, введенных в родительскую популяцию, рассчитывается по априорно заданной функции в зависимости от ранга особи. Пример такой функции показан на рис. 6.
Достоинство рангового метода заключается в возможности его применения, как для максимизации, так и для минимизации функции. Он также не требует масштабирования из-за проблемы преждевременной сходимости, актуальной для метода рулетки.
Рис. 6. Пример функции, определяющей зависимость количества копий особи в родительском пуле от его ранга при ранговой селекции.
Существуют различные варианты алгоритмов селекции. Представленные ранее методы (рулетки, турнирный и ранговый) применяются чаще всего. Другие методы представляют собой либо их модификации, либо комбинации - например, метода рулетки с турнирным методом, когда пары родительских хромосом выбираются случайным образом, после чего из каждой пары выбирается хромосома с наибольшим значением функции приспособленности. Большинство методов селекции основано на приведенных формулах, по которым рассчитывается вероятность селекции и количество копий, вводимых в родительский пул. В так называемом детерминированном методе каждая особь получает число копий, равное целой части от e(chi), после чего популяция упорядочивается в соответствии с дробной частью e(chi), а остальные хромосомы, необходимые для пополнения новой популяции, последовательно выбираются из верхней части сформированного таким образом списка. В другом методе (называемом случайным) дробные части e(chi) рассматриваются как вероятности успеха по Бернулли и, например, хромосома chi, для которой e(chi) = 1,5, получает одну копию гарантированно и еще одну - с вероятностью 0,5. В еще одном методе для устранения расхождения между расчетным значением e(chi) и количеством копий хромосом chi, выбираемым по методу рулетки, производится модификация e(chi) путем увеличения или уменьшения его значения для каждой хромосомы, выбранной для скрещивания и/или мутации.