автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование генетических алгоритмов решения задач компоновки элементов и трассировки СБИС

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ КОМПОНОВКИ ЭЛЕМЕНТОВ И ТРАССИРОВКИ

СБИС

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

АВТОРЕФЕРАТ

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

Ростов-на-Дону - 2006

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

заслуженный деятель науки РФ, доктор технических наук, профессор Чернышев Ю.О.

д-р техн. наук, проф. КурсПчик И.П. д-р техн. наук, проф. Витиска Н.И.

Федеральное Государственное унитарное предприятие Таганрогский НИИ связи (г. Таганрог)

Защита состоится 2/л/^с^^ 2006 года в часов на

заседании диссертационного совета Д 212.259.03 при Таганрогском государственном радиотехническом университете по адресу: 347928, г.Таганрог, пер. Некрасовский, 44, ауд. Д-406

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

Автореферат разосланI 2006 г.

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

Официальные оппоненты:

Ведущая организация:

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

Целых А.Н.

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

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

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

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

Цель и задачи исследования. Целью диссертационной работы является разработка и исследование эффективных поисковых и генетических алгоритмов для решения задач компоновки элементов и трассировки СБИС.

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

1. Построение архитектур генетического поиска, ориентированных на решение задачи компоновки элементов и трассировки СБИС;

2. Разработка и исследование генетических алгоритмов компоновки и группирования элементов СБИС, позволяющие получать локально-оптимальные решения за полиномиальное время;

3. Разработка генетического апп'ритма трагунровки СБИС путём построения дерева Штейнера; { р0с- национальная!

i библиотека | !

4. Разработка модифицированных генетических операторов

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

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

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

1. Разработаны архитектура и стратегии эволюционного и генетического поиска;

2. Разработаны генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать наборы локальных оптимумов;

3. Разработан алгоритм генетического поиска для построения дерева Штейнера;

4. Построены модифицированные генетические операторы кроссинговера и мутации.

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

На защиту выносятся:

1. Архитектура и стратегии эволюционного и генетического поиска, ориентированные на решение задач компоновки элементов и трассировки СБИС;

2. Алгоритм компоновки элементов СБИС;

3. Алгоритм группирования элементов СБИС;

4. Алгоритм трассировки соединений для построения дерева Штейнера;

5. Модифицированные операторы кроссинговера и мутации.

Реализация результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работах Ростовской государственной академии сельскохозяйственного машиностроения(РГАСХМ) на кафедре "Прикладная математика и вычислительная техника"(ПМ и ВТ) по заказу Минобрнауки РФ по темам: 'Теория поисковой адаптации для решения комбинаторных задач оптимиза-ции"(01.01.2003 - 31.12.2004г.г.) и "Теория интеллектуальных процедур по-

иска оптимальных решений"(01.01.2005 - 31.12.2005 г.г.), а также при проектировании и эксплуатации автоматизированных систем контроля и диагностики радиоэлектронной аппаратуры в НИИ специальных информационно-измерительных систем НИИСИИС (г. Ростов-на-Дону). Кроме того, материалы диссертации используются в учебном процессе на кафедре "ПМ и ВТ" РГЛСХМ при чтении лекций по дисциплинам "Дискретная математика" и "Программные средства САПР".

Основные положения, выносимые на защиту:

1. Архитектура генетического поиска ориентированная на решение задач компоновки элементов и трассировки СБИС;

2. Модифицированные генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать локально-оптимальные решения за полиномиальное время.

