Параллельные метаэвристики в аспекте решения задач децентрализованного диспетчирования информационно-управляющих систем

Parallel metaheuristics in the aspect of problem solving of decentralized manual supervision of information-control systems

Клименко А.Б. Клименко В.В. Пуха И.С.

28.09.2014 2362

№ 9 (10)

10. Информатика, вычислительная техника и управление

Цитировать:

Клименко А.Б., Клименко В.В., Пуха И.С. Параллельные метаэвристики в аспекте решения задач децентрализованного диспетчирования информационно-управляющих систем // Universum: технические науки : электрон. научн. журн. 2014. № 9 (10). URL: https://7universum.com/ru/tech/archive/item/1611 (дата обращения: 26.04.2024).

Прочитать статью:

Keywords: parallel algorithms; metaheuristics; simulated annealing; taboo search; genetic algorithms; ant colony algorithm; reconfiguration

АННОТАЦИЯ

Статья посвящена анализу методов распараллеливания метаэвристик с целью выбора наиболее подходящей комбинации «метаэвристика — метод распараллеливания» для решения задач децентрализованного диспетчирования, в частности — задачи формирования конфигурации информационно-управляющей системы. Рассмотрены: имитация отжига, поиск с запретами, генетические алгоритмы и алгоритмы муравьиных колоний. Обоснован выбор метода распараллеливания и семейства алгоритмов, рассмотрены перспективы их применения в системах реального времени.

ABSTRACT

The article is devoted to the analysis of methods of metaheuristics parallelization in order to choose the most relevant combination of metaheuristic and method of parallelizing for decentralized dispatching problem solving and problems of configuration formation of the information-control system in particular. Simulated annealing, tabu search, genetic algorithms and ant colony algorithm are considered. The selection of parallelization method and family of algorithms is proved; prospects of their use within real-time systems are determined.

Список литературы:

1.   Информационно-управляющая система / [Электронный ресурс] — Режим доступа. — URL: www.ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%BE-%D1%83%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D1%8F%D1%8E%D1%89%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0 (дата обращения: 10.03.2014).
2.   Каляев И.А, Мельник Э.В. Децентрализованные системы компьютерного управления. Ростов н/Д: Издательство ЮНЦ РАН, 2011. — 196 с.
3.   Костенко В.А. Проблемы разработки итерационных алгоритмов для построения расписаний с одновременным нахождением необходимого количества ресурсов и их характеристик // Искусственный интеллект. — 2002. — № 2. — С. 141—150.
4.   Alba E., Luna F., Nebro A.J. and al. Parallel heterogeneous GAS for continuous optimization // Parallel Computing. — 2004. — № 30. — Р. 699—719.
5.   Azencott R. Simulated Annealing: Parallelization Techniques. New York: John Wiley and Sons, 1992. — P. 47—79.
6.   Busetti F. Simulated annealing overview.2003 / [Электронный ресурс] — Режим доступа. — URL: (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=9F958F3AD8ACB341A84315A737883592?doi=10.1.1.66.5018) (дата обращения: 20.02.2013).
7.   Crainic T.G., Toulouse M. Parallel Metaheuristics // Fleet Management and Logistics. 1998. — Р. 205—251.
8.   Crainic T.G., Toulouse M., Gendreau M. Communication Issues in Designing Cooperative Multi Thread Parallel Searches // Meta-Heuristics: Theory &Applications. 1996. — Р. 501—522.
9.   Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis, Dipartimento di Elettronica, Politecnico di Milano. 1992.
10.   Dorigo M., Stiitzle T. Ant Colony Optimization // Computational Intelligence Magazine. — 2006. — № 11. — Р. 28—39.
11.   Durand M.D., White S.R. Trading accuracy for speed in parallel simulated annealing with simultaneous moves // Parallel Computing. — 2000. — № 26. — Р. 135—150.
12.   Ingber L. Simulated annealing: practice versus theory / [Электронный ресурс] — Режим доступа. — URL: http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.15.1046 (дата обращения: 20.02.2013).

Информация об авторах

Клименко Анна Борисовна

канд. техн. наук, м. н. с., Научно-исследовательский институт многопроцессорных вычислительных систем имени академика А.В. Каляева Федерального государственного автономного образовательного учреждения высшего профессионального образования "Южный федеральный университет", г. Таганрог, Россия

Klimenko Anna

Candidate of Technical Sciences, junior research scientist, Research Studies Institute of Multiprocessor systems named after the academician A.V. Kalyaev Federal State Autonomous Educational Institution of Higher Professional Education “Southern Federal University”, Taganrog, Russia

Клименко Владислав Валерьевич

канд. техн. наук, н. с., Научно-исследовательский институт многопроцессорных вычислительных систем имени академика А.В. Каляева Федерального государственного автономного образовательного учреждения высшего профессионального образования "Южный федеральный университет", г. Таганрог, Россия

Klimenko Vladislav

Candidate of Technical Sciences, research scientist, Research Studies Institute of Multiprocessor systems named after the academician A.V. Kalyaev Federal State Autonomous Educational Institution of Higher Professional Education “Southern Federal University”, Taganrog, Russia

Пуха Иван Сергеевич

программист, Научно-исследовательский институт многопроцессорных вычислительных систем имени академика А.В. Каляева Федерального государственного автономного образовательного учреждения высшего профессионального образования "Южный федеральный университет", г. Таганрог, Россия

Puha Ivan

Programmer, Research Studies Institute of Multiprocessor systems named after the academician A.V. Kalyaev Federal State Autonomous Educational Institution of Higher Professional Education “Southern Federal University”, Taganrog, Russia