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

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

СТОРОЖЕНКО АНДРЕЙ СЕРГЕЕВИЧ

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

Специальности: 05.13.12 - Системы автоматизации проектирования (вычислительная техника и информатика), 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание учёной степеш кандидата технических наук

СЮ347Э727

Научный руководитель: доктор технических наук, профессор В.В. Курейчик Научный консультант: кандидат технических наук, доцент А.Н. Берёза

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

003479727

Работа выполнена на кафедре: «Информационные системы и Радиотехника» Южно-Российского государственного университета экономики и сервиса в г. Шахты.

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

кандидат технических наук, доцент А.Н. Берёза

доктор технических наук, доцент Н.И. Чернов

доктор технических наук, профессор Д.А. Безуглов

Научный руководитель: Научный консультант: Официальные оппоненты:

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

Научно-исследовательский институт Информационных и управляющих систем (НИИ ВИУС) - структурное подразделение ЮРГТУ (НПИ), г. Новочеркасск

Защита состоится "5" ноября 2009 г. в \р/) на заседании диссертационного совета Д 212.208.22 по защите диссертаций при ФГОУ ВПО «Южный федеральный университет» по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан '¡¿2" п.&су&г>1& 2009 г.

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

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

А. Н. Целых

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

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

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

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

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

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

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

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

Процедура параметрической оптимизации выполняется в четыре этапа: создание или поиск новых значений внутренних параметров схемотехнического решения;

- оценка полученного варианта схемы;

- принятие решения о пригодности или непригодности этого варианта схемы;

- принятие решения о продолжении или прекращении дальнейшего поиска вариантов.

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

вычислительной трудности решения таких задач. Задача параметрической оптимизации схем является №-сложной.

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

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

Цель и основные задачи диссертационной работы.

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

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

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

3. Построение модифицированных генетических операторов, ориентированных на решение задачи параметрической оптимизации.

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

Методы исследования

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

Достоверность результатов исследования

Объем численных экспериментов, проведенных при решении различных контрольных (тестовых) задач и вариациях параметров гибридного бионического и комбинированного алгоритмов, составил не менее 104 опытов. Алгоритмы решения задачи параметрической оптимизации «Гибридный бионический алгоритм параметрической оптимизации» и «Комбинированный бионический алгоритм решения задачи параметрической оптимизации» прошли официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам. Получены свидетельства о государственной регистрации программ на ЭВМ №2009610574 от 26.01.2009 г. и №2009611534 от 19.03.2009 г. соответственно.

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

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

2. Модифицированный алгоритм Ant Colony, позволяющий адаптивно распределять время развития различных областей альтернативных решений, в

многопопуляционном генетическом алгоритме (относится к специальности 05.13.17).

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

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

5. Новые и модифицированные генетические операторы, ориентированные на решение задачи параметрической оптимизации, позволяющие сократить время поиска (относится к специальности 05.13.17).

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

Разработана инструментальная среда (ИС), позволяющая находить квазиоптимальные решения задачи параметрической оптимизации схемотехнических решений. Одним из возможных применений ИС является решение задачи параметрической оптимизации электрических схем и узлов РЭС. Программный комплекс разработан для операционной системы Windows, написан на языке С++. Компиляция выполнена в среде объектно-ориентированного программирования Microsoft Visual Studio 2005.

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

Материалы диссертации использованы в следующих научно-исследовательских работах: «Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.); «Применение интеллектуальных информационных технологий в науке, технике и образовании» (№ г.р. 01.2.008022797, 2008 г.); «Информационные технологии в науке, технике и образовании»; (№ г.р. 12.354) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска»; (№ г/б 12363) «Разработка теории и когнитивных принципов принятия

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

Апробация работы и публикации.

Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные системы», «Интеллектуальные САПР» (г. Геленджик, 2005 - 2009 гг.), Всероссийских научных конференциях молодых ученых и аспирантов (г. Волгодонск, 2005 - 2009 гг.). По материалам диссертационной работы опубликовано 7 печатных работ, материалы диссертационной работы вошли в отчеты по НИР.

Структура и объём диссертационной работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 153 стр., включая 43 рис., 8 таб., список литературы из 130 наименований, 12 стр. приложений и актов об использовании.

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

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

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

может быть представлена как задача нахождения вектора X е Е", который минимизирует целевую функцию

(1)

при ограничениях g(X) = 0 и }г(Х) < 0, где и /¡(X) - векторные функции описывающие систему ограничения на параметры проектирования „V, £" -множество допустимых решений.

При решении задачи параметрической оптимизации схемотехнических решений в качестве элементов вектора X выступают некоторые параметры элементов схемы (к примеру, номинала этих элементов), а целевая функция Р(Х) представляется в следующем виде:

