ПОИСК Статьи Чертежи Таблицы Разновидности генетических операторов из "Информационная поддержка наукоемких изделий. CALS-технологии " Разновидности генетических операторов и их сочетаний порождают множество генетических методов, описание некоторых из них можно найти, например, в [61 62]. [c.216] Варианты кроссовера связаны с числом мест разрыва родительских хромосом. Если место одно, то кроссовер называют одноточечным, иначе имеем многоточечный кроссовер. На рис. 2.14 показан результат двухточечного кроссовера для тех же родителей, что и в примере рис. 2.13, при разрывах после второго и пятого локусов. [c.216] Если структура хромосомы однородная в том смысле, что все проектные параметры, отображаемые генами, относятся к одной и той же классификационной группе в контексте решаемой задачи, то целесообразен одноточечный кроссовер. Когда гены могут быть сгруппированы по одному признаку (например, по принадлежности к определенным конструктивным блокам) и упорядочены в группах по другому признаку (например, по физическому смыслу), то более эффективным может оказаться многоточечный кроссовер, при котором по одной точке разрыва приходится на каждую группу. Конкретный пример многоточечного кроссовера будет приведен далее при рассмотрении задачи синтеза расписаний для многостадийных процессов. [c.216] Возможны разные способы выбора объекта мутации. В соответствии с одним из способов обращение к процедуре мутации происходит с некоторой постоянной вероятностью, как в базовом генетическом алгоритме. В соответствии с другим способом ради снижения опасности стагнации вероятность мутации увеличивают, когда две выбранные родительские хромосомы различаются значениями не более чем к генов, обычно /г = 0... 2. [c.216] Сами мутации различаются числом одновременно мутируемых генов и с этой точки зрения могут быть простыми, макромутациями (многопозиционными) и хромосомными. Во всех случаях мути-руемым генам присваиваются случайные значения, выбираемые в области определения генов. [c.216] При простой мутации изменение значения каждого гена происходит с вероятностью Р , обычно эта вероятность невелика и составляет сотые-тысячные доли единицы. В другой разновидности простой мутации в хромосоме изменяется значение единственного гена, позиция этого гена выбирается с равной вероятностью среди генов хромосомы. [c.217] В хромосомных мутациях К=п, т.е. изменяются значения всех генов. [c.217] С помощью оператора селекции формируется набор хромосом нового поколения. Часто в новое поколение включают лучшего из двух потомков после каждой операции кроссовера, а также хромосомы, получающиеся в результате мутаций. Другой вариант селекции - в новое поколение включаются две лучшие хромосомы, выбираемые среди двух потомков и двух родителей в каждой операции кроссовера. Третий вариант - новое поколение формируется из тех хромосом, являющихся результатами кроссовера и мутации, целевая функция которых меньше (при минимизации) некоторого порога. [c.217] Во многих приложениях между генами существуют зависимости, приводящие к некорректности некоторых экземпляров хромосом, генерируемьк случайным образом. Некорректность, в частности, выражается в том, что для некорректньк хромосом не удается правильно определить значение целевой функции. Другими словами, в процессе генетического поиска нельзя допустить, чтобы в популяции появлялись некорректные хромосомы. Поскольку и кроссовер, и мутации могут приводить к формированию недопустимых потомков, приходится вводить в генетический алгоритм дополнительные операторы корректировки хромосом. Это обстоятельство усложняет алгоритм. [c.218] Обычно возможность появления недопустимых хромосом связана с наличием зависимостей между генами. Тогда независимый случайный выбор значений генов, как это происходит при кроссовере и мутациях в базовом генетическом алгоритме, становится некорректным. [c.218] Рассмотрим примеры приложений, в которьк существуют межгенные зависимости, приводящие к таким некорректностям. [c.218] Пример . Рассмотрим задачу разбиения графа на два подграфа так, чтобы число верщин в подграфах и бьшо равно заданным значениям N a при этом целевая функция имела экстремальное значение. Будем считать, что если аллель А -го гена равен 1, то вершина к находится в А , если же аллель к-то гена равен о, то - в Aj. Очевидно, что число единиц в хромосоме должно равняться N , число нулей - N . Однако это условие для хромосом потомков, получающихся в результате кроссовера или мутаций, в общем случае не соблюдается, причем по-прежнему вероятность получения корректного потомка крайне мала. [c.219] Корректировка хромосомы заключается в принудительном изменении значений некоторых генов в хромосоме потомка. Например, в задаче разбиения графа (см. пример 7) левый участок хромосомы, который взят от одного из родителей, можно оставить без изменений, а в правом участке, взятом от другого родителя, нужно согласовать число единиц с требуемым тем или ршым способом. [c.219] Находят применение и некоторые дополнительные операторы. К их числу относится оператор переупорядочения генов - изменения их распределения по локусам. [c.220] Вернуться к основной статье