«РАЗРАБОТКА И ИССЛЕДОВАНИЕ НЕЧЕТКИХ СИСТЕМ И ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ КОНСТРУКЦИЙ РЭС ...»

Министерство высшего образования РФ

Ульяновский государственный технический университет

На правах рукописи

Наместников Алексей Михайлович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ НЕЧЕТКИХ СИСТЕМ И

ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ

АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ

КОНСТРУКЦИЙ РЭС

Специальность 05.13.12 - “Системы автоматизированного проектирования и автоматизация технологической подготовки производства (по отраслям)” Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель кандидат технических наук, профессор М. Я. Мактас

Научный консультант доктор технических наук, профессор Н. Г. Ярушкина Ульяновск -

СПИСОК СОКРАЩЕНИЙ

АП - автоматизированное проектирование БД - база данных БДЗ - база декларативных знаний БЗ - база знаний ГА - генетический алгоритм ИИ - искусственный интеллект ИМС - интегральная микросхема ИС - инструментальное средство ИСАПР - интеллектуальная система автоматизированного проектирования ИСППР - интеллектуальная система поддержки принятия решений ЛП - лингвистическая переменная ЛПР - лицо, принимающее решение МАИ - метод анализа иерархий МЗ - модуль знаний МВ - мягкие вычисления НК - нечеткий контроллер НЛ - нечеткая логика НС - нечеткая система ОП - объект проектирования ПЛВ - подсистема логического вывода ПМА - подсистема многокритериального анализа ПП - печатная плата ПР - принятие решений РЭС - радиоэлектронная система САПР - система автоматизированного проектирования СППР - система поддержки принятия решений СТО - стендовое технологическое оборудование СТП - стандарт предприятия СУБД - система управления базами данных ТЗ - техническое задание ТО - технический объект УБНК - унифицированные базовые несущие конструкции ЭВМ - электронно-вычислительная машина ЭРЭ - электрорадиоэлемент ЭС - экспертная система

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ ВОЗМОЖНОСТЕЙ И ОГРАНИЧЕНИЙ САПР

РЭС. МЕСТО НЕЧЕТКИХ СИСТЕМ И ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ В ИНТЕЛЛЕКТУАЛЬНЫХ САПР РЭС

1.1. АНАЛИЗ ЗАДАЧ, РЕШАЕМЫХ ТРАДИЦИОННЫМИ САПР ПРИ ПРОЕКТИРОВАНИИ

КОНСТРУКЦИЙ РЭС. ПОНЯТИЕ ИНТЕЛЛЕКТУАЛЬНОЙ САПР

1.2. ПРОБЛЕМНЫЕ ОБЛАСТИ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ. ТИП ПРОБЛЕМНОЙ

ОБЛАСТИ ПРОЕКТИРОВАНИЯ РЭС

1.3. АНАЛИЗ ОСНОВНЫХ НАПРАВЛЕНИЙ ПОСТРОЕНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ

САПР

1.4. АНАЛИЗ ФЕНОМЕНА НЕПОЛНОТЫ ПРОЕКТНОЙ ИНФОРМАЦИИ ПРИ ПОСТРОЕНИИ

ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ

1.4.1. Анализ различных аспектов неполноты. Способы формализации нечеткости

1.4.2. Схемы логического вывода. Понятие нечеткой системы

1.5. ПОДДЕРЖКА ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ В САПР. ПРИМЕНЕНИЕ

НЕЧЕТКИХ СИСТЕМ ДЛЯ ФОРМАЛИЗАЦИИ ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ.............. 1.5.1. Системы поддержки принятия решений в САПР

1.5.2. Многокритериальный выбор на основе метода анализа иерархий....... 1.5.3. Способы формализации качественной экспертной информации при принятии решений

1.6. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ КАК МЕТОД РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ.

МЕТОДОЛОГИЯ МЯГКИХ ВЫЧИСЛЕНИЙ

1.6.1. Схема стандартного генетического алгоритма

1.6.2. Методология мягких вычислений. Гибридные системы с использованием генетического алгоритма

1.7.

ОСНОВНЫЕ ВЫВОДЫ

ГЛАВА 2. АВТОМАТИЗАЦИЯ ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ

ПРИ ПРОЕКТИРОВАНИИ КОНСТРУКЦИЙ РЭС В УСЛОВИЯХ

НЕЧЕТКОСТИ ЭКСПЕРТНОЙ ИНФОРМАЦИИ

2.1. ФОРМАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ В САПР..............

2.2. ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЙ В САПР РЭС С ИСПОЛЬЗОВАНИЕМ

ЭКСПЕРТНЫХ СИСТЕМ И ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

2.3. ПОДХОД К НЕПОЛНОТЕ ПРОЕКТНОЙ ИНФОРМАЦИИ С ТОЧКИ ЗРЕНИЯ ПРИНЦИПА

“КОНСТРУКТИВНОЙ НЕОПРЕДЕЛЕННОСТИ”

2.4. ПРИНЯТИЕ ПРОЕКТНЫХ РЕШЕНИЙ С ИСПОЛЬЗОВАНИЕМ НЕЧЕТКОЙ ЭКСПЕРТНОЙ

СИСТЕМЫ

2.4.1. Задачи ЭС при генерации решений

2.4.2. Особенности структуры БЗ ЭС ИСАПР РЭС

2.4.3. Способ представления экспертной информации в БЗ ЭС.

Моделирование процессов принятия решений

2.5. МОДИФИКАЦИЯ МЕТОДА АНАЛИЗА ИЕРАРХИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ

МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА В ОБЛАСТИ ПРОЕКТИРОВАНИЯ РЭС

2.5.1. Структура системы предпочтений проектировщика

2.5.2. Субъективная оценка альтернатив с использованием лингвистических моделей

2.5.3. Способ агрегации локальных оценок в модифицированном МАИ..........

ГЛАВА 3. АДАПТАЦИЯ СТАНДАРТНОГО ГЕНЕТИЧЕСКОГО

АЛГОРИТМА К ЗАДАЧАМ ОПТИМИЗАЦИИ

3.1. СТАНДАРТНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ КАК АДАПТИРУЕМАЯ ПРОЦЕДУРА

ОПТИМИЗАЦИИ

3.1.1. Синтез адаптированного генетического алгоритма

3.1.2. Актуальность процедуры адаптации ГА при решении многокритериальных задач оптимизации

3.1.3. Схема адаптации ГА

3.2. ЭВОЛЮЦИЯ ПОПУЛЯЦИИ ХРОМОСОМ В СОСТАВЕ АДАПТИРОВАННОГО ГА......... 3.2.1. Формальное описание процесса эволюции

3.2.2. Разделение процесса эволюции популяции хромосом на две фазы....... 3.2.3. Феномен неполноты информации при построении адаптированного ГА

3.3. АДАПТИРОВАНИЕ ГА К ЗАДАЧАМ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ

НЕЧЕТКОГО КОНТРОЛЛЕРА

3.3.1. Схема управления с использованием нечеткого контроллера............. 3.3.2. Нечеткий контроллер процесса эволюции в адаптированном ГА.......

3.4. ХАРАКТЕРНЫЕ ОСОБЕННОСТИ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА ПО

СОЗДАНИЮ АДАПТИРОВАННОГО ГА

ГЛАВА 4. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ СТЕНДОВОГО

ТЕХНОЛОГИЧЕСКОГО ОБОРУДОВАНИЯ В УСЛОВИЯХ

НЕЧЕТКОЙ ЭКСПЕРТНОЙ ИНФОРМАЦИИ

4.1. ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ ПРИ

ПРОЕКТИРОВАНИИ СТЕНДОВОГО ТЕХНОЛОГИЧЕСКОГО ОБОРУДОВАНИЯ.................. 4.1.1. Формальное представление задачи выбора оптимальных типоразмеров корпусов

4.1.2. Структура и функции ИСППР

4.1.3. База знаний подсистемы логического вывода составе ИСППР.......... 4.1.4. Формирование допустимого множества типоразмеров корпусов средствами подсистемы логического вывода

4.1.5. Формирование системы предпочтений проектировщика

4.1.6. Результаты экспериментальных исследований с ИСППР

4.2. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

РАЗНОГАБАРИТНЫХ ЭРЭ

4.2.1. Формальное представление задачи размещения

4.2.2. Исследование возможности использования стандартного ГА и эволюционных стратегий для решения задачи размещения ЭРЭ.................. 4.2.3. Адаптированный ГА как один из методов решения задач размещения разногабаритных ЭРЭ

4.2.4. Исследование эффективности применения адаптированного ГА для решения задач размещения

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ

Автоматизированное проектирование (АП) конструкций радиоэлектронных средств (РЭС) характеризуется неполнотой проектной информации на всех этапах разработки нового технического объекта (ТО) - от анализа технического задания до разработки конструкторской документации. Высокий уровень неполноты является принципиальным при описании объектов проектирования (ОП), относящихся к классу РЭС и структура которого представляет собой иерархию сильно связанных элементов конструкции. Далеко не всегда удается применить точные математические методы для решения задач АП РЭС, поскольку часто их решение основывается на использовании субъективных знаний и опыта проектировщика, характеризующихся неполнотой и фрагментарностью. Формализация экспертных знаний традиционно производилась с использованием в процессе проектирования систем, основанных на знании - экспертных систем (ЭС). Соответствующие системы САПР получили название интеллектуальных САПР (ИСАПР).

Многие задачи АП РЭС, решение которых основывается на субъективных знаниях о закономерностях проблемной области, сводятся к задачам принятия решений в условиях многокритериальности и оптимизации. Для решения таких насыщенных расчетами задач часто недостаточно привлечения только технологии ЭС, для которой характерно доминирование символьных методов.

Поэтому для построения ИСАПР РЭС требуется привлекать альтернативные методы интеллектуализации.

В настоящее время на основе исследований в основном зарубежных ученых [97, 111, 114-117, 120-122, 131-133, 137] формируется методология “мягкие вычисления”, среди направлений которой можно выделить нечеткие системы (НС) [111, 114-117, 121, 132, 137] и генетические алгоритмы (ГА) [97, 111, 116, 117, 122, 131, 137]. В рамках указанных направлений новыми методами могут быть решены традиционные для САПР задачи оптимизации и принятия проектных решений в условиях неполноты проектной информации.

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

В последнее время вопросам построения систем, в основе которых лежит принцип “мягких вычислений” уделяется большое внимание. За рубежом издается международный журнал “Fuzzy Sets and Systems”, одним из членов редколлегии которого является российский академик Н. Н. Моисеев.

