Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Борисовский, Павел Александрович

• Борисовский, Павел Александрович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Борисовский, Павел Александрович

Введение.

Глава 1. Эволюционные методы вычислений и некоторые

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

Диссертация посвящена разработке, моделированию и сравнению различных эволюционных алгоритмов для решения задач дискретной оптимизации. Эволюционные алгоритмы (ЭА) - сравнительно новые эвристические методы поиска, которые успешно применяются при решении оптимизационных задач различных типов. В основе ЭА лежат элементы теории эволюции Ч. Дарвина [16], такие как наследственность, изменчивость и отбор. Многие термины, используемые при описании ЭА (особь, мутация, кроссинговер и др.), заимствованы из биологии, и обозначают элементы алгоритма, сходные с аналогичными объектами и процессами в природе.

Область практического применения ЭА включает в себя задачи планирования и размещения производства [14,82], управления потоками продукции [62,96], составления расписаний [98], раскроя и упаковки [29], проектирования автоматических производственных линий [59] и многие другие [12,17,65]. Известно большое количество различных реализаций ЭА для решения классических задач дискретной оптимизации, таких как задача целочисленного линейного программирования [18,64], задача коммивояжера [68], задача о выполнимости логической формулы [70], задачи о покрытии и упаковке множеств [43,45,49] и т.д.

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

I ' , I * * ко реализуется программно, хотя, несомненно, связан с большими вычислительными затратами. Появление в последнее время доступных компьютеров высокой скорости вычислений и с большим объемом памяти позволило преодолеть эту трудность, благодаря чему популярность ЭА значительно возросла.

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

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

