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

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

КАШИРИНА ИРИНА ЛЕОНИДОВНА

ОПТИМИЗАЦИЯ СТРУКТУРЫ ОБЪЕКТОВ ПРОЕКТИРОВАНИЯ НА ОСНОВЕ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ЗАДАЧИ О МИНИМАЛЬНОМ

ПОКРЫТИИ

Специальность 05.13.12 —

Системы автоматизации проектирования

Диссертация

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

Научный руководитель: доктор технических наук,

профессор Львович Я.Е.

Научный консультант: кандидат технических наук,

доцент Чернышова Г. Д.

Воронеж — 1999 /

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 3

ГЛАВА 1. ПУТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРО- 9 ЦЕДУР ПРИНЯТИЯ РЕШЕНИЙ НА ЭТАПЕ СТРУКТУРНОГО СИНТЕЗА ОБЪЕКТОВ ПРОЕКТИРОВАНИЯ

1.1. Анализ оптимизационных моделей этапа структурного син- 9 теза объектов проектирования

1.2. Требования к эффективности алгоритмических процедур 37

1.3. Цель и задачи исследования 44 ГЛАВА 2. ФОРМИРОВАНИЕ ЭКВИВАЛЕНТНЫХ ПОСТАНО- 48 ВОК ЗАДАЧИ О МИНИМАЛЬНОМ ПОКРЫТИИ ПРИ ОПТИМИЗАЦИИ СТРУКТУРЫ ОБЪЕКТОВ ПРОЕКТИРОВАНИЯ

2.1. Принципы формирования эквивалентных постановок 49

2.2. Детерминированные постановки 52

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

Выводы 2-й главы 62

ГЛАВА 3. РАЗРАБОТКА ВЕРОЯТНОСТНЫХ АЛГОРИТ- 64 МИЧЕСКИХ СХЕМ РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ПОКРЫТИИ

3.1. Методы конструирования точных и приближенных адаптив- 64 ных алгоритмов решения задачи о покрытии

3.2. Модификация "жадных" эвристических алгоритмов за счет 69 перехода к вероятностной постановке задачи

3.3. Вероятностная модификация двойственных субградиентных 89 алгоритмов

3.4. Алгоритм решения задачи о покрытии с дополнительными 101 ограничениями

3.5. Тестирование разработанных алгоритмов Выводы 3-й главы

116

ГЛАВА 4. ВНЕДРЕНИЕ АЛГОРИТМОВ И ПРОГРАММНЫХ 118 СРЕДСТВ В ЗАДАЧАХ ОПТИМАЛЬНОГО ПРОЕКТИРОВАНИЯ

4.1. Организация программного обеспечения для этапа структур- 118 ного синтеза объектов проектирования

4.2. Проектирование структуры производительной радиосети пе- 122 редачи информации

4.3. Структурная оптимизация базы знаний 125 Выводы 4-й главы 129

ВВЕДЕНИЕ

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

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

Из множества формализуемых задач структурного синтеза различ-

ных объектов существенная их часть может быть сведена к известной в целочисленном программировании задаче о минимальном покрытии (ЗМП). В частности, данной задаче соответствуют такие классы технических задач, как оптимизация логических схем, проектирование программируемых логических интегральных схем (ПЛИС), разбиение схем на подсхемы, разработка диагностических тестов и многие другие.

, Для ее решения разработано большое количество точных методов решения, которые, в частности, приведены в работах [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. ПУТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРОЦЕДУР ПРИНЯТИЯ РЕШЕНИЙ НА ЭТАПЕ СТРУКТУРНОГО СИНТЕЗА ОБЪЕКТОВ ПРОЕКТИРОВАНИЯ

1.1. Анализ оптимизационных моделей этапа структурного синтеза объектов проектирования

Этап структурного синтеза объектов проектирования составляет существенную часть процесса проектирования (рис.1) [50] и является особенно трудоемким. Процесс проектирования структуры сложного технического объекта представляет собой многоэтапную процедуру, осуществляемую по блочно- иерархическому принципу [7]:

1. Построение допустимого множества принципиально возможных типов входящих в объект элементов.

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

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

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

Рис. 1. Место задач покрытия в схеме процесса проектирования

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

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

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

процесса структурного проектирования.

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

Оптимизация логических схем

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

Но до сих пор мало конструктивных методов, позволяющих автоматизировать процесс синтеза с учетом всех перечисленных критериев [69]. Большая часть работ в данном направлении посв