Проводятся регулярные (в том числе и российские) научно-практические конференции, где рассматриваются проблемы построения НС и ГА для решения широкого спектра практических задач анализа и синтеза.

Существенный вклад в исследования НС внесли российские ученые А. Н.

Аверкин, И. З. Батыршин, В. Б. Тарасов. Одним из авторов работ по использованию генетических алгоритмов в АП РЭС является В. В. Курейчик.

Особенности проблемной области оказывают значительное влияние на способ реализации НС и ГА. Так учет неполноты системы предпочтений проектировщика при выборе оптимального варианта конструкции РЭС, который является иерархическим многокомпонентным ОП требует использовать не только простые решающие правила, но и формальные методы многокритериального анализа с учетом нечеткости экспертных оценок и стратегий свертывания критериев. Научная проблема формализации процессов принятия решений в САПР РЭС заключается в разработке интеллектуальных систем, синтезирующих традиционные математические методы многокритериального анализа, методы НС и ЭС.

Большинство задач оптимизации конструкций РЭС характеризуются значительным пространством поиска с большим количеством локальных экстремумов. Учитывая это, свойство стохастичности стандартного ГА не может гарантировать нахождение эффективных вариантов ОП. Повысить качество решений, найденных с использованием методов генетического поиска, возможно при определении оптимальных значений параметров алгоритма и адаптировании ГА к задачам оптимизации. В связи с этим, научная проблема построения ГА для решения задач оптимизации конструкций РЭС состоит в повышении его эффективности путем разработки методов адаптации ГА к определенному множеству задач.

автоматизация проектирования конструкций РЭС. В качестве предмета исследования выступают нечеткие системы и генетические алгоритмы для решения задач автоматизированного проектирования конструкций РЭС.

Перечисленные аспекты проблемы автоматизации проектирования конструкций РЭС с использованием нечетких систем и генетических алгоритмов делают тему диссертационной работы актуальной.

Цель предпринимаемого исследования заключается в разработке моделей, методов и средств автоматизированного проектирования конструкций РЭС с использованием нечетких систем и генетических алгоритмов.

Для достижения поставленной цели необходимо решить следующие задачи исследования:

1. Необходимо провести сравнительный анализ возможностей и ограничений САПР РЭС, выявить характерные особенности проблемной области проектирования конструкций РЭС и определить место НС и ГА в задачах 2. Разработать метод многокритериального анализа при проектировании конструкций РЭС, учитывающую нечеткий характер системы предпочтений проектировщика и подчинение различных групп критериев различным стратегиям агрегации.

3. Разработать метод адаптации стандартного ГА к задачам оптимизации.

4. Разработать комплекс программных средств на основе созданных методов и моделей для решения задачи определения оптимального типоразмера корпуса для стендового технологического оборудования и задачи размещения разногабаритных электрорадиоэлементов на непрерывном монтажном пространстве.

Для достижения цели исследования применялись следующие методы исследования: методы системного анализа, теории управления, математического моделирования, методы представления знаний, совокупность методов, обобщенных направлением мягких вычислений и проектирование программных систем. В качестве средств создания интеллектуальных автоматизированных систем были использованы оболочка нечеткой ЭС FuzzyClips 6.04 и cреда разработчика Microsoft Developer Studio 97.

Достоверность научных положений, выводов и рекомендаций подтверждается результатами экспериментальных исследований, а также результатом использования материалов диссертации в проектных организациях и учебных заведениях.

ГЛАВА 1. АНАЛИЗ ВОЗМОЖНОСТЕЙ И ОГРАНИЧЕНИЙ САПР РЭС.

МЕСТО НЕЧЕТКИХ СИСТЕМ И ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В

ИНТЕЛЛЕКТУАЛЬНЫХ САПР РЭС

1.1. Анализ задач, решаемых традиционными САПР при проектировании конструкций РЭС. Понятие интеллектуальной САПР Под традиционными системами автоматизированного проектирования (САПР) в данной диссертационной работе будем понимать такие программные комплексы, которые созданы без привлечения методологии использования различных форм представления знаний и адекватного аппарата их обработки.

Широкий класс решаемых ими задач и повсеместное использование таких систем в процессе проектирования РЭС дает право отнести их именно к традиционным САПР. В данном разделе мы ограничимся рассмотрением САПР, которые возможно использовать на конструкторском этапе проектирования РЭС, что связано с предметом данного исследования.

На основе анализа характеристик развития САПР [19, 95] можно выделить три основных этапа: автоматизация отдельных видов вычислительных работ (решение разрозненных проектных задач); автоматизация основных функциональных процедур научно-исследовательских и опытноконструкторских работ (оптимизация проектных решений, управление ходом разработок, чертежно-графические работы и др.); комплексный подход к использованию ЭВМ и проектированию.

Анализ некоторых САПР РЭC был выполнен в [95]: системы РАПИРА, КОМПАС, КАУНАС и др. Количество проектных процедур данных САПР является небольшим и в их число, как правило, включают вычислительные процедуры, процедуры ввода-вывода информации, выпуск конструкторской документации (табл. 1.1). Программное обеспечение представляет собой отдельные программы, реализующие частные задачи проектирования (расчет схем по постоянному току, расчет переходных процессов, компоновку, размещение элементов, трассировку соединений и другие).

РАПИРА - 0 Ввод и контроль информации; формирование библиотек элементов; редактирование библиотек; выпуск конструкторской РАПИРА - 3 Расстановка микросхем; распределение контактов разъемов;

РАПИРА - 5.3 Расчет геометрии резисторов; размещение элементов;

КАУНАС - 2 Компоновка микросхем и разногабаритных элементов, их размещение, трассировка соединений, контроль ручной трассировки, вывод конструкторской документации КОМПАС - 82 Моделирование распространения сигналов, получение традиционных, можно разделить на две группы [23]: САПР, используемые для всех уровней иерархии проектируемой РЭС и САПР для проектирования ячеек.

К первой группе САПР относятся такие пакеты программ, как: AutoCAD [86], T-FLEX CAD [47, 50], EUCLID [23, 55]. С их помощью может производиться разработка конструкторской документации для всех уровней РЭС. В тоже время не автоматизированы разработка монтажных чертежей, проведение тепловых и прочностных расчетов. Универсальность этих пакетов специализирован для задач конструкторского проектирования РЭС, распространенных конструкторских элементов - корпусов устройств, разъемов, креплений, а также кабелей, проводов и так далее.

Во вторую группу входят такие известные САПР, как P-CAD [83, 85], OrCAD [84], ACCEL EDA [85]. Все они решают задачу получения разводки печатной платы с размещением на ней элементов. Однако для разработки сборочного чертежа необходимо применить машиностроительные САПР.

Пакеты программ второй группы решают однотипную задачу и, следовательно, являются функционально эквивалентными. Пакет OrCAD [84] помимо ввода схемы обеспечивает и ее моделирование. В табл. 1.2 рассмотрены некоторые задачи конструкторского проектирования, решаемые современными САПР.

Таким образом, для реализации комплексного конструкторского проектирования РЭС любого уровня (ячейка, блок, прибор, устройство) необходимо использовать САПР из каждой группы.

В конструкторском проектировании выделяют три группы задач [95]: синтез конструкции; контроль полученных конструктивных решений; оформление конструкторской и технологической документации. Рассмотренные традиционные САПР в основном решают задачи последних двух групп. Что касается задач первой группы, то в большинстве современных САПР РЭС решение задач синтеза сводится к решению следующих коммутационномонтажных задач:

• компоновка конструктивов (i 1) - го в конструктивы i - го уровня (компоновка простейших функциональных элементов логических схем И, ИЛИ, НЕ в корпуса микросхем (покрытие и типизация), компоновка интегральных микросхем (ИМС) и других электрорадиоэлементов (ЭРЭ) в ячейки, ячеек в блоки и устройства);

• размещение конструктивов (i 1) - го уровня в конструктивах i - го уровня (размещение цифровых аналоговых бескорпусных ИМС на подложке гибридной интегральной схемы, размещение ЭРЭ на печатной плате, размещение ячеек в блоке и т. д.);

• трассировка монтажных соединений между конструктивами на всех уровнях (соединение между кристаллами ИМС, печатный монтаж, межплатные соединения).

Современные конструкторские САПР, используемые при проектировании РЭС каркасных, полигональных (поверхностных) и объемных (твердотельных) конструкций T-FLEX CAD Создание параметрических сбо- Полная под- Windows NT/ рочных чертежей; создание специ- держка ЕСКД.

EUCLID Создание объемной модели дета- оформление Windows NT/95, рование поверхностей любой слож- ЕСКД, ISO, DIN, плат (ПП); автоматическое размещение компонентов на ПП; трассировка.

ПРАМ 5.3М/PC- Проектирование коммутационных Windows NT/ 97 плат по следующим технологиям:

металлизация сквозных отверстий;

попарно-сквозная металлизация отверстий; послойное наращивание;

ACCEL EDA Выполнение полного цикла Автоматическое Windows NT/ Авторами работы [48] отмечается, что за последние годы системы САПР, как системы геометрического моделирования были значительно усовершенствованы: появились средства 3D - поверхностного и твердотельного моделирования, параметрического конструирования, был улучшен интерфейс.

Несмотря на все эти усовершенствования, касающиеся, в основном, геометрических функций, с точки зрения всего процесса конструкторского проектирования системы САПР оказывают конструктору весьма слабую помощь и оставляют методологию конструкторской работы такой же, какой она была при использовании кульмана.

В источнике [48] также отмечается, что до последнего времени концепция автоматизации труда конструктора базировалась на принципах геометрического моделирования и компьютерной графики, а инженерные знания - основа проектирования - оставались за пределами компьютеризации. В связи с этим, особое внимание на современном этапе развития САПР уделяется вопросам построения интеллектуальных систем проектирования.

Во многих источниках, посвященных интеллектуальным САПР (ИСАПР) [4, 11, 15, 19, 22, 25, 26, 35, 39, 41, 48, 74, 75, 78, 99, 102, 104, 105, 111, 127] понятие интеллектуальности связывается с возможностью системы принимать решения без участия проектировщика. Как отмечается в [11], реальные задачи проектирования не сводятся к “электронизации” инженерной документации.

Уровень любой системы САПР должен характеризоваться не набором заложенных универсальных функций, а степенью автоматизации самого процесса проектирования конкретного изделия.

