Помощь в учёбе, очень быстро...
Работаем вместе до победы

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

Диссертация: Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава 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. И.И. Теория линейной оптимизации. Екатеринбург: Изд-во ИММ, 1998. — 247 с.
  18. В.А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация (комбинаторная теория алгоритмов). -М.: Наука, 1981. 344 с.
  19. Н.Ф., Файзулин Р. Т. Гравитационная и генетическая аналогии в задаче безусловной оптимизации //Междунар. конф. «Проблемы оптимизации и экономические приложения»: Тез. докл. Омск, 1997. — С.71.
  20. О.А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации// Дискретная оптимизация и численные методы решения прикладных задач. Новосибирск: ВЦ СО АН СССР, 1986. — С.21−27.
  21. Н.Г. Прикладные методы анализа данных и знаний. -Новосибирск: Изд-во Ин-та математики, 1999. 270 с.
  22. Г. М., Колоколов А. А., Леванова Т. В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. Омск, 1992. — С.25−41.
  23. Л.А. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества // XI междунар. Байкальская школа-семинар «Методы оптимизации и их приложения»: Труды, Т.1. Иркутск, 1998. — С.139−142.
  24. JI.А. Исследование и решение некоторых классов задач целочисленного программирования на основе регулярных разбиений: Автореф. дис. канд. физ.-мат. наук. Омск, 1998. -16 с.
  25. А.А. Основы теории графов. М.: Наука, — 1987. — 384 с.
  26. А.Г. Системы эвристической самоорганизации в технической кибернетике. Киев: Техника, — 1971. — 372 с.
  27. В.П., Леванова Т. В. Анализ градиентного алгоритма минимизации супермодулярной функции на матроиде// XI между-нар. Байкальская школа-семинар «Методы оптимизации и их приложения»: Труды, Т.1. Иркутск, 1998. — С.143−146.
  28. Дж., Снелл Дж. Конечные цепи Маркова. Наука, 1970. -272 с.
  29. М.М. Дискретная оптимизация (целочисленное программирование). Минск: БГУ, 1977. — 192 с.
  30. А.А. Методы дискретной оптимизации // Учебное пособие. Омск: ОмГУ, 1984. — 75 с.
  31. А.А. О лексикографической структуре некоторых выпуклых многогранных множеств// Тез. докл. V Всесоюз. конф. по проблемам теоретической кибернетики. Новосибирск, — 1980. — С.77−79.
  32. А.А. Регулярные разбиения в целочисленном программировании / / Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. — С.67−93.
  33. А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. Новосибирск. — 1994. — Т.1, N 2. — С.18−39.
  34. А.А., Девятерикова М. В. Регулярные разбиения и устойчивость задач целочисленного программирования //11 Все-рос. конф. «Математическое программирование и приложения»: Тез. докл.- Информ. бюлл. АМП N 8. Екатеринбург, 1999. — С.161 — 162.
  35. А.А., Леванова Т. В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. Омск: ОмГУ, 1996. — N 1. — С.21−23.
  36. А.А., Сигал И. Х., Финкелынтейн Ю. Ю. Гибридные методы в дискретной оптимизации // Изв. АН СССР. Техн. кибернетика. 1988. — N 1. — С.65−77.
  37. А.А., Финкелыптейн Ю. Ю. Дискретное программирование. М.: Наука, 1969. — 368 с.
  38. Г. Математические методы статистики. М.: Мир, 1975. — 648 с.
  39. Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. — 432 с.
  40. Н.Н. О связи оптимумов в задачах линейного и целочисленного линейного программирования / / Дискретная математика. 1991. — Т. З, Вып.1. — С.98−104.
  41. М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990. — 488 с.
  42. В.И., Неймарк Ю. И., Ронин Е. И. Автоматная оптимизация с эволюционной адаптацией // Проблемы случайного поиска. Рига: Зинатне, 1973. — С.83−98.
  43. В.К. Математические модели живучести сетей связи. -Новосибирск: ВЦ СО АН СССР, 1990. 235 с.
  44. JI.A. Статистические методы поиска. М.: Наука, 1968. — 376 с.
  45. И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, думка, 1988. — 472 с.
  46. Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. — Вып.ЗО. — С.61−71.
  47. А.С., Цевээндоржийн И., Кузнецова А. А. Один способ решения задач «{0,1} программирования» //Междунар. конф. «Проблемы оптимизации и экономические приложения»: Тез. докл. — Омск, 1997. — С.150.
  48. А. Теория линейного и целочисленного программирования. Т.2. М.: Мир. 1991. — 342 с.
  49. Фогель JL, Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. — 230 с.
  50. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир. — 1974. — 520 с.
  51. В.Н. Качественные вопросы целочисленного программирования. М.: Физмат лит. — 1995. — 190 с.
  52. Aggarwal С.С., Orlin J.B., Tai R.P. An Optimized Crossover for Maximum Independent Set // Operations Research. 1997. — Vol.45.- P.225−234.
  53. 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.
  54. 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.
  55. 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.
  56. 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.
  57. 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.
  58. 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.
  59. 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.
  60. Battiti R., Protasi M. Reactive Local Search for the Maximum Clique Problem. Report No. TR-95−052. Berkeley: International Computer Science Institute, 1995.
  61. 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.
  62. 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.
  63. Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail // J. Oper. Res. Soc. 1990. — Vol. 41, N 11. — P.1069−1072.
  64. 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.
  65. Beasley J.E., Jornsten K. Enhancing an Algorithm for Set Covering Problems // European J. Oper. Res. 1992. — Vol. 58. — P.293−300.
  66. 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.
  67. Benders J.F. Partitioning Procedures for Solving of Mixed-Variables Programming Problems// Numer. Math. -1962. Vol. 4, N 3. — P.238−252.
  68. Caprara A., Fischetti M., Toth P. Algorithms for the Set Covering Problem. Report No. OR-98−3. Bologna: DEIS, University of Bologna, 1998.
  69. Caprara A., Fischetti M., Toth P., Vigo D. Modeling and Solving the Crew Rostering Problem // Oper. Res. 1998. — Vol. 46 — P.820−830.
  70. Chvatal V. A Greedy Heuristic for the Set Covering Problem // Mathematics of Oper. Res. 1979. — Vol. 4, N 3. — P.233−235.
  71. 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.
  72. Davis L. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991. — 371 p.
  73. 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.
  74. Dongarra J.J. Performance of Various Computers Using Standard Linear Equations Software. Report No. CS-89−85. Tennessee: University of Tennessee, 1998.
  75. Dorigo M., Maniezzo V., Colorny A. Ant System: An Autocatalytic Optimizing Process. Report No. TR-91−016. Milan: Politecnico di Milano, 1991.
  76. Erdos P. On a Combinatorial Problem // Nordisk Mat. Tidskrift. -1963. Vol. 11. — P.5−10.
  77. Eremeev A.V. A Genetic Algorithm for Set Covering Problem// International Conference on Operations Research: Abstr. Zurich: ETH, 1998. — P.42.
  78. 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.
  79. 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.
  80. Eremeev A.V. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of The 4th Artificial Evolution Conference. Dunkerque, 1999. — P.215−226.
  81. 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.
  82. Eremeev A.V. Some Approximate Algorithms for the Vertex Cover Problem // Simposium on Operations Research (SOR'99): Abstr. -Magdeburg, 1999. -P.46.
  83. 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.
  84. 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.
  85. 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.
  86. 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.
  87. Fisher M.L., Kedia P. Optimal Solution of Set Covering Problem Using Dual Heuristics // Manag. Sci. 1990. — Vol. 36, N 8. — P.674−688.
  88. 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.
  89. 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.
  90. Garey M.R., Johnson D.S., Stockmeyer L. Some Simplified NP-Complete Graph Problems// Theoret. Comput. Sci. 1976. — Vol. 1. — P.237−267.
  91. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989. — 412 p.
  92. Goldberg M.K., Russell H. Toward Computing m (4) // Ars Combinatoria 1995. — Vol. 3, N 9. — P.139−148.
  93. 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.
  94. Halldorsson M.M., Radhakrishnan J. Greed is good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs // Algorithmica. 1997. — Vol. 18. — P.143−163.
  95. 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.
  96. Hastad J. Some Optimal Inapproximability Results. Report No. TR-97−037. Trier: Electronic Colloquium on Computational Complexity, 1997.
  97. 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.
  98. Holland J.H. Outline For a Logical Theory of Adaptive Systems // Journal of the Association for Computing Machinery. 1962. — Vol. 3. — P.297−314.
  99. Holland J.H. Genetic Algorithms and the Optimal Allocations of Trials // SIAM Journal of Computing. 1973. — Vol. 2, N 2. — P.88−105.
  100. Karpinski M., Zelikovsky A. Approximating Dense Cases of Covering Problems. Report No. TR-97−001. Trier: Electronic Colloquium on Computational Complexity, 1997.
  101. 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.
  102. Korostensky С., Gonnet G. Gap Heuristics and Tree Construction Using Gaps. Report No. 321. Zurich: ETH, Institute of Scientific Computing, 1999.
  103. Koza J.R. Genetic Programming II: Automatic Discovery of Reusable Programs (Complex Adaptive Systems). MIT Press, 1994.- 746 p.
  104. 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.
  105. Mannino C., Sassano A. Solving Hard Set Covering Problems // Oper. Res. Letters. 1995. — Vol. 18. — P. l-5.
  106. 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.
  107. Nix A. and Vose M. D. Modeling Genetic Algorithms with Markov Chains // Annals of Mathematics and Artificial Intelligence. 1992.- Vol. 5, P. 79−88.
  108. Rechenberg I., Evolutionsstrategie: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution. Stuttgart: Formann-Holzboog Verlag, 1973. — 170 p.
  109. Reeves C.R. Genetic Algorithms for the Operations Researcher// INFORMS Journal on Computing. 1997. — Vol. 9, N 3. — R231−250.
  110. 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.
  111. Ross P. What are Genetic Algorithms Good at? // INFORMS Journal on Computing. 1997. — Vol. 9, N 3. — P.260−262.
  112. Rudolph G. Convergence Analysis of Canonical Genetic Algorithms // IEEE Transactions on Neural Networks. -1994. Vol. 5, N 1. — P. 96−101.
  113. Salveson M.E. The Assembly Line Balancing Problem // J. Industrial Engineering. 1955. — Vol. 6. — P.18−25.
  114. Soriano P., Gendreau M. Solving the Maximum Clique Problem Using a Tabu Search Approach // Annals of Operations Reserach. -1993. Vol. 41. — P.385−403.
  115. Trauth C.A., Woolsey R.E.D., Integer Programming: a Study in Computational Efficiency // Manag. Science. 1969. — Vol. 15, N 9. — P.481−493.
  116. Vose M. D. Modeling Simple Genetic Algorithms // Evolutionary Computation. -1995. Vol. 3, N 4. — P.453−472.
  117. 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.
  118. 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.
Заполнить форму текущей работой

Пора сдавать?