Норенков И.П. Основы автоматизированного проектирования

Подождите немного. Документ загружается.

Постановка

задач

структурного синтеза

•

формулировка предпочтений

многокритериальных ситуациях

(т. е.

пре-

образование векторного критерия

скалярную целевую функцию);

•

установление порядка (предпочтений) между альтернативами

отсутствие

количественной оценки целевой функции (что обычно является следствием

неколичественного характера всех

или

части критериев);

•

выбор

метода

поиска оптимального варианта (сокращение перебора вари-

антов).

Присущая проектным задачам неопределенность

нечеткость исходных

данных,

иногда

моделей, диктуют использование специальных методов

ко-

личественной формулировки исходных неколичественных данных

отношений.

Эти

специальные методы либо относятся

области построения измеритель-

ных

шкал, либо являются предметом теории нечетких множеств.

Измерительные шкалы могут быть:

абсолютными;

номинальными (классификационными), значения шкалы представляют

классы

эквивалентности, примером может служить шкала цветов; такие шка-

лы

соответствуют

величинам неколичественного характера;

порядковыми, если между объектами

АиВ

установлено одно

из

следую-

щих

отношений: простого порядка, гласящее,

что

если

лучше

В, то В

хуже

А и

соблюдается

транзитивность;

или

слабого порядка,

т. е.

либо

А не

хуже

В,

либо

не

лучше

В; или

частичного порядка.

Для

формирования целевой функции

F(X)

производится оцифровка порядковой шкалы,

т. е.

если

при

минимизации^

предпочтительнее

5, то

^(Х

)

