ЭВОЛЮЦИОННЫЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДИСПЕТЧЕРИЗАЦИИ

  • В.В. Курейчик Южный федеральный университет
  • А.Э. Саак Южный федеральный университет
  • Вл.Вл. Курейчик ООО «Газпром подземремонт Уренгой»
Ключевые слова: Grid-система, диспетчирование, эволюционное моделирование, эволюционный алгоритм

Аннотация

Рассмотрена одна из важных задач оптимизации – задача диспетчеризации. Она от-
носится к классу NP- сложных оптимизационных задач. В работе приведена и описана
постановка задачи диспетчеризации. Здесь массив заявок пользователей на компьютерноеобслуживание в Grid- системах моделируется протяжённой линейной полиэдралью коор-
динатных ресурсных прямоугольников. При этом диспетчирование представляется лока-
лизацией линейной полиэдрали в оболочку области вычислительно-временных ресурсов сис-
темы согласно многоцелевому критерию качества применяемого назначения заявок на об-
служивание. В связи со сложностью данной задачи для ее эффективного решения предла-
гаются методы эволюционного моделирования. В статье предложена и описана модифи-
цированная архитектура эволюционного поиска. В качестве модификации введены допол-
нительно три блока. Это блок «внешней среды», блок эволюционной адаптации и блок «не-
перспективных решений». Для ее реализации авторами разработан модифицированный
эволюционный алгоритм, использующий в качестве отбора решений модели эволюций Ч.
Дарвина и Ж. Б. Ламарка. Это позволяет значительно сократить время получения резуль-
тата, частично решить проблему преждевременной сходимости алгоритма и получать
наборы квазиоптимальных решений за полиномиальное время. Разработан программный
модуль на языке C#. Проведен вычислительный эксперимент на тестовых примерах. Про-
веденные экспериментальные исследования, показали, что качество решений, полученных
на основе разработанного эволюционного алгоритма, в среднем на 5 процентов превосхо-
дит результаты решений, полученные с использованием известных алгоритмов последова-
тельного, начально-кольцевого и уровневого при сопоставимом времени, что говорит об
эффективности предложенного подхода.

Литература