По мнению авторов [11, 19, 52] само понятие ИСАПР говорит о явном присутствии в системе знаний. При этом термин интеллектуальная система ни в коей мере не означает, что в процессе проектирования не может участвовать человек. Понятие ИСАПР подразумевает разумное сочетание в вопросах принятия решений между человеком и тем интеллектуальным ядром, которое присутствует в системе. Неоспоримым достоинством ИСАПР является то, что процесс проектирования изделия не связан с уровнем квалификации конечного пользователя. Вся нагрузка по грамотному формированию внутреннего интеллектуального ядра системы ложится на плечи эксперта в предметной области (ими, как правило, являются ведущие специалисты предприятий), и только на стадии создании системы.

Принципиальное отличие новой технологии от традиционной, когда обработка данных реализуется с помощью процедурно-ориентированных методов программирования и в ней ведущую роль играет процедурная компонента, а декларативная компонента (данные) остается пассивной, состоит в том, что ход решения задачи и результаты определяются текущим состоянием базы знаний, а не заложены жестко в алгоритм программы [26].

В работе [19] отмечается, что интеллектуализация комплексных САПР является очередным и естественным этапом развития систем и средств автоматизированного проектирования РЭС. Этот этап связан с реализацией процессов обмена и обработки информации в САПР на семантическом уровне как при организации диалогового взаимодействия, так и при организации функционирования комплекса аппаратно-программных средств САПР. Кроме того автором работы [19] высказывается мнение, что актуальность и значимость рассматриваемой проблемы позволяют говорить о необходимости теоретического обоснования, разработки и практической реализации нового вида обеспечения САПР - интеллектуального обеспечения.

В работах авторов [19, 52] при сравнении традиционных САПР и ИСАПР основное внимание акцентируется на том факте, что использование концепции баз данных (БД), которые являются основной составной частью информационного обеспечения традиционных САПР, не достаточно для осуществления процесса обработки знаний. Поэтому для описания семантики данных и их связи с задачами проектирования создается ориентированная на конкретную проблемную область база знаний (БЗ).

Выводы:

1. Диапазон задач, решаемых традиционными САПР РЭС ограничен, что не позволяет осуществить комплексный подход к использованию ЭВМ и проектированию.

2. Расширение диапазона задач достигается путем использования систем, основанных на знаниях (интеллектуальных системах).

1.2. Проблемные области интеллектуальных систем. Тип проблемной области проектирования РЭС Информация об основных характеристиках проблемной области, задачи которой предполагается решать ИСАПР, оказывает значительное влияние на выбор таких способов построения информационной системы, при которых достигается ожидаемый эффект с учетом затрачиваемых ресурсов. Ниже приведена классификация проблемных областей, используемая при построении интеллектуальных систем [98].

Понятие “проблемная область” включает предметную область (множество сущностей, описывающих область экспертизы, то есть множество объектов, значений и их характеристик и связывающих их отношений) и решаемых в предметной области задач. Иначе говоря, проблемная область включает сущности (структуры данных) и решаемые над ними задачи, представляемые в виде исполняемых утверждений (в виде правил, процедур, формул и т.п.). В связи с этим проблемная область определяется характеристиками соответствующей предметной области и характеристиками типов решаемых в ней задач.

Характеристики предметной области определяются следующим набором параметров:

1) тип предметной области:

- статический, то есть входные данные не изменяются за время сеанса работы приложения, значения других (не входных) данных изменяются только ЭС;

- динамический, то есть входные данные, поступающие от внешних источников, изменяются во времени, значения других данных изменяются ЭС или подсистемой моделирования внешнего окружения;

2) способ описания сущностей предметной области:

- совокупность атрибутов и их значений (фиксированный состав сущностей);

- совокупность классов (объектов) и их экземпляров (изменяемый состав сущностей);

3) способ организации сущностей в БЗ:

- неструктурированная БЗ;

- структурирование сущностей БЗ по различным иерархиям (например, иерархия “часть-целое”), что обеспечивает наследование свойств сущностей, представляемых в БЗ.

Характеристиками типов задач являются:

1) тип решаемых задач:

- задачи анализа и (или) синтеза;

- статические или динамические задачи;

2) частность (общность) исполняемых утверждений (правил, процедур, формул и так далее):

- частные (специализированные, конкретные) исполняемые утверждения;

- общие исполняемые утверждения.

Различные сочетания перечисленных выше параметров характеризуют проблемную среду. Выделяют несколько наиболее часто встречающихся типов проблемных сред [98]:

Тип 1. Статическая проблемная область: статическая предметная область;

сущности представляются как совокупность атрибутов и их значений; состав сущностей неизменяемый; БЗ не структурирована; решаются статические задачи анализа, используются только специализированные исполняемые утверждения.

Тип 2. Статическая проблемная область: статическая предметная область;

сущности представляются в виде атрибутов со значениями или вырожденных объектов (фреймов); состав сущностей неизменяемый; иерархия БЗ либо отсутствует, либо слабо выражена (нет наследования свойств); решаются статические задачи анализа, используются специализированные исполняемые утверждения.

Тип 3. Статическая проблемная область: статическая предметная область;

сущности представляются в виде объектов; состав сущностей изменяемый; БЗ структурирована; решаются статические задачи анализа и синтеза, используются общие и специализированные исполняемые утверждения.

Тип 4. Динамическая проблемная область: динамическая предметная область; сущности представляются совокупностью атрибутов и их значений;

состав сущностей неизменяемый; БЗ не структурирована; решаются динамические задачи анализа, используются специализированные исполняемые утверждения.

Тип 5. Динамическая проблемная область: динамическая предметная область; сущности представляются в виде объектов; изменяемый состав сущностей; БЗ структурирована; решаются динамические задачи анализа и синтеза; используются общие и специализированные исполняемые утверждения.

Анализируя множество решаемых задач и набор сущностей, описывающих область экспертизы [4, 26, 95], рассматриваемую проблемную область проектирования конструкций РЭС согласно приведенной классификации можно отнести к третьему типу. Действительно, большинство задач проектирования рассматриваемой проблемной области решается при неизменяемых входных данных во время сеанса работы приложения. Сущности представляются в виде объектов, поскольку состав сущностей (конструктивные элементы, условия эксплуатации, взаимосвязи между элементами конструкции и т.д.) является изменяемым. Принимая во внимание такие принципы проектирования конструкций РЭС, как декомпозиция и иерархичность описаний ОП, многоэтапность и итерационность проектирования, типизация и унификация проектных решений, интеллектуальная система проектирования структурирования заключается в ограничении круга сущностей, которые должны рассматриваться механизмом вывода, и таким образом сократить перебор при выборе решения и в адекватном способе представления знаний эксперта, повышая степень “прозрачности” БЗ.

Сферами приложений методов искусственного интеллекта (ИИ) в САПР РЭС являются [26]:

• структурный синтез РЭС, особенно на ранних стадиях проектирования;

• расчет и анализ параметров объекта проектирования в различных режимах с учетом разброса параметров компонентов и наличия дестабилизирующих факторов;

• параметрическая оптимизация;

• синтез топологии, включающий размещение элементов на плате и разводку соединений;

• верификация топологии.

Широкий круг задач АП РЭС, при которых целесообразно использовать многокритериального анализа слабоформализованных альтернатив ОП и задачи оптимизации. Характер слабоформализованности традиционно связывается с невозможностью построения точной математической модели ОП [75].

Вывод:

Проектирование конструкций РЭС обладает признаками проблемной области третьего типа согласно приведенной классификации. Соответствующими интеллектуальной САПР РЭС.

1.3. Анализ основных направлений построения интеллектуальных САПР Анализ публикаций, посвященных ИСАПР позволяет выделить основные направления в плане разработки программных продуктов, относящихся к ИСАПР:

• разработка инструментальных средств (ИС), предназначенных для создания интеллектуальных систем, решающих проектные задачи;

• разработка ИСАПР на базе проектирующих ЭС с применением ИС или используя традиционные языки программирования.

Отечественные инструментальные средства для проектирования ИСАПР Оболочка Подсистема Уточнение задачи; отбор аналогов Семантическая гибридной ЭС формирования проектируемого изделия; выбор или сеть фреймов;

“ПРОТЕЙ” требований синтез прототипа; формирование и продукционные Подсистема Отбор технических решений и посинтеза облика строение морфологической таблицы;

