ПОИСК Статьи Чертежи Таблицы Базовый генетический алгоритм из "Информационная поддержка наукоемких изделий. CALS-технологии " В задачах принятия решений и структурного синтеза любая альтернатива представляется значениями параметров х, относящихся к некоторому множеству X. В генетических методах множеству X соответствует запись, называемая хромосомой, элементы хромосомы соответствуют параметрам х , их называют генами, а значения генов - аллелями. Каждый ген размещается в хромосоме в некоторой позиции - локусе. В случае геометрической интерпретации каждому гену соответствует одна из осей координатного пространства, а хромосоме - некоторая точка поискового пространства. [c.211] Таким образом, цель генетического поиска - найти экземпляр хромосомы, имеющий значение функции полезности, максимально близкое к ее экстремальному значению. Направленный поиск малой окрестности экстремума осуществляется в генетическом алгоритме с помощью генетических операторов выбора родителей, кроссовера, мутации, селекции, переупорядочения, поясняемых далее. [c.212] Генетические алгоритмы имитируют эволюционный процесс приближения к оптимальному результату, начиная с некоторого исходного поколения структур, представленных экземплярами хромосом. Этот процесс в базовом генетическом алгоритме является вложенным циклическим вычислительным процессом. Внешний цикл имитирует смену поколений. Во внутреннем цикле формируются члены очередного поколения. [c.212] Результатом каждого очередного витка внешнего цикла является новое поколение, о качестве которого судят по экземпляру хромосомы с лучшим значением целевой ф)шкции F. [c.212] Характер приближения к экстремуму обычно таков, что на начальных витках скорость улучшения целевой функции довольно значительная, но по мере приближения к экстремуму она замедляется и может наступить прекращение улучшения Р на некотором удалении от экстремальной точки. Это явление называют стагнацией. Обычно она происходит из-за вырождения популяции - потери разнообразия генного материала. Поиск прекращают чаще всего при появлении признаков стагнации, о чем свидетельствует неулучшение целевой функции на протяжении нескольких последних поколений, либо по исчерпании лимита отведенного времени на решение задачи. [c.213] Во внутреннем цикле базового генетического алгоритма выполняется следующая последовательность генетических операторов выбор родителей, кроссовер (скрещивание), мутация, селекция. [c.213] Порождение новых экземпляров хромосом происходит в процессе скрещивания (кроссовера) родительских пар. Выбор пары членов популяции в качестве родителей производится случайным образом среди членов данного поколения. При этом вероятность выбора экземпляров в качестве родителей в базовом генетическом алгоритме зависит от их значений функции полезности, т.е. чем лучше значение Р, тем выше должна быть вероятность выбора. [c.213] Кроссовер заключается в разрыве двух выбранных родительских хромосом и рекомбинировании образовавшихся хромосомных отрезков, что дает пару хромосом потомков. На рис. 2.13 представлен пример кроссовера (разрыв после третьего локуса) и рекомбинации отрезков. Здесь два верхних экземпляра - родители, два нижних - пoтo пш. Для наглядности гены одного родителя обозначены буквами, другого - цифрами. [c.213] Мутации, т.е. случайные изменения некоторых аллелей, предназначены для реализации поиска в пространстве всех возможных экземпляров хромосом. Без мутаций поиск не может выйти за пределы того подмножества экземпляров хромосом, в котором аллели совпадают со сгенерированными значениями генов в начальной популяции. Например, если в некотором гене, отображающем дни недели, в хромосомах начальной популяции оказались сгенерированными только значения понедельнию , среда , четверг и воскресенье , то при вьшолнении операторов кроссовера или селекции значения вторнию , пятница и суббота появиться не могут. Мутации устраняют этот недостаток. Они происходят в очередном гене с некоторой заданной достаточно малой (сотые - тысячные доли) вероятностью Р . При мутациях значение гена выбирается случайным образом среди множества возможных значений, т.е. в нашем примере произойдет равновероятный выбор среди всех семи возможных дней недели. [c.214] Селекция - это отбор членов нового поколения среди потомков, полученных в результате кроссовера и мутаций в данном поколении. В базовом генетическом алгоритме в новое поколение включается лучший из двух потомков, порожденных после кроссовера. Внутренний цикл заканчивается, когда окажется сформированным новое поколение, т.е. в нем будет N членов. [c.214] Обозначим число экземпляров схемы Н в поколении с номером t через ДН, t). Введем также следующие обозначения Л - размер (число хромосом) популяции Q - множество номеров членов популяции, в хромосомах которых имеется схема Н /)(Н) - длина схемы Н, т.е. расстояние (число позиций) между крайними локусами схемы, так, в случае (2.5) имеем ДН) = 8-4 = 4 Х(Н) - порядок схемы Н (число локусов в Н), в примере (2.5) порядок равен 3 п - длина хромосомы. [c.215] При мутации, происходящей с вероятностью для каждой позиции, вероятность сохранения схемы Н, определяемая как (1 - приблизительно равна 1 - Т(Н)Р . [c.215] Следовательно, число схем из хромосом перспективных родителей (Р Р , имеющих лучшие значения функции полезности, увеличивается в генотипах популяции от поколения к поколению по показательному закону, пока не наступит стагнация, при которой Р (Н) = Р. [c.215] Вернуться к основной статье