Р(Х) = К(Л(М(Х)), (2)

гае М(Х) - математическая модель схемы, Л - функция множества анализов математической модели схемы, к - функция, отражающая зависимость значения ЦФ от вида анализа, применяемого для расчета выходных характеристик схемы оптимальности.

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

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

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

генетических алгоритмов, муравьиных алгоритмов и алгоритма имитации отжига.

Во второй главе приведены стратегия и принципы решения задачи параметрической оптимизации схемотехнических решений (рис. 1).

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

Математическая модель схемы

* . *

Критерии и показатели качества решений по различным характеристикам Вектор варьируемых параметров

Алгоритм вычислений

т

Рис 1. Принцип построения процесса решения задачи параметрической оптимизации электрических схем

Алгоритмы на базе этой архитектуры позволили улучшить получаемые результаты, незначительно увеличив при этом время работы алгоритма.

Разработаны следующие новые и модифицированные генетические операторы:

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

Анализы схемы

Исходное (оптимизируемое)

Следующий шаг проектирования

Рис 2. Архитектура гибридного поиска

Рис 3. Архитектура комбинированного поиска И

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

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

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

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

_КД-НД. (3)

ш

где КД - конец диапазона значений, НД - начало диапазона значений, Ш - шаг смены значений в диапазоне.

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

Работа модифицированного алгоритма Ant Colony характеризуется выполнением следующих трех формул:

T0(t +1) = (1 -р)* г,jit) + &тц,р е [0,1] (4)

Начало: инициализация

±

Начало: работа

Инициализация следов феромона: ArrayPh[0. ..Мтах-1]=Phl,m

Г 2

Помещаем агентов в вершины случайным образом

г з ■

±

т=-1

Наращиваем счетчик агентов т=т+1

L

[ BestCFOId^BestifAAaayMM)

Г

±

Выполнение ГАлтаумм

±

Изменение следов феромона

г 8 <

±

ArrayBad[s]=ArrayM[m]

г 9 •

±

s=Q

( Конец )

12

Воздействие внешней среды

Перемещаем агента в вершину j

14

т

BestCFOId=Best{rAi)

15

Выполнение TAj

г 16

т

Изменение следов феромона

t

ArrayBad[s]=j

г 13

т

Наращиваем счетчик переходов s=s+1

Рис 4. Схема модифицированного алгоритма Ant Colony 13

Рис 5. Схема модифицированного алгоритма имитации отжига