генерация вариантов; расчет техникоэкономических характеристик; выбор Подсистема Выявление составной части с задананализа элемен- ными характеристиками Инструмен- Подсистема ин- Создание набора взаимосвязанных Продукционные тальная систе- терактивного элементов пользовательского интер- правила ма “СПРУТ” проектирования фейса в виде сгенерированных модуэкранных форм лей Генератор Компьютеризация инженерных знаэкспертных ний, где элементом представления инженерных автоматизированное формирование Генератор Создание и заполнение разнообразсистем тексто- ных документов (спецификаций, графического маршрутных, операционных карт, Подсистема Использование и модификация дануправления БД ных, хранимых в системе СПРУТ в Среди работ в области ИСАПР следует особо отметить монографию [35], где достаточно подробно описаны принципы интеллектуальной поддержки начальных стадий проектирования на основе теории принятия решений и ЭС. В работе описаны методы, алгоритмы и программные средства решения задач проектирования, образующие оболочку гибридной ЭС (см. табл. 1.3).

Ряд статей [28, 29, 40, 48, 49] посвящен рассмотрению структурнофункционального решения интегрированной инструментальной системы автоматизированного проектирования “СПРУТ” (разработка АО “СПРУТ ТЕХНОЛОГИЯ”), которая представляет собой самостоятельную операционную среду с полным набором инструментальных средств и средств компьютеризации инженерной деятельности на единой информационной основе. В табл. 1.3 представлены характеристики оболочки гибридной ЭС “ПРОТЕЙ” [35] и ИС “СПРУТ” [28, 29, 40, 48, 49].

Следует отметить ограниченное число практических приложений методов искусственного интеллекта в современных системах АП РЭС. Основное количество из созданных пакетов программ, относящихся к ИСАПР, достигли стадий исследовательского или демонстрационного прототипов. В табл. 1. приведен перечень наиболее известных зарубежных ЭС, решающих задачи проектирования РЭС и микроэлектронных устройств.

Для того, чтобы рассмотреть особенности структурно-функционального решения ЭС в такой проблемной области, как проектировании РЭС, необходимо уделить некоторое внимание на структуру непосредственно объекта проектирования. Объект, относящийся к классу РЭС - это, как правило, сложный объект, представляющий собой систему с иерархической структурой. Связи между уровнями иерархии очень часто невозможно представить аналитическими выражениями, поэтому формальное описание системы и процессов, происходящих в ней, сопряжено со значительными трудностями математического характера.

CADHELP Проектирование цифро- Исследовательский Фреймы, FRANZLISP GRITTER Анализ правильности, Демонстрационный Фреймы, INTERLISP DFT Устранение обнаружен- Демонстрационный Правила PROLOG ных нарушений правил прототип EURISKO Проектирование новых Исследовательский INTERLISP видов микроэлектрон- прототип PEACE Проектирование Демонстрационный Логико-ориен- PROLOG REDESIGN Проектирование Исследовательский SADD Проектирование схем Демонстрационный Фреймы LISP SYN Разработка электронных Исследовательский Правила В целях упрощения решения общей задачи применяют декомпозицию такой задачи на ряд подзадач, решаемых в рамках отдельных иерархических уровней.

Для каждого уровня составляется математическая модель, достаточно полно отражающая связи и процессы, происходящие в нем. Что касается “стыковки” уровней, то здесь не всегда удается произвести решение в рамках формальных методов, поэтому прибегают к использованию методов решения задач на эвристическом уровне. В табл. 1.5 перечислены некоторые задачи, возникающие в процессе АП РЭС, сгруппированные по типу используемых знаний.

Распределение задач АП РЭС по типу используемых знаний используемых знаний использования Декларативные Набор Антецедент Представление информации знания фреймов продукцион- о характеристиках элементных правил ной базы, узлов, сборочных Продукцион- Набор четких Основа Определение влияния реалиные знания и нечетких модулей заций составных частей на взаимовлияния характеристик. Определение предпочтительности значений критериев. Определение допустимости сочетаний реализаций Процедурные Функции и Консеквент Поиск информации в БЗ, Опыт построения интеллектуальных систем для решения задач АП на основе ЭС позволяет выделить следующие особенности [35, 75, 98]:

- решаемые ЭС задачи в основном принадлежат к классу задач “вывода целого из частей”. Для этого класса характерно, что условия задачи задаются как части описания решения, а решение задачи выводится путем применения правил, интегрирующих заданные факты в целостное решение. В таких ЭС все возможные решения известны и поэтому, выдвигая и отвергая или подтверждая гипотезы, удается получить решение;

- малый удельный вес проектирующих систем и их принадлежность к стадии существования типа исследовательского или демонстрационного прототипа иллюстрирует высокую сложность разработок интеллектуальных систем подобного рода. В таких системах известны только требования к проектному решению в целом и проверить любое частичное решение на приемлемость удается далеко не всегда [98];

- при проектировании часто приходится принимать решения в условиях неполноты проектной информации, следствием которой выступает сложность ОП и размытый характер экспертных высказываний о типовых и эталонных соотношениях, устанавливающих связь между входными и выходными параметрами процесса проектирования [75].

Анализируя достижения в области построения ИС и ЭС и ограничения проектирующих интеллектуальных систем можно прогнозировать эффективное использование технологии ЭС для разработки таких ТО, принадлежащих классу РЭС, при которых широко используются унифицированные базовые несущие конструкции (УБНК).

Вывод:

Эффективное решение задач АП РЭС не может быть найдено только на основе современных интеллектуальных САПР, основным элементом которых выступает ЭС. Требуется привлечение дополнительных технологий решения проектных задач, характеризующихся значительным пространством поиска и высоким уровнем неполноты описания.

1.4. Анализ феномена неполноты проектной информации при построении интеллектуальных систем 1.4.1. Анализ различных аспектов неполноты. Способы формализации нечеткости Данные и знания, с которыми приходится иметь дело при решении различных проектных задач, редко бывают абсолютно точными и достоверными. В процессе проектирования нового изделия проектировщик, как правило, принимает решения на основе неполной проектной информации. Это может быть связано как со сложностью разрабатываемого технического объекта, который принципиально не может быть полностью описан [110], так и с непригодностью количественных методов для анализа гуманистических систем [10], к которым можно также отнести и систему “проектируемый объект - проектировщик”.

Обзор работ [5, 10, 18, 27, 31, 35, 36, 74, 75, 80, 98, 107, 110, 111, 117] позволяет выделить три основных аспекта неполноты: неточность, неопределенность и нечеткость. Для каждого из перечисленных аспектов имеет место изучающая его теория (или теории) [110]. В [111] отмечается неоднозначность трактования понятия неполноты в российской литературе, где термины неполноты и неопределенности являются синонимичными, что характерно для современной теории управления.

Рассмотрим один из аспектов неполноты в данных и знаниях - их неточность. Высказывание называется неточным, если его истинность (или ложность) не может быть установлена с определенностью [36]. Один из наиболее первых и простых подходов к проведению рассуждений при наличии неточности был использован в экспертной системе MYCIN [82]. Для реализации правдоподобных рассуждений в системе была заложена модель приближенной импликации в которой использовались числа (принимающие свои значения на шкале от -1 до 1), называемые коэффициентами уверенности, которые указывают силу данного эвристического правила. Например, число 0. говорит о том, что степень уверенности весьма высока (0.7 единицы), но не носит абсолютный характер. Введение таких чисел представляет собой попытку отойти от точности, присущей исчислению предикатов. В системе MYCIN утверждения не являются просто либо истинными, либо ложными. Рассуждение является неточным, и эта неточность имеет численное выражение в правилах.

К недостаткам данного метода можно отнести тот факт, что коэффициенты уверенности не являются, скажем, вероятностями, и для работы с ними предложены уникальные формулы, не встречающиеся в какой-либо математической теории. Как отмечается в [5], именно слабая теоретическая обоснованность - самый серьезный недостаток этого метода.

Что касается другого аспекта неполноты - неопределенности, то он имеет место при выборе альтернатив, когда необходимо принять решение о наиболее предпочтительном (оптимальном) варианте ОП.

Рассмотрим более подробно следующий аспект неполноты данных и знаний, а именно их нечеткость. Наиболее распространенный способ оперирования нечеткими данными связывается с использованием нечетких множеств. Автор [31] подчеркивает, что нечеткие множества представляют собой мощный инструмент для моделирования различных видов логического вывода (о которых будет сказано ниже), и их (нечеткие множества) можно рассматривать как подходящий способ установления упорядочения на интерпретациях.

В настоящее время среди приложений нечетких множеств можно отметить такие области [10, 31]: классификация и анализ данных, вывод в условиях неопределенности и проблемы принятия решений. Эти три применения используют три вида семантики степеней принадлежности, соответственно, в терминах сходства, неопределенности и предпочтения. Пусть µ F ( u) - степень принадлежности элемента u нечеткому множеству F, определенному на U.

Тогда при интерпретации принадлежности как сходства µ F ( u) - степень близости u к прототипу F. Эта интерпретация появилась раньше других и характерна для таких приложений, в которых ставятся задачи абстракции (выборки) данных. Следующая интерпретация была предложена позднее, и для нее предполагается, что F - множество более или менее предпочтительных объектов. В этом случае µ F ( u) представляет пригодность выбора u как значение переменной x и рассматривается как степень предпочтения. Такая интерпретация применяется в нечеткой оптимизации и анализе решений.

Интерпретация принадлежности как степени неопределенности была предложена Л. Заде в 1978 году. Здесь µ F ( u) - степень возможности того, что параметр x имеет значение u, отражающая, что “ x - это F ”. Рассматривая эпистемологическую интерпретацию, а физический смысл возможности больше соответствует предпочтению и пригодности.

Интересное замечание о теории нечетких множеств было сделано Дюбуа и Прадом [119]. Функцию принадлежности можно толковать как отношение упорядочения F, связанное с предикатом F, где u F u означает, что u больше рассматриваться как тернальное отношение ( u 3 ), т.е. как набор { u, u U } бинарных отношений, представляющих собой полное предупорядочение. Тогда неравенство µ R ( u, u ) µ R ( u, u ) может представлять ситуацию, в которой В работе [10] отмечается, что теорию нечеткости можно включить в теорию вероятности, используя при этом понятие случайного множества. Кроме того, в [10] упоминается работа Л. Заде, где фокусируется внимание на том, что нечеткость и вероятность моделируют разные типы неопределенности и взаимодополняют друг друга.

Основными объектами критики по отношению к теории нечетких множеств являются следующие: интерпретация функции принадлежности нечеткого множества, субъективный способ ее задания, способ представления функции целесообразность ее использования.

Автором [10] отмечается, что внутреннее противоречие теории нечетких множеств заключается в том, что она была создана для моделирования качественных суждений человека, для описания плохо определенных процессов, для которых невозможно построить точную модель, и о которых отсутствует точная информация. Однако эта теория требует точного задания значений принадлежности в виде чисел из интервала [0, 1], над которыми затем совершаются количественные операции. Это предполагает, что значения принадлежности должны измеряться в абсолютной шкале, что, по видимому, невозможно при субъективном задании значений принадлежности. Попытка представить качественные суждения человека о степени принадлежности или о степени обладания объектами рассматриваемым свойством в виде чисел, измеряемых в абсолютной шкале, приводит к построению нечетких моделей, неадекватных моделируемым процессам. Это противоречие достаточно успешно решается при моделировании объективных процессов, в результате отладки, настройке моделей при экспериментировании на моделируемом процессе, однако при моделировании субъективных процессов проблема повышения адекватности нечетких моделей стоит достаточно остро.

Следует различать по мнению автора [10] по крайней мере два типа нечеткой информации в зависимости от области определения нечетких множеств.

К первому типу относятся нечеткие множества, определенные на некотором числовом множестве U, например на интервале вещественных чисел. В этом случае говорят о нечетких множествах как о нечетких величинах, а множество называется числовой шкалой. Примерами нечетких величин являются нечеткие числа и нечеткие интервалы [10, 31].

Ко второму типу относятся нечеткие множества, определенные на нечисловом множестве, например, на множестве правил и фактов экспертной системы, на множестве целей или альтернатив, на элементах некоторого бинарного отношения между произвольными объектами и т.д. В этом случае говорят о нечетком множестве A = {( x, A( x ))} как о множестве “нечетких объектов” ( x, A( x )). Определение, интерпретация и обработка нечетких множеств этих двух типов в зависимости от области использования могут существенно отличаться между собой.

В [27] также различают несколько типов нечетких множеств, отражающих представление субъекта о некоторой расплывчатой категории. Различают простые категории, определенные на объективном линейно-упорядоченном универсальном множестве (например, “большой”), и сложные категории, которые требуют одновременного рассмотрения нескольких универсумов (“коренастый”), и в которых даже сами универсальные шкалы определимы с трудом (“красивый”). Для простых категорий оценка функции принадлежности есть задача теории психологических измерений. В основном функция принадлежности определяет порядок элементов. Более богатая структура порядка может быть получена при сравнении пар элементов из U. Отмечаются, что наиболее успешно на практике применяются два метода: 1) субъект задает ядро и носитель нечеткого множества, а затем с помощью светового пера графически строится функция принадлежности на множестве элементов носителя, не принадлежащих ядру; 2) используется параметрическое представление функции принадлежности. Отмечается, что небольшая ошибка при определении границ ядра и носителя будет менее значимой, чем при представлении расплывчатой категории обычным множеством (интервалом) [27]. Для сложных категорий, определенных на декартовом произведении линейных шкал функция принадлежности может быть получена за счет свертывания информации по простым категориям. Для категорий с трудно определимым универсальным множеством в качестве возможного решения предлагается введение универсума, состоящего из небольшого числа эталонных значений или состояний, в случае необходимости упорядоченных. В этом случае предполагается также, что достаточно ограничиться небольшим числом “типовых” значений принадлежности.

