Разработка инструментальных средств для исследования и конструирования генетических алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Минаков, Игорь Александрович

• Минаков, Игорь Александрович
• кандидат технических наук
• 2000

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

ВВЕДЕНИЕ

ГЛАВА 1 МЕТОДЫ ПОИСКА И ОПТИМИЗАЦИИ

1.1. Проблема поисковой оптимизации. Общая постановка задачи

1.2. Класс проблем, к которым неприменимы обычные детерминистические методы

1.3. Эвристические методы поиска и оптимизации

1.3.1. Методы случайного поиска

1.3.2. Моделируемый отжиг

1.3.3. Поиск с "запретами"

1.3.4. Генетические алгоритмы

1.3.5. Подход с использованием нечеткой логики

1.3.6. Нейронные сети

1.3.7. Эволюционное программирование

1.3.8. Остальные эвристические методы цоиска и оптимизации

1.4. Сопоставление эвристических методов поиска на примере некоторых задач. Проблема оптимального подбора параметров

1.5 Особенности и отличия генетических алгоритмов

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

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

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

Проблема оптимизации и построения модели системы является трудноформа-лизуемым процессом, в значительной степени определяющимся уровнем исходной информации. По мере усложнения систем и увеличения априорной неопределенности возникает необходимость создания специализированных методов анализа. Далеко не все уровни естественных, производственных и социальных комплексов имеют развитый аппарат для своего описания, а тем более для конструирования эффективных имитационных моделей с целью получения необходимых оценок проблемных ситуаций. Часто возникает существенная и принципиально неустранимая неполнота наших знаний, проявляющаяся как во фрагментарности эмпирических данных, так и в отсутствии закономерностей эволюции природных или технических процессов. Ситуация такова, что необходимо применение такой технологии моделирования и оптимизации, которая в отличие от традиционных учитывает внутреннюю динамику (эволюцию) структуры моделируемых процессов и адаптивно синтезирует модели в условиях неполноты и частичной достоверности данных [6, 8, 32].

Таким образом, все чаще встречаются задачи, в которых точные математические методы слабо применимы или неприменимы вовсе. Это связано с целым рядом проблем, основными из которых являются проблема размерности и проблема априорной неопределенности, Поэтому необходим альтернативный подход - использование эвристических методов и намеренное введение элемента случайности и вероятностного механизма в алгоритм поиска, при этом алгоритм поиска должен подчиняться эволюционной парадигме [5, 12, 37].

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

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

Основополагающей работой в области генетических алгоритмов можно считать работу Дж. Холланда (J. Holland) [90]. В дальнейшем Д. Голдберг (D. Goldberg) [84] выдвинул ряд гипотез и теорий, помогающих глубже понять природу генетических алгоритмов. К. ДеДжонг (К. DeJong) первым обратил внимание на важность настройки параметров ГА для общей эффективности работы и предложил свой оптимальный вариант подбора параметров [67], который послужил основой для всех дальнейших исследований. Существенный вклад в эти исследования внесли Дж. Грефенстетт (J. Grefenstette ) [87] и Г. Сисверда (G. Syswerda) [111].

В России одним из первых вопросом исследования альтернативы детерминистическим методам занимался JI.A. Растригин [31]. Также интересную теорию, во многом аналогичную ГА, предложил А.Г. Ивахненко [13]. Вопросами эволюционного моделирования одними из первых занимались И.Л.Букатова [5, 6], A.C. Антонов [1], В.Ф. Левченко и В.В. Меншуткин [25], Д.С. Чернавский и Н.М. Чернав-ская [43].

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

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

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

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

В том числе к научной новизне можно отнести следующие результаты:

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

- Предложены методы конструирования эффективных ГА для решения прикладных задач.

- Исследован вопрос о выборе эффективной схемы селекции и ее параметров, определяющий скорость сходимости ГА и точность получаемых результатов. Даны рекомендации по применению различных методов селекции.

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

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

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

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

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

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

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

