Норенков И.П. - Основы автоматизированного проектирования (1060628), страница 43
Текст из файла (страница 43)
В ГА оперируют хромосомами,относящимися к множеству объектов — популяции. Имитация генетическихпринципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции — ведет к эволюционному улучшениюзначений целевой функции (функции полезности) от поколения к поколению.Среди ЭМ находят применение также методы, которые в отличие от ГАоперируют не множеством хромосом, а единственной хромосомой.
Так, методдискретного локального поиска (его англоязычное название hillclimbing) основан на случайном изменении отдельных параметров (т. е. значений полей взаписи или, другими словами, значений генов в хромосоме). Такие измененияназывают мутациями. После очередной мутации оценивают значение функции полезности F (fitness function) и результат мутации сохраняется в хромосоме, только если F улучшилась. В другом ЭМ под названием «Моделирование отжига» (Simulated Annealing) результат мутации сохраняется с некоторойвероятностью, зависящей от полученного значения F.Постановка задачи поиска оптимальных решенийс помощью генетических алгоритмовДля применения генетических алгоритмов необходимо:1) выделить совокупность свойств объекта, характеризуемых внутреннимипараметрами и влияющих на его полезность, т.
е. выделить множество управляемых параметров X = (г,, х2, ..., хп); среди * могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин(enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;2) сформулировать количественную оценку полезности вариантов объекта— функцию полезности F. Если в исходном виде задача многокритериальна, тотакая формулировка означает выбор скалярного (обобщенного) критерия;3) разработать математическую модель объекта, представляющую собойалгоритм вычисления F для заданного вектора X;4) представить вектор X в форме хромосомы — записи следующего вида:х\Х2XT,хп1854. Математическое обеспечение синтеза проектных решенийВ генетических алгоритмах используется такая терминология:ген — управляемый параметр xt;аллель — значение гена;локус (позиция) — позиция, занимаемая геном в хромосоме;генотип — экземпляр хромосомы, генотип представляет собой совокупность внутренних параметров проектируемого с помощью алгоритма объекта;генофонд — множество всех возможных генотипов;функция полезности (приспособленности) F — целевая функция;фенотип — совокупность генотипа и соответствующего значения F, подфенотипом часто понимают совокупность выходных параметров синтезируемого с помощью ГА объекта.Простой генетический алгоритмВычислительный процесс начинается с генерации исходного поколения —множества, включающего N хромосом (N- размер популяции).
Генерация выполняется случайным выбором аллелей каждого гена.Далее организуется циклический процесс смены поколений:for (&=0; k<G;{for(j=0;j<N;j++){Выбор родительской пары хромосом;Кроссовер;Мутации;Оценка функции полезности F потомков;Селекция;}Замена текущего поколения новым;Для каждого витка внешнего цикла генетического алгоритма выполняетсявнутренний цикл, на котором формируются экземпляры нового (следующего затекущим) поколения.
Во внутреннем цикле повторяются операторы выборародителей, кроссовера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение.Рассмотрим алгоритмы выполнения операторов в простом генетическомалгоритме.Выбор родителей. Этот оператор имитирует естественный отбор, еслиотбор в родительскую пару хромосом с лучшими значениями функции полезности F более вероятен. Например, пусть F требуется минимизировать.
Тогдавероятность Р выбора родителя с хромосомой С можно рассчитать по формуле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-й позиции.Во втором подходе генами являются не сами проектные параметры, а номера эвристик, используемых для определения проектных параметров. Так,для задачи размещения можно применять несколько эвристик. По одной из них,в очередное посадочное место нужно помещать микросхему, имеющую наибольшее число связей с уже размещенными микросхемами, по другой — микросхему с минимальным числом связей с еще не размещенными микросхемами и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
