10.14489/vkit.2015.03.pp.016-021

DOI: 10.14489/vkit.2015.03.pp.016-021

Мельник Э. В., Клименко А. Б.
ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА ИМИТАЦИИ ОТЖИГА С УСКОРЕННЫМ ПОНИЖЕНИЕМ ТЕМПЕРАТУРЫ ДЛЯ ФОРМИРОВАНИЯ КОНФИГУРАЦИИ РАСПРЕДЕЛЕННОЙ ИНФОРМАЦИОННО-УПРАВЛЯЮЩЕЙ СИСТЕМЫ
(с. 16-21)

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

Ключевые слова: распределенная информационно-управляющая система; формирование конфигурации; имитация отжига; децентрализованное управление.

Melnik E. V., Klimenko А. B.
EXPERIMENTAL RESEARCH OF THE SIMULATED ANNEALING ALGORITHM WITH THE ACCELERATED TEMPERATURE CHANGE RATE FOR THE DISTRIBUTED INFORMATION-CONTROL SYSTEM CONFIGURATION FORMING
(pp. 16-21)

Abstract. Information-control systems(ICS) are in active use almost everywhere, so the fault-tolerant ICS design and development is the one of the key questions of the day. ICS with distributed dispatching is one of prospective branches in the fault-tolerant ICS area. Distributed dispatching concept implies the system based on peer-to-peer computational elements network without any dedicated control elements. Such systems provide reconfiguration capabilities; meaning in case of the computational element failure, other elements can accomplish its tasks. In order to reconfigure the ICS, the system should have prepared configurations in memory, or, at least, the possibility to create ones on the fly. So the problem of configuration forming is actual: computations have to be planned, and the set of computational elements must be chosen under strict time constraint. The formalized problem is NP-hard, and it is the reason to use some metaheuristics instead of “branch-and-bound” algorithms. Similar problems are successfully solved by simulated annealing methods, as well as by genetic algorithms, but there is no single opinion about the “best” method. In this paper we examined simulated annealing “quenching” algorithm and genetic algorithm with single-point crossover and tournament selection. The evaluation criterion is “the best objective function value for the shortest time period”. The results of experiments are presented and discussed, some conclusions are made and the future work outlined based on experimental evaluation results.

Keywords: Distributed information-control system; Configuration forming; Simulated annealing; Decentralized dispatching.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Э. В. Мельник, А. Б. Клименко (Научно-исследовательский институт многопроцессорных вычислительных систем им. акад. А. В. Каляева Южного федерального университета, Таганрог) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

E. V. Melnik, А. B. Klimenko (Scientific Recearch Institute оf Multiprocessor Computer Systems of Southern Federal University, Taganrog) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Каляев И. А, Мельник Э. В. Децентрализован-ные системы компьютерного управления. Ростов н/Д: Изд-во ЮНЦ РАН, 2011. 196 с.
2. Планирование выполнения заданий сервисных приложений в распределенной среде / В. Н. Захаров и др. // Системы и средства информатики. 2008. Вып. 18. С. 36 – 42.
3. Алгоритмы параллельного выполнения заданий сервисных приложений в распределенной среде / В. А. Дьячков и др. // Системы и средства информатики. 2008. Вып. 18. C. 49 – 70.
4. Барский А. Б. Параллельные процессы в вычис-лительных системах: планирование и организация. М.: Радио и связь, 1990. 256 с.
5. Костенко В. А. Проблемы разработки итераци-онных алгоритмов для построения расписаний с одно-временным нахождением необходимого количества ре-сурсов и их характеристик // Искусcтвенный интеллект. Донецк. 2002. № 2. С. 141 – 150.
6. Костенко В. А., Смелянский Р. Л., Трекин А. Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов // Программирование. 2000. № 5. С. 63 – 72.
7. Горелова Г. В., Мельник Э. В. Эффект вырав-нивания вычислительной нагрузки процессорных уст-ройств в высоконадежных распределенных информаци-онно-управляющих системах / Мехатроника, автомати-зация, управление. 2012. № 11. С. 29 – 35.
8. Мельник Э. В., Горелова Г. В. Имитационное моделирование вариантов резервирования в распреде-ленных информационно-управляющих системах с децен-трализованной организацией / Известия ЮФУ. Техни-ческие науки. 2013. № 3. С. 184 – 193.
9. Ingber L. Simulated Annealing: Practice Versus Theory // Mathematical and Computer Modelling. 1993. N 18. P. 29 – 57.
10. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by SimulatedAnnealing. Science, New Series, 1983. V. 220, N 4598. P. 671 – 680.
11. Goldberg D. E. Genetic Algorithms in Search, Op-timization and Machine Learning. USA: Addison-Wesley publishing Company, Inc., 1989.

Eng

1. Kaliaev I. A, Mel'nik E. V. (2011). Decentralized computer control systems. Rostov-on-Don: Izdatel'stvo IuNTs RAN.
2. Zakharov V. N., Kozmidiadi V. A., Kuz'min A. V., Popov A. S., Shuliatnikov D. S. (2008). Scheduling jobs exe-cution of service applications in a distributed environment. Systems and means of Informatics. Institut problem informatiki RAN. Moscow: Nauka.
3. D'iachkov V. A., Zakharov V. N., Kozmidiadi V. A., Kuz'min A. V., Shuliatnikov D. S. (2008). The algorithms of parallel jobs execution of service applications in a distributed environment. Systems and means of Informatics. Institut problem informatiki RAN. Moscow: Nauka.
4. Barskii A. B. (1990). Parallel processes in compu-ting systems: planning and organization. Moscow: Radio i sviaz'.
5. Kostenko V. A. (2002). Problems of development of iterative algorithms for constructing schedules with the sim-ultaneous finding the required number of resources and their characteristics. Iskusctvennyi intellekt, (2), pp. 141-150.
6. Kostenko V. A., Smelianskii R. L., Trekin A. G. (2000). Synthesis the structures of real time computing sys-tems using genetic algorithms. Programmirovanie, (5), pp. 63-72.
7. Gorelova G. V., Mel'nik E. V. (2012). The effect of the equalization processing of the processor devices load in a highly reliable distributed information management sys-tems. Mekhatronika, avtomatizatsiia, upravlenie, (11), pp. 29-35. Moscow: Novye tekhnologii.
8. Mel'nik E. V., Gorelova G. V. (2013). Simulation modelling of options in distributed information management systems with a decentralized organization. Izvestiia IuFU. Tekhnicheskie nauki, (3), pp. 184-193. Taganrog: Izdatel'stvo TTIIuFU.
9. Ingber L. (1993). Simulated annealing: Practice ver-sus theory. Mathematical and Computer Modelling, (18), pp. 29-57.
10. Kirkpatrick S.; Gelatt C. D., Vecchi M. P. (1983). Optimization by simulated annealing. Science, New Series, 220(4598), pp. 671-680.
11. Goldberg D. E. (1989). Genetic algorithms in search, optimization and machine learning. USA: Addison-Wesley publishing Company, Inc.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 250 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2015.03.pp.016-021}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 250 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2015.03.pp.016-021}