Внедрение результатов работы. Разработанные в диссертации методы и алгоритмы использовались при выполнении госбюджетных научно-исследовательских работ (Гос. per. № 01.9.60002398) в Институте проблем управления сложными системами РАН (Самара), внедрены в учебный процесс Самарского муниципального университета Наяновой (Самара), Поволжской государственной академии телекоммуникаций и информатики (Самара).

Апробация работы. Основные положения и результаты данной работы изложены и обсуждены на VI Международной конференции " Математика, компьютер, образование" (г. Пущино, январь 1999 г.); научной конференции "Управление сложными системами" (Самарский научный центр РАН, сентябрь 1999 г. ), Международной конференции "Проблемы управления и моделирования в сложных системах", (Самара, Самарский научный центр РАН, июнь 1999 г.), "Математическое моделирование и краевые задачи" (IX межвузовская конференция, г. Самара, 1999 г.) а также на научно-технических семинарах Института проблем управления сложными системами РАН, г. Самара, на научно-технических конференциях Самарского муниципального университета Наяновой.

Публикации. По теме диссертации опубликовано 9 печатных работ, в том числе 8 статей, 1 тезисы доклада.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и заключения. Объем работы 162 страницы основного текста, включая 29 рисунков и 27 таблиц. Список использованных источников содержит 116 наименований. Дополнительно включено 2 приложения.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Минаков, Игорь Александрович

Основные выводы и результаты

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

2. Разработано специальное математическое, алгоритмическое и программное обеспечение и созданы пакеты прикладных программ для анализа работы ГА, применения и гибкой настройки ГА при решении целого ряда прикладных задач.

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

4. Даны рекомендации по применению различных методов селекции, являющихся критичными по отношению к производительности ГА.

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Минаков, Игорь Александрович, 2000 год

1. Основные работы автора по теме диссертации

2. AI. Минаков H.A. Сравнительный анализ некоторых методов случайного поиска и оптимизации // Известия Самарского научного центра Российской академии наук. Самара: Самарский научный центр РАН, № 2. 1999. С. 286-293.

3. А2. Кораблин М.А., Минаков И.А. Эволюционные алгоритмы в имитационном моделировании // Проблемы управления и моделирования в сложных системах: Труды международной конференции. Самара: Самарский научный центр РАН. 1999. С. 45-50.

4. A4. Кораблин М.А., Минаков И.А. Применение генетических алгоритмов при решении класса задач "продавец потребитель" // Рыночная экономика: состояние, проблемы, перспективы. Сборник науч. трудов. Вып. 3. Самара: ИПО СГАУ. 1999. С. 383-388.

5. А6. Минаков И.А. Применение генетических алгоритмов для нахождения оптимального набора параметров // Математическое моделирование и краевые задачи: Труды IX межвузовской конференции. Ч. 2. 1999. Самара: СамГТУ. С. 92-94.

6. А7. Минаков И.А. Генетические алгоритмы в задачах эволюционного моделирования // Математика, компьютер, образование: Тез. докл. VI междунар. конф. (г.Пущино, 24-31 января 1999 г.) 1999. С. 188.

7. А8. Минаков И.А. О выборе оптимального метода селекции для генетического алгоритма // Вестник Самарского гос. техн. ун-та. Вып. 8. Самара: СамГТУ. 2000. С.198-203.

8. А9. Minakov I. Basic Overview of Genetic Algorithms // George Washington University, 1998.1. Другие источники

9. Антонов А. С. Генетические основы эволюционного процесса. М.: Знание, 1983. 64с.

10. Беркинблит М.Б. Нейронные сети М., МИРОС, 1993 г.

11. Болтянский A.A., Виттих В.А., Кораблин М.А., Куклин Г. Н., Сидоров А. А., Шамашов М. А. Цифровая имитация автоматизированных систем, - М.: Наука, 1983.

12. Боровицкий М.Д., Смирнов C.B. Реализация и исследование производительности объектно-ориентированной СУБД // Программирование, № 6, 1992, с. 18-28.

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

