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

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

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

Из множества формализуемых задач структурного синтеза различных объектов существенная их часть может быть сведена к известной в целочисленном программировании задаче о минимальном покрытии (ЗМП). В частности, данной задаче соответствуют такие классы технических задач, как оптимизация логических схем, проектирование программируемых логических интегральных схем (ПЛИС), разбиение схем на подсхемы, разработка диагностических тестов и многие другие. Для ее решения разработано большое количество точных методов решения, которые, в частности, приведены в работах [2, 21, 51, 66, 78, 81]. Но все точные алгоритмы связаны с перебором на некотором конечном множестве, задаваемом исходными данными. По объему этого перебора как функции количества исходных данных существующие точные алгоритмы решения задачи о минимальном покрытии относятся к экспонециальным, что делает невозможным их использование для практических задач больших размерностей. Таким образом, возникает необходимость в разработке точных методов решения задачи о покрытии, отличающихся более высоким порогом применимости по сравнению с известными алгоритмами.

Основным недостатком существующих приближенных алгоритмов [11, 21, 49, 51, 62, 66, 81] является то, что основываясь на тех или иных разумных соображениях, они предлагаются, к сожалению, без надлежащего теоретического обоснования, поэтому в общем неизвестно, насколько далеко полученное решение от оптимального. Кроме того, для каждого из приближенных алгоритмов желательно знать специфические особенности задач, для которых его использование наиболее целесообразно. В связи с универсальным характером задачи о минимальном покрытии, есть смысл разрабатывать алгоритмы, не привязанные к конкретной предметной интерпретации. Тогда ведущее значение приобретает не смысловая трактовка, а характеристики набора исходных данных и требования к качеству получаемого решения. Однако идея любого разрешающего алгоритма всегда существенно привязана к способу математической формализации задачи, поэтому базой для конструирования точных и эффективных приближенных алгоритмов решения могут служить различные эквивалентные постановки задачи.

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

Работа выполнена в соответствии с межвузовской комплексной научнотехнической программой 12.11 «Перспективные информационные технологии в высшей школе» и в рамках одного из основных направлений Воронежского государственного технического университета «САПР и системы автоматизации производства» .

Цель и задачи исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертационной работы используются в учебном процессе кафедры ММИО в Воронежском государственном университете для студентов специальности «Прикладная математика» .

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

Апробация работы. Основные результаты работы докладывались и обсуждались: на семинарах в Воронежском государственном университете, Воронежском государственном техническом университетена V Международной конференции женщин — математиков (1997 г.), III Международной конференции из серии «Нелинейный мир» (1997 г.), Всероссийском совещании — семинаре «Математическое обеспечение информационных технологий в технике, образовании и медицине» (1997 г.), 20-й Конференции молодых ученых (1998 г.), 20-й Международной научной школе-семинаре «Системное моделирование социально — экономических процессов» (1998 г.), конференции «Математическое моделирование систем» (1998 г.).

Публикации. По теме диссертационной работы опубликовано 12 печатных работ.

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

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

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

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

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

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

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

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

7. Созданные программные средства нашли практическое применение в составе программного комплекса по организации сетей радиодоступа, разрабатываемом в ВНИИС, и в «Экспертной системе контроля качества инноваций в мелкосерийном машиностроительном производстве», разрабатываемой РАУ «Агентство информационных систем и технологий» .

Теоретические и практические результаты работы используются в учебном процессе кафедры ММИО в Воронежском государственном университете для студентов специальности «Прикладная математика» в курсах «Адаптивные алгоритмы» и «Практическая реализация алгоритмов дискретной оптимизации» .