ПОИСК Статьи Чертежи Таблицы Разновидности генетических операторов из "Основы автоматизированного проектирования " Возможны отклонения от представленной выше в простом генетическом алгоритме схемы вычислений. [c.188] Кроссовер. Во-первых, допустимы схемы многоточечного кроссовера. [c.188] В табл. 4.4 первые две строки представляют родительские хромосомы. Третья строка содержит хромосому одного из потомков, сгенерированного в результате применения двухточечного кроссовера (после второго и пятого ло-кусов). Полученная хромосома не относится к числу допустимых, так как в ней значения генов 1, 2 и 9 встречаются дважды, а значения 3, 4 и 5 отсутствуют. Четвертая строка показьюает результат применения РМХ. В этом методе вьщеляются сопряженные пары аллелей в одноименных локусах одной из рекомбинируемых частей. В нашем примере это пары (3 и 1), (4 и 9), (5 и 2). Хромосома потомка просматривается слева направо если повторно встречается некоторое значение, оно заменяется сопряженным значением. Так, в примере в локусах 3, 5 и 9 повторно встречающиеся аллели 1,2 и 9 последовательно заменяются значениями 3, 5 и 4. [c.188] Мутации. Бывают точечные мутации (в одном гене), макромутации (в нескольких генах) и хромосомные (появление новой хромосомы). Обычно вероятность появления мутации указывается среди исходных данных. Но возможно автоматическое регулирование числа мутаций при их реализации только в ситуациях, когда родительские хромосомы различаются не более чем в К генах. [c.188] Селекция. После определения и положительной оценки потомка, он может быть сразу же включен в текущую популяцию вместо худшего из своих родителей, при этом из алгоритма исключается внешний цикл (что, однако, не означает сокращения общего объема вычислений). [c.189] Другой вариант селекции—отбор после каждой операции скрещивания двух лучших экземпляров среди двух потомков и двух родителей. [c.189] Часто член популяции с минимальным (лучшим) значением целевой функции принудительно включается в новое поколение, что гарантирует наследование приобретенных этим членом положительных свойств. Такой подход называют элитизмом. Обычно элитизм способствует более быстрой сходимости к локальному экстремуму, однако в многоэкстремальной ситуации ограничивает возможности попадания в окрестности других локальных экстремумов. [c.189] Примечание. Хромосому X будем называть точкой локального миншу1ума, если F X ) F (X.) для всех хромосом X., отличающихся от X значением единственного гена, где F (X) - значение функции полезности в точке X. [c.189] Следующий вариант селекции — отбор 7V экземпляров среди членов репродукционной группы, которая составляется из родителей, потомков и мутантов, удовлетворяющих условию F. /, где /— пороговое значение функции полезности. Порог может быть равен или среднему значению F в текущем поколении, или значению Пособи, занимающей определенное порядковое место. При этом суть мягкой схемы отбора — включение в новое поколение N лучших представителей репродукционной группы. Жесткая схема отбора — в новое поколение экземпляры включаются с вероятностью q . [c.189] Переупорядочение. Кроме перечисленных основных операторов находят применение некоторые дополнительные. К их числу относится оператор переупорядочения генов — изменения их распределения по локусам. [c.189] Вернуться к основной статье