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

Автор:

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

Бібліографічний опис статті:

. Аналіз методів селекції в генетичному алгоритмі знаходження оптимальної стратегії лікування//Наука онлайн: Міжнародний електронний науковий журнал - 2019. - №7. - https://nauka-online.com/ua/publications/tehnicheskie-nauki/2019/7/analiz-metodiv-selektsiyi-v-genetichnomu-algoritmi-znahodzhennya-optimalnoyi-strategiyi-likuvannya/

Стаття опублікована у: : Наука Онлайн No7 июль 2019

Технічні науки

УДК 004.02 + 616.1

Бабенко Віталій Олегович

студент

Національного технічного університету України

«Київський політехнічний інститут імені Ігоря Сікорського»

Науковий керівник:

Носовець Олена Костянтинівна

кандидат технічних наук,

доцент кафедри біомедичної кібернетики

Національний технічний університет України

«Київський політехнічний інститут імені Ігоря Сікорського» 

АНАЛІЗ МЕТОДІВ СЕЛЕКЦІЇ В ГЕНЕТИЧНОМУ АЛГОРИТМІ ЗНАХОДЖЕННЯ ОПТИМАЛЬНОЇ СТРАТЕГІЇ ЛІКУВАННЯ

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

Ключові слова: вроджені вади серця, генетичні алгоритми, рулеточний відбір, турнірний відбір, елітарний відбір, ранжування. 

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

Аналіз останніх досліджень і публікацій. Девід Е. Голдберг, Л. Гладков, В. Курейчик і В. Курейчик, Д. Рутковська, М. Пилинський і Л. Рутковський розглядали в своїх роботах генетичні алгоритми. Матеріал Бабенка В.О. використовувався для аналізу комплексного алгоритму вирішення багатокритеріальної задачі оптимізації. Панченко Т.В. приділив увагу покращенню генетичних алгоритмів.

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

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

Рис. 1. Вибірка пацієнтів з вродженими вадами серця для дослідження

Таблиця 1

Показники пацієнтів

Назва змінної Позначення
Вхідні змінні
AGE x101
ǾLPA x102
NAKATA x103
VEDP x104
pPA x105
EDI 106
PVR x107
RISK x108
(Z-score) MV x109
Гипертрофия x110
R x111
BAS x112
Змінні управління
PE by day x201
DOBUT x202
ADRENAL x203
EC COND TO x204
COAOR x205

 Продовж. табл. 1.

Назва змінної Позначення
Змінні управління
DKS 206
AV repair No TV closure x207
PA plasty bin x208
Kawashima + HV redirection x209
Вихідні змінні
PE>14 x301
Все аритмии бин x302
PLEURITIS EARLY x303
PLICAT x304
STROKE x305
THROMBOSIS x306
CHYLE x307
AV BLOCK x308
SND x309

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

В комплексному алгоритмі використовувався рулеточний метод селекції. Його суть полягає в тому, що особин відбирають за допомогою N-ої кількості «запусків рулетки» (N – кількість популяції). Колесо рулетки складається з секторів для кожної особи популяції, розмір яких пропорційний ймовірності попадання особи в нову популяцію.

Ефективність роботи даного методу було перевірено на експериментальній вибірці. Кількість осіб було задано числом 16, для кожного пацієнта комплексний алгоритм проводився 100 раз для більш точного результату. В результаті отримано (табл. 2).

 Таблиця 2

Результат роботи рулеточного методу селекції для популяції із 16 осіб

Пацієнт, № Середня кількість ітерацій для знаходження оптимального методу лікування
1 24,59
2 21,81
3 20
4 24,82
5 23,87
6 22,95
7 20,04
8 20,46
9 23,43
10 24,92

З цієї таблиці можна зробити висновок, що при заданій кількості 16 осіб в популяції, в середньому результат знаходиться за 22,69 ітерацій.

Збільшивши кількість осіб до 32 було отримано (табл. 3):

Таблиця 3

Результат роботи рулеточного методу селекції для популяції із 32 осіб

Пацієнт, № Середня кількість ітерацій для знаходження оптимального методу лікування
1 34,11
2 27,91
3 28,40
4 27,73
5 25,81
6 27,34
7 27,57
8 30,56
9 25,33
10 32,42

Тобто, якщо збільшувати популяцію, результат стає гіршим.

Даний метод порівнювався з наступними:

  • турнірний метод;
  • елітарний метод;
  • ранжування.