F(X

где

—

множества атрибутов

объектов

АиВ

соответственно;

интервальными, отражающими количественные отношения интервалов:

шкала

единственна

точностью

до

линейных преобразований,

т. е. у

ах +

Ъ,

а>0,

оо

оо,

или у — ах при а

О,

или у = х + Ъ.

большинстве случаев структурного синтеза математическая модель

виде алгоритма, позволяющего

по

заданному множеству

X и

заданной струк-

туре объекта рассчитать вектор критериев

К,

оказывается известной. Напри-

мер, такие

модели

получаются автоматически

программах анализа типа Spice,

Adams

или

ПА-9

для

объектов, исследуемых

на

макроуровне. Однако

ряде

других случаев такие модели

не

известны

силу недостаточной изученности

процессов

и их

взаимосвязей

исследуемой

среде,

но

известна совокупность

результатов наблюдений

или

экспериментальных исследований. Тогда

для по-

лучения

моделей используют специальные методы идентификации

аппрокси-

мации

(модели, полученные подобным путем, иногда называют феноменологи-

ческими).

Среди методов формирования моделей

по

экспериментальным данным наи-

более известны методы планирования экспериментов.

Не

менее популярным

становится

подход,

основанный

на

использовании искусственных нейронных

сетей.

Если

же

математическая модель

-»

остается неизвестной,

то

стара-

ются использовать подход

на

базе систем

искусственного

интеллекта (экс-

пертных

систем).

173

Математическое обеспечение синтеза проектных

решений

Возможности практического решения задач дискретного математического

программирования

(ДМП)

изучаются

теории сложности задач выбора,

где

показано,

что

задачи даже умеренного размера, относящиеся

классу

NP-полных

задач,

общем

случае

удается решать только приближенно.

Поэтому большинство практических задач структурного синтеза решают

помощью приближенных (эвристических)

методов.

Это

методы,

использую-

щие

специфические особенности того

или

иного

класса

задач

и не

гарантирую-

щие

получения оптимального решения. Часто

они

приводят

результатам, близ-

ким

оптимальным,

при

приемлемых затратах вычислительных ресурсов.

Если

все

управляемые параметры альтернатив, обозначаемые

виде мно-

жества

являются количественными оценками,

то

используют приближен-

ные

методы

оптимизации. Если

в X

входят также параметры неколичествен-

ного характера

пространство

неметризуемо,

то

перспективными являются

эволюционные методы вычислений, среди которых наиболее развиты генети-

ческие методы. Наконец,

отсутствие, обоснованных моделей

Мод их

созда-

ют,

основываясь

на

экспертных знаниях

виде некоторой системы искусст-

венного интеллекта.

Представление

множества

альтернатив

Решению проблем упорядочения

описания множества альтернатив

свя-

зей

между ними

конкретных приложениях

посвящена

специальная область

знания,

которую

по

аналогии

наукой

описания множеств животных

растений

биологии можно назвать систематикой.

Простейший способ задания множества

А —

явное перечисление всех аль-

тернатив. Семантика

форма описания альтернатив существенно зависят

от

приложения.

Для

представления таких описаний

памяти

ЭВМ и

доступа

ним

используют информационно-поисковые системы

(ИПС).

Каждой альтер-

нативе

в ИПС

соответствует поисковый образ, состоящий

из

значений атрибу-

тов

ключевых слов вербальных характеристик.

Явное

перечисление альтернатив

при

представлении множества альтерна-

тив

возможно лишь

при

малой мощности

А. В

большинстве случаев использу-

ют

неявное описание

А в

виде способа (алгоритма

или

набора правил

Р)

синте-

за

проектных решений

из

ограниченного набора элементов

Э.

Поэтому здесь

А =

Р, Э >, а

типичный процесс синтеза проектных решений состоит

из

следу-

ющих

этапов:

формирование альтернативы

(это может быть выбор

из

базы данных

ИПС

по

сформированному поисковому предписанию

или

генерация

из Э в со-

ответствии

правилами

Р);

оценка альтернативы

по

результатам моделирования

помощью модели

Мод;

принятие решения относительно перехода

следующей альтернативе

или

прекращения

поиска (выполняется лицом, принимающим решение

(ЛПР),

или

автоматически).

174

Постановка

задач

структурного

синтеза

Для

описания множеств

Р и Э

используют следующие подходы:

морфологические таблицы

альтернативные

И-ШШ-деревья;

представление знаний

интеллектуальных системах

—

фреймы, семанти-

ческие

сети,

продукции;

генетические методы;

базы

физических

эффектов

эвристических приемов, применяемые

при ре-

шении задач изобретательского характера.

Морфологические

таблицы

Морфологическая

таблица

(М)

представляет собой обобщенную струк-

туру

виде множества функций, выполняемых компонентами синтезируемых

объектов

рассматриваемого класса,

подмножеств способов

их

реализации.

Каждой

функции можно поставить

соответствие одну строку таблицы, каж-

дому способу

ее

реализации

—

одну клетку

этой строке. Следовательно,

морфологических таблицах элемент

означает

у'-й

вариант реализации

i-й

функции

классе технических объектов, описываемом матрицей

М.

Другими словами, множество альтернатив можно представить

виде отно-

шения

М,

называемого морфологической таблицей:

где

X —

множество свойств (характеристик

или

функций), присущих объектам

рассматриваемого типа;

п —

число этих свойств;

R = <

...,

множество значений (способов реализации)

/-го

свойства, мощность этого

множества далее обозначена

При

этом собственно множество альтернатив

представлено композицией множеств

т. е.

каждая альтернатива включа-

ет по

одному элементу (значению)

из

каждой строки морфологической табли-

цы.

Очевидно,

что

общее число альтернатив

представляемых морфологи-

ческой

таблицей, равно

„

k=UN,

1=1

Морфологические таблицы обычно считают средством неавтоматизиро-

ванного

синтеза, помогающим человеку просматривать компактно представ-

ленные

альтернативы, преодолевать психологическую инерцию. Последнее свя-

зано

тем,

что

внимание

ЛПР

обращается

на

варианты, которые

без

морфологической

таблицы оставались

бы вне его

поля зрения.

Собственно

таблица

М не

содержит сведений

способе синтеза. Однако

на

базе

возможно

построение методов синтеза

элементами алгоритмизации.

таких

методах

вводится метризация морфологического пространства. Мор-

фологическое пространство составляют возможные законченные структуры,

принимается,

что

расстояние между структурами

С,

есть

число несовпа-

дающих элементов (каждая клетка таблицы

есть один элемент). Поэтому

можно

говорить

об

окрестностях решении. Далее исходят

из

предположения

компактности

«хороших» решений, которое позволяет вместо полного

перебо-

ра

ограничиваться перебором

малой окрестности текущей точки поиска.

Та-

ким

образом, гипотеза

компактности

метризация пространства решений

175

Математическое

обеспечение синтеза

проектных

решений

фактически

приводят

построению математической модели,

которой можно

применить методы дискретной оптимизации, например локальные

методы.

недостаткам таблицы

относятся неучет запрещенных сочетаний эле-

ментов

законченных структурах

отражение состава элементов

структу-

рах без

конкретизации

их

связей.

Кроме

того, морфологические таблицы стро-

ят

предположении,

что

множества

(

взаимно независимы,

т. е.

состав

способов реализации

г'-й

функции

не

меняется

при

изменении значений

других

функций.

Очевидно,

что

предположение

взаимной независимости множеств

оправдано лишь

сравнительно простых структурах. Последний недостаток

устраняется путем обобщения метода морфологических таблиц

— при

исполь-

зовании метода альтернативных

(И-ИЛИ)

графов.

Альтернативные

графы

Любую

морфологическую таблицу можно представить

виде

дерева

(рис.

4.12).

На

рисунке функции показаны ребрами, идущими вниз

из

вершины

(вершина

И),

значения функций

—

множество ребер, идущих вниз

из

вершин

ИЛИ

(светлые кружки). Очевидно,

что

таблица представляет собой множе-

ство однотипных объектов, поскольку

все они

характеризуются одним

и тем

же

множеством функций.

Для

разнотипных объектов применяют многоярусные альтернативные гра-

фы.

Например,

на

рис.

4.13

показан двухъярусный граф,

котором

для

разных

типов объектов предусмотрены разные подмножества функций.

Если

допустить некоторую избыточность

при

изображении

И-ИЛИ-графа,

то его

можно превратить

И-ИЛИ-дерево,

что

ведет

определенным удобст-

вам.

Очевидно,

что

И-ИЛИ-дерево можно представить

как

совокупность мор-

фологических

таблиц. Каждая

И-вершина

дерева

соответствует

частной мор-

фологической

таблице,

т. е.

множеству функций так,

что

/-я

выходящая

ветвь

отображает

г-ю

функцию.

Каждая

ИЛИ-вершина,

инцидентная

z'-й

ветви,

соот-

ветствует множеству вариантов реализации

г'-й

функции,

при

этом/-я

исходя-

щая

из

ИЛИ-вершины

ветвь

отображает

/-и

вариант реализации.

Приложение

ИЛИ

Рис. 4.12.

Дерево,

соответствующее

морфологической

таблице

Типы

систем

Функции

ИЛИ

Значения

функций

Рис. 4.13.

И-ИЛИ-граф

176

Постановка

задач

структурного

синтеза

Алгоритмизация синтеза

на

базе

И-ИЛИ-деревьев

требует

введения пра-

вил

выбора альтернатив

каждой вершине ИЛИ.

Эти

правила чаще всего име-

ют

эвристический характер, связаны

требованиями

ТЗ,

могут

отражать

за-

преты

на

сочетания определенных компонентов структур.

Трудности

эффективного решения задачи существенно возрастают

при на-

личии ограничений, типичными среди которых являются ограничения

на со-

вместимость способов реализации разных функций,

т. е.

ограничения вида

and

false,

(4.29)

где

true, если

оцениваемый вариант вошел элемент

;

иначе

—

false.

Условие

(4.29)

означает,

что в

допустимую

структуру

не

могут входить одно-

временно

элементы

и Э .

Совокупность ограничений типа

(4.29)

можно

представить

как

систему логических уравнений

неизвестными

Тогда

за-

дачу синтеза можно решать эволюционными методами, если предварительно

или

одновременно

с ней

решать систему логических уравнений (задачу

о вы-

полнимости).

Исчисления

Очевидно,

что в

большинстве случаев структурного синтеза вместо нере-

ализуемого явного представления всего множества проектных решений зада-

ют

множество элементов

совокупность правил объединения этих элементов

допустимые структуры (проектные решения).

Эти

множества элементов

правил часто представляют

виде формаль-

ной

системы (исчисления),

т. е.

задача синтеза имеет

вид

ЗС

- О;

НТ;

АК;

П >,

где

Э —

алфавит исчисления (алфавит представлен базовыми элементами,

из

которых синтезируется структура);

НТ —

множество букв,

не

совпадающих

буквами алфавита

Э и

служащих

для

обозначения переменных;

АК —

множе-

ство аксиом исчисления,

под

которыми понимаются задаваемые исходные

формулы

(слова)

алфавите

(например, соответствия функций

элементов);

П —

множество правил вывода новых формул

алфавите

Э из

аксиом

ранее

выведенных корректных формул. Каждую формулу можно интерпретировать

как

некоторую структуру, поэтому синтез

— это

процесс вывода формулы, удов-

летворяющей исходным требованиям

ограничениям.

Другие

примеры компактного задания множества альтернатив

через мно-

жества

Э и П

связаны

использованием систем искусственного интеллекта,

которых

есть

база данных,

П —

база знаний,

или

эволюционных методов,

которых

Э —

также база данных,

П —

множество эвристик, последователь-

ность

их

применения определяется эволюционными

генетическими

принци-

пами.

177

Математическое обеспечение синтеза проектных

решений

Планирование

процессов

распределение

ресурсов

отдельную

группу

задач структурного синтеза выделяют планирование

процессов

распределение ресурсов.

В нее

входят синтез технологических

процессов

различных отраслях промышленности, проектирование вычисли-

тельных процессов

для

многопроцессорных систем

сетей, синтез логисти-

ческих процессов (например, планирование перевозок грузов

при

наличии мно-

жества заказов

ограниченном числе транспортных

средств),

также

планирование работ

при

управлении проектами.

Эти

задачи объединяет общ-

ность ряда свойств

подходов

решению,

как

задач синтеза расписаний.

Базовым

понятием

синтезе расписаний является понятие работы

—

эле-

ментарной

планируемой части процесса. Нужно составить план выполнения

работ,

котором фиксируются объемы работ, распределение ресурсов

всех

видов, моменты

(даты)

начала

окончания каждой работы, называемые собы-

тиями (или

вехами),

стоимости работ. Ресурсы

—

обеспечивающие компонен-

ты

деятельности, включающие исполнителей, энергию, материалы, оборудова-

ние

и т. д.

каждой

работой

можно связать функцию

потребности

ресурсах.

Разли-

чают ресурсы унарные

объемные. Единица унарного ресурса, называемая

далее сервером, может одновременно выполнять

не

более одной

работы,

и по

каждому

виду ресурса

на

работу

может

быть

назначен

не

более

чем

один

сервер. Примерами унарных ресурсов

могут

быть токарный станок, процессор

ЭВМ, водитель автомашины. Значение объемного ресурса (энергии, финансов,

пропускной

способности канала), назначаемое

для

конкретной работы, может

быть выбрано

некотором диапазоне

и от

выбранного значения зависят дли-

тельность

(или) стоимость выполнения работы.

Результаты

синтеза обычно представляют

виде таблиц

диаграмм. PERT-

диаграмма

(сеть типа «вершина

событие»)

—

ориентированный граф

без

кон-

туров, имеющий одну исходную

одну завершающую вершины,

котором вер-

шины поставлены

соответствие

событиям,

дуги

—

работам. Диаграмма

Ганга

(Gantt

diagram)

—

горизонтальная линейная диаграмма,

на

которой зада-

чи

проекта представляются протяженными

во

времени отрезками, распреде-

ленными

между серверами

характеризующимися датами начала

оконча-

ния,

задержками

и,

возможно, другими временными параметрами.

Для

задач планирования процессов

управления проектами характерны сле-

дующие особенности:

широкий диапазон размеров задач, причем верхняя граница диапазона

может достигать значений

десятки тысяч

более работ;

многокритериальность,

основные критерии

—

время

стоимость выпол-

нения

плана,

качестве целевой функции часто выбирают

стоимость,

число

ограничений включают времена окончания работ

и,

возможно,

ряд

условий

ис-

пользования

ресурсов;

разнообразие типов управляемых переменных, среди которых

могут

быть

величины действительные, целые, нечисловые.

Указанные

особенности обусловливают сложность решения задач синтеза

расписаний, являющихся задачами дискретной оптимизации.

178

4 4

Методы структурного синтеза

системах автоматизированного проектирования

4.4. Методы

структурного

синтеза

системах

автоматизированного

проектирования

Метод

ветвей

границ

Выбор метода поиска решения

вторая проблема после формализации

за-

дачи. Если

при

формализации

все

управляемые параметры удалось предста-

вить

числовом виде,

то

можно попытаться применить известные методы

ДМП.

Задача

ДМП

определяется

следующим образом:

extr

F(\),

(4.30)

XeD

= { X |

W(X)

>0,

Z(X)

= 0 },

где

-F(X)

—

целевая функция; W(X),

Z (X) —

вектор-функции, связанные

пред-

ставленными

в ТЗ

требованиями

ограничениями;

D —

дискретное множе-

ство.

полученной

модели,

во-первых, каждый элемент множества рассмат-

риваемых законченных структур должен иметь уникальное сочетание значений

некоторого

множества числовых параметров, вектор которых обозначим

Во-вторых, необходимо существование одной

или

нескольких функций Ф(Х),

значения

которых могут служить исчерпывающей оценкой соответствия струк-

туры предъявляемым требованиям. В-третьих, функции

Ф(Х)

должны отра-

жать внутренне присущие данному классу объектов свойства,

что

обеспечит

возможность использования Ф(Х)

качестве

не

только средств оценки дос-

тигнутого

при

поиске успеха,

но и

средств указания перспективных направле-

ний

продолжения поиска.

Эти

условия выполнимы далеко

не

всегда,

что и

обус-

ловливает трудности формализации задач структурного синтеза.

Однако

наличие формулировки

(4.30)

еще не

означает,

что

удастся подо-

брать метод (алгоритм) решения задачи

(4.30)

приемлемыми затратами

вы-

числительных ресурсов. Другими словами, применение точных методов мате-

матического программирования вызывает непреодолимые трудности

боль-

шинстве случаев практических задач типичного размера из-за

их

принадлеж-

ности

классу

NP-трудных

задач. Поэтому лидирующее положение среди

методов решения задачи

(4.30)

занимают приближенные методы,

частности

декомпозиционные

методы, отражающие принципы

блочно-иерархического

проектирования

сложных объектов. Декомпозиционные методы основаны

на

выделении ряда иерархических уровней,

на

каждом

из

которых решаются

за-

дачи приемлемого размера.

Основу большой группы математических методов, выражающих стремле-

ние

сокращению перебора, составляют операции разделения множества

ва-

риантов

на

подмножества

отсечения неперспективных подмножеств.

Эти

методы объединяются

под

названием

метода

ветвей

границ.

Основная

разновидность метода ветвей

границ относится

точным методам решения

комбинаторных задач. Рассмотрим

эту

разновидность.

179

Математическое

обеспечение

синтеза проектных

решений

Пусть имеется множество решений

М, в

котором нужно выбрать оптималь-

ный

по

критерию

F(X

)

вариант,

где X —

вектор параметров варианта

М;

пусть также имеется алгоритм

для

вычисления нижней границы

ДМ

)

крите-

рия

F(X'.)

любом подмножестве

М^

множества

М, т. е.

такого значения

i(M

что

F(X)

L(M

)

при

любому

(подразумевается минимизация

F(X)).

Тогда

основная

схема решения задач

соответствии

методом ветвей

границ

со-

держит следующие процедуры:

1) в

качестве

М^

принимаем

все

множество

М;

ветвление: разбиение

на

несколько подмножеств

М ; 3)

вычисление

нижних границ

ЦМГ)

