Cтраница 2
Выполнение генетических алгоритмов основано на обработке схем. Схемы малого порядка, с малым охватом и приспособленностью выше средней выбираются, размножаются и комбинируются, в результате чего формируются все лучшие кодовые последовательности. Простое скрещивание не слишком часто уничтожает схемы с малым охватом, однако ликвидирует схемы с достаточно большим охватом. Однако невзирая на губительность операций скрещивания и мутации для схем высокого порядка и охвата, количество обрабатываемых схем настолько велико, что даже при относительно низком количестве хромосом в популяции достигаются весьма неплохие результаты выполнения генетического алгоритма. [16]
Прежде всего отметим, что одни схемы оказываются более подверженными уничтожению в процессе скрещивания, чем другие. Видно, что схема S2 имеет больше шансов пережить операцию скрещивания, чем схема S. Обратим внимание на охват обеих схем, который - это очевидно - оказывается существенным в процессе скрещивания. [17]
Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности рс. Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью А /, то рс - 2 / N. Аналогично, если из родительской популяции численностью А / выбирается 2z хромосом ( z N12), которые образуют z пар родителей, то рс 2z / N. После операции скрещивания родители в родительской популяции замещаются их потомками. [18]