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

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

Черун Сергей Владимирович

СИНТЕЗ КОМБИНАЦИОННЫХ ЛОГИЧЕСКИХ СХЕМ НА ОСНОВЕ ЭВОЛЮЦИОННОГО ПОДХОДА

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

АВТОРЕФЕРАТ

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

Таганрог 2005

Работа выполнена в Таганрогском государственном радиотехническом университете

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

д-р. техн. наук, проф. Курейчик В.В.

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

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

доцент кафедры РК-9 МГТУ им. Баумана, к.т.н. Тарасов В.Б.

Ведущая организация: - РосНИИ ИТ и АП, г. Москва

Защита состоится «_» августа 2005 г. в 14:20 на заседании

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

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

Отзывы на автореферат в 2-х экземплярах, заверенные печатью организации, просим направлять по адресу: Ученый Совет ТРТУ, пер. Некрасовский, 44, ГСП-17А, Таганрог, Ростовская обл., 347928.

Автореферат разослан «_» июля 2005 г.

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

д-р техн. наук, проф.

А.Н. Целых

шл

3

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

Актуальность работы.

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

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

Значительный вклад в решение научно-технических задач с помощью эволюционного моделирования внесли: Holland John Н., D.B. Fogel, J. Koza, Батищев Д.И., Курейчик B.M.

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

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

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

ГГ

