Метаэвристический метод деформаций для решения задач комбинаторной оптимизации
Proc. of XIII Int. Conf. "Knowledge. Dialogue. Solution (KDS-2007)" (June, 2007, Varna, Bulgaria). V.1. – Sofia: ITHEA, 2007. – P. 95–102.
Анотація:
Исследуются проблемы разработки приближенных алгоритмов комбинаторной оптимизации. Приводится формализация понятия комбинаторных объектов, позволяющая строго формально определить понятие задачи комбинаторной оптимизации. Предлагается метаэвристический алгоритм комбинаторной оптимизации, названный Н-методом, метаэвристика которого использует аналогии с известным в недифференцируемой непрерывной оптимизации методом Нелдера-Мида. В качестве встроенной процедуры использован G-алгоритм – один из алгоритмов стохастического локального поиска. Обсуждаются вопросы практической реализации алгоритмов предложенного Н-метода. Приводятся результаты вычислительного эксперимента по решению квадратичных задач о назначениях из известной библиотеки.
Ключові слова: комбинаторная оптимизация, метаэвристики, популяционные методы, стохастический локальный поиск, квадратичная задача о назначении.