Клименко А.Б., Троценко Р.В. Решение задачи оптимизации ресурсов и планирования вычислений с использованием параллельной имитации отжига

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

Ключевые слова:

Abstract: various metaheuristics, such as method of simulated annealing, are currently used for solving the tasks of resource usage optimization and computation scheduling. Simulated annealing is a serial method and it is difficult to parallelize it. However, different methods of parallelization have been developed recently in order to improve the quality of the solutions and the time of algorithm execution. The subjects of the study are the methods of parallelization for annealing simulation, in particular, the method of independent starts with and without synchronization. As an example of simulated annealing implementation the authors select the method with thermal scheme “quenching” as the fastest one. The article shows analytical review of simulated annealing parallelization, with a selection of the most promising methods, for which a series of computational experiments was carried out. Scientific novelty of the work is in the discovery of new dependencies and trends that were not described previously in similar studies. In discussing the parallelized annealing simulation with synchronization the authors raise a question of the existence of the dependence of the quality of the solutions with not only the number of computing devices, but also with the frequency of the solutions exchanges. For asynchronous parallel simulated annealing the article shows a tendency to solutions improvement with the increase of the number of computing devices, while for synchronous simulated annealing a similar dependence was not found.

Keywords: