Содержание к диссертации
Введение
1. Анализ и состояние проблемы компоновки блоков ЭВА 12
1.1 Коммутационные модели блоков ЭВА 12
1.2 Постановка задачи компоновки 25
1.3 Анализ существующих алгоритмов разбиения графов и гиперграфов на части 31
1.4 Выводы 46
2. Разработка поисковых методов компоновки блоков ЭВА... 47
2.1 Использование экспертных систем при построении моделей компоновки блоков .47
2.2 Разработка архитектуры, стратегии и принципов компоновки блоков 61
2.3 Построение модифицированных генетических операторов 88
2.4 Выводы 105
3. Разработка композитных алгоритмов компоновки блоков ЭВА 106
3.1. Разработка алгоритмов компоновки на основе раскраски графов 106
3.2. Построение параллельно-последовательных алгоритмов компоновки на основе определение независимых и доминирующих подмножеств 125
3.3. Разработка композитного алгоритма компоновки на основе сжатия и построения паросочетаний графа 136
3.4. Выводы 142
4. Анализ экспериментальных исследований разработанных алгоритмов 144
4.1. Краткие сведения об инструментальной среде компоновки блоков ЭВА 144
4.2. Цель и средства экспериментальных исследований 146
4.3. Результаты экспериментальных исследований 147
4.4. Выводы 164
Заключение. 165
Список использованных источников 167
Приложение 177
- Анализ существующих алгоритмов разбиения графов и гиперграфов на части
- Разработка архитектуры, стратегии и принципов компоновки блоков
- Построение параллельно-последовательных алгоритмов компоновки на основе определение независимых и доминирующих подмножеств
- Цель и средства экспериментальных исследований
Анализ существующих алгоритмов разбиения графов и гиперграфов на части
Задачи разбиения графа и гиперграфа на части имеют много практических применений. Они используются при проектировании устройств автоматики и вычислительной техники, энергосистем, созданий систем управления, компьютерных и инженерных сетей, в коммунальном хозяйстве и т.п. Отметим, что задачи разбиения графа и гиперграфа на части относятся к классу NP-полных проблем, то есть не существует эффективных алгоритмов их решения с полиномиальной временной сложностью для массового набора задач [8,14,.21-23].
В полиномиальных алгоритмах временная сложность составляет О(п), 0(п2), 0(п3),.... Для экспоненциальных алгоритмов (NP) временная сложность алгоритма, например, имеет вид 0(пп), 0(n2n), 0(п3п),.... Класс NP-полных задач включает такие задачи, для которых не найдены полиномиальные алгоритмы, однако и не доказано, что их не существует [21,23]. Для рассмотрения вопроса о NP-полноте задачи разбиения графа, по аналогии с любой оптимизационной задачей, их можно преобразовать в задачу разрешения. Обычно в качестве задачи разрешения рассматривают проверку, является ли некоторое число верхней или нижней границей для оптимизируемой величины. Если для задачи разбиения графа имеется «быстрый» алгоритм, то и полученную из нее задачу разрешения можно решать «быстро». Для этого надо сравнить ответ этого алгоритма с заданной границей. Будем говорить, согласно [23], что произвольный алгоритм решает задачу разбиения графа за время 0(Т(п)), если на входных данных длины п алгоритм работает время 0(Т(п)).
Как известно [21,23], время работы алгоритма зависит от числа элементарных шагов, которые он выполняет. Время работы процедуры алгоритма зависит не только от п, но и от того, какой именно список или матрица размера п поданы ей на вход. Таким образом, в благоприятном случае время Т(п), необходимое для анализа графа на п вершин, является линейной функцией от п, т.е. имеет вид типа T(n) = an + Р для некоторых констант аир. Или, например, функция Т(п) - квадратичная, т.е. имеет вид T(n) = an2 + fki + у, где а,р\у - константы. Известно [21], что в задачах разбиения графов на части можно определить время работы алгоритма в худшем случае и в лучшем случае и они могут сильно различаться. На практике, наибольший интерес представляет время работы в худшем случае, которое определяется как максимальное время работы алгоритма для заданного п. Это обусловлено следующими причинами: зная время работы в худшем случае, можно гарантировать, что выполнение алгоритма закончится за некоторое время, даже не зная, какой именно размер графа по числу вершин и ребер будет анализироваться; время работы алгоритма в среднем часто бывает близко к времени работы в худшем случае.
Например, для оценки алгоритма разбиения графа на части вида an + Рп + ух говорят, что время работы в худшем случае имеет порядок роста n , отбрасывая линейные члены меньших порядков и не интересуясь коэффициентом при п2. Это записывают так: T(n) = 0(п2) [21,23]. Алгоритм разбиения графа на части с меньшим порядком роста времени работы обычно предпочтительнее. Если один алгоритм разбиения имеет время работы @(п2), а другой - 0(п3), то первый более эффективен (по крайней мере для достаточно больших п).
При разбиении графов на части из-за большой размерности коммутационных схем на начальных этапах («препроцессорные» исследования) используются эвристические алгоритмы типа «разделяй и властвуй» [23]. Предположим, что алгоритм типа «разделяй и властвуй» распределяет задачу разбиения графа размера п на а подзадач, каждая из которых имеет в Ь раз меньший размер. Тогда считают, что разбиение графа на части требует времени Щи), а соединение полученных решений — времени С(и). В результате получаем соотношение для времени работы Т(и) на задачи разбиения графа с п вершинами (в худшем случае):
Это соотношение справедливо для достаточно больших п, когда коммутационную схему имеет смысл предварительно разбивать на подзадачи. Для и 100, когда такое разбиение невозможно или не нужно, применяется какой-либо точный или композиционный метод решения. Предположим, что размер графа есть степень двойки. Тогда на каждом шаге анализируемый граф делится на две равные половины. Разбиение на части (вычисление границы) требует времени 0(1), а слияние — времени 0(п). Получаем соотношение [21]
Разработка архитектуры, стратегии и принципов компоновки блоков
В задачах САПР любое альтернативное решение представляется значениями параметров xh относящихся к некоторому множеству X. В бионических методах множеству X соответствует кодовая запись, считающаяся хромосомой. Элементы хромосомы соответствуют параметрам Xj, их называют генами, а значения генов - аллелями. Набор генов соответствует строительным блокам схемы. Каждый ген размещается в хромосоме в некоторой позиции - локусе. В случае геометрической интерпретации каждой хромосоме соответствует некоторая точка поискового пространства [2,39].
Очевидно, что в задачах САПР число возможных альтернатив столь велико, что их явное представление невозможно. Поэтому в каждый момент поиска генетический алгоритм оперирует подмножеством Р альтернативных решений мощности N. Это подмножество называют популяцией, а N -размером популяции. Хромосома, представленная конкретными значениями своих генов, есть проектная альтернатива.
Основная идея генетического алгоритма заключается в эволюции популяции, повторяющей некоторые черты эволюции организмов в живой природе. Если цель эволюции в живой природе — обеспечение наибольшей жизнеспособности популяции в условиях окружающей среды, то цель эволюции в генетическом алгоритме - получение альтернативных решений с наилучшими значениями заданных критериев [39]. Эти критерии характеризуют качество компоновки. Как и в других задачах САПР, в генетическом методе компоновки при наличии нескольких критериев задача сводится к однокритериальной путем свертки [40-43]. Объединенный критерий считают целевой функцией [ЦФ] компоновки. Таким образом, цель эволюционного поиска заключается в нахождении альтернативных решений, имеющих значение целевой функции, максимально близкое к ее оптимальному значению. Генетические алгоритмы имитируют эволюционный процесс приближения к оптимальному результату, начиная с некоторого исходного поколения альтернативных решений. Члены исходного поколения генерируются случайным, направленным или комбинированным образом.
Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Традиционный ПГА случайным образом генерирует начальную популяцию хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование хромосом и перестановка их частей на основе трех стандартных операторов: репродукции, кроссинговера и мутации. Раскроем понятия и приведем определения стандартных, модифицированных и новых генетических операторов [59-68]. Генетический оператор - это средство отображения одного множества на другое. Другими словами, это конструкция, представляющая один шаг из последовательности действий генетического алгоритма, описанного посредством некоторого языка. Оператор репродукции (селекция) (ОР) - это процесс, посредством которого хромосомы (альтернативные решения), имеющие более высокое значение ЦФ, получают большую возможность для воспроизводства (репродукции) потомков. Оператор кроссинговера - это языковая конструкция, позволяющая на основе преобразования (скрещивания) хромосом родителей (или их частей) создавать хромосомы потомков. Оператор мутации - это языковая конструкция, позволяющая на основе преобразования родительской хромосомы (или ее части) создавать хромосому потомка. Оператор инверсии - это языковая конструкция, позволяющая на основе инвертирования родительской хромосомы (или ее части) создавать хромосому потомка. Оператор транслокации - это языковая конструкция, позволяющая на основе скрещивания и инвертирования из пары родительских хромосом (или их частей) создавать две хромосомы потомков. Оператор транспозиции - это языковая конструкция, позволяющая на основе преобразования и инвертирования выделяемой части родительской хромосомы создавать хромосому потомка. Оператор сегрегации - это языковая конструкция, позволяющая на основе выбора строительных блоков из хромосом родителей (или их частей) создавать хромосомы потомков. Оператор удаления - это языковая конструкция, позволяющая на основе удаления строительных блоков из хромосом родителей (или их частей) создавать хромосомы потомков. Оператор вставки - это языковая конструкция, позволяющая на основе вставки строительных блоков в хромосомы родителей создавать хромосомы потомков. Оператор редукции - это языковая конструкция, позволяющая на основе анализа популяции, полученной после одного или нескольких поколений в процессе работы генетического алгоритма, уменьшать ее размер до заданной величины. Оператор рекомбинации - это языковая конструкция, которая определяет, как новая генерация хромосом будет построена из родителей и потомков.
Построение параллельно-последовательных алгоритмов компоновки на основе определение независимых и доминирующих подмножеств
При автоматизированном проектировании схем ЭВА и решении задач компоновки блоков ЭВА часто возникает необходимость восстановления первоначального задания схемы по некоторым формальным признакам. С целью создания формальной модели используют методы оптимального (параллельного) свертывания схемы [29]. Он основан на построении деревьев и прадеревьев свертки графовых и гиперграфовых моделей схемы.
Идея метода заключается в следующем. Исходные элементы (вершины) графовой и гиперграфовой модели ( отнесем к первому уровню прадерева свертки. На первом шаге из множества X (вершин) выделяем равноценные по выбранному критерию группы элементов — центры наращивания (ядра). Такие группы могут быть образованы объединением (композицией) двух или более элементов. Сформированные группы относим к множеству второго уровня прадерева свертки. На втором шаге формируем по выбранному критерию множество третьего уровня прадерева свертки и так до тех пор, пока все элементы исходного множества не будут объединены в одно, соответствующее единственному элементу самого высокого уровня,, т. е. корню прадерева свертки графовой или гиперграфовой модели схемы. Формирование произвольного элемента i-ro уровня прадерева свертки осуществляется двумя или большим количеством элементов более низких уровней. Процесс иерархического (параллельно-последовательного) свертывания схемы напоминает процесс кристаллизации и моделирования отжига, когда на первых этапах параллельно выделяются ядра, которые в дальнейшем укрупняются, расширяясь и объединяясь с другими ядрами.
Предлагаем метод компоновки, основанный на выделении элементов для их композиции в подсхемы и формирования деревьев и прадеревьев свертки [29,30]. Рассмотрим произвольный і-й шаг наращивания. Пусть на предыдущих шагах построен граф свертки т.е. многокорневое прадерево (ветвящееся дерево). Выделим множество максимальных его вершин. Тогда формирование множества вершин (i-H)-ro уровня образуется из подсхем с одинаковым оптимальным или близким к нему значением выбранного функционала К. Вместе с вершинами множества всех предыдущих уровней оно образует новое множество вершин графа свертки следующего уровня. С практической точки зрения выделение на одном шаге свертывания подсхем, объединяющих более двух элементов, связано с существенными вычислительными затратами, что требует формирования всех возможных групп элементов и вычисления для них значения функционала К. Поэтому для многих реальных задач ограничиваются рассмотрением пар и троек элементов. Область D допустимых решений определяется на множестве композиций пар подсхем, задаваемых декартовым произведением. Отметим, что в общем случае некоторые ребра графа или гиперграфа (коммутационные цепи) могут быть одновременно и внутренними, и внешними. При свертывании возможно возникновение неоднозначности. Для ее разрешения целесообразно выбрать несколько критериев, упорядоченных лексикографическим образом. Приведенные критерии могут быть использованы как для графовых, так и для гиперграфовых моделей схемы.
В качестве основных критериев и ограничений при декомпозиции схемы выступают следующие: функциональная завершенность (полнота) образованных подсхем; эквивалентность выделяемых подсхем подсхемам заданного набора типовых решений, определяемых библиотекой (задача покрытия схемы); взаимная эквивалентность выделяемых подсхем с минимизацией количества их типов (задача типизации); количество образованных подсхем; внешняя связность подсхем — общее количество коммутационных соединений (электрических цепей) между образованными подсхемами; внутренняя связность подсхем — общее количество связей внутри подсхем или их среднее значение на одну подсхему; отдельные характеристики каждой подсхемы: количество входящих в нее элементов, некоторый условный вес (площадь, объем), количество необходимых внешних контактов, определяемых количеством внешних связывающих цепей, и другие величины; множество элементов определенные конструктивно-технологическими ограничениями, которые должны быть разнесены в разные подсхемы или введены в строго заданные подсхемы [8,12,29,39,71].
Критерием свертки выбирается основной оптимизируемый параметр К, который косвенно учитывает все перечисленные критерии.
Задача компоновки связана с построением различных инвариантов графов. К ним относится независимые и доминирующие подмножества, ядра и клики графа. Подмножество из максимального числа смежных между собой вершин в графе называется кликой. В графе можно выделить некоторое семейство клик Q = {Qi, Q2,..-,QZ}- Стратегии, концепции и принципы композитных алгоритмов поиска, описанные выше, применим для построения семейства клик. Структура модифицированного композитного алгоритма, использующая инварианты графа для задачи компоновки, представлена на рис.3.17 [39,71]. В данной схеме используются идеи совместной эволюции, адаптации к внешней среде, активное взаимодействие с внешней средой, иерархическое управление генетическим поиском, локальный поиск решений и применение всех модифицированных генетических операторов на основе жадной стратегии и поисковых методов.
Цель и средства экспериментальных исследований
Цель экспериментальных исследований - это анализ зависимости скорости сходимости разработанных алгоритмов. В качестве критерия оптимальности алгоритма используется минимальное значение целевой функции (выражение 1.1). При этом анализируется определенное количество итераций алгоритма (число генерируемых поколений). Проведены серии экспериментов, используя различные тестовые функции (бенчмарки). Основные этапы экспериментальных исследований следующие: Проведение серии экспериментов для фиксированных значений общих параметров моделей коммутационных блоков разработанных алгоритмов; Проведение серии экспериментов с заданными изменяемыми параметрами моделей и алгоритмов; Анализ экспериментальных данных - максимального, минимального и среднего значения целевой функции, полученных при использовании конкретных алгоритмов; Проведение серии экспериментов для различных тестовых функций (бенчмарк) и их анализ; Определение оптимальных и квазиоптимальных параметров алгоритмов решения задачи компоновки блоков ЭВА удовлетворяющих конкретных пользователей САПР. Исходными данными для работы программы компоновки блоков ЭВА на основе раскраски графов являются: количество вершин и ребер коммутационной модели; число частей разбиения и количество вершин в них; матрицы и списки смежности графа; размер популяции; количество поколений (итераций); вероятности применения генетических операторов. Программа состоит из основного исполняемого модуля
Configuration.exe, разработанного под операционные системы Windows 2000 и выше. После вызова Configuration.exe появляется основное окно программы, представленное на рис. 4.2. Главное окно программы разбито на три блока: 1. Изображение графа - содержит графическое представление коммутационной модели блоков ЭВА. 2. График изменения целевой функции - отражает процесс компоновки на основе разработанных алгоритмов. 3. Индикатор реализации процесса поиска оптимальных и квазиоптимальных решений. Главное меню состоит из следующих элементов: Файл. Граф. Алгоритм. Параметры. Управление. Результаты. Помощь. При выборе пунктов меню «Новый граф» или случайный граф пользователю предлагается указать параметры графа в окне, представленном на рисунке 4.3. В выпадающем меню «Алгоритм» предусмотрен выбор одного из трёх алгоритмов: последовательный, итерационный, генетический. Настройками генетического алгоритма являются: вероятность применения генетических операторов, размер популяции, количество поколений (рис.4.4). Результатом работы программы являются графики изменения ЦФ для итерационного и генетического алгоритма (рис.4.5 и 4.6), для коммутационной модели (рис. 4.1).
Объем занимаемого места на жестком диске составляет 1 МБ. Учитывая пространственную сложность алгоритма, который лежит в основе данного программного комплекса можно определить, что минимальный объем памяти необходимый для запуска программы на графе из 30 вершин составляет примерно 6Мб. В нашем случае при использовании 512Мб памяти возможно обрабатывать модели содержащие до 2500 блоков. Однако при увеличении размера моделей объем требуемой оперативной памяти значительно возрастает. В работе были проведены экспериментальные исследования влияния параметров модифицированного генетического алгоритма МГА на изменение значений ЦФ и времени работы: количества поколений NP и размера популяции Ni; вероятности кроссинговера, вероятности мутации и инверсии Рок Ром и Р0и. Проанализируем сначала влияние размера популяции на получаемые результаты. При этом будем варьировать вероятность всех генетических операторов, а также менять количество итераций ГА. Построим таблицу 4.1, в которой приведем результаты проведенных экспериментов. В таблице приведены различные данные разбиения графа, содержащего п=300 вершин, т=3000 ребер, на три части по 100 вершин в каждой с минимизацией количества внешних ребер. По результатам экспериментов, сведенных в таблицу 4.1, построим графики зависимости времени и ЦФ получения лучшего решения от количества итераций N; (рис.4.7,4.8). Из графика следует, что время решения линейно зависит от числа генераций которые, влияют на получение оптимальных и квазиоптимальных результатов. Отметим, что при попадании в локальные оптимумы производим изменение размера популяции, количества генераций и вероятности применения генетических операторов. Экспериментальные исследования зависимостей значений ЦФ и времени решения от размера популяции Np приведены в таблице 4.2 и на рис.4.9 и 4.10. Размер популяции, как видно из таблицы, влияет на время решения и на получение оптимальных результатов.
