Формализация задачи комплектования и эволюционные аспекты ее решения
В статье рассмотрена технология решения задачи комплектования аварийно-спасательной техники с
 использованием многокритериальной оптимизации, последовательного анализа вариантов и эволюционного
 моделирования. Разработаны модели, служащие информационно-аналитическим базисом формирова...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/8172 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Формализация задачи комплектования и эволюционные аспекты ее решения / П. Кучер, В. Снитюк // Штучний інтелект. — 2009. — № 4. — С. 268-273. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860190077080043520 |
|---|---|
| author | Кучер, П. Снитюк, В. |
| author_facet | Кучер, П. Снитюк, В. |
| citation_txt | Формализация задачи комплектования и эволюционные аспекты ее решения / П. Кучер, В. Снитюк // Штучний інтелект. — 2009. — № 4. — С. 268-273. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| description | В статье рассмотрена технология решения задачи комплектования аварийно-спасательной техники с
использованием многокритериальной оптимизации, последовательного анализа вариантов и эволюционного
моделирования. Разработаны модели, служащие информационно-аналитическим базисом формирования
интегрального критерия.
У статті розглянута технологія розв’язання задачі комплектування аварійно-рятувальної техніки з
використанням багатокритеріальної оптимізації, послідовного аналізу варіантів та еволюційного моделювання.
Розроблені моделі, які є інформаційно-аналітичним базисом формування інтегрального критерію.
In this paper the problem decision technology of a rescue technics acquisition with use multiobjective
optimization, the consecutive analysis of variants and evolutionary modelling is considered. The models
which are information-analytical basis for forming of integrated criterion are developed.
|
| first_indexed | 2025-12-07T18:05:24Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 4’2009 268
5К
УДК 004.89:614.841.4
П. Кучер, В. Снитюк
Академия пожарной безопасности имени Героев Чернобыля, г. Черкассы, Украина
Черкасcкий государственный технологический университет, г. Черкассы, Украина
kucherpp@ukr.net, snytyuk@gmail.com
Формализация задачи комплектования
и эволюционные аспекты ее решения
В статье рассмотрена технология решения задачи комплектования аварийно-спасательной техники с
использованием многокритериальной оптимизации, последовательного анализа вариантов и эволюционного
моделирования. Разработаны модели, служащие информационно-аналитическим базисом формирования
интегрального критерия.
Описание предметной области
Современные аспекты функционирования служб МЧС Украины следуют из необ-
ходимости решения ряда задач в критических условиях и условиях неопределенности.
Актуальность задачи комплектации аварийно-спасательной техники (КАСТ) определя-
ется динамикой роста ситуаций, в которых необходимым является ее использование, а
также увеличением техногенной нагруженности окружающей среды. На практике ре-
шение задачи КАСТ принимается ответственным лицом исходя из собственного опыта,
следствием чего при выполнении аварийно-спасательных работ зачастую является от-
сутствие необходимого инструментария вообще или невозможность выполнения задания
в полном объеме.
Задача КАСТ является логическим продолжением ряда задач, решение и автома-
тизация решения которых является необходимым условием эффективного функциони-
рования служб спасения, и решаемых ранее с использованием технологий Soft
Computing. К ним относятся, в частности, задача определения оптимального маршрута
следования пожарного расчета к месту пожара с оптимизированным пространством по-
иска [1], пути и времени распространения огня к особо опасному объекту [2].
Современное состояние в рассматриваемой области характеризуется значительно
расширенным ассортиментом противопожарной и спасательной продукции, снятием
ограничений на импорт зарубежных образцов, но существованием определенного де-
фицита финансовых ресурсов. Нельзя также не обратить внимание на необходимость
обеспечения широкой функциональности и максимальной мощности оборудования.
Очевидно, что задача КАСТ имеет много общего с известной задачей упаковки в
контейнеры [3]. Задача упаковки в контейнеры заключается в размещении объектов
предопределенной формы таким образом, чтобы число использованных контейнеров
было наименьшим или объем объектов был наибольшим. В задаче КАСТ целевая
функция задачи об упаковке преобразовывается в ограничения на габаритные размеры
элементов. Целевыми функциями являются функциональность, мощность, стоимость,
другие характеристики элементов АСТ. Поэтому первоочередной задачей является
формирование интегрального критерия и представление потенциальных решений задачи.
Аспекты ее решения предложены ниже.
Формализация задачи комплектования и эволюционные аспекты ее решения
«Штучний інтелект» 4’2009 269
5К
Постановка задачи
Пусть множество 1 2{ , ,..., }nX X X X представляет ассортимент аварийно-
спасательной техники. Каждый элемент множества X принадлежит к одному из
классов множества 1 2{ , ,..., }kC C C C , где .k n Предположим, что в комплект
должно входить оборудование из каждого из 1 2{ , ,..., }mC C C классов, ,m k т.е.
1 2 1 21
1 1 1
1{ , ,..., } ,...,{ , ,..., } .
j jm
m m m
i i i i i i mX X X C X X X C Каждому элементу множества X поста-
вим в соответствие совокупность значений:
1 2 3, , , , , ,
q q qq q q qX F F F a b c (1)
где 1q
F − значение функциональности q -го элемента; 2q
F − значение его производи-
тельности (мощности); 3q
F − цена элемента; , ,q q qa b c − его габаритные размеры, 1, .q n
Сделаем упрощающие замечания. Пусть все элементы имеют форму прямоуголь-
ного параллелепипеда и они должны быть размещены в прямоугольном контейнере.
Кроме того, в контейнере должны быть по одному элементу из каждого класса.
Задача КАСТ сводится к задаче многокритериальной оптимизации:
1 2 3( ) max, ( ) max, ( ) min,F x F x F x (2)
где
1 2
1 2( , ,.., ),
l l l lm j
m j
i i i i jx x x x x C при ограничениях:
1 1min 2 2min 3 3max( ) , ( ) , ( ) , ( ) 0, 1,3,
l l lj j j
jj j j j j
i i i iF x F F x F F x F F i (3)
0 ( ) max{ , , }, 0 ( ) max{ , , }, 0 ( ) max{ , , },
l l lj j j
j j j
q i q i q ia x a b c b x a b c c x a b c (4)
где ( ), ( ), ( )
l l lj j j
j j j
q i q i q ia x b x c x − габаритные размеры элемента АСТ, , ,a b c − габаритные
размеры контейнера.
Задача (2)-(4) может быть сведена к задаче дискретного сепарабельного про-
граммирования [4]:
найти
1
max ( ) ( ),
N
i i
i
F x F x
при ограничениях:
*
1
( ) ( ) , 1, ,
N
p p i p
i
g x g x g p q
*
1
( ) ( ) , 1, ,
N
p p i p
i
g x g x g p q Q
где ( )i iF x , ( )p ig x − функции дискретного аргумента, заданные таблично.
Известно, что задачи такого рода относят к NP-полным. Но очевидно, что в
постановке (2)-(4) могут быть сделаны предположения, упрощающие процесс ее ре-
шения. Нам представляется рациональным использовать идеи решения задач много-
критериальной оптимизации [5], [6], метода последовательного анализа вариантов [4], [7]
и эволюционного моделирования [8].
Информационно-аналитические модели
В основе эффективного решения задачи (2)-(4) лежат такие предпосылки:
1. Формирование комплекса моделей, которые позволят осуществить идентифика-
цию критериальных функций.
Кучер П., Снитюк В.
«Искусственный интеллект» 4’2009 270
5К
2. Разработка интегрального критерия, получение значений которого позволит
установить предпочтения на множестве вариантов.
Рассмотрим задачу формирования комплекса моделей, которые составляют
информационно-аналитический базис исследования. Известно, что при создании
сложных систем традиционно [9] используют модели строения, функционирования и
развития.
В нашем случае модель строения имеет вид:
1 2, ,..., ,s nM X X X (5)
где n − количество элементов АСТ. Модель строения является базисом, который предна-
значен для формирования множества элементов и структуры при комплектовании АСТ.
Модель функционирования
1 2, ,..., ,f nM G G G (6)
где , 1, ,iG i n − преобразование, которое реализуется i -м элементом, причем
( , , ),i i i i i iY G I R P Y − некоторая характеристика, которая определяется преобразованием
iG и указывающая на его результат, iI − априорная информация о типах аварийных
ситуаций, их масштабах и возможных последствиях, iR − материальные и энергетиче-
ские ресурсы, необходимые для функционирования элемента iX и получения значения
iY , iP − особенности процесса преобразования , , 1, .i i iI R Y i n
Третью модель − модель развития – представим, используя принадлежность
элементов классам
1 2 1 21
1 1 1( , ,..., ),..., ( , ,..., )
j jm
m m m
d i i i i i iM X X X X X X , (7)
где m − количество классов элементов АСТ, выполняющих подобные функции. В пре-
делах каждой совокупности элементы могут быть упорядочены по уровню функ-
циональности, мощности и по стоимости. Возможны также варианты упорядочения по
значению габаритов.
Предложенные модели образуют базис для формирования критериев, которые
будут использованы при принятии решений по выбору оптимального варианта ком-
плектации АСТ в условиях ресурсного дефицита.
Особенности построения интегральной целевой функции
Задача комплектования АСТ имеет особенности, к которым относятся много-
критериальность, разноразмерность значений критериальных функций, слабострук-
турированность. Рассмотрим аспекты формирования интегрального критерия (целевой
функции), исходя из известных методов решения задач многокритериальной
оптимизации [10]. Заметим, что функции (2) могут как задаваться таблично, так и
иметь вид аналитических зависимостей.
1. Метод главного критерия. Предположим, что главным критерием является
стоимость элемента АСТ. Тогда задача (2)-(4) преобразуется к такому виду:
1 2
1 2
3( ) min, ( , ,.., ), ,
l l l lm j
m m
i i i i jF x x x x x x C (8)
min, { / ( ), 1,2}i ix D D x F F x i (9)
Формализация задачи комплектования и эволюционные аспекты ее решения
«Штучний інтелект» 4’2009 271
5К
и выполнено (4). В задаче (8), (9) min , 1,2,jF i − минимально возможное значение i -го
критерия. Таким образом, получаем задачу однокритериальной оптимизации. Ее реше-
ние в случае известных значений 1 2 3, ,F F F для всех элементов сводится к поиску
*
1 3max ( ),
x D
x F x
(10)
где D − область, в которой выполняются ограничения (3) и (4). Если *
1x D , то решение
найдено, если нет – ищем
*
1
*
2 3max ( )
x D
x x
x F x
и т.д. (11)
Если
'
* * *
3: max ( ) , ,i i ix D
x x F x x D
то задача имеет решение, в противном случае −
решения нет.
2. Метод линейной свертки. Необходимыми условиями реализации метода
являются:
− нормализация значений критериальных функций;
− определение весовых коэффициентов критериев.
Тогда интегральный критерий будет таким:
1 1 2 2 3 3( ) ( ) ( ) ( ) max,F x F x F x F x (12)
где
3
1
0, 1,3, 1.i i
i
i
Если известны значения критериальных функций и инте-
грального критерия на множестве контрольных точек (элементах АСТ), то коэффи-
циенты 1 2 3, , могут быть рассчитаны, например, по методу наименьших квадратов.
Однако это не всегда возможно, тем более, что, скорее всего, в массиве начальных
данных будет иметь место мультиколлинеарность факторов и результат будет смещен-
ным. В других случаях необходимо использовать техники обработки экспертных оценок.
3. Метод идеальной точки. Идеальной называется такая точка * * *
1 2 3( , , )x x x , что
* max ( ), 1,3.i ix D
x F x i
Решив задачи однокритериальной оптимизации, идеальная точка
будет найдена. Тогда дальнейшее решение заключается в поиске такой точки:
13
* * 2 2
1
min( ( ( ) ) ) .i ix D i
x Arg F x x
(13)
Значения критериальных функций должны быть нормированы и если критериальные
функции имеют весовые коэффициенты, то задачу (13) перепишем в виде:
13
* * 2 2
1
min( ( ( ) ) ) ,i i ix D i
x Arg F x x
(14)
где
3
1
0, 1,3, 1.i i
i
i
Существуют и другие методы решения задач многокритериальной оптимизации, та-
кие как выбор по количеству доминирующих критериев, метод последовательных
уступок, последовательного ввода ограничений и т.д., но все они требуют привлече-
ния дополнительной информации, которой может и не быть. Потому для решения
нашей задачи мы остановились на вышеприведенных трех методах.
Кучер П., Снитюк В.
«Искусственный интеллект» 4’2009 272
5К
Предварительные шаги, сокращающие количество
вариантов решения задачи
1. Удаление возможных вариантов решения задачи, которые строго доминируются
хотя бы одним из других вариантов. Заметим, что такая операция может быть выполнена
в начале реализации поиска решения задачи, если мощность множества вариантов срав-
нительно небольшая. Если это не так, то проверка на доминирование осуществляется в
процессе решения задачи для каждого элемента отдельно.
2. Необходимо осуществить предварительную проверку, не существует ли та-
кого элемента АСТ, что
( max{ , , }) ( max{ , , }) ( max{ , , })q q qa a b c b a b c c a b c ; (15)
не существует ли такого набора элементов АСТ, что
3 3 3
1 1 1
( max{ , , }) ( max{ , , }) ( max{ , , }).q q q
q q q
a a b c b a b c c a b c
(16)
Если элементы или наборы элементов, удовлетворяющие (15) или (16), соответст-
венно, существуют, то их необходимо удалить a priori или в процессе решения задачи.
Аналогично, используя схему последовательного анализа вариантов, удаляем варианты,
общая функциональность или мощность которых меньше минимально возможной, а
также те, стоимость которых превышает допустимую величину.
Основные направления решения задачи
Поскольку необходимо найти оптимум функции, заданной таблично, при
указанных ограничениях, и о свойствах которой ничего не известно, то нам пред-
ставляется рациональным применение эволюционного моделирования. Выбор метода
эволюционного моделирования является прерогативой исследователя.
Предположим, что мы используем генетический алгоритм [11]. Известно, что
его реализацию сопровождают две проблемы: формирование целевой функции и
представление потенциальных решений в виде бинарных хромосом. В нашей задаче
целевая функция уже получена. Для формирования хромосом-решений предложим
такой подход. Поскольку решение является набором из m элементов, то и длина хро-
мосомы будет m . Каждая ее позиция отвечает одному элементу АСТ. Все эле-
менты хромосомы принадлежат одному классу.
Каждый элемент имеет 3 фрагмента. Первый соответствует значению функцио-
нальности, второй – мощности, а третий – стоимости. Таким образом, хромосома-
решение будет иметь 3m фрагментов. На начальном этапе все значения характеристик
элементов были нормированы, их значения находятся в отрезке [0,1]. Далее приме-
няются все известные процедуры генетического алгоритма. Заметим, что полученное
решение может не соответствовать ни одному потенциальному варианту. Тогда
необходимо найти ближайшее к нему решение по критерию минимума среднеквадра-
тического расстояния. Применение генетического алгоритма предпочтительно в том
случае, когда известны значения частных критериальных функций. Для решения задачи
также рациональным является применение эволюционных стратегий [12].
Формализация задачи комплектования и эволюционные аспекты ее решения
«Штучний інтелект» 4’2009 273
5К
Выводы
Рассмотренная задача комплектования аварийно-спасательной техники является
сложной многокритериальной задачей. Ее сложность зависит от качества элементов АСТ
и носителей, на которые они будут установлены. Новые образцы техники, их эволюция
указывают на необходимость поиска оптимального решения задачи КАСТ. Технология,
которая предлагается в статье, базируется на элементах трех составляющих: много-
критериальной оптимизации, последовательного анализа вариантов, эволюционного мо-
делирования – и объединяет в себе их преимущества. Перспективным является ком-
позиционное использование эволюционного моделирования и последовательного анализа
вариантов. Определение порядка такого использования, оптимизация параметров, ис-
следование точности составляет самостоятельную актуальную научную задачу. В на-
стоящее время проводятся эксперименты по разработке быстродействующих алгоритмов
на основе предложенного подхода. Кроме того, поскольку большинство элементов АСТ
имеют многоцелевое назначение, различные аварийно-спасательные задачи с их помо-
щью могут решаться с разной эффективностью, то задача комплектования с учетом этого
фактора требует применения методов теории нечетких множеств.
Литература
1. Snytyuk V. Evolutionary technique of shorter route determination of fire brigade following to fire place with the
optimized space of search / V. Snytyuk, O. Dghulay // Information Technologies and Knowledge. − 2007. −
Vol. 1, № 4. − P. 325-332.
2. Снитюк В. Эволюционное моделирование процесса распространения пожара / В. Снитюк, А. Биченко //
Proc. XIII-th Int. Conf. [«Knowledge-dialogue-Solution»], (Bulgaria, Varna, June 2007). – P. 247-254.
3. Lodi A. Recent advances on two-dimensional bin packing problems / A. Lodi, S. Martello, D. Vigo // Discrete
Appl. Math. – 2002. − Vol. 123. − P. 379-396.
4. Михалевич В.С. Вычислительные методы исследования и проектирования сложных систем / В.С. Ми-
халевич, В.Л. Волкович. − М. : Наука, 1982. − 286 с.
5. Черноруцкий И.Г. Методы принятия решений / Черноруцкий И.Г. − Санкт-Петербург : BHV, 2005. −
416 с.
6. Волошин О.Ф. Теория принятия решений / О.Ф. Волошин, С.О. Мащенко. − К. : Kиевский университет,
2006. − 304 c.
7. Волкович В.Л. Модели и методы оптимизации надежности сложных систем / В.Л. Волкович, О.Ф. Во-
лошин [и др.]. – Киев : Наукова думка, 1993. − 312 с.
8. Michalewitcz Z. Genetic Algorithms+Data Structures=Evolution Programs / Michalewitcz Z. − Springer Verlag,
Berlin, Heidelberg, New-York, 1996. − 387 p.
9. Тимченко А.А. Основы информатики системного проектирования объектов новой техники / А.А. Тим-
ченко, A.A. Родионов. − К. : Наукова думка, 1991. − 231 с.
10. Ларичев О.И. Теория и методы принятия решений / Ларичев О.И. − Москва : Логос, 2003.
11. Holland J.H. Adaptation in natural and artificial systems. An introductory analysis with application to biology,
control and artificial intelligence / Holland J.H. – London : Bradford book edition, 1994. – 211 p.
12. Rechenberg I. Evolutionsstrategie “94” / Rechenberg I. – Stuttgart-Bad GannStatt : Frommann Halzboog,
1994. − 434 p.
П. Кучер, В. Снитюк
Формалізація задачі комплектування та еволюційні аспекти її розв’язання
У статті розглянута технологія розв’язання задачі комплектування аварійно-рятувальної техніки з
використанням багатокритеріальної оптимізації, послідовного аналізу варіантів та еволюційного моделювання.
Розроблені моделі, які є інформаційно-аналітичним базисом формування інтегрального критерію.
P. Kucher, V. Snytyuk
Formalization of a Acquisition Problem and Evolutionary Aspects of its Solving
In this paper the problem decision technology of a rescue technics acquisition with use multiobjective
optimization, the consecutive analysis of variants and evolutionary modelling is considered. The models
which are information-analytical basis for forming of integrated criterion are developed.
Статья поступила в редакцию 02.06.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-8172 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:05:24Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Кучер, П. Снитюк, В. 2010-05-14T08:40:23Z 2010-05-14T08:40:23Z 2009 Формализация задачи комплектования и эволюционные аспекты ее решения / П. Кучер, В. Снитюк // Штучний інтелект. — 2009. — № 4. — С. 268-273. — Бібліогр.: 12 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8172 004.89:614.841.4 В статье рассмотрена технология решения задачи комплектования аварийно-спасательной техники с
 использованием многокритериальной оптимизации, последовательного анализа вариантов и эволюционного
 моделирования. Разработаны модели, служащие информационно-аналитическим базисом формирования
 интегрального критерия. У статті розглянута технологія розв’язання задачі комплектування аварійно-рятувальної техніки з
 використанням багатокритеріальної оптимізації, послідовного аналізу варіантів та еволюційного моделювання.
 Розроблені моделі, які є інформаційно-аналітичним базисом формування інтегрального критерію. In this paper the problem decision technology of a rescue technics acquisition with use multiobjective
 optimization, the consecutive analysis of variants and evolutionary modelling is considered. The models
 which are information-analytical basis for forming of integrated criterion are developed. ru Інститут проблем штучного інтелекту МОН України та НАН України Интеллектуальные системы автоматизации научных исследований, проектирования и управления Формализация задачи комплектования и эволюционные аспекты ее решения Формалізація задачі комплектування та еволюційні аспекти її розв’язання Formalization of a Acquisition Problem and Evolutionary Aspects of its Solving Article published earlier |
