Нейронечіткий генетичний алгоритм оптимізації планів відновлювальних процедур

Размещено на http://www.allbest.ru/

Стаття з теми:

Нейронечіткий генетичний алгоритм оптимізації планів відновлювальних процедур

О.С. Ковалишин, Національний університет «Львівська політехніка»

У процесі відновлення особливе місце відводиться питанням індивідуалізації реабілітаційних послуг, оскільки сучасні травми мають поліструктурний характер, що зумовлює їх важкі наслідки й викликає труднощі на етапах реабілітації. Для вирішення цієї задачі необхідно побудувати повноцінний графік функціонування медичного закладу, на який накладаються множини жорстких обмежень -- умов що мають обов'язково виконуватися для забезпечення коректності розкладу, та м'яких -- корегування розкладу для підвищення якості лікування. У статті запропоновано метод оптимізації планів відновлювальної терапії з використанням генетичного алгоритму. Для оцінки альтернатив сформованих у процесі оптимізаційного процесу використано алгоритм нечіткої логіки з нейромережевою дефазифікацією -- Т-СоМюПек. Розроблений метод апробовано на вибірках побудованих на основі реальних планів відновлювальної терапії.

Ключові слова: багатокритеріальна оптимізація, генетичні алгоритми, нечітка логіка, відновлювальна терапія.

Постановка проблеми

За даними 178 країн 20-50 млн людей у світі щорічно одержують травми. Травми, що призводять до втрати працездатності й інвалідності, одержують понад 250 тис. чоловік на рік [1, 2].

За даними основних показників інвалідності та діяльності медико-соціальних комісій України за 2010-2014 роки первинна інвалідність внаслідок травм займає третє рангове місце в середньому по Україні -- 5,1 і 5,0 випадків на 10 тис. дорослого населення, відповідно. Високий рівень і складність травматизму пов'язані зі збільшенням кількості автодорожніх травм, використанням у побутових умовах сучасних механізмів та недотримання правил техніки безпеки. Сучасні травми мають більш поліструктурний характер, що зумовлює їх важкі наслідки й викликає труднощі на етапах реабілітації [3].

У зв'язку з цим у процесі відновлення особливе місце відводиться питанням надання індивідуально-орієнтованих реабілітаційних послуг, оскільки на сьогодні плани реабілітаційних терапій дуже обмежено враховують інтереси самих пацієнтів, що безпосередньо впливає на показники якості лікування.

Аналіз останніх досліджень та публікацій. Для вирішення задачі організації відновлювальної терапії до уваги слід брати множину обмежень, які накладають на процес -- необхідність узгодження графіків використання медичного обладнання, наявність кваліфікованого медичного персоналу для проведення кожної конкретної процедури в певний момент часу, доступність відповідного устаткування тощо.

Для вирішення цієї задачі необхідно побудувати графік роботи клініки, на який накладаються множини жорстких обмежень -- умов, що мають обов'язково виконувати для забезпечення коректності розкладу, та м'яких -- виконання яких є бажаним, власне інтересів пацієнтів.

Для розв'язання задачі побудови графіку роботи медичних установ використовуються такі методи: повного перебору, гілок та границь, логічного програмування з обмеженнями, розфарбування графу, імітації відпалу, імітаційного моделювання, генетичного алгоритму тощо [4].

Застосування генетичних алгоритмів має низку переваг: [5]:

Генетичний алгоритм використовує кілька точок пошукового простору одночасно, а не переходить від точки до точки, як це робиться в традиційних методах. Це дає змогу подолати один з недоліків традиційних підходів -- небезпеку потрапляння в локальний екстремум цільової функції.

Генетичні алгоритми у процесі роботи не використовують ніякої додаткової інформації, що підвищує швидкість роботи. Винятком слугує множина допустимих значень параметрів і цільової функції в довільній точці.

Генетичний алгоритм використовує як ймовірнісні правила для побудови нових розв'язків, так і детерміновані правила для переходу від одних розв'язків до інших. Одночасне використання елементів випадковості та детермінованості дає значно більший ефект, ніж роздільне.

Зважаючи на вказані переваги, запропоновано використати саме метод генетичних алгоритмів для оптимізації розкладу клініки.

Виклад основного матеріалу дослідження

Представлення розкладу функціонування клініки. До початку оптимізаційного процесу формується математичне представлення розкладу функціонування клініки. Для цього було згруповано процедури за типами з урахуванням застосування необхідного обладнання, наявності медичного персоналу, вимог до періоду проведення процедур та можливості об'єднання пацієнтів у групи.