В [75] приведены основные понятия теории нечетких множеств и описание нечеткой экспертной информации в виде формальных систем нечетких высказываний. Кроме того, предложены нечеткие модели принятия решений на трудноформализуемых этапах проектирования, основанных на правилах дедуктивного и индуктивного выводов. Рассмотрены нечеткие неориентированные и ориентированные гиперграфы как формальные модели нечетких систем принятия решений. Авторами [75] предложены методики решения задач, связанных с выбором варианта проектирования при нечеткой экспертной информации и с выбором аналогов проектируемого изделия.

Авторами [35] представлены ряд методов формализации и обработки нечеткой информации. Достаточно подробно описан процесс выполнения нечетких алгоритмов, которых образуют совокупности нечетких систем правил “Если-То”.

1.4.2. Схемы логического вывода. Понятие нечеткой системы При обосновании решений с помощью логического вывода пытаются представить все знания о задаче средствами какой-либо формальной логической системы. Формальная логическая система задается четверкой компонентов вида [35]:

где B - множество базовых элементов, из которых строятся все выражения в FS;

S - множество синтаксических правил, выделяющих среди всех возможных выражений из базовых элементов те, которые синтаксически правильны (являются формулами); A - множество аксиом FS, т.е. формул, которым априорно приписывается статус истинности, I - правила вывода.

При практическом использовании формальных логических систем, где требуется высокая эффективность процедур, возможно, за счет их общности, данные системы заменяют совокупностями продукций и методов прямого и обратного вывода [75, 82, 98, 107].

В наиболее общей форме продукцию можно представить следующим образом [35]:

Здесь N - уникальный номер продукции; K - описание класса ситуаций, в которых данная продукция может использоваться; - условие, при выполнении которого продукция актуализируется; A - левая часть продукции;

B - правая часть продукции; Q - указание на изменения, которые надо внести в данную продукцию (в условие C, в A или в B ) или в другие продукции системы после применения данной продукции. Применение продукции связано с ее ядром A B, которое можно интерпретировать как выполнение B или замену A на B при условии, что A истинно или A присутствует в некотором описании, к которому применяется продукция.

Системы продукций чаще всего реализуются в виде групп правил как условных операторов вида : ЕСЛИ условие ТО заключение.

Системы нечетких продукций строятся на основе понятий лингвистической переменной и нечеткого высказывания. В [32] рассматриваются понятия нечеткой переменной и лингвистической переменной, которые используются экспертом при описании сложных объектов и явлений, а также при формализации процессов принятия решений на трудноформализуемых этапах проектирования.

Определение 1.1. Нечеткая переменная представляет собой тройку объектов где - наименование нечеткой переменной; X = {x} - область ее определения;

C = {< µ ( x ) / x >} - нечеткое множество на X, описывающее ограничения на возможные значения нечеткой переменной (ее семантику).

Определение 1.2. Лингвистической переменной (ЛП) называется пятерка где - наименование ЛП; T - множество ее значений (терм-множество), представляющих собой наименование нечетких переменных, областью определений каждой из которых является множество X. Множество T называется базовым терм-множеством ЛП; G - синтаксическая процедура (грамматика), позволяющая оперировать элементами терм-множества T, в частности генерировать новые осмысленные термы; M - семантическая процедура, позволяющая превратить каждое новое значение ЛП, образуемое процедурой G, в нечеткую переменную, т.е. приписать ему нечеткую семантику путем формирования соответствующего нечеткого множества.

Нечеткими высказываниями называются высказывания следующего вида [75]:

1. высказывание < есть >, где - наименование ЛП, отражающей некоторый объект или параметр реальной действительности, относительно которой производится утверждение, являющейся ее нечеткой оценкой (нечеткой переменной);

2. высказывания вида < есть m >, < есть Q >, < Q есть m >, < m есть Q >, при этом m называется модификатором (ему соответствуют такие слова, квантификатором (ему соответствуют слова типа большинство, несколько, много, немного, очень много и др.);

3. высказывания, образованные из высказываний 1-го и 2-го видов и союзов И;

ИЛИ; ЕСЛИ..., ТО...; ЕСЛИ..., ТО... ИНАЧЕ.

Определение 1.3. Под нечеткой системой (НС) в рамках данного исследования будем понимать систему нечетких высказываний, которые могут относиться к любому из представленных выше видов.

Вывод в базе нечетких продукций строится на основе понятия нечеткого отношения [46, 117]. Знание эксперта A B отражает нечеткое причинное отношение предпосылки и заключения, называемое нечетким отношением и обозначаемым R :

R можно рассматривать как нечеткое множество на прямом произведении заключений Y.

Нечетким отношением R между множествами X и Y называется функция где в общем случае предполагается, что L - это полная дистрибутивная решетка.

В том случае, когда L является отрезком вещественной прямой [0, 1], функция (1.1) записывается в виде функции принадлежности В [74] рассматриваются следующие операции над нечеткими отношениями.

Объединение R S и пересечение R S нечетких отношений определяются следующим образом:

Отношение включения R S для нечеткого отношения определяется с помощью отношения частичного порядка в L :

отношения R между X и Y и нечеткого отношения S между Y и Z :

Здесь означает наименьшую верхнюю грань множества элементов ( R ( x, y ) S ( y, z )), где y пробегает все значения из Y.

В случае L = [ 0,1] соотношение (1.2) записывается в виде Основными правилами умозаключений являются два силлогизма [65, 81]:

modus ponens и modus tollens.

Рассмотрим случай, когда посылка и заключение выражаются с использованием нечетких высказываний.

Как известно [117, 118, 121], нечетким правилом modus ponens называется следующая схема вывода:

где Ai и Bi - нечеткие высказывания.

Нечеткий modus tollens:

Cвойства обобщенных нечетких умозаключений:

1) Базовое свойство умозаключений. Если множество фактов A совпадает совпадать с множеством следствий в импликации B = B.

2) Свойство общей неопределенности. Если факт полностью отрицает Процесс получения (нечеткого) результата вывода B с использованием данных наблюдения A и знания A1 B1 можно представить в виде формулы Здесь называется композиционное правило (правило свертки) нечеткого вывода. Кроме того, стрелка в правиле A1 B1 называется нечеткой импликацией.

На практике используемый метод композиции определяется комбинацией двух операторов - дизъюнкцией и конъюнкцией [121] (табл. 1.6).

Конъюнктивные и дизъюнктивные операторы ( x, y [ 0,1] ) Схема нечёткого вывода разными авторами уточняется с точностью до оператора нечёткой импликации. Распространены 5 схем нечёткого вывода [110, 117, 121].

Схема 1: Импликация моделируется минимумом, а агрегация - максимумом (максиминный метод вывода или схема вывода по Мамдани).

Схема 2: По Цукамото. Входные и выходные функций принадлежности реализуются в виде монотонных функций. Из-за их монотонности вычисления выходной переменной сводят к усреднению значений, полученных по разным правилам.

Схема 3: По Суджено. Правые части правил вывода ограничиваются линейным случаем:

Данная схема разрабатывалась для нечетких контроллеров.

Схема 4: По Ларсену. Моделирует импликацию произведением. В частности, правая часть, представленная нечетким множеством умножается на степень возможности левой части правила.

Схема 5: Упрощенная схема нечеткого вывода:

If X is Ai and Y is Bi then z = Zi (где Zi - четкое значение).

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

Дефаззификацией называют определение четкого представляющего элемента определения центра тяжести (центроидный метод) [121]. Центроидный метод вычисляет центр тяжести фигуры, ограниченной функцией принадлежности Кроме центроидного метода большое распространение получил метод медианы (используется среднее значение (медиана) верхней границы нечеткого множества). Выбор необходимого метода дефаззификации определяется во многом решаемой задачей.

Вывод:

Использование аппарата нечетких множеств позволяет адекватно представить знания эксперта, которые характеризуются неполнотой и являются субъективными. Тематика публикаций показывает, что в настоящее время применение нечеткой логики выходит за границы нечетких контроллеров и представляется весьма перспективным при решении таких насыщенных эмпирическими зависимостями задач, как анализ и синтез конструкций РЭС.

1.5. Поддержка процессов принятия решений в САПР. Применение нечетких систем для формализации процессов принятия решений 1.5.1. Системы поддержки принятия решений в САПР Проектировщик или лицо, принимающее решение (ЛПР), вынуждены исходить из своих субъективных представлений об эффективности возможных альтернатив и важности различных критериев. Эта субъективная оценка оказалась в настоящее время единственно возможной основой объединения разнородных физических параметров решаемой проблемы в единую модель, позволяющую оценивать варианты решений [54].

Признанием фактора субъективности ЛПР в принятии решения нарушен фундаментальный принцип методологии исследования операций: поиск объективно оптимального решения. Признание права на субъективность решения - есть признак появления новой парадигмы, характерной для другого научного направления - принятия решений при многих критериях [103].

Однако при принятии решений по многим критериям существует и объективная составляющая, которая включает в себя ограничения, накладываемые внешней средой на возможные решения (наличие ресурсов, экологические требования и другие). Многочисленные психологические исследования показывают, что сами проектировщики или ЛПР без дополнительной аналитической поддержки используют упрощенные, а иногда и противоречивые решающие правила [134].

