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

Ключевые слова: комбинаторная оптимизация, метаэвристики, Н-метод, агенты, задача коммивояжера, квадратичная задача о назначениях.

ACM Classification Keywords: G.1.6 Numerical Analysis Optimization – Stochastic programming, G.2.1 Discrete Mathematics Combinatorics – Combinatorial algorithms, I.2.8 Artificial Intelligence: Problem Solving, Control Methods, and Search – Heuristic methods.

Link:

МУЛЬТИАГЕНТНЫЙ Н-МЕТОД В КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ

Леонид Гуляницкий, Денис Гобов

http://foibg.com/ibs_isc/ibs-10/ibs-10-p13.pdf