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

Оглавление.

Введение.

Глава 1. Постановки задач и методы их решения

• 1.1 Формулировки задач и некоторые приложения

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

1.3 Генетический алгоритм для задачи целочисленного линейного программирования.

1.4 Алгоритм перебора L-классов для задачи целочисленного линейного программирования

1.5 Гибридный алгоритм для задачи целочисленного линейного программирования

Глава 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 Оценки доли особей с заданной пригодностью

4.4 Примеры использования модели.

4.5 Вычислительный эксперимент.

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

В настоящее время подход, основанный на использовании эволюционного моделирования, представляет собой интенсивно развивающееся направление дискретной оптимизации. Этот подход охватывает такие вопросы, как поиск приближенных решений, вероятностный анализ сходимости алгоритмов, структура задач и сложность их решения, гибридные алгоритмы, экспериментальные исследования и др. (см., например, [3, 7, 20, 22, 43, 45, 50, 61, 66, 89, 95, 116, 123]).

Важное место в дискретной оптимизации занимает проблематика целочисленного программирования (ЦП), которая включает вопросы, связанные с теорией двойственности, устойчивостью решений, полиэдральным подходом, методами отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, выпуклым и невыпуклым программированием и т.д. [4, 5, 18, 23, 21, 28, 30, 38, 42, 44, 47, 48, 49, 51, 101].

В ряде известных методов решения задач ЦП используется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны методы отсечения [8, 31, 51, 52], декомпозиции (например, с отсечениями Бендерса [36, 69]), ветвей и границ [38, 51], алгоритмы перебора L-классов [33] и др. Как правило, в этих методах используется релаксация условий целочисленности, позволяющая применять алгоритмы непрерывной оптимизации. Для исследования свойств задач ЦП, построения и анализа алгоритмов, основанных на релаксации условий целочисленности, А.А.Колоколовым предложен метод регулярных разбиений [31, 32, 33, 34]. С использованием этого подхода введены и исследованы новые классы отсечений, построены оценки числа итераций для ряда известных алгоритмов решения задач ЦП, разработаны новые алгоритмы. В последнее время найдены новые возможности применения данного подхода в вопросах устойчивости задач и алгоритмов [12, 35]. Значительное число результатов получено на основе L-разбиения, в частности, на основе этого разбиения предложен метод перебора L-классов для решения задач ЦП. Особенно продуктивным оказалось применение перебора L- классов в сочетании с эвристическими приближенными алгоритмами [24, 36], и в частности, генетическим алгоритмом (ГА) [89].

Эволюционные алгоритмы, к числу которых относятся генетические алгоритмы [95, 103], эволюционные стратегии [115], алгоритмы оптимизации коллективом адаптирующихся автоматов [43] и др., основаны на принципе моделирования процесса биологической эволюции. Методы эволюционного моделирования успешно применяются при решении задач распознавания образов, предсказания, проектирования сложных систем, систем управления и т.д. (см., например, [6, 7, 20, 22, 50, 95]). При решении задач большой размерности в ЦП хорошо зарекомендовали себя ГА [3, 61, 66, 76, 82, 89, 95, 116]. Характерными особенностями ГА являются групповой поиск с помощью популяции "особей", соответствующих точкам пространства решений, работа с символьным представлением решения, использование случайных операторов. В настоящее время возможности применения генетических алгоритмов в дискретной оптимизации исследованы далеко не полностью. Особенно актуальны вопросы моделирования работы ГА, исследования его поведения на заданном классе задач, использования

ГА в гибридных алгоритмах для поиска точного решения задач ЦП.

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

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

Диссертация состоит из введения, четырех глав, заключения и приложения. В первой главе приводятся постановки задачи целочисленного линейного программирования, задачи о наименьшем покрытии множества и задачи о вершинном покрытии на графе. Рассматриваемые задачи возникают в экономике, информатике, планировании, технике и других областях, (см., например, [4, 5, 30, 46]).

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

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

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

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

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

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

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

Заключение

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

1. Александров Д.А. Алгоритм муравьиной колонии для задачи о минимальном покрытии //XI междунар. Байкальская школа-семинар "Методы оптимизации и их приложения": Труды, Т.З. -Иркутск, 1998. С.17-20.

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

