Том 7, серия 2, номер 1, 2000 г., Стр. 47-60
УДК 519.854.6
А. В. Еремеев
Генетический алгоритм для задачи о покрытии
Аннотация:
Изучается известная задача о нахождении совокупности подмножеств минимального суммарного веса, покрывающих данное множество. Предложен новый вариант генетического алгоритма, в котором при выборе подпокрытия из объединения двух родительских покрытий используются методы линейного программирования. Проведен вычислительный эксперимент на эталонных тестовых задачах большой размерности, построенных случайным образом или имеющих комбинаторное содержание. Результаты счета и сравнение с другими подходами подтверждают хорошую работоспособность алгоритма.
Ил. 2, табл. 4, библиогр. 20.
Еремеев А. В. 1
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: eremeev@iitam.omsk.net.ru
Статья поступила 17 марта 1999 г.
Исправленный вариант — 2 марта 2000 г.