[г„(ОГ V

(5)

к* allowed t

(6)

.0

Формула 4 описывает воздействие внешней среды на следы феромона. Для этой формулы Г(.(/) - интенсивность следов феромона при переходе в

вершину у из вершины / в момент времени /, р - некоторый коэффициент,

определяющий степень испарения феромона, Дг =у,дг*. где Дг,' -

эффективность промежутка (у) на протяжении маршрута выбранного ¿-тым муравьем, вычисляемая по формуле 6.

По формуле 6 рассчитывается количество феромона, откладываемое каждым муравьем при переходе из одной вершины в другую. Для этой формулы Ср - количество популяций, min^(i) - лучшее значение ЦФ для i популяции в

момент времени /, ArninFm(/) - изменение лучшего значения ЦФ для m

популяции в момент I, J" - список пройденных вершин, ае - некоторая

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

Формула 5 описывает правило вычисления вероятности выбора вершины j муравьем, находящимся в вершине /.

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

Четвертая глава посвящена реализации ИС решения задачи параметрической оптимизации и тестированию предложенных гибридных и комбинированных алгоритмов решения задачи параметрической оптимизации. ИС реализована на языке С++ в среде Microsoft Visual Studio 2005 для

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

Сделаны выводы об оптимальном значении коэффициентов модифицированного алгоритма Ant Colony и модифицированного алгоритма имитации отжига. Наибольшая эффективность разработанного гибридного алгоритма достигнута при следующих значениях управляющих параметров: а = 0,2; /3 = 0,1; GATime=200; aF=0,2; р = ОД 7 .

Ниом» ¿»тмфмс jsice

Кжк»*«ст»с примеров Ю ;!

¡0 i]

"Дитиои ан*чмм>..................................

H«w ¡0 Ьх* ¡0 Ш*г. ¡0 Н*л»«| »мин*. ¡Г

Устанем* | WaiKXHtk дл» *с«к

Рис. 6. Основные экранные формы инструментальной среды «optima»

Исследована эффективность работы разработанных алгоритмов на тестовых функциях (benchmark) и схемотехнических решениях в рамках решаемой задачи. Результаты экспериментальных исследований разработанных алгоритмов на тестовых задачах показаны на рисунках 7 и 8, здесь: ГА -генетический алгоритм, МГА - многопопуляционный генетический алгоритм, ГБА - гибридный многопопуляционный генетический алгоритм, КБА -

Т"

Н«ми мип» jOrerl

ritntb.....................................................................................................................................................

у Врвмрейогы У lontaiЦФ Пуше» {*«*»»« С X*su*epeue»v Г Д«ИО. ' у bum мтераМ) ■} foenwpemema

Ko»*onc«r<v**4 0<WTfcj1 jjj Г Усс«>*«> мгкчок >vr яти no мимо!) (*vt о»

¡МГА | ГБА | ГБАмИО j

Ксллвств0М1ср4ц1Л ji'ooo i]

Коппкпо особей в потужи« j100 ^

On»v«cc .♦♦«^ч'м}«»»' Очо'орч'хохоейр«

^W»»»»« aa»*n< »j twromil »J Bapomoci» n»««i« Г" ;r«oc.M Vj

Оператор селощм и отбсо«

комбинированный бионический алгоритм на основе ГБА и модифицированного алгоритма имитации отжига, ИО - алгоритм имитации отжига.

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

Результаты экспериментальных исследований разработанных алгоритмов на тестовых схемах показаны на рисунках 10 и И. На рис. 10 показан график зависимости результата работы алгоритмов от тестовых схемотехнических решений. На рис. 11 показана зависимость времени поиска квазиоптимальных решений на различных тестовых схемах.

Из графиков 7 и 8 видно, что гибридный МГА показывает на тестовых функциях первого набора результаты соизмеримые с МГА (в среднем, отличие результатов этих алгоритмов составляет 14 %), но время, затрачиваемое на поиск квазиоптимальных решений, значительно ниже (в среднем на 28 % меньше). Комбинированный бионический алгоритм, в среднем, получил результаты на 30 % лучше, чем ГБА, а время поиска больше всего на 5%.

Тестовые функции

----ГА

-МГА

-ГБА

--КБА

—.—ИО

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

тестовых функциях

Тестовые функции

Рис. 8. Среднее время работы алгоритмов на тестовых функциях

Для проведения экспериментальных исследований на схемотехнических решениях была выбрана следующая целевая функция:

CF(X) = My • CD\ + Д/ • сог + ДКп ■ соj + ЛКс • ¿а4, CF{X) min

где o}x,m1,o)1,coi - весовые коэффициенты, устанавливаемые эмпирическим путем; дKv = \KUn~ Ки\ - отклонение значения коэффициента усиления от требуемого (КШУ> Д/ = |/„-(/2-/3)| _ отклонение ширины полосы усиления, fn - требуемая ширина полосы усиления ; ¿jcn = -Кп\~ отклонение крутизны

подъема, где кп„- требуемая крутизна подъема, ¡{п = ^^^—^(fi) _

fi

расчетная крутизна подъема; АКС - \КСп - Кс\ - отклонение крутизны спада, где Кг -требуемая крутизна спада, jf ~ ^(/з) _ расчетная крутизна спада.

с и-и

Для расчета показателей целевой функции использовалась данные полученные в моделирующей подсистеме AVO Spice. На рисунке 9 приведен пример определения элементов ЦФ для некоторого схемотехнического решения по его АЧХ.

Рис. 9. Пример определения элементов ЦФ для некоторого схемотехнического

решения по его АЧХ Из графиков 10 и 11 видно, что на тестовых функциях второго набора ГБА показывает результаты лучшие, чем МГА. В среднем, улучшение результата составляет 18 %, но время, затрачиваемое на поиск квазиоптимальных решений, значительно ниже (в среднем на 16 % меньше). Комбинированный бионический алгоритм, в среднем, получил результаты на 8 % лучше, чем ГБА, а время поиска на 32% больше. Также следует отметить, что на некоторых схемотехнических решениях (СЗ и С4) КБА показал незначительное улучшение результата от 2% до 5%, а время поиска при этом было больше, чем у ГБА, на 24% и 31%.

= 300,0 2

I 50.0

Q>

m 0,0-----1-------.---1------г-----1

C1 C2 C3 C4 C5

Тестовые схемотехнические решения

Рис. 11. Среднее время работы алгоритмов на тестовых схемах

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

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

ЗАКЛЮЧЕНИЕ

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

2. Разработан новый модифицированный алгоритм Ant Colony, предназначенный для адаптивного выбора наборов решений при развитии МГА.

3. Разработан новый гибридный алгоритм на основе многопопуляционного генетического алгоритма и модифицированного алгоритма Ant Colony, сокращающий время проведения поиска.

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

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

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

7. Проведены вычислительные эксперименты для различных алгоритмов на тестовых примерах. На основе результатов даны рекомендации к выбору управляющих параметров {СС, ß, GAtime, aF и д.р.), обеспечивающих получение набора оптимальных решений за полиномиальное время. Эти результаты, в среднем, от 14% до 18% лучше, чем у существующих алгоритмов, а время поиска от 16% до 28% меньше.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных

ВАК РФ

1.Стороженко A.C., Берёза А.Н. Комбинированный многопопуляционный муравьиный генетический алгоритм. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2008, № 9 (86). - 252 с. 24 - 31 с.

Публикации в других изданиях

2. Стороженко A.C., Берёза А.Н. Анализ основных этапов проектирования пользовательского интерфейса информационных систем.: Межвузовский сб. научн. трудов; под ред. С.А. Кузнецова. - Шахты: Изд-во ЮРГУЭС, 2005. -81с.

3.Стороженко A.C., Берёза А.Н. Применение муравьиного алгоритма для решения задачи коммивояжера. Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, апрель-июнь 2006 г., г.Шахты / ред. кол.: А.Э. Попов [и др.]. -Шахты: Изд-во ЮРГУЭС, 2006. - 70 с. 56-59 с.

4.Стороженко A.C., Бегляров В.В., Берёза А.Н. Применение муравьиных алгоритмов для анализа развития популяций в многопупуляционных алгоритмах. Информационные системы и технологии. Теория и практика: сб. науч. тр. / под. ред. А.Н. Берёза. - Шахты: Изд-во ЮРГУЭС, 2008. - 188 с. 33-39 с.

5.Стороженко A.C., Инструментальная среда проектирования алгоритмов на основе интеллектуальных методов «AILab». Информационные системы и технологии. Теория и практика: сб. науч. тр. / под. ред. А.Н. Берёза. - Шахты: Изд-во ЮРГУЭС, 2008. - 188 с. 39-46 с.

6.Стороженко A.C., Бегляров В.В., Берёза А.Н. Применение бионических методов при разработке проектных процедур параметрической оптимизации САПР. Информационные технологии в науке и образовании: материалы Междунар. науч.-прает. интернет-конференция, октябрь 2007 г. - март 2008 г., II Всерос. семинара «Применение MOODLE в сетевом обучении», 26-28 марта 2008 г. (Железноводск), VI Всерос. науч.-практ. Семинара «Автоматезированные системы управления учебным процессом в вузе: опыт, решения, возможности», октябрь 2007 г. / редкол.: А.Э. Попов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2008. - 238 с. 227-230 с.

7.Стороженко A.C., Бегляров В.В., Берёза А.Н. Нечёткий генетический алгоритм размещения 2D объектов. Информационные технологии в науке и образовании: материалы Междунар. науч.-практ. интернет-конференция, октябрь 2007 г. - март 2008 г., II Всерос. семинара «Применение MOODLE в сетевом обучении», 26-28 марта 2008 г. (Железноводск), VI Всерос. науч.-практ. Семинара «Автоматезированные системы управления учебным процессом в вузе: опыт, решения, возможности», октябрь 2007 г. / редкол.: А.Э. Попов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2008. - 238 с. 54-61 с.

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

Соискатель / Стороженко А.С,

ВВЕДЕНИЕ.

1. АНАЛИЗ ПРОБЛЕМ И ПЕРСПЕКТИВ РЕШЕНИЯ ЗАДАЧИ ПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ.

1.1. Постановка задачи параметрической оптимизации РЭС и анализ проблемы ее решения.

1.2. Анализ математических моделей элементов схем.

1.3. Исследование методов анализа схем.

1.4. Исследование критериев оптимальности применяемых в задаче параметрической оптимизации.

1.5. Классификация алгоритмов решения задачи параметрической оптимизации схем.

1.6. Выводы.

2. РАЗРАБОТКА ГИБРИДНЫХ И КОМБИНИРОВАННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ ПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ.

2.1. Стратегия и принципы решения задачи параметрической оптимизации.

2.2. Архитектура гибридного поиска.

2.2. Архитектура комбинированного поиска.

2.4. Построение усовершенствованных генетических операторов, ориентированных на решение задачи параметрической оптимизации.

2.5. Выводы.

3. ПОСТРОЕНИЕ ГИБРИДНОГО И КОМБИНИРОВАННОГО АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ ПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ.

3.1. Гибридный алгоритм на основе бионических методов.

3.2. Разработка модифицированного алгоритма Ant Colony.

3.3. Разработка комбинированного алгоритма решения задачи параметрической оптимизации.

3.4. Выводы.

4. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ И АНАЛИЗ РАЗРАБОТАННЫХ

ПОИСКОВЫХ АЛГОРИТМОВ.

4.1. Цель и задачи построения программного комплекса решения задачи параметрической оптимизации схемотехнических решений.

4.2. Описание программной реализации гибридного и комбинированного алгоритмов.

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

4.4. Выводы.

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

Современные системы автоматизированного проектирования являются комплексными, многоуровневыми и многоаспектными вычислительными системами [34, 36, 77, 105, 101].

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

Термин многоуровневая САПР обозначает, что в такой системе процесс проектирования разбивается на ряд иерархических уровней в соответствии с принципами блочно-иерархического проектирования технических объектов.

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

В соответствии с принципами блочно-иерархического проектирования технических объектов выделяют следующие уровни- его декомпозиции (разбиения) [106]:

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

- структурный уровень, охватывающий описание структуры объекта;

- функциональный уровень заключается в описании законов функционирования подсистем объекта или решении задачи работоспособности объекта как системы заданной структуры;

- конструктивный или элементный (приборный) уровень, содержащий детальный выбор и описание всех элементов системы (объекта) [52].

При разработке САПР возможны и другие подходы к декомпозиции процесса проектирования технического объекта [101, 112]. Так, процесс проектирования РЭС может быть разбит на шесть уровней:

- уровень системного проектирования;

- уровень структурного проектирования;

- уровень функционального проектирования;

- уровень схемотехнического проектирования;

- уровень компонентного проектирования;

- уровень конструкторского проектирования [62].

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

На схемотехническом уровне решаются следующие задачи: структурный синтез, заключающийся в выборе конфигурации схемы; предварительный расчет параметров элементов схемы; определение выходных параметров схемы, в зависимости от изменения внутренних и внешних параметров (одновариантный и многовариантный анализ); определение значений внутренних параметров схемы (параметрический синтез), обеспечивающих наилучшие значения выходных параметров (параметрическая оптимизация). [14, 82, 106, 110].

На сегодняшний день задачи анализа более или менее удовлетворительно автоматизированы [34, 82, 85, 104, 117, 118]. Что касается структурного^ синтеза, то он практически не автоматизирован и проводится, как правило, высококвалифицированными специалистами, опирающимися на накопленный опыт [52].

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

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

Процедура параметрической оптимизации выполняется в четыре этапа:

- создание или поиск новых значений внутренних параметров схемотехнического решения;

- оценка полученного варианта схемы;

- принятие решения о пригодности или непригодности полученного варианта схемы;

- принятие решения о продолжении или прекращении дальнейшего поиска вариантов.

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

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

В настоящее время рядом научных школ ведутся интенсивные исследования в направлении разработки алгоритмов оптимизации технических объектов, в том числе и на основе бионических методов [10, 34, 35,39, 42, 53,73].

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

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

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

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

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

- Построение модифицированных генетических операторов, ориентированных на решение задачи параметрической оптимизации.

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

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

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

В работе:

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

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

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

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

1. новую? гибридную; архитектуру алгоритма решения задачи параметрической оптимизации, основанную; на бионических методах;. . . * .

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

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

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

5. новые и усовершенствованные генетические операторы, обеспечивающие сокращение времени поиска;

6. инструментальная среда проектирования и анализа алгоритмов «optima».

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

Разработанная ИС решения задачи параметрической оптимизации схемотехнических решений реализована с использованием визуальной среды программирования Microsoft Visual Studio 2005 для операционной системы Microsoft Windows 9х и выше.

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

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

Реализация результатов работы. Материалы диссертации использованы в следующих научно-исследовательских работах: «Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.); «Применение интеллектуальных информационных технологий в науке, технике и образовании» (№ г.р. 01.2.008022797, 2008 г.); «Информационные технологии в науке, технике и образовании»; (№ г.р. 12.354) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска»; (№ г/б 12363) «Разработка теории и когнитивных принципов принятия решений на основе распределенных алгоритмов, инспирированных природных систем». Результаты этих работ внедрены и используются в учебном процессе на кафедрах САПР ТТИ ЮФУ (г. Таганрог), «Информационные системы и радиотехника» ЮРГУЭС (г. Шахты), «Информационные технологии и управление» ШИ ЮРГТУ (г. Шахты) и «Информатика» ВИС ЮРГУЭС (г. Волгодонск). Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

Апробация работы. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные системы», «Интеллектуальные САПР» (г. Геленджик, 2005 - 2009 гг.), Всероссийских научных конференциях молодых ученых и аспирантов (г. Волгодонск, 2005 -2009 гг.). По материалам диссертационной работы опубликовано 7 печатных работ, материалы вошли в отчеты по НИР.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 153 стр., включая 43 рис., 8 таб., список литературы из 130 наименований, 12 стр. приложений и актов об использовании.

4.4. Выводы

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

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

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

4. Проведенные серии экспериментов показали улучшение качества получаемых решений до 18%, а уменьшение времени поиска составило от 16% до 28%.

ЗАКЛЮЧЕНИЕ

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

2) Разработан новый модифицированный алгоритм Ant Colony, предназначенный для адаптивного выбора наборов решений при развитии МГА.

3) Разработан новый гибридный алгоритм на основе многопопуляционного генетического алгоритма и модифицированного алгоритма Ant Colony, сокращающий время проведения поиска.

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

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

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

