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

• Стасенко, Леонид Александрович
• кандидат технических наук
• 2003

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

Содержание.

Введение.

Глава 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. Разработка генетического алгоритма раскраски графа, определение независимых подмножеств и клик графов.

3.5. Построение и анализ эволюционного алгоритма определения паросочетаний графа.

Выводы

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

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

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

Выводы

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

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

Разработка методов и алгоритмов для решения оптимизационных задач на графах осуществляется на протяжении ряда лет, являясь, по-прежнему, актуальной проблемой. Это связано, в первую очередь, с тем, что эти задачи являются NP-полными и NP-трудными. Поэтому затруднительна разработка универсальных методов и алгоритмов, позволяющих находить точное оптимальное решение за приемлемое время. Появление новых, более совершенных средств электронно-вычислительной техники, и, как следствие, увеличение их степени интеграции является причиной для разработки новых совершенных технологий решения задач на графах. Существует несколько подходов к решению NP - полных задач на графах [1-17].

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

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

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

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

Комбинированные алгоритмы при незначительном увеличении времени позволяют получать локально оптимальный результат.

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

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

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

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

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

ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка эволюционных методов и генетических алгоритмов для решения графовых задач. Достижение указанной цели предполагает решение следующих основных задач:

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

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

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

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

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:

1. разработаны принципы разбиения графов на части и размещение графов на плоскости на основе комбинации поисковых и генетических алгоритмов;

2. определена процедура построения «жадных» стратегий для решения оптимизационных задач на графах;

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

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

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ результатов диссертационной работы определяется созданием комплекса программ и алгоритмов для решения задач на графах, позволяющих использовать разработанные математические модели, стратегии, методы и эвристики, отвечающие конкретным конструкторским и технологическим задачам. Программы реализованы на языке С++ под WINDOWS. Проведенные экспериментальные исследования, показали преимущество комбинированных поисковых и генетических алгоритмов для решения оптимизационных задач на графах по сравнению с существующими методами. Разработанные методы и алгоритмы решения графовых задач позволяют получать не одно, а набор оптимальных, или квазиоптимальных результатов. Время получения лучших результатов решения графовых задач соответствует полиномиальному времени, которого требуют итерационные алгоритмы.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические - результаты диссертационной работы использованы в госбюджетных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ № 01-01-00044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

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

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

ПУБЛИКАЦИИ. Результаты диссертации отражены в 6 печатных работах.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Работа содержит 175 стр., а также 84 рис., список литературы из 105 наименований, 2 стр. приложений и актов об использовании.

Заключение диссертации по теме «Теоретические основы информатики», Стасенко, Леонид Александрович

Основные результаты работы сформулированы следующим образом.

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

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

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат технических наук Стасенко, Леонид Александрович, 2003 год

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

2. Горбатов В.А. Основы дискретной математики. М.: Высшая школа, 1987.

3. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир Д 978.

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

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

6. Зыков А.А. Основы теории графов. М.: Наука, 1987.

7. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

8. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

9. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

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

11. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1983.

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

13. Нечепуренко М.И. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние,1990.

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

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

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

17. Курейчик В.М. Дискретная математика Ч.З. Оптимизационные задачи на графах. Таганрог: Изд-во ТРТУ, 1998.

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

19. Моисеев Н.Н. Алгоритмы развития. -М.: Наука, 1987.

20. Пригожин И., Стенгерс И. Порядок из хаоса. -М.: Прогресс, 1986.

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

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

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

24. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.3, Washington,US A, CRC Press, 1999.

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

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

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

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

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

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

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

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

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

34. Zebulum R.S., Pacheco M.C., Vellasco M. Evolutionary Electronics. Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. CRS PRESS, 2002.

35. Genetic Algorithms in Optimizations, Simulation and Modeling. Ed. J. Stendex, E. Hilelbrand and J. Kingdom. IOS PRESS, 1994.

36. Haupt Randy L., Haupt Sue Ellen. Practical Genetic Algorithms. John Willey Ysons, INC, CANADA, 1998.

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

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

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

40. Курейчик В.В., Стасенко Л.А. Применение генетических алгоритмов для решения оптимизационных задач на графах. // Перспективныеинформационные технологии и интеллектуальные системы, № 3 (11), 2002, с.13-19.

41. Стасенко JI.A. Применение методов одномерного поиска для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 4(12), 2002, с.69-71

42. Кини P.JL, Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.

43. Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных Странах. М.: Логос,2000.

44. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. М.: Синтег,1998.

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

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

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

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

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

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

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

52. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.1. Стр. 169

