автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Оптимизация проектных решений в условиях неопределенности на основе вероятностно-детерминированной поисковой среды

од

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

2 ДЕК

питолин

Андрей Владимирович

ОПТИМИЗАЦИЯ ПРОЕКТНЫХ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ НА ОСНОВЕ ВЕРОЯТНОСТНО-ДЕТЕРМИНИРОВАННОЙ ПОИСКОВОЙ СРЕДЫ

Специальность 05.13.12 -— Системы автоматизации

проектирования

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж — 1 997

Работа выполнена в Воронежском государственном техническом уни-7 версигете

*

Научный руководитель — канд. техн. наук, проф КАШШНСКИЙ А.И. Официальные оппоненты: д-р техн. наук ВОРОПАЕВ В.П.

канд. техн. наук ЯРНЫХ В.В.

Ведущая организация — Научно-исследовательский институт.

электронной техники (г. Воронеж)

Защита состоится 18 декабря 1997 г. в ^^часов на заседании диссертационного совета Д063.81.02 при Воронежском государственном техническом университете по адресу: 394026, г. Воронеж, Московский пр., 14.

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

Автореферат разослан ^ ноября 1997 г.

Ученый секретарь диссертационного совета

/ ^ Львович Я.Е.

/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Работа выполнена в соответствии с межвузовской комплексной программой 12.11 "Перспективные информационные технологии в высшей школе", г/б НИР 5/97 "Разработка среды поисковой и непрерывно-дискретной оптимиза-

ции для создания специализированного алгоритмического обеспечения САП?"7 в рамках одного из основных направлений Воронежского государственного технического университета "Разработка САПР, роботов и ГАГР.

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

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

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

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

создание среды интеграции программно-алгоритмического комплекса с процедурами имитационного моделирования.

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

Научная новизна. Основные результаты диссертации, выносимые на защиту и имеющие научную новизну:

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения диссертации докладывались и обсуяодались на следующих конференциях, семинарах и совещаниях: Всероссийских совещаниях-семинарах "Математическое обеспечение высоких технологий в технике, образовании и медицине" (Воронеж, 1994 - 1996); Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине" (Воронеж, 1997); Российской научно-технической конференции "Методы и средства оценки повышения надежности приборов,устройств и систем" (Пенза, 1994); Международных научно-технических конференциях "Методы и средства оценки повышения ьадеж-ности приборов, устройств и систем" (Пенза, 1995-1997); ежегодных научных конференциях профессорско-преподавательского состава Воронежского государственного технического университета.

Публикации. Основные результаты работы опубликованы в 11 печатных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами и заключениями на 116 е., списка литературы (131 наименование) на 14 е., 8 приложений на 25 е., содержит 15 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

нов при решении оптимизационных задач, построением диалогового интерфейса пользователя и подсистемы в процессе проектирования.

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

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

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

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

При этом исходная задача

/(*) = /(*, ,•••*„)-»/шгс

в"

заменяется осредненной (рандомизированной):

Р{Х)=М{Г{х)]->тт.

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

Итерационные процедуры поиска в этом случае формируются следующим образом:

XN*l=X"+aH+lYpl+l,

N+1

где N - помер итерации;

У1^1 - случайный вектор, задающий направление движения;

а,у+1 - величина шага в этом направлении.

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

V <р(х) = ми

нт-с]

a>Jx-u\

(х - и)

где СОп — площадь поверхности единичной сферы в R

\¡f(t)—монотонная неубывающая функция, такая, что y/(t)t>О, ty/fOj—O;

х, и — реализации случайных векторов;

С — некоторый уровень целевой функции, в зависимости от которого все реализации можно разделить tía перспективные и неперспективные.

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

ЛЧ1

XN+aN+lMv

ys[f(uN)-CN]

й)\Х

_

N\"

/ N N\

(X —и )

или в терминах математического ожидания:

M[XN+i] = M[XN] + aN+iM[YN+1] =

п

(x»-uN) .

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

