EN|RU

Том 18, номер 4, 2011 г., Стр. 3-16

УДК 519.8
Береснев В. Л., Гончаров Е. Н., Мельников А. А.
Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций

Аннотация:
Для задачи оптимизации псевдобулевой функции рассматривается алгоритм локального поиска с обобщённой окрестностью. Такая окрестность строится для локально-оптимальных решений и включает в себя другие локально-оптимальные решения, «окружающие» данное. Приводятся результаты вычислительных экспериментов с использованием псевдобулевых функций, оптимизация которых эквивалентна задачам размещения предприятий, покрытия множества и конкурентного размещения предприятий. Целью экспериментов является сравнительная оценка локально-оптимальных решений, получаемых стандартным алгоритмом локального поиска и алгоритмом локального поиска с обобщённой окрестностью.
Табл. 6, библиогр. 11.

Ключевые слова: оптимизация, локальный спуск, полином от булевых переменных, задача размещения предприятий, задача о покрытии.

Береснев Владимир Леонидович 1,2
Гончаров Евгений Николаевич 1,2

Мельников Андрей Андреевич 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: beresnev@math.nsc.ru, goncharov@math.nsc.ru, a.a.melnikov@hotmail.com

Статья поступила 4 апреля 2011 г.

 © Институт математики им. С. Л. Соболева, 2015