Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов
На основании квази Ф-функций построена математическая модель задачи плотной упаковки не- ориентированных сфероконусов в кубоиде минимальной высоты. Построенная модель позволила применить для поиска локальных экстремумов метод внутренней точки на последовательности подобластей области допустимых ре...
Збережено в:
| Опубліковано в: : | Искусственный интеллект |
|---|---|
| Дата: | 2014 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/85247 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов / В.В. Сёмкин, А.М. Чугай // Искусственный интеллект. — 2014. — № 1. — С. 74–79. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859878119875280896 |
|---|---|
| author | Сёмкин, В.В. Чугай, А.М. |
| author_facet | Сёмкин, В.В. Чугай, А.М. |
| citation_txt | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов / В.В. Сёмкин, А.М. Чугай // Искусственный интеллект. — 2014. — № 1. — С. 74–79. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Искусственный интеллект |
| description | На основании квази Ф-функций построена математическая модель задачи плотной упаковки не-
ориентированных сфероконусов в кубоиде минимальной высоты. Построенная модель позволила
применить для поиска локальных экстремумов метод внутренней точки на последовательности подобластей области допустимых решений. Предложен метод построения разнообразных начальных точек.
Представлен численный пример.
На основі квазі Ф-функцій побудовано математичну модель задачі щільного пакування неорієнтованих
сфероконусів у кубоїді мінімальної висоти. Побудована модель дозволила застосувати для пошуку локальних екстремумів метод внутрішньої точки на послідовності підобластей області припустимих розв’язків.
Запропоновано метод побудови різноманітних початкових точок. Наведено числовий приклад.
On the ground of quasi Ф-functions a mathematical model of non-oriented spherocones dense packing
problem into a cuboid of the minimal height is built. The model allows us to apply the interior point method
to search local extrema on a sequence of feasible subregions. An algorithm for construction different starting
points is suggested. A numerical example is given.
|
| first_indexed | 2025-12-07T15:51:59Z |
| format | Article |
| fulltext |
ISSN 1561-5359 «Искусственный интеллект» 2014 № 1 74
2С
УДК 519.85
В.В. Сёмкин, А.М. Чугай
Институт проблем машиностроения им. А.Н. Подгорного НАНУ, Украина
Украина, 61046, г. Харьков, ул. Дм. Пожарского, 2/10
Поиск локальных экстремумов в задаче плотной
упаковки неориентированных сфероконусов
V.V. Semkin, A.M. Chugay
Institute for Mechanical Engineering Problems, National Academy of Sciences of Ukraine
Ukraine, 61046, Kharkov, Pozharsky St. 2/10
Searching for Local Extrema of Non-Oriented
Spherocones Dense Packing Problem
В.В. Сьомкін, А.М.Чугай
Інститут проблем машинобудування ім. А.М. Підгорного НАНУ, Україна
Україна, 61046, м. Харків, вул. Дм. Пожарського, 2/10
Пошук локальних екстремумів у задачі щільного
пакування неорієнтованих сфероконусів
На основании квази Ф-функций построена математическая модель задачи плотной упаковки не-
ориентированных сфероконусов в кубоиде минимальной высоты. Построенная модель позволила
применить для поиска локальных экстремумов метод внутренней точки на последовательности под-
областей области допустимых решений. Предложен метод построения разнообразных начальных точек.
Представлен численный пример.
Ключевые слова: квази Ф-функция, задача упаковки, сфероконус.
On the ground of quasi Ф-functions a mathematical model of non-oriented spherocones dense packing
problem into a cuboid of the minimal height is built. The model allows us to apply the interior point method
to search local extrema on a sequence of feasible subregions. An algorithm for construction different starting
points is suggested. A numerical example is given.
Key words: quasi Ф-function, packing problem, spherocone.
На основі квазі Ф-функцій побудовано математичну модель задачі щільного пакування неорієнтованих
сфероконусів у кубоїді мінімальної висоти. Побудована модель дозволила застосувати для пошуку локаль-
них екстремумів метод внутрішньої точки на послідовності підобластей області припустимих розв’язків.
Запропоновано метод побудови різноманітних початкових точок. Наведено числовий приклад.
Ключові слова: квазі Ф-функція, упаковка, сфероконус.
Вопросы моделирования плотного размещения трехмерных объектов активно
исследуются различными авторами во всем мире. Задачи, в которых приходится
решать эти вопросы, широко используются в науке и промышленности [1-3]. Следует
отметить, что на сегодняшний день разработано большое количество методов моде-
лирования упаковок сфер. Однако в реальности очень часто приходится сталкивать-
ся с задачами, в которых необходимо рассматривать трехмерные объекты произволь-
ных пространственных форм. Моделирование плотного размещения таких объектов
является ресурсоемкой задачей. В существующих работах по упаковке трехмерных
объектов, форма которых отличается от сферической, рассматриваются только при-
Поиск локальных экстремумов в задаче плотной упаковки...
«Штучний інтелект» 2014 № 1 75
2С
ближенные подходы, не позволяющие провести адекватное моделирование задачи и
получить хорошее решение. Один из распространенных подходов к решению задачи
упаковки трехмерных объектов заключается в представлении объектов набором сфер и
рассмотрении условий не пересечений этих сфер. Например, в работе [2] с помощью
такого подхода решается задача упаковки цилиндров, сфероцилиндров, конусов,
сфер и кубов. Еще один распространенный подход сводится к использованию
простой «идеализированной» математической модели дискретизации объектов с
помощью трехмерной сетки, ячейки которой являются кубоидами [3]. В работе [4]
предлагается использовать сферополиэдры для представления различных трехмер-
ных объектов. Используемый авторами алгоритм позволяет получать размещение
большого числа объектов (>100) в задачах. Все эти подходы направлены на получе-
ние быстрого, оценочного размещения большого количества объектов.
Целью данного исследования является построение адекватной математи-
ческой модели задачи плотного размещения сфероконусов и разработка метода
поиска экстремумов данной задачи.
Сфероконусом SK называется выпуклый геометрический объект, который
образован усеченным конусом K высоты 2h с радиусами верхнего и нижнего осно-
ваний 1r и 2r ( 21 rr ) соответственно, верхним сферическим сегментом 1G с высотой и
радиусом основания, равными 1w и 1r соответственно, и нижним сферическим сегментом
2G , высота и радиус основания которого равны 2w и 2r соответственно. Условия,
обеспечивающие выпуклость объекта имеют вид:
1 1 2 2
1 2 1 2
2
4
hw r
r r h r r
,
2 2
1 2 1 2
2 2
4
2
r r h r r
w r
h
.
Обозначим через 1 2 1 2, , , ,r r w w h вектор метрических характеристик сферо-
конуса. Сфероконус является «базовым» объектом, изменяя метрические характери-
стики которого, можно получить следующие трехмерные объекты: сфероцилиндр
1 2 1 2 1 2( , , , , , );r r w w h r r усеченный конус 1 2( , , 0, 0, );r r h цилиндр 1 2 1 2( , ,0,0, , );r r h r r
конус 1( ,0,0,0, );r h сферические сегменты 1 1( , 0, ,0,0r w или 0,,0,,0 22 wr );
сферический диск ( 1 2 1 2 1 2, , , ,0 , r r w w r r ).
Пусть задано множество сфероконусов 3ROi , nIi n ,,1 .
Сфероконусы
1
, ni IiO допускают аффинные преобразования трансляции на
вектор 3,, Rzyx iiii и поворота на углы 2, Riii вокруг осей координат
xO и yO соответственно. Вектор движения объекта ni IiO , обозначим iiiu , .
Тогда, вектор nRuuu un u 5,,,1 , определяет положение всех объектов в
трёхмерном пространстве.
Пусть плоскость YX , определяется уравнением 0,, dXYNYX , где
3,, RdY и coscos,cossin,sin YN .
Плоскость YX , делит пространство 3R на два полупространства
3 : , 0X R X Y и 0,:3 YXRX .
Сёмкин В.В., Чугай А.М.
«Искусственный интеллект» 2014 № 1 76
2С
Область размещения Р (контейнер) описывается следующим образом:
21
3 ,,:,, hzhbybaxaRzyxXP .
Контейнер P высоты 12 hhh обозначим hP . Тогда вектора 0 0 0 0 3, , , 1, ,6 ,t t t tY d R t
0 0 0 0 3, , , 1, ,6 ,Y d R t порождающие плоскости, в которых лежат грани контейнера hP , имеют вид:
0
1 , 0, ,
2
Y a
0
2 , 0, ,
2
Y a
0
3 0, , ,
2
Y b
0
4 0, , ,
2
Y b
0
5 10,0, ,Y h 0
6 2,0, .Y h
Задача. Найти вектор ˆ ,uu R такой, что объекты iO , nIi , содержатся в кон-
тейнере )(hP и его высота h достигает минимума.
Для построения математической модели поставленной задачи в работе ис-
пользуется метод Ф-функций [5]. Эта математическая модель может быть пред-
ставлена в виде:
2,min YuRWXhh , (1)
где
,6,,2,1,,0,
,,,,0,,:,,,
0
,
2
21
tIiYu
jiIjiYuuRhhYuXW
ntiit
njiji
q
ij
Yu
(2)
jijjiijiji
q
ij YuYuYuu ,,, ,,,min,, , YuFYu sl
l
s
~,min~,
2,1
,
YuYuYuF ssl
l
s
~,,~,minmax~, 3
2,1
1 ,
YuYuYkuF ssl
l
ss
~,,~,minmax~,, 6
5,4
2
2
11
~,1~,)~,(~, YNRrYNRhYYu szsszsss ,
,~,2)~,(~, 2
1
2
1
1
2
1
2 YNR
wr
wrhYYu sz
ss
ss
sss
1
2
1
2
1
1
2
1
2
1
3 2
~,
2
)~,(~,
s
ss
sz
s
ss
sss w
wrYNR
w
wrhYYu
,
2
24
~,1~,)~,(~, YNRrYNRhYYu szsszsss ,
YNR
wr
wrhYYu sz
ss
ss
sss
~,2)~,(~, 2
2
2
2
2
2
2
5
,
2
2
2
2
2
2
2
2
2
2
6 2
~,
2
)~,(~,
s
ss
sz
s
ss
sss w
wrYNR
w
wrhYYu
,
sssssszR coscos,cossin,sin ,
jijijijijijijiji dYdY ,,,,,,,, ,,,,, ,
2
13
nn
Y .
Функция 0, tiit Yu является Ф-функцией объекта ni IiO , и полупростран-
ства , отделяемого плоскостью 0, tYX .
Использование метода Ф-функций позволило записать условия взаимного не-
пересечения объектов в виде набора систем неравенств, левые части которых являются
бесконечно дифференцируемыми функциями.
Поиск локальных экстремумов в задаче плотной упаковки...
«Штучний інтелект» 2014 № 1 77
2С
Задача (1), (2) является NP-трудной задачей. Для поиска приближения к гло-
бальному экстремуму такой задачи необходимо разработать метод получения ло-
кальных экстремумов.
Поскольку математическая модель (1), (2) поставленной задачи построена в
виде классической задачи нелинейного программирования, то для ее решения могут
быть применены различные модификации методов нелинейной оптимизации (напри-
мер, метод возможных направлений, метод внутренней точки и др.).
Однако для применения численных методов нелинейной оптимизации не-
обходимо иметь допустимую начальную точку. Среди методов, которые применяются
для построения начальных точек, в задачах размещения объектов в основном исполь-
зуются различные модификации «жадных» алгоритмов. Применение «жадных» алго-
ритмов в рассматриваемой задаче представляет большую сложность.
Поэтому, для получения начальных точек в работе предлагается метод, кото-
рый предполагает, что все метрические характеристики объектов являются перемен-
ными и принимают значения от некоторого минимального значения до изначально
заданного.
Рассмотрим предлагаемый метод решения. Для каждого объекта введём величину
0
iS , равную сумме его метрических характеристик. Таким образом, 0
2
0
1
0
iii rrS
0
2
0
1
0
iii wwh , nIi . Также введём переменные величины ik – коэффициенты гомо-
тетии объектов iO , nIi и вектор n
n Rkk ,,1 .
Зададим высоту 0hh так, что объекты гарантированно размещаются в области
0( ).P h Введём векторы ,,,1 uRuuu n
nR ,, , YRYYYYY nn
,13,23,12,1 ,,,,
и сформируем точку YuX ,, , где вектор u случайно генерируется таким
образом, что ni IihPu ,0 , а вектор jiIjiY nji ,,,, порождает плоскость, пер-
пендикулярную отрезку, соединяющему полюсы объектов iO и jO , jiIji n ,, , и
проходящую через его середину.
Сформулируем следующую задачу:
nn
i
ii YuRXkS
,max
1
0 , (3)
6,,2,1,,10,0,,
,,,,0,,,,:,,
0
,
tIikYku
jiIjiYkkuuRYuX
nitiiit
njijiji
q
ij
nYu
(4)
Заметим, что существует такое 1,0 , что YuX ,, . Решим данную
задачу, взяв точку X в качестве стартовой. Целью решения данной задачи
является нахождение такого размещения объектов в области hP , при котором все
метрические характеристики объектов достигают своих заданных значений, то есть
1ik , nIi . В случае, если в результате решения задачи (3), (4) будет получена
точка *
1
** ,, YuX глобального максимума, то точка ** ,Yu берется в качестве
начальной точки для поиска локального минимума задачи (1), (2).
Для поиска локальных максимумов задачи (1), (2) и локальных минимумов
задачи (3), (4) использовался метод последовательного улучшения значения функции
цели на последовательности подобластей, образуемых наборами систем неравенств
из квази Ф-функций для каждой пары сфероконусов. При этом поиск локального
Сёмкин В.В., Чугай А.М.
«Искусственный интеллект» 2014 № 1 78
2С
экстремума на каждой подобласти осуществлялся с использованием библиотеки IPOPT [6].
В данной библиотеке реализованы алгоритмы внутренней точки, которые для поиска
вектора движения используют матрицу Гессе левой части системы ограничений,
описывающей область допустимых решений.
Приведем численный пример. Положим количество объектов 10n , среди
которых 4 «базовых» сфероконуса, 3 сфероцилиндра и 3 цилиндра. Размеры кон-
тейнера установим 15,25 ba . Метрические характеристики и координаты точки
локального минимума û W приведены в табл. 1. Значение локального минимума:
ˆ 63,126h .
Таблица 1 – Метрические характеристики и координаты точки локального минимума
i 0
ih 0
1ir 0
2ir 0
1iw 0
2iw ˆix ˆiy ˆiz ˆi î
1 8,389 9,863 5,475 9,229 2,535 11,17 1,268 3,222 4,996 2,606
2 8,238 9,694 4,267 9,089 0,886 -8,54 -8,37 10,63 -0,74 5,193
3 6,14 9,349 7,442 8,27 4,162 -14,7 6,147 -22,7 0,785 1,463
4 7,452 9,988 6,455 8,743 2,705 16,36 7 -12,7 6,035 3,495
5 11 6,093 6,093 4,119 4,535 4,369 -8,91 -25,5 5,29 -1,57
6 11,27 10,35 10,35 6,894 8,395 6,616 0,228 21,21 1,571 4,175
7 12 9,192 9,192 2,949 6,532 -10,4 0,293 -3,86 2,279 2,555
8 4,397 8,888 8,888 0 0 1,511 -3,08 -10,8 3,045 0,827
9 2,553 6,375 6,375 0 0 -14,9 -6,93 28,67 3,146 3,138
10 3,251 6,281 6,281 0 0 21,57 8,493 10,94 5,25 4,709
Рисунок 1 – Локальный минимум
В работе благодаря использованию аппарата квази Ф-функций построена ма-
тематическая модель задачи плотной упаковки сфероконусов в кубоиде. Построен-
ная модель позволила применить для поиска локальных экстремумов метод внутрен-
ней точки.
Поиск локальных экстремумов в задаче плотной упаковки...
«Штучний інтелект» 2014 № 1 79
2С
Список литературы
1. Williams S.R. Random Packings of Spheres and Spherocylinders Simulated by Mechanical Contraction /
S.R. Williams, A.P. Philipse // Phys. Rev. E. – 2003. – № 67. – P. 051301.
2. LI ShuiXiang. Maximum packing densities of basic 3D objects/ LI ShuiXiang, ZHAO Jian, LU Peng,
XIE Yu // Chinese scince Bulletin. – 2010. – Vol.55.– №2.– P. 114-119.
3. A.C.J. de Korte. Random packing of digitized particles / A.C.J. de Korte, H.J.H. Brouwers // Powder
Technology. – 2013. – № 233. – P. 319-324.
4. Мизгулин В.В. Моделирование плотных материалов методом упаковки сферополиэдров / Мизгулин В.В.,
Кадушников Р.М., Алиевский Д.М., Алиевский В.М. // Компьютерные исследования и моделирование. –
2012. – Т. 4, № 4. – С. 757-766.
5. Stoyan Yu.G. Ф-function and its basic properties/ Yu.G. Stoyan // Доп. НАН України. – 2001. – № 8. –
С. 112-117.
References
1. Williams S.R. Random Packings of Spheres and Spherocylinders Simulated by Mechanical Contraction /
S.R.Williams, A.P.Philipse // Phys. Rev. E. – 2003. – № 67. – P. 051301.
2. LI ShuiXiang. Maximum packing densities of basic 3D objects/ LI ShuiXiang, ZHAO Jian, LU Peng,
XIE Yu // Chinese scince Bulletin. – 2010. – Vol. 55.– № 2.– P. 114-119.
3. A.C.J. de Korte. Random packing of digitized particles / A.C.J. de Korte, H.J.H. Brouwers // Powder
Technology. – 2013. – № 233. – P. 319-324.
4. Mizgulin V.V. Modeling dense material by spheropolyhedron packing methods / Mizgulin V.V.,
Kadushnikov R.М., Alievskiy D.М., Alievskiy V.М. // Kompyuternyye issledovaniya i modelirovaniye. –
2012. – Т.4, № 4. – P. 757-766.
5. Stoyan Yu.G. Ф-function and its basic properties/ Yu.G. Stoyan // Doklady NAN Ukrainy. – 2001. – № 8. –
P. 112-117.
RESUME
V.V. Semkin, A.M. Chugay
Searching for Local Extrema
of Non-Oriented Spherocones Dense Packing Problem
In this paper a mathematical model of dense packing problem of non-oriented
spherocones into a cuboid is constructed by using the Ф-function technic.
An application of Ф-functions allowed us to formulate mutual non-intersections
conditions for a pair of objects as a set of inequalities systems which left sides are infinitely
differentiable functions. Owing to this fact a mathematical model of the problem is presented as
a classical non-linear programming problem.
For construction of starting points we proposed method which assumes that all
objects metric characteristics are variable and take values from a minimum one to the
initially specified.
In order to find local minima of the problem (1), (2) and local maxima of the problem
(3), (4) we use the method of continuous improvement of the objective function values on a
sequence of subregions that are formed by sets of inequalities systems of quasi Ф-functions
for each pair of spherocones. The search of a local extremum in each subregion is per-
formed by using IPOPT library.
Статья поступила в редакцию 26.12.2013.
|
| id | nasplib_isofts_kiev_ua-123456789-85247 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T15:51:59Z |
| publishDate | 2014 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Сёмкин, В.В. Чугай, А.М. 2015-07-23T12:16:03Z 2015-07-23T12:16:03Z 2014 Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов / В.В. Сёмкин, А.М. Чугай // Искусственный интеллект. — 2014. — № 1. — С. 74–79. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85247 519.85 На основании квази Ф-функций построена математическая модель задачи плотной упаковки не- ориентированных сфероконусов в кубоиде минимальной высоты. Построенная модель позволила применить для поиска локальных экстремумов метод внутренней точки на последовательности подобластей области допустимых решений. Предложен метод построения разнообразных начальных точек. Представлен численный пример. На основі квазі Ф-функцій побудовано математичну модель задачі щільного пакування неорієнтованих сфероконусів у кубоїді мінімальної висоти. Побудована модель дозволила застосувати для пошуку локальних екстремумів метод внутрішньої точки на послідовності підобластей області припустимих розв’язків. Запропоновано метод побудови різноманітних початкових точок. Наведено числовий приклад. On the ground of quasi Ф-functions a mathematical model of non-oriented spherocones dense packing problem into a cuboid of the minimal height is built. The model allows us to apply the interior point method to search local extrema on a sequence of feasible subregions. An algorithm for construction different starting points is suggested. A numerical example is given. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов Пошук локальних екстремумів у задачі щільного пакування неорієнтованих сфероконусів Searching for local extrema of non-oriented spherocones dense packing problem Article published earlier |
| spellingShingle | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов Сёмкин, В.В. Чугай, А.М. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| title | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов |
| title_alt | Пошук локальних екстремумів у задачі щільного пакування неорієнтованих сфероконусів Searching for local extrema of non-oriented spherocones dense packing problem |
| title_full | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов |
| title_fullStr | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов |
| title_full_unstemmed | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов |
| title_short | Поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов |
| title_sort | поиск локальных экстремумов в задаче плотной упаковки неориентированных сфероконусов |
| topic | Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| topic_facet | Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85247 |
| work_keys_str_mv | AT semkinvv poisklokalʹnyhékstremumovvzadačeplotnoiupakovkineorientirovannyhsferokonusov AT čugaiam poisklokalʹnyhékstremumovvzadačeplotnoiupakovkineorientirovannyhsferokonusov AT semkinvv pošuklokalʹnihekstremumívuzadačíŝílʹnogopakuvannâneoríêntovanihsferokonusív AT čugaiam pošuklokalʹnihekstremumívuzadačíŝílʹnogopakuvannâneoríêntovanihsferokonusív AT semkinvv searchingforlocalextremaofnonorientedspheroconesdensepackingproblem AT čugaiam searchingforlocalextremaofnonorientedspheroconesdensepackingproblem |