Содержание к диссертации
Введение
1. Направления повышения эффективности процессов принятия решений при проектировании сложных объектов в САПР 19
1.1. Интеграция процедур многовариантного моделирования и оптималь ного выбора при автоматизированном проектировании 20
1.2 Особенности алгоритмизации задач оптимального проектирования при неполноте их априорного математического описания 30
1.3. Принципы формирования адаптивной многометодной среды оптимального проектирования сложных систем 40
1.4. Цель и задачи исследования 52
2. Алгоритмизация задач оптимального проектирования сложных систем на основе адаптивного подхода 55
2.1. Формирование адаптивных рандомизированных алгоритмов поискового типа при оптимизации параметров сложных систем 56
2.2. Повышение эффективности процесса параметрического синтеза на основе трансформации оптимизационных моделей 78
2.3. Алгоритмизация задач структурного синтеза с использованием гибридных вероятностно-детерминированных процедур дискретной оптимизации 92
2.4. Основные выводы главы 103
3. Декомпозиционно-агрегативные схемы преобразования и типизации оптимизационных моделей при поиске наилучших вариантов систем 106
3.1. Декомпозиционный подход к проектированию сложных систем с иерархической структурой 107
3.2. Адаптивные процедуры агрегирования показателей качества в много критериальных оптимизационных моделях 117
3.3. Декомпозиция локальных задач оптимального выбора на основе редукции варьируемых параметров и ограничений 135
3.4. Основные выводы главы 145
4. Формирование многометодной среды оптимального проектирования на основе компонентно-модульного подхода и интеллектуализации синтеза алгоритмических схем 147
4.1. Разработка компонентной структуры алгоритмической базы оптималь ного проектирования 148
4.1.1. Построение инвариантного ядра библиотеки модулей на основе структуризации оптимизационных процедур 151
4.1.2. Формирование проблемно-ориентированных внешних модулей 166
4.2. Формализация задачи автоматизированного синтеза алгоритмических схем при оптимальном проектировании 167
4.3. Организация процедур интеллектуальной поддержки комплексирова-ния структурных элементов алгоритмического обеспечения 176
4.4. Основные выводы главы 190
5. Организация интегрированных оптимизационно-имитационных процедур параметрического и структурного синтеза сложных систем 192
5.1. Схемы интеграции процедур имитационного моделирования и рационального выбора вариантов при оптимальном проектировании сложных систем 193
5.2. Формирование комплексной модели производственной системы
на основе интеграции CASE - технологий и имитационных процедур 201
5.3. Решение задач оптимального проектирования производственных
систем с использованием оптимизационно-имитационного подхода 209
5.3.1. Структурный синтез производственной системы 213
5.3.2. Параметрическая оптимизация производственной системы 226
5.4. Основные выводы главы 244
6. Разработка программного комплекса поддержки принятия проектных решений и его апробация в условиях производства 233
6.1. Структура и характеристики программного комплекса 233
6.2. Использование разработанного программного обеспечения для
моделирования и оптимизации производственной системы
изготовления телевизионной техники 244
6.3. Интеграция подсистемы поддержки принятия решений с копрора-
тивной информационной системой предприятия 259
6.4. Основные выводы главы 263
Заключение 266
Список литературы
- Интеграция процедур многовариантного моделирования и оптималь ного выбора при автоматизированном проектировании
- Формирование адаптивных рандомизированных алгоритмов поискового типа при оптимизации параметров сложных систем
- Декомпозиционный подход к проектированию сложных систем с иерархической структурой
- Разработка компонентной структуры алгоритмической базы оптималь ного проектирования
Введение к работе
Актуальность проблемы. Проблемы, связанные с принятием оптимальных решений, занимают важное место в автоматизированном проектировании. Многоаспектность и разнообразие задач оптимизации в САПР, их тесная взаимосвязь с задачами моделирования и анализа требуют совершенствования методов и средств поддержки процессов оптимального проектирования на различных этапах.
Организация процедур поиска оптимальных решений в современных САПР осложняется неполнотой априорного математического описания проектируемых объектов. Данная проблема особенно ярко проявляется при проектировании сложных систем (технических, технологических, информационно-телекоммуникационных, социально-экономических и др.), динамические и стохастические аспекты функционирования которых невозможно учесть на основе аналитического моделирования. Это приводит к необходимости использования при решении таких классов задач алгоритмических оптимизационных моделей, в которых отсутствуют явные аналитические формулировки критериев оптимальности и ограничений, а имеется лишь возможность определения их значений для каждого из вариантов с применением различных моделирующих процедур. Сложность оценки свойств таких моделей на априорном уровне ограничивает возможности использования стандартных алгоритмов оптимизации, применяющихся традиционно в САПР, что в конечном итоге снижает эффективность процесса оптимального проектирования. Кроме того, к особенностям задач структурно-параметрического синтеза сложных систем можно отнести разнообразие постановок, высокую размерность, множественность технико-экономических требований к основным характеристикам, значительную трудоемкость этапов моделирования и анализа, наличие разнообразных корреляционных связей между параметрами, учесть которые в рамках стандартного математического обеспечения САПР становится невозможным. Решение указанной проблемы может быть достигнуто при использовании адаптивного подхода к проектированию сложных объектов. Данный подход предполагает построение комплекса алгоритмов оптимизации, обеспечивающих совмещение процесса более полной формализации задачи с ее решением, и их объединение совместно с процедурами многовариантного моделирования в интеллектуальную адаптивную многометодную среду с возможностью ее динамической настройки на различные классы задач оптимального проектирования.
Таким образом, актуальность диссертационной работы определяется необходимостью создания инвариантной части математического обеспечения САПР для повышения эффективности процессов принятия решений при проектировании сложных объектов в условиях неполноты их априорного описания.
Работа выполнена в соответствии с межвузовской научно-технической программой И.Т.601 "Перспективные информационные технологии в высшей школе", ГБ НИР 91.04 "Моделирование и оптимизация в автоматизированных системах", ГБ НИР 01.04 "Интеллектуализация принятия решений в автоматизированных и информационных системах", грантами Минобразования РФ "Теоретические основы оптимального проектирования слабоформализованных объектов" (№ госрегистрации 01200115180) и "Экспертно-оптимизационное моделирование целенаправленных систем" (№ госрегистрации 01200204147) в рамках одного из основных научных направлений Воронежского государственного технического университета "САПР и системы автоматизации производства".
Цель и задачи исследования. Целью диссертационной работы является создание комплекса методов, моделей и алгоритмов оптимального проектирования сложных объектов в САПР при неполноте априорной информации и формирование на их основе адаптивной поисковой среды принятия проектных решений, интегрированной с процедурами многовариантного моделирования и анализа.
Для достижения поставленной цели необходимо решить следующие основные задачи: провести анализ методов и средств оптимального проектирования сложных объектов в САПР, рассмотреть особенности задач данного класса и определить принципы их алгоритмизации на основе адаптивного подхода;
сформировать комплекс вероятностно-детерминированных алгоритмов параметрического и структурного синтеза сложных объектов при низком уровне их математического описания;
построить процедуры преобразования и типизации оптимизационных моделей в процессе проектирования, обеспечивающие комплексный учет особенностей решаемых задач;
разработать компонентную структуру алгоритмической базы оптимального проектирования с возможностью формирования оптимизационных процедур различных классов посредством комплексирования инвариантных модулей;
создать средства модульного синтеза алгоритмических схем и многоме-тодные стратегии поиска оптимальных проектных решений с использованием априорной и текущей информации;
разработать технологию интегрированного взаимодействия процедур многовариантного моделирования и оптимального выбора при алгоритмизации практических задач оптимального проектирования;
построить программное обеспечение подсистемы поддержки принятия проектных решений на основе интеграции многовариантного моделирования и адаптивной мультикомпонентнои поисковой среды и провести его апробацию в условиях производства.
Методы исследования. При выполнении работы использованы основные положения системного анализа, теории вероятностей и математической статистики, теории графов и комбинаторики, аппарат вычислительной математики, принципы искусственного интеллекта, методы имитационного моделирования, исследования операций и принятия решений.
Научная новизна результатов исследования. В диссертации получены следующие основные результаты, характеризующиеся научной новизной: подход к оптимальному проектированию сложных объектов в САПР, основанный на интеграции в едином цикле многовариантного моделирования и адаптивной среды рационального выбора проектных решений, позволяющий на основе совмещения процесса более полной формализации задачи с поиском наилучших вариантов учесть особенности проектируемого объекта при низком уровне его математического описания;
комплекс адаптивных поисковых алгоритмов параметрической оптимизации сложных систем, сочетающих в ходе оптимизационного процесса исследование свойств задачи с ее решением и отличающихся альтернативными стратегиями реализации отдельных алгоритмических шагов с возможностью построения как стандартных, так и новых поисковых процедур на основе их различных комбинаций;
алгоритмы структурного синтеза, особенностью которых является объединение в общей алгоритмической схеме рандомизированных и детерминированных процедур дискретной оптимизации, позволяющих формировать схемы направленного перебора проектных вариантов при отсутствии аналитических формулировок критериев оптимальности;
декомпозиционно-агрегативные процедуры, ориентированные на работу с алгоритмическими моделями проектируемых объектов и обеспечивающие адаптивное преобразование оптимизационных задач и приведение их к типовым постановкам на основе анализа априорной и текущей информации;
методика формирования мультикомпонентной среды оптимального проектирования, отличающаяся выделением инвариантных структурных составляющих алгоритмического обеспечения и наличием интеллектуальных средств их комплексирования, что позволяет осуществлять модульный синтез различных алгоритмических схем и реализовывать многометодные стратегии поиска в соответствии с особенностями решаемых задач;
иерархические схемы интегрированного взаимодействия процедур многовариантного моделирования и адаптивной среды оптимального выбора при решении практических задач параметрического и структурного синтеза сложных систем, обеспечивающие согласование и координацию проектных решений на различных уровнях иерархии и возможность учета динамических и стохастических аспектов функционирования проектируемых объектов;
структура подсистемы поддержки принятия проектных решений, характеризующаяся разнообразием форм задания оптимизационных моделей, наличием интеллектуальных средств генерации оптимизационных процедур из ин-вариантных модулей и возможностью интегрированного взаимодействия со стандартным программным обеспечением моделирования и анализа.
Практическая значимость и результаты внедрения.
Практическая значимость работы заключается в следующем:
разработаны основы построения инвариантной части математического обеспечения САПР при проектировании сложных объектов различных классов с использованием интегрированной среды многовариантного моделирования и поиска оптимальных проектных решений;
реализованный при разработке алгоритмической базы оптимального проектирования компонентно-модульный подход позволил сформировать библиотеку инвариантных модулей непрерывной и дискретной оптимизации с возможностью построения на их основе новых оптимизационных процедур и приложением в различных предметных областях;
разработано программное обеспечение подсистемы оптимального проектирования, применение которого в рамках САПР позволяет повысить эффективность оптимизационного процесса, улучшить качество принимаемых проектных решений, уменьшить вычислительные и временные затраты для получения оптимального варианта;
предложен комплекс интегрированных оптимизационно-имитационных процедур, позволяющих осуществлять оптимальное проектирование развивающихся производственных систем на различных уровнях иерархии.
Результаты работы внедрены в ОАО "Видеофон" (г. Воронеж), в НИИ электронной техники (г. Воронеж) и на Воронежском заводе полупроводниковых приборов при структурной и параметрической оптимизации производственных систем изготовления телевизионной техники и электронных компонентов РЭС с суммарным годовым экономическим эффектом 647 тыс. руб., а также используются в учебном процессе кафедры "Систем автоматизированного проектирования и информационных систем" Воронежского государственного технического университета и кафедры "Информатика и вычислительная техника" Воронежского института высоких технологий.
Основные программные модули подсистемы оптимального проектирования зарегистрированы в Государственном фонде алгоритмов и программ.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях, семинарах и совещаниях: Всесоюзном совещании-семинаре "Разработка и оптимизация САПР и ГАП изделий электронной техники на базе высокопроизводительных мини- и микро- ЭВМ" (Воронеж, 1989); IX Всесоюзном симпозиуме "Эффективность, качество и надежность систем "Человек-техника"" (Воронеж, 1990); Российской научно-технической конференции "Методы оценки и повышения надежности РЭС" (Пенза, 1991); Всесоюзной школе-семинаре "Разработка и эксплуатация САПР в радиоэлектронике" (Челябинск, 1991); Всесоюзном совещании-семинаре "Интерактивное проектирование технических устройств и автоматизированных систем на персональных ЭВМ" (Воронеж, 1991); Республиканской конференции "Современные проблемы алгоритмизации" (Ташкент, 1991); Российском совещании-семинаре "Оптимальное проектирование технических устройств и автоматизированных систем" (Воронеж, 1992); Межгосударственной научной конференции "Экстремальные задачи и их приложения" (Н. Новгород, 1992); Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, образовании и медицине" (Воронеж, 1994-1997); V, VI, VII, IX, X Международных конференциях "Математика. Моделирование. Экология" (Волгоград, 1996; Ростов-на-Дону, 1997, 2002; Чебоксары, 1998, Воронеж, 2000); Международной научно-технической конференции "Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем" (Пенза, 1998); Всероссийском совещании-семинаре "Интеллектуальные информационные системы" (Воронеж, 1999-2004); Всероссийской научно-технической конференции "Информационные технологии и модели в научных исследованиях, автоматизированном проектировании и производстве" (Тула, 2002); Международной научной конференции "Информационные технологии в естественных, технических и гуманитарных науках" (Таганрог, 2002); Международной научной конференции "Развивающиеся интеллектуальные системы автоматизированного проектирования и управления" (Новочеркасск, 2002); Всероссийской конференции "Интеллектуализация управления в социальных и экономических системах" (Воронеж, 2002-2004); Международной научной конференции "Современные сложные системы управления" (Старый Оскол, 2002); XVI Международной научной конференции "Математические методы в технике и технологиях - ММТТ-16" (Санкт-Петербург, 2003); VII Международной научно-технической конференции "Системный анализ в проектировании и управлении" (Санкт-Петербург, 2003); X Международной конференции "Математика. Компьютер. Образование" (Москва-Ижевск, 2003); Международных конференциях "Системные проблемы качества, математического моделирования, информационных и электронных технологий" и "Системные проблемы надежности, качества, информационных и электронных технологий ИННОВАТИКА-2004" (Москва-Воронеж-Сочи, 2003, 2004); научно-методических семинарах кафедры "Систем автоматизированного проектирования и информационных систем" ВГТУ (1990-2004).
Публикации. По результатам исследований опубликовано 67 печатных работ, в том числе 2 монографии и 14 статей в изданиях, рекомендованных ВАК.
В работах, опубликованных в соавторстве и приведенных в конце автореферата, соискателем предложены: алгоритмические схемы решения слабо 12
формализованных задач непрерывной и дискретной оптимизации [7,9,12,17,28]; библиотека модулей оптимального проектирования [1,3]; многометодные стратегии поиска проектных решений [29,33]; схемы интегрированного взаимодействия оптимизационных и имитационных процедур [10]; структура и программное обеспечение подсистемы оптимального проектирования [22,30,34,41, 46,51,60]; технология формирования функционально-имитационной модели производственной системы [54,56,61]; оптимизационные модели и процедуры параметрического и структурного синтеза производственных систем [11,14,52,55]; подходы к интеграции программных средств поддержки принятия решений с корпоративной информационной системой предприятия [45,48,50,53,58].
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка литературы из 219 наименований и приложений. Основная часть работы изложена на 268 страницах, содержит 58 рисунков и 9 таблиц.
Во введении обоснована актуальность работы, дана ее краткая характеристика, сформулированы цель и задачи исследования, изложены основные научные положения и результаты, выносимые на защиту.
В первой главе рассмотрены взаимосвязи процедур многовариантного моделирования и оптимального выбора при автоматизированном проектировании; проведен анализ особенностей задач оптимального проектирования сложных объектов в САПР; определены основные требования к математическому и программному обеспечению процессов поиска рациональных проектных решений в условиях неполноты априорной информации.
Показано, что особенностью задач оптимального проектирования сложных систем является совместное использование на этапах структурного и параметрического синтеза процедур многовариантного моделирования и рационального выбора проектных решений. С математической точки зрения рассматриваемые задачи можно отнести к классу задач оптимального проектирования, в которых ряд критериев оптимальности и ограничений задан не в явном аналитическом виде, а алгоритмически с помощью моделирующих процедур. Это требует организации специфических итеративных схем оптимального проектирования, основанных на решении последовательности задач моделирования и анализа под управлением процедур генерации и целенаправленного перебора проектных вариантов.
Для комплексного учета особенностей задач оптимального проектирования сложных объектов предлагается использовать адаптивный подход. При этом выделяются два уровня адаптации:
- внутренняя адаптация, которая предполагает построение процедур оптимального выбора, позволяющих сочетать в единой алгоритмической схеме исследование свойств оптимизационной модели с поиском наилучших решений;
- внешняя адаптация, предполагающая модульную организацию алгоритмической базы с возможностью ее настройки на различные классы задач.
В работе ставится задача практической реализации адаптивного подхода на основе построения мультикомпонентной поисковой среды оптимального проектирования. При этом адаптивная поисковая среда определяется как совокупность методов и средств, обеспечивающих в условиях неполноты априорной информации формирование процедур оптимального проектирования различных классов посредством комплексирования инвариантных структурных компонент, и объединяющих вероятностно-детерминированные алгоритмы выбора наилучших вариантов, интеллектуальные процедуры генерации алгоритмических схем и средства управления оптимизационным процессом в единую многометодную технологию принятия рациональных проектных решений.
На основе проведенного анализа определяются цель и задачи работы.
Вторая глава посвящена вопросам алгоритмизации задач параметрического и структурного синтеза сложных объектов в САПР. Алгоритмическую базу предлагается формировать на основе интеграции вероятностных и детерминированных адаптивных процедур непрерывной и дискретной оптимизации. В главе рассматриваются принципы формирования и структурная организация поисковых процедур непрерывной и дискретной оптимизации, построенных с использованием адаптивного подхода. При этом более полная формализация задач оптимального проектирования достигается за счет их эквивалентной рандомизированной переформулировки и погружения в вероятностно-детерминированную среду направленного перебора. Для решения задач оптимального параметрического синтеза сформирован комплекс адаптивных нелокальных алгоритмов поискового типа. Повышение эффективности оптимизационного процесса обеспечивается использованием процедур дополнительной обработки текущей информации, построенных на основе трансформации оптимизационных моделей. Решение задач структурного синтеза осуществляется на основе сочетания рандомизированных процедур псевдобулевой оптимизации и модифицированных вариантов алгоритмической схемы ветвей и границ.
При формировании алгоритмических схем параметрического и структурного синтеза используется подход, основанный на реализации каждого этапа обобщенной процедуры с применением альтернативных взаимозаменяемых стратегий. Такой подход открывает широкие возможности для модульной организации алгоритмической базы и позволяет на основе ограниченного набора модулей посредством их комплексирования формировать как стандартные, так и новые оригинальные алгоритмические процедуры.
В третьей главе представлены декомпозиционно-агрегативные схемы преобразования и типизации оптимизационных моделей при поиске наилучших вариантов объектов проектирования.
При декомпозиции задач оптимального проектирования выделяются два основных этапа. Первый этап (внешняя декомпозиция) осуществляется на системном уровне посредством структуризации объекта проектирования и выделения совокупности локальных оптимизационных задач с возможностью их координации. Второй этап (внутренняя декомпозиция) реализуется на уровне локальных оптимизационных моделей и предполагает решение следующих задач: - агрегирование частных критериев оптимальности и формирование единого обобщенного показателя качества;
- редукция ограничений в скалярной оптимизационной задаче и ее дальнейшее преобразование в задачу безусловной оптимизации;
- сокращение пространства варьируемых параметров в локальной задаче безусловной оптимизации.
Агрегирование критериев оптимальности предлагается осуществлять на основе адаптивных алгоритмических процедур векторной оптимизации, в которых предпочтения ЛПР в ходе оптимального выбора связываются с перестройкой вероятностей привлечения критериев к оптимизационному процессу. В работе предлагаются различные стратегии настройки вероятностных характеристик и схемы организации оптимизационного процесса в зависимости от информации ЛПР. Для редукции ограничений в скалярных задачах оптимального проектирования используется релаксационный подход, который основан на последовательном введении и выведении ограничений из допустимой области. Предлагается алгоритмическая схема адаптивного привлечения ограничений к оптимизационному процессу с использованием информации о степени их нарушения. Сокращение пространства варьируемых параметров осуществляется на основе их структуризации и выделения групп существенных и второстепенных параметров. При этом поиск оптимального решения производится по ограниченному набору существенных переменных с фиксацией значений второстепенных параметров. Рассматриваются две алгоритмические схемы выделения существенных переменных, первая из которых основана на исследовании чувствительности критерия оптимальности к изменению варьируемых параметров в текущей точке поиска, а вторая использует стратегию параметрической декомпозиции оптимизационных задач.
Четвертая глава посвящена формированию интеллектуальной многоме-тодной среды оптимального проектирования. С целью обеспечения гибкости и адаптируемости алгоритмической базы предлагается использовать компонентно-модульный подход, основанный на структуризации оптимизационных задач и алгоритмов их решения. При этом алгоритмическое обеспечение в общем виде определяется как совокупность библиотеки модулей оптимального выбора и интеллектуальных процедур ком-плексирования модулей в зависимости от специфики решаемой задачи.
Библиотека модулей строится по иерархическому принципу и включает модули двух классов: инвариантные модули, реализующие различные шаги обобщенных вычислительных схем непрерывной и дискретной оптимизации; внешние модули, подключаемые к инвариантному алгоритмическому ядру в зависимости от специфики решаемой оптимизационной задачи (размерности, типов критериев и ограничений и т.д.). Структура библиотеки обобщенно может быть представлена в виде графа, вершинам которого соответствуют алгоритмические модули, а дугам - возможные связи между ними. Конкретная вычислительная схема образуется "сборкой" модулей в единый алгоритм.
Для адаптивного управления оптимизационным процессом и компонентно-модульного синтеза алгоритмических схем разработаны интеллектуальные процедуры, обеспечивающие поддержку комплексирования модулей оптимального проектирования и формирование многометодных стратегий поиска в соответствии со спецификой решаемых задач. При этом определен набор признаков оптимизационных задач, сформированы критерии и условия применимости алгоритмических модулей и схем их сборки в различных ситуациях, разработаны стратегии организации оптимизационного процесса. Выделяются два уровня функционирования интеллектуальных процедур:
- априорная адаптация, состоящая в генерации алгоритмических схем на начальном этапе поиска непосредственно по постановке задачи;
- апостериорная адаптация, предусматривающая формирование многометодных стратегий решения задачи и комплексное использование различных алгоритмических схем в ходе оптимизационного процесса. В пятой главе рассмотрены вопросы интеграции адаптивной среды оптимального проектирования с процедурами моделирования и анализа при решении практических задач параметрического и структурного синтеза.
В главе представлены различные схемы интегрированного взаимодействия процедур имитационного моделирования и оптимизации в процессе поиска наилучших вариантов. Развиваемый оптимизационно-имитационный подход применяется для решения задач оптимального проектирования развивающихся производственных систем, связанных с определением параметрических и структурных изменений в действующей и стабильно функционирующей системе с целью повышения эффективности производства.
При оптимальном проектировании производственных систем используется принцип декомпозиции, предусматривающий структуризацию систем на взаимосвязанные блоки различной степени детализации с возможностью принятия оптимальных проектных решений как на уровне отдельных блоков, так и на уровне системы в целом. Каждому блоку декомпозиционной структуры ставится в соответствие управляющий элемент иерархической системы принятия проектных решений, включающий имитационную модель данного блока и комплекс оптимизационных моделей, предназначенных для решения различных классов задач оптимального проектирования. Для организации направленных имитационных экспериментов используются адаптивные вероятностно-детерминированные процедуры непрерывной и дискретной оптимизации.
Предлагаются оптимизационные модели и иерархические схемы поиска проектных вариантов при решении различных классов задач параметрического и структурного синтеза развивающихся производственных систем. Рассматриваются вопросы декомпозиции, согласования и координации моделей при оптимальном проектировании.
В шестой главе рассматривается организация программного комплекса поддержки принятия проектных решений, ориентированного на объекты проектирования с низким уровнем априорного математического описания. Основные компоненты программного комплекса и интерфейсные средства реализованы в среде Delphi 7.0. Программные модули, реализующие отдельные этапы оптимизационных процедур, оформлены в виде DLL-библиотек и подключаются к общей вычислительной схеме в зависимости от особенностей решаемой задачи. Используются как аналитическая, так и алгоритмическая формы задания оптимизационных моделей.
Включение в состав программного комплекса моделирующих блоков придает ему проблемную ориентацию на решение практических задач При решении задач оптимального проектирования производственных систем реализуется технология моделирования, основанная на совместном использовании CASE-средств и имитационных процедур. На начальном этапе производится функциональное моделирование с использованием CASE-системы BPwin. На основе построенной функциональной модели осуществляется формирование имитационной модели в среде Arena. Для интеграции имитационных моделей с программной средой принятия решений разработаны интерфейсные средства, представляющие собой совокупность процедур для корректировки базы данных модели. Связь с базой данных модели обеспечивается средствами ADO.
Показано использование разработанных моделей, алгоритмов и программных средств при параметрической и структурной оптимизации производственной системы изготовления телевизионной техники. При этом структурный синтез связан с решением задач замены оборудования и увеличения производственных мощностей. Параметрическая оптимизация предусматривает определение оптимальных интенсивностей и объемов партий комплектующих и материалов, поступающих на производственные участки. В рамках телевизионного производства осуществлена интеграция разработанного программного обеспечения с корпоративной информационной системой MFG/PRO.
В заключении представлены основные результаты работы.
Приложения содержат результаты тестирования предлагаемых алгоритмов, а также акты внедрения результатов диссертационной работы.
Интеграция процедур многовариантного моделирования и оптималь ного выбора при автоматизированном проектировании
Проблемы, связанные с принятием оптимальных решений, занимают особое место в автоматизированном проектировании. Их актуальность обусловлена многообразием моделей и форм проектируемых объектов и процессов, возникновением новых практических задач возрастающей сложности. Корректностью и эффективностью используемых оптимизационных процедур во многом обеспечивается успех автоматизации проектирования, особенно на ранних этапах. Вопросы совершенствования численных методов и алгоритмов оптимального проектирования, разработки и использования программных средств при решении широкого круга задач оптимизации рассматриваются как одно из перспективных направлений современных исследований [2,5,6,16,17, 33,47,58,76,101,110,115,150,153,166]. При этом, несмотря на разнообразие подходов, можно выделить два основных направления повышения эффективности процессов оптимального проектирования в САПР. С одной стороны, это достигается за счет рационального построения алгоритмической базы, а с другой - благодаря эффективной организации соответствующих средств программной поддержки - диалоговых систем оптимального проектирования, которые помимо непосредственного решения задачи выполняют функции адаптивного управления оптимизационным процессом [17,47,70,115,150,178].
При проектировании систем различных классов возникают многочисленные задачи, требующие оценки количественных и качественных закономерностей процессов функционирования объектов проектирования, проведения их структурного и параметрического синтеза. Несмотря на возрастающую сложность проектируемых объектов, процесс оптимального проектирования в современных САПР базируется на типовой итерационной схеме [17,98,140,168], включающей последовательность процедур структурного, параметрического синтеза, анализа и принятия решений (рис. 1.1).
Рассмотренной схеме процесса проектирования соответствуют три уровня оптимизации [17,98]. Первый уровень состоит в выборе наилучшей технической идеи или принципа действия объекта проектирования; второй уровень - в поиске наилучшей структуры или схемы в рамках выбранного принципа действия; третий уровень - в определении наилучших значений параметров объекта проектирования для выбранной структуры. Задачи первого уровня характерны для этапов внешнего проектирования и решаются с использованием экспертных подходов и методов. Математическое обеспечение современных САПР ориентировано на решение задач второго и третьего уровней и содержит методы и алгоритмы поиска в автоматизированном режиме оптимальных вариантов структуры и параметров объекта. Получение оптимального решения связано с выбором наилучшего варианта объекта из некоторого допустимого множества решений. Содержанием оптимизационного процесса является выбор вариантов, отвечающих требованиям к функционированию объекта оптимизации, а также набору эксплуатационных и технологических ограничений.
Задачи оптимального проектирования в САПР в общем виде формулируются следующим образом [17,58,98,140]: fl(X)- min , i = l,m XzD D = {X\xfn xJ xfax, j = u; gp(X) 0, hk(X) = 0, p = 1,5, к = \,q} Здесь X = (x\,...xn) - вектор варьируемых параметров объекта; fj(X)-частные критерии оптимальности; D - допустимая область, представленная ог У11У1 YY1CXX. і раничениями двух видов: прямыми х , X; Xj и функциональными gp(X) Q,hk(X) = 0.
Одной из основных проблем современного проектирования является проблема параметрического и структурного синтеза сложных объектов различного целевого назначения. Особенностью большинства оптимизационных задач, возникающих при автоматизированном проектировании сложных систем, является невозможность адекватного отображения свойств и процессов функционирования объектов оптимизации с помощью аналитических моделей [17,49,109,131,132,170,190]. Современные технические, социально-экономические, информационно-телекоммуникационные, производственные, организационные системы, относящиеся к классу сложных систем, характеризуются многообразием взаимосвязей между элементами, неоднозначностью алгоритмов поведения при различных условиях, наличием многочисленных случайных воздействий и возмущений, корреляционным взаимодействием между большим числом параметров [82,170,190]. Это затрудняет аналитическую формулировку критериев оптимальности и ограничений в оптимизационных моделях. Модели, описывающие зависимость между входными, выходными и внутренними параметрами в аналитической форме, используются, как правило, в частных случаях проектирования отдельных элементов при наличии ряда упрощающих предположений.
Формирование адаптивных рандомизированных алгоритмов поискового типа при оптимизации параметров сложных систем
Задача оптимального параметрического синтеза обобщенно может быть сформулирована следующим образом: fi(X)- тіп, і = 1,от, (2.1) ХєИ где X (x\,...,xn) - вектор варьируемых параметров объекта проектирования; fi(X) - частные критерии оптимальности; D - область допустимых решений.
При этом в зависимости от характера изменения варьируемых параметров задача может быть непрерывной, дискретной или дискретно-непрерывной.
Широкий класс задач оптимального параметрического синтеза сложных систем формализуется с виде задач с непрерывными переменными, в которых варьируемые параметры могут принимать любые значения в пределах, установленных прямыми ограничениями. Алгоритмизация задач данного класса предполагает выделение в качестве инвариантной части подзадачи скалярной безусловной минимизации в л-мерном евклидовом пространстве Rn: f(xi,...,xn)- min (2.2) R"
Предполагается, что целевая функция определена алгоритмически в виде моделирующей процедуры, позволяющей по заданным значениям вектора варьируемых параметров X = (х\,...,хп) получать значения /(X). Таким образом, ставится проблема построения процедур поиска экстремума алгоритмически заданного критерия f(X) при отсутствии информации о дифференциальных характеристиках данной функции.
Разработку схем алгоритмизации задачи (2.2) предлагается осуществлять с использованием адаптивных алгоритмов нелокальной оптимизации поискового типа, предложенных в работах [71,87,88,97]. В основе их построения лежит методологический прием более полной формализации задачи оптимального выбо pa, связанный с ее вероятностной переформулировкой (рандомизацией) и переходом к осредненному критерию оптимальности: F(X) = M[f(X)]- min, (2.3) {X} где М - операция математического ожидания; {X} - множество случайных векторов. Решением задачи (2.3) считается случайный вектор из множества {X}, минимизирующий функционал F(X).
Рассматриваемый подход является обобщенным, так как включает в качестве частного случая детерминированную постановку. Рандомизация задачи позволяет вынести поиск оптимальных решений на более высокий информационный уровень - уровень множества случайных векторов, что обеспечивает возможность выявления статистических закономерностей в свойствах оптимизируемой функции. В переформулированной осредненной задаче (2.3) не конкретизируется вероятностная схема перебора. При этом уже на уровне постановки задачи создаются возможности объединения вероятностных (обеспечивающих идентификацию свойств целевой функции) и детерминированных поисковых алгоритмов.
Итерационные процедуры поиска оптимальных вариантов формируются в множестве случайных векторов следующим образом: XN+l=XN+aNYN , (2.4) где N - номер итерации; Y - случайный вектор, задающий направление дви-жения и статистически связанный с X ; aN — величина шага в данном направлении.
Построение вычислительных алгоритмов основано на интерпретации итерационной процедуры (2.4) с использованием различных вероятностных характеристик случайных векторов. При этом необходимо обеспечить выполнение условия убывания целевого функционала F(X) на каждой итерации: F(XN+l) F(XN). Наиболее удобной для алгоритмизации является перезапись движения (2.4) в терминах математического ожидания: M[XN+l] = M[XN] + aNM[YN] . (2.5) Учитывая статистическую зависимость случайных векторов X и Y и используя формулу полного математического ожидания, M[Y ] можно представить в виде: M[YN] = MxN{M[YN\XN]} . (2.6)
Переход к рандомизированной постановке задачи приводит к необходимости использования в ходе оптимизационного процесса не отдельных локальных направлений поиска в точке, а векторного поля направлений. Обозначим
M[YN\XN=x] = yN(x), где (х) имеет смысл функции регрессии. Таким образом, направление поиска на каждой итерации определяется векторным полем у (х). Для его определения в [87,97] используется разложение в достаточно общих предположениях вектор-функции у(х), xeRn на потенциальную и бездивергентную составляющие: у{х) = 4 р{х) + W(x), divW(x) = О.
Таким образом, с точностью до бездивергентной составляющей движение на каждой итерации ориентировано в направлении градиента потенциальной функции (р{х). При этом ф{х) можно рассматривать как замену исходной целевой функции в процессе поиска экстремума. В результате формируются оптимизационные процедуры градиентного типа по отношению к потенциальной функции (р(х). Согласно [87,88,97], градиент потенциальной функции (р(х) может быть определен следующим образом:
Декомпозиционный подход к проектированию сложных систем с иерархической структурой
Предлагаемая алгоритмическая схема является обобщенной и предусмат ривает возможность реализации ее отдельных шагов с использованием альтерна тивных стратегий в зависимости от различных интерпретаций итерационной по исковой процедуры (2.10). Рассмотрим различные варианты реализации отдель ных этапов алгоритма. Для определения начальной выборки и , i = l,k (шаг 1) могут быть предложены следующие стратегии:
1. Выбираются реализации случайного вектора U, равномерно распре деленного на поверхности n-мерной сферы единичного радиуса с центром в на чальной точке поиска. В дальнейшем может быть произведена их ортогонализа ция [4,31,71].
2. Выбираются реализации случайного вектора, равномерно parape ts деленного на поверхности «-мерного эллипсоида, определяемые следующим об разом: г} = eg, где rf - случайный вектор, распределенный на поверхности эллип соида; — случайный вектор, распределенный на единичной сфере; В — матри 63 ца, преобразующая «-мерную сферу в «-мерный эллипсоид. Очевидно, что при _ соответствующем выборе матрицы 2?, учитывающей информацию о перспектив ности реализаций, вероятность розыгрыша в перспективных направлениях увеличивается. Подобная стратегия может быть применена при наличии априорной информации, являющейся основой для построения матрицы В. Такая информация может быть получена от пользователя перед началом итерационного процесса или накапливается в ходе поиска.
3. Осуществляется построение ортогональной системы из « векторов с по iP следующим переносом ее в начальную точку поиска. При этом используется схема: uN i+l=uN 1 +/?/, / = ЇЯ (2.14) где к; - длина шага в направлении г -й координатной оси; et - единичный орт.
4. Реализации случайного вектора U интерпретируются как вершины пра вильного многогранника в пространстве Rn с длиной стороны L: .; - uf +W, ІФІ м- (2.15) ,N,i, Lnf +G, i = j где j = 1,п - номера координат вектора и ; / = 2,« + 1 - номера реализаций. Параметры SnG определяются по схеме: nr L-(4 +\ \) L-(-JW+l + n-\) уу- ; (j- = «V2 «V2
Стратегия определения уровня оптимизируемой функции сдг (шаг 5) зависит от выбора функции W(t) в итерационной процедуре (2.10). Определим F(t) двумя способами: F(t) = t (линейная функция) и F(t) = sign(t) (знаковая функция). Для выбора уровня с используется условие (2.8). При этом в первом случае в соответствии с (2.8) получим: cN = \ f(x)PN(x)dx = M[f(UN]. Таким Г образом, при линейности функции F(t) в качестве уровня с выбирается мате i матическое ожидание случайного вектора U . При этом уровень сдг может оп 1 м ределяться следующим образом: сдг =— f(u ,l). При W(t) = sign(t) соот ki=\ ношение (2.8) имеет вид: J sign(f(x) -с )Р (x)dx = О и выполняется R" при выборе в качестве уровня медианы соответствующего распределения: р(/(и 1) сдг = p(f(u ,l ) Ctf, где р - вероятность попадания поисковой точки в неперспективную или перспективную область. Тогда \ f(uN (k+X)/2), если А: нечетно CN \(f(uN-k/2) + f(uN k/2+l ))/2, если Счетно. В методе Нелдера-Мида в качестве уровня сдг выбирается "предхудшее" значение целевой функции: /(и ) = f(u n).
Разделение реализаций на группы перспективности в соответствии с значением уровня сдг позволяет применять различные стратегии движения при попадании текущей поисковой точки в перспективную или неперспективную области. Так, из соотношения (2.10) следует, что направления движения в перспективной и неперспективной областях будут противоположны. При этом при lF(t) = sign(t) используется только знаковая информация о перспективности реализаций. При 4 (t) -1 учитывается не только знак соответствующей разности (f(u )-Ctf), но и ее значение, что позволяет определять очередное направление на основании степени перспективности (или неперспективности) данной реализации. Границы множеств Пр,Пу меняются при итерационной перестройке уровня сдг на основании текущей информации. В дальнейшем будем обозначать перспективные реализации х ,J, j = 1, г, а неперспективные реализации и ,l, i = \,q (при этом г и q - соответственно количество перспективных и неперспективных реализаций, q = n + \ r).
Разработка компонентной структуры алгоритмической базы оптималь ного проектирования
Реализация компонентно-модульного подхода к организации алгоритмической базы оптимального проектирования предполагает структуризацию оптимизационных задач и методов их решения. Рассмотренные выше и включенные в состав алгоритмического обеспечения оптимизационные процедуры разбиваются на ряд функциональных компонент, реализуемых одним или более модулями, различные комбинации которых приводят к формированию конкретных оптимизационных процедур. При этом алгоритмическая база оптимального проектирования сложных систем может быть определена как совокупность библиотеки модулей и проблемно-адаптивных процедур их комплек-сирования в зависимости от специфики решаемой задачи.
Состав библиотеки алгоритмических модулей представлен на рис. 4.1. Библиотека построена по иерархическому принципу, обеспечивает решение задач оптимального проектирования различной сложности и включает процедуры двух классов: процедуры скалярной безусловной оптимизации; проблемно-ориентированные внешние модули. Процедуры безусловной оптимизации образуют инвариантную часть алгоритмической базы. Подключение модулей второго класса осуществляется на внешнем уровне в зависимости от специфики решаемой оптимизационной задачи (размерности пространства варьируемых параметров, характера изменения параметров, количества и типов прямых и функциональных ограничений, числа критериев оптимальности и.т.д.) и не требует внесения изменений в инвариантное алгоритмическое ядро.
Каждый модуль представляет собой отдельно хранимую и независимо компилируемую единицу и имеет два имени: внешнее, объявленное в заголовке модуля и совпадающее с именем содержащего его дискового файла, и внутреннее, являющееся заголовком реализованной в нем процедуры. Альтернативные взаимозаменяемые модули имеют различные внешние и одинаковые внутренние имена. При этом внутреннее имя связывается не с конкретным объектом (модулем), а с выполняемой им функцией, что позволяет в разных ситуациях использовать модули, одинаковые по назначению, но различные по стратегиям реализации.
Структура библиотеки алгоритмических модулей обобщенно может быть представлена в виде агрегированного графа (рис. 4.2), вершинам которого соответствуют простые графы определенного функционального назначения. При этом различные алгоритмические структуры могут быль получены при выборе определенного пути в графе. Затем осуществляется дальнейшая конкретизация вычислительной схемы посредством раскрытия вершин агрегированного графа, включенных в обобщенный алгоритм.
Инвариантные алгоритмические процедуры оптимального проектирования структурируются следующим образом: процедуры непрерывной, дискретной и непрерывно-дискретной оптимизации. При этом непрерывные и непрерывно-дискретные оптимизационные процедуры предназначены для решения задач параметрического синтеза, а процедуры дискретной оптимизации — для решения задач как параметрического, так и структурного синтеза.
Модули непрерывной поисковой оптимизации можно условно разделить на две группы: модули, реализующие адаптивные рандомизированные алгоритмы нелокальной оптимизации; модули покоординатного поиска. Алгоритмы случайного поиска и их адаптивные расширения формируются на основе сочетания модулей первой и второй групп. Остальные модули являются вспомогательными и могут подключаться к поисковым процедурам по мере необходимости. Модульная структура алгоритмов непрерывной оптимизации может быть обобщенно представлена в виде ориентированного графа (рис. 4.3.), вершинам которого соответствуют алгоритмические модули, а дугам - возможные связи между ними. Конкретная вычислительная схема образуется "сборкой" модулей в единый алгоритм (или при выделении определенного пути в графе). Посредством различных комбинаций модулей можно формировать как стандартные, так и оригинальные алгоритмы поисковой оптимизации. Таким образом, на основе ограниченного набора инвариантных модулей осуществляется построение различных по степени сложности и информационной наполненности оптимизационных процедур. На рис. 4.3. модули, подключаемые к вершине INP1, соответствуют адаптивным рандомизированным алгоритмическим процедурам, а модули, подключаемые к вершине INP2 - алгоритмам покоординатного поиска. Модули, отличающиеся в названии последней цифрой, имеют одинаковое функциональное назначение и являются взаимозаменяемыми.