14. Букатова И. JL, Михасев Ю. И., Шаров А. М. Эвоинформатика: теория и практика эволюционного моделирования. М: Наука, 1991. 205 с.

15. Буч Г. Объектно-ориентированное проектирование с примерами приложения: Пер. с англ. М.: Конкорд, 1992. 519с.

16. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов. Уфа: Уфимск. гос. авиац. техн. ун-т. 1999. 105 с.

17. Дал У. И. Языки для моделирования систем с дискретными событиями. Сб. "Языки программирования". М: Мир, 1972. с. 344-401.

18. Ю.Дромашко С. Е., Романовский Ю. М. Эволюция математических моделей генетики. -М: Знание, 1984. 64с.

19. Жиглявский A.A., Жилинскас А.Г. Методы поиска глобального экстремума -М.: Наука. 1991.

20. Зайцева E.H. Станкевич Ю.А. Некоторые современные методы решения оптимизационных задач // Материалы Второй международной конференции "Новые информационные технологии в образовании". 1996.

21. Ивахненко А.Г. Системы эвристической самоорганизации в технической кибернетике. Киев: Техника. 1971.

22. Кандрашина Е.Ю., Литвинцева JI.B., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах M : Наука, 1989 г.

23. Киндлер Е. Языки моделирования. Пер. с чеш. М.: Энергатомиздат. 1985. 288с.

24. Клейнен Дж. Статистические методы в имитационном моделировании: Пер. с англ. Вып.1 М.: Статистика. 1978.221 с.

25. Колемаев В.А. Математическая экономика. М.: ЮНИТИ. 1998.

26. Компьютер обретает разум / Под ред. B.JI. Стефанюка М.: Мир, 1990 г.

27. Кораблин M. A. EXCEL для менеджера: решение оптимизационных задач. -Самара: СГАУ.60 е., 1998.

28. Кораблин М. А. Реинжиниринг бизнес-процессов новое направление современного менеджмента. Сб. "Рыночная экономика: состояние, проблемы, перспективы", выпуск 2.- Самара: ИПО СГАУ, 1998, с.50-54.

29. Кораблин М. А., Смирнов С. В. Наследование свойств в задачах объектно-ориентированного программирования на языке Модула-2.-М.: Программирование, 1990, 4, с.38-43.

30. Кроссовский H.H., Субботин А.И. Позиционные дифференциальные игры, М.: Наука, 1974.

31. Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы

32. Изв. РАН. Теория и системы управления. 1999. № 1, с. 144-160.

33. Ланкастер К. Математическая экономика. М.: Советское радио, 1972.

34. Левченко В.Ф., Меншуткин В.В. Имитация макроэволюционного процесса на ЭВМ // Ж. эвол. биохим. и физиол. 1987. Т.23. N.5. С.668-673.

35. Леонтьев В.В. Межотраслевая экономика. М.: Экономика, 1997.

36. Мичи Д., Джонстон Р. Компьютер творец - М : Мир, 1987 г.

37. Моришима М. Равновесие, устойчивость, рост. М.: Наука ,1972.

38. Нейлор К. Как построить свою экспертную систему М.: Энергоатомиздат, 1991 г.

39. Оно С. Генетические механизмы прогрессивной эволюции. Пер. с англ. М.: Мир. 1973,227 с.

40. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. 376 с.

41. Смирнов С.В. Открытая архитектура инструментальных средств моделирования сложных систем // Проблемы управления и моделирования в сложных системах. Тр. международной конференции. Самара: Самарский научный центр РАН, 1999,с.59-66.

42. Таха X. Введение в исследование операций: в 2-х книгах, перев. с англ., М.: Мир, 1985.

43. Техническая имитация интеллекта / Под. ред. И.М. Макарова М.: Высшая школа, 1986 г.

44. Фишер Ф.Н. Проблемы идентификации в эконометрии. М.: Финансы и статистика, 1978.