Компьютерная поддержка процесса принятия решений так или иначе основана на формализации методов получения исходных и промежуточных оценок, даваемых конструктором, и алгоритмизации самого процесса выработки решения. Неопределенность (неполнота) является неотъемлемой частью процессов принятия решений. Эти неопределенности принято разделять на три класса [103]:

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

- неопределенность, связанная с невозможностью точного учета реакции окружающей среды на действия ЛПР;

- неточное понимание своих целей ЛПР.

Увеличение объема информации, поступающей проектировщикам, усложнение решаемых задач, необходимость учета большого числа проектируемому объекту настоятельно требуют использовать вычислительную технику в процессе принятия решений. В связи с этим появился новый класс вычислительных систем - системы поддержки принятия решений (СППР).

В работе [53] дано определение СППР: “Системы поддержки принятия решений являются человеко-машинными объектами, которые позволяют ЛПР использовать данные, знания, объективные и субъективные модели для анализа и решения слабоструктурированных и неструктурированных проблем”. В этом слабоструктурированных и неструктурированных задач.

В соответствии с работой [134] к слабоструктурированным относятся задачи, которые содержат как количественные, так и качественные оценки проблемы, причем качественные имеют тенденцию доминировать.

Неструктурированные проблемы имеют лишь качественное описание.

Человеко-машинная процедура принятия решений в САПР с помощью СППР представляет собой итеративный процесс взаимодействия конструктора и компьютера. СППР в САПР [103]:

1. Генерируют возможные варианты конструкторских решений.

2. Осуществляют оценку этих вариантов и выбирают лучший.

3. Обеспечивают постоянный обмен информацией между конструкторами о принимаемых ими решениях и помогают согласовывать групповые решения.

4. Моделируют принимаемые решения (в тех случаях, когда это возможно).

5. Оценивают соответствие выполнения принятых конструкторских решений намеченным целям.

В работах [35, 75, 103, 110, 111] подчеркивается перспективность использования для решений задач многокритериального выбора метода анализа иерархий Т.Саати [89, 90].

1.5.2. Многокритериальный выбор на основе метода анализа иерархий Среди современных методов исследования операций известен и широко применяется метод анализа иерархий (МАИ) Т. Саати [89, 90], который позволяет решать задачу многокритериального выбора слабоформализованных альтернатив. В МАИ Саати предлагает математическую обработку экспертных оценок на основе матричных вычислений и аддитивной свертки критериев.

Кратко изложим основные положения МАИ. При решении задачи многокритериального выбора объекты составляют нижний уровень иерархии.

Вершиной иерархии является цель. "Минимальное" представление задачи выбора - это трехуровневая иерархия:,, (рис.1.1).

Критерий-1-1 Критерий-1-2...... Критерий-1-n Критерий-2-1 Критерий-2-2...... Критерий-2-n Критерий-m-1 Критерий-m-2...... Критерий-m-n Рис. 1.1. Иерархия многокритериального выбора В иерархии каждый элемент высшего уровня считается значимым для каждого низшего, то есть действуют все возможные связи. Элементом анализа является в МАИ уровень иерархии, начиная со вторичного. Для уровня (критериев, объектов) методом попарных сравнений составляется матрица на основе шкалы субъективных суждений.

Этапы МАИ:

1. Составить иерархию (рис.1.1).

2. Попарные сравнения критериев (объектов) на основе шкалы субъективных суждений (табл. 1.7).

Матрица попарных сравнений размерности n n :

3. Расчет вектора локальных приоритетов - весов критериев (объектов) X = ( x1, x2,..., xn ) :

4. Расчет собственного значения матрицы W - max, индекса согласованности ИС, отношения согласованности ОС.

Для контроля согласованности матрицы W вычисляются:

где Иср - индекс согласованности матрицы размерности n, заполненной при случайном моделировании (табл. 1.8).

согласованность Величина ОС должна быть порядка 10% или менее, чтобы быть приемлемой. В некоторых случаях можно допустить 20%, но не более. Если ОС выходит из этих пределов, то участникам нужно исследовать задачу и проверить свои суждения.

5. Этап расчета - проведение анализа для следующего уровня критериев (объектов).

6. Этап вычисления глобального вектора приоритетов.

Полученные собственные векторы (один из каждого критерия) взвешиваются с помощью соответствующей компоненты собственного вектора объединенного критерия, и результаты суммируются и нормализуются.

Наличие публикаций, посвященных проблеме модификации МАИ и его применения для решения широкого спектра прикладных задач [20, 79, 88, 103, 109, 110] демонстрирует устойчивый интерес к данному методу. Так в [20] рассматриваются вопросы реализации математического аппарата МАИ в виде пакета программ для трех-, четырех- и пятиуровневых полных и неполных иерархий. Программное обеспечение разработано в среде Matlab for Windows и позволяет решать задачи эффективного ранжирования конечного множества сложных объектов в условиях неполноты и неопределенности исходной информации. Описываются функциональные возможности пакета.

Автором [79] отмечается, что в процессе проектирования электронной аппаратуры при переходе с одного этапа или подэтапа на другой требуется давать оценку проделанной работы, сравнивать варианты решений, выбирать наиболее приемлемые. Предлагается эту процедуру выполнять с использованием МАИ для проектирования электронных вольтметров.

В работе [109] рассмотрена система экспертных оценок и их обработка для МАИ. Выявлены ее недостатки, которые заключаются в большой вероятности логических ошибок, возникающих при попарных сравнениях значительного количества очень сложных элементов. Предложено использовать шкалу абсолютной важности элементов для упрощения расчетов при обработке оценок и исключения формальных рассогласований в ответах экспертов.

Представление системы предпочтений проектировщика в МАИ, используя понятие иерархии, может оказаться эффективным при построении САПР РЭС.

При этом сложная задача формирования данной системы предпочтений, требующая учета множества взаимоисключающих критериев, может быть сведена к совокупности более простых задач, доступных для решения с использованием парных сравнений.

1.5.3. Способы формализации качественной экспертной информации при принятии решений Обзор работ, посвященных исследованию способов формализации экспертной информации при принятии решений [3-5, 10, 15, 16, 18, 26-28, 31, 32, 35, 36, 53, 54, 74, 75, 82, 89, 90, 103, 104, 111] позволяет выделить в качестве удобного инструмента для представления знаний эксперта нечеткие множества [32, 46]. Можно выделить в качестве основных несколько представленных ниже математических постановок задач принятия решений на основе теории нечетких множеств [3, 16].

1. Многокритериальный выбор альтернатив на основе максиминной свертки.

представляют собой степени соответствия этим понятиям. Оценки альтернатив по каждому критерию представлены нечетким множеством. Правило выбора лучшей альтернативы представляется как пересечение нечетких множеств, соответствующих критериям, причем операция пересечения реализовывается различными способами: путем арифметического умножения или взятия минимума. Лучшей считается альтернатива, имеющая наибольшее значение целевой функции. Если критерии имеют различную важность, то их вклад в общее решение представляется как взвешенное пересечение. Весовые коэффициенты определяются, используя процедуру парного сравнения критериев по МАИ Т. Саати.

2. Многокритериальный выбор альтернатив на основе аддитивной свертки.

В рассматриваемом методе экспертные предпочтения представлены с помощью нечетких чисел, имеющих функции принадлежности треугольного вида. Оценка каждой альтернативы по каждому критерию представлена нечетким числом, а относительная важность конкретного критерия задается нормированным коэффициентом. Взвешенная оценка альтернативы по всем критериям является результатом линейной комбинации нечетких чисел и также имеет функцию принадлежности треугольного вида. Ранжирование альтернатив с использованием полученных взвешенных оценок производится на основе их нечеткой композиции. Лучшей считается альтернатива, имеющая наибольшее значение целевой функции (результата нечеткой композиции).

отношения предпочтения.

Сравнение альтернатив выполняется попарно по каждому критерию, на основании чего формируются отношения предпочтения. Процедура принятия решений включает следующие основные шаги:

Шаг 1.

Строится нечеткое отношение, которое является пересечением исходных отношений предпочтения и определяется подмножество недоминируемых альтернатив.

Шаг 2.

Строится нечеткое отношение, определяемое линейной комбинацией отношений предпочтений. Весовые коэффициенты, представляющие собой коэффииценты относительной важности являются нормированными величинами. Определяется соответствующее подмножество недоминируемых альтернатив.

Шаг 3.

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

Шаг 4.

Рациональным считается выбор альтернатив из множества, представляющего собой верхнюю границу подмножества, полученного на шаге 3.

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

4. Ранжирование альтернатив на множестве лингвистических векторных оценках.

Задано множество альтернатив и множество соответствующих исходов.

Каждый исход характеризуется альтернативой и вектором лингвистических оценок на множестве критериев. Множество лингвистических векторных оценок исходов упорядочивается путем введения функции принадлежности нечеткого отношения порядка. Между множеством альтернатив и исходов существует взаимно однозначное соответствие. Задача принятия решений с использованием данного метода состоит из следующих основных шагов:

- построение нечеткого отношения порядка на основе парного сравнения альтернатив по критериям;

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

- выявление лучшей альтернативы.

5. Многокритериальный выбор альтернатив с использованием правил нечеткого вывода.

В данном методе для оценки альтернатив по критериям используются функции принадлежности соответствующих понятий, а представление о степени удовлетворительности альтернативных вариантов выражаются с помощью правил. Результат получается на основе процедуры нечеткого вывода на правилах.

Представления ЛПР об удовлетворительности решения выражены правилами, антецеденты которых содержат комбинации критериев с соответствующими значениями, соединенные связками “И”. Заключения правил отражают представления ЛПР о степени удовлетворительности решения, для чего используется соответствующая ЛП. Лучшей считается альтернатива с наибольшим значением точечной оценки данной ЛП.

Выводы:

1. Представление системы предпочтения ЛПР в виде иерархической структуры в СППР отражает принцип декомпозиционно-агрегативного подхода, выступающего в качестве основного при построении САПР РЭС.

2. Процессы выбора технического решения в САПР РЭС - это по своей природе иерархические субъективные процессы принятия решений. В связи с этим при построении СППР возникает необходимость применения НС для учета нечеткого характера субъективной экспертной информации.

1.6. Генетический алгоритм как метод решения задач оптимизации.

