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

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

МИЩЕНКО МАКСИМ НИКОЛАЕВИЧ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА БИОНИЧЕСКИХ МЕТОДОВ РАЗМЕЩЕНИЯ КОММУТАЦИОНЧЫХ

СХЕМ ЭВА

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

Автореферат на соискание ученой степени кандидата технических аук

Таганрог - 2005 г.

Работа выполнена на кафедре САПР Государственного образовательного учреждения высшего профессионального образования «Таганрогский государственный радиотехнический университет» (ТРТУ)

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

профессор Курейчик В.В.

Официальные оппоненты: заслуженный деятель науки РФ,

доктор технических наук, профессор Чернышев Ю.О.

доктор технических наук, профессор Ковалев С.М.

Ведущая организация: РОСНИИ информационных технологий и

автоматизации проектирования г. Москва

Защита состоится «28 » октября 2005 г. в 14-30 на заседании диссертационного совета Д 212.259.03 при Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, пер. Некрасовский 44, ауд.Д-406.

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

Автореферат разослан « 17 »октября 2005 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Целых А.Н.

1Ц-Ч

чТТз"

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

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

Целью диссертационной работы является разработка бионических методов и алгоритмов для решения задачи размещения блоков ЭВА.

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

• построение моделей коммутационной схемы и монтажного пространства для анализа и преобразования данных при размещении элементов схем ЭВА;

• построение новых архитектур бионического поиска ориентированных на решение задач размещения;

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

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

Методы исследования в диссертации основаны на использовании элементов теории множеств, графов, алгоритмов и эволюционного моделирования.

Научная новизна диссертационной работы заключается в следующем:

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

• Предложена новая архитектура бионического поиска для распараллеливания процесса размещения элементов схем ЭВА.

• Разработаны новые бионические алгоритмы размещения, основанные на комплексных эвристических процедурах поиска.

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

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

• бионические алгоритмы размещения, позволяющие распараллеливать процесс решений;

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

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

размещения, отвечающие конкретным конструктивным и технологическим ограничениям. Программная среда отвечает конкретным задачам управления жизненным циклом продукции при размещении элементов схем ЭВА. При построении комплекса программ использовались пакеты С++, Builder, Visual С++. Тестирование проводилось на ЭВМ типа IBM PC с процессором Pentium-IV с ОЗУ-512М6. Проведенный вычислительный эксперимент, показал преимущество бионических алгоритмов для решения задач размещения элементов и блоков ЭВА, по сравнению с известными методами.

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук; госбюджетная работа по заказу Минобрнауки РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений». Материалы диссертации использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле лекций и практических занятий по курсам «автоматизация конструкторского и технологического проектирования» и «Эволюционное моделирование и генетические алгоритмы».

Апробация основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на международных научно-технических конференциях «Интеллектуальные САПР» (г. Дивноморск 2002- 2005гт.), на международной конференции «Интеллектуальные системы» (г.Дивноморск, 2004, 2005гг.), на научных семинарах Северо-Кавказкого научного центра высшей школы (г. Ростов-на-Дону, Таганрог, 2003 - 2005гг.) на международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2005 г.).

Публикации. Результаты диссертации отражены в 7 печатных работах.

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

литературы и приложения. Работа содержит 135 стр., а также 36 рис., расположенных на 23 стр., список литературы из 109 наименований, 2 стр. приложений и актов об использовании.

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

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

А(в) = а ЦО + р П(0 + уВ(О) +6С(0)+т10(С) + тсЕ(О) + ^(в), (1) здесь а,Р,у,8, т], я, ^ - коэффициенты, учитывающие важность критериев (а+Р+у+5+Т1+я+4= 1)- Значения а,Р,у,5,т|,я,4 могут определяться на основе опыта конструктора или экспертных оценок. Величина Цв) - общая суммарная длина соединений, П(в ) - число пересечений проводников коммутационной схемы (КС), В(С) - суммарная длина критических связей, С(в) - суммарное число изгибов соединений, И (в) - сумма полупериметров охватывающих прямоугольников всех цепей КС, Е(О) - суммарная площадь областей, занятая цепями КС.

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