45. Фогель Л., Оуэне А., Уолш М. "Искусственный интеллект и эволюционное моделирование" М: Мир, 1969 г.

46. Фон Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971, 382с.

47. Форрестер Дж. Основы кибернетики предприятия. (Индустр. динамика). Пер. с англ. М.: Прогресс, 1971, 340с.

48. Фути К., Судзуки Н. Языки программирования и схемотехника СБИС: Пер. с япон.-М.: Мир, 1988. -224с.

49. Хакен Г. Информация и самоорганизация: Макроскопический подход к сложным системам. М.: Мир, 1991. 240с.

50. Хейс Д. Причинный анализ в статистических исследованиях. Пер. с англ.-М.: Финансы и статистика, 1981.-255с.

51. Хесин Р.Б. Непостоянство генома. М.: Наука, 1985. 474 с.

52. Шеннон Р. Имитационное моделирование систем искусство и наука. - М.: Мир, 1978.

53. Юэ Ж., Оппен Д. Равенства и правила переписывания. Обзор. Сб. "Математическая логика в программировании". Пер. с англ. М.: Мир, 1991, с. 176-232.

54. Языковые средства диалога человека и ЭВМ т.2 / Под ред. В.Н. Четверикова -М.: Высшая школа, 1990 г.

55. Abramson D., Abela J. A Parallel Genetic Algorithms for Solving the School Timetabling Problem.

56. Abramson D.A. Constructing School Timetables Using Simulated Annealing: Parallel and Sequential Solutions, Management Science, pp. 98-113. Jan 1991.

57. Ackley D.H. An empirical study of bit vector function optimization. In L. Davis, editor, Genetic Algorithms and Simulated Annealing, chapter 13, pp. 170-204. Pitman, 1987.

58. Axelrod R. The evolution of strategies in the iterated prisoner's dilemma. In L. Davis, editor, Genetic Algorithms and Simulated Annealing, chapter 3, pp. 32-41. Pitman, 1987.

59. Back T., Hoffmeister F. and Schwefel H.-P. A Survey of Evolution Strategies, in Proceedings of the 4th International Conference on Genetic Algorithms(ICCA IV), ed. R.K. Belew and L.B. Booker, Morgan Kaufman Publishers, Inc., San Diego, 1991.

60. Baker J. E. An Analysis of the Effect of Selection in Genetic Algorithms. PhD thesis, Graduate School of Vanderbilt University, Nashville, Tennessee, 1989.

61. Battiti R., Tecchiolli G. Local Search with Memory: Benchmarking RTS, Operations Research Spectrum, 1995.

62. Beasley David, Bull David R., Martin Ralph R. An Overview of Genetic Algorithms, in 2 parts. University Computing, 1993, 15(2), 58-69

63. Blickle Tobias, Thiele Lothar. A Comparison of Selection Schemes used in Genetic Algorithms. TIK-Report Nr. 11, December 1995.

64. Boese Kenneth. Cost Versus Distance. In the Traveling Salesman Problem, UCLA Computer Science Dept.

65. Booker L. Improving search in genetic algorithm. In L.Davis, editor, Genetic Algorithms and Simulated Annealing, chapter 5, pp. 61-73. Pitman, 1987.

66. Bulmer M.G. The Mathematical Theory of Quantitative Genetics, Clarendon Press, Oxford, 1980.

67. Colorni A., Dorigo M. and Maniezzo V. A Genetic Algorithm to Solve the Timetable Problem. Technical Report No. 90-060, Politécnico di Milano, Italy, 1990.

68. Davis L. Applying adaptive algorithms to epistatic domains. In 9th Int. Joint Conf. on AI, pp. 162-164, 1985.

69. Davis L. Job shop scheduling with genetic algorithms. In J.J. Grefenstette, editor, Proceedings of the First International Conference on Genetic Algorithms, pp. 136140. Lawrence Erlbaum Associates, 1985

70. Davis. L. Handbook of Genetic Algorithms. VanNostrand Reinhold, 1991.