Рассмотрены различные варианты формирования алгоритмических кои струкций, основанные на интерпретациях лтерациошшй процедуры поиска множестве случайных векторов, отличающиеся возможностью объединен» исследования поведения целевой функции и процесса поиска наилучших вари антов. Окончательный вариант вычислительной схемы зависит от вида преоб разования if/{t), плотности распределения PJx), выбора константы С, а гаюк различных способов статистической оценки математического ожидания.

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

3. Определение уровня оптимизируемой функции.

4. Разделение реализаций на группы перспективности.

5. Вычисление вероятностей для определения математического ожида

ния.

6. Оценка математического ожидания случайных векторов.

7. Движение в случайных векторах.

8. Анализ ситуаций и адаптивное уточнение шага.

9. Проверка сходимости. Бели сходимость не достигнута, переход I шагу 3.

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

2. Получение реализаций случайных векторов.

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

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

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

1=I

Для приведения функции/(х) к сепарзбельному виду используется замена переменных х-Ау и переход к новым переменным у— (у ],..,}>.

Замена переменных формулируется в виде

3А~\ у — А~хх — Вх.

Структура матриц А и В определяется путем последовательного применения замены переменных:

Х = Ал,у, х = Ан =

У = = >

где ы —корректирующая матрица; ■V-номер итерации.

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

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

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

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

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

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

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

ОЕй

Ш2

OSV

РИМ

тм

ГНР5 |-

сжт

БМО

РУ1 тг

I_ —I—

руз

РУ4

Га№~1 ГАТО

-С1

—

| КХ>1 I 1 кш |

1 ЕРМ 1 [от М 1

ЕЬР

[в а] ПУМ]

| 1 1 WES |

ОРТ] 1 ОР2 | I Х'РК I

гыт

РАЯ

вер"]! вта |

ЦкшЦСм!

РвУ

рвП 1 РС2~|

СЕ8~| -Т-^

кю

1 оь 1 1 ею 1

0«1 ] | ОЭ2 1

ОЙЗ

оит

Рис. 1. Структура библиотеки алгоритмических модулей поисковой оптимизации

Основными являются блоки:

• получения реализаций случайных векторов (модули OSV, PRM, SVS);

• определения уровня оптимизируемой функции (модули LVP, LVS, LVM);

• пересчета вероятностей для последующей оценки математического ожидания (модули RWR, WES);

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

• движения в случайных векторах на основе различных интерпретаций обобщенной итерационной процедуры (модули DV1, DV2, DV3, DV4);

• анализа результатов движения и адаптивной настройки шага (модули AN1, AN2);

• проверки сходимости алгоритмических процедур (модули OS1, OS2);

• выбора системы координат (модули KDl, KD2);

• одномерного поиска в выбранном направлении (модули ОР1, ОР2, NPR, INT);

• построения диагональной матрицы замены переменных (модули DG1, DG2);

• накопления информации о направлениях поиска и корректировки матрицы замены неременных с использованием оператора Шора (модули PAR, BFP, BFN; KR1.KR2).

Модули непрерывной поисковой оптимизации можно условно разделить на две большие группы: модули, реализующие стандартный детерминированный алгоритм переменного многогранника и его адаптивные расширения (подключаются к вершине INP1); модули покоординатного поиска (подключаются в вершине INP2). Алгоритмы случайного поиска и их адаптивные рас ширения формируются на основе сочетания определенных модулей первой и второй групп. Новая вычислительная схема создается на основе готовых модулей из числа имеющихся в библиотеке. Возможность построения конкретных оптимизационных процедур на базе различных комбинаций инвариантных модулей поисковой оптимизации обеспечивает гибкость и адаптируемость алгоритмических конструкций.

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

Схема 1; INPl; OSV; LVP; RWR; SMO; DVI; AN1; SIC; OS2; OUT. Схема 2: ШР1; OSV; LVM; RWR; SMO; DVI; AN1; DL; OS1; OUT. Схема3: INPl; OSV; LVS; WES; SMO; DV2; AN2; DL; OSI; OUT. Схема 4:1NP2; RND; NRM; EDS; ELP; OP1; PAR; KR2; OS3; OUT. Схема 5:1NP2; KD1; EDM; OP2; OBR; OS3; OUT.

