Генетический локальный поиск для задачи о разбиении графа на доли ограниченной мощности

Для задачи о разбиении графа на доли ограниченной мощности разработан метод генетического локального поиска. На каждой итерации метода имеется набор локальных оптимумов задачи. Этот набор используется для целенаправленного поиска новых локальных оптимумов с меньшей погрешностью. Установлена плотная PLS-полнота задачи нахождения локальных оптимумов с рядом полиномиально проверяемых окрестностей. Показано, что в худшем случае число локальных улучшений может оказаться экспоненциальным при любых правилах выбора направления спуска. Для частного случая задачи, когда веса ребер равны единице и нахождение локальных оптимумов является полиномиальной процедурой, проведены численные эксперименты. Результаты экспериментов свидетельствуют о высокой эффективности разработанного метода и возможности решать задачи большой размерности. Библ. 25.