Для кожного типу згрупованих процедур період, охоплений розкладом, було розбито на можливі часові інтервали їх проведення.

Математично множину часових проміжків проведення процедур представлено так:

де -- дата проведення процедури; -- час проведення процедури; -- максимально допустима кількість паралельних процедур.

У результаті такого розбиття побудовано тривимірний масив, характеристики якого відповідають за розподіл процедур по днях місяця та розподіл за часом впродовж дня; за урахуванням можливості проведення декількох або групових процедур у той самий часовий проміжок.

Побудова структури хромосоми. Після формування представлення розкладу необхідно визначити структуру хромосоми -- вектор значень, які оптимізуються. У цьому випадку кодування хромосоми у вигляді множини символьних чи бінарних даних є недоцільним через складність задачі та часові затрати на кодування та декодування проміжних результатів, тому використано множину процедур, з яких складається розклад.

Математично множину процедур розкладу представлено так:

де-- дата та час проведення процедури; -- медичний персонал,що проводить процедуру; -- множина пацієнтів, для яких процедура проводиться; -- множина обладнання, необхідного для проведення процедури; -- загальна кількість медичного персоналу клініки; -- загальна кількість пацієнтів клініки; -- загальна кількість медичного обладнання.

Графічно структуру хромосоми можна представити так (рис. 1):

Рис. 1 - Структура хромосоми задачі оптимізації розкладу клініки

Побудова початкової вибірки розкладів. Після формування структури хромосоми необхідно побудувати початкову популяцію розкладів.

Для побудови елементів популяції розроблено скінченний автомат [6], вхідним параметром якого є множина планів відновлювальної терапії, з наборами процедур для включення в розклад, а вихідним -- сформований розклад, що задовольняє накладеним жорстким обмеженням (медичний персонал та пацієнти не можуть перебувати на двох процедурах одночасно; процедури необхідно проводити в порядку, визначеному індивідуальним планом лікування; не можна проводити процедури у випадку відсутності або часткового забезпечення устаткуванням чи лікарями).

Математична модель апарата виглядає так:

де X -- множина вхідних даних автомата; Y -- множина вихідних даних автомата; S -- множина допустимих станів автомата; /у -- функція виходів автомат; ^ -- функція переходів з одного стану автомата в інший; 50 -- початковий стан автомата.

Побудова еволюційних операторів. Для організації оптимізаційного процесу необхідно створити механізми розвитку популяції. У контексті генетичних алгоритмів для цього реалізують оператори схрещування та мутації [7].

У цьому випадку використано такі оператори:

зміна часу проведення процедури, що полягає у перенесенні певної процедури з одного часового проміжку на довільний інший доступний часовий проміжок впродовж того самого дня;

зміна дати проведення процедури полягає у перенесенні певної процедури з одного часового проміжку на довільний інший доступний часовий проміжок іншого дня;

обмін пацієнтів процедур полягає у взаємозаміні пацієнтів двох однакових процедур;

обмін медичного персоналу полягає у частковій взаємозаміні кваліфікованого персоналу, що проводить дві процедури одного типу.

Кожен з вищенаведених операторів з певною імовірністю застосовуються на кожній ітерації оптимізаційного процесу.

Нейро-нечітка багатокритеріальна оцінка прогресу оптимізації. Для оцінки прогресу оптимізації необхідно сформувати механізм оцінки альтернатив, сформованих у процесі роботи еволюційних операторів -- функцію приналежності.

Для означення аргументів функції доцільно ввести показники, засновані на штрафах, що встановлюються кожному параметру за будь-який незручний момент у розкладі. З цією метою для кожного типу процедур у розкладі визначається кількість порушень. Значення порушень нормалізуються за такою формулою:

де -- поточне значення /-того критерія порушень; .-- максимальне можливе значення /-того критерія порушень; -- мінімальне можливе значення /-того критерія порушень;

Сформувавши у такий спосіб множину критеріїв оптимізації, здійснено згортання векторного критерію для переходу до однокритеріальної оптимізації завдяки використанню алгоритму нечіткої логіки.

Загальним недоліком таких алгоритмів є неоднозначна та неточна дефазифікація, тому для здійснення нечіткого логічного висновку обрано систему нечіткого виведення T-Controller[8-11] за такі її переваги над іншими системами:

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

об'єднання в єдиний крок логічного виведення (and) і композиції (or);

кількість правил зумовлена особливостями тільки вихідних змінних;

висока точність Т-Controller має нульову методичну похибку дефазифікації (чим точніші «входи», тим точніші «виходи»);

