Курсовая работа: Генетические алгоритмы в задаче оптимизации действительных параметров

3.3 Механизм отбора

Обсуждение вопроса о влиянии метода создания родительских пар на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Наиболее эффективные два механизма отбора элитный и отбор с вытеснением.

Идея элитного отбора, в общем, не нова, этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективных.

Второй метод, на котором хотелось бы остановиться, это отбор вытеснением. Будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, вместо особей, группирующихся около текущего найденного решения. Этот метод особенно хорошо себя показал при решении многоэкстремальных задач, при этом помимо определения глобальных экстремумов появляется возможность выделить и те локальные максимумы, значения которых близки к глобальным.

4. Наиболее актуальные проблемы ГА и интересные модификации ГА

Неудачный выбор упорядочивания и кодирования битов в хромосоме может вызвать преждевременное схождение к локальному оптимуму, ведя алгоритм по ложному пути. Для преодоления этого недостатка можно выбирать способ кодирования основываясь на дополнительной информации о задаче. Существуют так же мобильные ГА, с переменной длиной хромосом. Для некоторых задач такое представление естественно, для других надо вводить специальные правила чтения хромосом. Вместо оператора кроссинговера используются операторы разрезания строк (CUT), вероятность которого повышается с увеличением длины строки, и оператор сцепления строк (SPLICE), который выбирает из популяции два куска и сцепляет их в один кусок. Популяция представляет собой совокупность пере- и недоопределённых строк. Правила чтения таких строк могут быть, например такими: в переопределённой строке при чтении слева направо не учитываются уже использованные гены, а в недоопределённых строках отсутствующие места заимствуются у лучшего элемента.

Проблема баланса исследования новых областей и приспособления к найденным. Это необходимо для предотвращения преждевременной сходимости к локальному оптимуму. Используются модифицированные способы отбора хромосом в промежуточную популяцию (отказ от вероятностных принципов в пользу элитного и отбора с вытеснением) и выбора родительской пары (случайный, селективный, на основе близкого или дальнего родства).

Интересные результаты может дать сочетание ГА с другими методами. И в заключение остановимся на том, когда же следует использовать генетические алгоритмы. В одних обстоятельствах они хороши, в других - не очень. В общем случае генетические алгоритмы не находят оптимального решения очень трудных задач. Если оптимальное решение задачи (например, ЗКВ с очень большим числом городов) не может быть найдено традиционными способами - например, методом сцепления ветвей (branch and bound method), - то и генетический алгоритм вряд ли найдет оптимум. С другой стороны, вполне возможно, что генетический алгоритм найдет достаточно хорошее решение. В конце концов, коммивояжеру в любом случае надо ехать продавать свои товары, даже если мы не уверены в абсолютной оптимальности маршрута! Но есть примеры, когда в очень трудных задачах, в том числе и в ЗКВ, с помощью генетических алгоритмов были получены очень хорошие решения.

В двух случаях генетические алгоритмы очень хороши. Первый случай: когда не известен способ точного решения задачи. Если мы знаем, как оценить приспособленность хромосом, то всегда можем заставить генетический алгоритм решать эту задачу. Второй случай: когда способ для точного решения существует, но он очень сложен в реализации, требует больших затрат времени и денег, то есть, попросту говоря, дело того не стоит. Пример - создание программы для составления персонального расписания на основе техники покрытия множеств с использованием линейного программирования.

Несмотря на то, что конструирование хромосом и фитнес-функций может потребовать значительных усилий, генетические алгоритмы легко реализуются даже с нуля и способны решать широкий круг задач. Используя аналогию с развитием живых организмов от простых форм к более сложным, генетические алгоритмы приблизились к тому, чтобы стать общим методом решения задач. Другие "природоподобные" парадигмы, такие как моделирование отжига (simulated annealing) и табу-поиск (taboo search), тоже позволяют решать аналогичные задачи.

5. Пример ГА: Решение Диофантова уравнения

Рассмотрим диофантово (только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d). Конечно, Вы можете спросить: почему бы не использовать метод грубой силы: просто не подставить все возможные значения a, b, c, d (очевидно, 1 <= a,b,c,d <= 30) ? Архитектура ГА-систем позволяет найти решение быстрее за счет более 'осмысленного' перебора. Мы не перебираем все подряд, но приближаемся от случайно выбранных решений к лучшим. Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30.

Таблица 2: 1-е поколение хромосом и их содержимое

Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением.

Таблица 3: Коэффициенты выживаемости первого поколения хромосом (набора решений)

Так как меньшие значения ближе к 30, то они более желательны. В нашем случае большие численные значения коэффициентов выживаемости подходят, увы, меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Одно решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел - ГСЧ).

Таблица 4: Вероятность оказаться родителем

Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-сторонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы.

Таблица 5: Симуляция выбора родителей

Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кросс-оверов (| = разделительная линия):

Таблица 6: Кроссоверы между родителями

Есть достаточно много путей передачи информации потомку, и кроссовер - только один из них. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты. А теперь попробуем проделать это с нашими потомками

Страницы: 1, 2, 3, 4