ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МЕТОДА ИЗМЕНЯЮЩИХСЯ ВЕРОЯТНОСТЕЙ : научное издание | Научно-инновационный портал СФУ

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МЕТОДА ИЗМЕНЯЮЩИХСЯ ВЕРОЯТНОСТЕЙ : научное издание

Перевод названия: 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

Место издания: Пенза

Издатель: Общество с ограниченной ответственностью "Издательский Дом "Академия Естествознания"

Авторы

  • Казаковцев Л.А. (Сибирский государственный аэрокосмический университет)
  • Ступина А.А. (Сибирский государственный аэрокосмический университет)

Вхождение в базы данных

Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.

Вы можете отметить интересные фрагменты текста, которые будут доступны по уникальной ссылке в адресной строке браузера.