висока швидкість роботи.

Перевагою такого підходу є те, що функція приналежності сформована з врахування досвіду експертів у галузі розробки планів терапії та побажань пацієнтів.

Розроблена нечітка база знань складається з 16 правил, що визначають правила узгодження критеріїв оцінки розкладу.

Визначення критеріїв зупинки роботи методу оптимізації. За умови досягнення ухвалених результатів оптимізації, необхідно здійснити зупинку процесу оптимізації [12].

У цьому випадку зупинка роботи методу відбувається, якщо впродовж визначеної кількості поколінь оптимізації не відбувається покращення хромосоми з найвищим рівнем оцінки. Це означає, що застосування вищенаведених еволюційних операторів не спричинює позитивного впливу на якість результуючого розкладу (чи взагалі спричиняє його погіршення). Інакше кажучи, зупинка алгоритму відбувається в момент досягнення екстремуму та в час збіжності значень функції приналежності.

У процесі роботи алгоритму виконуються такі дії:

Кожна особина поточної популяції оцінюється за допомогою алгоритму нечіткої логіки щодо ступеня задоволення поставлених обмежень.

Кращі рішення копіюються в нову популяцію без змін.

На основі пропорційного відбору з поточної популяції вибираються хромосоми, які піддаються рекомбінації.

Якщо нова популяція сформована, то стара видаляється. Після цього переходимо до п. 5, а в іншому випадку -- до п. 3.

Якщо не виконується критерій зупинки оптимізаційного процесу, виконується перехід на п.1.

Апробація методу. Розроблений метод апробовано на тестових вибірках, побудованих на основі реальних планів відновлювальної терапії. На основі відгуків пацієнтів стосовно процесу терапії сформовано перелік з чотирьох м'яких обмежень:

Критерій 1: відсутність заходів терапії, що передбачають спортивні активності перед сніданком.

Критерій 2: наявність повної години для проведення обіду.

Критерій 3: наявність перерв після водних процедур для відновлення.

Критерій 4: наявність перерв в проведенні процедур для переміщення пацієнтів між місцями проведення.

Для множини вибірок проведено оптимізацію відповідно до жорстких вимог процесу лікування та наведених вище м'яких обмежень.

На рис. 2-4 графічно зображено процес оптимізації.

У табл. 1 наведено результати початкової оцінки розкладів з використання алгоритму нечіткої логіки, значення нормалізованої кількості порушень кожного м'якого обмеження, а також результуючі значення після проведення процесу оптимізації.

Рис. 2 - Графічне відображення роботи методу оптимізації планів відновлювальної терапії. Тестова вибірка № 1

Рис. 3 - Графічне відображення роботи методу оптимізації планів відновлювальної терапії. Тестова вибірка № 2

Рис. 4 - Графічне відображення роботи методу оптимізації планів відновлювальної терапії. Тестова вибірка № 3

Таблиця 1 - Результати роботи методу оптимізації планів відновлювальної терапії

З наведених вище даних видно, що на початкових стадіях роботи методу є висока варіативність варіантів розкладів. Завдяки відбору результатів з найвищою оцінкою разом з наступним застосуванням до них еволюційних операторів відбувається поступове зниження кількості порушень накладених обмежень. Варто зауважити, що метод продовжує роботу у випадках досягнення псевдооптимального значення (різкого зниження кількості порушень за одним із обмежень разом з одночасним підвищенням кількості порушень за іншими). Зупинка методу відбувається в момент, коли застосування операторів схрещування та мутації не призводить до покращення результати оцінки протягом 10 та більше ітерацій методу.

Висновки

У процесі відновлювальної терапії та лікування загалом особливе місце відведено наданню індивідуально-орієнтованих реабілітаційних послуг. Ефективне проведення реабілітації неможливе без удосконалення та оптимізації планів проведення та розкладів виконання процедур у лікувальних закладах.

Оскільки відомо, що не існує ефективних алгоритмів розв'язку задач побудови та оптимізації розкладів за поліноміальний час, одним із найефективніших підходів для вирішення цієї проблеми, що дає можливість уникнути локальних екстремумів та отримати множину глобальних оптимальних рішень, є використання генетичних алгоритмів.

Використання алгоритму нечіткої логіки підвищеної точності забезпечує згортання векторного критерію обмежень та перехід від багатокритеріальної оцінки до однокритеріальної. Перевагою такого підходу є використання цільової функції сформованої з врахуванням багаторічного досвіду експертів у галузі побудови планів відновлювальної терапії.

