Разработка и исследование генетических алгоритмов решения задач компоновки элементов и трассировки СБИС тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Ищенко, Станислав Николаевич

• Ищенко, Станислав Николаевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Ищенко, Станислав Николаевич

Содержание.

Введение.

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

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

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

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

1.4. Выводы.

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

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

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

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

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

2.5. Выводы.

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

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

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

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

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

3.5. Выводы.

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

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

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

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

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

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

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

4.4. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование генетических алгоритмов решения задач компоновки элементов и трассировки СБИС»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Ищенко, Станислав Николаевич

4.4. Выводы.

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

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

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

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

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

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

Заключение.

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Ищенко, Станислав Николаевич, 2006 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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