3. Батищев Д.И. Генетические алгоритмы решения экстремальных задач // Учебное пособие. Воронеж: Воронеж, гос. техн. ун-т, 1995. - 69 с.

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

5. Береснев В.Л., Гимади Э.Х., Деменьтьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. - 385 с.

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

7. Букатова И.Л., Михасев Ю.И., Шаров A.M. Эвоинформатика: Теория и практика эволюционного моделирования М.: Наука, 1991.- 206 с.

8. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977. - 161 с.

9. Герман О.В., Ефремов О.В. Алгоритм решения обобщенной задачи о покрытии // Экон. и мат. методы. 1998. Т. 34. - N 4. -С.134-140.

10. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций 1999. - Серия 2, Т. 6, N 1. - С.12-32.

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

12. Девятерикова М.В., Колоколов А.А. Об устойчивости дробных накрытий задач целочисленного программирования / / Между-нар. конф. "Проблемы оптимизации и экономические приложения": Тез. докл. Омск, 1997. - С.59-61.

13. Еремеев А.В. Анализ эффективности генетического алгоритма для некоторых задач дискретной оптимизации //11 Всерос. конф. "Математическое программирование и приложения": Тез. докл.-Информ. бюлл. АМП N 8. Екатеринбург, 1999. - С.98.

14. Еремеев А.В. Генетические алгоритмы и некоторые задачи дискретной оптимизации // Междунар. конф. "Проблемы оптимизации и экономические приложения": Тез. докл. Омск, 1997. -С.68.

15. Еремеев А.В. Генетический алгоритм для задачи о наименьшем покрытии множества // Междунар. конф. по исследованию операций: Тез. докл. Новосибирск, 1998. - С.107.

16. Еремеев А.В. Исследование приближенного алгоритма для всюду плотной задачи вершинного покрытия //XI междунар. Байкальская школа-семинар "Методы оптимизации и их приложения": Труды, Т.1. Иркутск, 1998. - С.131-134.

17. Еремеев А.В. Применение генетических алгоритмов для решения некоторых задач дискретной оптимизации //XXXIV Международная научная студенческая конференция "Студент и научно-технический прогресс": Тез. докл. Новосибирск, 1996. - С.23-24.

18. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во ИММ, 1998. - 247 с.

19. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория алгоритмов). -М.: Наука, 1981. 344 с.

20. Жихалкина Н.Ф., Файзулин Р.Т. Гравитационная и генетическая аналогии в задаче безусловной оптимизации //Междунар. конф. "Проблемы оптимизации и экономические приложения": Тез. докл. Омск, 1997. - С.71.

21. Заблоцкая О.А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации// Дискретная оптимизация и численные методы решения прикладных задач. Новосибирск: ВЦ СО АН СССР, 1986. - С.21-27.

22. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. -Новосибирск: Изд-во Ин-та математики, 1999. 270 с.

23. Заикина Г.М., Колоколов А.А., Леванова Т.В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. Омск, 1992. - С.25-41.

24. Заозерская Л.А. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества // XI междунар. Байкальская школа-семинар "Методы оптимизации и их приложения": Труды, Т.1. Иркутск, 1998. - С.139-142.

25. Заозерская JI.А. Исследование и решение некоторых классов задач целочисленного программирования на основе регулярных разбиений: Автореф. дис. канд. физ.-мат. наук. Омск, 1998. -16 с.

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

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

28. Ильев В.П., Леванова Т.В. Анализ градиентного алгоритма минимизации супермодулярной функции на матроиде// XI между-нар. Байкальская школа-семинар "Методы оптимизации и их приложения": Труды, Т.1. Иркутск, 1998. - С.143-146.

29. Кемени Дж., Снелл Дж. Конечные цепи Маркова. Наука, 1970. -272 с.

30. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Минск: БГУ, 1977. - 192 с.

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

32. Колоколов А.А. О лексикографической структуре некоторых выпуклых многогранных множеств// Тез. докл. V Всесоюз. конф. по проблемам теоретической кибернетики. Новосибирск, - 1980. - С.77-79.

