МОДИФИЦИРОВАННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ФОРМИРОВАНИЯ ГРАФИКА ПРОХОЖДЕНИЯ ЛЕЧЕБНО-ОЗДОРОВИТЕЛЬНЫХ ПРОЦЕДУР

MODIFIED GENETIC ALGORITHM FOR CREATION OF THE SCHEDULE FOR THE PASSING OF HEALTH-RELATED PROCEDURES

Zadorozhnaya K.G., Savkova H.O., Kozhbakova A.A.
«Donetsk National Technical University», Donetsk, Russian Federation

Введение

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

В результате анализа было выявлено, что ни один из методов в классическом представлении не может покрыть все аспекты разрабатываемой предметной области. Однако, генетический алгоритм является более гибким в процессе поиска решения, поскольку использует несколько точек поискового пространства [1]. Для решения поставленной задачи предложено использовать модифицированный генетический алгоритм, который позволит получать оптимальные решения с учетом особенностей и специфики работы лечебно-оздоровительных учреждений.

Представление особи

В разрабатываемом модифицированном генетическом алгоритме подразумевается, что особь является возможным вариантом графика прохождения лечебно-оздоровительных процедур для выбранного пациента p_i.

Каждая особь представлена в виде двух взаимосвязанных хромосом, где информация 1-ой – оборудование, отведенное на проведение назначенных процедур, а 2-ой – сеансы (промежутки времени), за которые процедуры будут проведены пациенту (рисунок 1) [2]. Также в данной задаче можно использовать особь, состоящую из трех хромосом, где 3-я содержит информацию о специалистах, предоставляющих процедуры. Однако для упрощения алгоритма данная информация будет учитываться в назначениях a_ps.

В предлагаемом генетическом алгоритме не требуется кодирования генов хромосом в виде нулей и единиц как это принято в существующих генетических алгоритмах. Гены 1-ой хромосомы содержат информацию об оборудовании из множества Eq = {eq_z}, где z ∊ [1, N_eq]. При этом каждое оборудование предназначено для определённой процедуры или вида процедур. Поэтому оборудование (eq_z^num, eq_z^type) характеризуется номером eq_z^num и типом проводимых процедур eq_z^type. Гены 2-ой хромосомы содержат информацию о промежутках времени из множества временных интервалов T = {t_k}, где k ∊ [1, N_t]. Каждый временной интервал (t_k^date, t_k^time) характеризуется двумя параметрами: t_k^date – дата проведения лечебно-оздоровительной процедуры (номер дня), t_k^time – время (номер временного интервала в течение дня).

Рисунок 1 – Структура особи

Для структурирования необходимых данных возникла необходимость в множестве назначения A_p = {a_ps}, где s ∊ [1, f]. Данное множество содержит блочную информацию о назначенных процедурах proc_j пациенту p_i, и специалистах, которые будут их проводить.

В обеих хромосомах одинаковое количество генов f, равное количеству назначенных процедур пациенту. Следовательно, s гену 1-ой хромосомы соответствует оборудование (из числа допустимых), выбранное для предоставления процедуры, а s гену 2-ой хромосомы – время её проведения [2].

Этапы модифицированного генетического алгоритма

Разработанный модифицированный генетический алгоритм для решения задачи формирования оптимального графика прохождения лечебно-оздоровительных процедур можно представить следующей последовательностью действий:

1. Установка параметров эволюции. Инициализация начальной популяции для одного пациента. Формирование каждой особи происходит следующим образом. Для каждого гена 1-ой и 2-ой хромосомы, соответствующей назначению a_ps для p_i пациента, задаются некоторые значения: для 1-ой - номер оборудования из допустимых для проведения назначенной процедуры, для 2-ой – номер свободного интервала времени. Описанный процесс продолжается до момента достижения численности популяции, определяемой в начале алгоритма при установке параметров эволюции.
2. Селекция особей. Оценка всех особей, входящих в популяцию, отбор наиболее приспособленных особей, имеющих более предпочтительные значения функции пригодности по сравнению с остальными особями [3]. Оператор отбора является важнейшим фактором, влияющим на эффективность генетического алгоритма, поскольку неудачный выбор метода селекции может привести к сужению области поиска и к потере наиболее приспособленных особей популяции.

Для предотвращения потери лучших особей в качестве метода отбора предлагается использовать турнирную селекцию, дополненную принципом элитарной стратегии [4], которая заключается в защите наилучших особей на последующих итерациях. Из предыдущей популяции выбирается Q отдельных особей (число Q имеет фиксированное числовое значение), имеющих максимальное значение функции пригодности (1) [3].

