Норенков И.П. - Основы автоматизированного проектирования (1060628), страница 42
Текст из файла (страница 42)
е. ответить на вопрос, удовлетворяет ли данное решение заданным условиям; очевидно, что Р включено в NP, од-1814. Математическое обеспечение синтеза проектных решенийнако вопрос о совпадении этих классов пока остается открытым, хотя, по-видимому, на этот вопрос будет получен отрицательный ответ;• класс NP-полных задач, характеризующийся следующими свойствами:1) для этих задач не известны полиномиальные алгоритмы точного решения;2) любые задачи внутри этого класса могут быть сведены одна к другой заполиномиальное время. Последнее означает, что если будет найден полиномиальный алгоритм для точного решения хотя бы одной NP-полной задачи, то заполиномиальное время можно будет решить любую задачу этого класса.Из результатов теории сложности следуют важные практические рекомендации: 1) приступая к решению некоторой комбинаторной задачи, необходимосначала проверить, не принадлежит ли она к классу NP-полных задач, и еслиэто так, то не следует тратить усилия на разработку алгоритмов и программточного решения; 2) отсутствие эффективных алгоритмов точного решения массовой задачи выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за полиномиальноевремя.Методы локальной оптимизации и поиска с запретамиСреди приближенных методов решения задачи (4.30) часто используемымявляется метод локальной оптимизации.
Так как пространство D метризовано,то можно использовать понятие а-окрестности So(Xt) текущей точки поискаXk. Вместо перебора точек во всем пространстве D осуществляется перебортолько в Sa(Xt). Если F(X ) > F (Х^) для всех Х^ € So(Xt), то считается, что найден локальный минимум целевой функции в точке Хг В противном случае точку X , в которой достигается минимум F(X) в So(Xt), принимают в качественовой текущей точки поиска.Недостатком метода является его явно выраженная локальность — «застревание» в окрестностях локальных экстремумов. Повысить эффективностьпоиска можно с помощью метода оптимизации с запретами (tabu search).
Дляэтого в 8я(Х4) вводят запреты на попадание в некоторые точки. Обычно этозапреты на повторное исследование точек, пройденных на нескольких последних шагах оптимизации. Запрет распространяется и на лучшую точку Х^ предыдущего шага, которая может оказаться точкой локального минимума. Тогдана данном шаге перемещение происходит в лучшую незапрещенную точку Xt+1,несмотря на то что /r(X;t+]) > /*XXt). Тем самым появляется тенденция к выходу из области притяжения локального экстремума.Системы искусственного интеллектаВ теории интеллектуальных систем синтез реализуется с помощью экспертных системЭС = <БД,БЗ,И>,где БД — база данных, включающая сведения о базовых элементах; БЗ — базазнаний, содержащая правила конструирования вариантов структуры; И — ин-1824.4.
Методы структурного синтеза в системах автоматизированного проектированиятерпретатор, устанавливающий последовательность применения правил из базызнаний. Системы искусственного интеллекта основаны на знаниях, отделенных от процедурной части программ и представленных в одной из характерныхформ. Такими формами могут быть продукции, фреймы, семантические сети.Реально функционирующие в современных САПР системы с базами знанийчаще всего относятся к классу экспертных систем.Продукция представляет собой правило типа «если А, то 5», где А — условие, а В — действие или следствие, активизируемое при истинности А. Продукционная база знаний содержит совокупность правил, описывающих определенную предметную область.Фрейм — структура данных, в которой в определенном порядке представлены сведения о свойствах описываемого объекта.
Типичный вид фрейма:< имя фрейма; *, =/?,; х2 = р2; ... ; xN = pN; qv qv ..., qM >,где х — имя /-го атрибута; pi — его значение; q — ссылка на другой фрейм илинекоторую обслуживающую процедуру. В качествеpt можно использовать имядругого (вложенного) фрейма, описывая тем самым иерархические структурыфреймов.Семантическая сеть — форма представления знаний в виде совокупностипонятий и явно выраженных отношений между ними в некоторой предметнойобласти.
Семантическую сеть удобно изображать в виде графа, в котором вершины отображают понятия, а ребра или дуги — отношения между ними. Вкачестве вершин сети можно использовать фреймы или продукции.Экспертная система является типичной системой искусственного интеллекта, в которой база знаний содержит сведения, полученные от людей-экспертов в конкретной предметной области. Трудности формализации процедур структурного синтеза привели к популярности применения экспертных систем в САПР,поскольку в них вместо выполнения синтеза на базе формальных математических методов осуществляется синтез на основе опыта и неформальных рекомендаций, полученных от экспертов.Методы распространения ограниченийВо многих задачах структурного синтеза множество D допустимых вариантов, задаваемое ограничениями W(X) > 0 и (или) Z(X) = 0, включает сравнительно малое число элементов, и в качестве результатов синтеза принимаетсялюбой из этих вариантов. Такое решение задачи часто выполняют с помощьюметода распространения ограничений (constraints propagation).Сущность этого метода заключается в сужении допустимых интерваловуправляемых переменных X с помощью учета (распространения) исходныхограничений на выходные параметры W и Z.Для пояснения метода рассмотрим простой пример.
Пусть в задаче фигурируют триуправляемые целочисленные переменные х, у, z, заданы исходные интервалы допустимых значений этих переменных х е [1: 100], у е [1: 100], z e [10:100], а область Dопределена ограничениямиx+y>5z,(4.31)1834. Математическое обеспечение синтеза проектных решенийх>у+5.(4.32)Распространение ограничения (4.31) на интервал переменного z приводит к уменьшению его верхней границы, так как z < (хтх1+утгк)/5 = 40, а с учетом ограничения (4.32)- к его новой корректировке z < 39, поскольку jmax= 95, а также к увеличению нижнихграниц переменных х ну, так как решение неравенств х + у > 50 и (4.32) дает х>2В,у>22.Таким образом, получено сужение допустимой области х е [28:100],^ е [22:95],ze [10:39].Метод легко распространяется на задачи с нечисловыми параметрами. Вэтом случае вместо сокращения числовых интервалов уменьшают мощностидопустимых подмножеств значений параметров.Одним из практических приложений метода распространения ограниченийявляется поиск допустимых вариантов в множестве синтезируемых структурпри ограничениях типа (4.29) на совместимость элементов структуры.Пример.
Рассмотрим фрагмент структуры, состоящий из трех компонентов А, ВиС,причем Л е {а,, а2, ау а4, а;}, В е {&,, Ь2, Ъу Ь4}, С е {с,, с2, с}}. Заданы списки допустимыхсочетаний компонентов в синтезируемой структуре:L1: а,, Ь{; ау Ъ^ а4,Ь2, а5, Ь3; о5, £4;L2: Ь}, с,; Ъу су й4, с,; Ь4, с2;L3:a 2 , с3;а3, с2;а4, С3;а5,с2.Сокращение первого списка выполняется путем поочередного выбора в нем а(, фиксации в L3 соответствующих значений ck, а затем в L2 сопряженных с ck значений b'.
Еслив L1 имеется элемент a,, bj, то он сохраняется в сокращенном списке, остальные сочетания с а из L1 удаляются. В нашем примере, поскольку значения я, в L3 нет, то сочетаниеа,, и, недопустимо и из L1 удаляется. Далее для символа аг фиксируем в L3 значение суему в L2 соответствует только значение Ьу Поэтому а2, Ь, -также недопустимое сочетание. Обработав подобным образом все списки, получаем результат распространенияограничений в виде LI: a5,i>4;L2: 64,c2;L3: a},c2.Следовательно, решение состоит из единственной допустимой структуры, включающей компоненты ау 64, с3.В общем случае сокращение списков выполняется в итерационном процессе до совпадения их содержимого на двух последних итерациях.На базе метода распространения ограничений компанией ILOG создан программный комплекс оптимизации и синтеза проектных решений, состоящий изподсистем Solver, Configurator, Scheduler и др.Эволюционные методыЭволюционные методы (ЭМ) предназначены для поиска предпочтительных решений и основаны на статистическом подходе к исследованию ситуацийи итерационном приближении к искомому состоянию систем.В отличие от точных методов математического программирования ЭМ позволяют находить решения, близкие к оптимальным, за приемлемое время, а вотличие от известных эвристических методов оптимизации характеризуютсясущественно меньшей зависимостью от особенностей приложения (т.
е. болееуниверсальны) и в большинстве случаев обеспечивают лучшую степень приближения к оптимальному решению. Универсальность ЭМ определяется так1844 4 Методы структурного синтеза в системах автоматизированного проектированияже применимостью к задачам с неметризуемым пространством управляемыхпеременных (т. е. среди управляемых переменных могут быть и лингвистические).Важнейшим частным случаем ЭМ являются генетические методы и алгоритмы. Генетические алгоритмы основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.Свойства объектов представлены значениями параметров, объединяемыми в запись, называемую в ЭМ хромосомой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