33. Колоколов А.А. Регулярные разбиения в целочисленном программировании / / Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. - С.67-93.

34. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. Новосибирск. - 1994. - Т.1, N 2. - С.18-39.

35. Колоколов А.А., Девятерикова М.В. Регулярные разбиения и устойчивость задач целочисленного программирования //11 Все-рос. конф. "Математическое программирование и приложения": Тез. докл.- Информ. бюлл. АМП N 8. Екатеринбург, 1999. - С.161 - 162.

36. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. Омск: ОмГУ, 1996. - N 1. - С.21-23.

37. Корбут А.А., Сигал И.Х., Финкелынтейн Ю.Ю. Гибридные методы в дискретной оптимизации // Изв. АН СССР. Техн. кибернетика. 1988. - N 1. - С.65-77.

38. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

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

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

41. Кузюрин Н.Н. О связи оптимумов в задачах линейного и целочисленного линейного программирования / / Дискретная математика. 1991. - Т.З, Вып.1. - С.98-104.

42. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990. - 488 с.

43. Мухин В.И., Неймарк Ю.И., Ронин Е.И. Автоматная оптимизация с эволюционной адаптацией // Проблемы случайного поиска. Рига: Зинатне, 1973. - С.83-98.

44. Попков В.К. Математические модели живучести сетей связи. -Новосибирск: ВЦ СО АН СССР, 1990. 235 с.

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

46. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, думка, 1988. - 472 с.

47. Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. - Вып.ЗО. - С.61-71.

48. Стрекаловский А.С., Цевээндоржийн И., Кузнецова А.А. Один способ решения задач "{0,1} программирования" //Междунар. конф. "Проблемы оптимизации и экономические приложения": Тез. докл. - Омск, 1997. - С.150.

49. Схрейвер А. Теория линейного и целочисленного программирования. Т.2. М.: Мир. 1991. - 342 с.

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

51. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир. - 1974. - 520 с.

52. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физмат лит. - 1995. - 190 с.

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

54. Al-Sultan K., Hussain M., J .Nizami M. A Genetic Algorithm for the Set Covering Problem // J. Oper. Res. Soc. 1996. - Vol. 47. - P.702-709.

55. Arora S., Karger D., Karpinski M. Polynomial Time Approximation Schemes for Dense Instances of iVP-Hard Problems // Proc. of 27th ACM Symposium on Theory of Computing. 1995. P.284-293.

56. Arora S., Lund C. Hardness of approximations // Approximation Algorithms for NP-Hard Problems/ Ed. by S.D.Hochbaum. PWS Publishing Company, 1995. - P.399-446.

57. Back T. The Interaction of Mutation Rate, Selection, and Self-Adaptation Within a Genetic Algorithm // Proc. of Parallel Problem Solving from Nature (PPSN II) / Ed. by R. Manner, B. Manderick.- North Holland, 1993. -P.85-94.

58. Balas E., Carrera M.C. A Dynamic Subgradient-Based Branch and Bound Procedure for Set Covering // Oper. Res. 1996. - Vol. 44, N 6. - P.875-890.

59. Balash E., Ho A. Set Covering Algorithms Using Cutting Planes, Heuristics and Subgradient Optimization: A Computational Study // Math. Programming. 1980. - Vol. 12. - P.37-60.

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

61. Battiti R., Protasi M. Reactive Local Search for the Maximum Clique Problem. Report No. TR-95-052. Berkeley: International Computer Science Institute, 1995.

62. Bar-Yehuda R., Even S. A Linear Time Approximation Algorithm for the Weighted Vertex Cover Problem // Journal of Algorithms. -1981. Vol. 2. - P.198-203.

63. Bar-Yehuda R., Even S. A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem // Annals of Discrete Mathematics. 1985. - Vol. 25. - P.27-45.

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

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

66. Beasley J.E., Jornsten K. Enhancing an Algorithm for Set Covering Problems // European J. Oper. Res. 1992. - Vol. 58. - P.293-300.

67. Bellare M., Goldreich O., Sudan M. Free Bits and Non-Approximability Towards Tight Results. // Proc. of 36th Annual IEEE Symposium on Foundations of Computer Sciense, 1995. -P.422-431.

