Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 44
Текст из файла (страница 44)
Тогдавероятность Р выбора родителя с хромосомой С можно рассчитать по формулеP=(F-F)/I,(Fimaxi'*^vv.H186max-F),j''(4.33)1v4.4. Методы структурного синтеза в системах автоматизированного проектированиягде Fmax — наихудшее значение целевой функции F среди экземпляров (членов)текущего поколения; F — значение целевой функции i-го экземпляра.Правило (4.31) называют правилом колеса рулетки.
Если в колесе рулеткивыделить секторы, пропорциональные значениям Fmm— F, то вероятности попадания в них суть Р, определяемые в соответствии с (4.33).Пример. Пусть N=4, значения F и Р приведены в табл. 4.2.Т а б л и ц а 4.2Fтк —Fi/'F,Р,гГ1250,527003610,14340,4Кроссовер (скрещивание). Кроссовер, иногда называемый кроссинговером, заключается в передаче участков генов от родителей к потомкам. Припростом (одноточечном) кроссовере хромосомы родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как это показано в табл.
4.3, где разрыв подразумевается междупятым и шестым локусами.Т а б л и ц а 4.3ХромосомаГеныРодителя АfасdgkVeРодителя ВаЪсde/ghПотомка Сfасdg/ghПотомка DаЪсdekVeМутации. Оператор мутации выполняется с некоторой вероятностью Рм,т. е. с вероятностью Ри происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска.Селекция. После каждого акта генерации пары потомков в новое поколение включается лучший экземпляр пары.Внутренний цикл заканчивается, когда число экземпляров нового поколениястанет равным N.
Количество повторений G внешнего цикла чаще всего определяется автоматически по появлению признаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита машинного времени.1874. Математическое обеспечение синтеза проектных решенийРазновидности генетических операторовВозможны отклонения от представленной выше в простом генетическомалгоритме схемы вычислений.Кроссовер. Во-первых, допустимы схемы многоточечного кроссовера.Во-вторых, отметим ситуации, когда на состав аллелей наложены некоторые дополнительные условия. Например, пусть в задаче разбиения графа число вершин в подграфах А, и А2 должно быть N, и N2 и пусть &-й аллель, равный1, означает, что вершина k попадает в А р если же k-й аллель равен 0, то в А2.Очевидно, что число единиц в хромосоме должно равняться N}, число нулей —Nr Тогда при рекомбинации левый участок хромосомы берется от одного изродителей без изменений, а в правом участке (от другого родителя) нужносогласовать число единиц с Af, тем или иным способом.Один из способов — метод РМХ (Partially Matched Crossover).
Для иллюстрации РМХ рассмотрим пример двухточечного кроссовера в задаче, когда вхромосоме должны присутствовать, причем только по одному разу, все значения генов из заданного набора. Пусть в примере этот набор включает числа от1 до 9.В табл. 4.4 первые две строки представляют родительские хромосомы.Третья строка содержит хромосому одного из потомков, сгенерированного врезультате применения двухточечного кроссовера (после второго и пятого локусов). Полученная хромосома не относится к числу допустимых, так как вней значения генов 1,2 и 9 встречаются дважды, а значения 3, 4 и 5 отсутствуют. Четвертая строка показывает результат применения РМХ. В этом методевыделяются сопряженные пары аллелей в одноименных локусах одной из рекомбинируемых частей.
В нашем примере это пары (3 и 1), (4 и 9), (5 и 2).Хромосома потомка просматривается слева направо; если повторно встречается некоторое значение, оно заменяется сопряженным значением. Так, в примере в локусах 3,5 и 9 повторно встречающиеся аллели 1,2 и 9 последовательно заменяются значениями 3, 5 и 4.Т а б л и ц а 4.4124563789371924865121926789123956784Мутации. Бывают точечные мутации (в одном гене), макромутации (в нескольких генах) и хромосомные (появление новой хромосомы).
Обычно вероятность появления мутации указывается среди исходных данных. Но возможно автоматическое регулирование числа мутаций при их реализации только вситуациях, когда родительские хромосомы различаются не более чем в К генах.1884 4 Методы структурного синтеза в системах автоматизированного проектированияСелекция. После определения и положительной оценки потомка, он можетбыть сразу же включен в текущую популяцию вместо худшего из своих родителей, при этом из алгоритма исключается внешний цикл (что, однако, не означает сокращения общего объема вычислений).Другой вариант селекции — отбор после каждой операции скрещивания двухлучших экземпляров среди двух потомков и двух родителей.Часто член популяции с минимальным (лучшим) значением целевой функции принудительно включается в новое поколение, что гарантирует наследование приобретенных этим членом положительных свойств.
Такой подход называют элитизмом. Обычно элитизм способствует более быстрой сходимости клокальному экстремуму, однако в многоэкстремальной ситуации ограничиваетвозможности попадания в окрестности других локальных экстремумов.П р и м е ч а н и е . Хромосому X* будем называть точкой локального минимума, еслиF (X*) < F (X ) для всех хромосом X , отличающихся от X* значением единственного гена,где F (X) — значение функции полезности в точке X.Следующий вариант селекции — отбор N экземпляров среди членов репродукционной группы, которая составляется из родителей, потомков и мутантов,удовлетворяющих условию F < /, где /— пороговое значение функции полезности.
Порог может быть равен или среднему значению F в текущем поколении,или значению F особи, занимающей определенное порядковое место. При этомсуть мягкой схемы отбора — включение в новое поколение N лучших представителей репродукционной группы. Жесткая схема отбора — в новое поколениеэкземпляры включаются с вероятностью q:q=(FчiVNrmax- F,/) / X_]( Fmax-F),1'где Nr— размер репродукционной группы.Переупорядочение. Кроме перечисленных основных операторов находятприменение некоторые дополнительные. К их числу относится оператор переупорядочения генов — изменения их распределения по локусам.Назначение переупорядочения связано со свойством, носящим названиеэпистасис.
Эпистасис имеет место, если функция полезности зависит не только от значений генов (аллелей), но и от их позиционирования. Наличие эпистасиса говорит о нелинейности целевой функции и существенно усложняет решение задач. Действительно, если некоторые аллели двух генов оказываютопределенное положительное влияние на целевую функцию, образуя некоторуюсвязку (схему), но вследствие эпистасиса при разрыве связки эти аллели оказывают уже противоположное влияние на функцию полезности, то разрыватьтакие схемы не следует. А это означает, что связанные эпистасисом гены желательно располагать близко друг к другу, т. е.
при небольших длинах схем.Оператор переупорядочения помогает автоматически «нащупать» такие совокупности генов (их называют хромосомными блоками или building blocks) и разместить их в близких локусах.1894. Математическое обеспечение синтеза проектных решенийГенетический метод комбинирования эвристикВозможны два подхода к формированию хромосом. Первый из них основанна использовании в качестве генов проектных параметров.
Например, в задачеразмещения микросхем на плате локусы соответствуют посадочным местамна плате, а генами являются номера (имена) микросхем. Другими словами,значением £-го гена будет номер микросхемы в k-й позиции.Во втором подходе генами являются не сами проектные параметры, а номера эвристик, используемых для определения проектных параметров. Так,для задачи размещения можно применять несколько эвристик.
По одной из них,в очередное посадочное место нужно помещать микросхему, имеющую наибольшее число связей с уже размещенными микросхемами, по другой — микросхему с минимальным числом связей с еще не размещенными микросхемами и т. д. Генетический поиск в этом случае есть поиск последовательностиэвристик, обеспечивающей оптимальный вариант размещения.Второй подход получил название метод комбинирования эвристик. Этотметод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т.
е. проектнымипараметрами для каждой работы будут номер сервера и порядковый номер вочереди на обслуживание. Пусть N— число работ, М— число серверов. Еслигены соответствуют номерам работ, то в первом подходе в хромосоме нужноиметь 2N генов и общее число отличающихся друг от друга хромосом W заметно превышает наибольшее из чисел N ! и MN.Согласно методу комбинирования эвристик, число генов в хромосоме в 2раза меньше, чем в первом подходе, и равно N. Поэтому если число используемых эвристик равно К, то мощность множества возможных хромосом уженесравнимо меньше, а именно:Очевидно, что меньший размер хромосомы ведет к лучшей вычислительной эффективности, а меньшее значение Ж позволяет быстрее найти окрестности искомого экстремума.
Кроме того, в методе комбинирования эвристик всехромосомы, генерируемые при кроссовере, будут допустимыми. В то же время при применении обычных генетических методов необходимо использоватьпроцедуры типа РМХ для корректировки генов, относящихся к номерам в очереди на обслуживание, что также снижает эффективность поиска.Примеры применения метода комбинирования эвристикРассмотрим примеры постановки задач оптимизации и структурного синтеза для решения генетическими методами.
В каждом из представленных нижеклассов задач при использовании НСМ можно получить значительно лучшееприближение к экстремуму по сравнению с альтернативными одноэвристическими методами.1904.4. Методы структурного синтеза в системах автоматизированного проектированияКомпоновка. Содержательная суть задачи компоновки — распределениеработ по исполнителям, оборудования — по помещениям, прикладного ПО и БД— по подсетям виртуальной локальной вычислительной сети и т. п.Задача компоновки оборудования, в частности, может заключаться в распределении микросхем по модулям (платам или типовым элементам замены),модулей — по панелям, панелей — по шкафам РЭА или приборов — по отсекамкорабля и т. п.Пусть задача характеризуется следующими исходными данными:Р — множество элементов (конструктивов) Р, /' = 1,..., п;В — множество блоков В ,j = 1, ..., т;С — множество связей, связь Сл соединяет элементы Р и ?k.D — матрица п х и, элемент которой Dik равен числу связей между элементами Р и Р .Опишем множество альтернатив А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
