Практический опыт применения генетических алгоритмов (ГА) свидетельствует о преимуществах многоточечного кроссовера перед одноточечным. Генетический метод с фрагментным кроссовером, называемый также смешанным эволюционным методом (MMEM — Mixed Mode Evolution Method), является одним из способов реализации многоточечного кроссовера. Целью применения ММЕМ является повышение эффективности генетического поиска, достигаемое в ММЕМ за счет выбора оптимальных размеров фрагментов, на которые разделяются хромосомы при кроссовере. ММЕМ характеризуется следующими двумя свойствами: 1) многоточечный кроссовер; 2) многохромосомная рекомбинация, т.е. хромосома каждого потомка формируется из хромосом более двух родителей.
Фрагментами в ММЕМ называют участки, на которые делятся хромосомы при кроссовере. В пределах каждого фрагмента выполняются свои операции выбора родительской пары и одноточечного кроссовера. Мутации и оценка целевой функции осуществляются в пределах всей хромосомы. Фрагментацию хромосом иллюстрирует рис. 1.
Рис. 1.  Структура хромосомы в ММЕМ
Специфика MMEM отражена главным образом в блоке формирования хромосом для следующего поколения. Параметрами, характеризующими особенности применяемого метода, являются длина фрагментов, на которые разделяются родительские хромосомы, число хромосом-родителей у каждой формируемой хромосомы.
На рис. 2 показаны результаты решения ряда тестовых задач с помощью ММЕМ при различных значениях длины фрагментов. Длины хромосом находились в диапазоне от 40 генов в задаче VRPTW до 800 в задаче синтеза расписаний. Поскольку при имеем генетический алгоритм (ГА) с одноточечным кроссовером, а при =1 — с однородным кроссовером, где — длина фрагмента (число генов в фрагменте), — длина хромосомы, результаты рис. 2 дают возможность сравнения точности решения задач при различных числах точек кроссовера. Во всех четырех задачах в случае ММЕМ степень приближения к экстремуму (в задачах , , выполнялась минимизация, а в задаче — максимизация целевой функции) была выше, чем при одноточечном, двухточечном или однородном кроссовере, при одинаковых вычислительных затратах.
Рис. 2.  Экспериментальные зависимости целевых функций от длины фрагментов в задачах: а) синтеза расписаний; б) маршрутизации транспортных средств с временными окнами (VRPTW); в) компоновки; г) синтеза топологии вычислительной сети.
Обоснованием наличия оптимальных, с точки зрения точности, значений длин фрагментов служат следующие соображения.
Рассмотрим двухфрагментный участок хромосомы в условиях отсутствия мутаций и внутрифрагментного кроссовера (рис. 3).
Рис. 3.  Двухфрагментный участок хромосомы
Вероятность случайной генерации шаблона . состоящего из левой части и правой части и инцидентного двум фрагментам, в исходном поколении при равна
= /
где — размер популяции, — число символов в алфавите кодирования хромосом, () — порядок шаблона . Аналогично вероятности генерации шаблонов и с порядками () и () соответственно- оцениваются (при и ) как
= / и = /.
Во многих практических задачах (синтез расписаний относится к их числу) плотные шаблоны оказывают большее влияние на функцию полезности, чем шаблоны с удаленными друг от друга локусами. Поэтому рассмотрение целесообразно провести применительно к плотному шаблону с () = ().
Пусть шаблон является полезным и входит в состав оптимальной хромосомы. Существует некоторая длина шаблона , при которой появление в исходной популяции становится маловероятным и эта вероятность есть . Например, при = 0,02, = 100 и = 5 (последнее может означать, что используются 5 различных эвристик в мультиметодном алгоритме) имеем
= lg(50)/lg5 > 5.
Появиться шаблон в текущей популяции при > может только вследствие его генерации (сохранение отсутствует). Генерация происходит с вероятностью рекомбинации частей шаблона и , равной Следовательно, необходимо, чтобы и были больше , что, очевидно, выполняется в рассмотренном примере при = 6 или 7.
В ситуации рис. 3 появившийся шаблон не может сохраниться и разрушается в следующем акте кроссовера. Однако высокая оценка его полезности ведет к увеличению вероятностей и , т.е. к усилению генерационных возможностей алгоритма. Для шаблонов меньшей полезности, чем полезность шаблона , генерационные возможности составляющих компонентов усиливаются слабее или даже ослабевают. Таким образом, важно не столько сохранение полезных шаблонов в популяции, сколько усиление возможностей их генерации.
Увеличение числа позиций, в которых происходит генерация новых шаблонов, способствует появлению полезных шаблонов в большем числе частей хромосомы, что и объясняет улучшение целевой функции при уменьшении на графиках рис. 2 при длинах фрагментов выше оптимальной длины . При = начинает сказываться близость соседних точек разрыва друг к другу. Если расстояние между этими точками становится соизмеримым или менее , интенсивность генерации полезных шаблонов падает, так как теперь шаблон формируется уже из трех участков , , , принадлежащих каждый разным фрагментам, и вероятность его генерации определяется произведением трех вероятностей << 1.
Характер генерации новых полезных шаблонов будет аналогичным рассмотренному, если учитывать наличие внутрифрагменого кроссовера (возможные линии разрыва фрагментов показаны на рис. 3 красными линиями), при этом оптимальные длины фрагментов должны возрасти приблизительно вдвое.
В практических алгоритмах ММЕМ при использовании метода комбинирования эвристик оптимальные значения находятся в диапазоне от 4 до 30. Поскольку априорно значение неизвестно, целесообразно использовать алгоритм с автоматическим выбором из некоторого набора, заданного в качестве исходных данных.
Список литературы
1. Норенков И.П. Исследование эффективности генетического метода с фрагментным кроссовером // Информационные технологии, 2008, N 6, стр. 26-29.