Искусственный интеллект в САПР
Искусственный интеллект в САПР
Возможность и эффективность применения ЭВМ для решения тех или иных задач проектирования непосредственно связаны со степенью математической формализации этих задач. Наибольший успех достигнут для тех объектов и задач проектирования, для которых найдены адекватные ММ, развиты эффективные вычислительные процедуры, доказана их разрешимость, определены ограничения. В САПР это, в первую очередь, относится к задачам анализа и параметрической оптимизации.
В то же время многие задачи проектирования (например, подавляющее большинство задач структурного синтеза) плохо поддаются автоматизации, решаются вручную, эвристически на основе опыта и интуиции разработчика. При этом качество получаемых решений определяющим образом зависит от творческих способностей человека. Такие задачи принято называть плохоформализуемыми, к ним относятся: 1) задачи, не имеющие точно выраженной математической постановки (в терминах АП - задачи, не имеющие конструктивной ММ) и/или 2) задачи, решение которых алгоритмическими методами невозможно или неэффективно. Наряду с поиском и разработкой формальных подходов к решению таких задач перспективным является использование методов и средств искусственного интеллекта.
Искусственный интеллект (ИИ) - это (применительно к проблематике АП) научная дисциплина, развивающая теорию и средства решения на ЭВМ плохоформализуемых задач на основе оперирования неформальными знаниями человек.
Кроме перечисленных выше плохоформализуемые задачи обычно обладают следующими особенностями:
- неоднозначность, неполнота и противоречивость исходных данных,
- неоднозначность, неполнота и противоречивость знаний о решаемой задаче,
- большое количество возможных решений.
Плохоформализуемые задачи - это чаще всего задачи в нечисловой форме.
Работы в области ИИ ведутся по нескольким тесно связанным друг с другом направлениям: автоматическое доказательство теорем, распознание образов и сцен, обработка естественного языка, автоматическое программирование, планирование целесообразного поведения роботов, консультирующие экспертные системы и др. Теоретические и практические результаты достигнутые в каждом из этих разделов ИИ, находят или могут найти приложение в САПР.
В зависимости
от масштабности той роли, которую призваны
играть методы и средства ИИ в решении
задач проектирования, условно можно выделить
3 уровня интеллектуализации САПР. На первом
уровне средства ИИ используются лишь
в качестве компонент отдельных подсистем
САПР, где они используются для решения
подзадач, решений которых формальными
методами неэффективно или невозможно.
Второй уровень предусматривает наличие
в САПР, построенных на традиционных принципах,
подсистем (проектирующих или обслуживающих),
полностью организованных в соответствии
с методологией ИИ. Третий уровень интеллектуальности
достигается при построении САПР целиком
на организационных принципах систем
ИИ с использованием как формальных так
и эвристических процедур проектирования.
Пример. Иллюстрацией первого уровня интеллектуальности могут служить подсистемы трассировки печатных плат, в которых 90...95% межсоединений трассируются формальными методами, а для размещения в автоматическом режиме остальных используются эвристические приемы. Ко второму уровню может быть отнесена САПР жидкостных расходомеров, в которой для выбора физических принципов действия расходомеров используется подсистема структурного синтеза, воплощающая в себе методы ИИ. К средствам построения САПР третьего уровня интеллектуальности относится мониторная подсистема INTERLOG, служащая средством интеграции независимых программных комплексов в единую САПР и основанная на идеологии ИИ.
Основным объектом изучения и манипулирования в ИИ являются знания - не определяемое формально понятие, в которое обычно включается совокупность сведений, используемых человеком при решении конкретных задач. Особенностями, отличающими знания от данных являются:
- интерпретируемость (понимаемая как наличие у элемента знаний смысла, не связываемого с какой-либо конкретной процедурой его обработки);
- структурированность (участие знаний в классифицирующих отношениях типа "элемент - класс", "часть - целое" и т.п.;
- связность (включение в причинно-следственные, пространственные, временные и др. отношения);
- активность (свойство знаний служить побудителем к действию).
Пример. В системе знаний инженера последовательность символов ТИТАН имеет однозначный смысл "конструкционный материал" (свойство интерпретируемости). Это понятие, с одной стороны, включает в себя титаны различных марок, а, с другой, само является элементом более широкого понятия "материалы, используемые в технике" (свойство структурированности). С каждым конструкционным материалом связываются такие его свойства, как плотность, модуль упругости, коэффициент Пуассона и др., при этом значение модуля упругости, например, непосредственно влияет на напряжения и деформации, возникающие в конструкциях (свойство связности). Отсутствие численного значения какого-либо атрибута для конструкционного материала служит стимулом к его поиску в справочнике или проведению физического эксперимента (свойство активности).
Та же последовательность символов, выступая в качестве данного, обретает свой смысл только в контексте использующей ее процедуры и может иметь смысл "город в Мурманской области" или "название хоккейной команды".
Следует отметить, что четкой границы между данными развитой структуры и знаниями нет.
Знания об
объектах и явлениях принято делить на
синтаксические, семантические и прагматические.
Первые описывают структуру объектов
и явлений, вторые - информацию, связанную
с их значением и их смыслом, а третьи описывают
объекты и явления с точки зрения решаемой
задачи.
Пример. Синтаксические знания об электронном усилителе включают в себя сведения о возможных структурных схемах таких усилителей, состоящих из каскадов различных типов, объединенных разнообразными связями. Семантические знания - это знания о назначениях отдельных каскадов (согласование по входу - выходу, предварительное усиление, поворот фазы сигнала и т.п.) и принципах их функционирования. В прагматические знания разработчика усилителей входят знания, позволяющие по ТЗ выбрать структурную схему усилителя и принципиальные электрические схемы отдельных каскадов, рассчитать значения внутренних параметров и т.п. Прагматические знания наладчика усилителя состоят из знаний о способах поиска и устранения неисправностей.
Центральное место в системах ИИ любого назначения занимает база знаний (БЗ) - вместилище всей совокупности знаний, относящихся к решаемой задаче. Важной проблемой при создании БЗ является выбор наиболее адекватного с точки зрения указанных выше особенностей способа представления знаний. Различают декларативную и процедурную формы представлений знаний. Форма представления знаний совокупностью программ называется процедурой. Представление знаний в виде набора утверждений об объектах предметной области и отношениях между ними называется декларативным. При использовании этой формы представления в системах ИИ подразумевается, что их интеллектуальность достигается за счет наличия небольшого числа универсальных процедур работы со знаниями, а их специализация на конкретную предметную область обеспечивается наполнением утверждениями, характеризующими эту область. Этим достигается независимость друг от друга предметных знании и знаний о методах решения задач, что гарантирует их гибкость и легкую модифицируемость. Однако, для некоторых понятий использование декларативного представления невозможно или неэкономично. В связи о этим на практике чаще всего используют смешанные представления, сочетающие в себе оба подхода.
Важными с т.з. представления являются понятия экстенсионал и интенсионал знаний. Под экстенсионалом некоторого понятия подразумевается множество конкретных фактов, соответствующих данному понятию. Интенсионал определяется как правило, либо порождающее множество фактов, составляющих экстенсионал, либо проверяющее принадлежность некоторого факта к экстенсионалу.
Пример. Экстенсионалом понятия "числа Фибоначчи" является бесконечное множество целых чисел 1,1,2,3,5,8,... , интенсионалом - следующее правило порождения:
С1=1, С2=1, Сk=Сk-1+Сk-2 для k = 3,4.... .
Интенсиональные знания могут быть представлены как в процедурой, так и в декларативной формах, в то время как экстенсиональные знания всегда задаются декларативно.
В соответствии с указанными двумя способами представления знаний в БЗ выделяют две части - интенсиональную и экстенсиональную, реализуемую как база данных. Для представления знаний в БЗ используются формализмы, носящие название моделей представления знаний, и соответствующий инструмент - языки представления знаний.
Примечание. Модели
и языки представления знаний можно рассматривать
как результат эволюционного развития
и усложнения моделей данных и языков
их описания и манипулирования.
Используемые в настоящее время модели представления знаний условно классифицируют на 3 типа: логические, сетевые модели и продукционные системы (см. рис. 1). К первым относят обычно исчисление предикатов первого порядка и формальные продукционные системы, ко вторым - семантические сети и фреймовые модели. Однако, как правило, возможности указанных моделей каждой в отдельности оказываются недостаточными для представления всей необходимой совокупности знаний, поэтому в реальных системах ИИ используются комбинированные представления - чаще всего логические и сетевые модели встраиваются в продукционные системы.
Рис. 1. Классификация моделей представления знаний
Прежде
чем перейти к обсуждению
Пример. Пусть необходимо представить знания о чрезвычайно упрощенной предметной области "проектирование башен". Башня представляет собой сооружение из крыши и поддерживающего ее ствола. Крыша может быть призматической высотой 4 м или плоской высотой 1 м. Ствол башни может состоять из 1, 2 или 3 блоков одинаковой формы. Цилиндрические блоки имеют высоту 5 м и 3 м, а блоки в виде параллелепипеда - 4 м и 2 м. Все башни в нашей предметной области должны иметь громоотвод и сигнальный маяк на крыше.
Основной
задачей, решаемой в этой
В основе
моделей представления знаний
этого типа лежит сеть (ориентированный
граф), вершины которого
Рис. 2. Пример эктенсиональной семантической сети
Пример. На рис. 2. представлен фрагмент СС, описывающей башню из нашего примера, состоящую из крыши призматической формы и ствола из двух цилиндрических блоков высотой по 3 и 5. Дуги, помеченные символами ISA, соответствуют отношению "быть элементом множества" (is a - быть одним из), а дуги, помеченные AKO - отношению "быть подмножеством" (a kind of).
В зависимости
от характера (типа) отношений,
приписываемых дугам,
Функциональная
сеть представляет собой
Сценарии
представляют собой однородные
сети, дуги которых моделируют
отношения нестрогого порядка
(временные, причинно-
В собственно
СС не фиксируются строго ни
типы вершин, ни дуг, т.е., как
это видно из примера, вершины
СС могут иметь различные
СС, представленная в примере, относится к простым. В иерархических СС вершины могут иметь собственную сложную структуру, представляемую, в свою очередь, семантической сетью, называемой в данном случае подсетью (пространством). В иерархических СС между пространствами устанавливается отношение видимости - как правило, из пространств более высокого иерархического уровня информация, содержащаяся в пространствах, лежащих ниже, недоступна (невидима). Введение иерархии на СС позволяет декомпозировать решаемые задачи на подзадачи и тем самым бороться с их сложностью.
Пример. СС, содержащая знания об электронном усилителе, может иметь два уровня иерархии. На верхнем в качестве базовых вершин будут выступать вершины, соответствующие отдельным каскадам усилителя, на нижнем каждый каскад может быть раскрыт сетью, описывающей, в частности, принципиальную электрическую схему этого каскада.
Рассмотренная в примере с башней СС носит название экстенсиональной (ЭСС), поскольку описывает факты о башне конкретной конструкции. Знания же об абстрактной башне (т.е. о всех возможных конструкциях башен в нашем примере) представляются в интенсионалной СС (ИСС), как это показано на рис 3, через общие понятия и отношения между ними. СС рассмотренных двух типов составляют соответственно экстенсиональную и интенсиональную части БЗ.
Рис. 3. Пример интенсиональной семантической сети
Отношения
предметной области, явно
- в виде процедур, вычисляющих значение функций или предикатов (ИССС рис. 3 содержит явные ссылки на одну из таких процедур - процедуру вычисления высот, высота ствола и башни в ЭСС рис. 2 рассчитаны с привлечением именно этой процедуры);
- путем использования свойств симметричности, рефлексивности, транзитивности базовых отношений (например, транзитивность отношения "находится - на" позволяет из фактов "крыша находится на стволе", "ствол состоит из блока-1 и блока-2", "блок-1 находится на блоке-2" вывести новый факт "крыша находится на блоке-2");
- в виде правил продукционных систем, как это будет рассмотрено ниже.
Основными
режимами в функционировании
БЗ на основе СС являются
её пополнение и информационно-
В организации
информационно-поискового
Наличие
в СС явных ассоциативных
Фреймовые модели представления знаний
Их можно
рассматривать как специальную
разновидность СС, используемую
для представления хорошо
В простом случае фрейм может быть представлен в виде следующей конструкции:
имя_фрейма:ISA-_или_АКО-ссылка
(описание_слота#1;
. . .
описание_слота#N) .
Здесь слот
является основной единицей
Слот в
свою очередь состоит из ряда
ячеек и имеет следующую
имя_слота(ЗНАЧЕНИЕ:значение_
ТИП:тип_значения_слота;
УМОЛЧАНИЕ:значение_по_
ДЕМОНЫ:имена_процедур-демонов;
СЛУГИ:имена_процедур-слуг)
Обязательными
в структуре слота являются
только ячейки ЗНАЧЕНИЕ и ТИП,
обеспечивающие
Присоединенные
процедуры в зависимости от
способа вызова делятся на
две группы. Процедуры-демоны включаются
в работу автоматически (без
явного на то указания) при
выполнении некоторого условия.
Вызов
процедур-слуг осуществляется
Интенсиональную часть фреймовых БЗ составляют фреймы-прототипы с присоединенными к ним процедурами, при этом, как правило, фреймы объединяются в сеть с помощью слотов типа ссылка согласно отношениям, существующим между реализуемыми фреймами понятиями, и ISA- и АКО-связей. Фрейм - прототип представляет собой готовую структуру, которая при том или ином заполнении слотов значениями превращается в описание конкретного факта.
Пример. Фрагмент интенсиональной части БЗ на основе фреймов для рассматриваемого нами примера с башней может иметь следующий вид:
башни: сооружения
(крыша
(ЗНАЧЕНИЕ: крыши;
ТИП: ссылка);
ствол
(ЗНАЧЕНИЕ: стволы;
ТИП: ссылка;
СЛУГИ: расч_кол_бл);
высота
(ЗНАЧЕНИЕ: <>;
ТИП: положит. действ. число;
ДЕМОНЫ: расч_высоты);
имеет
(ЗНАЧЕНИЕ: громоотвод, маяк;
ТИП: текст);
цвет
(ЗНАЧЕНИЕ: <>;
ТИП: множество {красный, . . . , фиолетовый};
УМОЛЧАНИЕ: желтый) )
Здесь
в виде фрейма представлено
понятие "абстрактная башня"
(иначе, все башни в нашей
предметной области). Понятие "башня"
выступает в качестве
Экстенсиональную часть БЗ составляет сеть фреймов-примеров (конкретных фреймов), создаваемая путем полной или частичной конкретизации фреймов-прототипов значениями слотов (необязательной является конкретизация слотов, имеющих значения "по умолчанию").
Пример. Сгенерированный на основе фрейма-прототипа башни конкретный фрейм башня_1 может быть представлен в экстенсиональной части БЗ следующим образом:
башня_1: башни
(крыша
(ЗНАЧЕНИЕ: крыша_1;
ТИП: ссылка);
ствол
(ЗНАЧЕНИЕ: ствол_1;
ТИП: ссылка) ;
высота
(ЗНАЧЕНИЕ: 12;
ТИП: положит. действ. число;
ДЕМОНЫ: расч_высоты);
цвет
(ЗНАЧЕНИЕ: <>;
ТИП: множество {красный, ..., фиолетовый};
УМОЛЧАНИЕ: желтый) )
В этом фрейме установлена ISA-ссылка на фрейм-прототип башни и отсутствует слот имеет. Второе обстоятельство обусловлено тем, что содержимое этого слота одинаково для всех фреймов-примеров башен в нашей предметной области и поэтому он в фрейм-пример не копируется. При запросе к слоту имеет фрейма башня_1 будет автоматически включен встроенный механизм наследования понятий, который осуществит навигацию вверх по ISA- и АКО-связям и доставит необходимое значение слота.
Для реализации
присоединенных процедур и
- пользователь сам пишет соответствующие процедуры на каком-либо языке программирования, используя базовый набор подпрограмм доступа к ячейкам фреймов;
- выделяется ограниченный набор допустимых фреймов, для которых однократно создаются специфические процедуры (такой подход возможен только для БЗ узкой ориентации);
- включение в интенсиональную часть БЗ наряду с предметными "вычислительных" фреймов, реализующих, например, алгебраические операции (фрейм-сложение, фрейм-вычитание и т.п.) или вычисление значений предикатов (фрейм-И, фрейм-ИЛИ, кванторные фреймы и др.).
В последнем случае, например, присоединенная процедура может быть представлена как сценарий из вычислительных фреймов.
Основной операцией на фреймах является операция поиска по образцу. Образец представляет собой отдельный фрейм, в котором конкретизированы не все, а лишь некоторые значения слотов. В задачу поиска входит обнаружение в БЗ фрейма (или фреймов) с совладающими значениями слотов и возврат значений для неконкретизированных слотов фрейма-образца. В более сложных вариантах может ставиться задача поиска подсети фреймов или поиска при наложенных ограничениях на значения слотов.
Популярность фреймовых моделей представления знаний в системах ИИ обусловлена их гибкостью и универсальностью, заключающихся в том, что всегда есть возможность сконструировать систему фреймов, наиболее полно и адекватно отвечающую специфике предметной области и решаемых задач. Фреймовое представление позволяет в широких пределах варьировать соотношением декларативности и процедурности в представлении знаний.
Примечание. Необходимо отметить, что сам термин "фрейм" (frame - рамка) и соответствующая формализация были введены специалистами в области ИИ, однако подразумеваемая под этим термином концепция широко использовалась задолго до этого в программировании, где она получила название абстрактного типа данных.
Продукционные системы (ПС)
Под ПС будем понимать систему <W, P, I>, состоящую из трех компонент, где W - рабочая память, содержащая информацию, характеризующую текущее состояние предметной области, P -множество продукций вида ЕСЛИ условие, ТО следствие, применимых к W; I - интерпретатор (решатель), управляющий применением продукций. Общая постановка задач при использовании ПС - даны начальное W0 и конечное Wk состояния рабочей памяти, необходимо найти путь (пути) из W0 в Wk, реализуемый последовательностью применения продукций из P.
Рабочая память W в простейшем варианте представляет собой информационную структуру, описывающую факты предметной области и организованную наиболее удобным для этого способом (здесь можно использовать любые структуры данных, известные в программировании). W в таком виде представляет собой экстенсиональную часть БЗ, используемой в ПС. В сложных предметных областях W реализуется на основе рассмотренных выше моделей знаний, при этом чаще всего используются фреймовое представление и СС.
Множество
продукций P составляет основу интенсиональной
части БЗ. Основное достоинство ПС как
раз состоит в том, что с помощью продукций
наиболее адекватно отражаются механизмы
принятия решений человеком, основанные,
как показывают результаты психологических
исследований, на правилах типа "причина-следствие",
"посылка-заключение", "условие-действие".
Левая часть продукции (ЕСЛИ ...) представляет
собой заданное в декларативной форме
условие ее применимости, выраженное в
виде объединенных связками И, ИЛИ, НЕ
требований к элементам W. Оценка условий
применимости продукций осуществляется
интерпретатором. Правая часть продукции
(ТО...) может иметь декларативную или процедурную
форму и задает изменения, которые необходимо
выполнить в случае истинности условия
в левой части. Если правая часть продукции
задана в декларативной форме, то предписываемые
ею изменения в W (удаление, модификация,
добавление элементов) реализуются интерпретатором.
В альтернативной форме правой части подразумевается
наличие ассоциированной с продукцией
процедуры, непосредственно выполняющей
в W все необходимые изменения. В ПС, W которых
организуется с использованием представлений
на основе фреймов или СС, целесообразным
является представление и самих продукций
в рамках этих формализмов (в виде специальных
фреймов-продукций и фрагментов СС) - этим
достигается единообразие в организации
компонентов ПС.

- Искусственный интеллект, достижение и проблемы
- Искусственный интеллект, его понятие, сущность, теории
- Искусственный интеллект и эволюционное моделирование.
- Искусственный интеллект как феномен современной культуры
- Искусственный интеллект: надежды и возможности реализации
- Искусственный интеллект: новая информационная революция
- Искусственный интеллект. Философский анализ
- Искусственный интеллект
- Искусственный интеллект
- Искусственный интеллект
- Искусственный интеллект
- Искусственный интеллект
- Искусственный интеллект (7)
- Искусственный интеллект. Вопрос о возможности его создания