Разработка и исследование генетических алгоритмов компоновки блоков ЭВА тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Смирнова, Ольга Валентиновна

• Смирнова, Ольга Валентиновна
• кандидат технических наук
• 2002

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

Введение.

1. Анализ и состояние проблемы компоновки блоков ЭВА.

1.1 Графовые и гиперграфовые модели блоков ЭВА.

1.2 Постановка задачи компоновки.

1.3 Обзор существующих алгоритмов разбиения.

1.4 Выводы.

2. Разработка поисковых методов компоновки графовых моделей блоков ЭВА.

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

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

2.3. Построение архитектур генетического поиска при разбиении графа на части.

2.4. Выводы.

3. Разработка комбинированных генетических алгоритмов компоновки блоков ЭВА.

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

3.2. Разработка эвристического алгоритма разбиения графов на основе агрегации фракталов.

3.3. Разработка алгоритмов разбиения графов с использованием клик, независимых множеств графов.

3.4. Выводы.

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

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

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

4.3. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование генетических алгоритмов компоновки блоков ЭВА»

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

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

Большой вклад в разработку и исследование САПР и эволюционного моделирования внесли Б.В.Баталов, Д.И.Батищев, Л.С.Берштейн, И.Л.Букатова, Ж.Н.Зайцева, Г.Г.Казенов, В.П.Корячко, В.М.Курейчик, Н.Я.Матюхин, А.Н.Мелихов, И.П.Норенков, Л.А.Растригин, Г.Г. Рябов, Ю.О.Чернышев, Д.Гольдберг, Ж.Грефенстетте, Л.Дэвис, И.Чамберс, Д.Холланд и многие другие.

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

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

Цель диссертационной работы состоит в разработке и исследовании комбинированных поисковых и генетических алгоритмов компоновки блоков ЭВА.

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

• Построение графовых и гиперграфовых моделей схем ЭВА для этапа конструкторского проектирования.

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

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

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

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

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

2. Построены новые модифицированные операторы генетического поиска, ориентированные на комбинаторно-логические задачи САПР.

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

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

1. Генетические алгоритмы разбиения графов с генетическими операторами на основе дихотомического деления, чисел Фибоначчи, методов «золотого сечения»и агрегации фракталов.

2. Модифицированные поисковые алгоритмы построения клик графа и независимых подмножеств.

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

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

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Ростовской государственной академии сельхозмашиностроения (РГАСХМ): « Основы вычислительного представления генетических алгоритмов для решения оптимизационных задач» и «Развитие эволюционного моделирования для решения оптимизационных задач».

Результаты этих работ внедрены на предприятии г. Ростова-на Дону. Материалы диссертации используются в учебном процессе в ТРТУ (г.Таганрог) и РГАСХМ (г. Ростов-на Дону). Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

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

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

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

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

4.3. Выводы

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

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

3. Использование новых ГО позволяет улучшать качество решений.

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

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

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

Заключение

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

2. Построены поисковые алгоритмы разбиения: дихотомии; на основе чисел Фибоначчи; «золотого сечения»; поиска в глубину, ширину, с возвратом; метода «горизонта», позволяющие решать проблемы предварительной сходимости алгоритмов и получать квазиоптимальные и оптимальные решения. Временная сложность этих алгоритмов не выходит за пределы полиномиальной области.

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

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

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

6. Приведены теоремы построения минимальных и квазиминимальных массивов в графах. На их основе разработан модифицированный алгоритм агрегации фракталов для разбиения графов на части с ВСА 0(А,п ) для одной генерации.

Список литературы диссертационного исследования кандидат технических наук Смирнова, Ольга Валентиновна, 2002 год

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

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

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

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

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

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

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

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

9. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983.

10. Ю.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемыезадачи. М.: Мир, 1982.

11. П.Малышев Н.Г., Берштейн Л.С., Боженюк A.B. Нечеткие модели для экспертных систем в САПР. М.: Энергоатомиздат, 1991.

12. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: Изд-во РГУ, 1991.

13. Чернышев Ю.О. Методы оптимизации комбинаторных устройств. М.: Советское радио, 1977.

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

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

16. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.17.0ре О. Т. Теория графов. М.: Наука, 1973.

17. Харари Ф. Теория графов. М.: Мир, 1977.

18. Мелихов А.Н., Берштейн J1.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

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

20. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на-Дону: Изд-во РГУ, 1999.

21. Kernighan В., Lin S. An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech.J., v.49, Feb 1970, pp. 291-307.

22. Fiduccia C., Mattheyses R. A linear time heuristics for improving network partitions. Proceedings 19th ACM/IEEE Design automation conference, 1982, pp. 175-181.

23. Saab Y. G., Rao V. B. Fast Effective Heuristics for the Graph Bisectioning Problem, IEEE, Transaction on CAD. V.9, N1, January 1990, pp.

24. Wei Y.C., Cheng C.K. A two-level two-way partitioning algorithm, Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

25. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. A general purpose multiple way partitioning algorithm. Proceedings 28th ACM/IEEE Design Automation Conference, paper 25/1, 1991, pp.421-425.

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

27. Ackley D.H. A connectionist Machine for Genetic Hillclimbing. Kluvvcr Academic Publishers, Boston, MA, 1987.

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

29. Курейчик B.M., Курейчик B.B. Генетический алгоритм разбиения графа// Известия АН. Теория и системы управления, № 5, 1999, с.79-87.

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

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

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

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

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

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

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

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

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

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

40. Норенков И.П., Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации// Информационные технологии, №2, 1999, с.2-7.

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

42. Растригин JI.A. Статистические методы поиска. М.: Наука, 1968.

43. Rastrigin L.A. Random Search in Evolutionary Computations. Proceedings 1st International conf., Evolutionary Computation and Its Application, EvCA 96, Moscow, 1996, pp. 135-143.

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

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

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

47. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.l, Washington,US A, CRC Press, 1995.

48. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.2, Washington,US A, CRC Press, 1995.

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

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

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

52. Вороновский Г.К. и др. Генетические алгоритмы, искусственные нейроны сети и проблемы виртуальной реальности. Харьков, Украина, Основа, 1997.

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

54. Kureichik V.M, Kureichik V.V. A Genetic Algorithms for Graph Partitioning. Journal of Computer and Systems Sciences International,vol.38, №4, 1999, pp.580-588.

55. Курейчик B.B. Алгоритмы разбиения графа на основе генетического поиска// Известия ТРТУ, N3. 1999,с.97-104.

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

57. Дубинин Н.П. Избранные труды, Т.1. Проблемы гена и эволюции. М.: Наука,2000.

58. Хакен Г. Синергетика. Иерархия неустойчивостей в самоорганизующихся системах и устройствах. М.: Мир, 1985.

59. Емельянов В.В. Метод построения математических моделей сложных дискретных систем и процессов// Вестник МГТУ. Серия Машиностроение, 1993, №1, с. 14-19.

60. Artificial Life. / Eds С. Langton.,Т. Shimohara. Cambridge MA: MTT PRESS,1996.

61. Fogel D.B. Evolutionary computing. IEEE Spektrum, February,2000, pp.2633.

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

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

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

65. Курейчик В.В., Смирнова О.В. Эволюционное моделирование при принятии решений // Известия ТРТУ, № 4, Таганрог, 2002, с.57-64.

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

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

68. Астанин C.B., Берштейн Л.С., Захаревич В.Г. Проектирование интеллектуального интерфейса «человек-машина». Ростов-на-Дону: Изд-во РГУ, 1990.

69. Гладков Л.А. Курейчик В.М. Методы решения 03 с использованием интеллектуальных технологий// Труды 7-ой национальной конференции по ИИ с международным участием Т. 2, М.: Наука,2000,с.532-541.

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