Проведений аналіз і розроблений метод дають змогу провести побудову та багатокритеріальну оптимізацію планів відновлювальної терапії у контексті розкладів медичних закладів. Врахування інтересів пацієнтів як обмежень дає можливість підвищити індивідуалізацію надаваних послуг та, як наслідок, сприяє покращенню ефективності діяльності медичних закладів.

Список використаних джерел

клініка розклад алгоритм оптимізація

1. Аналіз сучасного стану реабілітацції інвалідів в Україні / Хобзей М. К., Іпатов А. В., Коробкін Ю. І., Мороз О. М. Медичні перспективи. 2010. № 4.

2. Іпатов А. В., Сергієні Т. Г., Войтчак О. В. Професійна реабілітація інвалідів / за ред. В. В. Марунича. Дніпропетровськ: Пороги, 2005. 227 с.

3. Основні показники інвалідності та діяльності медико-соціальних експертних комісій України за 2014 рік.

4. Іпатов А. В., Мороз О. М., Голик В. А., Перепелична Р. Я., Ханюкова І.Я., Коробкін Ю. І., Молчанов Р. М., МаловичкоГ. М., Гондуленко Н. О., Саніна Н.А. Основні показники інвалідності та діяльності медико-соціальних експертних комісій України за 2014 рік.

5. Аналітико-інформаційний довідник / за ред. С.І. Черняка. Дніпропетровськ: Роял-Принт, 2015. 167 с.

6. Коффман Э.Г. Теория расписаний и вычислительные машины. Москва: Наука, 1984. 335 с.

7. Глибовец H.Н., Медвідь С.А. Генетичиские агоритмы и их использование для решения задачи составления расписания. Кибернетика и системный анализ. 2003. № 1. С. 95-108.

8. Tkachenko R. O., Kovalyshyn O. S. Method of making up clinic schedule with use of finite-state automaton. Econtechmod. An international quarterly journal. 2016. Vol. 5. №. 3. 131-134.

9. Hosny M., Shameem F. A Survey of Genetic Algorithms for the University Timetabling Problem. International Conference on Future Information Technology. Singpore. 2011. Vol. 13. Pp. 34-39.

10. Дорошенко А. В., Ткаченко Р. О. Нейроподібніструктуримашинигеометричнихперетворень у завданняхінтелектуальногоаналізуданих. Міжнароднанауковаконференція «Інтелектуальнісистемиприйняттярішень і проблемиобчислювальногоінтелекту» ISDMCI'2009: зб. наук. пр. у 2 т., 18-22 трав. 2009 р. Євпаторія, Україна. Херсон, 2009. Т. 2. С. 309-314.

11. Rule based Fuzzy system of Improved accuracy / Tkachenko O., Tkachenko R., Hirniak Yu., Mushenyk P. Proceeding of the 56-th international Colloquium: Innovation of Mechanical Endineering - Shaping the Future. Ilmenau University of Technology. Pp. 1-6.

12. Verbenko I., Tkachenko R. Fuzzy Methods and Tools for Grane Management System Based on T-Controller. Journal of Global Research in Computer Science. 2013. Vol. 4. № 3. Pp. 1-4.

13. T-Controller Workshop. URL: http://tkatchenko.com/t-controller/about-t-controller/ (станомна 21.05.2018).

14. Odim O. M., Oguntunde B. O., Alli O. O. On the Fitness Measure of Genetic Algorithm for Generating Institutional Lecture Timetable. Journal of Emerging Trends in Computing and Information Since. 2013. Vol. 4 №. 4. Pp. 436-444.0.

15. REFERENCES

1. Khobzei, M. K., Ipatov, A. V., Korobkin, Yu. I., &Moroz, O. M. (2010).Analizsuchasnohostanureabilitatstsiiinvalidiv v Ukraini: Medychniperspektyvy, 4 (in Ukrainian).

16. Ipatov, A. V, Serhiieni, T H., &Voitchak, O. V. (2005). Profesiinareabilitatsiiainvalidiv. Dnipropetrovsk: Porohy (in Ukrainian).

17. Ipatov, A. V., Moroz, O. M., Holyk, V. A., Perepelychna, R. Ya., Khaniukova, I. Ya., Ko- robkin, Yu. I., Molchanov, R. M., Malovychko, H. M., Hondulenko, N. O., &Sanina, N. A. (2015). Osnovnipokaznykyinvalidnostitadiialnostimedyko-sotsialnykhekspertnykhko- misiiUkrainyza 2014 rik: Osnovnipokaznykyinvalidnostitadiialnostimedyko-sotsialnykhekspertnykhkomisiiUkrainyza 2014 rik: Analityko-informatsiinyidovidnyk. Dnipropetrovsk: Roial-Prynt (in Ukrainian).

