Перевод названия: PARALLEL REALIZATION OF THE PROBABILITY CHANGIGNG METHOD
Тип публикации: статья из журнала
Год издания: 2012
Ключевые слова: parallel algorithms, combinatorial optimization, параллельные алгоритмы, комбинаторная оптимизация
Аннотация: Методы случайного поиска находят применение для решения широкого круга дискретных задач оптимизации большой размерности, когда использование детерминированных методов становится невозможным без упрощения исходной задачи из-за резкого роста требуемых вычислительных мощностей. Даже в случае применения случайного поиска, однако, требуПоказать полностьюются весьма значительные вычислительные мощности, и точность решения зависит от затраченного времени. Быстрое развитие сравнительно дешевых многопроцессорных систем позволяет значительно сократить время поиска приемлемого решения с коэффициентом ускорения, близким к идеальному. Здесь рассмотрен подход к распараллеливанию алгоритма, реализующего модифицированный вариант метода изменяющихся вероятностей с адаптацией и процедурой возврата для задач оптимизации псевдобулевой функции с ограничениями. Существующий оптимизационный алгоритм адаптирован для систем с общей памятью (использована библиотека GNU OpenMP и соответствующий компилятор). Оценена эффективность параллельного алгоритма. Random search methods are implemented for solving wide variety of large-scale discrete optimization problems when implementing of the determined methods is impossible due to increase of the computational capacity needed. Even the random search methods need sufficient computational facilities and the precision of the solution depends on the dime spent for problem solving. Rapid development of comparatively inexpensive multiprocessor systems allows us to decrease significantly the time spent for obtaining an acceptable solution with almost ideal parallel efficiency coefficient. Here, we consider an approach for parallelizing an algorithm realizing the modified variant of probability changing method with adaptation and rollback procedure for constrained pseudo-Boolean optimization problems. The existing optimization algorithm is adapted for shared memory systems (with use of GNU OpenMp library and corresponding compiler). Parallel algorithm efficiency is estimated.
Журнал: Современные проблемы науки и образования
Выпуск журнала: № 4
Номера страниц: 139-139
ISSN журнала: 20707428
Место издания: Пенза
Издатель: Общество с ограниченной ответственностью "Издательский Дом "Академия Естествознания"