71. Davis L., Ritter F. Schedule Optimization with Probabilistic Search, Proc. 3rd IEEE Conference on Artificial Intelligence Applications, February 1987, Orlando, Florida

72. DeJong K. The Analysis and Behavior of a Class of Genetic Adaptive Systems. PhDthesis, University of Michigan, 1975.

73. DeJong K. Adaptive system design: a genetic approach. IEE Trans SMC, 10:566-574, 1980.

74. DeJong Kenneth A., Spears William M. An Analysis of the Interacting Role of Population Size and Crossover in Genetic Algorithms.

75. Durbin R., Szeliski R., and Yuille A., An Analysis of the Elastic Net Approach to the Travelling Salesman Problem, Neural Computation, Vol. 1, pp. 348-358, 1989.

76. Dzubera J. and Whitley D. Advanced Correlation Analysis of Operators for the Traveling Salesman Problem, Colorado State University, CO 80523

77. Even S., Itai A., Shamir A. On the Complexity of Timetable and Multicommodity Flow Problems, SIAM Journal of Computing, Vol.5, No.4, 1976

78. Fogel D.B. Applying evolutionary programming to selected traveling salesman problem, Cybernetics and Systems 24(1), 1993.

79. Forrest S. and Mayer-Kress G. Genetic algorithms, nonlinear dynamical systems, and models of international security. In L. Davis, editor, Handbook of Genetic Algorithms, chapter 13, pp. 166-185, Van Nostrand Reinhold, 1991.

80. Fourman M.P. Compaction of symbolic layout using genetic algorithms. In J.J. Gre-fenstette, editor, Proceedings of the First International Conference on Genetic Algorithms, pp. 141-153. Lawrence Erlbaum Associates, 1985

81. Freisleben B. and Sculte M. Combinatorial Optimization with Parallel Adaptive Threshold Accepting, In Proc. 1992 European Workshop on Parallel Computing, Barcelona, pp. 176-179. IOS Press, 1992.

82. Gambardella L. M. and Dorigo M., Ant-Q: A Reinforcement Learning Approach to the Travelling Salesman Problem, in Proc. 12th Int. Conf. on Machine Learning, pp. 252-260, Morgan Kaufmann, 1995.

83. Gero John S., Kazakov Vladimir A. Evolving design genes in space layout planning problems. Artificial Intelligence in Engineering, 12, 1998, p. 163-176.

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

85. Goldberg D. and Deb K. A comparison analysis of selection schemes used in genetic algorithms. // In G. Rawlins, editor, Foundations of Genetic Algorithms, pp. 69-93, San Mateo, 1991, Morgan Kaufmann.

86. Goldberg D. and Lingle R. Alleles, loci and the travelling salesman problem. In Proceedings of the Second International Conference on Genetic Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985

87. Goldberg D.E. Alleles, loci and the TSP. // In J.J. Grefenstette, editor, Proceedings of the First International Conference on Genetic Algorithms, pp. 154-159. Lawrence Erlbaum Associates, 1985

88. Goldberg D.E. and P. Segrest. Finite markov chain analysis of genetic algorithms. // In J.J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms, pp. 1-8. Lawrence Erlbaum Associates, 1987.

89. Gorges-Schleuter M. ASPARGOS: an asynchronous parallel genetic optimization strategy. // In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pp. 422-427, Morgan Kaufmann, 1989

90. Grefenstette J., R.Gopal, R. Rosmaita and D. Gutch. Genetic algorithms for the travelling salesman problem.// In Proceedings of the Second International Conference on Genetic Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985

91. Grefenstette J. and Baker J.E. How genetic algorithms work: A critical look at implicit parallelism. // In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pp. 20 -27, San Mateo, CA, Morgan Kaufmann, 1989.

92. Harp S.A. and Samad T. Genetic synthesis of neural network architecture. // In L. Davis, editor, Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.

93. Hertz A., de Werra D. Informatique et horaires scolaires, Output, Vol.12, p.53-56

94. Holland J. Adaptation in Natural and Artificial Systems. MIT Press, 1975.

