Автоматизированное проектирование. Норенков И.П. - 116 стр.

 5@!"! 4                            %!#*%!#&F*:,$*    $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

классу NP-полных задач, и если это так, то не следует тратить усилия на разработку алгоритмов и про-
грамм точного решения; 2) отсутствие эффективных алгоритмов точного решения массовой задачи
выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса
NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за
полиномиальное время.
       Q94D;=+4001. /.-451. F(#4<='#**.$ /$&#-. (ЭМ) предназначены для поиска предпочти-
тельных решений и основаны на статистическом подходе к исследованию ситуаций и итерационном
приближении к искомому состоянию систем.
       В отличие от точных методов математического программирования ЭМ позволяют находить ре-
шения, близкие к оптимальным, за приемлемое время, а в отличие от известных эвристических мето-
дов оптимизации характеризуются существенно меньшей зависимостью от особенностей приложения
(т.е. более универсальны) и в большинстве случаев обеспечивают лучшую степень приближения к оп-
тимальному решению. Универсальность ЭМ определяется также применимостью к задачам с немет-
ризуемым пространством управляемых переменных (т.е. среди управляемых переменных могут быть
и лингвистические).
       Важнейшим частным случаем ЭМ являются 8$*$&'1$+%'$ /$&#-. ' )48#"'&/.. Генетические
алгоритмы (ГА) основаны на поиске лучших решений с помощью наследования и усиления полезных
свойств множества объектов определенного приложения в процессе имитации их эволюции.
       Свойства объектов представлены значениями параметров, объединяемыми в запись, называе-
мую в ЭМ ,"#/#+#/#;. В ГА оперируют хромосомами, относящимися к множеству объектов — 0#07-
49=''. Имитация генетических принципов — вероятностный выбор родителей среди членов популя-
ции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на осно-
ве оценки целевой функции — ведет к эволюционному улучшению значений целевой функции (функ-
ции полезности) от поколения к поколению.
       Среди ЭМ находят применение также методы, которые в отличие от ГА оперируют не множест-
вом хромосом, а единственной хромосомой. Так, метод дискретного 4#%)45*#8# 0#'+%) (его англо-
язычное название Hillclimbing) основан на случайном изменении отдельных параметров (т.е. значений
полей в записи или, другими словами, значений генов в хромосоме). Такие изменения называют /7-
&)='9/'. После очередной мутации оценивают значение E7*%='' 0#4$6*#+&' F (Fitness Function) и
результат мутации сохраняется в хромосоме только, если F улучшилась. В другом ЭМ под названием
“L#-$4'"#()*'$ #&@'8)” (Simulated Annealing) результат мутации сохраняется с некоторой вероят-
ностью, зависящей от полученного значения F.
       "4,-:0497: ?:5:A+ 34+,7: 43-+/:DF016 8.I.0+2 , 34/4RF; @.0.-+A.,7+6 :D@48+-/49.
Для применения ГА необходимо:
       1) выделить совокупность свойств объекта, характеризуемых внутренними параметрами и вли-
яющих на его полезность, т.е. выделить множество управляемых параметров X = (x1,x2,...xn); среди xi
могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых ве-
личин (enumeration) обусловливает возможность решения задач не только параметрической, но и
структурной оптимизации;
       2) сформулировать количественную оценку полезности вариантов объекта — функцию полезно-
сти F. Если в исходном виде задача многокритериальна, то такая формулировка означает выбор ска-
лярного (обобщенного) критерия;
       3) Разработать математическую модель объекта, представляющую собой алгоритм вычисления
F для заданного вектора N;
       4) Представить вектор N в форме хромосомы — записи следующего вида
                            P1     P2     P3          ....        Pn

     В ГА используется следующая терминология:
     8$* — управляемый параметр xi;
     )44$45 — значение гена;

 &.+.)$(*),$" . !"#$%!#&'&($"!))$*         +($*,#&($"!)&*                                   116