Во втором разделе приведены модифицированные методы поиска, ориентированные на размещение ТЭК ЭВА. Разработаны способы создания стартовой популяции, построения целевой функции и оценки генетического разнообразия популяции альтернативных решений. Описаны стратегии селекции (отбора) хромосом (альтернативных решений). Сделан вывод о перспективности интегрированного «жёсткого и мягкого» отбора решений. Построены поисковые алгоритмы размещения ТЭК. На рис.1, приведена упрощенная схема бионического алгоритма размещения.

Рис.1. Упрощенная схема бионического алгоритма размещения

Здесь БА, ГА и ЭА - соответственно бионический, генетический и эволюционный алгоритмы размещения, ОР - оператор репродукции, изменяющий размер популяции альтернативных решений, ЭС - экспертная система, определяющая дальнейший ход поиска.

Бионический алгоритм состоит из пяти основных блоков. БА = (ГА,ЭА,ОР,ЭС, блок останова). Тогда ЭА и ГА можно представить в следующем виде:

ЭА = (Р, N, МК, С, ЦФ, ОГР, ГУ, ОМ,ОР, G, р„ L), (2)

ГА = (Р, N, МК, С, ЦФ, ОГР, ГУ, ГО (ОК, ОМ, ОИ, ОТ, ОС, OTP, ОУ, ОВ), OP, G, р„ L). (3)

Здесь МК- метод кодирования хромосомы (альтернативного решения), С -селекция, ОГР и ГУ - ограничения и граничные условия на задачу размещения, ГО - генетические операторы, в - число генераций или поколений алгоритма, р, е Р - хромосома, а Ь- длина хромосомы.

При случайном выборе хромосом частота II образования родительских

пар не зависит от значения ЦФ хромосом Р^ и определяется размером популяции N.

К = —1— (4)

N(N-1)' 1 '

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

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

Автором предлагается БА, состоящий из четырех основных блоков. Первый - блок моделей. Здесь строятся модели монтажно-коммутационного пространства и коммутационных схем, подлежащих размещению. Второй блок - препроцессор. Здесь производится создание одной или некоторого множества начальных популяций альтернативных решений размещения. Третий блок - блок бионического поиска. Он состоит из четырех этапов: выбор микро-, макро- или метаэволюции; выбор способов кодирования альтернативных решений; определение элементов эволюции; разработка генетических операторов случайных, направленных и интегрированных преобразований входной информации; выбор моделей эволюции и способов «выживания» решений; рекомбинация решений. Четвертый блок -постпроцессор. Здесь реализуются принципы адаптации полученных решений к внешней среде (лицу, принимающему решения). Базисную структуру бионического алгоритма для решения задач размещения ТЭК ЭВА представим следующим образом:

I. Построение моделей монтажно-коммутационного пространства (МКП) и коммутационных схем (КС).

II. Препроцессор:

1. Создание начальных популяций альтернативных решений размещения ТЭК ЭВА.

2. Построение интегрированной ЦФ размещения на основе заданных ЛГТР частичных целевых функций.

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

III. Бионический поиск

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

2. Выбор способов кодирования альтернативных решений.

3. Выбор моделей эволюции и способов «выживания» решений.

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

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

6. Если заданные условия размещения выполнены, то переход к блоку IV, если нет, то к пункту 7.

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

8. Редукция, т.е. приведение размера популяции к заданному ЛПР виду.

9. Получена новая популяция альтернативных решений. Переход к следующей генерации.

IV. Постпроцессор

1. Проверка выполнения принципов бионического поиска.

2. Реализация новой генерации. В случае получения оптимального или квазиоптимального решения переход к пункту 3. Иначе - переход к блоку П1.

3. Конец работы алгоритма.

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

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

у =---<т** ~<сх N