71. Карелин В.П., Родзин С.И. УМП по методам математического программирования (поисковой оптимизации). Таганрог: Изд-во ТРТУ,1999.

72. Смирнова О.В. Построение генетических операторов, основанных на дихотомическом разбиении // Известия ТРТУ, № 4, Таганрог, 2002, с.134-135.

73. Смирнова О.В. Метод локального поиска для разбиения схем ЭВА //Перспективные информационные технологии и интеллектуальные системы, №2(10), 2002, с.

74. Андрейчиков A.B. Андрейчикова О.Н. Компьютерная поддержка изобретательства. М.: Машиностроение, 1998.

75. Ботвинник М.М. О решении неточных переборных задач. М.: Советское радио, 1979.

76. Алексеев A.B., Борисов А.Н. и др. Интеллектуальные системы принятия проектных решений. Рига: Зинатне, 1997.

77. Кнут Искусство программирования Т.3.2002.

78. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска// Автоматика и телемеханика РАН №10. М.: Изд-во Наука, 2001,с.174-187

79. Князева E.H., Курдюмова С.П. Законы эволюции и самоорганизации сложных систем. М.: Наука, 1994.

80. Cohoon J.P., Paris W.D. Genetic Placement, IEEE Trans, on CAD, v.6, No 6, November, 1987. pp. 956 964.

81. Кордюм В.А. Эволюция и биосфера. Киев: Наук. Думка, 1982.

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

83. Ларичев О.И. и др. Выявление экспертных знаний. M.: Наука, 1989.

84. Банди Б. Методы оптимизации. М.: Радио и связь, 1988.

85. Лебедев Б.К. Адаптация в САПР. Таганрог: Изд-во ТРТУ,1999.

86. Будущее искусственного интеллекта//Под ред. К.Е. Левитина и Д.А.Поспелова. М: Наука, 1991.

87. Пайтген Х.О., Рохтер П.Х. Красота фракталов. М.: Мир, 1990

88. Кроновер P.M. Фракталы и хаос в динамических системах. Основы теории. М.: Постмаркет,2000.

89. Дульнев Т.Н. Введение в синергетику. СПб.: Изд-во «Проспект», 1998.

90. Колесников A.A. Основы теории синергетического управления. М.: Фирма «Испо- Сервис»,2000.

91. Винер Н. Кибернетика или управление и связь в животном мире. М.: Сов. радио, 1968.

92. Лоскутов А.Ю. Синергетика и нелинейная динамика: новые подходы к старым проблемам. Синергетика// Труды семинара. Том 3. М.: Изд-во МГУ, 2000 с.204-224.

93. Смирнова О.В. Модели эволюции в задачах компоновки схем ЭВА //Перспективные информационные технологии и интеллектуальные системы, №1(9), 2002, с.47-49.

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

95. Johnson D.S. Fast Algorithms for Bin Packing. J. Computer Sys. Sci.,8, 1974.

96. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.

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

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

99. ЮО.Курейчик В.М. Дискретная математика, Часть 2. Элементы теории графов. Таганрог: Изд во, ТРТУД997.

100. Курейчик В.В. Построение и анализ генетических алгоритмов раскраски графа на основе моделей искусственных систем// Труды международного конгресса ICAI-2001, Искусственный интеллект в 21-веке. М.: Физмалит, 2001,с.665-675

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

102. Chandrasekharam R., Subhramanian and chadhurys. Genetic algorithms for node partitionaly problem and application in VLSI design. IEEE Proc-E, v. 140, N.5, September, 1993. pp. 167- 178.

103. Bui T. N., Moon B. R. Genetic algorithm and graph partitioning, IEEE Trans. Comput., vol.45, 1996, pp. 841-855.

104. Frohlich N., Glockel V., Fleischmann J. A new partitioning method for parallel simulation of VLSI circuits on transistor level. Proceedings Design, Automation and Test in Europe Conference, 2000, Paris, France, 27-30 March 2000, pp.679-685.