68. Benders J.F. Partitioning Procedures for Solving of Mixed-Variables Programming Problems// Numer. Math. -1962. Vol. 4, N 3. - P.238-252.

69. Caprara A., Fischetti M., Toth P. Algorithms for the Set Covering Problem. Report No. OR-98-3. Bologna: DEIS, University of Bologna, 1998.

70. Caprara A., Fischetti M., Toth P., Vigo D. Modeling and Solving the Crew Rostering Problem // Oper. Res. 1998. - Vol. 46 - P.820-830.

71. Chvatal V. A Greedy Heuristic for the Set Covering Problem // Mathematics of Oper. Res. 1979. - Vol. 4, N 3. - P.233-235.

72. Clementi A.E.F., Trevisan, L. Improved Non-Approximability Results for Vertex Cover with Density Constraints // Proc. of 2nd Computing and Combinatorics Conference (COCOON'96). Berlin: Springer Verlag, 1996. - P.333-342.

73. Davis L. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991. - 371 p.

74. Day R.H. On Optimal Extracting from a Multiple File Data Storage System: An Application of Integer Programming // Oper. Res. -1965. Vol. 13. N 3. - P.482-494.

75. Dongarra J.J. Performance of Various Computers Using Standard Linear Equations Software. Report No. CS-89-85. Tennessee: University of Tennessee, 1998.

76. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process. Report No. TR-91-016. Milan: Politecnico di Milano, 1991.

77. Erdos P. On a Combinatorial Problem // Nordisk Mat. Tidskrift. -1963. Vol. 11. - P.5-10.

78. Eremeev A.V. A Genetic Algorithm for Set Covering Problem// International Conference on Operations Research: Abstr. Zurich: ETH, 1998. - P.42.

79. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem // Proc. of Operations Research (OR'98). Springer Verlag, 1999. - P.175-181.

80. Eremeev A.V., Kolokolov A.A. A Hybrid of Genetic and L-class Enumeration Algorithms for Linear Integer Programming Problem // International Conference " Optimal Discrete Structures and Algorithms": Abstr. Rostock, 1997. - P.21.

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

82. Eremeev A.V. On Some Approximation Algorithms for Dense Vertex Cover Problem // Proc. of Simposium on Operations Research (SOR'99). Springer Verlag, 2000. - P.58-62.

83. Eremeev A.V. Some Approximate Algorithms for the Vertex Cover Problem // Simposium on Operations Research (SOR'99): Abstr. -Magdeburg, 1999. -P.46.

84. Eremeev A.V., Kolokolov A.A. An Application of Genetic Algorithm and L-class Enumeration to the Integer Programming Problem // Proc. of the 1st Online Workshop on Soft Computing. Nagoya, 1996. - P.104-106.

85. Eremeev A.V., Kolokolov A.A. An Application of Genetic Algorithm and L-class Enumeration to the Integer Programming Problem // Proc. of the 4th European Congress on Intelligent Techniques and Soft Computing. Aachen, 1996. - P.476-477.

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

87. Feige U., Goldwasser S., Lovasz L., Safra S., Szegedy M. Approximating Clique is Almost NP-complete // Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. 1991. P.2-12.

88. Fisher M.L., Kedia P. Optimal Solution of Set Covering Problem Using Dual Heuristics // Manag. Sci. 1990. - Vol. 36, N 8. - P.674-688.

89. Fogel L., Owens A.J., Walsh M.J. Intelligent Decisionmaking Though a Simulation of Evolution // IEEE Trans. Prof. Techn. Group on Human Factors in Electronics. 1964. - Vol. 6, N 1. - P.13-23.

90. Fulkerson D.R., Nemhauser G.L., Trotter L.E. Two Computationally Difficult Set Covering Problems that Arise in Computing the 1-Width of Incidence Matrices of Steiner Triple Systems // Math. Programming Study. 1974. - Vol. 2. - P.72-81.

91. Garey M.R., Johnson D.S., Stockmeyer L. Some Simplified NP-Complete Graph Problems// Theoret. Comput. Sci. 1976. - Vol. 1. - P.237-267.

92. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989. - 412 p.

93. Goldberg M.K., Russell H. Toward Computing m(4) // Ars Combinatoria 1995. - Vol. 3, N 9. - P.139-148.