Методология мягких вычислений 1.6.1. Схема стандартного генетического алгоритма Стандартный генетический алгоритм (ГА) характеризуется следующими особенностями [97, 122]:

1) Задается целевая функция, определяющая эффективность каждого найденного решения.

2) В соответствии с определенными ограничениями инициализируется исходная популяция потенциальных решений. Каждое решение кодируется как вектор x, который называется хромосомой. Его элементами являются части вектора - гены, изменяющие значения в определенных позициях, которые называются аллелями. Наиболее часто используется двоичное представление переменных.

3) Каждая хромосома xi, i = 1,..., p в популяции декодируется в необходимую форму для последующей оценки и затем ей присваивается значение эффективности µ( xi ) в соответствии с целевой функцией.

Pi, i = 1,..., p, которая зависит от эффективности данной хромосомы.

5) В соответствии с вероятностями воспроизведения Pi создается новая популяция хромосом, причем с большей вероятностью воспроизводятся наиболее эффективные элементы. Хромосомы производят потомков, используя обмениваясь частями строк) и мутация (вероятностное изменение аллелей).

6) Процесс останавливается, когда получено удовлетворительное решение, либо если исчерпано отведенное на эволюцию время. Если процесс не окончен, то вновь повторяются процессы оценки и воспроизведения новой популяции.

Формально ГА описывается следующим образом:

где P 0 = (a10,..., a ) - исходная популяция, где ai0 - решение задачи, представленное в виде хромосомы;

- целое число (размер популяции);

l - целое число (длина каждой хромосомы популяции);

s - оператор отбора;

- отображение, определяющее рекомбинацию (кроссинговер и мутацию);

f - целевая функция;

t - критерий остановки.

P 0 является случайно сгенерированной исходной популяцией и параметры и l описывают число индивидуумов одного поколения и длину (размер) каждого индивидуума популяции соответственно.

Оператор отбора s порождает промежуточную популяцию P t из популяции P t посредством отбора и генерации новых копий элементов P t : P t = s( P t ).

Целевая функция f, обеспечивающая обратную связь от результатов конкурентноспособных индивидуумов популяции.

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

i {1,..., }: rank (ait ) = i, где - означает в случае минимизации и в случае максимизации.

Следовательно, можно использовать индекс i для обозначения ранга элемента. В соответствии с этим предполагается, что элементы сортируются согласно их конкурентноспособности (оптимальности) так, что a1t будет лучшим элементом P t.

Отбор производится на основании вероятностей Ps (ait ), вычисленных для каждого индивидуума популяции. В настоящее время применяются следующие основные схемы отбора:

• Пропорциональный отбор:

• Линейное ранжирование:

• ( µ, ) - равномерное ранжирование:

Наиболее часто используется пропорциональная схема отбора.

В [97] отмечается, что одна из математических проблем, связанных с пропорциональным отбором состоит в том, что данная процедура не может Наилучшая хромосома в популяции может быть потеряна в любом поколении и нет какой-либо гарантии, что результаты эволюции, достигнутые в ряде поколений, не будут утрачены. Одним из способов преодоления этого является использование элитного отбора, который всегда сохраняет наилучшую хромосому популяции. Этот вид отбора гарантирует асимптотическую сходимость, но скорость сходимости при этом может существенно различаться в зависимости от вида конкретной решаемой задачи. Кроме того в [97] приводится теорема Холланда (теорема о шаблоне), результаты которой утверждают, что ГА - оптимальная процедура для получения лучших элементов.

(вероятность применения, выбор локуса внутри хромосомы). Соответственно элементу ait P t выбирается партнер из P t для рекомбинации, если это необходимо (например, для кроссинговера) и строится новая хромосома.

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

Одноточечный кроссинговер выполняется следующим образом:

1) Случайный выбор партнера для скрещивания 2) Случайный выбор точки кроссинговера 3) Формирование двух новых индивидуумов 4) Случайный выбор a {a1, a2 }.

Кроссинговер контролирует баланс между дальнейшим использованием уже найденных хороших подобластей пространства и исследованием новых подобластей. Достигается это за счет неразрушения общих блоков внутри хромосом - родителей, сохраняющих “хорошие” паттерны и одновременном исследовании новых областей в результате обмена частями строк (хромосом).

Мутации вносят новизну и предотвращают невосстановимую потерю аллелей в определенных позициях, которые не могут быть восстановлены пространства поиска. Мутация представляет собой случайное изменение части хромосомы, вероятность которого довольно низкая ( Pm 0.001 ). Мутация функционирует следующим образом:

1) Случайный выбор (с некоторой фиксированной вероятностью Pm ) позиций {x1,..., xk } {1,..., l} внутри битовой строки, подверженной мутации;

2) a = (a1,1...a1,x11ax1a1, x1+1...a1, xh 1axha1, xh +1...a1, l ), где axi {0,1} i = 1,..., h выбираются случайным образом.

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

Критерий остановки эволюции t может быть определен произвольным образом (например, получение удовлетворительного решения, достижение определенного числа поколений, количество затраченного времени, низкая скорость сходимости и т. п.).

Несмотря на то, что первые упоминания о ГА появились в 70 - х годах [122], развитие вычислительной техники в последнее время позволило по новому взглянуть на решение некоторых практических задач поиска и оптимизации с использованием данного класса алгоритмов.

Остановимся на некоторых из практических приложений ГА для решения модифицированная архитектура генетического поиска с миграцией и искусственной селекцией для решения задач размещения ЭРЭ. Предложенная схема оптимизации позволяет во многих случаях выходить из локальных оптимумов.

В [76] автором предлагается использовать эволюционные методы для представлены результаты разработки эволюционно-генетических алгоритмов структурного синтеза и проиллюстрирована их эффективность на примерах многостадийных задач синтеза расписаний.

В [9] рассмотрен “гибридный” подход, основанный на использовании эвристических методов и ГА, для синтеза топологии микроэлектронных устройств с нерегулярной структурой и однослойной коммутацией.

Рассмотрено применение ГА для выбора порядка размещения элементов и разводки электрических связей.

Некоторыми исследователями [51, 97, 110, 131] в качестве основного недостатка при разработке программных систем на основе ГА выделяется необходимость в каждом конкретном случае подбирать индивидуальную чувствительность ГА к параметрам задачи оптимизации, что не позволяет его использовать для решения задач различной сложности без перенастройки параметров.

1.6.2. Методология мягких вычислений. Гибридные системы с использованием генетического алгоритма Понятие мягких вычислений (soft computing) впервые было упомянуто в работе Л. Заде (Lotfi A. Zadeh) по анализу мягких (soft) данных в 1981 году.

Мягкие вычисления (МВ) - это сложная компьютерная методология, основанная на нечеткой логике (НЛ), генетических вычислениях, нейрокомпьютинге и вероятностных вычислениях [137]. Составные части не конкурируют, но создают эффект синергизма. Ведущий принцип МВ - это учет неточности, неопределенности, частичной истины и аппроксимации для достижения робастности, низкой цены решения, большего соответствия с реальностью. Четыре составные части мягких вычислений включают в себя:

- нечеткую логику - приближенные вычисления, грануляция информации, вычисление на словах;

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

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

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

Традиционные компьютерные вычисления (hard computing) слишком точные для реального мира. Имеется два класса задач для мягких вычислений:

во-первых, существуют проблемы, для решения которых полная информация не может быть получена и, во-вторых, проблемы, определение которых не достаточно полно.

Каждая из отдельных компонент МВ обладает рядом внутренних проблем, взаимная компенсация которых и создает синергетический эффект. Нейронные сети решают задачи аппроксимации или классификации, причем настройка весов происходит за счет обучения. Но знания распределены по многим связям и результаты работы нейронной сети кажутся пользователю необъяснимыми, то есть необходима экспликация знаний. Системы нечеткого вывода наоборот обладают явными знаниями в виде продукций и позволяют легко построить протокол объяснений. Однако такая ясность достигается долгим и творческим по своей сути предшествующим процессом извлечения знаний и последующей отладкой совокупности правил. Отсутствие возможности извлечения знаний из данных, настройки параметров функций принадлежности в ходе обучения, автоматизированной редукции правил - проблемы систем логического вывода.

Применение ГА требует предварительного исследования проблемы с целью выбора вероятностей модели, формулировки целевая функции. Выбор отдельной компоненты МВ в качестве базовой обычно определяет общую архитектуру гибридной системы (под гибридной системой в данном случае понимается “мягкая” система).

В работах [117, 121, 137] отмечается, что за последние несколько лет наблюдается увеличение числа так называемых гибридных алгоритмов, в которых интегрированы две или более технологии МВ (НЛ, нейронные сети, ГА) для улучшения в целом производительности алгоритмов. В качестве примера можно привести комбинацию систем “ГА+НЛ” [116]:

1. ГА, управляемые НЛ.

Способность НЛ преобразовывать и улучшать эвристические правила позволяет применять ее для управления ресурсами ГА (размер популяции, тип селекции и др.) во время их перехода от режима исследования (глобальный поиск в пространстве решений) к режиму эксплуатации (локализованный поиск в обнаруженных перспективных областях полного пространства решений).

Управление ресурсами ГА дает алгоритму возможность приспосабливаться под конкретную задачу. При этом улучшается эффективность алгоритма.

2. НЛ контроллер, настраиваемый ГА.

Предложены различные методы, использующие такую комбинацию компонент МВ. Эти методы различаются в основном в порядке или выборе настраиваемых компонент НЛ контроллеров (терм-множество, правила и др.):

- ГА используется для модификации функций принадлежности в терммножествах переменных, которые используются нечетким контроллером.

- ГА напрямую настраивает каждое правило, используемое нечетким контроллером.

- ГА настраивает правила и терм-множества.

В работах [117, 121, 137] авторами подчеркивается перспективность использования подобных гибридных систем для решения широкого класса задач, в том числе и для автоматизации процедур проектирования сложных технических объектов, к классу которых можно отнести и конструкции РЭС.

Выводы:

1. В автоматизированном проектировании конструкций РЭС решаются задачи оптимизации ОП, значительное пространство поиска которых не позволяет использовать полный перебор. Для решения таких задач можно использовать ГА, так как он является эффективной процедурой преодоления локальных экстремумов и осуществляет поиск в перспективных областях пространства решений.

2. Совместное использование НС и ГА в форме единой гибридной системы целесообразно в задачах АП РЭС, поскольку компенсация недостатков отдельных компонент методологии МВ расширяет возможности для построения интеллектуальных систем в условиях неполноты экспертной информации.