7) Проведены вычислительные эксперименты для различных алгоритмов на тестовых примерах. На основе результатов даны рекомендации к выбору управляющих параметров (а, /7, GAtime, aF и д.р.), обеспечивающих получение набора оптимальных решений за полиномиальное время. Эти результаты в среднем от 14% до 18% лучше, чем у существующих алгоритмов, а время поиска от 16% до 28% меньше.

1. Ackley, D.: An Empirical Study of Bit Vector Function Optimization. Genetic Algorithms and Simulated Annealing, 1987, pp. 170-215

2. Back T., Schwefel H.-P. An Overview of Evolutionary Algorithms for Parameter Optimization// Evolutionary Computation. 1993. -Vol.1.-pp. 1-23.

3. Caldwell A.E., Kahng A.B. and Markov I. L. Optimal Portitioners and End Case Placers for Standard - Cell Layout. -//-V.19, №11, November 2000, pp. 1304- 1313.

4. Colorai A., Dorigo M., Maniezzo V., "Distributed Optimization by Ant Colonies," Proceedings of the First European Conference on Artificial Life, Paris, France, F.Varela and P.Bourgine (Eds.), Elsevier Publishing, 1991, pp. 134142

5. Colorni A., Dorigo M., Maniezzo V., "The Ant System: Optimization by a colony of cooperating agents," Tech.Rep.IRIDIA/94-28, Université Libre de Bruxelles, Belgium, 1996.