Турнірний відбір полягає в тому, що із N особин вибирають випадковим чином обирають t особин, найкращий із яких стає батьком наступного покоління. Так повторюється N раз.

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

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

    (1)

де:

  • 1 ≤ a ≤ 2 вибирається випадковим чином;
  • N – кількість осіб в популяції
  • i – номер особи в упорядкованому списку.

Для експериментальної вибірки проведемо кожен із цих методів. Результати представлені в табл. 4-6.

Таблиця 4

Результат роботи турнірного методу селекції

Пацієнт, № Середня кількість ітерацій при n = 16 Середня кількість ітерацій при n = 32
1 6,66 7,66
2 6,38 7,8
3 6,85 8,55
4 6,86 7,9
5 6,72 8,11
6 6,93 7,85
7 6,72 8,13
8 6,39 7,87

 Продовж. табл. 4

Пацієнт, № Середня кількість ітерацій при n = 16 Середня кількість ітерацій при n = 32
9 6,82 8,55
10 6,66 7,72

Таблиця 5

Результат роботи елітарного методу селекції

Пацієнт, № Середня кількість ітерацій при n = 16 з використанням рулеточного відбору Середня кількість ітерацій при n = 32 з використанням рулеточного відбору Середня кількість ітерацій при n = 16 з використанням турнірного відбору Середня кількість ітерацій при n = 32 з використанням турнірного відбору
1 28,66 44,98 7,5 9,08
2 23,62 33,48 7,08 9,37
3 21,18 31,14 7,05 10,05
4 25,36 44,96 6,87 10,02
5 25,61 39,28 7,13 9,06
6 26,53 37,64 7,03 9,6
7 23,52 34,08 7,23 9,39
8 24,21 36,33 7,14 10,09
9 22,49 34,16 7,34 9,71
10 24,11 38,75 7,03 9,32

Таблиця 6

Результат роботи методу ранжування

Пацієнт, № Середня кількість ітерацій при n = 16 Середня кількість ітерацій при n = 32
1 29,32 45,02
2 28,62 42,32
3 26,82 44,84
4 27,89 45,5
5 29,22 46,47
6 31,12 47,33
7 28,53 44,79
8 28,63 47,62
9 32,23 45,72
10 27,07 43,13

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

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

Література

  1. Бабенко В.О. Система аналізу ризиків після хірургічного лікування у ранньому післяопераційному періоді / В.О. Бабенко // Міжнародний науковий журнал “Інтернаука”. 2019. №8. С. 12. (стаття).
  2. Goldberg D. E. Genetic algorithms in search, optimization & machine learning / D. E. Goldberg. — Addison-Wesley Publishing Company, Inc., 1989.
  3. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилинський, Л. Рутковский. Москва : Горячая линия – Телеком, 2013. 385 с.
  4. Гладков Л. Генетические алгоритмы / Л. Гладков, В. Курейчик, В. Курейчик. Litres, 2018. 303 с.
  5. Панченко Т. В. Генетические алгоритмы / Т. В. Панченко. Астрахань: Издательский дом «Астраханский университет», 2007. 88 с.

References

  1. Babenko V.O Sistema analiza rizikov pislia hirurgichnogo likuvannia u ranniomu pisliaoperaciynomu periodi / V.O. Babenko // Mizhnarodniy naukoviy jurnal “Internauka”. 2019. №8. 12. (stattia).
  2. Goldberg D. E. Genetic algorithms in search, optimization & machine learning / D. E. Goldberg. — Addison-Wesley Publishing Company, Inc., 1989.
  3. Rutkovskaya D. Neyronnie seti, geneticheskie algoritmi i nechetkie sistemi / D. Rutkovskaya, M. Pilinskiy, L. Rutkovskiy. Москва : Горячая линия – Телеком, 2013. 385 p.
  4. Gladkov L. Geneticheskie algoritmi / L. Gladkov, V. Kureychik, V. Kureychik. Litres, 2018. 303 p.
  5. Panchenko T.V. Geneticheskie algoritmi / T.V. Panchenko. Astrahan: Izdatelskiy dom «Astrahansiy univesitet», 2007. 88 p.

Перегляди: 275

Коментарі закрито.

To comment on the article - you need to download the candidate degree and / or doctor of Science

Підготуйте

наукову статтю на актуальну тему, відповідно до роздлів журналу

Відправте

наукову статтю на e-mail: editor@inter-nauka.com

Читайте

Вашу статтю на сайті нашого журналу та отримайте сертифікат