Норенков И.П. - Автоматизированное производство (1054022), страница 43
Текст из файла (страница 43)
Если в исходном виде задача многокритериальна, то такая формулировка означает выбор скалярного (обобщенного) критерия;3) Разработать математическую модель объекта, представляющую собой алгоритм вычисленияF для заданного вектора N;4) Представить вектор N в форме хромосомы — записи следующего видаP1P2P3....PnВ ГА используется следующая терминология:8$* — управляемый параметр xi;)44$45 — значение гена;&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1165@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M4#%7+ (0#6'='9) — позиция, занимаемая геном в хромосоме;8$*#&'0 — экземпляр хромосомы, генотип представляет совокупность внутренних параметровпроектируемого с помощью ГА объекта;8$*#E#*- — множество всех возможных генотипов;E7*%='9 0#4$6*#+&' (приспособленности) F — целевая функция;E$*#&'0 — совокупность генотипа и соответствующего значения F, под фенотипом часто понимают совокупность выходных параметров синтезируемого с помощью ГА объекта."84,-42 @.0.-+A.,7+2 :D@48+-/.
Вычислительный процесс начинается с генерации исходного поколения — множества, включающего N хромосом, N — размер популяции. Генерация выполняется случайным выбором аллелей каждого гена.Далее организуется циклический процесс смены поколений:for (k=0; k<G; k++){ for (j=0; j<N; j++){ D6&)" ")1,.#(/25)7 8$"6 @")%)2)%;F")22):#";='.$>,,;9>#+5$ C'+5>,, 8)(#3+)2., F 8).)%5):;G#(#5>,4;}H$%#+$ .#5'?#*) 8)5)(#+,4 +):6%;}Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, накотором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цикле повторяются операторы выбора родителей, кроссовера родительских хромосом, мутации, оценкиприспособленности потомков, селекции хромосом для включения в очередное поколение.Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.I.2#" "#-'&$4$;.
Этот оператор имитирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями функции полезности F более вероятен. Например, пусть F требуется минимизировать. Тогда вероятность Si выбора родителя с хромосомой Ci можно рассчитать поформулеNSi = (Fmax-Fi) / ∑ (Fmax - Fj)(4.31)j=Wгде Fmax — наихудшее значение целевой функции F среди экземпляров (членов) текущего поколения,Fi — значение целевой функции i-го экземпляра.Правило (4.31) называют 0")('4#/ %#4$+) "74$&%'. Если в колесе рулетки выделить секторы,пропорциональные значениям Fmax-Fi, то вероятности попадания в них суть Pi, определяемые в соответствии с (4.31).+ - 0 B .
- . Пусть N=4, значения Fi и Pi приведены в табл. 4.2.M:BD+=: 4.2iFiFmax-FiPi1250,527003610,14340,4&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1175@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&MO"#++#($" (+%"$A'()*'$). Кроссовер, иногда называемый кроссинговером, заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном) кроссовере хромосомыродителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрываравновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, какэто показано в табл. 4.3, где разрыв подразумевается между пятым и шестым локусами.M:BD+=: 4.3ХромосомаГеныродителя Afacdgkveродителя Babcdefghпотомка *facdgfghпотомка DabcdekveL7&)=''.
Оператор мутации выполняется с некоторой вероятностью Sм, т.е. с вероятностью Sмпроисходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска.:$4$%='9. После каждого акта генерации пары потомков в новое поколение включается лучшийэкземпляр пары.Внутренний цикл заканчивается, когда число экземпляров нового поколения станет равным N.Количество повторений G внешнего цикла чаще всего определяется автоматически по появлениюпризнаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита машинного времени.%:?049+504,-+ @.0.-+A.,7+6 43.8:-4849. Возможны отклонения от представленной выше впростом генетическом алгоритме схемы вычислений.O"#++#($". Во-первых, допустимы схемы многоточечного кроссовера.Во-вторых, отметим ситуации, когда на состав аллелей наложены некоторые дополнительныеусловия.
Например, пусть в задаче разбиения графа число вершин в подграфах C1 и C2 должно бытьN1 и N2 и пусть k-й аллель, равный 1, означает, что вершина k попадает в C1, если же k-й аллель равен0, то в C2. Очевидно, что число единиц в хромосоме должно равняться N1, число нулей — N2. Тогдапри рекомбинации левый участок хромосомы берется от одного из родителей без изменений, а в правом участке (от другого родителя) нужно согласовать число единиц с N1 тем или иным способом.Один из способов — метод PMX (Partially Matched Crossover). Для иллюстрации PMX рассмотрим пример двухточечного кроссовера в задаче, когда в хромосоме должны присутствовать, причемтолько по одному разу, все значения генов из заданного набора. Пусть в примере этот набор включает числа от 1 до 9.M:BD+=: 4.4В табл. 4.4 первые две строки представляют родительские хромосомы.
Третья стро)23456789ка содержит хромосому одного из потомков,37)924865сгенерированного в результате применения)2)926789двухточечного кроссовера (после второго ипятого локусов). Полученная хромосома не)23956784относится к числу допустимых, так как вней значения генов 1, 2 и 9 встречаются дважды, а значения 3, 4 и 5 отсутствуют. Четвертая строка показывает результат применения РМХ. В этом методе выделяются сопряженные пары аллелей в одноименных локусах одной из рекомбинируемых частей.
В нашем примере это пары (3 и 1), (4 и 9), (5 и2). Хромосома потомка просматривается слева направо; если повторно встречается некоторое значение, оно заменяется на сопряженное значение. Так, в примере в локусах 3, 5 и 9 повторно встречаю&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1185@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mщиеся аллели 1, 2 и 9 последовательно заменяются на значения 3, 5 и 4.L7&)=''. Бывают точечными (в одном гене), макромутациями (в нескольких генах) и хромосомными (появление новой хромосомы). Обычно вероятность появления мутации указывается среди исходных данных. Но возможно автоматическое регулирование числа мутаций при их реализации только в ситуациях, когда родительские хромосомы различаются не более чем в K генах.:$4$%='9.
После определения и положительной оценки потомка он может быть сразу же включен в текущую популяцию вместо худшего из своих родителей, при этом из алгоритма исключаетсявнешний цикл (что однако не означает сокращения общего объема вычислений).Другой вариант селекции — отбор после каждой операции скрещивания двух лучших экземпляров среди двух потомков и двух родителей.Часто член популяции с минимальным (лучшим) значением целевой функции принудительновключается в новое поколение, что гарантирует наследование приобретенных этим членом положительных свойств.
Такой подход называют B4'&'6/#/. Обычно элитизм способствует более быстройсходимости к локальному экстремуму, однако в многоэкстремальной ситуации ограничивает возможности попадания в окрестности других локальных экстремумов.+ - 0 B .F 6 9 0 . . Хромосому N* будем называть точкой локального минимума, если F(X*)<F(Xi) для всех хромосом Xi, отличающихся от X* значением единственного гена, где F(X) — значение функции полезности в точке N.Следующий вариант селекции — отбор N экземпляров среди членов репродукционной группы,которая составляется из родителей, потомков и мутантов, удовлетворяющих условию Fi < t, где t —пороговое значение функции полезности. Порог может быть равен или среднему значению F в текущем поколении, или значению F особи, занимающей определенное порядковое место.
При этом мягкая схема отбора — в новое поколение включаются N лучших представителей репродукционной группы. Жесткая схема отбора — в новое поколение экземпляры включаются с вероятностью qi:Nrqi = (Fmax-Fi) / ∑ (Fmax - Fj)j=Wгде Nr — размер репродукционной группы.!$"$70#"9-#1$*'$. Кроме перечисленных основных операторов, находят применение некоторыедополнительные. К их числу относится оператор переупорядочения генов — изменения их распределения по локусам.Назначение переупорядочения связано со свойством, носящим название эпистасис. F0'+&)+'+имеет место, если функция полезности зависит не только от значений генов (аллелей), но и от их позиционирования.
Наличие эпистасиса говорит о нелинейности целевой функции и существенно усложняет решение задач. Действительно, если некоторые аллели двух генов оказывают определенноеположительное влияние на целевую функцию, образуя некоторую связку (схему), но вследствие эпистасиса при разрыве связки эти аллели оказывают уже противоположное влияние на функцию полезности, то разрывать такие схемы не следует. А это означает, что связанные эпистасисом гены желательно располагать близко друг к другу, т.е. при небольших длинах схем. Оператор переупорядоченияпомогает автоматически “нащупать” такие совокупности генов (они называются хромосомными блоками или building blocks) и разместить их в близких локусах.K.0.-+A.,7+2 /.-45 74/B+0+849:0+> T98+,-+7.
Возможны два подхода к формированиюхромосом.Первый из них основан на использовании в качестве генов проектных параметров. Например, взадаче размещения микросхем на плате локусы соответствуют посадочным местам на плате, а генамиявляются номера (имена) микросхем. Другими словами, значением k-го гена будет номер микросхемыв k-й позиции.Во втором подходе генами являются не сами проектные параметры, а номера эвристик, используемых для определения проектных параметров. Так, для задачи размещения можно применять несколько эвристик. По одной из них в очередное посадочное место нужно помещать микросхему, имеющую наибольшее число связей с уже размещенными микросхемами, по другой — микросхему с минимальным числом связей с еще не размещенными микросхемами и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