Схема 6: INP2; KI>2; ORM; NPR; INT; GES; DG2; KR3; CLR; OS3; OUT.

Рис 2. Сравнительный анализ сходимости оптимизационных алгоритмов

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

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

Разработан пользовательский интерфейс, состоящий из средств диалогового взаимодействия проектировщика с системой и средств i-рафической визуализации результатов оптимизационного процесса. Интерактивную основу интерфейса составляют совокупность иерархических меню, очередной уровень которых формируется динамически по мере конкретизации вычислительного процесса, и система окон, каждое из которых представляет некоторый набор диалоговых ресурсов управления процессом решения оптимизационной задачи. В качестве аппаратной среды выбраны ПЭВМ типа IBM PC и совместимые модели. Все программные компоненты и соответствующие интерфейсные процедуры реализованы в среде Turbo Pascal с использованием программной оболочки Turbo Vision. Программно-алгоритмический комплекс занимает 1,2 Мбайт дисковой памяти.

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

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

Методы направленного имитационного моделирования реализованы в диалоговой системе оптимизации проектных решений в условиях неопределенности на имитационных моделях. Система состоит из блока моделирования и алгоритмического окружения (библиотеки алгоритмических модулей для конструирования поисковых оптимизационных алгоритмов). Для организации

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

1. Дискретно-непрерывные модели оптимального проектирования: Учеб. пособие / А.Й. Кашншский, Я.Е. Львович, С.Ю. Белецкая, A.D. шшшш, М.В. Питолин. — Воронеж, ВГТУ, 1997. — 109 с.

2. Каплинский А.И.,"Питолин A.B., Питолин М.В. Алгоритмизация решения некоторых нестандартных задач оптимизации // Методы и средства оценки и повышения надежности приборов, устройств и систем: Тез. докл. Международной науч-техн. конф. — Пенза, 1995. — С. 127.

3. Питолин A.B. Модульная организация алгоритмического обеспечения методов нелокального поиска оптимальных вариантов // Математическое обеспечение высоких технологий в технике, образовании и медицине: Тез. докл. Вссрос. совещ.- семинара. — Воронеж, 1995. — С. 145.

4. Питолин A.B. Интеграция процедур имитационного моделирования и поисковой оптимизации // Математическое обеспечение информационных технологий в технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. — Воронеж, 1996. — С. 97.

5. Питолин A.B. Разработка программных средств реализации некоторых алгоритмических процедур нелокальной оптимизации // Методы и средства оценки и повышения надежности приборов устройств и систем: Тез. докл. Международной научг техн. конф.— Пенза, 1996.-—С. 147.

6. Питолин A.B. Организация пользовательского интерфейса подсистемы оптимального проектирования // Математическое обеспечение информационных технологий в технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. — Воронеж, 1997. — С. 26.

7. Питолин A.B. Пакет прикладных программ для решения задач поисковой оптимизации в САПР // Методы и средства оценки и повышения надежно-сти^прибо|)Ов^/стройств и систем: Тез. докл. Международной науч-техн. конф.

8. Питолин A.B., Питолин М.В. Базовая библиотека алгоритмических модулей обучающей подсистемы по непрерывно-дискретной оптимизации в САПР для линейных моделей // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. — Воронеж, 1995, —С. 118-122.

9. Питолин A.B., Питолин М.В. Структура алгоритмического обеспечения слабоформанизованных задач оптимизации // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. — Воронеж, 1995.

10. Питолин A.B., Питолин М.В. Алгоритмизация поиска оптимальных вариантов при низком информационном уровне математического описания // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. — Воронеж, 1996. — С. 76-81.

11. Питолин A.B., Питолин М.В., Севостьянов Д.А. Оптимизационно-имитационный подход к проектированию структуры технических систем // Оптимизация и моделирование в автоматизированных chcti * ' . сб. науч.

СПИСОК ПУБЛИКАЦИИ

тр. — Воронеж, 1997. — С. 43-48.