Информатика, вычислительная техника и инженерное образование 2011, №1(3) эволюционное моделирование, генетические и бионические алгоритмы
Скачать 1.19 Mb.
|
Информатика, вычислительная техника и инженерное образование 2011, № 1(3) ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫУДК 681.3 В.В. Курейчик, Н.Е. Курносова, Е.Е. Полупанова ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИНТЕГРИРОВАННОГО АЛГОРИТМА КОМПОНОВКИ1 Решение оптимизационной задачи компоновки зависит от выбираемой формальной математической модели коммутационной схемы. В работе рассматривается интегрированный эволюционно-генетический алгоритм для задачи компоновки блоков СБИС на основе гиперграфовой модели. Приводится его программная реализация. Интегрированный алгоритм, математическая модель, гиперграф. V.V. Kureichik, N.E. Kurnosova, E.E. Polupanova PROGRAM REALIZATION OF CONFIGURATION INTEGRATED ALGORITHMSolution of configuration optimization problem depends on mathematical model of connections diagram. Integrated algorithm for a problem of configuration VLSI elements based on hyper-graph models are resulted in this work. Also the program realization of this problem are represented. The integrated algorithm, mathematical model, hyper-graph. Введение Задачи конструкторского проектирования принадлежат к классу комбинаторных оптимизационных задач, реализация которых на ЭВМ зависят от выбираемой формальной математической модели коммутационной схемы. Различные математические модели в различной степени описывают одни и те же параметры устройства при решении каждой конкретной задачи конструкторского проектирования. В этой связи на различных этапах конструкторского проектирования используются различные коммутационные модели. Одним из важнейших вопросов этапа конструкторского проектирования ЭВА, РЭА, объектов машиностроения и др. является компоновка коммутационной схемы рассматриваемого устройства в конструктивно законченные части. Данная задача решается посредством разбиения схемы, с последующим группированием компонентов в блоки. В результате разбиения формируется множество блоков и межсоединений между блоками [1,2]. В данной работе рассмотрена гиперграфовая математическая модель задачи компоновки, а также приводится программная реализация интегрированного эволюционно-генетического алгоритма, рассмотренного в [3-5]. Построение математической модели для задачи компоновки Математическая модель – это совокупность математических объектов (чисел, переменных, векторов, множеств и т.п.) и отношений между ними, которая адекватно отображает некоторые свойства проектируемого технического объекта [2]. Различные математические модели с различной степенью точности описывают одни и те же параметры устройства. В этой связи, к математическим моделям предъявляются следующие требования:
Любая функциональная или принципиальная электрическая схема СБИС состоит из некоторого набора базовых элементов, определенным образом связанных между собой. Тогда схему можно рассматривать как некоторое множество элементов x1, х2, ..., xп, соединенных между собой цепями из множества E. На рис. 1 показана условная коммутационная схема блоков ЭВА. Здесь x1- x5 блоки; е1-е5 цепи (внешние связи); k1, k2 внешние контакты цепей схемы.  Рис. 1. Условная коммутационная схема блоков ЭВА Графотеоретические модели объектов сохраняют всю наглядность и содержательность описываемых объектов и позволяет строить формальные алгоритмы конструирования, которые легко обрабатываются на ЭВМ. В этой связи, рассмотрим задачу компоновки блоков в конструктивно-законченные части на примере гиперграфовой математической модели [6]. Считают, что гиперграф Н = (X, E) задан, если задано множество вершин  и множество ребер E = {e1, e2, …, em}, |Х|= n, |E| = m. Причём, каждое ребро гиперграфа представляет собой некоторое подмножество вершин, т.е.,  где множество X1 – подмножество вершин гиперграфа, соответствующие множеству блоков коммутационной схемы, а X2 – подмножество входных и выходных контактов коммутационной схемы. Причем, каждое ребро е Е соответствует соединённым одной электрической цепью элементам схемы. В данной математической модели каждому ребру E гиперграфа H взаимно однозначно соответствует некоторая цепь схемы. При этом заранее не обуславливается, в каком порядке будут соединяться вершины, инцидентные данному ребру. Задачу разбиения гиперграфа Н=(Х, Е) с взвешенными вершинами и рёбрами сведём к задаче о назначении множества гиперрёбер Е в К узлов при выполнении следующих условий: каждое гиперребро может быть назначено только в один узел, а стоимость вершин, назначенных в соответствующий узел, не должна превышать максимально допустимый суммарный вес вершин. Будем считать, что гиперребро назначено в узел, если всё множество составляющих его вершин назначено в этот узел. Таким образом, задача разбиения гиперграфа с взвешенными вершинами и рёбрами по критерию минимальной стоимости связей между узлами, или, что одно и то же, максимальной стоимости гиперрёбер, полностью размещённых в узлах, формулируется следующим образом: k m максимизировать F = h jv j , при ограничениях: v 1 j 1 n yivi pv ; v = 1, 2, …, k; i 1 k yiv 1; i = 1, 2, …, n; (1) v1 yiv hjv (еj); j = 1, 2, …, m; v = 1, 2, …, k, iI j где yiv, hjv – заданные условия; i – вес i-й вершины; j – вес j-го гиперрёбер; pv – максимально допустимый суммарный вес вершин, назначенных в v-й узел. Реализация этого критерия очень важна, т.к. очевидно, что внешние соединения между частями схемы являются одним из важнейших факторов, определяющих надёжность электронных устройств, а реализация этого критерия обеспечивает минимизацию взаимных индуктивных наводок, упрощение конструкции и, как следствие, повышение надёжности работы. На рис. 2 показан гиперграф, соответствующий коммутационной схеме (см. рис. 1).  Рис. 2. Неориентированный гиперграф H = (X, E) Для упрощения в нём не показаны входные и выходные контакты. Здесь каждое ребро гиперграфа представлено в виде замкнутой кривой, охватывающей инцидентные ребру вершины. Описание гиперграфа рассматриваемой схемы имеет вид: e1 = { x1, x2, x5}, e2={ x2, x3}, e3= { x1, x4, x5}, e4= { x2, x4, x5}, e5= { x3, x4, x5}. Гиперграф Н может быть описан и в матричном виде – с помощью матрицы инцидентности: I(Н)=||πij||, где i = 1, 2,..., n + N; j = 1, 2,..., D; (2)  (3) Указанный способ представления схемы гиперграфом приводит к адекватной математической модели в тех случаях, когда элементы схемы (блоки) допускают стягивание в точку. Это возможно либо в случае безразличного расположения контактов (выводов на блоке), либо в случае использования гиперграфов для задач, в которых не существен порядок выводов. Програмная реализация интегрированного алгоритма Эффективность интегрированных алгоритмов определяется тщательной настройкой их параметров. При произвольном выборе параметров эффективность алгоритма может быть как очень высокой, так и очень низкой, а его надёжность может лежать в приделах от нуля до ста процентов для одной и той же задачи. Поэтому в результате тщательной настройки параметров данного алгоритма удаётся повысить его эффективность и снизить при этом время работы [5]. На рис. 3 показано окно настройки параметров разработанного интегрированного алгоритма компоновки.  Рис. 3. Задание параметров интегрированного алгоритма компоновки Так как алгоритм является стохастическим, то для каждой настройки алгоритма эксперименты проводились по десять прогонов с ограничением по числу итераций, равным ста. В качестве параметра эффективности использовался процент нахождения оптимума целевой функции относительно ПГА. На рис. 4 показано окно для задания исходных данных задачи компоновки. Вес всех вершин принимался равным нулю, т.е. фактически не учитывался, а вес всех гиперрёбер − единице. Число вершин генерируемого гиперграфа X = 40, а число гиперрёбер Е = 60.  Рис. 4. Задание исходных данных задачи компоновки Далее осуществлялась генерация коммутационной схемы ЭВА на основе гиперграфовой модели, по заданным параметрам, что показано на рис. 5.  Рис. 5. Генерация коммутационной схемы ЭВА После запуска интегрированного алгоритма компоновки получили разбиение на 2 подгиперграфа с равным количеством вершин в каждом разбиении, что показано на рис. 6.  Рис. 6. Результат работы интегрированного алгоритма компоновки на основе роевого интеллекта (ИАКРИ) Заключение Проанализировав вышеизложенные факты, можно утверждать, что гиперграфовая модель является оптимальным вариантом для решения задачи компоновки элементов ЭВА в сильносвязные блоки при проектировании СБИС. Разработанный интегрированный алгоритм получает оптимальные результаты за меньшее число итераций за счёт направленности эволюционно-генетического поиска. Таким образом, использование предложенного интегрированного алгоритма компоновки на основе роевого интеллекта позволяет повысить эффективность решения задач конструкторского проектирования САПР СБИС, экономит процессорное время и память ЭВМ. Библиографический список
Курейчик Владимир Викторович Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге. E-mail: vkur@tsure.ru 347928, г. Таганрог, пер. Некрасовский, 44. Тел.: 8(8634) 38-34-51. Кафедра систем автоматизированного проектирования. Заведующий кафедрой, д.т.н., профессор. Курносова Наталья Евгеньевна Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге. E-mail: kurnosova_88@mail.ru 347928, г. Таганрог, пер. Комсомольский, 5, кв. 18. Тел.: 8(928) 171-75-10. Кафедра систем автоматизированного проектирования. Полупанова Елена Евгеньевна Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге E-mail: jienka@mail.ru 353900, г. Новороссийск, ул. Дзержинского, 195, кв. 47. Тел.: 8(928) 401-33-01. Кафедра систем автоматизированного проектирования; аспирант. |
Похожие:
 | В настоящем выпуске размещены работы по проблемам филологии, педагогики и методике обучения иностранным языкам, а в следующем выпуске... |  | Учебное пособие предназначено для студентов вузов, обучающихся по направлениям подготовки Информатика и вычислительная техника; Прикладная... |
| Б90 Использование субд для создания программных систем и их компонентов: Методические указания к практическим занятиям для студентов... | | «Информатика и вычислительная техника» 2 курс (заочное обучение, платные места) |
| ... | | Методические указания по выполнению междисциплинарной курсовой работы студентами образовательной программы «Информатика и вычислительная... |
| Правильный ответ помечается знаком × в бланке ответов. Исправления в бланке ответов не допускаются | | Федерального государственного образовательного стандарта по специальности среднего профессионального образования, входящей в состав... |
| Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования | | Федеральное государственное автономное образовательное учреждение высшего профессионального образования «национальный исследовательский... |