В области эволюционных алгоритмов можно выделить два направления: теоретическое и экспериментальное. Теоретические исследования ЭА направлены в основном на построение математических моделей различных алгоритмов, исходя из которых выдаются рекомендации по выбору тех или иных вычислительных схем и настройке внутренних параметров, а также вычисляются оценки точности и скорости работы алгоритмов [52,54,63,74,77,87,91,92]. В рамках экспериментального направления разрабатываются алгоритмы, предназначенные для решения прикладных задач. Особое место здесь занимают способы гибридизации ЭА, методов локального поиска и алгоритмов, разработанных для решения конкретного типа задач с учетом их специфики [29,34,45,49,59,64,98]. Вопросы о сравнении алгоритмов и настройке параметров решаются путем вычислительных экспериментов. Важную роль здесь играет создание общедоступных библиотек тестовых задач, размещенных в сети Интернет, которые позволяют исследователю сравнивать свои результаты с работами других авторов. В качестве примеров можно привести проект DIMACS Challenge II [75] (http://dimacs.rutgers.edu), библиотеку OR Library [48] (http://mscmga.ms.ic.ac.uk/infoMtm1), библиотеку тестовых задач Института математики им. C.JI. Соболева [13] (http://math.nsc.ru/AP/benchmarks/).

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

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

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

Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. В первой главе приведены схемы различных алгоритмов эволюционного типа, таких как имитация отжига, генетический алгоритм, алгоритмы (//, А)-ЕА и (/z + А)-ЕА, показана их связь с алгоритмами локального поиска. Дан краткий обзор некоторых классических результатов теории эволюционных вычислений, имеющих отношение к вопросам, обсуждаемым в данной работе: теорема об эквивалентности алгоритмов поиска (известная в англоязычной литературе как теорема "no free lunch"), моделирование генетического алгоритма и (1+1)-ЕА с помощью цепей Маркова, исследование метрических свойств пространства поиска. В качестве примеров практического применения ЭА приводятся генетические алгоритмы для решения классической задачи о вершинном покрытии графа и одной прикладной задачи о поставках продукции. Проведены вычислительные эксперименты, которые показали хорошую производительность алго

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Борисовский, Павел Александрович

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

1. Построены модели, описывающие распределения значений целевой функции решений, найденных на заданной итерации алгоритмов (1,А)-ЕА и (1+1)-ЕА. Указаны условия сходимости к оптимальному решению. Проведены вычислительные эксперименты для задачи о независимом множестве графа, подтвердившие адекватность построенных моделей в начальной стадии процесса поиска.

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

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Борисовский, Павел Александрович, 2005 год

1. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982. - 368 с.

2. Бахтин А.Б., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. - 167 с.

3. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. - 316 с.

4. Борисовский П.А. Сравнение и оценка трудоемкости некоторых эволюционных алгоритмов: Препринт. Омск: "Полиграфический центр КАН", 2005. - 12с.

5. Борисовский П.А. Генетические алгоритмы для задачи о поставках продукции // Материалы V Междунар. науч.-техн. конф. "Динамика систем, механизмов и машин". Омск: Изд-во ОмГТУ, 2004, Кн. 2. - С.255-258

6. Борисовский П.А. Разработка генетического алгоритма для задачи о вершинном покрытии // Тезисы докладов XXIII научной студенческой конференции.-Омск: ОмГУ, 1999. С.7-8.

7. Борисовский П.А., Еремеев А.В. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. N2, 2004. С.3-9.

8. Борисовский П.А., Еремеев А.В. Об одном алгоритме случайного поиска // Материалы конф. "Дискретный анализ и исследование операций". Новосибирск: Изд-во Ин-та математики, 2002. - С.225.

9. Боровков А.А. Теория вероятностей. М.: Наука, - 1986. - 431 с.

10. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности // Харьков: ОСНОВА, 1997. -112 с.

11. Гончаров Е.Н., Иваненко Д.А., Кочетов Ю.А., Кочетова Н.А. Электронная библиотека "Дискретные задачи размещения" // Труды Байкальской международной конференции, Иркутск, 2001, Т. 1. С. 132-137.

12. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций, Серия 2, 9(2), 2002. -С.13-30.

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

14. Дарвин Ч. Происхождение видов. М., JL: ОГИЗ: Сельхозгиз, 1937. - 608 с.

15. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: Авто-реф. дис. канд. физ.-мат. наук. Омск, 2000. - 16 с.

16. Еремеев А.В., Заозерская J1.A., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.

17. Заозерская J1.A. Алгоритм ветвей и границ для решения одной задачи о поставках продукции // Материалы конференции "Проблемы оптимизации и экономические приложения". Омск, Изд-во Наследие. Диалог Сибирь, 2003. - С.88.

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

19. Колоколов А.А. Методы дискретной оптимизации // Учебное пособие. Омск: ОмГУ, 1984. - 75 с.

20. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. -Новосибирск. 1994. -T.I, N.2. - С. 18-39. - Омск: ОмГУ, 1992. -С.67-93.

21. Колоколов А.А. Ярош А.В. Некоторые обобщения задачи максимальной выполнимости и их приложения // Информационный бюллетень Ассоциации математического программирования. 10. Екатеринбург: УрО РАН, 2003. - С.151-152.

22. Кочетов Ю.А., Младенович Н., Хансен П. Локальный поиск в комбинаторной оптимизации: достижения и перспективы // Материалы конференции "Проблемы оптимизации и экономические приложения". Омск, Изд-во Наследие. Диалог Сибирь, 2003. - С.43-47.

23. Кочетов Ю.А., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Сер. 2, 2003, Т. 10, N 1, С. 11-43.

24. Крамер Г. Математические методы статистики. М.: Мир, 1975. - 648 с.

25. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика, 3, 2004.- С.80-88.

26. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Материалы конф. "Дискретный анализ и исследование операций". Новосибирск: Изд-во Ин-та математики, 2002. - С.80-87.

27. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск, Наука (Сибирское отделение), 1990. - 515 с.

28. Пападимитриу Х.,Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 516 с.

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

30. Ширяев А.Н. Вероятность. М.: Наука, 1980. - 576 с.

31. Aggarwal C.C., Orlin J.B., Tai R.P. An Optimized Crossover for Maximum Independent Set // Operations Research. 1997. -Vol.45. - P.225-234.

32. Aldous D., Vazirani U.U."Go with the Winners" Algorithms // Proc. IEEE Symposium on Foundations of Computer Science. 1994. P.492-501.

33. Altenberg, L.: The evolution of evolvability in genetic programming // In К. E. Kinnear (ed.) Advances in Genetic Programming. MIT Press, Cambridge, MA. 1994. P. 47-74

34. Altenberg L. Fitness distance correlation analysis: an instructive counterexample // In T. Back (ed.) Proc. of the Seventh International Conference on Genetic Algorithms (ICGA97), San Francisco: Morgan Kaufmann. 1997. P. 57-64.

35. Altenberg, L.: The schema theorem and Price's theorem // In D. Whitley and M. Vose (eds.) Foundations of Genetic Algorithms 3, San Francisco: Morgan Kaufmann. 1995. P. 23-49.

36. Angel E., Zissimopolous V., On the classification of NP-complete problems in term of their correlation coefficient // Discrete Applied Mathematics, 2000. - Vol. 99. - P.261-277.

37. Arora S., Lund C. Hardness of approximations //In S.D.Hochbaum (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1995. - P.399-446.

38. Ausiello G., Protasi M. Local search, reducibility and approximabi-lity of NP-optimization problems // Information Processing Letters, Vol. 54. 1995. P.73-79.

39. Back Т. Evolution Strategies: Ail Alternative Evolutionary Algorithm // In J.M. Alliot et al (eds.) Artificial Evolution. -Springer Verlag, LNCS. 1995. - Vol. 1063, - P.3-20.

40. Back Т., Khuri S. An Evolutionary Heuristic for the Minimum Vertex Cover Problem //In J. Hopf (ed.) Genetic Algorithms within the Framework of Evolutionary Computation. Max Planck Institut fur Informatik, Saarbrucken, 1994. - P. 86-90.

41. Back Т., Schwefel H.-P. An overview of evolutionary algorithms for parameter optimization // Evolutionary Computation, 1993. - Vol. 1, N 1, - P. 1-23.

42. Balas E., Niehaus W. Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems // Journ. of Heuristics. 1998. - Vol. 4, N 4, -P.107-122.

43. Balas E., Niehaus W. A Max-Flow Based Procedure for Finding Heavy Cliques in Vertex-Weighted Graphs // MSRR No. 612. -GSIA, Carnegie-Melon University. 1996. P.29-53.

44. Batitti R., Protasi M. Reactive local search for the maximum clique problem // Algorithmica, 2001. - Vol. 29, N. 4. - P. 610-637.

45. Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail // J. Oper. Res. Soc. 1990. - Vol. 41, N 11. - P.1069-1072.

46. Beasley J.E., Chu P.C. A Genetic Algorithm for the Set Covering Problem // European J. Oper. Res. 1996. - Vol. 94, N 2. - P.394-404.

47. Boese K.D., Kahng А.В., Muddu S. A new adaptive multy-start technique for combinatorial dlobal optimization // Oper. Res. Lett. 1994. - Vol. 16, N.2. - P.101-114.

48. Bomze I. M., Budinich M., Pardalos P. M., Pelillo M. The maximum clique problem //In D.-Z. Du and P. M. Pardalos (eds) Handbook of Combinatorial Optimization. Dordrecht: Kluwer. 1999. - Suppl. Vol. A. - P. 1-74.

49. Borisovsky P.A., Eremeev A.V. On Performance Estimates for Two Evolutionary Algorithms // In E.J.W.Boers et al. (Eds.) Applications of evolutionary computing: Proceedings of EvoWorkshops 2001. Springer Verlag, LNCS. - 2001. - Vol. 2037, - P.161-171.

50. Borisovsky P.A., Eremeev A.V. Comparing Evolutionary Algorithms to the (1+1)-EA by Means of Stochastic Ordering // Wide materials of Dagstuhl Seminar "Theory of Evolutionary Algorithms". February 2004. (http://www.dagstuhl.de/04081/ Talks/).

51. Borisovsky P.A., Eremeev A.V. A Study on Performance of the (l+l)-Evolutionary Algorithm // In K. De Jong, R. Poli, and J. Rowe (eds.) Foundations of Genetic Algorithms 7. San Francisco: Morgan Kaufmann. 2003. P.271-287.

52. Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. On Solving Concave Cost Supply management problem with single manufacturing unit. // Proc. of Production System Design, Supply Chain Management and Logistics Conf. Poland, 2002. P. 147-154.

53. Chauhan S.S., Proth J.-M. The Concave Cost Supply Problem // European J. Oper. Res. 2003. V. 148. N. 2. P. 374-383.

54. Daley D.J. Stochastically monotone Markov chains // Z. Wahrscheinlickeitstheorie und Verw. Gebiete, 10,1968. P.307-317.

55. Dolgui A., Eremeev A., Kolokolov A., Sigaev V. A genetic algorithm for the allocation of buffer storage capacities in a production line with unreliable machines // Journal of Mathematical Modelling and Algorithms, 2002. Vol. 1. - P. 89-104.

56. Dorigo M., Di Caro G. The ant colony optimization meta-heuristic // In D. Corne at al.(eds.) New ideas in optimization McGraw Hill, UK, 1999. P. 11-32.

57. Droste S., Jansen Т., Tinnefeld K., Wegener I. A new framework for the valuation of algorithms for black-box optimisation //In K. De Jong, R. Poli, and J. Rowe (eds.) Foundations of Genetic Algorithms 7. San Francisco: Morgan Kaufmann. 2003. P. 197214.

58. Eckert C., Gottlieb J. Direct Representation and Variation Operators for the Fixed Charge Transportation Problem // Proc. of Parallel Problem Solving from Nature (PPSN VII), Springer, LNCS 2439, 2002. P. 54-63.

59. Eremeev A.V. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of The 4th Artificial Evolution Conference. Dunkerque, 1999. - P.215-226.

60. Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the First International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. - P.297-303.

61. Fuchs MM. An evolutionary approach to support web page design // Proc. 2000 Congress on Evolutionary Computation (CEC-2000). IEEE Press, Piscataway, NJ, 2000. - P. 1312-1319.

62. Glover F., Laguna M. Tabu Search //In C.Reeves (ed.) Modern heuristic techniques for combinatorial problems. Blackwell, Oxford, UK, 1993. - P. 70-141.

63. Goldberg D.E., Deb K. (1991). A comparative study of selection schemes used in genetic algorithms //In G.Rawlins (ed.) Foundations of Genetic Algorithms. San Mateo: Morgan Kaufmann. 1991. P. 197-214. P. 69-93.

64. Goldberg D.E., Linge R. Alleles, Loci and the Travelling Salesman Problem //In J.J. Grefenstette (ed.) Proc. of an International Conference on Genetic Algorithms and Their Applications. -Hillsdale, NJ, 1985. P.154-159.

65. Halldorsson, M.M., Radhakrishnan, J. Greed is good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs // Algorithmica. 1997. - Vol. 18. - P.143-163.

66. Hao J.-K., Lardeux F., Saubion F. Evolutionary Computing for the Satisfiability Problem //In S.Cagnoni et al. (eds.) Applications of evolutionary computing: Proc. of EvoWorkshops 2003. Springer Verlag. LNCS, V. 2611. 2003. P.258-267.

67. Hastad, J. Some Optimal Inapproximability Results. Report No. TR-97-037. Trier: Electronic Colloquium on Computational Complexity, 1997.

68. Hochbaum D.S. Efficient bounds for the stable set, vertex cover and set packing problems // Discrete Applied Mathematics, 1983. -Vol. 6. - R243-254.

69. Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems // In D.S. Hochbaum (ed.) Approximation algorithms for NP-hard problems. PWS Publishing Company, 1995. P.94-143.

70. Holland J. Adaptation in natural and artificial systems. University of Michigan Press, 1975.

71. Jones Т., Forrest S. Fitness distance correlation as a measure of problem difficulty for genetic algorithms //In L.J. Eshelman (ed.) Proc. of the 6th International Conference on Genetic Algorithms. San Mateo: Morgan Kaufmann. 1995. P. 184-192.

72. Juliany J., Vose M.D. The Genetic Algorithm Fractal // Evolutionary Computation 1994. - Vol 2, N 2, - P. 165-180.

73. Kamae Т., Krengel U., O'Brien G.L. Stochastic inequalities on partially ordered spaces, The Annals of Probability 1977. - Vol 5, N 6, - P. 899-912.

74. Kirkpatrick S., Gellatt C.D., Vecchi M.P. Optimization by simulated annealing // Science 1983. - Vol 220, N 4598, - P.671-780.

75. Ко К. Some observations on the probabilistic algorithms and NP-hard problems // Information Processing Letters, 1982. N 14, -P.39-43.

76. Koza J.R. Genetic programming: On the programming of computers by means of natural selection. MIT Press. 1992.

77. Kratica J., Tosic D., Filipovic V., Ljubic I. Solving the Simple Plant Location Problems by Genetic Algorithm // RAIRO Operations Research, 35, 2001. P.127-142.

78. Kuznetsova A., Strekalovsky A.S. On solving the maximum clique problem // J. Global Optim. 2001. - Vol. 21. N. 3. - P. 265-288.

79. Lindvall T. Lectures on the coupling method. Whiley, New York. 1992.

80. Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of state calculation by fast computing machines // Journal of Chemical Physics 1953. - Vol. 21. - P.1078-1092.

81. Motwani R., Raghavan P. Randomized Algorithms. Cambridge University Press, 1995.

82. Miihlenbein H. How genetic algorithms really work I: Mutation and hillclimbing // Proc. of Parallel Problem Solving from Nature (PPSN II). North Holland, 1992. P.54-63.

83. G.L. Nemhauser, Trotter, J.L.E. Vertex packing: structural properties and algorithms// Math. Progr. 1975. - Vol. 8. - P.232-248.

84. Rechenberg I., Evolutionsstrategie: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann-Holzboog Verlag, 1973.

85. Reeves C.R. Genetic Algorithms for the Operations Researcher// INFORMS Journal on Computing. 1997. - Vol. 9, N 3. - P.231-250.

86. Reeves C.R., Rowe J.E. Genetic Algorithms Principles and Perspectives: A Guide to GA Theory // Kluwer Academic Publishers, 2003.

87. Richardson J. Т., Palmer M. R., Liepins G., Hilliard M. Some guidelines for genetic algorithms with penalty functions.// In J.D. Schafer (Ed.) Proc. of the 3rd International Conf. on Genetic Algorithms. Morgan Kaufmann. 1989. - P. 191-197.

88. Rudolph G. Finite Markov Chain Results in Evolutionary Computation: A Tour d'Horizont // Fundamenta Informaticae 35 (1-4) 1998. P.67-89.

89. Scharnow J., Tinnefeld K., Wegener I. Fitness landscapes based on sorting and shortest paths problems // Proc. of Parallel Problem Solving from Nature (PPSN VII), Springer, LNCS 2439, 2002. -P.54-63.

90. Syswerda G. A study of reproduction in generational and steady state genetic algorithm // In G. Rawlings (ed.) Foundations of Genetic Algorithms 7. San Mateo: Morgan Kaufmann. 1991. 94101.

91. Sun M., Aronson J.E., McKeown P.G., Drinka D. A Tabu Search Heuristic Procedure for the Fixed Charge Transporation Problem // European J. Oper. Res. 1998. V. 106. P. 441-456.

92. Wolpert D.H., Macready W.G. No free lunch theorem for optimization // IEEE Transactions on Evolutionry Computation V. 1. P. 67-82.

93. Yamada Т., Nakano R. Job-shop scheduling //In A.M.S.Zalzala and P.J.Fleming (eds.) Genetic Algorithms in Engeneering Systems. Peter Peregrinus, London. 1997. - P. 134-160.