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

УДК 004.02 + 616.1

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

студент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблиця 1

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

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

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

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

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

 Таблиця 2

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

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

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

Таблиця 3

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

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

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

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

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

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

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

де:

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

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

Таблиця 4

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

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

Таблиця 5

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

Таблиця 6

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

Отримавши повні результати, можна побачити, що серед усіх перевірених методів селекції найбільш ефективним, тобто найшвидшим, є метод турнірного відбору. При популяції в 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.