Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями
В статье предложен метод решения задач линейного программирования, базирующийся на эволюционной парадигме. Исследован алгоритм его реализации, в основе которого находится полное пространство поиска возможных решений. Рассмотрены аспекты программной реализации метода. Выполнена экспериментальная...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/59939 |
| 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: | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями / О.В. Егорова, В.Е. Снитюк // Штучний інтелект. — 2011. — № 3. — С. 349-354. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859682114161606656 |
|---|---|
| author | Егорова, О.В. Снитюк, В.Е. |
| author_facet | Егорова, О.В. Снитюк, В.Е. |
| citation_txt | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями / О.В. Егорова, В.Е. Снитюк // Штучний інтелект. — 2011. — № 3. — С. 349-354. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | В статье предложен метод решения задач линейного программирования, базирующийся на эволюционной парадигме. Исследован алгоритм его реализации, в основе которого находится полное пространство поиска
возможных решений. Рассмотрены аспекты программной реализации метода. Выполнена экспериментальная
верификация и сравнительный анализ с результатами применения генетических алгоритмов.
У статті запропонований метод розв’язання задач лінійного програмування на основі еволюційної парадигми. Досліджено алгоритм його реалізації на основі повного простору пошуку можливих рішень. Розглянуто аспекти програмної реалізації методу. Виконана експериментальна верифікація та наведені результати порівняльного аналізу з генетичними алгоритмами.
In this paper the problem decision method for linear programming on the basis of evolutionary paradigm is offered. Its realization algorithm is investigational on the basis of complete space search of possible decisions. The aspects of method software realization are considered. Experimental verification and comparative analysis the results are executed.
|
| first_indexed | 2025-11-30T20:27:10Z |
| format | Article |
| fulltext |
«Штучний інтелект» 3’2011 349
5Е
УДК 004.89:004.93
О.В. Егорова, В.Е. Снитюк
Черкасский государственный технологический университет, г. Черкассы, Украина
yegorovaov@gmail.com, snytyuk@gmail.com
Применение технологии композиционного
преодоления неопределенности к решению
задач с ограничениями
В статье предложен метод решения задач линейного программирования, базирующийся на эволюционной
парадигме. Исследован алгоритм его реализации, в основе которого находится полное пространство поиска
возможных решений. Рассмотрены аспекты программной реализации метода. Выполнена экспериментальная
верификация и сравнительный анализ с результатами применения генетических алгоритмов.
Введение
Функционирование сложных производственных, экономических, технических
и социальных систем характеризуется набором определенных факторов, параметров
и оценивается множеством критериев. Как факторы, так и критерии могут иметь
различную природу, но в подавляющем большинстве случаев (в практических задачах),
количество критериев ограничено, а на значения факторов или их комбинации наложены
определенные ограничения. Математически формализованные задачи оптимизации
процессов функционирования указанных систем составляют класс задач с ограни-
чениями (Constraint Satisfaction Problem) [1].
К классу задач с ограничениями относятся и задачи линейного программирования,
широко применяемые в экономико-математическом моделировании. Использование
таких моделей в экономике позволяет выделить и формально описать наиболее
существенные связи между экономическими объектами, используя высокий уровень
абстракции в силу сложности изучаемых процессов и явлений, индуктивным путем
получить новые знания об объекте исследования. Первоочередными проблемами, для
решения которых целесообразно применять экономико-математическое моделирование
и методы оптимизации, являются: определение номенклатуры продукции (видов услуг),
а также оптимизация объектов производства на определенный перспективный период;
распределение имеющихся материальных и финансовых ресурсов по видам деятель-
ности; определение цены, которая будет обеспечивать оптимальный уровень прибыли;
накопление собственных средств для развития производственной деятельности, опре-
деления потребностей в кредитах, которые могут привлекаться; определение влияния
изменений стоимостных показателей на экономическую эффективность предприятия и т.д.
Однако решения таких задач является сложным нетривиальным процессом, который
требует разработки эффективных методов поиска решений с использованием компью-
терной техники, новых идей, принципов, моделей и методов.
В последние годы в области эволюционных вычислений новые методы появляются
из идеи комбинированного использования технологий Soft Computing [2]. Одним из
таких методов является технология композиционного преодоления неопределенности [2],
которая позволяет осуществлять целенаправленную оптимизацию, учитывающую
субъективные предпочтения исследователя и интегрирующая в себе элементы
теории вероятностей, теории нечетких множеств и эволюционных стратегий.
Егорова О.В., Снитюк В.Е.
«Искусственный интеллект» 3’2011 350
5Е
Целью настоящей работы является адаптация технологии композиционного
преодоления неопределенности к решению задач линейного программирования на
основе использования штрафных функций, определение особенностей ее применения,
преимуществ и недостатков, а также выполнение сравнительного анализа результатов,
полученных с использованием эволюционных методов.
Постановка задачи
Задачи с ограничениями заключаются в поиске:
nXxoptXfy , (1)
при ограничениях
,,,,
1
M
m m
m
cc CсCсsrc
(2)
где nxxX ,...,1 – множество переменных, принадлежащих пространству
nX ; xf – целевая функция; m
c Xr – произвольное m -арное отношение на x ;
mn
c XXs : – функция для проектирования вектора n
n XxxX ,...,1 на некоторые
из m его компонент [1].
Классифицируют задачи с ограничениями, как правило, по свойствам входной
информации (детерминированные, стохастические); по характеру описываемых явлений
(динамические, статистические); типу переменных (зависимые, независимые; дискрет-
ные, непрерывные; детерминированные, случайные); типу ограничений (унарные,
бинарные, высших порядков; линейные, нелинейные; абсолютные, приоритетные).
Задачи линейного программирования формулируются так:
nXxoptXfy ,)( (3)
при ограничениях
,0,,...,0,0 ppiXgi (4)
,0,,...,1,0 pmmpiXhi (5)
где .FSx Множество nXS определяет пространство поиска, а множество
nXF – допустимое пространство поиска, добавленное ограничениями. Пространство
поиска S является -n мерным прямоугольником в nX (область определения перемен-
ных определена верхними и нижними границами):
.1),()( niiuxil i
Основные направления решения задачи
Поскольку необходимо найти глобальные оптимумы целевой функции в много-
мерном пространстве независимых переменных, целесообразно применить эволюци-
онные методы. Их использование, в отличие от традиционных методов, не зависит от
выбора начальной точки и не требует выполнения дополнительных условий на
характеристики целевой функции. Выбор метода эволюционного моделирования
является прерогативой исследователя.
Для обработки ограничений с целью изъятия неперспективных решений в
генетических алгоритмах применяются штрафные функции:
, , ,
, ,
f X если X F S
eval X
f X penalty X в противном случае
Применение технологии композиционного преодоления неопределенности...
«Штучний інтелект» 3’2011 351
5Е
где штраф Xpenalty равен нулю, если ограничение выполняется, в противном
случае штраф имеет определенное значение. Существует несколько подобных
методов, в большинстве из них множество функций mjf j 1
используется для
генерации штрафов; функция jf оценивает штраф, который будет наложен на j -е
ограничение, по формуле:
.1,
1,,0max
mjqякщоXh
qjякщоXg
Xf
j
j
j
Конечно, методы отличаются некоторыми важными деталями, в частности, построением
штрафных функций и изъятием неперспективных решений. Рассмотрим два из них.
Первый метод, предложенный A. Homaifar, S.H.-Y. Lai, X. Qi [3], предусматривает,
что для каждого ограничения формируется множество интервалов, которые определяют
соответствующие штрафные коэффициенты. Метод представлен таким алгоритмом:
Шаг 1. Для каждого ограничения сформировать несколько l штрафных уровней.
Шаг 2. Для каждого штрафного уровня и каждого ограничения сгенерировать
штрафные коэффициенты mjliRij ,...,2,1,,...,2,1 , причем наивысшему штрафному
уровню должно соответствовать наибольшее значение коэффициента.
Шаг 3. Определить выборочную совокупность возможных решений.
Шаг 4. Вычислить значение функции, оптимумы которой ищут, в точках
выборочной совокупности по формуле:
.
1
2
m
j jij XfRXfXeval
Недостаток метода заключается в том, то он зависит от большего числа
параметров. Так, для m ограничений метод требует: m параметров для генерации
числа интервалов для каждого ограничения – границ интервалов, l параметров для
каждого ограничения – штрафных коэффициентов .ijR Таким образом, в общем случае
метод требует 12 lm параметров для управления m ограничениями.
Авторы второго метода J.A. Joines и C.R. Houk [4], аналогично предыдущему
методу, предлагают использовать динамические штрафы. Индивиды вычисляются
(на итерации t ) c использованием формулы:
,
1
m
j j XftCXfXeval
где ,C и константы. Целесообразно принять такие значения этих параметров:
,5,0C .2 Этот метод содержит намного меньше параметров, чем предыдущий.
Воспользуемся приведенными штрафными функциями в технологии компози-
ционного преодоления неопределенности [2], которая определена таким алгоритмом
(процедура Evomax):
Шаг 1. 1.i
Шаг 2. Определить совокупность возможных решений и определить
процентное соотношение количества индивидов на следующем шаге.
Шаг 3. Пока условия завершения работы алгоритма не выполнены {
Шаг 3.1. 1.i i
Шаг 3.2. Вычислить значение функции .
Егорова О.В., Снитюк В.Е.
«Искусственный интеллект» 3’2011 352
5Е
Шаг 3.3. Построить функцию принадлежности .
Шаг 3.4. Определить множество точек ix , которые принадлежат множеству
среза и для которых выполняется неравенство *.i jx x
Шаг 3.5. Генерировать последовательности jiz для каждой точки с
множества .ix
Шаг 3.6. Мутация .j
iz
}
Приведенный метод позволяет осуществлять целенаправленную оптимиза-
цию, учитывая цели и задачи исследования, поскольку в нем в значительной степени
преодолены такие недостатки технологий Soft Computing, как: зависимость точности
решений от дискретности их представления и заданной точности будущего результата
(как в генетических алгоритмах); использование исключительно равномерного и (или)
нормального распределения, что значительно увеличивает время решения задачи
(как в эволюционных стратегиях); зависимость сходимости от качества популяции.
Результаты экспериментов
Рассмотрим пример. Фабрика производит изделия четырех наименований: печенье,
пряники, сухари и бублики. Для изготовления продукции используется сахар, расти-
тельное масло, пшеничная мука, маргарин, изюм.
Интенсивность потребления каждого ингредиента на тонну изделия соответству-
ющего наименования и прибыль от реализации единицы веса заданы в табл. 1.
Необходимо определить оптимальный объем производства продукции каждого наимено-
вания (на фабрике есть 20 т сахара, 24 т растительного масла, 30 т муки, 0,8 т
маргарина, 0,6 т изюма), при котором прибыль будет максимальной.
Таблица 1 – Интенсивность потребления ингредиентов и прибыль
Ингредиенты
Изделие
Сахар Раститель
ное масло Мука Марга-
рин Изюм Прибыль,
тыс. грн
Печенье 0,15 0,2 0,6 0,03 0,02 1
Пряники 0,4 0,1 0,8 – – 1,2
Сухари 0,3 0,2 0,5 – 0,05 0,8
Бублики 0,2 0,2 0,4 – – 1
Рыночный спрос на печенье, пряники, сухари и бублики составляет 5, 6, 3 и 4 т
соответственно.
Математическая модель задачи. Пусть 3,1,0 ixi – количество изделий
-i го наименования, тогда экономико-математическая модель задачи выглядит так:
1 2 3 40,15 0,4 0,3 0,2 20,x x x x
1 2 3 40,2 0,1 0,2 0,2 24,x x x x
1 2 3 40,6 0,8 0,5 0,4 30,x x x x
10,03 0,8,x
Применение технологии композиционного преодоления неопределенности...
«Штучний інтелект» 3’2011 353
5Е
1 30,02 0,05 0,6,x x
10 5,x
20 6,x
30 3,x
40 4,x
1 2 3 41,2 0,8 max.f x x x x
Для исследования, целью которого было выяснение эффективности технологии
композиционного преодоления неопределенности при решении задач линейного
программирования, выполнено фиксированное число запусков алгоритма. При этом
начальная популяция состояла из 50 индивидов, максимальное число возможных
итераций – 300, вероятность мутации – 1%, среднеквадратическое отклонение – 1,
точность решения – 10-4.
Таблица 2 – Результаты экспериментов
Название критерия
Генетический
алгоритм
Композиционный
метод
Метод 1 Метод 2 Метод 1 Метод 2
Критерий
максимума
функции
b
m
w
t
16,767
9,5754
13,157
16,6
21,618
12,871
17,869
35,124
18,6
12,655
15,128
4,46
18,6
12,428
15,395
6,096
Критерий
среднего
значения функции
b
m
w
t
- -
18,6
12,63
14,769
107,109
18,6
12,883
15,691
46,561
Критерий
максимального
количества
итераций
b
m
w
t
21,606
12,820
16,968
88,45
18,059
9,17
13,625
86,53
18,6
12,785
15,664
6,46
18,6
12,427
15,07
6,26
Все критерии
b
m
w
t
21,679
12,707
17,079
50,21
21,646
12,758
17,879
79,42
18,6
12,509
14,72
3,42
18,6
12,594
15,603
2,43
Результаты экспериментов для каждого метода (1, 2) поданы в табл. 2, где
показано наилучшее (b), среднее (m) и наихудшее (w) значение целевой функции, а
также время расчета (t). Эксперименты проводились с использованием трех типов
критериев. Согласно первому критерию итерации прекращались, когда максимальные
значения целевой функции на соседних итерациях незначительно отличались. По второму
критерию сравнивались средние значения целевой функции на разных итерациях.
Вычисления прекращались после определенного количества итераций – по третьему
критерию. Использовался также интегральный критерий: вычисления прекращались,
если выполнялся хотя бы один критерий из предложенных выше.
Выводы, которые можно сделать по результатам моделирования, являются неодно-
значными. В частности, согласно критерию среднего значения функции, используя
генетический алгоритм, не удалось получить результат за приемлемое время. Лучшие
Егорова О.В., Снитюк В.Е.
«Искусственный интеллект» 3’2011 354
5Е
результаты были получены в случае применения критерия максимального количества
итераций. Причиной этого является полиэкстремальный характер целевой функции
и, как следствие, частое попадание в локальные экстремумы.
Выводы
Предложенный метод позволяет решать задачи линейного программирования,
учитывая особенности ограничений. Еще одним его преимуществом является время
решения задачи. Как следует из табл. 2, значение времени, необходимое для расчета
разработанным методом, на порядок меньше времени работы генетического
алгоритма. Результаты работы двух методов являются сравнимыми.
Следует заметить, что технология композиционного преодоления неопределен-
ности является параметрическим методом. Его использование для решения указанной
задачи осуществлено без оптимизации параметров. Применение метода для решения
тестовых оптимизационных задач показало, что оптимизация параметров метода
приводит к увеличению точности результата до 30% и скорости сходимости до 24%.
Поэтому параметрическая оптимизация предложенного метода является еще одним
перспективным способом повышения эффективности процессов решения задач с
ограничениями, тем более что для эволюционных методов эта проблема актуальна.
Литература
1. Рассел С. Искусственный интеллект: Современный подход / С. Рассел, П. Норвиг. – М. : Вильямс,
2005. – 1424 с.
2. Снитюк В.Е. Композиционное преодоление неопределенности в задачах нелинейной многофактор-
ной оптимизации / В.Е. Снитюк // Искусственный интеллект. – 2004. – № 4. – С. 207-210.
3. Homaifar A. Constrained optimization via genetic algorithms / A. Homaifar, S.H.-Y. Lai, X. Qi // Simulation. –
1994. – Vol. 62, № 4. – P. 242-254.
4. Joines J.A. On the use of non-stationary Penalty functions to solve nonlinear constrained optimization
problems with Gas / J.A. Joines and C.R. Houk // Proceedings of the IEEE ICEC. – 1994. – P. 579-584.
5. Michalewicz Zbigniew. Genetic algorithms, numerical optimization, and constraints / Zbigniew Michalewicz //
Commun, ACM 39 (12es). – 1996. – P. 175-201.
Literatura
1. Rassel S. Iskusstvennyj intellekt: Sovremennyj podhod. M.: Vil'jams. 2005. 1424 s.
2. Snitjuk V.E. Iskusstvennyj intellekt. № 4. 2004. S. 207-210.
3. Homaifar A. Simulation. Vol. 62. № 4. 1994. S. 242-254.
4. Joines J.A. Proceedings of the IEEE ICEC. 1994. P. 579-584.
5. Michalewicz Zbigniew. Commun, ACM 39 (12es). 1996. P. 175-201.
О.В. Єгорова, В.Є. Снитюк
Аспекти застосування методу композиційного подолання невизначеності в задачах з обмеженнями
У статті запропонований метод розв’язання задач лінійного програмування на основі еволюційної
парадигми. Досліджено алгоритм його реалізації на основі повного простору пошуку можливих рішень.
Розглянуто аспекти програмної реалізації методу. Виконана експериментальна верифікація та наведені
результати порівняльного аналізу з генетичними алгоритмами.
O.V. Yegorova, V.E. Snytyuk
Application of the Uncertainty Composition Overcoming Technology to Solving Problems with Constraints
In this paper the problem decision method for linear programming on the basis of evolutionary paradigm is
offered. Its realization algorithm is investigational on the basis of complete space search of possible decisions.
The aspects of method software realization are considered. Experimental verification and comparative analysis
the results are executed.
Статья поступила в редакцию 22.06.2011.
|
| id | nasplib_isofts_kiev_ua-123456789-59939 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-30T20:27:10Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Егорова, О.В. Снитюк, В.Е. 2014-04-10T16:47:47Z 2014-04-10T16:47:47Z 2011 Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями / О.В. Егорова, В.Е. Снитюк // Штучний інтелект. — 2011. — № 3. — С. 349-354. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/59939 004.89:004.93 В статье предложен метод решения задач линейного программирования, базирующийся на эволюционной парадигме. Исследован алгоритм его реализации, в основе которого находится полное пространство поиска возможных решений. Рассмотрены аспекты программной реализации метода. Выполнена экспериментальная верификация и сравнительный анализ с результатами применения генетических алгоритмов. У статті запропонований метод розв’язання задач лінійного програмування на основі еволюційної парадигми. Досліджено алгоритм його реалізації на основі повного простору пошуку можливих рішень. Розглянуто аспекти програмної реалізації методу. Виконана експериментальна верифікація та наведені результати порівняльного аналізу з генетичними алгоритмами. In this paper the problem decision method for linear programming on the basis of evolutionary paradigm is offered. Its realization algorithm is investigational on the basis of complete space search of possible decisions. The aspects of method software realization are considered. Experimental verification and comparative analysis the results are executed. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные системы планирования, управления, моделирования и принятия решений Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями Аспекти застосування методу композиційного подолання невизначеності в задачах з обмеженнями Application of the Uncertainty Composition Overcoming Technology to Solving Problems with Constraints Article published earlier |
| spellingShingle | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями Егорова, О.В. Снитюк, В.Е. Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| title | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями |
| title_alt | Аспекти застосування методу композиційного подолання невизначеності в задачах з обмеженнями Application of the Uncertainty Composition Overcoming Technology to Solving Problems with Constraints |
| title_full | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями |
| title_fullStr | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями |
| title_full_unstemmed | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями |
| title_short | Применение технологии композиционного преодоления неопределенности к решению задач с ограничениями |
| title_sort | применение технологии композиционного преодоления неопределенности к решению задач с ограничениями |
| topic | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| topic_facet | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/59939 |
| work_keys_str_mv | AT egorovaov primenenietehnologiikompozicionnogopreodoleniâneopredelennostikrešeniûzadačsograničeniâmi AT snitûkve primenenietehnologiikompozicionnogopreodoleniâneopredelennostikrešeniûzadačsograničeniâmi AT egorovaov aspektizastosuvannâmetodukompozicíinogopodolannâneviznačenostívzadačahzobmežennâmi AT snitûkve aspektizastosuvannâmetodukompozicíinogopodolannâneviznačenostívzadačahzobmežennâmi AT egorovaov applicationoftheuncertaintycompositionovercomingtechnologytosolvingproblemswithconstraints AT snitûkve applicationoftheuncertaintycompositionovercomingtechnologytosolvingproblemswithconstraints |