94. Grossman Т., Wool A. Computational Experience with Approximation Algorithms for the Set Covering Problem // European J. Oper. Res. 1997. - Vol. 101, N 1. - P.81-92.

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

96. Hasselberg J., Pardalos P.M., Vairaktarakis G. Test Case Generators and Computational Results for the Maximum Clique Problem// Journal of Global Optimization. 1993. N 3. - P.463-482.

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

98. Hochbaum D.S. Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems // Approximation Algorithms for ЖР-Hard Problems. / Ed. by S.D.Hochbaum. PWS Publishing Company, 1995. - P.94-143.

99. Holland J.H. Outline For a Logical Theory of Adaptive Systems // Journal of the Association for Computing Machinery. 1962. - Vol. 3. - P.297-314.

100. Holland J.H. Genetic Algorithms and the Optimal Allocations of Trials // SIAM Journal of Computing. 1973. - Vol. 2, N 2. - P.88-105.

101. Karpinski M., Zelikovsky A. Approximating Dense Cases of Covering Problems. Report No. TR-97-001. Trier: Electronic Colloquium on Computational Complexity, 1997.

102. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On Hybrid L-class Enumeration and Genetic Algorithm for Set Covering Problem //15-th Conference of Interational Federation of Operational Research Societies (IFORS'99): Abstr. Pekin, 1999. -P.117.

103. Korostensky С., Gonnet G. Gap Heuristics and Tree Construction Using Gaps. Report No. 321. Zurich: ETH, Institute of Scientific Computing, 1999.

104. Koza J.R. Genetic Programming II : Automatic Discovery of Reusable Programs (Complex Adaptive Systems). MIT Press, 1994.- 746 p.

105. Lagarias J.C., Shor P.W. Keller's Cube-Tiling Conjecture is False in High Dimensions // Bulletin of the AMS. 1992. - Vol. 27, N 2. -P.279-283.

106. Mannino C., Sassano A. Solving Hard Set Covering Problems // Oper. Res. Letters. 1995. - Vol. 18. - P.l-5.

107. Miihlenbein H. How Genetic Algorithms Really Work: I. Mutation and Hillclimbing // Proceedings of Parallel Problem Solving from Nature (PPSN II) / Ed. by R. Manner and B. Manderick. North Holland, 1993. - P. 15-26.

108. Nix A. and Vose M. D. Modeling Genetic Algorithms with Markov Chains // Annals of Mathematics and Artificial Intelligence. 1992.- Vol. 5, P. 79-88.

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

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

111. Revelle C., Marks D., Liebman J.C. An Analysis of Private and Public Sector Facilities Location Models // Management Sci. 1970. - Vol. 16, N 12. - P.692-707.

112. Ross P. What are Genetic Algorithms Good at? // INFORMS Journal on Computing. 1997. - Vol. 9, N 3. - P.260-262.

113. Rudolph G. Convergence Analysis of Canonical Genetic Algorithms // IEEE Transactions on Neural Networks. -1994. Vol. 5, N 1. - P. 96-101.

114. Salveson M.E. The Assembly Line Balancing Problem // J. Industrial Engineering. 1955. - Vol. 6. - P.18-25.

115. Soriano P., Gendreau M. Solving the Maximum Clique Problem Using a Tabu Search Approach // Annals of Operations Reserach. -1993. Vol. 41. - P.385-403.

116. Trauth C.A., Woolsey R.E.D., Integer Programming: a Study in Computational Efficiency // Manag. Science. 1969. - Vol. 15, N 9. - P.481-493.

117. Vose M. D. Modeling Simple Genetic Algorithms // Evolutionary Computation. -1995. Vol. 3, N 4. - P.453-472.

118. Vose M. D. and Wright A.H. The Walsh Transform and the Theory of the Simple Genetic Algorithm // Genetic Algorithms for Pattern Recognition / Ed. by S.K. Pal, P.P. Wang, 1995. -P. 25-44.

119. Walker W. Application of the Set Covering Problem to the Assignment of Ladder Trucks to Fire Houses // Oper. Res. 1974. -Vol. 22. - P.275-277.