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

• Балюк, Любовь Владимировна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Балюк, Любовь Владимировна

ВВЕДЕНИЕ

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. Разработка модифицированного алгоритма Ant Colony

3.3. Разработка модифицированных генетического и эволюционного алгоритмов размещения фрагментов БИС

3.4. Разработка параллельного алгоритма размещения фрагментов БИС

3.5. Выводы

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

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

4.2. Описание программной реализации интегрированного алгоритма размещения фрагментов БИС

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

4.4. Выводы

Введение диссертации (часть автореферата) на тему «Разработка и исследование интегрированных алгоритмов размещения элементов на основе методов эволюционного моделирования»

Технологии интеграции сверхвысокого уровня (Very Large Scale Integration - VLSI), Standart Cells, Mask-Programmed Gate Arrays (MPGAs) явились основой повсеместного применения практически неограниченных возможностей цифровых интегральных схем (ИС) за минимальную плату. Каждая из этих тепологий, тем пе менее, предполагает огромные капиталовложения в производство, а также временные затраты па весь процесс проектирования.

Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидепт фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год па протяжении последующих 10 лет. Это предсказание впоследствии было названо законом Мура [1]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года.

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

Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции БИС на уровне узлов, блоков и ЭВС [3 - 8]. Сегодня БИС способны выполнять сложнейшие наборы функций, содержат более миллиона транзисторов па кристалле [9], а сами геометрические размеры транзисторов сократились до 0,18 мкм.

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

Programmable Gate Arrays - FPGA) - стали эффективным решением проблем, связанных с прогнозированием риска и временными показателями освоения рынка электронных технологий.