6. D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Wesley, 1989.

7. Davis L. Genetic Algorithms and Simulated Annealing. Pitman, London, 1997.

8. Davis, L.D. Handbook of Genetic Algorithms/ L.D. Davis New York, Van Nostrand Reinold, 1991.

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

10. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, CA, 1991.

11. Goldberg, D. E.: Genetic Algorithms and Walsh Functions: Part II, Deception and Its Analysis. Complex Systems 1989, pp. 153-171

12. Griewangk, A.O.: Generalized Descent of Global Optimization. Journal of Optimization Theory and Applications, 34: 11.39, 1981

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

14. Hastings R. A. The Art of Analog Layout. Prentice Hall, 2000

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

16. Ingber L. Very fast simulated re-annealing // Mathematical and Computer Modelling. 12. 1989, pp. 967-973.

17. Kirkpatrick S., Gelatt Jr. C. D., and Vecchi M. P. Optimization by Simulated Annealing// Science. 220. 1983, pp. 671-680.

18. Koza. J.R. Genetic Programming. Cambridge/MA: MIT Press, 1998.

19. Kasabov N. Evolving Connectionist Systems. Berlin: Springer Verlag, 2003.

20. Langton C. (Ed.) Artificial Life. New York: Addison Wesley, 1998.

21. Lee T.H. The Design of CMOS Radio-Frequency Integrated Circuits. Cambridge University Press, 2003

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

