Норенков И.П. - Автоматизированное производство (1054022), страница 42
Текст из файла (страница 42)
В-третьих, функции J(X)должны отражать внутренне присущие данному классу объектов свойства, что обеспечит возможность использования J(X) в качестве не только средств оценки достигнутого при поиске успеха, но исредств указания перспективных направлений продолжения поиска. Эти условия выполнимы далеконе всегда, что и обусловливает трудности формализации задач структурного синтеза.Однако наличие формулировки (4.30) еще не означает, что удастся подобрать метод (алгоритм)решения задачи (4.30) с приемлемыми затратами вычислительных ресурсов.
Другими словами, применение точных методов математического программирования вызывает непреодолимые трудности вбольшинстве случаев практических задач типичного размера из-за их принадлежности к классу NPтрудных задач. Поэтому лидирующее положение среди методов решения задачи (4.30) занимают приближенные методы, в частности, декомпозиционные методы, отражающие принципы блочно-иерархического проектирования сложных объектов. Декомпозиционные методы основаны на выделенииряда иерархических уровней, на каждом из которых решаются задачи приемлемого размера.Основу большой группы математических методов, выражающих стремление к сокращению перебора, составляют операции разделения множества вариантов на подмножества и отсечения неперспективных подмножеств.
Эти методы объединяются под названием /$&#-) ($&($; ' 8")*'=. Основная разновидность метода ветвей и границ относится к точным методам решения комбинаторных задач. Рассмотрим эту разновидность.Пусть имеется множество решений M, в котором нужно выбрать оптимальный по критериюF(Xj) вариант, где Xj — вектор параметров варианта mj ∈ M; пусть также имеется алгоритм для вычисления нижней границы L(Mk) критерия F(Xj) в любом подмножестве Mk множества M, т.е.
такогозначения L(Mk), что F(Xj) ≥ L(Mk) при любом j (подразумевается минимизация F(X)). Тогда основнаясхема решения задач в соответствии с методом ветвей и границ содержит следующие процедуры: 1)в качестве Mk принимаем все множество M; 2) ветвление: разбиение Mk на несколько подмножествMq; 3) вычисление нижних границ L(Mq) в подмножествах Mq; 4) выбор в качестве Mk подмножестваMp с минимальным значением нижней границы критерия (среди всех подмножеств, имеющихся наданном этапе вычислений), сведения об остальных подмножествах Mq и их нижних границах сохраняются в отдельном списке; 5) если | Mk| > 1, то переход к процедуре 2, иначе одноэлементное множество Mk есть решение.Метод ветвей и границ в случае точного вычисления нижних границ относится к точным методам решения задач выбора и потому в неблагоприятных ситуациях может приводить к экспоненциальной временной сложности.
Однако метод часто используют как приближенный, поскольку можноприменять приближенные алгоритмы вычисления нижних границ.Среди других приближенных методов решения задачи ДМП отметим /$&#- 4#%)45*#; #0&'/'6)=''. Так как пространство D метризовано, то можно использовать понятие )-окрестности Sa(Xk) текущей точки поиска Xk. Вместо перебора точек во всем пространстве D осуществляется перебор точек только в Sa(Xk). Если F(Xj) ≥ F(Xk) для всех Nj ∈ Sa(Xk), то считается, что найден локальный минимум целевой функции в точке Xk.
В противном случае точку Xq, в которой достигается минимумF(X) в Sa(Xk), принимают в качестве новой текущей точки поиска.&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1145@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&MQD./.0-1 -.48++ ,D4L04,-+. В теории сложности выделяют массовые и индивидуальные задачи. Первые из них сформулированы в общем виде, вторые представлены с конкретными числовыми значениями исходных данных. Исследования сложности проводятся в отношении массовых задачи получаемые выводы, как правило, относятся к наихудшему случаю — к наиболее неблагоприятному возможному сочетанию исходных данных.Цель исследований — установление вида зависимости объема Q требуемых вычислений от размера задачи N.
Объем вычислений может определяться числом арифметических и логических операций или затратами процессорного времени ЭВМ с заданной производительностью. Размер задачи вобщем случае связывают с объемом описания задачи, но в приложениях понятие размера легко наполняется более конкретным содержанием.Далее, в теории сложности задач выбора вводят понятие эффективных и неэффективных алгоритмов. К эEE$%&'(*./ относят алгоритмы с полиномиальной зависимостью Q от N, например, алгоритмы с функцией Q(N) линейной, квадратичной, кубической и др. Для *$BEE$%&'(*., алгоритмовхарактерна экспоненциальная зависимость Q(N).Важность проведения резкой границы между полиномиальными и экспоненциальными алгоритмами вытекает из сопоставления числовых примеров роста допустимого размера задачи с увеличением быстродействия Б используемых ЭВМ (табл.
4.1, в которой указаны размеры задач, решаемых заодно и то же время ? на ЭВМ с быстродействием Бi при различных зависимостях сложности Q от размера N). Эти примеры показывают, что выбирая ЭВМ в O раз более быстродействующую, получаемувеличение размера решаемых задач при линейных алгоритмах в O раз, при квадратичных алгоритмах в К1/2 раз и т.д.M:BD+=: 4.)Иначе обстоит дело с неэффективнымиQ(N)Б1Б2 = 100 Б1Б3 = 1000 Б1алгоритмами. Так, в случае сложности 2N дляодного и того же процессорного времени разNN1100 N11000 N1мер задачи увеличивается только на lgK / lg2N2N210 N231.6 N2единиц. Следовательно, переходя от ЭВМ сБ = 1 Gflops к суперЭВМ с Б = 1 Tflops, можN3N34.64 N310 N3но увеличить размер решаемой задачи только2NN46.64+N49.97+N4на 10, что совершенно недостаточно для практических задач. Действительно, в таких задачах, как например, синтез тестов для БИС число входных двоичных переменных может составлять более 150 и поэтому полный перебор всех возможных проверяющих кодов потребует выполнения более2150 вариантов моделирования схемы.В теории сложности все комбинаторные задачи разделены на классы:— класс неразрешимых задач, в который входят массовые задачи, решение которых полным перебором принципиально невозможно с точки зрения современных научных представлений; этот классотделяется от других задач так называемым пределом Бреммермана, оцениваемым величиной N =1093; отметим, что реальный предел неразрешимости значительно ниже;— класс P, к которому относятся задачи, для которых известны алгоритмы решения полиномиальной сложности;— класс NP, включающий задачи, для которых можно за полиномиальное время проверить правильность решения, т.е.
ответить на вопрос, удовлетворяет ли данное решение заданным условиям;очевидно, что P включено в NP, однако вопрос о совпадении этих классов пока остается открытым,хотя по-видимому на этот вопрос будет получен отрицательный ответ;— класс NP-полных задач, характеризующийся следующими свойствами: 1) для этих задач неизвестны полиномиальные алгоритмы точного решения; 2) любые задачи внутри этого класса могутбыть сведены одна к другой за полиномиальное время. Последнее означает, что если будет найден полиномиальный алгоритм для точного решения хотя бы одной NP-полной задачи, то за полиномиальное время можно будет решить любую задачу этого класса.Из результатов теории сложности следуют важные практические рекомендации: 1) приступая крешению некоторой комбинаторной задачи, следует сначала проверить, не принадлежит ли она к&.+.)$(*),$" .
!"#$%!#&'&($"!))$*+($*,#&($"!)&*1155@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mклассу NP-полных задач, и если это так, то не следует тратить усилия на разработку алгоритмов и программ точного решения; 2) отсутствие эффективных алгоритмов точного решения массовой задачивыбора отнюдь не означает невозможности эффективного решения индивидуальных задач из классаNP-полных или невозможности получения приближенного решения по эвристическим алгоритмам заполиномиальное время.Q94D;=+4001.
/.-451. F(#4<='#**.$ /$&#-. (ЭМ) предназначены для поиска предпочтительных решений и основаны на статистическом подходе к исследованию ситуаций и итерационномприближении к искомому состоянию систем.В отличие от точных методов математического программирования ЭМ позволяют находить решения, близкие к оптимальным, за приемлемое время, а в отличие от известных эвристических методов оптимизации характеризуются существенно меньшей зависимостью от особенностей приложения(т.е.
более универсальны) и в большинстве случаев обеспечивают лучшую степень приближения к оптимальному решению. Универсальность ЭМ определяется также применимостью к задачам с неметризуемым пространством управляемых переменных (т.е. среди управляемых переменных могут бытьи лингвистические).Важнейшим частным случаем ЭМ являются 8$*$&'1$+%'$ /$&#-. ' )48#"'&/.. Генетическиеалгоритмы (ГА) основаны на поиске лучших решений с помощью наследования и усиления полезныхсвойств множества объектов определенного приложения в процессе имитации их эволюции.Свойства объектов представлены значениями параметров, объединяемыми в запись, называемую в ЭМ ,"#/#+#/#;.
В ГА оперируют хромосомами, относящимися к множеству объектов — 0#0749=''. Имитация генетических принципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции — ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению.Среди ЭМ находят применение также методы, которые в отличие от ГА оперируют не множеством хромосом, а единственной хромосомой. Так, метод дискретного 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
