Методическое пособие 719
.pdf
фективности методов решения оптимизационных задач является разработка алгоритмов адаптации значений их свободных параметров к особенностям конкретной задачи, либо к особенностям некоторого класса задач.
Комбинирование различных алгоритмов может быть высокоуровневым, когда между методами существует слабая связь и легко выделить каждый из них, и низкоуровневым, при которой методы интегрированы настолько сильно, что выделить составляющие итогового метода обычно невозможно, т.е. низкоуровневая гибридизация порождает, по сути, новый метод оптимизации. Иллюстрация обоих методов комбинирования приведена на рис.
При комплексировании объединяться могут не только однотипные алгоритмы, но и алгоритмы из разных классов. Очень эффективными при решении сложных задач большой размерности являются комбинации детерминированных и стохастических методов.
Детерминированные алгоритмы, как правило, требуют много времени и вычислительных ресурсов, и не могут использоваться для решения сложных задач оптимизации. Но в объединении с эволюционными методами они могут улучшить эффективность поиска.
Метод M1 |
|
|
Метод |
|
Метод |
Метод |
|
|
|
|
|
|
M1 |
Метод Mn |
Метод Mn
Способы комплексирования алгоритмов: а) – высокоуровневое; б) – низкоуровневое
При низкоуровневом комбинировании эволюционных и точных методов используется «встраивание» как точного алгоритма в эвристический, так и наоборот. Например, основным может быть ветвей и границ, который для выбора следующего узла дерева использует какой-либо из эволюционных алгоритмов. Обратным примером может являться обращение из генетического алгоритма к точному для выбора лучшего потомка из возможных [3].
При высокоуровневом комбинировании алгоритмы различных классов вызываются последовательно, передавая друг другу информацию о полученном на текущий момент решении. Например, какой-либо из стохастических методов может использоваться для уменьшения размерности задачи, которая потом ре-
230
шается каким-либо из методов математического программирования. Или для упрощения задачи могут использоваться методы релаксации, а дальнейшее решение продолжает стохастический метод.
Литература
1.Белышев, Д.В. Программный комплекс многометодных интеллектуальных процедур оптимального управления / Д.В. Белышев, В.И. Гурман // Автоматика и телемеханика. 2003. №6. С. 60-67.
2.Минаева, Ю.В. Применение параллельных вычислений в многометодных процедурах решения задач оптимизации / Ю.В. Минаева // Вестник Воронежского государственного технического университета. 2013. Т. 9. № 5-1. С.
57-59.
3.Минаева, Ю.В. Структурно-параметрическая адаптация генетического алгоритма / Ю.В. Минаева // Вестник СибГУТИ. 2017. № 1 (37). С. 83-89.
ФГБОУ ВО «Воронежский государственный технический университет», Россия
УДК 681.3
Э.И. Воробьев, Д.В. Иванов, А.В. Буздалин
РАЗРАБОТКА ПРОЦЕДУРЫ ВЫБОРА ОПТИМАЛЬНОЙ СТРУКТУРЫ СПЕЦИАЛИЗИРОВАННЫХ ПОДВИЖНЫХ МЕДИЦИНСКИХ КОМПЛЕКСОВ
В статье рассматриваются вопросы с определением оптимальной структуры подвижных медицинских комплексов и определения алгоритма оптимального выбора оборудования.
Процесс формирования оптимальной структуры специализированных медицинских комплексов (СПМК), может осуществляться двумя способами [2].
При проектировании СПМК первична структура комплекса, состоящая из набора оборудования, должна удовлетворять требованиям ТЗ.
Решение задачи проектирования СПМК можно разбить на 3 этапа:
1)формируется предварительная структура комплекса, т.е. осуществляется выбор вариантов оборудования комплекса;
2)составляется целевая функция оптимизации параметров комплекса;
3)решается задача оптимизации построенной целевой функции с целью выявления оптимальности выбранного оборудования.
Исходными данными для выбора оборудования СПМК является анализ оборудования, разрешенного к применению на подвижных объектах, анализ оборудования существующих комплексов, новые разработки оборудования.
231
Обозначим через S = {s1, s2 ,..., sR} набор оборудования предполагаемого
СПМК. Пусть S R, где множество R представляет собой формализованное описание всех возможных вариантов предполагаемого СПМК. Это описание производится на основе опыта, накопленного при создании и эксплуатации существующих комплексов.
Все оборудование обладает характеристиками, отвечающими за эффективность функционирования СПМК. Совокупность характеристик оборудования представляет собой список величин, заданных в ТЗ, которые необходимо оптимизировать.
Для оптимизации выбора оборудования построим целевую функцию с целью получения наилучших характеристик параметров комплекса, по которым проводится оптимизация. Целевая функция содержит частные критерии оптимальности, соответствующие той или иной характеристике. Так, например, при проектировании СПМК в качестве оптимизируемых характеристик выступают: пропускная способность комплекса, потребляемая мощность, массо-габаритные показатели, уровень радиационной безопасности, показатели надежности. Тогда задача выбора оптимального оборудования комплекса выразится следую-
−
щим образом: найти хотя бы один вектор параметров комплекса V , обеспечивающий минимум скалярной функции
− |
R |
− |
(1) |
F(V ) = min ∑Fk (V )Pk , |
|||
k =1
−
где Fk (V ) – частные критерии оптимальности; Рk – весовые коэффициенты па-
раметров.
Частный критерий оптимальности является функционалом того или иного параметра комплекса. В то же время частный критерий оптимальности является функцией параметров оборудования.
Различают детерминированные и статистические частные критерии оптимальности. Статистические критерии оптимальности основаны на использовании статистических характеристик оборудования.
К детерминированным критериям относятся критерии, соответствующие задаче максимального приближения определенного параметра комплекса к заданному. Тогда
− |
, |
(2) |
Fk (V ) = min Ki − K0 |
где Кi – i-й параметр комплекса; Ко – заданный в ТЗ параметр комплекса. Каждый из частных критериев оптимальности вносит свой вклад в целе-
вую функцию обладая разной размерностью. Так, например, пропускная способность флюорографического комплекса составляет не менее 10 человек в час. В то же время потребляемая мощность такого комплекса составляет не более 10000 Вт. Поэтому весовые коэффициенты устанавливаются таким образом, чтобы слагаемые в (1) были примерно одинаковыми.
232
При практическом проектировании СПМК встает задача поиска минимума целевой функции. Известны методы решения задачи оптимизации целевой функции [1]: методы одномерного поиска, градиентные методы, статистические методы.
Методы одномерного поиска определяют минимум функции одной переменной F(V) в случае отсутствия ограничений на область допустимых значений. В этом сл учае довольно трудно оптимизировать многомерную целевую функцию.
Градиентные методы оптимизации решают задачу минимизации многомерной целевой функции, однако они довольно сложны, требуют больших затрат машинного времени, применение малых шагов для расчета производных может привести к потере точности.
Применение статистических методов оптимизации позволяет решать задачу нахождения минимума многомерной целевой функции последовательным приближением к экстремуму путем накопления статистических данных на предыдущих шагах оптимизации. В этом случае зона поиска с каждым шагом сужается и при достижении ее заданных размеров принимается за минимум многомерной функции. Если находится несколько областей экстремумов, то каждый исследуется отдельно, а затем выбирается глобальный оптимум.
При применении метода Монте-Карло генерируется случайный набор оборудования Si, который статистически учитывается. Рассчитывается значение целевой функции, что соответствует первому шагу поиска. Далее генерируется другой набор оборудования Sj и рассчитывается целевая функция. Перебор вариантов оборудования позволит случайным образом найти границу минимума целевой функции. При дальнейших переборах оборудования, в случае выхода значения целевой функции за границу минимума, данный вариант отбрасывается. На следующих шагах уточняется набор оборудования с целью получения минимума целевой функции. После выполнения определенного числа шагов область поиска смещается к оптимальной точке.
Метод Монте-Карло с сокращением границ на каждом шаге позволит обеспечить решение задачи оптимального выбора оборудования СПМК.
Исходя из вышесказанного, алгоритм выбора структуры СПМК представляется следующей последовательностью действий.
1.На основании концепции предполагаемого комплекса, генерируется набор оборудования комплекса Si, определяется первая граница F(V).
2.Генерируется набор оборудования комплекса Sj. Если целевая функция уменьшилась, определяется новая граница.
3. Уточняется набор оборудования комплекса для получения целевой функции.
4. Если параметры выбранного оборудования удовлетворяют требованиям ТТЗ, окончить оптимизацию, в противном случае, необходимо либо снижать требования ТТЗ, либо формировать другое множество R возможных вариантов.
233
Таким образом, решение задачи нелинейного программирования на основе метода структурной оптимизации, позволит проектировать оптимальные СПМК.
Литература
1.Балашов, Е.П. Эволюционный синтез систем / Е.П. Балашов. – М.: Радио и связь, 1985. – 328 с.
2.Основы теории надежности и эксплуатации радиоэлектронной техники.
/Под ред. Н.А. Шишонка. – М.: Сов. радио, 1964. – 551 с.
ФГБОУ ВО «Воронежский государственный технический университет», Россия
УДК 681.3
В.Н. Коровин
ОЦЕНКА ЗНАЧИМОСТИ КЛИНИЧЕСКИХ ПРИЗНАКОВ ЯЗВЫ, ПАНКРЕАТИТА И ЖЕЛЧНОКАМЕННОЙ БОЛЕЗНИ
С ПОМОЩЬЮ КОРРЕЛЯЦИОННОГО АНАЛИЗА
Для проведения анализа были отобраны данные сорока пациентов с различными диагнозами: язва желудка, панкреатит, желчнокаменная болезнь. Данные первых 10 пациентов приведены в табл. 1-2.
Таблица 1
Исходные данные пациентов для проведения анализа
|
|
|
|
|
ОАК |
|
|
|
|
|
ОАМ |
|
|
|
|
||
№ |
|
|
|
|
|
|
|
|
|
прозра |
|
|
|
|
|
|
|
|
по |
воз- |
Hh(г/ |
Лц(*10 |
|
Эр(*10 |
Эф( |
СОЭ( |
цве |
зра- |
рРе- |
|
|
бе- |
|
слиз |
со |
|
л |
раст |
л) |
9/л) |
|
12/л) |
%) |
мм/ч) |
т |
ность |
акция |
уд.вес |
лок |
Лц |
ь |
ли |
|
1 |
1 |
36 |
142 |
4,8 |
|
4,2 |
2 |
10 |
1 |
1 |
1 |
0 |
024 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 |
30 |
144 |
6,3 |
|
3,9 |
1,8 |
5 |
1 |
1 |
1 |
1022 |
1 |
1 |
1 |
1 |
|
3 |
2 |
72 |
136 |
7,2 |
|
4 |
1,6 |
22 |
2 |
2 |
1 |
1023 |
1 |
1 |
1 |
1 |
|
4 |
2 |
55 |
132 |
4,8 |
|
3,7 |
1,8 |
5 |
2 |
3 |
1 |
1029 |
2 |
1 |
2 |
1 |
|
5 |
2 |
29 |
118 |
12,9 |
|
4,4 |
2 |
58 |
1 |
1 |
1 |
1003 |
1 |
1 |
1 |
1 |
|
6 |
1 |
48 |
111 |
6,7 |
|
4,37 |
4 |
3 |
1 |
3 |
1 |
1008 |
1 |
1 |
1 |
1 |
|
7 |
1 |
83 |
144 |
6,3 |
|
3,9 |
3 |
10 |
1 |
1 |
1 |
1011 |
1 |
1 |
1 |
1 |
|
8 |
2 |
63 |
133 |
5,5 |
|
4,2 |
1,6 |
13 |
3 |
3 |
1 |
1009 |
2 |
2 |
2 |
1 |
|
9 |
1 |
54 |
87 |
7,7 |
|
2,82 |
2 |
5 |
1 |
1 |
1 |
1013 |
1 |
1 |
2 |
2 |
|
10 |
1 |
85 |
114 |
10,4 |
|
3,81 |
0 |
0 |
1 |
2 |
1 |
1019 |
2 |
2 |
1 |
1 |
|
234
|
|
|
|
|
|
|
|
|
|
Таблица 2 |
|
|
|
Исходные данные пациентов для проведения анализа |
|
|
|||||||
|
|
|
|
БхАК |
|
|
|
|
|
|
|
№ |
глюко- |
билиру- |
моче- |
об.белок(г/ |
|
|
|
|
|
|
|
|
за |
бин |
вина |
л) |
креатинин |
амилаза |
ЭКГ |
ФГДС |
УЗИ |
Диагноз |
|
1 |
4,8 |
10 |
3,6 |
76,2 |
81 |
98 |
3 |
2 |
1 |
1 |
|
2 |
5,3 |
12,1 |
6,7 |
65,7 |
116 |
87 |
1 |
3 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
4,3 |
13 |
6,8 |
59 |
79 |
120 |
1 |
3 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
5,1 |
17,8 |
6 |
79,2 |
82 |
101 |
1 |
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
4,9 |
11,1 |
5 |
50 |
101 |
94 |
1 |
1 |
4 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
8,54 |
15 |
28,8 |
63 |
233,9 |
98,3 |
2 |
1 |
4 |
3 |
|
7 |
7,3 |
196 |
3,8 |
72 |
78 |
76 |
2 |
1 |
4 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
7,3 |
275,8 |
6,9 |
51 |
76,2 |
34 |
2 |
3 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
5,7 |
9,3 |
2,7 |
54,3 |
77,4 |
67,7 |
1 |
2 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
6,2 |
15,2 |
9,9 |
77 |
120 |
47,3 |
1 |
2 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
В столбцах для каждого пациента указаны различные клинические признаки, а также данные инструментальных исследований. Некоторые показатели отмечены цифрами, которые характеризуют следующее:
ПОЛ: 1- мужской, 2 - женский.
ОАМ: цвет:1-светло-желтая;2-темная;3-грязно-желтая. ОАМ: прозраность:1-прозрачная;2-полупрозрачная;3-мутная.
ОАМ:реакция:1-кислая;2-слабокислая;3-щелочная;4-нейтральная. ОАМ: белок: 1-в пределах нормы; 2-незначительная протеинурия. ОАМ: лейкоциты:1-в пределах нормы; 2- лейкоцитурия.
ОАМ: соли:1-"-";2-"+". ОАМ: слизь: 1- "-"; 2- "+".
ЭКГ: 1-норма, 2-ГМЛЖ, 3- блокада правой ножки п.Гиса ФГДС: 1-норма, 2-язва, 3- гастрит.
УЗИ: 1-норма;2-изменения в поджелудочной железе; 3-измнения в печени;4-изменения в желчном пузыре. Диагноз: 1-Язвенная болезнь, 2-панкреатит, 3-ЖКБ
Показатели биохимического анализа крови глюкоза и амилаза указаны, в ммоль/л. Показатели общий билирубин, мочевин и креатинин указаны в мкмоль/л. Общий белок приведен в г/л.
Входные признаки также были оценены с помощью корреляционного анализа. Для этого воспользовались программным продуктом Statistica 5.0
Для данных использовались следующие коэффициенты корреляции: ρ – коэффициент ранговой корреляции Спирмена; τ – коэффициент ранговой корреляции Кендалла;
γ – коэффициент ранговой корреляции Гудмена – Краскела.
Результаты корреляционного анализа на основе этих коэффициентов приведены на рис. 1,2 и 3.
235
Как видно из рисунков наиболее значимыми показателями являются: результат УЗИ – исследования, уровень лейкоцитов в крови, удельный вес и слизь в моче и уровень мочевины. Корреляционный анализ проведенный при помощи γ - коэффициента ранговой корреляции Гудмена – Краскела указывает на значительное влияние солей в моче, что не показывают результаты анализа на основе коэффициентов Спирмена и Кендалла.
Рис. 1. Корреляция с помощью коэффициента Спирмена
Рис. 2. Корреляция с помощью коэффициента Кендалла
236
Рис. 3. Корреляция с помощью коэффициента Гудмена – Краскела
Результаты УЗИисследования для всех трех методов являются самым признаком (значение близко к единице). Наименее значимыми показателями являются значение эозинофилов, прозрачность и белок в моче, уровень креатинина, глюкозы и общий белок.
Литература
1.Коровин Е.Н., Сергеева М.А., Стародубцева Л.В. Методы обработки биомедицинской информации. Курск, 2017. 152 с.
2.Данилов Д.В., Коровин Е.Н. Разработка рациональной процедуры принятия решений при коррекции сахарного диабета на основе регрессионного анализа и "дерева решений" // Системный анализ и управление в биомедицинских системах. 2012. Т. 11. № 3. С. 615-618.
ФГБОУ ВО «Воронежский государственный технический университет»
УДК 681.3
В.Н. Коровин, Е.А. Назаренко, Е.В. Платонова
ОПТИМИЗАЦИЯ ТРАНСПОРТНОЙ ЛОГИСТИКИ СЕТЕВОЙ АПТЕКИ НА ОСНОВЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ
При закупке нового лекарства возможность быстро его развести приведет не только к повышению прибыли, но и престижа аптечной сети. Кроме этого снизится стоимость и время перевозок, что особенно актуально в крупных ме-
237
гаполисах с многокилометровыми пробками. Интуитивно построить маршрут из большого количества промежуточных остановок достаточно затруднительно, потому что следует учитывать большое количество влияющих факторов - расстояния, пробок, разворотов, одностороннего движения, путей объезда и т.д.
Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные пункты (например, аптеки) с определенным товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.
Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):
1.Построение матрицы с исходными данными.
2.Нахождение минимума по строкам.
3.Редукция строк.
4.Нахождение минимума по столбцам.
5.Редукция столбцов.
6.Вычисление оценок нулевых клеток.
7.Редукция матрицы.
8.Если полный путь еще не найден, переходим к пункту 2, если найден к пункту.9
9.Вычисление итоговой длины пути и построение маршрута.
Сведения об аптеках "Максавит" можно найти на одноименном сайте. Наглядно на карте данную информацию можно увидеть на рис. 1.
Рис. 1. Аптеки «Максавит» на карте Воронежа
Адреса данных аптек: 1. ул. Минская, д.1, пом.4
238
2.ул. Невского, д.49
3.ул. Южно-Моравская, д.54
4.б-р. Пионеров, д.27
5.пр-т. Московский, д.24
6.пр-т. Ленинский, д.131
7.ул. Моисеева, д.1
8.ул. Сибиряков, д.69
9.ул. Моисеева, д.82
10.пр-т. Московский, д.114
11.ул. Лизюкова д.16
12.ул. Лизюкова, д.56
13.ул. Комарова, д.2
14.ул. Южно-Моравская, д.26
15.ул. 20 лет Октября, д.40
16.б-р Победы д.24 пом. 2
Найдем расстояния между соответствующими аптеками с помощью сервиса Яндекс.Карты (рис. 2).
Рис. 2. Поиск расстояний с помощью Яндекс.Карты
Данные занесем в таблицу. Логично, что расстояние из пункта i в пункт j может отличаться от расстояния между пунктом j и пунктом i, так как возможны развороты, объезды, одностороннее движение, более рациональный с точки зрения времени маршрут и т.п. В клетки матрицы, расположенные по диагонали занесем величину М, обозначающую бесконечность. Это сделано для того, чтобы исключить маршруты из первой аптеки в первую и т.д., так как они являются бессмысленными. В таблице для удобства поменяем аптеки на номера из списка, представленного выше.
239