Технология создания FPGA обеспечила возможность «реального» производства гибких схем (прототипов) за минимальную стоимость: время выпуска 1 прототипа занимает несколько минут, а его стоиомсть составляет около 100 долларов. Ренрограммируемое устройство - это гибкая схема, логическая структура которой может быть скорректирована (задана и изменена) конечным пользователем без использования интегрированной схемы (статичной), собранной выпускающей компанией [9J.

Важнейшим этапом в цикле проектирования FPGA, является этап конструкторского проектирования, на котором решаются задачи разбиения (компоновки), планирования, размещения, трассировки (разводки), упаковки, верификации [5J.

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

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

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

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

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

• Построение архитектуры интегрированного алгоритма размещения фрагментов БИС, основанного на методах эволюционного моделирования.

• Разработка интегрированного подхода и алгоритмов размещения.

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

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

Научная новизна работы заключается в решении задачи размещения фрагментов БИС на основе интегрированного подхода. В работе:

1. Построена новая архитектура интегрированного поиска решений задачи размещения фрагментов БИС.

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

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

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

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

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

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

2. Модифицированную архитектуру алгоритма Ant Colony для решения задачи размещения фрагментов БИС.

3. Усовершенствованные операторы размещения, обеспечивающие уменьшение времени поиска.

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

Разработанный программный комплекс решения задач размещения фрагментов БИС реализован с использованием визуальной среды программирования Borland С-н- Builder 6.0, СИ иод WINDOWS.

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

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

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно-исследовательских работах Таганрогского государственного радиотехнического университета (ТРТУ), по гранту Министерства образования и науки РФ, а также научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12354, 12362). Результаты этих работ внедрены и используются в учебном процессе на кафедре САПР ТТИ ЮФУ (г. Таганрог). Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Балюк, Любовь Владимировна

4.4. Выводы

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

В холе выполнения диссертационной работы получены результаты:

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

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

3. Предложены новые и усовершенствованные генетические операторы, обеспечивающие уменьшение времени поиска.

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

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

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

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

8. Выполнены тестирование и обработка экспериментальных данных, что позволило улучшить качество размещения па 29%, время решения от 10% до 30%.

Список литературы диссертационного исследования кандидат технических наук Балюк, Любовь Владимировна, 2007 год

1. Schallcr Robert R. MOORE IS LAW: past, present, and future. IEEE SPECTRUM JUNE, 1997, pp. 53 59.

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

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

4. Системы автоматизированного проектирования: В 9-ти кн. Кп. 6. Автоматизация конструкторского и технологического проектирования: Учеб. пособие для втузов/11од ред. Порспкова И.П. М.: Высшая школа, 1986. 160 с.

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

6. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

7. Деньдобрспко Б.11., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высш. шк., 1980. -384 с.

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

9. Stephen D. Brown. Field-Programmable Gate Arrays. Kluwer Academic Publishers, 1992,-210 p.

10. Под редакцией Морозова K.K. Методы разбиения схем РЭА па конструктивно закопченные части. М.: Советское радио, 1978.

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

12. Cong J., Sung Kyu Lim. Multiway Partitioning with Pairwise Movement // UCLA Department of Computer Science, Los Angeles, CA. 1996.

13. Sanchis L.A. Multiple-way network partitioning // IEEE Trans, on Computers. 1989.

14. Shahookar K., Ma/.umdcr P. VLSI Cell Placement Techniques. // Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109. «ЛСМ Computing Surveys», Vol. 23, No. 2, June 1991.

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

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

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

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

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

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

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

22. Норенков И.П. основы автоматизированного проектирования. Учебник для вузов. 3-е изд., перераб. и доп. М.: Изд-во МГТУ им. Баумана, 2006.-448 с.

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

24. Karypis G., Aggarwal R., Kumar V., and Shekhar S. Multilevel hypcrgraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 1997.

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

26. Kureichik V.V., Kurcichik V.M., Genetic Algorithms. I1G Verlag, Konstans, 2004.

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

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

29. Никифоров A.M. Выбор критериев размещения. Известия ТРТУ № 3, 1999. стр. 300-301.

30. Alpert C.J. et all. Ilypcrgraph Partitioning with Fixed Vertices. //V.19, №2, February 2002, pp. 267 271.

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

32. Гладков J1.A., Курейчпк В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курсйчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002.82 с.

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

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

35. J. Хи, Р. N. Guo, and С. К. Cheng, "Rectilinear block placement using sequence-pair," in Proc. 1998 ACM/1FFF Int. Syrnp. on Physical Design, Monterey, С A, Apr. 6-8, 1998, pp. 173-178.

36. Ойхман Е.Г. Графические системы для СМ ЭВМ. М.: Паука, 1986

37. Sherwani Navccd. Algorithms for VI,SI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.

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

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

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

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

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

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

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

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

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

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

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

49. Моисеев Н.Н. Современный рационализм. М.: MI В11 Кокс, 1995.

50. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. М.: Паука, 1990.

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

52. Eisemann II. and Johannes P.M. Gcncric global placement and door planning. // in Proc IRE/ACM Int Conf CAD 1998. pp. 269-274.

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

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

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

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

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

58. Caldwell А.Е., Kahng А.В. and Markov I. Г. Optimal Portitioncrs and End •Case Placers for Standard Cell Layout. -//-V.19, №11, November 2000, pp. 1304- 1313.

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

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

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

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

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

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

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

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

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

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

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

70. 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.

71. Mak W.K. Mic Cut Partitioning With Functional Replication for Technology Mapped Circuits Using Minimum Area Over hed. //V.21, №4, april 2002, -pp.491 496

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

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

74. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. PAII, №10, Москва, 2001, с. 174187.

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

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

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

78. Colorni A., Dorigo М., Maniezzo V., "Distributed Optimization by Ant Colonics," Proceedings of the First Huropcan Conference on Artificial Life, Paris, France, F.Varela and P.Bourginc (lids.), Hlsevicr Publishing, 134 142, 1991.

79. Colorni A., Dorigo M., Maniezzo V., "The Ant System: Optimization by a colony of cooperating agents," Tcch.Rep.IRIDIA/94-28, Universitc Libre dc Bruxelles, Belgium, 1996.

80. Балюк JI.B. Сравнительный анализ возможностей вероятностного генетического алгоритма Ant Colony с алгоритмами полного перебора с симметричной матрицами для решения задачи о коммивояжере.

81. Материалы нерпой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. Ростов-на-Дону: Изд-во ЮНЦ РАИ, 2005. с. 195-197.

82. Балюк J1.B. Генетические алгоритмы решения задачи размещения элементов СБИС. Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). с. 66-72.

83. Langton С. (Ed.) Artificial Life. New York: Addison Wesley, 1998.

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

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

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

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

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

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

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

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

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

93. Breuer М. Min cut placement. J. Des. Autom. and Fault Tolerant Comput., 1997. V. 1. pp. 343-362.

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

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

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

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

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

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

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

101. Ведерникова О.Г. Разработка и исследование комбинированного генетического алгоритма генетического поиска и имитации отжига для задачи размещения элементов СЬИС: Дне. к.т.н. Ростов и/Д РГЛ сельхозмашиностроения, 1999.

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

103. Гладков JI.Д., Курсйчик В.В., Курсйчик В.М. Дискретная математика. Часть 2. Теория алгоритмов и алгебра логики: Учебное пособие. Под ред. В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2006. 152 с.