ПОРІВНЯННЯ РЕЗУЛЬТАТІВ ЕКСПЕРИМЕНТУ СКЛАДАННЯ РОЗКЛАДУ ПРОЦЕДУР МЕТОДАМИ: ГЕНЕТИЧНИЙ АЛГОРИТМ, МУРАШИНИЙ АЛГОРИТМ ТА МЕТОД ГІЛОК І МЕЖ

Анна Олександрівна Данильченко, Світлана Миколаївна Кравченко

Анотація


В статті наведені порівняння результатів експерименту складання розкладу процедур пацієнтами санаторію (на прикладі санаторію «Дениші» (Житомирська обл.)) за різноманітними методами (генетичний алгоритм, мурашиний алгоритм та метод гілок та меж) та алгоритмами (наприклад, генетичним алгоритмом), що були модифіковані автором для пошуку максимального паросполучення у дводольному графі та враховують обмеження сумісності. Експеримент порівняння методів проведено на обчислювальних платформах за допомогою авторського програмного продукту ICS_DENISH. Оцінено часові витрати на виконання розрахунків та ефективність алгоритмів. В основі порівняльного обчислювального експерименту необхідність вибору алгоритму з найменшою обчислювальною складністю для прикладного використання його в санаторних закладах України.


Ключові слова


паросполучення; дводольний граф; генетичний алгоритм; метод гілок і меж; метод повного перебору

Повний текст:

PDF

Посилання


Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э.Рейнгольд, Ю.Нивергельт, Н.Део. – М. : Мир, 1980. – 476 с.

Харари Ф. Теория графов / Ф.Харари ; пер. с англ. и предисл. В.П. Козырева ; под ред. Г.П. Гаврилова. – 2-е. изд. – М. : Едиториал УРСС, 2003. – 296 с.

Балдин А.В. Математическое программирование : учебник / К.В. Балдин, Н.А. Брыз¬галов, А.В. Рукосуев ; под общ. ред. д.э.н., проф. К.В. Балдина. – М. : Издат.-торг. корпорація «Дашков и К», 2009. – 220 с.

Гладков Л.А. Генетические алгоритмы : учебное пособие / Л.А. Гладков, В.В. Курей¬чик, В.М. Курейчик. – 2-е изд. – М. : Физматлит, 2006. – 320 с.

Данильченко О.М. Інтелектуальний аналіз даних (Data Mining) : навч. посібник / О.М. Данильченко, А.О. Данильченко. – Житомир : ЖДТУ, 2009. – 405 с.

Жолобов Д.А. Введение в математическое программирование : учебное пособие / Д.А. Жолобов. – М. : МИФИ, 2008. – 376 с.

Cormen Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. – MIT Press, 2001. – P. 1292.

Штовба С.Д. Муравьиные алгоритмы. Exponenta Pro / С.Д. Штовба // Математика в приложениях. – 2003. – № 4. – С. 70–75.

Алгоритм для решения задачи коммивояжера / Д.Ж. Литтл, К.Мурти, Д.Суини и др. // Экономика и математические методы. – 1965. – Т. 1. – Вып. 1. – С. 90–107.

Данильченко О.М. Розв’язання одного класу задач складання розкладів генетичними алгоритмами на кластерних системах / О.М. Данильченко, А.О. Данильченко, С.А. Ібрагім // Вісник ЖІТІ. – 2004. – № 4. – С. 130–135.


Пристатейна бібліографія ГОСТ






DOI: https://doi.org/10.26642/tn-2015-2(73)-159-166

Copyright (c) 2016 Анна Олександрівна Данильченко, Світлана Миколаївна Кравченко

Це видання ліцензовано за ліцензією Creative Commons Із Зазначенням Авторства - Некомерційна 4.0 Міжнародна.