3. Генетический алгоритм трассировки СБИС, позволяющий получать наборы локально-оптимальные решений.

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях "Интеллектуальные системы "(Л 15-05) и "Интеллектуальные САПР"(САО-2005) (г. Геленджик 2005 г.), на VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (КРЭС'04) (г.Таганрог 2004 г.), на региональных научно-технических конференциях "Проблемы современного машиностроения"(г. Ростов-на-Дону. РГАСХМ, 2005,2004 г.г.)

По материалам диссертационной работы опубликовано 6 работ, материалы вошли в два отчета по НИР.

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

Структура и объём диссертационной работы. Диссертация состоит из введения, 4 глав, заключения, списка использованной литературы и приложения. Объем диссертации 132 страниц, 47 рисунков, 16 таблиц и списка литературы из 100 наименований. В приложении вынесены акты об использовании и внедрении результатов диссертационной работы.

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

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

генетические операторы, существующие алгоритмы и методы решения задач компоновки и трассировки СБИС.

На основании проведённого анализа генетических операторов и алгоритмов сделаны выводы о необходимости разработки новых более эффективных генетических операторов и алгоритмов компоновки и трассировки СБИС.

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

Выход

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

Третий блок - блок генетического поиска:

• выбор представления решения;

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

• определение закона выживания;

• рекомбинация.

Четвертый блок называется постпроцессором. Здесь реализуются принципы адаптации полученных решений к внешней среде. Это обобщенная горизонтально организованная архитектура генет ического поиска при компоновке элементов и трассировки СБИС. Ее преимуществом является то, что в ней все уровни связаны с уровнем внешней среды и могут общаться между собой.

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

Сформулирована постановка задачи компоновки СБИС, как 1адача разбиения гиперграфа схемы на заданное или произвольное число частей Построена структурная схема разбиения гиперграфа на части на основе рассмотренной выше архитектуры эволюционного поиска (рис. 2) Здесь в первом блоке строится начальная популяция решений, т.е. определяв iui заданное подмножество В,, В2, ..., Bk (k < s). В качестве обьективной функции (fitness) выбираем К. Критерии К (число связей между частями разбиения) и М (количество связей) являются взаимообратными, т.е. минимизация К максимизирует М и наоборот. Для каждого элемента текущей популяции вычислим К и определим Кср- среднее значение объективной функции на данной популяции. На рис 2. блок 2 формирует начальную популяцию, состоящую из двух родительских хромосом, затем блок 3 осуществляет вычисление ЦФ. Блок 4 осуществляет выполнение оператора кроссинговера описанного выше, блок 5 осуществляет проверку условия полученных потомков по ЦФ. Если условие не выполняется, то осуществляется селекция популяции (блок 6) и осуществляется муоция (блок 7). Если условие выполняется то алгоритм заканчивает работу. Далее вычисляется ЦФ и проверка условия. F-сли условие выполняется то алгоритм заканчивает работу, если условие не выполняется, то осуществляется селекция и переход на выполнение оператора кроссинговера. Простейшим случаем селекции может являться

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

Рассмотренный пример разбиения гиперграфа на части основан на структурной схеме АЦП последовательного приближения(действия).

Определена трудоёмкость алгоритма компоновки. Пусть ^ - размер популяции, >!„ - количество полученных потомков, - количество генераций генетического алгоритма. Тогда общая трудоёмкость алгоритма ориентировочно определяется как

Т «[ ^ 1р + К + (Ыр + мп) у где - трудоёмкость построения одной индивидуальности в популяции; 1П -трудоёмкость генерации одного потомка; ^ - трудоёмкость селекции. При этом 1, 2, 3, 4. Однако, = 1, если в алгоритме после применения оператора кроссинговера будет иметь место все четыре варианта соединения хромосомы в одну строку, при использовании двоичного кода либо количество вершин графа, как показано в данном примере. Трудоёмкость построения одной индивидуальности может колебаться от О(п) до 0(п!), а трудоёмкость генерации одного потомка зависит от сложности применяемого генетического оператора кроссинговера и ориентировочно изменяется от О(п) до О(п^п). Трудоёмкость селекции может изменяться от О(п) до 0(п2).

Вероятность получения оптимального решения при случайной генерации индивидуума может быть определена

р(0 ~ Н,ок/ N06,,,,

где Млок - количество удовлетворительных решений (локальных оптимумов). п - размер индивидуальности (хромосомы), Ыонш - общее количеств решений. Причем N„6,,, может быть равно п!.

На основании рассмотренного показано, что сложность описанного алгоритма ориентировочно составляет от О(п) ло П(п1) для одной генерации

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

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

Рис. 3. Структура алгоритма группирования элементов СБИС. хромосомы(начальную популяцию), которые будут соответствовать всем столбцам матрицы, и при этом в любом случае будет получено лучшее решение.

Трудоёмкость алгоритма определяется как :

где. 10к - трудоёмкость ОК, а 1С1Ы, - трудоёмкость операции склеивания.

Временная сложность алгоритма (ВСА) для одной генерации меняется о г О(п) до 0(п1о§п).

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

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

иначе переход на выполнение оператора кроссинговера. Для решения данной задачи необходимо определить метрику - способ вычисления расстояния между двумя точками в монтажном пространстве. Наиболее часто используется ортогональная метрика, при которой расстояние определяется

как с1ц = |<3, — ^ | + — У} |, где х„ х} - расстояние между точками

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

Предлагается алгоритм построения дерева Штейнера. Входными данными алгоритма будет количество точек на КП, которые строятся случайным образом. Строится начальная популяция, состоящая из 4-х хромосом, по две хромосомы для каждого родителя. Начальная популяция строится случайным образом. Далее применяется оператор кроссинговера После применения оператора кроссинговера оцениваются полученные хромосомы, т.е. вычисляется длина между каждыми точками и строится дерево Штейнера. На рис. 4. приведена структурная схема алгоритма построения ДШ.

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

Ориентировочная трудоёмкость алгоритма определяется:

Т = tk + [Np t„ + (Np + N„) ^ ь Np tc] Ng, где, t|¡ - трудоёмкость кодирования ДШ, tn - трудоёмкость получения одного потомка, Np - количество потомков. Отметим, что трудоёмкость получения одного потомка меняется в пределах О(п) 0(п2) и ВСА для разработанного алгоритма генетического поиска ДШ определяется как 0(ап2), где а - коэффициент, определяющий специфику генетического поиска.

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

Рассмотрим оператор кроссинговера при построении хромосомы в две строки. На рис. 5, показано как расположена хромосома в генетических операторах и в клетке. Для определения принадлежности генов верхнему или нижнему рядам введём двух индексные обозначения (см. рис.5).

i о i i о i о i i о

110010« I О I

А, Л,

в

О 0 1 1 I I О О I 1

I ООО 1 1 1 и о

В, в,

Рис. 5. Представление двух хромосом.

Рассмотрим работу оператора кроссинговера. Точка разрыва выбирается случайным образом. В результате работы кроссинговера мы получим некоторое количество потомков, например А|' и В',, показанных на рис. 6 Если точка разрыва совпадает в обеих хромосомах, то возможно большее количество полученных потомков. При построении хромосомы в одну строку ( для вычисления двоичного кода) возможны 4-е варианта соединений, показанных на рис. 7 для хромосомы Л',.

А',

1 I ООО ! О 1 1 0

10I1I00I01

В',

1000 1110 11

0011110110

Рис. 6. Полученные потомки.

1010 01 1 101 1 100010110 0 110 10 0 0 1110 1110 0 10 1

10111001011100010110 11000101101011100101

Рис. 7. Соединение хромосом в одну строку(нить).

Применение оператора кроссинговера увеличивает популяцию альтернативных решений, что позволит повысить вероятность получения "лучшего" решения. При построении хромосомы в одну строку ( для вычисления двоичного кода) возможны 4-е варианта соединений , для каждой хромосомы.

В случае если, построить все хромосомы в одну строку, то вероятность получения лучшего решения существенно возрастёт. Точка разрыва (точка кроссинговера) будет определяться случайно, но будет одинакова в обеих частях хромосомы. Соединение хромосомы в одну строку будет сопровождаться несколькими вариантами соединений.

При таком представлении простой оператор кроссинговера будет работать как многоточечный. Разработанный оператор кроссинговера назовём естественным простым оператором кроссинговера. Естественный, потому - что данное представление хромосом в две строки является общеизвестным представлением хромосомы в клетке живого организма, в частности, как у человека. Простой, потому - что в процессе оплодотворения участвуют всего две хромосомы (по одной от каждого родителя).

При представлении двух пар родительских хромосом ог каждого родителя, будет являться одноточечный оператор кроссинговера. Случайным образом составляются отцовские и материнские клетки. Каждая клетка состоит из двух хромосом. Гены представляются двоичным кодом. Далее определяется точка кроссинговера (х), точка определяется также случайным образом. На рисунках маленькими буквами обозначены хромосомы материнские, большими - отца. Рассмотрим его работу на ад\х клетках, каждая клетка состоит из двух хромосом, как показано на рис.8

X X

10 10 1 110 0 0

10 111 0 0 0 0 1

А1 А2

0 0 11 0 110 0 1

10 0 0 0 11111

а1

а2

0 110 0 10 1 1 0 В1 0 0 1111 110 1 ы

10 0 1110 1 0 0 В2 10 0 111 10 10 Ь2

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

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

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

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

На рис.9 показано как располагается хромосома в два ряда до применения оператора мутации.

1

10 110 0 10 11

0 10 1I10 0 0 1

в

А,

I

1П0101М1

0 0 0 1 10 10 1 I

В,

Рис. 9. Представление двух хромосом до мутации.

На рис.9 показаны хромосомы до мутации, стрелкой показано расположение мутируемых генов. Точка мутации определяется случайным образом, и изменяется от одной хромосомной пары к другой. На рис. 10 показаны хромосомы после мутации.

В рассмотренном операторе построение хромосомы в одну строку осуществляется, также как описано выше.

А'

10 110000 11

0 10 1111001

В'

1 1 1 000 111 1

000 100 10 11

Рис. 10. Хромосомы после мутации Оператор мутации, а именно точечная мутация будет работать как двухточечный оператор мутации, и при этом мутация является симметричной. Так как расположение мутируемых генов совпадает в обеих частях хромосомы. Соединение хромосомы в одну строку можно осуществлять только начиная с верхней части и заканчивая последним геном нижней, т.е. нижняя строка является продолжением верхней. Данный оператор му!ации назовём естественным простым оператором мутации.

Рассмотрим оператор мутации при представлении двух пар родительских хромосом, по две хромосомы от каждого родителя, с представлением хромосом в две строки. Здесь оператором мутации является одноточечная мутация, мутируемые гены находятся в верхней и нижней частях хромосомы и точка разрыва совпадает в обеих частях. На рис. 11 показаны хромосомы каждого из родителей до мутации. Точка мутации выбирается случайным образом, но совпадает в обеих частях хромосомы. После мутации хромосомы будут иметь вид показанный на рис. 12. >

10 10 1110 0 0

1 011 1 О О 0 О 1

0 110 0 10 1 10

10 0 I I 10 10 0

А1 А2

В1 В2

0 0 1 10 1 10 0 1

10 0 0 0 11 1 11

1

0 0 111 1 110 1

10 0 11 1 10 10

а1

а2

Ы

Ь2

Рис. 11. Представление двух хромосом родителей до применения оператора мутации.

1 0 1 0 0 1 10 0 0 0 0 0 10 1 10 0 1

А' 1 0 1 1 0 0 0 0 0 1 а' 10 10 0 1 1 1 1 1

В' 0 1 1 0 0 1111 0 Ь' 0 0 111 1110 1

1 0 0 111110 0 10 0 11 11110

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

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

Если будет иметь место (для данного оператора) все четыре варианта со- i

единения хромосомы в одну, то получим больше решений, т.е. увеличится вероятность получения лучших или оптимальных решений в зависимости от требований конкретной задачи, что позволит уменьшить количество итера- '-

ций алгоритмов, используемых предлагаемые операторы.

Разработанный оператор мутации назовём естественным оператором мутации.

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

В четвертой разделе описаны результаты вычислительных экспериментов. Приведены качественные и количественные оценки разработанных алгоритмов компоновки, группирования и трассировки СБИС По результатам вычислительных экспериментов уточнены оценки временной сложности разработанных алгоритмов. Произведено сравнение результатов, полученных разработанными алгоритмами, с существующими. Описаны структурные схемы программной реализации разработанных алгоритмов. Программная среда реализована на языке Turbo Pascal 7.0 в среде Windows.

Тестирование и экспериментальные исследования проводились на основе сравнения известных данных в виде таблиц раннее исследованных алгоритмов компоновки элементов и трассировки СБИС. Разработаны программы для предложенных алгоритмов на языке Turbo Pascal 7.0 в среде Windows, программы совместимы с операционными системами семейства Windows. Для эксперимента использовались следующие аппаратные средства: Intel(R) Pentium(R) 4 2.4 ГГц, 512 Mb DDR-333.

Предложенные алгоритмы дают улучшение по качеству 10%. а по времени работы алгоритмов 15%. Например, для тестовой схемы алгоритмов трассировки, при построении ДШ состоящего из 90 точек, улучшение по качеству составило 10%, а по времени 15%.

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

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

Заключение.

1. Сформулированы стратегии и построена архитектура эволюционного поиска, ориентированные на решение задач компоновки элементов и трассировки СБИС.

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

3. Разработан модифицированный генетический алгоритм трассировки СБИС построением дерева Штейнера на основе предложенных генетических операторов, позволяющий работать с задачами большой размерности.

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

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

6. Проведены экспериментальные исследования и обработка экспериментальных данных, что позволило уточнить теоретические оценки, временной сложности предложенных генетических алгоритмов компоновки элементов и трассировки СБИС. Проведённые исследования показали улучшение работы предложенных алгоритмов но сравнению с известными методами. Улучшение по качеству составило 10%, а по времени 15% в зависимости от количества вершин(точек - для трассировки).

7. Построена программная среда на языке Turbo Pascal 7.0 для решения и исследования генетических алгоритмов компоновки, группирования элементов и трассировки СБИС.

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

1. Ищенко С.Н. Об одном генетическом алгоритме. VII Всероссийская научная конференция студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (КРЭС '04). Тезисы докладов. Таганрог, ТРТУ, 2004 г., с.96-97.

2. Ищенко С.Н. Эффективные генетические операторы. Труды международных научно-технических конференций "Интеллектуальные системы(А18'05)" и "Интеллектуальные САПР (CAD'05)". Научное издание в 4-х томах. М.: ФИЗМАТЛИТ, 2005, Т. 4. - с. 63-64.

3. Ищенко С.Н. Новый подход к построению генетических операторов. Труды

международных научно-технических конференций "Интеллектуальные системы(А18'05)" и "Интеллектуальные САПР (САГ)'05)" Научное издание в 4-х томах. М.: ФИЗМАТЛИТ, 2005, Т. 4. - с. 64-69.

4. Ищенко С.Н., Чернышев Ю.О. Алгоритм компоновки элементов СБИС. Труды международных научно-технических конференций "Интеллектуальные системы(А18'05)" и "Интеллектуальные САПР (САО'05)". Научное издание в 4-х томах. М.: ФИЗМАТЛИТ, 2005, Т. 4. - с. 69-72.

5. Ищенко С.Н. Генетический алгоритм группирования элементов. Сборник трудов "Повышение эффективности систем управления и связи". Ставрополь: Минобороны, Ставропольское высшее военное авиационно - инженерное училище (военный институт). 2006 г, с. 36-38.

6. Ищенко С.Н. Генетический алгоритм трассировки соединений. Сборник трудов "Повышение эффективности систем управления и связи". Ставрополь: Мин.обороны, Ставропольское высшее военное авиационно - инженерное училище (военный инсттуг). 2006 г., с. 38-40.

ЛОШ

«2- 6 9 6 4

%

u

у

Содержание.

Введение.

1. Обзор и анализ генетических алгоритмов для решения задач проектирования БИС.

1.1. Генетические операторы.

1.2. Генетические алгоритмы компоновки элементов СБИС.

1.3. Алгориты трассировки СБИС.

1.4. Выводы.

2. Разработка архитектуры и стратегии генетического поиска генетических алгоритмов компоновки, группирования элементов и трассировки СБИС.

2.1. Архитектура и стратегии.

2.2. Генетический алгоритм компоновки.

2.3. Генетический алгоритм группирования элементов.

2.4. Генетический алгоритм трассировки СБИС построением дерева Штейнера.

2.5. Выводы.

3. Разработка модифицированных генетических операторов.

3.1. Представление хромосом по Нейману.

3.2. Разработка модифицированных операторов кроссинговера.

3.3. Разработка модифицированных операторов мутации.

3.4. Анализ разработанных генетических операторов.

3.5. Выводы.

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

4.1. Программная среда для решения задач компоновки и группирования элементов СБИС.

4.2. Программная среда для решения задачи трассировки СБИС.

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

4.3.1. Порядок выполнения экспериментальных исследований.

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

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

4.4. Выводы.

В настоящее время основным фактором ускорения научно-технического прогресса, повышения качества общественного производства, является полная автоматизация производственных процессов, одним из важных направлений является использование средств вычислительной техники, которая в настоящее время достигла высоких результатов в скорости и быстродействии. В то же время появление новых разработок в области вычислительной техники, создание компьютерных моделей, обладающих более высокой степенью быстродействия, являются основными предпосылками для разработки новых технологий производства основных узлов электронно-вычислительной аппаратуры (ЭВА), основными элементами которых являются БИС и СБИС[8,90,96,100-119]. Основным языком ЭВА является формальный язык математики. Способность формализовать математические структуры и оперировать с ними - краеугольный камень человеческого интеллекта. Математические структуры и алгоритмы - это те формы, в которых теория вычислительной техники и искусственного интеллекта (ИИ) образуют знания об интеллектуальных процессах. Вследствие роста интеграции элементной базы ЭВА и повышения требований к параметрам узлов ЭВА актуальной является проблема создания методов проектирования БИС, выполняемых без участия человека. СБИС составляют элементную базу ЭВА новых поколений, содержат миллион и более транзисторов на кристалле. В этом случае трудоёмкость полных задач проектирования [90, 96, 100 - 119], конструирования и технологии резко возрастает и поэтому использовать алгоритмы с экспоненциальной временной сложностью становится невозможным из-за необходимости обработки огромных массивов информации. В этой связи становится необходимым модернизация структуры, как традиционных САПР, так и основных алгоритмов входящих в математическое обеспечение(МО) САПР. Одним из подходов такой модернизации является использование методов моделирования эволюции и генетических алгоритмов(ГА), а также их модификация и нахождение новых подходов к решению задач проектирования СБИС.

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

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

Генетика - наука о законах наследственности и изменчивости организмов. Основные задачи генетики это разработка методов управления наследственностью и наследственной изменчивостью для получения "нужных" индивидууму форм организмов или в целях управления их индивидуальным развитием. В 1985 году Мендель разработал основные законы генетики. Они утвердили принцип дискретности в явлениях наследования и организации генетического материала, сосредоточив основное внимание на изучение закономерностей наследования потомками признаков и свойств их родителей. Понятие "гена" введено в 1909 году В.Иогансеном. В настоящее время ген это элементарная единица наследственности, отвечающая за появление какого- либо признака. Гены обычно собираются в пределах хромосом. Наследование признаков может изменяться и нарушаться в результате различных генетических операций, а также изменение порядка расположения генов в хромосоме, ведущих к перераспределению генетического материала между хромосомами. Наследственное разнообразие особей создаётся с одной стороны за счёт рекомендации генов при скрещивании, а с другой стороны в результате изменения самих генов за счёт разнообразных мутаций.

В 1975 году Холланд [5], описал методологию для изучения натуральных адаптивных систем и их применение для искусственных адаптивных систем, а также привёл подходы к решению задач ИИ. Идеи Холланда и его учеников оказались настолько плодотворными и эффективными, что в США и в других странах начали проводиться разработки и исследования в этой области. Сейчас генетические алгоритмы - хорошо известная и эффективная оптимизационная методология, которую применяют для решения различных задач техники, основанная на аналогии процессов натуральной селекции и генетических преобразований в биологии. Биологическая основа этой эффективной методологии для адаптивных процессов, есть эволюция от одной генерации к другой. Причём основой этого процесса является выживание сильнейших, что выполняется путём исключения слабых элементов и составления оптимальных или квазиоптимальных элементов.

В последнее время проведена разработка и исследование применения генетических алгоритмов эффективного решения задач в проектировании СБИС [47,52]. А именно для этапов конструкторского проектирования: компоновка элементов СБИС, компоновка блоков СБИС, трассировка, размещение элементов, группирование элементов и блоков СБИС, типизация, верификация и кланирование кристалла [14,15,34,68,81,84,101,105119]. Разработаны эффективные ГА, позволяющие оптимизировать процесс проектирования. Разрабатываются новые модифицированные генетические операторы и генетические алгоритмы. Среди основных задач данного этапа (конструкторского проектирования) являются задачи компоновки элементов и трассировки СБИС, которые являются многовариантными, экстремальными, комбинаторно-логическими задачами, требующими больших временных затрат для их решения. Поэтому разработка новых генетических алгоритмов с полиномиальной временной сложностью для решения рассматриваемых задач является актуальной проблемой.

Цель и задачи исследования. Целью диссертационной работы является разработка и исследование эффективных поисковых и генетических алгоритмов для решения задач компоновки элементов и трассировки СБИС.

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

• построение архитектур генетического поиска, ориентированных на решение задач компоновки элементов и трассировки СБИС;

• разработка и исследование генетических алгоритмов компоновки и группирования элементов СБИС;

• разработка генетического алгоритма трассировки СБИС путём построения дерева Штейнера;

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

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

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

1. Разработана архитектура генетического поиска, ориентированная на решение задач компоновки элементов и трассировки СБИС;

2. Разработаны генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать локальные оптиму-мы;

3. Разработан алгоритм генетического поиска для построения дерева Штейнера;

4. Построены генетические операторы кроссинговера и мутации;

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

На защиту выносятся:

- архитектуры генетического поиска, ориентированные на решение задач компоновки элементов и трассировки СБИС;

- алгоритм компоновки элементов СБИС, позволяющий находить локальные оптимумы;

- алгоритм группирования элементов СБИС;

- алгоритм трассировки соединений для построения дерева Штейнера;

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

Реализация результатов работы. Полученные результаты использованы при выполнении фундаментальных госбюджетных научно-исследовательских работ Ростовской государственной академии сельскохозяйственного машиностроения(РГАСХМ) на кафедре "Прикладная математика и вычислительная техника"(ПМ и ВТ) по заказу Минобрнауки РФ по темам: "Теория поисковой адаптации для решения комбинаторных задач оптимизации"^ 1.01.2003 - 31.12.2004г.г.) и "Теория интеллектуальных процедур поиска оптимальных решений"(01.01.2005 - 31.12.2005 г.г.), а также при проектировании и эксплуатации автоматизированных систем контроля и диагностики радиоэлектронной аппаратуры в НИИ специальных информационно-измерительных систем НИИСИИС (г. Росто-на-Дону). Кроме того, материалы диссертации используются в учебном процессе на кафедре "ПМ и ВТ" РГАСХМ при чтении лекций по дисциплинам "Дискретная математика" и "Программные средства САПР".

Основные положения, выносимые на защиту:

1. Архитектура и стратегии генетического поиска;

2. Модифицированные генетические алгоритмы компоновки и группирования элементов СБИС, позволяющие получать оптимальные решения за однократное срабатывание операторов.

3. Генетический алгоритм трассировки СБИС, позволяющий получать оптимальные решения за полиномиальное время.

4. Модифицированные операторы кроссинговера и мутации, основанные на представлении хромосом по Нейману.

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международых научно-технических конференциях "Интеллектуальные системы "(AIS-05) и "Интеллектуальные CAnP"(CAD-2005) (г. Геленджик 2005 г.), на VII Всероссийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (КРЭС'04) (г.Таганрог 2004 г.), на региональных научно-технических конференциях "Проблемы современного машиностроения"(г. Ростов-на-Дону, РГАСХМ, 2005, 2004 г.г.)

По материалам диссертационной работы опубликовано 6 работ, материалы вошли в два отчета по НИР.

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

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

4.4. Выводы.

В данной главе проведены экспериментальные исследования разработанных генетических алгоритмов компоновки элементов и трассировки СБИС построением дерева Штейнера на основе предложенных генетических операторов кроссинговера с представлением хромосом, построенных в две строки.

1. Реализация разработанного алгоритма компоновки элементов СБИС при разбиении графов на части показало его преимущество по времени решения в сравнении с известными до 10%.

2. Исследование разработанного алгоритма построения дерева Штейнера показало его преимущество по времени решения в сравнении с известными от 3,5% до 15%.

3. Использование разработанных генетических операторов позволило сократить количество итераций алгоритмов компоновки и трассировки до четырёх.

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

5. Предложена программная среда на языке Turbo Pascal 7.0 для решения и исследования генетических алгоритмов компоновки, группирования элементов и трассировки СБИС.

Заключение.

1. Проведён анализ известных генетических операторов и генетических алгоритмов компоновки элементов и трассировки СБИС.

2. Сформулированы стратегии и архитектура эволюционного поиска, ориентированные на решение задач компоновки элементов и трассировки СБИС.

3. Разработаны модифицированные генетические алгоритмы компоновки и группирования элементов СБИС на основе предложенных генетических операторов, которые имеют полиномиальную временную сложность О(ап) и позволяют сократить на 10-15% время поиска оптимальных решений по сравнению с существующими.

4. Разработан модифицированный генетический алгоритм трассировки СБИС построением дерева Штейнера на основе предложенных генетических операторов кроссинговера и мутации,отличающийся выбором хромосом, и позволяющий работать с задачами большой размерности, повысить качество трассировки и сократить время поиска оптимального решения на 12-18% по сравнению с существующими. л

Временная сложность алгоритма составляет 0(п ).

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

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

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

8. Построена программная среда на языке Turbo Pascal 7.0 для решения и исследования генетических алгоритмов компоновки, группирования элементов и трассировки СБИС.

1. Eiben А.Е. Orgy in the computer: multi-parent reproduction in the genetic algorithms. Amsterdam: CWI, 1995.

2. Gen M., Cheng R. Genetic Algorithms and Engineering design. John Wiley & Sons, 1997.

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

4. Handbook of Genetic Algorithms, Edited by Lowrence Davis, Van Nostrand Reinhold, New York, 1991, 385 p.

5. Holland J.H. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975, 210 p.6. http: www.schools.techno.ru/sch748/genetic.

6. Naveed Sherwani. Algorithms for VLSI physical design automation. Kluwer academic publishers. Boston /Dordrecht/ London. 1995.

7. Энкарначчо Ж., Шлехтендаль Э. Автоматизированное проектирование: основные понятия и архитектура систем. М.: Радио и связь, 1986.

8. Neyman J. First Course in Probability and Statistics. University of California, Berkeley. New York, 1970, 450 p.

9. Van Kemenade C.H.M. A two-level evolution strategy. Amsterdam: CWI, 1995.11 .Van Kemenade C.H.M. Multi-parent recombination to overcome premature convergence in genetic algorithms. Amsterdam: CWI, 1995.

10. Jones J., Harris F. A Genetic Algoritm for the Steiner Minimal Tree Problem. University of Nevada.http://www.cs.unr.edu/~fredh/papers/conf/agaftsmtp/paper/docl.ps.gz

11. Michael J. Alexander and Gabriel Robins, "New Perfomance-Driven FPGA Routing Algorithms", Proceedings of ACM/SIGDA Design Automation Conference, June 1995.

12. Автоматизация проектирования БИС. Практическое пособие. Кн.2. П.В.Савельев,В-В.Коняхин.Функционально-логическое проектирование БИС.М.: Высшая школа,1990,-156 е.: ил.

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

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

15. Божич В.И., Лебедев О.Б., Лебедев В.Б. Организация генетического поиска для мультихромосомных представлений решений. Известия ТРТУ, № 3, 2003 г, стр.68 -74.

16. Букатова И.Л. и др. Эвоинформатика. Теория и практика эволюционного моделирования. М.: Наука, 1991.

17. Букатова И.Л. Эволюционное моделирование и его приложения. М.: Наука, 1979.о

18. Бюргер Ю А, Гнапок ВМ., ЛитвиненкоВЛ, Ткачук АА. Применение распределительного генетического алгоритма при решении задач об упаковке в контейнеры. Перспективные информационные технологии и интеллектуальные системы№2, 2002, стр. 11-15.

19. Возыка В.В. Построение дерева Штейнера генетическим алгоритмом. Известия ТРТУ, Материалы Международной конференции "Интеллектуальные САПР", № 3, 2003 г., стр. 213- 214.

20. Воробьёв М.А., Гальченко В.Я. Генетические алгоритмы в проектирования источников магнитных полей. 1Т +8Е'2003, майская сессия, 2003 г., стр. 52- 55.

21. Вязгин В.А. Фёдоров В.В. Математические методы автоматизированного проектирования.: Учебное пособие для втузов.- М.: Высшая школа.,1989.-184 с.

22. Гармаш A.B. Решение задачи планирования СБИС на основе квантовых алгоритмов. Таганрог, ТРТУ. Перспективные информационные технологии и интеллектуальные системы, № 2, 2003 г., стр. 47 52.

23. Горелик A.JL, Скрипкин В.А. Методы распознавания. Учебное пособие. 2-е изд.; переработанное и дополненное. - М.: Высшая школа, 1984. - 208 е., ил.

24. Гудилов ВВ., Зинченко JLA. Аппаратная реализация вероятностных генетических алгоритмов с параллельным формированием хромосомы. Перспективные информационные технологии и интеллектуальные сисгемы№4,2003, стр. 31-35.

25. Давиденко В.I L, Курейчик ВМ Генетический алгоритм для трассировки двухслойных каналов. Автоматизация проектирования, № 1,1999 r.(hüp'/www.ospju).

26. Дж. Д. Ульман. Вычислительные аспекты СБИС.: Под редакцией П.П. Пар-хоменко.-М.: Радио и связь. 1990.-480 е.: ил.

27. Зинченко JI.A., Курейчик В.М. Многоальтернативные генетические алгоритмы поиска экстремума функции// Известия Академии наук. Теория и системы управления, 2003, №4, с. 82-91.

28. Зинченко JI.A., Курейчик В.М. Многоальтернативные генетические алгоритмы поиска экстремума функции//Известия академии наук. Теория и системы управления, 2003, №4, с.82-91.

29. Ильин В.Н. Машинное проектирование электронных схем. М., "Энергия", 1972,280 с. с ил.

30. Калашников P.C. Повышение эффективности генетического поиска. Перспективные информационные технологии и интеллектуальные системы. № 4, 2004 г.

31. Колосов В.Г., Мелехин В.Ф. Проектирование узлов и систем автоматики и вычислительной техники: Учебное пособие для вузов.- JI: Энергоатомиздат. Ленинградское отделение. 1983.- 256 е., ил.

32. Конструирование аппаратуры на БИС и СБИС. Под ред. Б.Ф. Высоцкого и В.П. Сретенского. М.: Радио и связь, 1989.

33. Крылов В Л., Цетлин M.JI. Игры между автоматами. Автоматика и телемеханика, 1963, Т.24, №7.

34. Курейчик B.B. Диссертация. Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС. Таганрог. 1994 г.

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

36. Курейчик В.В., Калашников P.C. построение ортогонального дерева Штейне-ра модифицированным методом. Известия ТРТУ, №3,2004 г., стр.86-89.

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

38. Курейчик В.М. Квантовый алгоритм определения паросочетаний в графе. Таганрог, ТРТУ. Перспективные информационные технологии и интеллектуальные системы. № , 2004 г., стр. 4-11.

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

40. Курейчик В.М. Новый подход к раскраске клик графа на основе квантовых алгоритмов. Известия ТРТУ, №3,2004г., стр.29-34.

41. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа. Известия академии наук. Теория и системы управления, 1999, № 4, с. 79-84.

42. Курейчик В.М., Калашников В А., Лебедев Б.К. Автоматизация проектирования печатных плат. Изд-во Ростовского университета, 1984.80с.

43. Курейчик В.М., Лебедев Б.К. Искусственный интеллект в САПР: Текст лекций. Таганрог: Изд-во ТРТИ, 1989.48 с.

44. Курейчик В.М., Лебедев Б.К., Лях A.B. Проблемы эволюционной адаптации в САПР.//Новинтех. -1991. -№3.

45. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. -Таганрог: Изд-во ТРТУ, 2000. -192с.

46. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: Изд-во ТРТУ, 2000. -192с.

47. Лебедев Б.К. Методы поисковой адаптации на основе механизмов генетики, самообучения и самоорганизации. Программные продукты и системы, №1,2002 г., стр. 16-20.

48. Лебедев Б.К. Поисковый алгоритм трассировки // Изв. ЛЭТИ: Сб.науч.тр. / Ленингр. электротехн. ин-т им. В.И.Ульянова (Ленина). 1984. Вып.347. С.94-98.

49. Лебедев Б.К. Процедуры сужения пространства решений при построении дерева Штейнера. Известия ТРТУ, №3,2004 г., стр. 55-60.

50. Лебедев Б.К. Решение задач покрытия методами генетического поиска. Перспективные информационные технологии и интеллектуальные системы, № , 200 г., стр. 13-20.

51. Лебедев Б.К., Лебедев О.Б. Разбиение на основе коллективной адаптации. Известия ТРТУ, №3,2004 г., стр. 61 -66.

52. Лебедев Б.К., Мухлаев A.B. Элементы адаптации в алгоритмах монтажно-коммутационного проектирования // Автоматизация проектирования электронной аппаратуры. Таганрог: Изд-во ТРТИ, 1988. Вып.5. С.67-71.

53. Лебедев В.Б. Планирование СБИС методом адаптивного поиска. Известия ТРТУ, № 2 , г., стр. 168 177.

54. Лебедев О.Б. Механизмы генетического поиска при глобальной трассировке. Таганрог, ТРТУ. Перспективные информационные технологии и интеллектуальные системы, № , 2003 г., стр. 27 31.

55. Минкин Ю.И., Петров А.И. Самоорганизующийся генетический алгоритм: Теория и системы управления. 2001, №3, с. 66-74.

56. Наместников AM, Ярушкина КГ. Эффективность генетических алгоритмов для задач автоматизированною проектирования. Известия академии наук. Теория и системы управления, 2002, №2, стр. 127-133.

57. Нейман Ю. Вводный курс теории вероятностей и математической статистики .Перевод с английского Ю.В.Линник, А. М. Каган.

58. Неупокоева HB. Об одной архитектуре генетического поиска. Перспективные информационные технологии и интеллектуальные системы№4,2003, стр. 32-35.

59. Никитин A.B., Никитина Л.И. Эволюционная модель оптимизации ассоциативной памяти для машин потока данных на основе генетического алгоритма. Программирование, № 6, 2002 г., стр. 31-42.

60. Орлов H.H. Решение Евклидовой задачи Штейнера. Известия ТРТУ, №3, 2004 г., стр.86-89.

61. Панадимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.512 с.

62. Поздняков Д.В. Генетический алгоритм трассировки в канале. VII Всероссийская научная конференция студентов и аспирантов, Техническая кибернетика, радиоэлектроника и системы управления. КРЭС'04, стр.110-111.

63. Проектирование монтажных плат на ЭВМ / К.К. Морозов, А.Н. Мелихов, В.Г. Одиноков, В.М. Курейчик, В.А. Калашников, Б.К. Лебедев: Под ред. К.К. Морозова. М.: Сов.радио, 1979.224с.

64. Растригин Л.А. Адаптация сложных систем. Рига: Зинатне, 1981.375с.

65. Растригин Л.А., Рипа К.К., Тарасенко Г.С. Адаптация случайного поиска. Рига: Зинатне, 1978.

66. Родзин С.И. Генетическое программирование и проблемы синтеза программ. Известия ТРТУ,№ 3, 2003 г.

67. Семенила АН Планирование развития первичных сетей связи на основе генетических алгоритмов. Автоматика и телемеханика, №1,2002, стр. 67-75.

68. Сергеев A.C. Диссертация. Исследование и разработка методов трассировки проводящих покрытий БИС на основе стратегии эволюционного поиска. Ростов -на- Дону. 2000 г.

69. Сигорский В.Г. Проблемная адаптация в системах автоматизированного проектирования. Известия высших учебных заведений: Радиоэлектроника. Т. 31, №6,1988 г.

70. Сигаотин ДС. Специфика организации генетического поиска изоморфной подстановки графов. Перспективные информационные технологии и интеллектуальные сисгемы.№4,2003, стр. 100-103.

71. Системы автоматизированного проектирования в радиоэлектронике: Справочник / Е.В. Авдеев, А.Т. Еремин, И.П. Норенков, М.И. Песков; Под ред. И.П. Норенкова. М.: Радио и связь, 1986.368с.

72. Смирнова О.В. Диссертация. Разработка и исследование генетических компоновки блоков ЭВА. Ростов- на -Дону. 2002 г.

73. Сороколетов П.В. Генетические операторы мутации на основе чисел Фибоначчи.

74. Сороколетов ПВ. Методы адаптации в задачах компоновки. Перспективные информационные технологии и интеллектуальные системьь№4,2003, стр. 27-30.

75. Теоретические основы эволюционного моделирования генетических алгоритмов. Чернышев Ю.О., Курейчик В. М., Ведерникова О.Г., Басова A.B. Ростов-на-Дону. 1999 г.

76. Чернышев Ю.О., Курейчик В.М. Методическое пособие. Математические основы САПР: Конспект лекций \ РИСХМ: Ростов -на -Дону, 1987.52 с.

77. Шкамардин И.А. Алгоритмы эволюционного проектирования электронных устройств. Перспективные информационные технологии и интеллектуальные системы, № 2, 2004 г., стр. 39-43.

78. Шкамардин И.А. Применение генетических алгоритмов в задачах оптимизации схемотехнических решений. Перспективные информационные технологии и интеллектуальные системы, № 1, 2004 г., стр. 21-26.

79. Штейн М.Е., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры. М.: Советское радио,1973,296 с.

80. Юрин О.Н. Единая система автоматизации проектирования ЭВМ. М.,"Советское радио",1976,176 с.

81. Чернышев Ю.О., Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Теория поисковой адаптации для решения комбинаторных задач оптимизации. Отчет. ГР 01.20.030.8394. Ростов-на-Дону. РГАСХМ, 01.01.2003-31.12.2004 г.г.

82. Чернышев Ю.О., Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Теория интеллектуальных процедур поиска оптимальных решений. Отчет . . Ростов-на-Дону, РГАСХМ, 01.01.2005-31.12.2005 г.г.

83. Калашников Р.С. Разработка и исследование алгоритмов построения деревьев Штейнера на основе эволюционного моделирования. Диссертация. Таганрог, ТРТУ, 2004 г.

84. Ищенко С.Н. Об одном генетическом алгоритме. VII Всероссийская научная конференция студентов и аспирантов 'Техническая кибернетика, радиоэлектроника и системы управления" (КРЭС'04). Тезисы докладов. Таганрог, ТРТУ, 2004 г., с. 96-97.

85. Курейчик В.М., Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О. Адаптация на основе самообучения. Монография.- РГАСХМ ГОУ,. Ростов-на-Дону, 2004 г.,-146 с.

86. Ищенко С.Н. Эффективные генетические операторы. Труды международных научно-технических конференций "Интеллектуальные системы(1ЕЕ А18'05)" и "Интеллектуальные САПР (САЕ)'05)". Научное издание. Таганрог, ТРТУ, 2005, Т.4.- с.63-64.

87. Ищенко С.Н. Новый подход к построению генетических операторов. Труды международных научно-технических конференций "Интеллектуальные сис-темы(1ЕЕ А18'05)" и "Интеллектуальные САПР (САО'05)". Научное издание.

88. Таганрог, ТРТУ,, 2005, Т.4.- с.64-69.

89. Ищенко С.Н., Чернышев Ю.О. Алгоритм компоновки элементов СБИС. Труды международных научно-технических конференций "Интеллектуальные системы(ШЕ А18'05)" и "Интеллектуальные САПР (САБ'05)". Научное издание. Таганрог, ТРТУ,, 2005, Т.4.- с.69-72.

90. Ищенко С.Н. Генетичечкий алгоритм группирования элементов. Труды научной конференции «Повышение эффективности систем передачи информации». г. Ставрополь, 2006г., с. 36-38.

91. Ищенко С.Н. Генетический алгоритм трассировки соединений. Труды научной конференции «Повышение эффективности систем передачи информации». г. Ставрополь, 2006г., с. 38-40.

92. Гладков Л.А., Куречик В.В., Куречик В.М. Генетические алгоритмы. Учебное пособие. Под ред. В.М. Курейчика. Ростов - на - Дону: ООО «Ростиз-дат», 2004. -400 с.

93. Сороколетов П.В. Разработка и исследование композитных алгоритмов компоновки блоков ЭВА: Диссертация на соискание ученой степени к.т.н. Таганрог, 2004 г.

94. Мищенко М.Н. Исследование и разработка бионических методов размещения коммутационных схем ЭВА: Диссертация на соискание ученой степени к.т.н. Таганрог, 2005 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

110. Казеннов Г. Основы проектирования интегральных схем и систем. М.: Бином. Лаборатория знаний, 2005. - 295 с.

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

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