1.7. Основные выводы проектирования РЭС, показал их недостаточную эффективность при принятии проектных решений и оптимизации ОП. Достаточно большой объем современных научных исследований в рассматриваемой области посвящен вопросам построения ИСАПР, которые способны генерировать решения в условиях неполноты проектной информации, основываясь на знаниях и опыте высококвалифицированных специалистов - экспертов. Структуры подобных САПР включают в себя ЭС. Принимая во внимание специфику проблемной области проектирования конструкций РЭС, можно сделать вывод о необходимости разработки альтернативных методов построения ИСАПР. В основу таких методов могут быть положены результаты исследований в области нового научного направления “мягкие вычисления”, в рамках которого получают свое развитие теории НС и ГА.

Особенности проблемной области оказывают значительное влияние на способ реализации НС и ГА. Учет неполноты системы предпочтений проектировщика при выборе оптимального варианта конструкции РЭС требует наличие интеллектуальных систем, синтезирующих традиционные математические методы многокритериального анализа, методы НС, ЭС и ГА.

Большинство практических задач оптимизации конструкций РЭС характеризуются значительным пространством поиска с большим количеством локальных экстремумов. В связи с этим, проблема построения ГА для решения задач оптимизации конструкций РЭС состоит в повышении его эффективности путем разработки методов адаптации ГА к определенному множеству задач.

Разработке и исследованию НС и ГА, учитывающих особенности рассматриваемой проблемной области, посвящены следующие главы диссертационной работы.

ГЛАВА 2. АВТОМАТИЗАЦИЯ ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ

ПРИ ПРОЕКТИРОВАНИИ КОНСТРУКЦИЙ РЭС В УСЛОВИЯХ

НЕЧЕТКОСТИ ЭКСПЕРТНОЙ ИНФОРМАЦИИ

В сложных системах и процессах адекватное математическое описание принятия решений (ПР) часто отсутствует или представляет собой достаточно громоздкие математические конструкции, оптимизация которых и практическое использование является затруднительным. Одно из решений данной проблемы может быть связано с построением алгоритма ПР на основе моделей, имитирующих данный процесс опытным экспертом.

В начале главы описывается постановка задачи принятия решений при векторном критерии. Такая ситуация часто имеет место при проектировании неопределенности”, предлагается использовать элементы теории нечетких множеств и ЭС для формализации процесса ПР с учетом качественной информации, представленной в лингвистической форме и исходящей от эксперта. Генерацию решений и оптимизацию предлагается осуществлять с применением ГА и нечетких ЭС. Для решения задач многокритериального анализа в интеллектуальной СППР (ИСППР) РЭС предлагается использовать модифицированный МАИ Т. Саати.

2.1. Формальное представление задачи принятия решений в САПР итеративный процесс взаимодействия проектировщика и компьютера.

В общем случае задачу ПР можно представить в виде следующей семерки [35]:

где t - постановка задачи (например, линейное упорядочение всех альтернатив, неупорядоченного подмножества лучших альтернатив и др.); X - множество допустимых альтернатив (непрерывное или дискретное); R - множество критериев оценки степени достижения поставленной цели (одно- или многоэлементное множество); - множество шкал критериев (шкалы отношений, наименований, порядковые шкалы и т.д.); F - отображение множества допустимых альтернатив X в множество R их критериальных оценок; G - система предпочтений решающего элемента; p - решающее правило.

Рис. 2.1. Отображение пространства альтернатив в пространство их критериальных оценок в условиях неопределенности Будем рассматривать задачу ПР, где отображение пространства альтернатив неопределенности (рис. 2.1). Такой тип задач ПР имеет место во многих процедурах выбора наиболее предпочтительного технического решения из ряда альтернативных решений в области проектирования конструкций РЭС.

Если ОП имеет фиксированную структуру, то есть определены количество, перечень составных частей для выполнения требуемых функций и отношения между ними, то множество альтернатив можно представить в следующем виде:

где yi - значение i - го параметра, n - количество параметров альтернативы.

При этом будем различать два типа множества Y : дискретное ограниченное множество и непрерывное множество альтернатив ОП.

Процессы принятия решений в условиях неопределенности в зависимости от типа неопределенности подразделяют на:

- конфликтные, в которых неопределенность создается за счет недостаточного знания поведения субъекта проектирования (или ЛПР);

- принятия решений в условиях неизвестного состояния объективной недостаточной изученности всех обстоятельств в условиях которых приходится принимать решения.

Для одного и того же ОП количество параметров при его анализе может быть различным и зависит от выбранного уровня абстракции. Любой ОП можно представить как иерархию подсистем и выбор необходимого уровня проектирования РЭС уровни иерархии регламентированы стандартами, и подразделяются на элементы, ячейки, блоки, стойки и так далее, упрощая проблему структуризации данных и знаний для принятия решения.

альтернатив Y, учитывая различного рода ограничения, и записывается в следующем виде:

где ai xi bi, i = 1, n - параметрические ограничения, cl f l ( x ) dl, l = 1, L - функциональные ограничения, q j ( x ) rj, j = 1, m - критериальные ограничения.

Качество решения x оценивается m скалярными критериями R1,..., R j,..., Rm, оценки решения по которым образуют вектор эффективности r = ( r1,..., rj,..., rm ).

Последний связан с альтернативой x функциональным отображением F: X R, которое для задачи выбора в условиях неопределенности задается эвристически (на основе экспертных оценок и суждений).

Решение задачи многокритериального выбора заключается в нахождении оптимального решения x*, которое принадлежит множеству допустимых альтернатив X и является наилучшим:

где opt - оператор оптимизации вектора r = F ( x ).

Выбор применяемого в задаче многокритериального выбора принципа оптимальности осуществляется на основе анализа характеристик решаемой задачи и системы предпочтений проектировщика G.

Если анализ полученного решения показал, что ОП невозможно выполнить в заданном конструктивном базисе или цели процесса ПР не были достигнуты, то в этом случае необходим возврат к генерации множества допустимых альтернатив, либо к пересмотру системы предпочтений проектировщика. Если ни тот ни другой вариант не приводят к допустимому решению, то можно сделать вывод или о невозможности нахождения оптимального решения в указанных ограничениях или о неэффективном способе реализации ИСППР.

Таким образом задача ПР состоит из двух основных подзадач: генерация допустимого множества альтернатив и многокритериальный анализ.

Вывод:

Решение задачи ПР будем представлять в виде этапов выделения допустимого множества альтернатив [см. формулы (2.2) и (2.3)] из исходного множества вариантов ОП [см. формулу (2.1)] и определения оптимального варианта ОП [см. формулу (2.4)], учитывая систему предпочтений проектировщика.

2.2. Процесс принятия решений в САПР РЭС с использованием экспертных систем и генетических алгоритмов Процесс принятия решений можно представить в виде кортежа следующего вида:

где G - генерация допустимого множества альтернатив, среди которых выбирается оптимальный вариант ОП, O - выбор оптимального варианта.

При генерации допустимого множества альтернатив X, определяемого по формулам (2.2), (2.3) принципиальным моментом является вид исходного множества альтернативных вариантов Y [см. формулу (2.1)], вследствие чего будем различать два способа формирования множества X :

1. Определение допустимого множества альтернатив производится на основе усечения множества Y (задача анализа вариантов ОП).

2. Генерация допустимого множества альтернатив осуществляется путем синтеза вариантов ОП предпочтений Компонента многокритериального анализа Компонентами ИСППР проектировщика РЭС, обобщенная структура которой представлена на рис. 2.2, являются [67]: нечеткая ЭС, решающая задачу формирования допустимого множества вариантов ОП в случае, когда возможно осуществить полный перебор; ГА, способный осуществлять генерацию модифицированный МАИ для решения задачи многокритериального анализа учитывающий нечеткий характер системы предпочтений проектировщика и подчинение различных групп критериев различным стратегиям агрегации.

Способность ГА воплощать в себе принципы как детерминированных, так и стохастических подходов к процессу оптимизации, позволяет использовать данный класс алгоритмов для решения задачи генерации вариантов ОП.

Свойство детерминированности проявляется в определении направленности эволюции, используя целевую функцию ГА. Свойство стохастичности таким алгоритмам придают операторы рекомбинации, имеющие вероятностный характер действия. Таким образом, при одних и тех же исходных данных ГА иллюстрируется способность ГА генерировать множество вариантов ОП.

Рис. 2.3 Представление ГА как генератора вариантов ОП Сгенерированное множество вариантов ОП (рис. 2.3) является допустимым множеством альтернатив в смысле формулы (2.3) с учетом того, что ряд ограничений носят размытый характер, поскольку содержат элементы системы предпочтений проектировщика.

Будем выделять три аспекта системы предпочтений проектировщика РЭС, которые оказывают влияние на процесс ПР:

где - аспект, выражающийся в виде простых решающих правил, связывающих условия и ограничения с параметрами ОП (находит свое отражение в БЗ нечеткой ЭС); S ( 2 ) - аспект, выражающийся в целевой функции многокритериальном анализе.

Применение компоненты многокритериального анализа необходимо вследствие невозможности учета большого числа критериев как при формализации ПР с использованием нечеткой ЭС, так и при использовании ГА [68]. В случае ЭС данная проблема связана с доминированием символьных методов формализации знаний, а для ГА особенно важным является возможность построения быстро вычислимой целевой функции, содержащей, как правило, только два или три самых важных критерия с точки зрения интенциональности процесса оптимизации.

Далее в главе рассматриваются проблемы построения нечеткой ЭС и модификации МАИ для АП РЭС. Метод адаптации стандартного ГА к задачам оптимизации рассматривается в третьей главе данной диссертации.

2.3. Подход к неполноте проектной информации с точки зрения принципа “конструктивной неопределенности” информация, необходимая для принятия решения, очень часто является неполной, неколичественной, а формальные модели исследуемой системы либо слишком сложны, либо отсутствуют. Для решения подобных задач обычно привлекают знания экспертов. Удобным инструментом для представления таких знаний являются нечеткие множества [46].

Теория нечетких множеств и основанная на ней нечеткая логика позволяют описывать расплывчатые категории, представления и знания, оперировать ими и делать соответствующие заключения и выводы. Наличие таких возможностей для формирования моделей ОП, процессов и явлений на качественном, понятийном уровне определяет интерес к организации систем проектирования на основе применения методов нечеткой логики.