Том 19, номер 2, 2012 г., Стр. 41-54

УДК 519.7
Еремеев А. В. 
Генетический алгоритм с турнирной селекцией как метод локального поиска

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

Ключевые слова: генетический алгоритм, локальный поиск, приближенное решение.

Еремеев Антон Валентинович ¹
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: eremeev@ofim.oscsbras.ru

Статья поступила 18 июня 2011 г.
Исправленный вариант — 2 августа 2011 г.

Литература

[1] Гнеденко Б. В. Курс теории вероятностей. — М: Наука, 1988. — 451 с.

[2] Загоруйко Н. Г. Самообучающийся генетический алгоритм прогнозирования (GAP) // Искусств. интеллект и эксперт. системы. Вып. 160. — Новосибирск: Вычисл. системы, 1997. — С. 3–17.

[3] Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. — М: МЦНМО, ЧеРо, 1999. — 192 с.

[4] Кочетов Ю. А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журн. вычисл. математики и мат. физики. — 2008. — T. 48, № 5. — C. 788–807.

[5] Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискрет. математика и её приложения: Сб. лекций молодежных научных школ по дискретной математике и её приложениям. — М: Изд-во центра прикл. исслед. при мех.-мат. фак. МГУ,
2001. — С. 84–117.

[6] Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечёткие системы. — М: Горячая линия — Телеком, 2006. — 452 с.

[7] Сайко Л. А. Исследование мощности $L$-накрытий некоторых задач о покрытии // Дискрет. оптимизация и анализ сложных систем: Сб. науч. тр. — Новосибирск: ВЦ СО АН СССР, 1989. — C. 76–97.

[8] Aarts E. H. L., Lenstra J. K. Introduction // Local search in combinatorial optimization. — New York: John Wiley & Sons Ltd., 1997. — P. 1–19.

[9] Ausiello G., Protasi M. Local search, reducibility and approximability of NP-optimization problems // Inf. Process. Lett. — 1995. — Vol. 54. — P. 73–79.

[10] Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems // J. Heurist. — 1998. — Vol. 4, N 2. — P. 107–122.

[11] Droste S., Jansen T., Wegener I. Upper and lower bounds for randomized search heuristics in black-box optimization // Theory Comput. Syst. — 2006. — Vol. 39, N 4. — P. 525–544.

[12] Eremeev A. V. Modeling and analysis of genetic algorithm with tournament selection // Proc. Artificial Evolution Conf. (Dunkerque, France, November 3–5, 1999). — Berlin: Springer-Verl., 2000. — P. 84–95. (Lect. Notes Comp. Sci.; Vol. 1829.)

[13] Eremeev A. V., Reeves C. R. Evolutionary algorithms in discrete optimization // Discrete Optimization and Operations Research Conf. (Novosibirsk, June 24–28, 2002). Abstr. — Novosibirsk, IM Press, 2000. — P. 40–45.

[14] Goldberg D. E. A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing // Complex Syst. — Vol. 4. — P. 445–460.

[15] Holland J. Adaptation in natural and artificial systems. — Ann Arbor: Univ. Michigan Press, 1975. — 183 p.

[16] Reeves C. R. Genetic algorithms for the operations researcher // INFORMS J. Comput. — 1997. — Vol. 9, N 3. — P. 231–250.

[17] Rödl V., Tovey C. Multiple optima in local search // J. Algorithms. — 1987. — Vol. 8. — P. 250–259.