Содержание к диссертации
Введение
ГЛАВА 1 Анализ состояния вопроса и задачи Проектирования автоматизированных Технологических систем 18
1.1. Обзор существующих систем проектирования 18
1.2. Особенности проектирования сложных тс 30
1.3. Модели функционирования объектов проектирования 36
1.4. Системный анализ атк как объекта Проектирования 43
1.5. Постановка задачи разработки методов автоматизированного проектирования сложных тс 47
1.6. Анализ тп получения оптического волокна как объекта оптимизации 52
1.7. Выводы 56
Глава 2 разработка и исследование методов принятия Оптимальных проектных решений 58
2.1. Метод последовательного анализа Вариантов 69
2.2. Алгоритмы последовательного анализа Вариантов 72
2.3. Оптимизация алгоритмов последовательного Анализа вариантов 74
2.3.1. Метод многошаговой редукции Размерности 74
2.3.2. Методы глобального поиска с Использованием равномерной и неравномерной Сетки 76
2.3.3. Метод глобального поиска с использованием кривой пеано 79
2.3.4. Метод оптимального покрытия прямоугольного параллелепипеда равными кубами 84
2.3.5. Метод многомерного поиска с помощью стохастического автомата 86
2.3.6. Метод многомерного поиска с помощью коллектива независимых автоматов 89
2.4. Поиск локального экстремума Многопараметрических функций 93
2.5. Тестирование алгоритмов последовательного Анализа вариантов 98
2.6. Выводы 108
Глава 3 разработка иерархической структуры принятия Проектных решений 110
3.1. Особенности структур иерархических систем Принятия решений 110
3.2. Оптимизация иерархических систем 117
3.3. Разработка модели для последовательного Принятия решений с иерархической структурой 119
3.4. Выбор и принятие решений на основе теории Байеса 123
3.5. Организация поиска решений по бинарным Деревьям 129
3.6. Выводы 136
Глава 4 разработка программной системы и реализация Разработанных алгоритмов и методов при Проектировании сложных тс 138
4.1. Ранжирование методов оптимизации 141
4.2. Реализация алгоритма накопления информации о проектируемом объекте 143
4.3. Реализация подсистемы расчета чувствительности параметров 146
4.4. Алгоритм обработки информации 147
4.5. Подсистема построения близкого к оптимальному дерева бинарного поиска 149
4.6. Апробация системы оптимального выбора и Принятия решений на тп оптического Производства 155
Выводы 159
Заключение 161
Литература 163
- Постановка задачи разработки методов автоматизированного проектирования сложных тс
- Методы глобального поиска с Использованием равномерной и неравномерной Сетки
- Разработка модели для последовательного Принятия решений с иерархической структурой
- Реализация алгоритма накопления информации о проектируемом объекте
Введение к работе
Оптическая промышленность, как и другие виды производств в настоящее время переживает процесс трансформаций из плановой экономики в отрасль рыночной экономики [1,2]. Так как развитие оптической промышленности напрямую зависит от стоимости различных потребляемых ресурсов: сырьевых, топливно-энергетических, трудовых, то в наше время чтобы выжить необходимо учитывать и рационально использовать эти ресурсы.
Так как современная оптическая промышленность в значительной мере определяет развитие почти всех отраслей народного хозяйстза, таких как: космическая, электронная, медицинская и т.д.. и по сути своей является стратегической, то необходима ее поддержка как со стороны государства, так и со стороны самих предприятий. Из-за скудных капиталовложений предприятиям оптической промышленности приходится развивать отрасль ориентируясь все чаще на зарубежный опыт, а производство ориентировать на рынок оптических изделий, куда не так-то легко пробиться.
В условиях современного рынка от технологических систем оптического производства требуется обеспечение высокого качества готовой продукции при низкой себестоимости. Для этого необходимо: повышать качество исходного сырья, шихты, тепловую и технологическую эффективность оборудования; механизировать и автоматизировать максимальное число стадий технологического процесса, тем самым снижая себестоимость. Таким образом, без внедрения совершенно новых технологий, основанных на использовании современного математического аппарата, вычислительных экспериментов, средств искусственного і интеллекта и комплексной автоматизации процесса производства,
невозможно продвижения вперёд не только оптической, но и других отраслей народного хозяйства.
Переход экономики к рыночным отношениям и усиление концепции вертикальных рынков ставит перед отечественными предприятиями,, оптической промышленности принципиально новые, несвойственные прежним плановым способам ведения хозяйства, задачи. Одной из главных задач является повышение эффективности производства, и, в следствии этого, усиление позиции предприятия во внутреннем, так и во внешнем секторах рынка [3]. Для этого необходимо широкое внедрение автоматизированных систем управления (АСУ), которое может осуществляться двумя путями [4].
1. Попытка постепенного внедрения систем автоматизации лишь на отдельных участках своей деятельности, а затем в будущем, построение на их основе единой СУ, либо довольствование полученной "кусочной" автоматизацией.
2. Комплексное внедрение систем автоматизации, которое позволяет охватить все звенья системы менеджмента от производства до верхнего управленческого уровня и включает в себя:
• автоматизацию общехозяйственной деятельности предприятия (бухгалтерский учет, сбыт/снабжение и т.п.);
• автоматизацию основных технологических процессов предприятия;
• автоматизацию управленческих процессов, анализ и стратегическое планирование.
Второй путь хотя и характеризуется большими капиталовложениями, но эффективность такой системы неизмеримо больше, чем от постепенной автоматизации.
Построение комплексных СУ включает в себя следующие этапы:
• стратегический бизнес-анализ существующей СУ и разработка ее оптимальной модели;
• выбор программных и аппаратных компонентов информационной системы и проработка различных вариантов решения;
• проектирование, внедрение и последующее сопровождение системы (CALS- технологии).
Современные действующие системы автоматизированного проектирования технологических процессов (САПР ТП) и гибкие производственные системы (ГПС) позволяют быстро перестраиваться на новые соотношения сырьевых ресурсов, производить переналадку оборудования с автоматизированных рабочих мест (АРМ) [5].
Возрастающий в последние годы поток информации привел к необходимости существенного изменения подходов к решению задачи его обработки с целью повышения эффективности научных исследований и использования их результатов для решения одной из основных задач - максимальной автоматизации научных и производственных процессов [6,7]. Применение ЭВМ в технике автоматизации приводит в частности к изменению требований к уровню знаний и умений квалифицированных рабочих [8].
Интеллектуализация ранних стадий проектирования состоит в привлечении сложных форм знаний и в применении адекватного аппарата их обработки и использования. Это служит основой подхода для создания САПР, состоящего не в последовательном наращивании возможностей путем подключения дополнительных программных модулей и создания требуемых баз данных (БД) а в радикальном перераспределении вычислительных работ и концентрации исследовательских, поисковых задач проектирования в экспертной системе, которая может рассматриваться как особая комплексная подсистема со своей информационной базой и программным обеспечением общего и специального назначения [9].
В настоящее время необходимо, чтобы подход к процессу проектирования был системным, т.е. имел следующие отличия от традиционного [10]:
• необходимость совместного проектирования и планирования производства изделия и вспомогательных устройств;
• анализ изменения потребностей, последствий от внедрения, предопределяющих развитие систем;
• единый критерий эффективности, характеризующий качество проектируемой системы, в то время как все остальные критерии должны носить вспомогательный характер;
• критерий эффективности должен быть составлен таким образом, чтобы учитывать затраты и доходы на этапах проектирования, организации производства, производства, распространения и эксплуатации системы;
• использование в процессе проектирования и планирования имитационных моделей, достаточно полно отображающих
• функционирование проектируемой системы в условиях, близких к реальным, и предусматривающих работу в интерактивном режиме с человеком-проектировщиком;
• создание банков данных, позволяющих оперативно применять всю информацию о существующих инженерных решениях, которые необходимы для успешного проектирования и планирования с высокой эффективностью;
• широкое применение вычислительной техники, заменяющей в ряде случаев интеллектуальную деятельность проектировщика;
• организация дружественного общения проектировщика с вычислительной техникой с помощью лингвистического обеспечения.
Таким образом, в отличие от традиционного подхода к решению задач проектирования и планирования, системный подход предусматривает более широкое рассмотрение проблемы принятия решений, отличающееся тщательным обоснованием целей, что определяет более высокий уровень проектирования.
Все системы проектирования многокритериальные по своему существу, следовательно, основная проблема, встающая перед проектировщиком - улучшение одних показателей системы, при которых не ухудшаются остальные [11]. А если учесть, что представление готового оптимального проекта необходимо обеспечить в предельно сжатые сроки, то возникает необходимость в построении и обработке допустимого множества вариантов, которые удовлетворяют всем требованиям, предъявляемым к будущей системе. В этом множестве имеется подмножество не улучшаемых или парето-оптимальных вариантов системы, т.е. таких, которые нельзя одновременно улучшить по всем оптимизируемым критериям качества не ухудшив при этом значения хотя бы одного из этих показателей. В результате проектирования на выходе должна получиться парето-оптимальная система. Этого можно достичь только применением группы методов многокритериальной оптимизации и грамотной постановкой задачи проектирования сложных технологических систем (ТС) [12].
Сложная ТС должна быть адаптивной или способной к целенаправленному приспосабливающемуся поведению в сложных условиях окружающей среды, изменения которой выводят проектируемую систему за границы исходной области устойчивости [10]. В начальных стадиях внедрения вычислительной техники в инженерную практику цифровые ЭВМ выполняли сложные числовые расчеты, облегчающие решение задач математической физики. Вторым направлением использования ЭВМ было накопление и систематизация фактических данных. Затем вычислительная техника стала способна к моделированию множества физических, технических и логических задач. К задачам, которые требуют больших вычислительных мощностей относятся задачи конструирования, которые располагаются по сложности между задачами сложного инженерного расчета и задачами искусства. Процесс конструирования содержит два составляющих элемента: строго логический и интуитивный. Для современной вычислительной техники все задачи, сформулированные в виде построений математической логики и представленных в виде алгоритмов, могут быть решены на ЭВМ с большим успехом, чем это делает человек. Для этого потребуется лишь определенный уровень комплектующих ЭВМ устройств -памяти, процессора и т.п. Принципиальные трудности возникают при решении задач, которые связаны с эмоциональным восприятием и оценкой воздействия среды на субъект.
Управление ТП в настоящее время переходит от автоматизированного к автоматическому, которое включает в себя комплекс технических средств по сбору, обработке информации, принятию и реализации решений по управлению объектом, без участия человека [13].
Основными целями автоматизации проектирования являются улучшение качества и повышение технико-экономического уровня проектируемых изделий в т.ч. при их изготовлении, эксплуатации; рост производительности труда; сокращение затрат на создание изделий; снижение стоимости и трудоемкости проектирования [14,15]. Использование ЭВМ з процессе проектирования позволяет повысить его эффективность за счет увеличения рассматриваемых альтернатив проектных решений и более детального их анализа с помощью аппарата математического моделирования.
На этапе выбора рациональных вариантов одной из основных проблем является оценка вариантов по многим критериям в условиях существенной неопределенности и отбор вариантов в диалоговом режиме.
Для оказания помощи проектировщику на всех этапах проектирования может служить человеко-машинная система проектирования.
САПР представляет собой организационно-техническую систему, состоящую из комплекса средств автоматизации проектирования органически связанных между собой.
Функциональные подсистемы, входящие в состав интегрированной САПР имеют следующий состав:
• автоматизированная система управления процессом проектирования (АСУПП);
• автоматизированная система проектирования (АСП)
• автоматизированная система конструирования (АСК);
• автоматизированная система технологической подготовки производства (АСТПП);
• автоматизированная система управления технологическими процессами изготовления опытных образцов (АСУТП);
• автоматизированная система комплексных испытаний и отработки изделий (АСКИО).
АКТУАЛЬНОСТЬ. Для ускорения научно-технического прогресса предусматривается внедрение автоматизированных систем (АС) в различные сферы хозяйственной деятельности и в том числе в проектирование, управление оборудованием и технологическими процессами в промышленности. При этом существенную роль играет решение проектно-конструкторских и научно-исследовательских задач с применением современных средств вычислительной техники, что позволяет сократить сроки разработки, повысить производительность оборудования и снизить затраты на производство.
С развитием вычислительной техники развивается и автоматизация всех областей промышленности. От систем автоматизации технологических процессов (САТП) требуется гибкость и оперативность при принятии новых технологических решений. Однако, при всё более возрастающей технологической сложности процессов важна и высокая эффективность работы САТП с сохранением дружественности интерфейса для построения АРМ проектировщиков. Это приводит к противоречию со всё более возрастающими требованиями, предъявляемыми к современным САПР автоматизированных технологических комплексов (АТК): возможность мониторинга и управления в объектах промышленной автоматизации, дружественный объектно-ориентированный интерфейс "человек-машина", сбор, обработка и хранение информации в БД реального времени с возможностью её обмена при межсистемных взаимодействиях и анимации, и, в то же время, соотношение цены с качеством готового продукта. Для обеспечения баланса необходима тщательная проработка САПР АТК на всех этапах жизненного цикла ТС, особенно на начальном этапе её проектирования, так как именно этот этап характеризуется наибольшей сложностью из-за многовариантности и многокритериальности функции эффективности и широкого спектра методов её оптимизации. Для определения эффективности применения методов оптимального проектирования необходима разработка иерархической структуры принятия проектных решений.
В связи с успехами в развитии средств вычислительной техники стал возможен не только первичный процесс обработки данных о ходе технологического процесса, но и моделирование процессов, накопление и анализ результатов на основе систем искусственного интеллекта и т.д. Проведение таких работ вручную либо трудоемко, либо вообще не представляется возможным из-за сложности математического и программного аппарата.
Разработка системы автоматизации проектирования АТК включает в себя следующие этапы: формирование математического аппарата, пригодного для описания данного объекта проектирования, создание группы математических моделей, на основе которых может производиться их выбор для определенного ТП, разработка методов принятия проектно-конструкторских решений, на основе которых создается объект заданного назначения.
Несмотря на то, что технический прогресс идет по пути создания все более сложных алгоритмов и систем проектирования, полностью исключить человека на определенных этапах не представляется возможным, поэтому для достижения наилучших результатов создаются интерактивные системы проектирования, где человеку предоставляется АРМ. Число АРМ определяется уровнем иерархичности определенной ТС и ее сложностью.
Таким образом, разработка и исследование математических методов и алгоритмов оптимизации проектных решений на начальном этапе проектирования АТК как комплекса алгоритмов и технических средств для управления ТП, является актуальной проблемой, решение которой позволит ускорить работу проектировщика при разработке сложных ТС. •
Предметом исследования диссертационной работы
являются математические методы и алгоритмы оптимизации проектных решений, а также методы проектирования АТК.
Цель работы. Основной целью диссертационной работы является исследование и разработка алгоритмов и методов оптимизации -выбора и принятия технических решений на начальном этапе проектирования и имитационное моделирование ТП для апробации и возможности интеграции в САПР АТК.
Для достижения этой цели решались следующие задачи:
• Анализ современных систем автоматизации проектирования АТК с целью декомпозиции основной задачи проектирования.
• Разработка и исследование методов принятия оптимальных проектных решений на начальном этапе проектирования.
• Моделирование работы и тестирование алгоритмов поиска глобального экстремума многопараметрических функций.
• Разработка и исследование алгоритма свертки локальных критериев оптимизации в глобальный и механизма выбора предпочтительного варианта.
• Разработка программной системы принятия оптимальных проектных решений и организация быстрого поиска в базе знаний с выводом основных результатов.
Методы исследования. В методах исследования использовались: математический аппарат теории выбора и принятия решений, бинарных отношений и деревьев; методы оптимального проектирования, последовательного анализа вариантов и методы глобальной оптимизации многопараметрических функций; теория вероятности; теория множеств и теория графов.
Научная новизна. Научная новизна диссертационной работы заключается в следующем: %
1. Разработаны алгоритмы и методы принятия проектных решений, ориентированные на АТК оптического производства.
2. Разработан алгоритм выбора оптимального варианта свертки локальных критериев оптимальности в глобальный.
3. Разработаны и модифицированы алгоритмы поиска глобального оптимума многопараметрических целевых функций проектирования.
4. Разработаны методы оценки точности алгоритмов анализа и принятия проектных решений, учитывая вычислительную сложность и приоритеты использования.
5. Разработана иерархическая структура принятия оптимальных проектных решений для САПР АТК с применением теории Байеса и бинарных деревьев.
Практическая ценность. Разработанные в диссертационной работе методы и алгоритмы использованы для создания пакета прикладных программ (ППП), включённых в состаз САПР АТК. Данная подсистема охватывает начальный этап проектирования и образует АРМ проектировщика. Получены результаты экспериментов с применением широкого диапазона параметров и ряда математических моделей, которые подтвердили эффективность применения разработанной системы.
Основные результаты диссертационной работы внедрены в ВНЦ ГОИ им. СИ. Вавилова, СПб ИЗМИР РАН и в учебный процесс на кафедре "Проектирования компьютерных систем" СПб ГУИТМО.
Публикации. По материалам диссертации опубликовано 9 печатных работ.
Краткое содержание работы.
Во введении к диссертации проведён краткий обзор проблем, стоящих перед современным проектированием сложных технологических систем, а также систем управления ТП, сформулирована цель работы, методы исследования, научная новизна и практическая ценность данной работы. Кратко описана структура диссертационной работы и апробация её материалов.
В первой главе проведен анализ состояния вопроса и задач автоматизации проектирования, рассмотрены существующие методы проектирования и особенности проектирования сложных ТС; сделана постановка задача диссертационной работы.
Во второй главе освещаются вопросы, связанные с разработкой и исследованием методов принятия оптимальных проектных решений на основе алгоритмов последовательного анализа вариантов и оптимизационных методов многомерного поиска. Описана их работа и указаны их теоретические ограничения для практического применения на предварительном этапе проектирования.
В третьей главе произведена разработка иерархической структуры принятия проектных решений и её оптимизация. Разработана процедура формирования базы знаний и поиска информации по бинарным деревьям. Разработаны процедуры и алгоритмы восстановления сбалансированности деревьев после включения и удаления узлов.
Четвертая глава посвящена вопросам программной реализации разработанных алгоритмов и методов в виде системы оптимального выбора и принятия решений с иерархической структурой. Осуществлена оптимизация математической модели (ММ) ТП вытягивания оптического волокна с помощью разработанных методов.
В приложении приведены документы подтверждающие внедрение результатов диссертационной работы на производстве и в учебном процессе.
Апробация работы. Обсуждение и доклады производились на:
? международной конференции "Прикладная оптика - 96", г. Санкт-Петербург, 1996г.;
? научно-технической конференции "Проектирование и технология элементов компьютерных систем", СПбГИТМО (ТУ), 1997г.;
? межвузовском научно-техническом семинаре с международным участием "Автоматизация проектирования, технология элементов и узлов компьютерных систем", апрель 98г., СПбГИТМО (ТУ);
? XXXI научно-технической конференции профессорско-преподавательского состава, 1999г. СПб ГИТМО (ТУ);
? XXXII научно-технической конференции профессорско-преподавательского состава, 2003г. СПб ГИТМО (ТУ).
Эффект от использования результатов данной работы заключается в сокращении затрат и сроков проектирования АТК. Создана иерархическая система принятия решений, реализованная в виде ППП.
Основные положения, выносимые на защиту:
• методология системного анализа проектирования АТК;
• комплекс алгоритмов и методов принятия решений при проектировании АТК;
• методика свертки локальных критериев оптимизации в глобальный и механизм выбора предпочтительного варианта.
• теоретические методы и экспериментальные оценки точности методов оптимизации, а также их ранжирование по предложенным параметрам;
• методика последовательного анализа и выбора вариантов для проектирования АТК;
• принципы построения иерархической структуры принятия оптимальных проектных решений для САПР АТК. Структура и объём диссертации
Диссертация состоит из введения, четырёх глав, заключения, приложений и списка литературы. Материал изложен на 172 страницах машинописного текста с поясняющими рисунками и таблицами.
Постановка задачи разработки методов автоматизированного проектирования сложных тс
Для того, чтобы осуществить постановку задачи разработки и исследования методов оптимального проектирования [41,42] разобьем процесс проектирования на ряд подзадач.
Первое. Как было показано выше при проектировании сложных систем в период их жизненного цикла возникает проблема выбора технического решения [43]. Особенно часто такая задача возникает на предварительном этапе проектирования. Для принятия решений необходимо задать свойства альтернативных вариантов, на основании которых производится их сравнение. У сложных ТС оптического производства необходимо учитывать некоторое множество свойств для каждого альтернативного варианта. Тогда задача выбора окончательного варианта - задача принятия сложного решения. Для решения задачи необходимо задать множество альтернатив А, имеющие определенный вид ограничения (см. главу II) (р, и множество функций цели Фі: где: I - множество индексов, соответствующих совокупности свойств, с учетом которых производится выбор управляющего воздействия на систему, М - число этих свойств. При этом локальные функции цели Фі могут максимизироваться (управляющие или входные воздействия будут доставлять максимум функциям цели Фі) и/или минимизироваться [44]. Задачей принятия оптимального решения будет: или наилучшая альтернатива а є А. Второе. Выделим отдельно методы сравнения альтернатив по множеству функций цели Фі. Введем следующие отношения между альтернативами: слабое предпочтение или "не хуже" ( :), равноценность ( ) и отношение строгого предпочтения ( -), тогда: и ах -а2 при выполнении системы (1.5.3) и когда одно из них строгое.
Отношение слабого предпочтения в (1.5.3) является нелинейной полуупорядоченностью [45], т.е. нельзя считать, что для любых двух альтернатив либо \ Рг либо idPi либо и то и другое. Поэтому не всякая пара альтернатив сравнима по множеству функций цели Фі. Нахождение наилучшей или неулучшаемой альтернативы а на множестве А считается завершенным, если не существует такой О, , что:и хотя бы одно из них было строгим [46]. Найденная альтернатива а является Парето-оптимальной [47]. Существование и поиск неулучшаемых альтернатив связан с наличием оптимума по каждой функции цели Фі в отдельности. Если неулучшаемая альтернатива одна, то она обеспечивает оптимум каждой функции цели и, следовательно, является решением задачи поиска альтернативы а . Если неулучшаемых альтернатив больше одной, то они будут эквивалентными решениями поставленной задачи.
С другой стороны может и не быть такой альтернативы, которая оптимальна для всех функций цели, но быть приемлемой для всего множества Ф, тогда: тіпАФ,(йг) = тіп где Ф, - оптимальное значение і-й функции цели на множестве допустимых альтернатив. Так как наименьшее значение величин АФу {а) не достигается одновременно на одной альтернативе, то возникает необходимость предусмотреть возможность сравнения этих величин между собой, что потребует дополнительных математических процедур. Это достигается с учетом следующего: - необходимо определить количественно характеристики, позволяющие сравнивать друг с другом величины отклонений от оптимальных значений функций цели различной размерности; задать предпочтения на множестве функций цели, с учетом которых принимается решение. - определить оптимальные значения функций цели на предварительном этапе проектирования приводит к необходимости исследования чувствительности функций на изменение каждой переменной. Поэтому оценку чувствительности необходимо будет разработать в виде отдельной процедуры.
Четвертое. Необходимо предусмотреть информационную подсистему хранения и поиска альтернативных вариантов. Так как сложные ТС характеризуются большими мощностями векторов внутренних и внешних параметров, то множество А также многомерно. Следовательно, поиск и работа с альтернативными вариантами должна вестись на АРМ с предоставлением проектировщику необходимой информации о последствиях от принимаемых решений. Так как помимо обработки данных предусматривается их накопление, то разрабатываемая система должна динамично решать проблему размещения, хранения и сортировки данных с созданием иерархической структуры хранения известных вариантов альтернатив.
Пятое. Проектировщик, опираясь на собственный опыт может заранее предсказать результаты некоторых экспериментов на установке. В других случаях такое прогнозирование затруднительно. Необходимо, чтобы разрабатываемая система учитывала априорные оценки и позволяла прогнозировать все возможные последовательности экспериментов с исследованием их реализаций как можно дальше вперед. Таким образом будет образовываться разветвленная сеть решений возрастающая к последним стадиям проектирования. Это множество увеличит временные затраты машинного обсчета вариантов. Поэтому необходимо ввести систему усечения деревьев решения для получения необходимой информации за разумное время. Для этого необходимо воспользоваться теорией последовательного анализа вариантов (см. п.2.1), которая на основе правил отсечения позволяет: во-перзых, решить вопрос о том, когда следует закончить анализ любой из ветвей дерева решений, что позволит исключить целые поддеревья, а, во-вторых, потом определить эквивалентное значение для граничной точки, которое представляло бы величину ожидаемой выгоды от использования оптимальной стратегии на отсеченной части дерева. Перечисленные выше операции взаимосвязаны, поэтому влияние метода последовательного анализа вариантов на принятие решения происходит совместно с байесовой теорией
Методы глобального поиска с Использованием равномерной и неравномерной Сетки
В качестве метода одномерного поиска глобального минимума функции применяются следующие алгоритмы. а) алгоритм, применяющий пассивную стратегию поиска глобального минимума. Он основан на последовательном переборе точек области О., вычислении функции качества и выборе минимального значения на равномерной сетке узлов с шагом 8. Для этого вычисляются значения функции Q(xi), где ТОЧКИ Xi находятся из выражений: Минимальное число шагов, необходимое для отыскания глобального минимума определяется выражением: где ABS[] - целая часть от числа, a L- константа Липшица, вычисляемая для непрерывных функций как максимум первой производной: С практической точки зрения сохранение постоянного шага 8 на всем отрезке 1а,Ь] является нецелесообразным [21,29], т.к.: во-первых, для сложных ТС, работающих в условиях непредсказуемых внешних возмущений, присуще свойство грубости, при котором малым изменениям параметров системы соответствуют небольшие изменения показателей качества ТП; а, во-вторых, параметры объекта обычно известны неточно и в процессе эксплуатации могут меняться в некоторых пределах. Исходя из этого сделаем следующее. б) модифицируем вышеописанный алгоритм так, чтобы осуществлялся перебор на неравномерной сетке. Это реализуется с помощью выражений [21,72]: Данный алгоритм может привести к искомому минимуму за меньшее число шагов, но для его работы необходимо вычисление значения константы Липшица, в отличие от метода перебора по равномерной сетке. в) неравномерную сетку можно строить по другому алгоритму без использования константы Липшица по следующим соотношениям [29]: Є - точность определения глобального минимума. Для данного алгоритма присущи следующие достоинства. Во-первых, алгоритм исключает вероятность зацикливания у нулевой точки области допустимого изменения і-го параметра, а, во-вторых, участки с малыми абсолютными значениями ХІ ускоренно проходятся в линейном, а большими - в логарифмическом масштабе. Общее число точек сетки перебора составляет:
Таким образом, описанные выше методы перебора на равномерной и неравномерной сетке узлов являются надежным средством нахождения глобального минимума и наиболее просты в применении, хотя и очень трудоемки по затратам машинных ресурсов. 2.3.3. Метод глобального поиска с использованием кривой Пеано Идея метода состоит в отображении части вещественной оси - отрезка [0,1 J в гиперпараллелепипед Dx [69,73]. Каждая точка этого гиперпараллелепипеда соответствует точке &, принадлежащей отрезку, с помощью которой значение выражения: позволяет отыскать глобальный минимум, используя переход к методу одномерного глобального поиска по схеме:
Для реализации метода выполним последовательно следующие действия. 1. Преобразуем область Dx таким образом, чтобы отрезок [а,Ь] проецировался на отрезок [0,1]. Линейное преобразование координат осуществляется по формуле: где N - количество испытаний в Dx. Для отыскания коэффициентов составим систему уравнений, приравняв значение X сначала левому, а затем правому концу отрезка [0,1]. Решая систему, находим значения коэффициентов: Подставив полученные значения коэффициентов в (2.3.3.2), получим линейное преобразование координат для отрезка [0;1]: 9 =J i= N a b- (2.3.3.4) 2. Полученный гиперкуб с длиной ребра, равной 1 разделим координатными плоскостями на 2N гиперкубов первого разбиения с длиной ребра 1 /2, которые нумеруются числами Z. от 1 до N, а гиперкубы обозначаются D(z,). Затем каждый гиперкуб также делится на 2N гиперкубов второго разбиения с длиной ребра 1 /4 гиперплоскостями, параллельными координатным и проходящими через середины ребер гиперкуба, ортогональных к этим гиперплоскостям. Гиперкубы второго разбиения нумеруются числами z2, а гиперкубы обозначаются D(Z},ZJ) . Количество таких разбиений обозначим через т. 3. Разделим отрезок [0,1] на 2N частей, каждую из которых разобьем на 2N частей, и так m раз. Полученные отрезки также занумеруем слева направо от 1 до 2N. Таким образом получим интервалы d(Zj,...,zm) с длиной (1/2) 4. Сопоставим точку Y («9), где Э принадлежит отрезку [0,1], соответствующему гиперкубу т-го разбиения D(z.,...,z ). При любом т 1 такое сопоставление будет однозначным. 5. Для любого $, принадлежащего d(z1,...,zm), можно записать: Ы где (Хг двоичные коэффициенты, принимающие значения {0,1}. По этому числу отыскивается гиперкуб m-го разбиения, содержащий точку Y (#) с точностью не хуже, чем: 6. Добьемся того, чтобы построение отображения было непрерывно. Для этого достаточно ввести строгую нумерацию при которой гиперкубы при любом количестве разбиений имели не более двух смежных гиперкубов, и при которой смежные гиперкубы имеют не более одной общей грани. 7. Для выполнения п.6 вводится дополнительный гиперкуб А, который делится координатными плоскостями на 2N частей. Номером такого гиперкуба будет число s, а центром U(s) гиперкуба A(s) будет точка, удовлетворяющая: Для того, чтобы гиперкубы A(s) и A(s+1) имели общую грань, необходимо и достаточно существование номера j, чтобы: j=j(s),l j N, т.е центры этих гиперкубов должны отличаться только одной координатой. 8. Устанавливаются свойства, для введенных дополнительных гиперкубов A(s):
Разработка модели для последовательного Принятия решений с иерархической структурой
Как было показано в п.2.1 настоящей диссертационной работы, уровни процесса проектирования удобно выстроить исходя из двух процессов: генерации вариантов с заданной глубиной детализации и последующего выбора наилучших вариантов. На следующем подуровне отобранные варианты становятся исходными для новой их проработки и новой селекции. Такой способ проектирования сложных систем можно представить иерархической моделью, в которой каждый уровень характеризуется определенной детализацией всей системы, а переход от одного уровня к другому осуществляется с помощью операции, отображающей направление движения в модели, и связанной с увеличением информации о данном подмножестве вариантов [97]. Каждую такую операцию характеризуют: затратами временных или вычислительных ресурсов, необходимых для ее выполнения; вероятностными затратами на последующую детализацию низлежащих уровней ТС.
Таким образом, весь процесс проектирования представляется в виде некоторой последовательности операций на иерархической модели или дереве решений при условии минимизации временных затрат [39,98]. Где переход от одной І-й стадии проектирования к другой (i+1) описывается с помощью оператора, включающего множество вычислительных процедур, и осуществляющего: поиск новой операции из подмножества, образованного (і+0-м уровнем; выбор путем сравнения новой операции с ранее образованной альтернативной операцией и установление относительной ценности операции с процедурой принятия решения.
Выбор новой (i+D-й операции ведется путем сравнения затрат, связанных с проектированием на последующих стадиях, включая стоимость текущей і-й операции при выборе из множества альтернативных операций на данной і-й стадии проектирования. В ходе такого выбора может оказаться, что после выполнения некоторой операции произойдет изменение стоимости, оценивающей затраты на выполнение операции, так как изменится представление о характеристиках сложной системы или может выявиться новая операция. Поэтому необходима "переоценка ценностей" всех последующих операций на (n-i)-x стадиях после прохождения і-го уровня. Возможные пути решений отображаются в виде дерева решений, а процедуры генерации новых вариантов решений и вычисление оценочных функций вариантов осуществляется на АРМ. Причем лицу, принимающему решения приходится не только выбирать оператор, но и то, к какой операции он должен быть применен, чтобы породить новую операцию - новую вершину в дереве процесса проектирования.
В операциях, рассмотренных выше, все действия: поиск и отбор производятся на разных уровнях, однако, как показано в п.3.1, операции могут вестись и на одном уровне, т.е. с вариантами, определяемыми той же степенью детализации и точности. Такой оператор назовем одноуровневым оператором.
Из вышесказанного вытекают следующие проблемы при построении иерархических моделей сложных систем: а) построение иерархии процессов проектирования в зависимости от особенностей задачи и объема априорной информации; б) разработка лингвистического обеспечения, соответствующего различным уровням проработки отдельных подсистем; в) формализация методов целенаправленного выбора вариантов; г) исследование потенциала симбиоза человек-машина для быстрого перебора вариантов с элементом эвристики со стороны ф человека.
Для построения иерархической системы принятия решений строится процедура, имеющая следующие основные.-черты: основной выбор в системе производится между комбинациями, состоящими из оператора и операции, к которой этот оператор должен быть применен. Такие комбинации составляют эксперимент; только те множества вариантов, которые удовлетворяют множеству ограничений Q(Y) являются потенциальными решениями. Следовательно, практическая ценность других
Реализация алгоритма накопления информации о проектируемом объекте
Ранжированные по оптимальному выполнению условий, ец -результат решения или полезность решения. Такой матрицей удобно пользоваться при принятии решений в условиях неопределенности 111 3]. Для того, чтобы прийти к однозначному решению, проектировщик формирует целевую функцию Ф с ограничениями и матрица (4.8.1) преобразуется в матрицу-столбец в которой варианту Ej будет соответствовать единственный результат eij, характеризующий все последствия этого решения. При этом предполагается, что ситуация, в которой принимается решение, характеризуется тем что: - вероятности появления состояния Fi известны и не зависят от времени; - решение (теоретически) реализуется бесконечное число раз; - для малого числа реализаций решения допускается определенный риск. Поэтому эту подсистему удобно подключать после того, как система проработала достаточно большое число комбинаций эксперимент-результат-операция-состояние. Для процесса принятия решений схема функционирования может содержать следующие блоки: рис.27, и представляет собой интерактивную систему, в которой генерация вариантов для предварительной обработки эксперимента осуществляется как человеком-оператором, так и самой системой. Алгоритм К включения узла Z в дерево Т строится аналогично алгоритму поиска SR, который изображен на рис. 28. Если новый узел Z еще не содержится в дереве, то алгоритм связывает Z с последним узлом, пройденным во время безуспешного поиска Z. Для стыковки данного алгоритма с алгоритмом $И, необходимо производить процедуру до предложений p=Left(p) или p=Right(p). В результате работы, процедуры, программе возвращается указатель на поддерево, в которое добавлен узел Z. щ Алгоритм исключения имени Z (3) осуществляется сложнее: если узел Z находится на самом низком уровне дерева, то он удаляется; если удаляемое имя Z имеет одно подчиненное ему имя X, то при исключении Z производится сдвиг X на один уровень ближе к корню; если имя Z имеет два разветвления на подчиненные ему имена X и у, тогда находится либо имя z\ которое непосредственно предшествует Z, либо Z , следующее за Z. Так как Z и Z принадлежат узлам, имеющим в подчинении не более одного узла [102], то Z исключается заменой либо Z , либо z", а затем исключается узел, который содержал Z или Z соответственно. Рис. 28. Процедура включения новых узлов Z в дерево бинарного поиска.
Как было описано выше, во время прохождения алгоритма включения новых узлов К, необходимо обеспечить заполнение стека по мере движения по дереву Т. Тогда появляется возможность пройти это дерево в обратном порядке: снизу вверх, и при этом проверить узлы на флаги высотности. Балансировку дерева поиска осуществим по следующей процедуре (рис. 29). Здесь вращение и двойное вращение осуществляется по направлению,,, соответствующему ориентации подветвей дерева бинарного поиска. Изображенный на рисунке алгоритм является обобщенным, так как для его практической реализации необходимо ввести еще несколько флагов, такие как: флаг ориентации текущего поддерева (левое, правое), флаг направленности движения и флаг веса поддерева из текущего узла.
После удаления узлов из дерева поиска также нарушается сбалансированность. Дерево теряет одну единицу высоты какой-либо из ветвей. Устраним разбалансированность применением процедуры, позволяющей отслеживать не весь путь до корня, а лишь некоторый участок кроны дерева. Время работы ее не зависит от высоты дерева. Приведенный на рис. 30 алгоритм применим после удаления вершины z из дерева Т, процедура которого была описана выше
В настоящей диссертационной работе получены следующие основные результаты: 1. Разработана модификация алгоритма последовательного анализа вариантов ддя интегрированной системы автоматизированного производства оптических материалов. 2. Разработаны алгоритмы, реализованные на языке высокого уровня, для методов принятия решений на предварительном этапе проектирования. Алгоритмы оптимизированы для достижения лучшей эффективности при сниженных требованиях к ресурсам ЭВМ. « 3. Предложена система ранжирования методов оптимизации перед их использованием в составе САПР оптических материалов. Ранжирование произведено на основе испытания методов на тестовых задачах оптимизации с расстановкой приоритетов методов. 4. Разработана методика хранения и обработки информации с использованием аппарата бинарного отношения эффективности. Организован поиск информации по бинарным деревьям с возможностью восстановления сбалансированности их по высоте после добавления/удаления вершин.