95. Horn J. The nature of niching: genetic algorithms and the evolution of optimal, cooperative populations. A Dissertation from the University of Illinois, 1997.

96. Hunt K.J. Polynomial LQC and hOT controller synthesis: a genetic algorithm solution. // In Proc. IEEE Conf. Decisions and Control, 1992.

97. Juliff K. Using a multi chromosome genetic algorithm to pack a truck. Technical Report RMIT CS TR 92-2, Royal Melbourne Institute of Technology, August, 1992.

98. Jo Jun H., Gero John S. Space layout planning using an evolutionary approach. Artificial Intelligence in Engineering, 12, 1998, p. 149-162

99. Keane A.J. A brief comparison of some evolutionary optimization methods, in Modern Heuristic Search Methods, ed. V.Rayward-Smith, I.Osmat, C.Reeves and G.D. Smith, J.Wiley, 1996

100. Krishnakumar K. and Goldberg D.E. Genetic algorithms in control system optimization. In AIAA Guidance, Navigation, Control Conf., pp. 1568-1577, 1990.

101. Langton, C.G. Artificial Life. (1992). In L. Nadel and D. Stein (eds.) Lectures in Complex Systems, SFI Studies in the Sciences of Complexity, Lect. vol. IV, Reading, MA.

102. Liepins G.E., Hillard M.R., Palmer M. and Morrow M. Greedy genetics. // In J.J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms, pp. 1-8. Lawrence Eribaum Associates, 1987.

103. Louis Sushil J., Li Gong. Genetic Algorithms with Memory for Traveling Salesman Problems, University of Nevada, 1997

104. Manikas T.W., Cain G.T. Genetic Algorithms vs. Simulated Annealing: A Comparison of Approaches for Solving the Circuit Partitioning Problem, Technical Report No. 96-101, University of Pittsburgh, Dept. of Electric Engineering, 1996.

105. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. Wiley-Interscience, Chichester, UK, 1996.

106. Mathias K. and Whitley D. Genetic operators, the fitness landscape and the traveling salesman problem.

107. Mitchell M., Forrest S., and Holland J. The Royal Road for Genetic Algorithms: Fitness Landscapes and GA performance // in Proceedings of the First European Con-ferenceon Artificial Life, MIT Press, Cambridge, 1992.

108. Muhlenbein H. and H.-M. Voigt Gene combination in genetic algorithm. // In I.H. Osman and J.P. Kelly, editors, In Proceedings of the Metaheuristics Inter. Conf., Norwell, 1995, Kluwer Academic Publishers.

109. Muhlenbein H. and Schlierkamp-Voosen D. Predictive models for the breeder genetic algorithm. Evolutionary Computation. 1(1), 1993.

110. Padberg M. and Rinaldi. Optimization of a 532-city symmetric travelling salesman164problemby branch and cut / Operations Research Letters, 6(1): 1-7, 1987.

111. Rintala T. Empirical comparison of stochastic algorithms // In Preceedings of the Second Nordic Workshop on Genetic Algorithms and their Applications, University ofVaasa, 1996.

112. Rutenbar R.A. Simulated annealing algorithms: An overview. IEEE Circuits and Devices Magazine, January 1989.

113. Starkweather T., S. McDaniel, K. Mathias, D.Whitley and C. Whitley. A Comparison of Genetic Sequencing Operators. // In Proc. Fourth Int. Conf. on Genetic Algorithms, Morgan Kauffman. 1991.

114. Syswerda G. Schedule optimization using genetic algorithms.// In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pp. 2-9, Morgan Kaufmann, 1989

115. Whitley D., Mathias K., Rana S. and Dzubera J. Building Better Test Functions.

116. Whitley D. et al. Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator // Proc. Third International Conf. on Genetic Algorithms. San Mateo, California, 1989.

117. Wolpert D.H.and Macready W.G. No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, vol. 1. no. 1, 1997

118. Zade L. Fuzzy Sets. Information and Control, 1973.