Один класс алгоритмов стохастического локального поиска
Proc. of XIII Int. Conf. "Knowledge. Dialogue. Solution (KDS-2007)" (June, 2007, Varna, Bulgaria). V.1. – Sofia: ITHEA, 2007. – P. 102–111.
Анотація:
Рассматриваются алгоритмы ускоренного вероятностного моделирования, которые относятся к классу методов стохастического локального поиска. Приводится общая вычислительная схема алгоритмов, на основе которой с использованием принципа «золотого сечения» предлагается алгоритм комбинаторной оптимизации, названный GS-алгоритмом. Исследуются вопросы сходимости предложенного алгоритма на основе анализа цепей Маркова. Приведена оценка числа операций, необходимых для достижения глобального решения. Дан обзор применения рассмотренных алгоритмов для решения разных типов задач комбинаторной оптимизации.
Ключові слова: combinatorial optimization, stochastic local search, simulated annealing, Markov chains.