подмножествах

;

выбор

качестве

подмно-

жества

М с

минимальным значением нижней границы критерия (среди всех

подмножеств, имеющихся

на

данном этапе вычислений), сведения

об

осталь-

ных

подмножествах

и их

нижних границах сохраняются

отдельном спис-

ке;

если

> 1, то

переход

процедуре

иначе одноэлементное множе-

ство

М^есть

решение.

Метод

ветвей

границ

случае точного вычисления нижних границ отно-

сится

точным методам решения задач выбора

потому

неблагоприятных

ситуациях может приводить

экспоненциальной временной сложности. Одна-

ко

метод часто используют

как

приближенный, поскольку можно применять

приближенные алгоритмы

вычисления

нижних границ.

Среди

других

приближенных методов решения задачи

ДМП

отметим

ме-

тод

локальной

оптимизации.

Так как

пространство

метризовано,

то

мож-

но

использовать понятие

я-окрестности

(Х

)

текущей точки поиска

Вме-

сто

перебора точек

во

всем пространстве

осуществляется перебор точек

только

Если

F(X)

F(X.

)

для

всех

X е

(Х

то

считается,

что

найден

локальный минимум целевой функции

точке

противном случае

точку

которой достигается минимум

F(X)

принимают

качестве

новой

текущей точки поиска.

Элементы

теории сложности

теории сложности выделяют массовые

индивидуальные задачи.

Пер-

вые

из них

сформулированы

общем виде, вторые представлены

конкретны-

ми

числовыми значениями исходных данных. Исследования сложности прово-

дятся

отношении массовых задач,

получаемые выводы,

как

правило,

относятся

наихудшему случаю

— к

наиболее неблагоприятному возможному

сочетанию исходных данных.

Цель

исследований

—

установление вида зависимости объема

требуе-

мых

вычислений

от

размера задачи

Объем вычислений может определять-

ся

числом арифметических

логических операций

или

затратами процессор-

ного времени

ЭВМ с

заданной производительностью. Размер задачи

общем

случае связывают

объемом описания задачи,

но в

приложениях понятие раз-

мера легко наполняется более конкретным содержанием.

Далее,

теории сложности задач выбора вводят понятия эффективных

неэффективных

алгоритмов.

эффективным

относят алгоритмы

полино-

180

4.4.

Методы структурного синтеза

системах автоматизированного проектирования

Таблица

4.1

Q(N)

Б,

=100Б,

100

4,647/э

6,64

Я,

53=10006,

ЮООЛГ,

31,6

9,97

миальной

зависимостью

onN,

например, алгоритмы

функцией

(N)

линей-

ной,

квадратичной, кубической

и др. Для

неэффективных

алгоритмов харак-

терна экспоненциальная зависимость

(N).

Важность проведения резкой границы между полиномиальными

экспонен-

циальными

алгоритмами вытекает

из

сопоставления числовых примеров рос-

та

допустимого размера задачи

увеличением быстродействия

используе-

мых

ЭВМ

(табл.

4.1,

которой указаны размеры задач, решаемых

за

одно

и то

же

время

на ЭВМ с

быстродействием

;

при

различных зависимостях слож-

ности

Q от

размера

N).

Эти

примеры показывают,

что

выбирая

ЭВМ в

раз

более

быстродействующую,

получаем увеличение размера решаемых задач

при

линейных алгоритмах

раз,

при

квадратичных алгоритмах

раз и т. д.

Иначе

обстоит

дело

неэффективными алгоритмами. Так,

случае слож-

ности

для

одного

того

же

процессорного времени размер задачи увеличи-

вается только

на

\gK

Ig2

единиц. Следовательно, переходя

от ЭВМ с Б

Гфлопс

суперЭВМ

с Б = 1

Тфлопс, можно увеличить размер решаемой зада-

чи

только

на

10,

что

совершенно недостаточно

для

практических задач. Дей-

ствительно,

таких задачах, как, например, синтез

тестов

для

БИС, число вход-

ных

двоичных переменных может составлять более

100 и

поэтому полный

перебор всех возможных проверяющих

кодов

потребует

выполнения более

100

вариантов

моделирования схемы.

теории сложности

все

комбинаторные задачи разделены

на

классы:

•

класс неразрешимых задач,

него входят массовые задачи, решение

ко-

торых полным перебором принципиально невозможно

точки зрения совре-

менных

научных представлений; этот класс отделяется

от

других

задач

так

называемым пределом Бреммермана, оцениваемым величиной

;

отме-

тим,

что

реальный предел неразрешимости значительно ниже;

•

класс

Р, к

нему относятся задачи,

для

которых известны алгоритмы реше-

ния

полиномиальной сложности;

•

класс

NP,

включающий задачи,

для

которых можно

за

полиномиальное

время

проверить правильность решения,

т. е.

ответить

на

вопрос, удовлетворя-

ет

ли

данное решение заданным условиям; очевидно,

что Р

включено

в NP, од-

181

Математическое обеспечение синтеза проектных

решений

нако

вопрос

совпадении этих классов пока остается открытым, хотя, по-види-

мому,

на

этот вопрос будет получен отрицательный ответ;

•

класс

NP-полных

задач, характеризующийся следующими свойствами:

для

этих задач

не

известны полиномиальные алгоритмы точного решения;

любые задачи внутри этого класса могут быть сведены одна

другой

за

полиномиальное

время. Последнее означает,

что

если будет найден полиноми-

альный

алгоритм

для

точного решения хотя

бы

одной

NP-полной

задачи,

то за

полиномиальное время можно будет решить

любую

задачу этого класса.

Из

результатов теории сложности

следуют

важные практические рекомен-

дации:

приступая

решению некоторой комбинаторной задачи, необходимо

сначала

проверить,

не

принадлежит

ли она к

классу NP-полных задач,

если

это

так,

то не

следует тратить усилия

на

разработку алгоритмов

программ

точного решения;

отсутствие эффективных алгоритмов точного решения мас-

совой

задачи выбора отнюдь

не

означает невозможности эффективного реше-

ния

индивидуальных задач

из

класса NP-полных

или

невозможности получе-

ния

приближенного решения

по

эвристическим алгоритмам

за

полиномиальное

время.

Методы

локальной

оптимизации

поиска

запретами

Среди

приближенных методов решения задачи

(4.30)

часто используемым

является

метод локальной оптимизации.

Так как

пространство

метризовано,

то

можно использовать понятие

а-окрестности

)