| spellingShingle | Формализация задачи комплектования и эволюционные аспекты ее решения Кучер, П. Снитюк, В. Интеллектуальные системы автоматизации научных исследований, проектирования и управления |
| title | Формализация задачи комплектования и эволюционные аспекты ее решения |
| title_alt | Формалізація задачі комплектування та еволюційні аспекти її розв’язання Formalization of a Acquisition Problem and Evolutionary Aspects of its Solving |
| title_full | Формализация задачи комплектования и эволюционные аспекты ее решения |
| title_fullStr | Формализация задачи комплектования и эволюционные аспекты ее решения |
| title_full_unstemmed | Формализация задачи комплектования и эволюционные аспекты ее решения |
| title_short | Формализация задачи комплектования и эволюционные аспекты ее решения |
| title_sort | формализация задачи комплектования и эволюционные аспекты ее решения |
| topic | Интеллектуальные системы автоматизации научных исследований, проектирования и управления |
| topic_facet | Интеллектуальные системы автоматизации научных исследований, проектирования и управления |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8172 |
| work_keys_str_mv | AT kučerp formalizaciâzadačikomplektovaniâiévolûcionnyeaspektyeerešeniâ AT snitûkv formalizaciâzadačikomplektovaniâiévolûcionnyeaspektyeerešeniâ AT kučerp formalízacíâzadačíkomplektuvannâtaevolûcíiníaspektiíírozvâzannâ AT snitûkv formalízacíâzadačíkomplektuvannâtaevolûcíiníaspektiíírozvâzannâ AT kučerp formalizationofaacquisitionproblemandevolutionaryaspectsofitssolving AT snitûkv formalizationofaacquisitionproblemandevolutionaryaspectsofitssolving |