53. Saab. Y. A new effective and efficient multi-level partitioning algorithm. Proceedings Design, Automation and Test in Europe Conference 2000, Paris, France, 27-30 March 2000, pp.112-116.

54. Grefenstette J, Gopal G, Rosmaita В., D. van Gucht. Genetic algorithms for the traveling salesman problem. Proc. Intern. Conf. of Genetic Algorithms and their applications. John Grefenstette, ed. New Jersey, 1987. pp. 160-165.

55. Oliver L, Smith D., and Holland J.R. A study of permutation crossover operators on the traveling salesman problem. Proc. of the Second International Conf. on Genetic Algorithms, pp. 224-230.

56. Kureichik V.M., Miagkikh V. Some New Features in Genetic Solution of the TSP. Proceedings of the second International conference, Plymouth UK, 1996.pp.

57. Стасенко Л.А. Использование «жадных» стратегий для решения графовых задач // Перспективные информационные технологии и интеллектуальные системы, №3(11), 2002, с.88-89.

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

59. Курейчик В.В., Стасенко Л.А. Построение моделей эволюций для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 4 (12), 2002, с. 14-21.

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

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

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

63. Гладков JI.А. и др. Методы генетического поиска // под редакцией В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2002.

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

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

66. Приходченко Н.Н., Шкурат Т.П. Основы генетики человека. Ростов-на-Дону: Феникс, 1997.

67. Genetic Algorithms and Evolution Strategy in Engineering and Computer Science. Editid by D. Quagliarella and et all. John Wiley & Song, NY, USA, 1998.

68. Курейчик B.B., Смирнова O.B. Генетические операторы в задаче компоновки схем ЭВА. // Перспективные информационные технологии и интеллектуальные системы, № 4 (8), 2001, с.41-46.

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

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

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

72. Берштейн Л.С., Боженюк А.В. Введение в теорию нечетких графов. Таганрог. Изд-во ТРТУ, 1999.

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

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

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

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

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

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

79. Курейчик В.М., Курейчик В.В. Об установлении порядка в моделях искусственных систем. // Известия ТРТУ, № 5, Таганрог, 2001, с.43-59.

80. Курейчик В.М., Курейчик В.В. Фрактальный алгоритм разбиения графа // Известия АН. Теория и системы управления, № 4, 2002, с.65-75.

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

82. Стасенко Л.А. Основные принципы генетического поиска для решения задач на графах. // Перспективные информационные технологии и интеллектуальные системы, № 1 (13), 2003, с.27-31.

83. 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, v.24, No.l, 1994, pp. 73 86.

84. Shahookar K.,Mazumder P. A Genetic Approach to standard Cell Placement Using Meta-Genetic Parameter Optimization. IEEE Trans, on CAD, v.9, No.5, 1990, pp. 500-511.

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

86. Kling R.M., Banerjee P.: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, 1989. pp. 245-256.

87. 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.1. Стр. 172

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

89. Paris W. GENIF: A new placement Algorithms. Thesis (ms) University of Virginia, USA, 1989.

90. Mayer M. Parallel GA for the DAG Vertex spelling problem. Thesis, Univesity of Missouri, USA, 1993.

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

92. Таха, Хэмди А., Введение в исследование операций. М.: Издательский дом «Вильямс»,2001.

93. Литвиненко В.А., Логинов В.А. К вопросу применение метода параметрической адаптации для задачи определения клик графа// Известия ТРТУ, № 3, Таганрог, 1999, с.301-302.

94. Литвиненко В.А. Адаптивные алгоритмы на графах // Известия ТРТУ, № 2, Таганрог, 2000, с. 186-189.

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

96. Курейчик В.В., Курейчик В.М., Стасенко Л.А. Построение и анализ эволюционного алгоритма определения паросочетаний графа. //Интегрированные модели и мягкие вычисления в ИИ. М.: Физматлит, 2003, с.41-47.

97. Wolfe G., Wong J.L. and Potkonjak M.Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, №10, October 2002, pp. 1196 1204

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

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

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

101. Sul., Buntine., Newton A.R. and Peters B.B. Learning as Applied to Stochastic Optimization for Standard Cell Placement. -//-V. 20, №4, april 2001, pp. 516-527

102. Tsuya A., Tanaka A. A Fractal representation of city distribution using renormalization coordinates proceedings. 2001 Int. symposium on nonlinear theory and its applications, Miyagi, Japan, 2001, pp.319-322.

103. Cordone R., Ferrandi F., Scinto D. and Calvo Wolfler.An Efficient Heuristic Approach to solve the Unate Covering Problem. -//-V. 20, №12, gecember 2001, pp. 1377-1388.