текущей точки поиска

Вместо перебора точек

во

всем пространстве

осуществляется перебор

только

Если

F(X )

(Х^)

для

всех

Х^

€

то

считается,

что

най-

ден

локальный минимум целевой функции

точке

противном случае точ-

ку

X , в

которой достигается минимум

F(X)

принимают

качестве

новой

текущей точки поиска.

Недостатком метода является

его

явно

выраженная локальность

—

«за-

стревание»

окрестностях локальных экстремумов. Повысить эффективность

поиска

можно

помощью метода оптимизации

запретами (tabu search).

Для

этого

(Х

)

вводят запреты

на

попадание

некоторые точки. Обычно

это

запреты

на

повторное исследование точек, пройденных

на

нескольких послед-

них

шагах оптимизации. Запрет распространяется

и на

лучшую

точку

Х^

пре-

дыдущего шага, которая может оказаться точкой локального минимума. Тогда

на

данном шаге перемещение происходит

лучшую незапрещенную точку

t+1

несмотря

на то что

;t+]

)

/*XX

Тем

самым появляется тенденция

выхо-

ду из

области притяжения локального экстремума.

Системы

искусственного

интеллекта

теории интеллектуальных систем синтез реализуется

помощью экс-

пертных систем

ЭС

<БД,БЗ,И>,

где

БД —

база данных, включающая сведения

базовых элементах;

БЗ —

база

знаний, содержащая правила конструирования вариантов структуры;

И —

ин-

182