18. Koffman, E. G. (1984). Teoriiaraspisaniiivychislitelnyemashiny. Moskva: Nauka (in Russian).

19. Glibovetc, H. N., &Medvid, S. A. (2003). Genetichiskieagoritmyiikhispolzovaniedliaresheniiazadachisostavleniiaraspisaniia: Kibernetikaisistemnyianaliz, 1, 95-108 (in Russian).

20. Tkachenko, R. O., &Kovalyshyn, O. S. (2016). Method of making up clinic schedule with use of finite-state automaton: Econtechmod. An international quarterly journal, 5, 3, 131-134 (in English).

21. Hosny, M., &Shameem, F. (2011). A Survey of Genetic Algorithms for the University Timetabling Problem: International Conference on Future Information Technology. Singpore, 13, 34-39 (in English).

22. Doroshenko, A. V., &Tkachenko, R. O. (2009). Neiropodibnistrukturymashynyheomet- rychnykhperetvoren u zavdanniakhintelektualnohoanalizudanykh. Mizhnarodnanaukovakonferentsiia «Intelektualnisystemypryiniattiarisheniproblemyobchysliuvalnohointelektu» ISDMCI'2009: zb. nauk. pr. u 2 t., 18-22 trav. 2009 r. Yevpatoriia, Ukraina. Kherson, T. 2, 309-314 (in Ukrainian).

23. Tkachenko, O., Tkachenko, R., Hirniak, Yu.,&Mushenyk, P. Rule based Fuzzy system of Improved accuracy: Proceeding of the 56-th international Colloquium: Innovation of Mechanical Endineering - Shaping the Future. Ilmenau University of Technology, 1-6 (in English).

24. Verbenko, I., &Tkachenko, R. (2013). Fuzzy Methods and Tools for Grane Management System Based on T-Controller: Journal of Global Research in Computer Science, 4, 3, 1-4 (in English).

25. T-Controller Workshop. Retrieved from http://tkatchenko.com/t-controller/about-t-controller/ (stanomna 21.05.2018) (in English).

26. Odim, O. M., Oguntunde, B. O., &Alli, O. O. (2013). On the Fitness Measure of Genetic Algorithm for Generating Institutional Lecture Timetable: Journal of Emerging Trends in Computing and Information Since, 4, 4, 436-444.0 (in English).

The high level and complexity of domestic injuries are associated with an increase in the number of road injuries and the use of modern mechanisms in domestic conditions, noncompliance with safety rules. Modern injuries have a poly structured character, which causes their severe consequences and difficulties in the different stages of rehabilitation. In this regard, in the process of rehabilitation, special attention is given to the issue of individually oriented rehabilitation services, since at present plans for rehabilitation therapy are very limited to the interests of patients themselves, which directly affects the quality of treatment.

In order to solve the problem, it is necessary to take into account the set ofrestrictions imposed on the process -- the need to consolidate schedules of the medical equipment usage, the availability of qualified medical personnel for each specific procedure at a certain time, the availability of off-the-shelf equipment, etc.

Infact, to solve this problem, it is necessary to construct afullfunctioning schedule of the medical institution, which is superimposed on the set of hard restrictions -- the conditions that must necessarily be fulfilled to ensure the correctness of the schedule, and soft requirements -- the implementation of which is desirable -- the actual interests ofpatients. The following methods are used to solve the problem of constructing a schedule for medical institutions: full selection, method of branches and boundaries, logical programming with constraints, graph coloring, simulated annealing, simulation modeling, genetic algorithm, etc.

Regarding other methods, genetic algorithms have several advantages, such as: simultaneous use of several points of the search space, the use of probabilistic and deterministic rules for the transition between solutions, the absence of the need to use an external extra data and operations. Therefore, it has been suggested to use genetic algorithms to solve the problem of multi-criteria optimization of rehabilitation therapy plans. To assess the progress of optimization, a mechanism for evaluating alternatives generated during the work of evolution operators has been constructed. A fuzzy logic controller, the T-Controller, has several advantages over classical methods: high accuracy of computations, zero methodological error, high speed of operation.

Indicators based on fines imposed for violation of a certain criterion are used as input arguments of the controller. For the organization of the optimization process, the mechanisms of population development--crossover and mutation operators have been developed.

Keywords: multicriteria optimization, genetic algorithms, fuzzy logic, rehabilitation therapy.

Размещено на Allbest.ru