t- (

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

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

Цель работы.

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

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

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

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

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

4. Найден метод оценки качества получаемых альтернативных решений, с учетом внешних критериев.

5. Разработан комплекс программ эволюционного проектирования на основе предложенных алгоритмов.

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

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

2. Разработан генетический алгоритм синтеза комбинационных логических схем;

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

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

Практическая ценность.

Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов синтеза комбинационных схем, позволяющих использовать разработанные методы, отвечающие конкретным задачам САПР. Алгоритмы реализованы на языке С# под ОС Windows.

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

Реализация результатов работы.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации нейросетевых моделей и методов принятия решений», а также в научно-исследовательской работе №12388 по теме «Разработка теорем и принципов принятия решений при разбиении сложных математических объектов на части на основе моделирования эволюции и фрактальных множеств».

Материалы диссертации были использованы в лабораторных, практических работах и при чтении следующих курсов на кафедре САПР ТРТУ: «Математическая логика и теория алгоритмов», «Эволюционное моделирование и генетические алгоритмы».

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

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

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

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

3. Метод нахождения решения в заданном пространстве поиска.

Апробация результатов работы.

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

Публикации.

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

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 128 стр., 45 рис., 19 табл., список литературы из 107 наименований, 32 стр. приложений и актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Приведены самые значимые особенности и преимущества эволюции

схем:

• Потенциал для нахождения новых схем;

• Возможность нахождения новых топологических проектных норм из новых полученных схем;

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

• Эволюционные системы способны достигать конкурентоспособных схем, когда сравниваются с современным положением дел в электронике.

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

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

Постановка задачи синтеза комбинационных схем описана кортежем: <Х, В, (}>. Где X - является множеством всех решений, О - ограничения, накладываемые на множество X, для получения допустимых решений и -целевая функция (ЦФ), с помощью которой можно определить наилучшее (оптимальное) решение.

X - множество всех возможных хромосом в популяции. Эти хромосомы могут быть нерелевантными, т.е. кодировать в себе недопустимые решения, или решения, не приводящие ни к какому результату. Обозначим популяцию на шаге ГА / как Рь а хромосому с номером / - И,. Тогда можно записать, что популяция на шаге I

П ={И„ ... ,к„}, где г=[1,7.7, п=[1,И], Т - количество итераций ГА и ТУ-количество хромосом в популяции. Параметр Г может варьироваться в заданных пределах. Тогда X можно записать в следующей форме: {Р„ <=/.....Г/ = (к» 1=1, ..., Т; 1=1, ..., Щ.

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

О - целевая функция. Целевая функция является многопараметрической. Во-первых, она зависит от количества логических элементов. Второй составляющей целевой функции является количество связей (соединителей). Целевая функция описывается в следующем виде:

е-й+е*

где <3|, количество логических элементов в альтернативном решении и Ог представляет собой количество связей между логическими элементами в альтернативном решении.

Оптимизация задачи синтеза комбинационных схем сводится к максимизации критерия 0, т.е. ()(Х)-±тах.

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

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

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

Схема предлагаемого алгоритма эволюционного проектирования комбинационных логических схем с возможностью задания технических величин показана на рис. 1.

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

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

Альтернативное решение кодируется как двухмерная матрица, в которой каждый элемент является в свою очередь логическим элементом. Всего используется четыре типа логических элементов: И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, также введен так называемый СОЕДИНИТЕЛЬ. Каждый элемент матрицы, может принимать свои входы от любого элемента в предыдущем столбце.

Рис. 1. Алгоритм эволюционного проектирования комбинационных логических

схем

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

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

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

2. Получить количество входов в таблице истинности

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

4. Для каждого элемента матрицы т[и] выполнить генерацию строительного блока на основании данных полученных в пунктах 1 и 2. После формирования начальной популяции происходит последовательное

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

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

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

Цель работы алгоритма - достижения значения целевой функции равной количеству строк в таблице истинности с одновременной минимизацией количества логических элементов в комбинационной схеме.

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

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

1. Вычисление целевой функции для каждой особи на всем множестве особей (популяции);

2. Построение таблицы вероятностей, описывающей стол рулетки по формуле:

РМП/ Рг|1=1-Н1, где Р[1] - текущее значение таблицы вероятностей; ЯП] - значение целевой функции для текущей особи; ^ - сумма целевых функция всех особей;

п - количество особей в популяции;

3. Генерация случайного числа я в диапазоне от 0 до 1;

4. Обнуление частичной суммы рагёит;

5. Последовательный просмотр таблицы вероятностей с наращиванием частичной суммы на значение вероятности 1 - й хромосомы до выполнения условия:

раПвшп < q;

6. Индекс, найденный в пункте 5, будет определять очередного кандидата для этапа скрещивания.

Функция рекомбинации определяет, как новая генерация хромосом будет построена из родителей и потомков. Другими словами, функция рекомбинации — это анализ и преобразование популяции при переходе из одной генерации в другую Существует много путей выполнения рекомбинации.

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

Для вычисления ЦФ определяется дерево, внутри пространства матрицы, представляющее возможное решение (рис.3).

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

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

О

Рис.2. Алгоритм применения функции рекомбинации

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

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

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

(Г

;

1>

Содокь масс як О ( спить *«<ж» 1емрО По дупла, пяряметр <жфа&

гНКГ на1» 0-,»< <кврю *> • —|

— г —

Замесгм номара строк« мходо* » мжсмО

1п1 ^СмН МаОТ^ис - I, > >•" 0; | -

МацкУаг • I 0

1 содержи? «омср

Огтредеат. чоиер строя» от Кйтороб прядет первый вход

ляг ЙхМ * Ьсвттевф,. Оирпмшпъ ноьмр с.]«»» от ььлорой щшдег торов вюа

Добавил. иочер першого «хода * мяоядопю Ш1фО «етрР \ddiftmh

Добяапг идем? «ггорвга ¡мимм • миожеегтл гетро

£

Очистит* косое О Добаюго * О мдеев» доярО О ЛМЙяп^ияпрО) очистить масса* №»п$Ю Х&щКУ.С

Рис.3. Алгоритм нахождения дерева внутри матрицы

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

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

Целью исследования разработанных алгоритмов является определение оптимальных параметров, при которых алгоритм находит наилучшие решения за минимальное время работы по сравнению с существующими алгоритмами, а также доказательство его эффективности (оптимальности), по сравнению с другими аналогичными алгоритмами. По результатам экспериментов, даны рекомендации генетических параметров (размер популяции, вероятность кроссинговера, вероятность мутации, количество генераций (поколений)), обеспечивающих возможность получения наиболее оптимальных решений. Для алгоритма оптимальное значение размера начальной популяции »1000, вероятность кроссинговера »45-60%, вероятность мутации - »45-55%, число поколений зависит от размерности матрицы - пространства поиска.

Результаты экспериментов показали эффективность разработанного алгоритма по сравнению с существующими аналогами. Основными критериями эффективности являются качество получаемого решения (количество логических элементов) и временная сложность алгоритма. Алгоритм, получает решения с количеством элементов на 5-10%, и время работы на 20% меньше, по сравнению с известными аналогами.

Для проведения исследований разработана программа синтеза комбинационных логических схем на основе эволюционного подхода. Программа написана на языке Microsoft С# для операционных систем семейства Windows. Эксперименты проводились на IBM PC совместимом компьютере с процессором Intel Р4 2.8 Ггц, объемом оперативной памяти 512Мб.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Предложен комбинированный алгоритм эволюционного поиска комбинационных логических схем.

3. Разработан алгоритм формирования начальной популяции.

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. C.B. Черун, Влияние структуры нейронной сети на снижение вычислительных затрат, Известия ТРТУ №3,2002, с 56-59.

2. C.B. Черун, Эволюционное проектирование логических схем, Перспективные информационные технологии и интеллектуальные системы №4/2002, с.30-34.

3. C.B. Черун, Минимизация вычислительных затрат в задачах эволюционного проектирования, Известия ТРТУ №3,2002 с. 45-48.

4. C.B. Черун, Эволюционное проектирование логических схем, Перспективные информационные технологии и интеллектуальные системы №1(21)/2005 с.28-31

5. C.B. Черун, Особенности вычисления значения функции пригодности при синтезе комбинационных логических схем на основе эволюционного подхода, Известия ТРТУ №2,2005 с.85-87

6. C.B. Черун, Особенности использования функции рекомбинации при синтезе комбинационных логических схем на основе эволюционного подхода, Перспективные информационные технологии и интеллектуальные системы №2(22)/2005 с.35-38

Соискатель

C.B. Черун

/

Тип.ТРТУ Заказ №ЗО9тир./00экз.

ВВЕДЕНИЕ.

1. ЭВОЛЮЦИОННОЕ ПРОЕКТИРОВАНИЕ ЛОГИЧЕСКИХ СХЕМ

1.1. Эволюционная электроника.

1.2. Особенности эволюционных алгоритмов.

1.3. Постановка задачи синтеза комбинационных схем.

1.4. Основные логические элементы и их полный набор.

1.5. Анализ методов проектирования комбинационных логических схем.

1.6. Эволюционные методы проектирования.

1.7. Выводы.

2. ОСОБЕННОСТИ ЭВОЛЮЦИОННОГО ПРОЕКТИРОВАНИЯ КОМБИНАЦИОННЫХ ЛОГИЧЕСКИХ СХЕМ.

2.1. Алгоритм эволюционного проектирования комбинационных логических схем.

2.2. Особенности системы кодирования комбинационных схем в строку хромосомы.

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

2.4. Особенности использования генетических операторов при эволюционном проектировании комбинационных логических схем.

2.5. Особенности управления эволюционным процессом.

2.6. Выводы.

3. РЕАЛИЗАЦИЯ И УПРАВЛЕНИЕ ПРОЦЕССОМ ЭВОЛЮЦИОННОГО ПОИСКА.

3.1. Входные данные.

3.2. Выбор кандидатов для очередного этапа скрещивания.

3.3. Функция рекомбинации.

3.4. Вычисление значения функции пригодности.

3.5. Критерий завершения процесса.

3.6. Выходные данные.

3.7. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.

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

4.2. Сведения об инструментальной среде.

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

4.4. Сравнение результатов.

4.5. Экспериментальное исследование возможности творческого проектирования.

4.6. Вычислительный эксперимент с промышленными бенчмарками

4.7. Выводы.

В современных условиях жесткой конкуренции и значительного ускорения темпов технического прогресса необходимо при минимальных ^ сроках проектирования обеспечить высочайшее качество проектируемых изделий большой функциональной сложности. Решение сложных задач проектирования сегодня уже невозможно без применения помощи систем автоматизированного проектирования (САПР). Постоянное усложнение и увеличение задач, решаемых проектировщиком, обуславливает потребность в постоянном развитии САПР, совершенствовании и внедрении накопленных, а также разработке новых методов и средств, способных существенно повысить качество проектирования [1-5].

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

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

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

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

Известно [6-13], построению комбинационных логических схем предшествует операция получения и упрощения структурной формулы, полученной в свою очередь из функции представленной в виде таблицы состояний. В настоящее время для получения и упрощения структурной формулы используют несколько основных методов. Это диаграммы Карно и метод Квайна - Мак-Класски.

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

Оба метода, и карты Карно, и процедура Квайна - Мак-Класски, разрешают получить двухуровневые схемы. Заметим, что наилучшим решением является комбинационная схема с минимальной задержкой прохождения сигналов в ней. Тем не менее, довольно часто требуется получить минимизацию количества логических элементов в схеме, при этом, не утратив скорости прохождения сигналов. Для минимизации количества логических элементов часто необходимо получить многоуровневую комбинационную схему. Поэтому совместно с методами Карно и Квайна - Мак-Класски используют различные алгебраические манипуляции над логическими выражениями. Помимо этого метод Квайна - Мак-Класски не эффективен в смысле минимизации вычислительных затрат. Верхняя граница количества основных операций равна —, где п п количество входящих элементов в таблице истинности. Это означает, что вычислительные затраты для реализации этого метода растут экспоненциально с количеством входов таблицы истинности. Также этот метод накладывает ограничение на используемые логические элементы в схемах: доступны только основные -элементы, такие как: AND, OR, NOT. Для использования элементов XOR приходится генерировать решение опытному эксперту [6].

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

Использование эволюционных вычислений для нахождения решений в различных задачах является одним из альтернативных путей повышения интеллектуальности систем проектирования. Способность эволюционных алгоритмов к нахождению нестандартных и неожиданных решений подтверждается результатами большого числа исследований [14-25].

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

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

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

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

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

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

4. Найден метод оценки качества получаемых альтернативных решений.

5. Разработан комплекс программ эволюционного проектирования на основе предложенных алгоритмов.

Методы исследования. Методы исследования основаны на теории алгоритмов, алгоритмах эволюционных вычислений.

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

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

2. Разработан генетический алгоритм синтеза комбинационных логических схем.

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

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

Практическую ценность представляют:

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

Реализация результатов работы.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации нейросетевых моделей и методов принятия решений», а также в научно-исследовательской работе №12388 по теме «Разработка теорем и принципов принятия решений при разбиении сложных математических объектов на части на основе моделирования эволюции и фрактальных множеств».

Материалы диссертации были использованы в лабораторных, практических работах и при чтении следующих курсов на кафедре САПР

ТРТУ: «Математическая логика и теория алгоритмов», «Эволюционное моделирование и генетические алгоритмы».

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

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

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 129 стр., 57 рис., 24 табл., список литературы из 112 наименований, 30 стр. приложений и актов об использовании.

4.7. Выводы

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

2. Проведены экспериментальные исследования по данным алгоритмам на тестовых примерах. Результаты показывают преимущество синтезируемых схем перед известными методами.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

4. Разработан комбинированный алгоритм эволюционного поиска, , позволяющий получать квазиоптимальные и оптимальные решения ' за полиномиальное время 0(п2).

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

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

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

8. Проведены серии экспериментов и выполнена обработка экспериментальных данных. Результаты экспериментов показали эффективность разработанных методов и алгоритмов по сравнению с существующими аналогами. Улучшение составило по качеству 510%, а по времени на 20% меньше.

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

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

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

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

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

6. McCluskey Е. Minimization of Boolean Functions. The Bell System Technical Journal, November 1956. Vol. 35. P. 1417-1444.

7. Quine W. The Problem of Simplifying Truth Functions // American Mathematical Monthly. 1952. Vol. 59. P. 521-531.

8. Закревский А.Д. Логический синтез каскадных схем. Москва: Наука. 1981.416 с.

9. Su Y., Cheung P. Computer Minimization of Multi-Valued Switching Functions // IEEE Trans, on Computers. September 1972. Vol. C-21. № 9. P. 995-1003.

10. Sasao T. An Application of Multiple-Valued Logic to a Design of Programmable Logic Arrays // Proc. of the 8th Int. Symp. Multiple Valued Logic. 1978.

11. DeMicheli G., Brayton R.K., Sangiovanni-Vincentelli A. Optimal state assignment for finite state machines // IEEE Trans, on CAD. July 1985. Vol. CAD-4. P. 269-284.

12. DeMicheli G. Symbolic design of combinational and sequentional logic circuits implemented by tow-level logic macros // IEEE Trans, on CAD. October 1986. Vol. CAD-5. P. 597-616.

13. Brayton R.K., Hachtel G., McMullen C., Sangiovanni-Vincentelli A. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston, 1984.

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

15. Букатова И.Л. Эволюционные технологии средства интенсивной информатизации. М.: РАН, ИРЭ, препринт №5(593), 1994.

16. Букатова И.Л. Когнитивные процессы эволюционирующих систем. М.: РАН, ИРЭ, препринт №10(598), 1994.

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

18. В.В. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

19. Д.И. Батищев, Т.С. Кулакова, Д.Е. Шапошников. Применение эволюционно-генетических алгоритмов САПР. //Всерос. совещ.-семинар "Мат. обеспеч. высок, технол. в техн. обр. и мед.", Воронеж, 3-5 ноября, 1994.: Тез. докл. 1994, - с. 125-126.

20. В.М. Курейчик, Л.А. Зинченко. Эволюционное моделирование на основе символьных информационных технологий. Интеллектуальное управление. М.: Физматлит, 1999, с.64 -68.

21. В.М. Курейчик, Л.А. Зинченко. Алгоритмы эволюционного проектирования электронных устройств в статическом режиме. Изв. ТРТУ, №2, 2000, с. 85-89.

22. С.В. Черун, Эволюционный подход . при проектировании комбинационных логических схем, Перспективные информационные технологии и интеллектуальные системы №4/2002, с.30-34.

23. C.B. Черун, Эволюционное проектирование логических схем, Перспективные информационные технологии и интеллектуальные системы №1(21)/2005 с.28-31

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

25. Курейчик В.М., Курейчик В.В. Эволюционные, синергетические и гомеостатические стратегии. Состояние и перспективы// Новости искусственного интеллекта. М., № 3,2000, с.22-92.

26. Cohoon, J.P. and Paris. W.D., Genetic Algorithms in Engineering Systems, The Institute of Electrical Engineers, London, 1997.

27. Louis, S.J. and Rawlins, J.E., Designer genetic algorithms: genetic algorithms in structure design, ICGA-91, in Proc. of the Fourth International Conference on Genetic Algorithms, Belew, R.K., Booker, L.B., and Kauffman, M., Eds., 1991, 53.

28. Vassilev, V.K., Fogarty, T.C., and Miller, J.F., Information characteristics and the structure of landscapes, in Evolutionary Computation, 8, 1, MIT Press, Cambridge, 2000, 31.

29. Курейчик B.M., Родзин С.И. Эволюционные алгоритмы: генетическое программирование. Обзор //Известия РАН: ТиСУ. 2002. №1 с. 127-137

30. Nissen V. Einführung in evolutionäre algorithmen. Braunschweig: Vieweg, 1997.

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

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

33. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -М., МЦНМО, 2000. 960 с.

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

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

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

37. Rudell R., Sangiovanni-Vincentelli A. ESPRESSO-MV: Algorithms for Multiple-Valued Logic Minimization // Proc. of the Custom Integrated Circuits Conference (Portland, USA). 1985. P. 230-234.

38. Rudell R., Sangiovanni-Vincentelli A. Multiple-Valued Minimization for PLA Optimization // IEEE Trans, on CAD. September 1987. Vol. CAD-6. № 5. P. 727-750.

39. Davidson E. An Algoristhm for- NAND Decomposition under Network Constraints //IEEE Trans, on Computers. 1969. Vol. C-18. № 12. P. 10981109.

40. Ashenhurst R.L. The Decomposition of Switching Functions // Proc. of the Int. Symposium on Theory of Switching Functions, 1957. P. 74-116.

41. Brayton R.K. Factoring logic functions // IBM Journal of Research and Development. Vol. 31. № 2. March 1987. P. 187-198.

42. Curtis H.A. A New Approach to Design of Switching Circuits. Princeton, NJ, Van Nostrand, 1962.

43. Roth P.J., Karp R.M. Minimization Over Boolean Graphs // IBM Journal of Research and Development. 1962. Vol. 6. № 2. P. 227-238.

44. Brayton R.K., Rudell R., Sangiovanni-Vincentelli A. Wang A. MIS: A multiple-level logic optimization system // IEEE Trans, on CAD. November 1987. Vol. CAD-6. № 6. P. 1062-1081.

45. Lavagno L., Malik S., Brayton R., Sangiovanni-Vincentelli A. MIS-MV: Optimization of Multi-Level Logic with Multiple Valued Inputs // Proc. of the 27th Design Automation Conference (DAC). 1990. P. 560-563.

46. Murgai R., Shenoy N., Brayton R., Sangiovanni-Vincentelli A. Improved Logic Synthesis Algorithm for Table Look Up Architectures // Proc. of the Int. Conf. on Computer-Aided Design (ICCAD). 1991. P. 564-567.

47. Sushil J. Louis and Gregory J. Rawlins. Using genetic algorithms to design structures. Technical Report 326, Computer Science Department, Indiana University, Blooming-ton, Indiana, feb 1991.

48. R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang. MIS: A multiple-level logic optimization system. IEEE Transactions on Computer-Aided Design, CAD-6 (6): 1062-1081, November 1987.

49. Carlos Artemio Coello Coello. An Empirical Study of Evolutionary Techniques for Mul-tiobjective Optimization in Engineering Design. PhD thesis, Department of Computer Science, Tulane University, New Orleans, LA, aprl996.

50. John J. Grefenstette. Deception Considered Harmful. In L. Darrell Whit ley, editor, Foundations of Genetic Algorithms 2, pages 75-91. Morgan Kaufmann, San Mateo, California, 1993.

51. Kalganova, Т., Miller, J. F. and Lipnitskaya, N., "MultipleValued Combinational Circuits Synthesised using Evolvable Hardware," in Proceedings of the 7th Workshop on Post-Binary Ultra Large Scale Integration Systems, 1998.

52. Hollingworth, G. S., Smith, S. L. and Tyrrell, A. M., "The Intrinsic Evolution of Virtex Devices Through Internet Reconfigurable Logic," in Proceedings of the Third International Conference on Evolvable Systems. Vol. 1801, 2000, pp. 72-79.

53. Vassilev, V. K. and Miller, J. F., "Scalability Problems of Digital Circuit Evolution," in Proceedings of the Second NASA/DOD Workshop on Evolvable Hardware, 2000, pp. 55-64.

54. Gordon, T. G. and Bentley, P., "Towards Development in Evolvable Hardware," in Proceedings of the 2002 NASA/DOD Conference on Evolvable Hardware, 2002. pp. 241-250.

55. Goldberd D. E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 412 p.

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

57. В.В. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

58. Холланд Д. Генетические алгоритмы. В мире науки. 1992. № 9-10. С.32-40.

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

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

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

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

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

67. Курейчик В.В. Генетические алгоритмы в проектировании СБИС: Учебное пособие. Таганрог: Изд-во ТРТУ, 1997.

68. Norenkov I.P. Genetic Method for Structure Synthesis in Design on the Basic of AND/OR Trees. Proceedings 1st International conf., Evolutionary Computation and Its Application, EvCA' 96 Moscow, 1996, p.164-169.

69. Kureichik V.M., Zinchenco L. Symbolic Information Technologies in Evolutionary modelling. ECAI Workshop Notes, ASC2000, Berlin, Germany, 2000,pp.50-53.

70. Genetics Algorithms. Editor Lawrence Elbaum. Proceedings of the 1st International conf., New Jersey, USA, Associates Publishers, 1985.

71. Genetics Algorithms. Editor J.' Grefenstette. Proceedings of the 2nd International conf., New Jersey, USA, Associates Publishers, 1987.

72. Genetic Algorithm. Editor D.Schaffer D. Proceedings 3d International conf., San Mateo, USA, Morgan Kaufman Publishers, 1989.

73. Genetics Algorithms . Editors R. Belew , L.Booker . Proceedings of the 4th International conf., San Mateo, USA, Morgan Kaufman Publishers, 1991.

74. Genetics Algorithms. Editor R. Forrest. Proceedings of 5th International conf., San Mateo, USA, Morgan Kaufman Publishers, 1993.

75. Genetics Algorithms. Editor R. Forrest. Proceedings of 6th International conf., San Mateo, USA, Morgan Kaufman Publishers, 1995.

76. Genetics Algorithms. Editor T.Back. Proceedings of the 7th International conf., San Francisco, USA, Morgan Kaufman Publishers, Inc, 1997.

77. Genetics Algorithms. Editor David Goldberg. Proceedings of the 8th International conf., San Francisco, USA, Morgan Kaufman Publishers, Inc, 1999.

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

79. Методы генетического поиска. Под редакцией В.М. Курейчика. Изд-во ТРТУ, Таганрог, 2002, 145с.

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

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

82. Zebulum R. S., Pacheco M., Vellasco M. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms, CRC Press, 2002.

83. В.М.Курейчик, А.И Гулевич, Л.А.Зинченко. Повышение эффективности эволюционного проектирования электронных устройств на основе иерархического конструирования численно-аналитических моделей. Известия ТРТУ, 2002, №3, с. 82-88.

84. Л.А.Зинченко, А.И.Гулевич. Реализация систем эволюционного проектирования с использованием символьных информационных технологий. Известия ТРТУ, №4, 2001, с. 177-182.

85. L.Zinchenko, V.Kureichik., H.Milhlenbein, T.Mahnig, Application of the Univariate Marginal Distribution Algorithm to Analog Circuit Design. Evolvable hardware conference, 2002. p.93-101

86. Гулевич А.И. Эволюционное проектирование электронных устройств на этапе параметрического синтеза с использованием решающих деревьев. Известия ТРТУ, №1, 2004, с.214.

87. Ю.А. Абилов, Р.А. Алиев, И.М.Насиров. Генетический алгоритм с групповым выбором и направленной мутацией. Изв. РАН. Теории и системы управления № 5, 1997. с. 96-99.

88. А.В. Осыка. Экспериментальное исследование зависимости скорости сходимости генетического алгоритма от его параметров. //Изв. РАН. Теории и системы управления № 5, 1997. с. 100-111.

89. К.A. De Jong, An Analysis of the Behavior of a Class of Genetic-adaptive Systems. Ph.D. Thesis, University of Michigan, 1975.

90. Grefensette J. Optimisation of Control Parameters for genetic algorithms, IEEE Transactions onSystems, Man and Cybernetics, 16(1), 1986.

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

92. D.B. Fogel. Evolutionary Computation. New York. NY: IEEE Press, 1995.

93. Angeline P.J., Pollack J.B. Evolutionary Module Acquisition. Proceedings of the Second Annual Conference on Evolutionary Programming. , ed. by D.B. Fogel and W. Atmar. Palo Alto, 1993, CA: Morgan Kauffinan.

94. 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, p. 73-86.

95. Dr. D. K. Blandford, Verilog Tutorial, Department of Electrical Engineering and Computer Science University of Evansville March 10, 2004

96. Емец С. Verilog — инструмент разработки цифровых электронных схем, http://vmw.compitech.rU/html.cgi/arhiv/0 l02/stat86.htm

97. Carlos A. Coello, Use of evolutionary techniques to automate the design of combinational circuits

98. Зинченко Л.А., Хабарова И.В. Сравнительный анализ экспериментальных исследований алгоритмов эволюционного моделирования с динамическими параметрами. //Известия ТРТУ, Таганрог, ТРТУ. 2002. № 1, с. 234-235.

99. Львовский E.H. Статистические методы построения эмпирических формул: Учеб.пособие для втузов. М., Высшая школа, 1988. 239 е.: ил.

100. Митропольский А.К. Техника статистических вычислений. М., Наука., 1971. 576 е.: ил.

101. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие. / Под общ. ред. Останина А.Н. Минск.: Вышэйшая школа., 1989. 218 е.: ил.

102. Адлер Ю.П. Введение в планирование эксперимента. М., Металлургия, 1969. 157 е.: ил.

103. Гилани Ф. С# и наука: применение языковых средств С# в проектах для научных вычислений, http://www.microsoft.eom/Rus/Msdn/Magazine/2004/03/ScienceComputi ng.mspx

104. Математическая энциклопедия. Т.1., А.-Г. М.: Изд-во «Советская энциклопедия», 1972.

105. C. A. Coello, A. D. Christiansen and A. A. Hernández, "Towards automated evolutionary design of combinational circuits", Computers and Electrical Engineering, Pergamon Press, Vol. 27, No. 1, pp. 1-28, January 2001

106. S. Yang. "Logic synthesis and optimisation benchmark user guide version 3.0, MCNC, 1991".

107. P.K, Samudrala, J. Ramos, S. Katkoori, S.; "Selective triple Modular redundancy (STMR) based single-event upset (SEU) tolerant synthesis for FPGAs'MEEE Transactions on Nuclear Science, Volume: 51 , Issue: 5 , Oct. 2004 Pages:2957 2969