23. Medsker L.R. Hybrid Intelligent Systems. Dordrecht: Kluwer Academic Publ., 1995.

24. Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., and Teller E. Equation of State Calculations by Fast Computer Machines // J. Chemical Physics. 21. 6. June. 1953, pp. 1087-1092.

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

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

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

28. Rastrigin, L. A.: Extremal Control Systems. In Theoretical Foundations of Engineering Cybernetics Series, Moscow, Nauka, Russian, 1974

29. Schwefel, H. P.: Numerical Optimization of Computer Models, John Wiley & Sons, 1981

30. Szu H. H., Hartley R. L. Fast Simulated Annealing // Physical Letters A. 122. 1987, pp. 157-162.

31. Whitley, D.: Fundamental Principles of Deception in Genetic Search. In G. J. E. Rawlins (Ed.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1991

32. Williams C.P. Quantum Search Algorithms in Sciences and Engineering. Computing in sciences and engineering, March April 2001, pp. 4451.

33. Yao X. A New Simulated Annealing Algorithm // International Journal of Computer Mathematics. 56. 1995, pp. 161-168.

34. Аветисян, Д.А. Автоматизация проектирования электрических систем. / Д.А. Аветисян — М.: Высш. шк., 1998. 331 е., ил.

35. Автоматизация поискового конструирования (искусственный интеллект в машинном проектировании) / А.И. Половинкин, Н.К. Бобков, Г.Я. Буш и др.; под ред. А.И. Половинкина. М.: Радио и связь, 1981. - 344с., ил.

36. Автоматизация проектирования БИС. Петренко А.И., Сыпчук П.П., А. Тетельбаум и др. Киев: Виша школа, 1983. с.312.

37. Автоматизация проектирования радиоэлектронных средств : учеб. пособие для вузов/О. В. Алексеев и др.; под. ред. О. В. Алексеева. М.: Высш. Шк., 2000.-479 е.: ил.

38. Автоматизация схемотехнического проектирования : учебное пособие для вузов/ В.Н. Ильин и др.; под ред. В.Н. Ильина. М.: Радио и связь, 1987.-386 е.: ил.

39. Автоматизированное проектирование СБИС на базовых кристаллах / А.И. Петренко, В.М. Лошаков, А. Тительбаум и др. М., Радио и связь, 1988.

40. Алиев P.A., Алиев P.P. Теория интеллектуальных систем и ее применение. — Баку: Чашыоглы, 2001.

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

42. Анисимов В.И. Топологический расчет электронных схем. JL, «Энергия», 1977. 240 с. с ил.

43. Аттетков, А. В. Методы оптимизации : учеб. для вузов / А. В. Аттетков, С. В. Галкин, В. С. Зарубин; под ред. В. С. Зарубина, А. П. Крищенко. М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. - 440 с. (Сер. Математика в техническом университете; Вып. XIV)

44. Ахо, А. Построение и анализ вычислительных алгоритмов / А.Ахо, Дж. Хопкрофт, Дж.Ульман. М.: Мир, 1979.

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

46. Батищев, Д.И. Оптимизация в САПР : учебник./ Д.И. Батищев, Я.Е. Львович, В.Н. Фролов. Воронеж: Издательство Воронежского государственного университета, 1997. - 416 с.

47. Бахвалов, Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. М: Бином, 2008. - 636с.

48. Стороженко, редкол.: А.Э. Попов и др.. Шахты: Изд-во ЮРГУЭС, 2008. -238 с. 54-61 с.

49. Бентли, Дж. Жемчужины программирования. / Дж. Бентли. — Изд. 2-е. СПб.: Питер, 2002. - 272 е.: ил.

50. Берёза А.Н. Разработка и исследование векторных макромоделей и генетических алгоритмов для синтеза схемотехнических решений // Диссертация на соискание ученой степени кандидата технических наук. — М.: ТРТУ 2000.

51. Берёза А.Н., Мешков В.Е. Обобщенный алгоритм синтеза структурных схем аналоговых устройств РЭА. Тезисы докладов Международной конференции «Новые информационные технологии в науке, образовании и бизнесе» (IT+SE'97). Гурзуф, 1997. стр. 62-63.

52. Берёза, А.Н. Комбинированный многопопуляционный муравьиный генетический алгоритм. Известия ЮФУ. Технические науки.

53. Тематический выпуск «Интеллектуальные САПР». / А.Н. Берёза, A.C. Стороженко Таганрог: Изд-во ТТИ ЮФУ, 2008, № 9 (86). -252 с. 24-31 с.

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

55. Большая советская энциклопедия. Т.1 — М.: Изд-во СЭ, 1970.

56. Большая советская энциклопедия. Т.18. — М.: Изд-во СЭ, 1974.

57. Большая советская энциклопедия. Т.2. М.: Изд-во СЭ, 1978.

58. Большая советская энциклопедия. Т.29. М.: Изд-во СЭ, 1978.

59. Букатова, И.Л. Эвоинформатика. Теория и практика эволюционного моделирования. / И.Л. Букатова, Ю.И. Михасев, A.M. Шаров -М.: Наука, 1991.

60. Васильев Ф.П. Численные методы решения экстремальных задач. -М.: Наука, 1981.

61. Влах, И. Машинные методы анализа и проектирования электронных схем / И. Влах, К.Сингхал; перевод с англ. М.: Радио и связь, 1988

62. Гаврилов A.B. Гибридные интеллектуальные системы. — Новосибирск: Изд-во НГТУ, 2003.

63. Галеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи. — М: Элиториал УРСС, 2000. 320 с.

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

65. Гилл Ф., Мюррей У., Рай М. Практическая оптимизация: Пер. с англ. М.: Мир, 1985. - 509 е., ил.

66. Гладков JI.A, Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. Под ред. В.М. Курейчика. М: ФИЗМАТЛИТ, 2004. - 402 с.

67. Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курейчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002.-82с.

68. Гладков, Л. А. Разработка бионических методов и алгоритмов поиска оптимальных решений при проектировании : научное издание/ Л.А. Гладков и др.; под редакцией Б. К. Лебедева. Таганрог: Изд-во ТТИ ЮФУ, 2008. -244 с.

69. Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик; под ред. В.М. Курейчика. М.:Физматлит, 2006.

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

71. Глушань В.М., Зинченко Л.А. Математическое и компьютерное моделирование электрических цепей в режиме малого сигнала. 4.1. Моделирование в частотной области: Учебное пособие. Таганрог: Изд-во ТРРУ, 1998. 100 с.

72. Гончаров, В. А. Методы оптимизации : учебное пособие / В. А. Гончаров. М.: Высшее образование, 2009. - 191 с. — (Основы наук).

73. Дарвин Ч. Происхождение видов путем естественного отбора. М.: «Тайдекс Ко», 2003.

74. Джонс, М.Т. Программирование искусственного интеллекта в приложениях / М.Т.Джонс; перевод с англ. Осипов А.И. — М.: ДМК Пресс, 2004.-312 е.: ил.

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

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

77. Зинченко, Л.А. Алгоритмы численно-аналитического моделирования и средства программной поддержки САПР электронных устройств. /Л.А. Зинченко Таганрог: Изд-во ТРТУ, 1999. 194 с.

78. Зыков, A.A. Основы теории графов. / A.A. Зыков — М.: Наука. Гл. ред. физ. мат. лит., 1987. - 384 с.

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

80. Ильин, В.Н. Основы автоматизации схемотехнического проектирования / В.Н. Ильин. — Изд. 2-е, перераб. и доп. М.: Энергия, 1979.-392 е.: ил.

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

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

83. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ. / Под ред. И.Ф. Шахнова. М.: Радио и связь, 1981. - 560 е., ил.

84. Кнут, Д.Э. Искусство программирования: в Зт. / Д.Э. Кнут; пер. с англ. М.: Издательский дом «Вильяме», 2001. - 720 е.: ил.

85. Колесников A.B. Гибридные интеллектуальные системы. Теория и технология разработки/ Под ред. A.M. Яшина СПб.: СПбГТУ, 2001.

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

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

88. Круглов, В.В. Искусственные нейронные сети. Теория и практика. — 2-е изд. /В.В. Круглов, В.В. Борисов М.: Горячая линия -Телеком, 2002. — 382 е.: ил.

89. Кузнецов О.П. Неклассические парадигмы в искусственном интеллекте// Известия РАН: Теория и системы управления. — 1995. №5. -С.3-23.

90. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера —М.: Энергоатомиздат, 1988. -480 с.

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

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

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

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

95. Курейчик В.М. Квантовый алгоритм определения гамильтонова цикла/ Теоретический и научно-методический журнал «Перспективные информационные технологии и интеллектуальные системы», N 1 (21), Таганрог, ТРТУ, 2005, стр. 4-11

96. Курейчик В.М. Совместные методы квантового и бионического поиска. Труды конференций IEEE AIS'04, CAD-2004, М.: Физматлит, 2004. с. 12-19.

97. Курейчик, В.М. Совместные методы квантового и бионического поиска. Труды конференций IEEE AIS'04, CAD-2004 / В.М. Курейчик М.: Физматлит, 2004. с. 12-19

98. Лапчик, М. П. Численные методы : учеб. пособие для студ. высш. учеб. Заведений /М. П. Лапчик, М. И. Рагулина, Е. К. Хеннер; под ред. М. П. Лапчика. 3-е изд., стер. - М.: Издательский центр «Академия», 2007. - 384 с.

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

100. Лизунова, Н. А. Матрицы и системы линейных уравнений / H.A. Лизунова, С.П. Шкоба. М.: ФИЗМАТЛИТ, 2007. - 352 с.

101. Люгер Дж.Ф. Искусственный интеллект. Стратегии и методы решения сложных проблем: Пер с англ. М.: Изд. Дом «Вильяме», 2003.

102. Мищенко, В.А. Интеллектуальные системы автоматизированного проектирования больших и сверхбольших микросхем / В.А. Мищенко, Л.М. Городецкий, Л.И. Гурский и др.; Под ред. В.А. Мищенко. М.: Радио и связь, 1988. - 272 е.: ил.

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

104. Норенков И.П. Разработка систем автоматизированного проектирования. Учебник для вузов. — М.: Изд — во МГТУ им. Н.Э. Баумана . 1994.-207 е., ил.

105. Норенков, И.П. Основы автоматизированного проектирования: Учеб. для вузов. 2-у изд., перераб. и доп. / И.П. Норенков М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 336 е.: ил.

106. Опадчий Ю.Ф. Аналоговая и цифровая электроника (Полный курс): Учебник для вузов / Под ред. О. П. Глудкина. — М.: Горячая линия -Телеком, 2002. 768 с.

107. Оссовский, С. Нейронные сети для обработки информации / С. Оссовский Пер. с польского И.Д. Рудинского. — М.: Финансы и статистика, 2002. 344 е.: ил.,

108. Павлов В.Н., Ногин В.Н. Схемотехника аналоговых электронных устройств: Учебник для вузов. — М.: Горячая линия — Телеком, 2001. 320 с.

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

110. Петренко А.И. Основы автоматизации проектирования. К.: Техшка, 1982. - 295 е., ил.

111. Поспелов Г.С. Искусственный интеллект основа новой информационной технологии. - М.: Наука, 1988.

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

113. Рено, Н.Н.Численные методы / Н.Н.Рено. М.: КДУ, 2007. - 100с.

114. Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования// Новости искусственного интеллекта. 2000. - №3. - С. 159-170.

115. Родзин С.И. Проектирование самотестируемых СБИС с применением метода генетического поиска. Известия ТРТУ, №3, Таганрог, 1997.

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

117. Страуструп, Б. Язык программирования С++. / Б. Страуструп; пер. с англ. М.: ООО «Бином-Пресс», 2005 г. -1104 е.: ил.

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

119. Фоминых И.Б. Принципы построения гибридных интеллектуальных систем реального времени // Труды Международногоконгресса «Искусственный интеллект в ХХ1-М веке». — М.: Физматлит, 2001. — Т.2. С.570-583.

120. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. М: Техносфера, 2004. - 320 с.

121. Хакен Г. Тайны природы. М.: Институт компьютерных исследований, 2003.

122. Харари, Ф. Теория графов / Ф. Харри; пер. с англ. В.П. Козырева.- М.: Едиториал УРСС, 2003. 296 с.

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

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

125. Эннс, В.И. Проектирование аналоговых КМОП-микросхем. Краткий справочник разработчика / Эннс В.И., Кобзев Ю.М. Под редакцией канд. техн. наук В.И. Эннса. М.: Горячая линия - Телеком. - 2005. - 454 е.: ил.

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

127. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. / под ред. В.М. Курейчика. Учебное пособие. Ростов — на Дону: Ростиздат, 2004.