1. Kovalenko V.N., Koryagin D.A. Grid: istoki, printsipy i perspektivy razvitiya [Grid: sources,
principles and prospects of development], Informatsionnye tekhnologii i vychislitel'nye sistemy
[Information technologies and computing systems], 2008, No. 4, pp. 38-50.
2. Vasenin V.A., Shundeev A.S. Evolyutsiya tekhnologii Grid [Evolution of Grid technology],
Informatsionnye tekhnologii [Information Technologies], 2012, No. 1, pp. 2-9.
3. Barskiy A.B. Algoritmicheskie, arkhitekturnye i strukturnye metody organizatsii
upravlyayushchikh protsessov v virtual'nom prostranstve sredstv Grid-sistemy [Algorithmic, architectural
and structural methods of organizing control processes in the virtual space of Gridsystem
tools], Informatsionnye tekhnologii [Information Technologies], 2012, No. 5, pp. 2-6.
4. Kovalenko V.N., Semyachkin D.A. Metody i algoritmy upravleniya parallel'nymi zadaniyami v
gride s resursami v forme klasterov [Methods and algorithms for managing parallel tasks in a
grid with resources in the form of clusters], Vestnik Yuzhnogo nauchnogo tsentra RAN [Bulletin
of the Southern Scientific Center of the Russian Academy of Sciences], 2008, Vol. 4,
No. 3, pp. 23-34.
5. Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoylov V.I. Rekonfiguriruemye mul'tikonveyernye
vychislitel'nye struktury [Reconfigurable multiconveyor computing structures], under the general
ed. of I.A. Kalyaeva. Rostov-on-Donu: Izd-vo YuNTS RAN, 2009.
6. Liu C., Baskiyar S. A general distributed scalable grid scheduler for independent tasks, J. Parallel
Distrib. Comput., 2009, Vol. 69, pp. 307-314.
7. Saak A.E. Lokal'no-optimal'nye resursnye raspredeleniya [Locally optimal resource distributions],
Informatsionnye tekhnologii [Information technologies], 2011, No. 2, pp. 28-34.
8. Saak A.E. Dispetcherizatsiya v Grid-sistemakh na osnove odnorodnoy kvadratichnoy tipizatsii
massivov zayavok pol'zovateley [Dispatching in Grid-systems based on homogeneous quadratic
typing of arrays of user requests], Informatsionnye tekhnologii [Information Technologies],
2012, No. 4, pp. 32-36.
9. Saak A.E. Polinomial'nye algoritmy raspredeleniya resursov v Grid-sistemakh na osnove
kvadratichnoy tipizatsii massivov zayavok [Polynomial algorithms for resource allocation in
Grid systems based on quadratic typing of request arrays], Informatsionnye tekhnologii [Information
Technologies], 2013, No. 7. Appendix, 32 p.
10. Korf R. Huang E. New Improvements in Optimal Rectangle Packing. In Proceedings of the
21st International Joint Conference on Artificial Intelligence (IJCAI 2009). Pasadena,
California, USA, July 11-17, 2009, pp. 511-516.
11. Saak A.E. Dispetchepizatsiya massivov zayavok summapnoy pesupsnoy mepy, pavnoy
kvadpatu tselogo chisla [Dispatching of request arrays with a total resource measure equal to
the square of an integer], Informatsionnye tekhnologii [Information Technologies], 2015, Vol.
21, No. 9, pp. 675-679.
12. Emel'yanov V.V., Kureychik V.V., Kureychik V.M. Teoriya i praktika evolyutsionnogo
modelirovaniya: monografiya [Theory and practice of evolutionary modeling: monograph].
Moscow: Fizmatlit, 2003.
13. Kureychik V.V., Kureychik V.M., Rodzin S.I. Kontseptsiya evolyutsionnykh vychisleniy,
inspirirovannykh prirodnymi sistemami [The concept of evolutionary calculations inspired by
natural systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2009, No. 4 (93), pp. 16-24.
14. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy:
monografiya [Theory of evolutionary calculations: monograph]. Moscow: Fizmalit, 2012.
15. Kureychik V.V., Rodzin S.I. O pravilakh predstavleniya resheniy v evolyutsionnykh
algoritmakh [On the rules for the representation of solutions in evolutionary algorithms],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7
(108), pp. 13-21.
16. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: a textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p.
17. Kureychik V.M., Kureychik V.V. Ob upravlenii na osnove geneticheskogo poiska [About management
on the basis of genetic search], Avtomatika i telemekhanika RAN [Avtomatika i
telemekhanika RAS], 2001, No. 10, pp. 174-187.
18. Kureychik V.V. Kureychik V.M., Sorokoletov P.V. Analiz i obzor modeley evolyutsii [Analysis
and review of models of evolution], Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy
upravleniya [Izvestiya Rossiyskoy akademii nauk. Theory and control systems], 2007, No. 5,
pp. 114-126.
19. Korf R. Huang E. Optimal Rectangle Packing on Non- Square Benchmarks. In Proceedings of
the twenty-fours AAAI Conference on Artificial Intelligence (AAAI-10). Atlanta, Georgia, USA,
July 11–15, 2010, pp. 83-88.
20. Saak A.E. Sravnitel'nyy analiz polinomial'nykh algoritmov dispetcherizatsii v Grid-sistemakh
[Comparative analysis of polynomial dispatching algorithms in Grid systems],
Informatsionnye tekhnologii [Information Technologies], 2012, No. 9, pp. 28-32.
21. Saak A.E. Urovnevye algoritmy dispetcherizatsii massivami zayavok krugovogo tipa v Gridsistemakh
[Level algorithms for dispatching circular-type request arrays in Grid-systems],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6
(167), pp. 223-231.
Опубликован
2021-07-18
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