шах ср

где ^р - среднее время работы БА; в - число генераций; N - размер популяции; - число поколений БА, прошедших до выполнения условия сходимости; ^ - ограничение на число поколений сверху < 1:тах. Очевидно, что случаю несходимости 1тах=1сх соответствует скорость, равная нулю. БА осуществляют поиск локального решения по одной стратегии для различных целевых функций. Временная сложность этих алгоритмов не выходит за пределы полиномиальной области.

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

получать оптимальные и квазиоптимальные решения в задачах размещения ТЭК ЭВА за время, сопоставимое с временем реализации итерационных алгоритмов.

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

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

Приведем алгоритм реализации оператора сегрегации с использованием кодов Хоффмана.

1. Пусть задана популяция родительских хромосом длины Ь.

2. Точки разрыва оператора сегрегации определяются на основе кодов Хоффмана.

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

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

5. Вычисляется значение ЦФ полученной хромосомы. Если полученное значение ЦФ, лучше значения ЦФ родительских хромосом, то процесс повторяется аналогично. В противном случае переход к 2.

6. Алгоритм оканчивает работу по достижению заданного критерия или когда проанализированы все строительные блоки.

Целесообразность оператора сегрегации определяется на основе вероятности его выживания. Вероятность выживания альтернативного решения с лучшим значением ЦФ после реализации оператора вычисляется по формуле:

Рг(8)[ОС]=(1-2/Ь-1)/а, (6)

а вероятность уничтожения хромосомы определяется:

Р^)[ОС]=1-Р,(8)[ОС], (7)

где а - коэффициент, определяющий зависимость Рг(в)[ОС] от размера популяции. Он принимает значение в диапазоне от 1 до N/2.

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

• ОМГ1 - обмен хромосом между популяциями;

• ОМГ2 - обмен строительных блоков хромосом между различными популяциями.

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

Приведем алгоритм размещения элементов на этапе макроэволюции:

1 ° Определение случайным и направленным образом групп хромосом для следующего шага эволюции.

2° Определение групп хромосом для обмена с выбранными в п. 1. Процедура выполняется на основе элитного отбора.

3° Экспертная подсистема размещения производит выбор операторов бионического поиска.

4° Выбор порядка реализации операторов.

5° Выбор и реализация оператора миграции

6° Проведение очередной генерации эволюционного процесса.

7° Проверка завершения поиска? Если поиск незавершен, то переход к п. 1.

8° Конец работы алгоритма.

Предлагается следующая структура алгоритма размещения элементов ТЭК ЭВА. После ввода исходных данных (блок 1 алгоритма) производится процедура факторизации - разбиения МКП на строительные блоки (СБ). Причём, для каждой ветви дерева решений предлагаются различные эвристики сжатия моделей коммутационных схем (блоки 2). Блок 3

соответствует реализации эвристик эволюционного, генетического и локального поиска. На четвертом этапе производится заполнение МКП строительными блоками. Процессу макроэволюции предшествует неитерационная процедура размещения элементов внутри СБ (блок 5). В блоке 6 на основе экспертной информации производится выбор и реализация различных операторов бионического алгоритма. Этап макроэволюции представляет собой генетическую процедуру размещения элементов ТЭК ЭВА. В ней кроме стандартных бионических процедур используются жадные эвристики (блок 7). В каждой ветви алгоритма предусматривается автономный блок окончания процесса поиска.

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

«параллельно-параллельно-последовательный» и другие варианты поиска.

