Введение к работе
Актуальность темы. Проблемы, связанные с принятием оптимальных решений, занимают южное место в автоматизированном проектировании. При этом одной из ключевых проблем автоматизированного проектирования является оптимизация. Решение этой проблемы требует разработки и практического применения методов оптимизации, основанных на использовании ЭВМ. Среди прикладных задач оптимизации важное место занимают задачи дискретного программирования. Переход .от непрерывных моделей и методов исследования к дискретным является одной из особенностей современного этапа развития науки. Развитие вычислительной техники открыло новые области использования математических методов, привело к быстрому развитию методов оптимального проектирования, позволяющих реализовать построенные модели в рамках САПР. Сложность и многообразие задач оптимизации в САПР обусловливают повышенные требования к построению процедур оптимального проектирования и эффективности средств их алгоритмической и программной поддержки.
В настоящее время решение каждой задачи оптимального проектирования требует индивидуального подхода и связано с применением нескольких методов и еще большего числа алгоритмических процедур поиска оптимального решения. Для некоторых задач необходимо совместное использование нескольких алгоритмических процедур или их базовых модулей, т.е. приходится конструировать алгоритмы оптимизации для САПР.
Эффективность процедур оптимального проектирования, а также средств их алгоритмической и программной реализации может быть достигнута за счет построения библиотеки типовых моделей и алгоритмических, программных модулей. При этом важным вопросом эффективности применения данной библиотеки является этап математического моделирования задачи принятия решения (т.е. возможность сведения исходной постановки оптимизационной задачи к моделям, допускающим применение типовых алгоритмических конструкций).
При соответствующей переформулировке исходной задачи ряд существенных алгоритмических конструкций, обычно связанных с разными классами моделей описания как стандартных, так и нестандартных ситуаций, может быть вынесен на параметрический уровень по отношению к структурам, образующим инвариантное алгоритмическое ядро. Благодаря выделению инвариантного ядра открывается возможность при разработке алгоритмического обеспечения нестандартных задач поиска более полно использовать в рамках параметрического подхода уже имеющееся алгоритмическое обеспечение, осуществляя преемственность
детерминированных и вероятностных алгоритмов, ранее рассматри- "7 вавшихся для разного класса задач. При этом достигается совмещение этапа исследования объекта (идентификации целевой функции) с этапом собственно поиска лучших вариантов.
Во многих САПР большое внимание уделяется подсистемам интеллектуальной поддержки проектировщика. Характерными недостатками разработанных в настоящее время систем являются:
1) неадаптивность к различным классам объектов проектирования;
2) отсутствие обучающих элементов, которые позволили бы проектировщику использовать эти средства для решения прикладных задач.
В этой связи становится актуальной проблема создания подсистемы - библиотеки алгоритмических модулей для конструирования широкого класса алгоритмов, т. е. проектировщику предоставляется возможность конструирования конкретного алгоритма с учетом его функционального назначения. При этом данная подсистема должна обладать способностью к эффективному совмещению процесса формализации задачи с ее решением, гибкой модульной организацией, наличием элементов адаптации к особенностям объекта проектирования и развитых тек-стово-графических процедур поддержки пользовательского интерфейса. Таким образом, актуальность диссертационной работы определяется необходимостью разработки программного и алгоритмического обеспечения для формализации и решения определенного класса задач непрерывно-дискретной оптимизации в САПР, а именно, решения задач целочисленного и булева целочисленного программирования.
Диссертационная работа выполнена в соответствии с межвузовской научно-технической программой 12.11 "Перспективные информационные технологии в образовании", г/б НИР 5/97 "Разработка среды поисковой и непрерывно-дискретной оптимизации для создания специализированного алгоритмического обеспечения в САПР" в рамках одного из основных направлений Воронежского государственного технического университета "Разработка САПР, роботов и ГЛП".
Цель и задачи исследования. Целью диссертационной работы является разработка средств алгоритмической и программной поддержки процедур оптимального проектирования в СЛПР, ориентированных на решение определенного класса задач непрерывно-дискретной оптимизации и предусматривающих возможность более полной формализации задач оптимального проектирования, используя их вероятностную переформулировку. В соответствии с поставленной целью в работе решались следующие основные задачи:
разработка алгоритмических схем и процедур оптимального проектирования на основе адаптивного подхода;
формирование библиотеки базовых и проблемно-ориентированных модулей непрерывно-дискретной оптимизации;
разработка структуры комплекса инструментальных средств для задач непрерывно-дискретной оптимизации с привлечением элементом обучения;
создание средств диалогового взаимодействия с проектировщиком и гибкой, целостной системы обучающего материала;
разработка программного обеспечения для диалоговой обучающей подсистемы по непрерывно-дискретной оптимизации в САШ' и апробация среды непрерывно-дискретной оптимизации при решении некоторых прикладных задач в САПР при решении ряда прикладных задач оптимального проектирования (задача выбора параметров для контроля работоспособности системы, задача размещения прямоугольных элементов с минимальной длиной связывающей их сети).
Методы исследования основываются на методах непрерывно-дискретной оптимизации, аппарате вычислительной математики, теории вероятностей, теории систем, исследования операции, на экспериментальных исследованиях. При разработке программных средств использовались методы модульного программирования и технология объектно-ориентированного программирования.
Научная новизна. Основные результаты диссертации, выносимые на защиту и имеющие научную новизну:
построены алгоритмические схемы оптимального проектирования, основанные на сочетании детерминированных и вероятностных процедур для определенных методов непрерывно-дискретной оптимизации, характеризующиеся возможностью адаптации к особенностям моделей проектируемых объектов в рамках параметрического подхода;
сформирована библиотека алгоритмических модулей оптимального проектирования, отличающаяся иерархической структурой, наличием группы альтернативных взаимозаменяемых компонент, возможностью синтеза различных по уровню сложности оптимизационных процедур из набора инвариантных модулей;
разработаны средства диалогового взаимодействия с проектировщи
ком, позволяющие конструировать алгоритмы по непрерывно-
дискретной оптимизации на основе методов, реализованных в них;
разработан комплекс инструментальных средств для конструирования и программной реализации специального алгоритмического обеспечения в САПР, представляющий собой совокупность обучающих компонентов и библиотеки алгоритмических модулей.
Практическая ценность работы заключается в следующем:
используемый при разработке принцип объектно-ориентированного программирования позволил сформировать библиотеку инвариантных
модулей тю методам непрерывно-дискретной оптимизации с возможностью построения на их основе различных оптимизационных процедур, более эффективных, чем стандартные непрерывно-дискретные детерминированные и вероятностные алгоритмы;
в результате проведенных исследований разработана подсистема оптимального проектирования, применение которой в рамках САПР позволяет повысить эффективность оптимизационен) процесса, улучшить качество принимаемых проектных решений на параметрическом уровне, уменьшить временные и вычислительные затраты для получения оптимального решения;
создан программно-методический комплекс оптимального проектирования, направленный на решение определенного класса задач непрерывно-дискретной оптимизации, отличающийся сочетанием автоматизированного и интерактивного режимов функционирования, наличием средств интеллектуальной поддержки генерации программных компонент и гибкой подсистемы помощи на основе гипертекста, возможностью интеграции с прикладными программами за счет использования объектно-ориентированной технологии программирования;
разработанная подсистема инвариантна к предметной области приложения, обладает высокой гибкостью и может быть использована как при решении прикладных задач оптимального проектирования в САПР, так и в учебном процессе.
Реализация результатов работы. Разработанный программно-методический обучающий комплекс оптимального проектирования для задач непрерывно-дискретной оптимизации и разработки специального алгоритмического обеспечения в САПР внедрен в учебный процесс на кафедрах "Системы автоматизированного проектирования и информационные системы" Воронежского государственного технического университета и "Техническая кибернетика и автоматическое регулирование" Воронежского государственного университета и используется при проведении курсовых и лабораторных работ но курсам: "Конструирование алгоритмов в САПР", "Оптимизация в САПР", "Модели и алгоритмы оптимального выбора", "Модели и алгоритмы обработки финансовой информации".
Апробация рлботы. Основные положения диссертации докладывались и обсуждались на следующих конференциях, семинарах и совещаниях: Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, образовании и медицине" (Воронеж, 1994 -1995.); Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине" (Воронеж, 1996-1997); Международной научно-технической конференции "Методы и средства оценки и повышения приборов, уст-
ройсгв и систем'ЧПенза, 1995); Международной научно-техническом конференции "Актуальные проблемы анализа и обеспечения надежности и качестна приборов, устройств и систем'ЧПенза, 1996-1997); ежегодных научных конференциях профессорско-преподавательского состава Воронежского государственного технического университета.
Публикации. Основные результаты работы опубликованы в 12
печатных работах, перечень которых приведен в конце автореферата.
Структура и объём работы. Диссертация состоит из введения, четырех глав с выводами и заключения на 146 с, списка литературы (85 наименований) на 8 с, трех приложений па 25 с, содержит 16 рисунков, 4 таблицы.