Функцией пригодности в данном случае является целевая функция, представленная в виде суммы значений критериев потери качества К для всех назначенных процедур пациенту p_i. Требуется найти такое решение, которое минимизирует значение целевой функции:

F = ∑_p=1^N K_p → min,

(1)

где K_p – значение критерия потери качества для одной из назначенных процедур пациенту.

При этом K_p вычисляется по формуле:

K = f(eq_z, t_k) = ∑_q=1^M c_q × koef_q(eq_z, t_k),

(2)

где koef_q − значение коэффициента штрафа за невыполнение q−го частного критерия;
c_q − оценка, определяющая степень невыполнения q−го частного критерия;
eq_z – оборудование;
t_k − временной интервал [4].

3. Создание потомков выбранных пар родителей – выполнение оператора кроссинговера. Для каждой пары отобранных особей случайным образом выбираются позиции гена G1 и G2 и производится обмен участками генетического кода между соответствующими хромосомами родительских особей. Первая часть одного родителя копируется в первого потомка. Во вторую часть потомка копируются гены второго родителя. Если такие гены уже встречаются в потомке, то они пропускаются, а оставшуюся часть потомка дополняют генами первого родителя [5].

Рисунок 2 – Схема скрещивания двух особей

4. Мутация новых особей. Мутация играет достаточно важную роль в работе генетического алгоритма: вносит дополнительное разнообразие в текущую популяцию и тем самым расширяет пространство поиска оптимального решения [3].

Рисунок 3 – Схема мутации особи

В результате мутации s-му 1-ой хромосомы будет присвоен номер оборудования, из допустимого набора оборудований, предназначенных для проведения данной процедуры, а для s-го гена 2-ой хромосомы будет выбрано любое свободное значение временного интервала для данного оборудования (рисунок 3).

5. Проверка значений функции конфликтов. Если этот ген не равен нулю, значит в хромосоме или одинаковым временным интервалам соответствуют разные процедуры, или одному оборудованию соответствуют разные процедуры, или одно оборудование соответствует одинаковым временным интервалам. Такое расписание содержит конфликт, который обязательно должен быть разрешен. В этом случае следует заменить номер оборудования или временного интервала на свободный (рисунок 4).

Рисунок 4 – Проверка значения функции конфликтов

Ген «конфликтов» позволяет сократить время проведения вычислительного эксперимента, что непосредственно ускоряет процесс сходимости алгоритма и получения оптимального решения [3].

6. Расширение популяции новыми порожденными особями. Оператор отбора выполняет функции фильтрующего инструмента, который выделяет в составе популяции особи, имеющие низкое значение функции пригодности. Выделенные найденные слабые особи удаляются из популяции, происходит сокращение расширенной популяции до исходного размера [3].
7. Обнаружена сходимость или достигнуто максимальное количество итераций. В результате применения операторов селекции, кроссинговера и мутации формируется популяция потомков, которая заменяет родительскую популяцию, после чего выполняется проверка сходимости алгоритма.

Если критерий останова алгоритма выполнен, то выбор лучшей особи в конечной популяции – результат работы алгоритма. Иначе переходим на шаг 2 (селекция особей) и выполняем алгоритм до тех пор, пока не выполнится критерий останова. В качестве решения выбирается особь, которая в наибольшей степени удовлетворяет всем требованиям и ограничениям разрабатываемой предметной области [2].

Существует также менее ресурсозатратный вариант решения. Упрощение происходит на уровне формирования особи. Поскольку каждая процедура proc_j, назначенная пациенту p_i может предоставляться с определённой периодичностью (каждый день, раз в 2-3 дня и т. д.), то оптимально будет определить оборудование и интервал времени для 1-ой процедуры каждого вида, а потом занимать полученные интервалы с указанной периодичностью. Эффективность обоих вариантов будет рассмотрена экспериментальным путем.

Выводы

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

Также были предложены модифицированные процедуры скрещивания, мутации, проверки значений функции конфликтов, специально адаптированные для работы с предложенными структурированными объектами генетической оптимизации. Это позволяет существенно упростить учет ограничений, вызванных особенностями разрабатываемой предметной области.

В результате была сформирована теоретическая база для реализации модифицированного генетического алгоритма. Целесообразно проводить исследования по оптимизации и улучшению разрабатываемого алгоритма для получения более удовлетворяющих результатов.