Автор, считает, что перспективным при размещении, является использование комбинированных вариантов эволюции, поскольку результаты размещения получаются за время реализации одного эволюционного процесса. Временная сложность разработанных алгоритмов находится в полиномиальной зависимости от числа элементов ТЭК и ориентировочно равна (О(п^п)-О(п3).

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

3000 связей, время решения составило 162 секунды, а отношение условного начального значения ЦФ к конечному результату равно 0,54. При этом получены следующие параметры бионического поиска: размер популяции -10, число генераций - 500, вероятности применения генетических операторов - кроссинговера (0,8), мутации (0,9), сегрегации (0,1). Приведен интерфейс программы, построены таблицы, графики и гистограммы, показывающие преимущества разработанных алгоритмов. Из приведенных статистических данных следует, что в общем случае время решения линейно зависит от количества генераций алгоритма. Временная сложность алгоритмов, полученная экспериментально, подтверждает теоретические предпосылки и ориентировочно равна 0((п^п) - (п3)). Отметим, что разработки автора дают лучшие решения по качеству на 10% - 20% при одинаковом или незначительном увеличении времени работы.

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

В приложении даны копии актов внедрения.

Заключение

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

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

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

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

вероятность «выживания» альтернативных решений с лучшим значением ЦФ.

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

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

7. Проведены серии тестов и экспериментов, выполнена обработка экспериментальных данных, что позволило уточнить теоретические оценки временной сложности алгоритмов размещения. Проведенные исследования показали улучшение работы предложенных алгоритмов по сравнению с известными методами. Улучшение составило по качеству от 15% до 25%, а по времени от 10% до 20% в зависимости от вида моделей коммутационных схем и монтажно-коммутационного

г пространства.

I Список используемых источников

1. Мищенко М.Н. Операторы мутации в эволюционных алгоритмах размещения. Перспективные информационные технологии интеллектуальные системы, №4 (16), 2003, с.130-135.

2. Курейчик В.В., Мищенко М. Н. Бионический метод определения путей оптимальной длины в графовых моделях. Материалы 1П-го Международного научно-практического семинара "Интегрированные модели и мягкие вычисления в искусственном интеллекте. М: Изд-во Физматлит, 2005, с. 261-266.

3. Мищенко М.Н. О размещении элементов схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №4 (20), 2004, с. 101-107.

4. Курейчик В.В., Мищенко М.Н. Бионический алгоритм размещения элементов. Известия ТРТУ,№4, 2005, с.42-48.

А

2007-4 4173

5. Мищенко М.Н. Модели КОММуТаЦИОННОГО Прис l pan v i oa и LACM JDA Перспективные информационные технологии интеллектуальные системы, Xsl (21), 2005, с.36-42.

6. Мищенко М.Н. Бионический метод размещения элементов схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (22), 2005, с.34-36.

7. Курейчик В.В., Мищенко М.Н. Построение архитектуры комбинированного поиска для размещения элементов ЭВА. IEEE AIS-05, CAD-2005. Интеллектуальные системы, интеллектуальные САПР т.1, М.: Физматлит, 2005, с 56-64.

В работах, опубликованных в соавторстве, автору принадлежат следующие результаты: [2] - алгоритм определения путей оптимальной длины в графовых моделях; [4] - бионический алгоритм и результаты вычислительного эксперимента; [7] - методы кодирования альтернативных решений задачи размещения.

/М.Н. Мищенко/

ВВЕДЕНИЕ.

1. Анализ задач размещения при автоматизированном проектировании типовых элементов конструкций ЭВА.

1.1. Постановка оптимизационной задачи размещения.

1.2. Построение математических моделей монтажного пространства для задачи размещения.

1.3. Анализ методов размещения типовых элементов конструкций ЭВА.

1.4. Выводы.

2. Теоретические исследования эволюционных и генетических алгоритмов ориентированных на размещение элементов ЭВА.

2.1. Построение архитектуры комбинированного поиска для размещения элементов ЭВА.

2.2. Разработка стратегии и принципов размещения элементов в бионических алгоритмах.

2.3. Построение генетических операторов, ориентированных на решение задачи размещения ТЭК ЭВА.

2.4. Выводы.

3. Построение бионических алгоритмов размещения типовых элементов конструкций ЭВА.

3.1. Разработка бионических алгоритмов параллельного размещения.—

3.2. Размещение элементов КС на основе анализа коротких цепей.

3.3. Комплексные методы размещения ТЭК ЭВА.

3.4. Выводы.

4. Результаты вычислительного эксперимента при исследовании разработанных алгоритмов.

4.1. Цель и основные задачи построения программного обеспечения для решения задач размещения.

4.2. Описание программной оболочки.

4.3. Результаты экспериментальных исследований на стандартных и тестовых задачах.

4.4. Выводы.

Методы автоматизированного проектирования, конструирования и технологической подготовки производства позволяют создавать высоконадёжные СБИС и ССБИС в короткие сроки и при сравнительно низких затратах. Тенденция к росту степени интеграции СБИС «проблема проклятия размерности», приводит к увеличению трудоёмкости автоматизированного проектирования и конструирования [1-30].

Построение современных ЭВА на основе СБИС и ССБИС выдвигает проблему эффективной реализации межсоединений (коммутационных соединений) на всех уровнях на первый план. Одним из основных этапов автоматического или автоматизированного проектирования СБИС является этап конструкторского проектирования, который включает в себя следующие стадии: типизация, компоновка, размещение, планирование кристалла, сжатие, трассировка и верификация [20-30].

В общей проблеме автоматизации конструкторского проектирования ЭВА одной из важнейших является задача размещения узлов низшего уровня в узлах высшего уровня. Задачи размещения элементов тесно связаны с последующими этапами сжатия, трассировки соединений и верификации схем. Поэтому основной целью задачи размещения считают создание наилучших условий для последующих этапов сжатия, трассировки соединений и верификации схем при выполнении заданных ограничений и граничных условий, обеспечивающих эффективную работоспособность схем [15-20].

Задача размещения не может рассматриваться, как частная, локальная она должна решаться с учетом компоновки блоков будущей трассировки, т.е.: в рамках системного и синергетического подходов [31-39].

Задачи конструкторского проектирования и в частности размещение элементов принадлежат к классу оптимизационных задач [10-30,40-49].

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

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

В этой связи, разработка новых бионических методов и алгоритмов размещения элементов СБИС и СБИС, позволяющих найти эффективное по качеству, трудоёмкости и времени работы ЭВМ решения, является АКТУАЛЬНОЙ ПРОБЛЕМОЙ.

ЦЕЛЬЮ диссертационной работы является разработка бионических методов и алгоритмов для решения задачи размещения блоков ЭВА.

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

• построение моделей коммутационной схемы и монтажного пространства для анализа и преобразования данных при размещении элементов схем ЭВА;

• разработка принципов и механизмов распределения элементов схем ЭВА по макрообластям на основе списковых и стековых представлений с целью оптимизации заданных критериев качества;

• построение новых архитектур бионического поиска ориентированных на решение задач размещения;

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

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

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, графов, алгоритмов, комбинаторной оптимизации и эволюционного моделирования.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:

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

• предложена новая архитектура бионического поиска : для распараллеливания процесса размещения элементов схем ЭВА;. .„

• разработаны новые бионические алгоритмы размещения, основанные на выделении клик и ядер графа.

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

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

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

• модифицированные генетические операторы, ориентированные на знания о решаемой задаче размещения, позволяющие сокращать время поиска ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы определяется созданием комплекса программ размещения элементов на различных иерархических уровнях, позволяющих использовать новые архитектуры, принципы и эвристики размещения, отвечающие конкретным конструктивным и технологическим ограничениям.

Программная среда отвечает конкретным задачам управления жизненным циклом продукции при размещении элементов схем ЭВА. При построении комплекса программ использовались пакеты С++, Builder, Visual С++. Отладка и тестирование проводилось на ЭВМ типа IBM PC с процессором Pentium-IV с ОЗУ-512М6. Проведенный вычислительный эксперимент, показал преимущество бионических алгоритмов для решения задач размещения элементов и блоков ЭВА, по сравнению с известными методами. Разработанные алгоритмы размещения позволяют получать набор квазиоптимальных альтернативных решений за полиномиальное время. .

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском государственном радиотехническом университете: грант .РФФИ

Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов, принятия решений». Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле лекций и практических занятий по. курсам «автоматизация конструкторского и технологического проектирования».

Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».

Апробация основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на международных научно-технических конференциях «Интеллектуальные САПР» (г. Дивноморск 20022005гг.), на международной конференции «Интеллектуальные системы» (г.Дивноморск, 2004, 2005гг.), на научных семинарах Северо-Кавказкого научного центра высшей школы (г. Ростов-на-Дону, Таганрог, 2003, 2004г.г.).

Публикации. Результаты диссертации отражены в 6 печатных работах.

Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх разделов, заключения, списка литературы и приложения. Работа содержит 135 стр., а также 36 рис., расположенных на 23 стр., список литературы из 109 наименований, 2 стр. приложений и актов об использовании. .

4.4. Выводы

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

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

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

Заключение

1. Сформулирована стратегия бионического поиска решений : при размещении коммутационных схем ЭВА. Приведена классификация оптимизационных задач размещения.

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

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

4. Описаны модифицированные эволюционные и генетические операторы, ориентированные на решения задач размещения ТЭК ЭВА. Проанализированны новые и модифицированные операторы мутации. Их использование в задачах размещения увеличивается вероятность «выживания» альтернативных решений с лучшим значением ЦФ,; и каждая новая генерация генетических алгоритмов приводит к сокращению интервала неопределенности.

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

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

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

1. Колчин А.Ф. и др. Управление жизненным циклом продукции. М.: Анархасис, 2002.

2. Ли К. Основы САПР (CAD/CAM/CAE). СПб. Литер,2004.

3. Норенков И.П. Принципы построения и структура САПР. М.: Высшая школа, 1986.

4. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. CALS-технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

5. Норенков И.П. Основы автоматизированного проектирования. -М.: Изд-во МГТУ имени Н.Э.Баумана, 2000.-360с.

6. Евгеньев Г.Б. и др. CASE- технология создания многоагентных САПР изделий машиностроения. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 41-46.

7. Справочник конструктора РЭА. Общие принципы конструирования. Под ред. Р.Г. Варламова. М.: Советское радио, 1980.

8. Справочник по САПР. Под ред. В .И. Скурихина. Киев.: Техника, 1988.

9. Справочник. Системы автоматизированного проектирования в радиоэлектронике. Под ред. И.П. Норенкова. М.: Радио и связь, 1986.

10. Автоматизированное конструирование монтажных плат РЭА. Справочник специалиста/ под ред. Л.П. Рябова. М.: Радио и связь, 1986.

11. Грувер М., Зимерс Э. САПР и автоматизация производства. М.: Мир, 1987.

12. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат, 1987.

13. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио, .и связь, 1990.

14. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983.

15. Гридин В.Н. Теоретические основы построения базовых адаптируемых компонентов САПР МЭА. М.: Наука, 1989.

16. Ойхман Е.Г. Графические системы для СМ ЭВМ. М.: НаукаД986

17. Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

18. Бершадский А.М. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во СГУ, 1993.

19. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.

20. Physical Design Automation of VLSI Systems. Edited by T. Preas and M. Lorenzetti. BCPC, Inc. USA: Menlo Park, 1988.

21. Малышев Н.Г., Мицук H.B. Основы оптимального управления процессами автоматизированного проектирования. М.: Энергоатомиздат, 1990.

22. Мелихов А.Н., Берштейн JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

23. Эйрис Р. Проектирование СБИС. М.: Наука,1988.

24. Чичварин Н.В. Экспертные компоненты САПР. М.: Машиностроение, 1991.

25. Морозов К.К. и др. Методы разбиения схем РЭА на конструктивно законченные части. М.: Советское радио,1978.

26. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций РЭА. М.: Радио и связь, 1983.

27. Селютин В.А. Машинное конструирование электронных устройств. М.: Сов. Радио, 1979.

28. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом.- М.: Радио и связь, 1987.

29. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

30. Баталов Б.В., Щемелинин В.М. Проектирование топологии интегральных схем на ЭВМ. М.: Машиностроение, 1979.

31. Современная прикладная теория управления: Оптимизационный подход в теории управления/ Под ред. A.A. Колесникова. Таганрог: Изд-во ТРТУ,2000.4.1.

32. Современная прикладная теория управления: Синергетический подход в теории управления/ Под ред. A.A. Колесникова. Таганрог: Изд-во ТРТУ,2000.4.2.

33. Современная прикладная теория управления: Новые классы регуляторов технических систем/ Под ред. A.A. Колесникова. Таганрог: Изд-во ТРТУ,2000.4.3.

34. Садовничий В.А. и др. Устойчивость глобального развития и хаотичность региональных явлений в нелинейных динамических процессах. Синергетика// Труды семинара. Том 3. М.: Изд-во МГУ, 2000, с.5-39.! ,

35. Пригожин И., Стенгерс И. Время, хаос, квант. К решению парадокса времени. М.: Эдиториал УРСС,2000.

36. Моисеев H.H. Современный рационализм. М.: МГВП Кокс, 1995.

37. Лоскутов А.Ю., Михайлов A.C. Введение в синергетику. М.: Наука, 1990,

38. Пригожин И. От существующего к возникающему. М.: Наука, 1985.

39. Хакен Г. Синергетика. Иерархия неустойчивостей в самоорганизующихся системах и устройствах. М.: Мир, 1985.

40. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМО,2000.

41. Панадимитриу X., Стайниц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1983.

42. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вищашк., 1981.

43. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов на-Дону. Изд-во РГУ,1981.

44. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990.

45. Петренко А.И., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры (топологический подход). Киев: Вищашк., 1980.

46. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

47. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во ВГУ, 1997.

48. Курицкий Б.Я. Оптимизация вокруг нас. Л.: Машиностроение, 1989.

49. Алексеев О.В. и др. Автоматизация проектирования радиоэлектронных средств. М.: Высшая школа,2000.

50. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит,2003.

51. Holland John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

52. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

53. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991.

54. Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики. М.: Изд-во ТВП, 1966.

55. Батищев Д.А. Генетические алгоритмы решения экстремальных задач. Воронеж: Изд-во ВГТУ, 1995.

56. Курейчик В.М. Генетические алгоритмы и их применение: Монография. -Таганрог: Изд-во ТРТУ, 2002.

57. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. -Таганрог: Изд-во ТРТУ, 2001.

58. Курейчик В.М. Генетические алгоритмы. Обзор и состояние. Новости искусственного интеллекта, №3, 1998, с. 14-64.

59. Mazumder P., М. Rudnic. Genetic Algorithms For VLSI Design, Layout & Test Automation. PE, Inc. Singapore, 1999.

60. Курейчик В.М. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН, Москва, N 1, 1999, с.144-160.

61. Practical Handbook of Genetic Algorithms. Editor I. Chambers. ; T.l, Washington, USA, CRC Press, 1995.

62. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.2, Washington, USA, CRC Press, 1995.

63. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.3, Washington, USA, CRC Press, 1999.

64. Гладков JI.A., Курейчик B.B., Курейчик В.М. Генетические алгоритмы. / под ред. В.М. Курейчика. Учебное пособие. Ростов на - Дону: Ростиздат,2004.

65. Мищенко M. Н. Модели коммутационного пространства и схем ЭВА Перспективные информационные технологии интеллектуальные системы, №1 (21), 2005, с.36-42.

66. Сороколетов П.В. Коммутационные модели блоков ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (18), 2004, с.46-53. .

67. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

68. Андерсон Д. Дискретная математика и комбинаторика. М.: Вильяме, 2003.

69. Кузнецов О.П. Дискретная математика для инженера. СПб.: Лань, 2004,

70. Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001.

71. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

72. Мищенко М. Н. О размещении элементов схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №4 (20), 2004, с.101-107.

73. Петренко А.И. Тетельбаум А.Я. Модели электронных устройств при решении конструкторских задач. Кибернетика,№2,1978, с.47-54.

74. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 133-138.

75. Davis L. Genetic Algorithms and Simulated Annealing. San Mateo, USA, Morgan Kaufman Publisher, 1987.

76. De Jong K. Evolutionary Computation: Recent Development and Open Issues. Proceedings 1st International conf., Evolutionary Computation and Its Application, EvCA 96, Moscow, 1996, pp.7-18.

77. Kureichik V.V., Kureichik V.M., Genetic Algorithms. HG Verlag, Konstans, 2004.

78. Мищенко M. H. Бионический метод размещения элементов схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (22), 2005, с.34-36.

79. Никифоров A.M. Оценка качества размещения. // Известия ТРТУ №;3, 1999. стр. 206-209.

80. Barjee Р М. Jones. A Parallel Simulated Annealing Algorithm for Standart Cell Hyper Cube Computer. // Proc. Int Conf. on CAD 1986, pp. 156-159., :

81. Eisemann H. and Johannes F.M. Generic global placement and floor planning. // in Proc IEE/ACM Int Conf CAD 1998 pp. 269-274.

82. High Performance Cluster Computing; под ред. Rajkumar Buyya (Monash University, Australia); Prentice Hall; 1999.

83. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики// Составление Д.Г. Лахути, В.Н. Садовского, В.К. Финна. М.: Эдиториал УРСС, 2000.

84. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

85. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10, Москва, 2001, стр.174-187.

86. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4,1993, с.24-67.

87. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. -М.: Эдиториал УРСС, 2002. -352с.

88. Нильсон Н. Принципы искусственного интеллекта.- М: Радио и связь, 1985. 376 с.

89. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. М.: Изд-во МГТУ, 2002.

90. Курейчик В.В., Курейчик В.М. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1, М.: Физматлит, 2003, с 59-67.

91. Редько В .Г. Эволюционная кибернетика. -М.: Наука, 2001. . ,

92. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов// Приложение к журналу Информационные технологии, №12, 2000.

93. Скурихин А.Н. Генетические алгоритмы// Новости искусственного интеллекта, М., №4,1995,с.6-46.

94. Мищенко М. Н. Операторы мутации в эволюционных алгоритмах размещения. Перспективные информационные технологии интеллектуальные системы, №4 (16), 2003, с. 130-135.

95. Kling R.M., Banerjee P.: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, 1989. pp. 245-256.

96. Kling R.M. and Banerjee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standard Cell Placement. IEEE Trans, on CAD, Vol.10, No. 10, 1991. pp. 1303-1315.

97. Potts C.I., Giddens T.D., Yadav S.B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial selection. IEEE Trans, on Systems, Man and Cybernetics, vol.24, No.l, 1994, pp. 73 -86.

98. Shahookar K.,Mazmunder P. A Genetic Approach to standard Cell Placement Using Meta-Genetic Parameter Optimization. IEEE Trans, on CAD, Vol.9, No.5, 1990, pp. 500-511. :

99. Cohoon J.P., Paris W.D. Genetic Placement, IEEE Trans, on CAD, Vol.6, No 6, November, 1987. pp. 956 964.

100. Курейчик B.M. Курейчик В.В. Генетический алгоритм размещения графа// Известия АН. Теория и системы управления, № 5, 2000, с.67-74.

101. Kureichik V.M, Kureichik V.V. Genetic Algorithm for Graph Placement Journal of Computer and Systems Sciences International,vol.39, №5, 2000, pp.733-740.

102. Попов Э. В. и др. Статические и динамические экспертные системы. М.: Финансы и статистика, 1996. , ;

103. Курейчик В.В. Программная подсистема по исследованию оптимизационных задач на графах. Программные продукты и системы. №1,2002 с.26-28.