Упаковка неравных шаров в различные контейнеры

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
Hauptverfasser:	Стоян, Ю.Г., Шайтхауер, Г., Яськов, Г.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/133685
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Упаковка неравных шаров в различные контейнеры / Ю.Г. Стоян, Г. Шайтхауер, Г.Н. Яськов // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 97-105. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-133685
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1336852025-02-09T13:59:03Z Упаковка неравных шаров в различные контейнеры Пакування нерівних куль у різні контейнери Packing non-equal spheres into containers of different shapes Стоян, Ю.Г. Шайтхауер, Г. Яськов, Г.Н. Системный анализ Рассматривается оптимизационная задача упаковки разных шаров в контейнеры типа кубоид, шар, прямой круговой цилиндр, кольцевой цилиндр и сферический слой. Предполагается, что радиусы шаров переменные. Это позволяет предложить новый способ получения начальных точек, принадлежащих области допустимых решений задачи, а также осуществлять перебор локальных экстремумов, используя модификацию алгоритма JA (jump-алгоритм), который реализует плавный переход от одного локального минимума к другому с лучшим значением функции цели. Уменьшение размерности задачи и попарные перестановки шаров позволяют улучшить значение функции цели. Полученные результаты сравниваются с лучшими известными. Розглянуто оптимізаційну задачу пакування різних куль у контейнери типу кубоїд, куля, прямий круговий циліндр, кільцевий циліндр і сферичнй шар. Вважається, що радіуси куль змінні. Це дозволяє запропонувати новий спосіб отримання початкових точок, що належать області допустимих розв’язків задачі, а також здійснювати перебір локальних екстремумів, використовуючи модифікацію алгоритму JA (jump-алгоритм), який реалізує плавний перехід від одного локального мінімуму до іншого з кращим значенням функції цілі. Зменшення розмірності задачі та попарні переставлення куль дозволяють покращити значення функції цілі. Отримані результати порівнюються з кращими відомими. The paper considers the optimization problem of packing different solid spheres into containers of types: a cuboid, a sphere, a right circular cylinder, an annular cylinder, and a spherical layer. The radii of spheres are assumed to be variables. This allows us to propose a new technique to derive initial points belonging to the feasible region of the problem, as well as to carry out a non-exhaustive search of local extrema, using a modification of the jump algorithm (JA), which implements a continuous transition from one local minimum to another with a better value of the objective. A reduction of the solution space dimension of the problem and rearrangements of sphere pairs allow improving the objective function value. The results obtained are compared with benchmark ones. 2016 Article Упаковка неравных шаров в различные контейнеры / Ю.Г. Стоян, Г. Шайтхауер, Г.Н. Яськов // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 97-105. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/133685 519.85 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Стоян, Ю.Г. Шайтхауер, Г. Яськов, Г.Н. Упаковка неравных шаров в различные контейнеры Кибернетика и системный анализ
description	Рассматривается оптимизационная задача упаковки разных шаров в контейнеры типа кубоид, шар, прямой круговой цилиндр, кольцевой цилиндр и сферический слой. Предполагается, что радиусы шаров переменные. Это позволяет предложить новый способ получения начальных точек, принадлежащих области допустимых решений задачи, а также осуществлять перебор локальных экстремумов, используя модификацию алгоритма JA (jump-алгоритм), который реализует плавный переход от одного локального минимума к другому с лучшим значением функции цели. Уменьшение размерности задачи и попарные перестановки шаров позволяют улучшить значение функции цели. Полученные результаты сравниваются с лучшими известными.
format	Article
author	Стоян, Ю.Г. Шайтхауер, Г. Яськов, Г.Н.
author_facet	Стоян, Ю.Г. Шайтхауер, Г. Яськов, Г.Н.
author_sort	Стоян, Ю.Г.
title	Упаковка неравных шаров в различные контейнеры
title_short	Упаковка неравных шаров в различные контейнеры
title_full	Упаковка неравных шаров в различные контейнеры
title_fullStr	Упаковка неравных шаров в различные контейнеры
title_full_unstemmed	Упаковка неравных шаров в различные контейнеры
title_sort	упаковка неравных шаров в различные контейнеры
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Системный анализ
url	https://nasplib.isofts.kiev.ua/handle/123456789/133685
citation_txt	Упаковка неравных шаров в различные контейнеры / Ю.Г. Стоян, Г. Шайтхауер, Г.Н. Яськов // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 97-105. — Бібліогр.: 15 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT stoânûg upakovkaneravnyhšarovvrazličnyekontejnery AT šajthauerg upakovkaneravnyhšarovvrazličnyekontejnery AT âsʹkovgn upakovkaneravnyhšarovvrazličnyekontejnery AT stoânûg pakuvannânerívnihkulʹurízníkontejneri AT šajthauerg pakuvannânerívnihkulʹurízníkontejneri AT âsʹkovgn pakuvannânerívnihkulʹurízníkontejneri AT stoânûg packingnonequalspheresintocontainersofdifferentshapes AT šajthauerg packingnonequalspheresintocontainersofdifferentshapes AT âsʹkovgn packingnonequalspheresintocontainersofdifferentshapes
first_indexed	2025-11-26T14:27:11Z
last_indexed	2025-11-26T14:27:11Z
_version_	1849863423420006400
fulltext	ÓÄÊ 519.85 Þ.Ã. ÑÒÎßÍ, Ã. ØÀÉÒÕÀÓÅÐ, Ã.Í. ßÑÜÊÎÂ ÓÏÀÊÎÂÊÀ ÍÅÐÀÂÍÛÕ ØÀÐÎÂ Â ÐÀÇËÈ×ÍÛÅ ÊÎÍÒÅÉÍÅÐÛ Àííîòàöèÿ. Ðàññìàòðèâàåòñÿ îïòèìèçàöèîííàÿ çàäà÷à óïàêîâêè ðàçíûõ øà- ðîâ â êîíòåéíåðû òèïà êóáîèä, øàð, ïðÿìîé êðóãîâîé öèëèíäð, êîëüöåâîé öèëèíäð è ñôåðè÷åñêèé ñëîé. Ïðåäïîëàãàåòñÿ, ÷òî ðàäèóñû øàðîâ ïåðåìåí- íûå. Ýòî ïîçâîëÿåò ïðåäëîæèòü íîâûé ñïîñîá ïîëó÷åíèÿ íà÷àëüíûõ òî÷åê, ïðèíàäëåæàùèõ îáëàñòè äîïóñòèìûõ ðåøåíèé çàäà÷è, à òàêæå îñóùå- ñòâëÿòü ïåðåáîð ëîêàëüíûõ ýêñòðåìóìîâ, èñïîëüçóÿ ìîäèôèêàöèþ àëãîðèò- ìà JA (jump-àëãîðèòì), êîòîðûé ðåàëèçóåò ïëàâíûé ïåðåõîä îò îäíîãî ëî- êàëüíîãî ìèíèìóìà ê äðóãîìó ñ ëó÷øèì çíà÷åíèåì ôóíêöèè öåëè. Óìåíü- øåíèå ðàçìåðíîñòè çàäà÷è è ïîïàðíûå ïåðåñòàíîâêè øàðîâ ïîçâîëÿþò óëó÷øèòü çíà÷åíèå ôóíêöèè öåëè. Ïîëó÷åííûå ðåçóëüòàòû ñðàâíèâàþòñÿ ñ ëó÷øèìè èçâåñòíûìè. Êëþ÷åâûå ñëîâà: óïàêîâêà, óïàêîâêà øàðîâ, íåâûïóêëàÿ çàäà÷à îïòèìèçà- öèè, jump-àëãîðèòì. ÂÂÅÄÅÍÈÅ Çàäà÷è óïàêîâêè øàðîâ èãðàþò âàæíóþ ðîëü â ðàçëè÷íûõ îòðàñëÿõ [1]. Óïà- êîâêà íåðàâíûõ øàðîâ èñïîëüçóåòñÿ â ðàäèîõèðóðãèè [2]. Ãàììà-ëó÷è ôîêóñè- ðóþòñÿ íà îáùèé öåíòð, ñîçäàâàÿ øàðîîáðàçíûé îáúåì âûñîêîé äîçû ðà- äèàöèè. Êëþ÷åâàÿ çàäà÷à â ëå÷åíèè ãàììà-íîæàìè — êàê ðàçìåñòèòü øàðû â îïó- õîëè ïðîèçâîëüíîé ïðîñòðàíñòâåííîé ôîðìû. Â ðàáîòå [2] Sutou è Day ïðåäëàãàþò ïîäõîä ê ãëîáàëüíîé îïòèìèçàöèè óïà- êîâêè íåðàâíûõ øàðîâ. Îïòèìèçàöèîííàÿ çàäà÷à ôîðìóëèðóåòñÿ êàê íåâûïóêëàÿ îïòèìèçàöèîííàÿ çàäà÷à ñ êâàäðàòè÷íûìè îãðàíè÷åíèÿìè è ëèíåéíîé ôóíêöèåé öåëè. Â ñòàòüå [3] ïðåäëàãàåòñÿ ìàòåìàòè÷åñêèé ìåòîä îïòèìèçàöèè óïàêîâêè íå- ðàâíûõ øàðîâ â êóáîèä, îñíîâàííûé íà ìåòîäå ñóæàþùèõñÿ îêðåñòíîñòåé è ìåòî- äå ëîêàëüíîé îïòèìèçàöèè. Ìîäåëè äëÿ 2D è 3D çàäà÷ óïàêîâêè, èñïîëüçóþùèå äâàæäû äèôôåðåíöèðóåìûå ôóíêöèè, âêëþ÷àÿ óïàêîâêó øàðîâ ðàçëè÷íîãî ðàäèó- ñà, ïðåäñòàâëåíû â [4]. Kubach è äð. [5, 6] àäàïòèðóþò ïàðàëëåëüíûå æàäíûå àëãî- ðèòìû, ïðåäëîæåííûå â ðàáîòå [7], ê òðåõìåðíîìó ñëó÷àþ ñ íåêîòîðûìè âàæíûìè óñîâåðøåíñòâîâàíèÿìè (ìåòîä B1.6_3DSPP) è ñîçäàþò âíóøèòåëüíóþ áàçó òåñòî- âûõ êîíòðîëüíûõ çàäà÷. Âûáèðàåòñÿ êîìïðîìèññ ìåæäó êà÷åñòâîì ïîëó÷àåìûõ ðåçóëüòàòîâ è âðåìåíåì ðåøåíèÿ. Hifi è Yousef [8] ïðåäëàãàþò óëó÷øåíèå øèðî- êîëó÷åâîãî ïîèñêà, îñíîâàííîãî íà æàäíûõ àëãîðèòìàõ, ñ ïîìîùüþ óïðàâëåíèÿ íèæíèìè ãðàíèöàìè è ïðèìåíåíèÿ ñòðàòåãèè õèëë-êëàéìáèíã (hill-climbing) è ïî- ëó÷àþò ïðè ýòîì õîðîøèå ðåçóëüòàòû. Â ñòàòüå [9] ðàçðàáàòûâàåòñÿ ãèáðèäíûé àë- ãîðèòì ELPGD äëÿ óïàêîâêè íåðàâíûõ êðóãîâ è øàðîâ â áîëüøèé êðóãîâîé (ñôå- ðè÷åñêèé) êîíòåéíåð. Ýòîò àëãîðèòì îñíîâàí íà óëó÷øåííîì ìåòîäå (energy landscape paving method) ñ ïðîöåäóðîé ãðàäèåíòíîãî ñïóñêà. Â ñòàòüå [10] ðàçðàáî- òàí àëãîðèòì óïàêîâêè íåðàâíûõ øàðîâ â áîëüøåì øàðå, â êîòîðîì èñïîëüçóåòñÿ ïîèñê ñ çàïðåòàìè (tabu search), ñòðàòåãèÿ quasi-human basin-hopping è ìåòîä Áðîé- äåíà–Ôëåò÷åðà–Ãîëüäôàðáà–Øàííî. Â ðàáîòå [11] Hifi è M’Hallah äåëàþò îáçîð ðÿäà ýôôåêòèâíûõ ìîäåëåé è ìåòîäîâ äëÿ óïàêîâêè êðóãîâ è øàðîâ. Â íàñòîÿùåé ñòàòüå jump-àëãîðèòì (JA), ðàçðàáîòàííûé äëÿ óïàêîâêè íåðàâ- íûõ êðóãîâ [12], àäàïòèðóåòñÿ äëÿ óïàêîâêè íåðàâíûõ øàðîâ. Àëãîðèòì JA ïîç- âîëÿåò ïåðåéòè îò îäíîé òî÷êè ëîêàëüíîãî ìèíèìóìà ê äðóãîé òàê, ÷òî ïåðåìåí- íûé ðàçìåð êîíòåéíåðà íå âîçðàñòàåò. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 97 © Þ.Ã. Ñòîÿí, Ã. Øàéòõàóåð, Ã.Í. ßñüêîâ, 2016 ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó. Øàðû S x y z x x y y z z ri i i i i i( ) { ( , , ) :( ) ( ) ( ) �� R 3 2 2 2 2 0}, i I n� � { , , ..., }1 2 , ãäå � i i i ix y z� ( , , ) — êîîðäèíàòû öåíòðà øàðà S i , íåîáõîäèìî óïàêîâàòü â êîíòåéíåð P , êîòîðûé ìîæåò èìåòü îäíó èç ñëåäóþùèõ ôîðì: êóáîèä PB � �{ :� R 3 0 � �x a, 0 � �y b, 0 � �z h}, ãäå a r i Ii/ max{ � : }2 � � , b r i Ii/ max{ � : }2 � � ; øàð PS � �{� R 3: x y z R2 2 2 2 0� � � � }; öèëèíäð PC � �{� R 3: x y R2 2 2 0� � � , 0 � �z h }, ãäå R r i Ii� �max { � : } è h / 2 � � �max{ � : }r i Ii ; êîëüöåâîé öèëèíäð P x y RCC � � � � �{ :� R 3 2 2 2 0, � � � �x y2 2 2 0� , R � � , 0 � �z h} , ãäå R r i Ii� � �� max{ � : } , è øàðîâîé ñëîé P x y z R x y z RSS � � � � � � � � � � � �{ : , , }� � �R 3 2 2 2 2 2 2 2 20 0 . Ïîëàãàåì, ÷òî âûñîòà h êóáîèäà PB è ðàäèóñ R øàðà PS , êîëüöåâîãî öèëèí- äðà PCC è øàðîâîãî ñëîÿ PSS — ïåðåìåííûå. Âûñîòà h èëè ðàäèóñ R ÿâëÿþòñÿ ïåðåìåííûìè äëÿ PC . Äëÿ óäîáñòâà ñ÷èòàåì, ÷òî h � � (R � �). Øàð S i , òðàíñëèðîâàííûé íà âåêòîð � i , è êîíòåéíåð P ñ ïåðåìåííûì ðàçìå- ðîì � îáîçíà÷èì S i i( )� è P ( )� ñîîòâåòñòâåííî. Âåêòîð � � � �� ( , )1 2 � n �R 3n îïðåäåëÿåò ïîëîæåíèå øàðîâ S i , i I� , â R 3 . Íå òåðÿÿ îáùíîñòè, ïîëàãàåì, ÷òî � � �r r rn1 2� � �� , � �r rn1 . (1) Çàäà÷à. Íàéòè âåêòîð �, ãàðàíòèðóþùèé óïàêîâêó øàðîâ S i i( )� , i I� , áåç âçàèìíûõ íàëîæåíèé â êîíòåéíåðå P ìèíèìàëüíîãî ðàçìåðà �* . ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ È ÅÅ ÎÑÍÎÂÍÛÅ ÑÂÎÉÑÒÂÀ Ïðåäñòàâèì ìàòåìàòè÷åñêóþ ìîäåëü çàäà÷è â âèäå � �* min� , Y W n� � � �( , )� � R 3 1, (2) W Y i j I i In ij i j i i� � � � � ��{ : ( , ) , , ( , ) , }R 3 1 0 0� �� . (3) Íåðàâåíñòâî �ij i j i j i j i j i jx x y y z z r r( , ) ( ) ( ) ( ) ( � � )� � � � � � � � � � �2 2 2 2 0 îáåñïå÷èâàåò íåíàëîæåíèå øàðîâ S i è S j , à �i i( , )� � � 0 — ðàçìåùåíèå øàðà S i i( )� â îáëàñòè P ( )� . Ôóíêöèÿ �i i( , )� � çàâèñèò îò òèïà êîíòåéíåðà è èìååò âèä �i i( , )� � � � � � � � � � � � �min � , � , � , � , � , �{x r y r z r a x r b y r h zi i i i i i i i i i i r P P x y z R r P P x i B i i i i S } åñëè åñëè { , , ( � ) , , min � � � � � � � � 2 2 2 2 i i i i i i i C i y R r z r h z r P P x 2 2 2 2 � � � � � � � � ( � ) , � , � , ,} åñëè min{ � � � � � � � � �y R r x y r z r h z ri i i i i i i i i 2 2 2 2 2( � ) , ( � ) , � , � ,� } åñëè { P P x y z r x y z R CC i i i i i i i � � � � � � � � � � , min ( � ) , ( �2 2 2 2 2 2 2� r P Pi SS) .2 }, åñëè � � � �� Ìàòåìàòè÷åñêàÿ ìîäåëü (2), (3) èìååò òå æå ñâîéñòâà, ÷òî è ìàòåìàòè÷åñêàÿ ìîäåëü, ðàññìîòðåííàÿ â [3], ò.å. ëîêàëüíûå ìèíèìóìû äîñòèãàþòñÿ â êðàéíèõ òî÷êàõ îáëàñòè W, ìàòðèöà ñèñòåìû íåðàâåíñòâ â (3) ñèëüíî ðàçðåæåíà, ÷èñëî 98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 íåðàâåíñòâ, çàäàþùèõ W, îïðåäåëÿåòñÿ êàê � � � �n n n( ) /1 2 è ïîñòàâëåííàÿ çàäà÷à ÿâëÿåòñÿ NP-òðóäíîé. Òàêèì îáðàçîì, â îáùåì ñëó÷àå ãëîáàëüíûé ìèíèìóì çàäà÷è ìîæíî ïîëó÷èòü òîëüêî òåîðåòè÷åñêè. Ñëåäîâàòåëüíî, äëÿ óñïåøíîãî ðåøåíèÿ çàäà÷è (2), (3) íåîáõîäèìî ñòðîèòü äîïóñòèìûå íà÷àëüíûå òî÷êè, âû÷èñëÿòü ëîêàëüíûå ìèíèìóìû è îñóùåñòâëÿòü ýôôåêòèâíûé íàïðàâëåííûé ïåðåáîð ëîêàëüíûõ ìèíèìóìîâ. ÏÎÑÒÐÎÅÍÈÅ ÍÀ×ÀËÜÍÛÕ ÒÎ×ÅÊ È ÏÎÈÑÊ ËÎÊÀËÜÍÛÕ ÌÈÍÈÌÓÌÎÂ Íà÷àëüíàÿ òî÷êà Y 0 ìîæåò áûòü çàäàíà êàê äåòåðìèíèðîâàííûì ñïîñîáîì, òàê è ñëó÷àéíî. Ëþáîé äåòåðìèíèðîâàííûé ñïîñîá (æàäíûå èëè ýâðèñòè÷åñ- êèå àëãîðèòìû, íàïðèìåð [5]) íå ïîçâîëÿåò ïîëó÷èòü ïðîèçâîëüíûå íà÷àëüíûå òî÷êè, ïðèíàäëåæàùèå îáëàñòè äîïóñòèìûõ ðåøåíèé. Ïîýòîìó áîëåå ïðåäïî÷- òèòåëüíî èñïîëüçîâàòü ñëó÷àéíûé âûáîð íà÷àëüíûõ òî÷åê. Ïîëàãàåì, ÷òî ðàäèóñû ri øàðîâ S i , i I� , ÿâëÿþòñÿ ïåðåìåííûìè è ôîðìèðó- þò âåêòîð r r r rn n� �( , )1 2 � R . Òîãäà X r n� �( , )� R 4 — âåêòîð âñåõ ïåðåìåí- íûõ. Â ýòîì ñëó÷àå íåðàâåíñòâà â ñèñòåìå (3) ïðèíèìàþò âèä � �ij i j i j i i ir r i j I r i I( , , , ) , , ( , , ) ,� � � �� 0 0 . Ïóñòü � �� 0 0. Çàäàåì ñëó÷àéíûì îáðàçîì òî÷êó X r r� ( , )� 0 òàê, ÷òî � �i r P� ( )0 , i I� . Äëÿ ïîñòðîåíèÿ òî÷êè ( , )� �0 �W ñ ïîìîùüþ òî÷êè ( , )� �r 0 ðåøàåì çàäà÷ó � �( ) max ( ) max � r r ri i n � � � � 1 , X r D n� � �( , )� R 4 , (4) D X r r i j I rn ij i j i j i i i� � � � �{ , ( , , , ) , , ( , , )R 4 00 0� �� , � i i i i ir r r r i I( ) � , , }� � � � �0 0 . (5) Èç ïîñòðîåíèÿ òî÷êè X r ñëåäóåò, ÷òî îíà ïðèíàäëåæèò D. Òîãäà, çàäàâ íà- ÷àëüíóþ òî÷êó X r , ðåøàåì çàäà÷ó (4), (5) è ïîëó÷àåì òî÷êó ëîêàëüíîãî ìàêñè- ìóìà � � � X r� ( , )� . Åñëè �( ) � � � r r ri i n i i n � � � � � � � 1 1 �, òî � r r� � è øàðû S i , i I� , óïàêîâûâàþòñÿ â P ( )�0 . Ýòî îçíà÷àåò, ÷òî � X — òî÷êà ãëîáàëüíîãî ìàêñèìóìà çàäà÷è (4), (5). Åñëè æå � X — òî÷êà ãëîáàëüíîãî ìàêñèìóìà çàäà÷è (4), (5) è �( ) � r �, òî øàðû S i , i I� , íå ìîãóò áûòü óïàêî- âàíû â P ( )�0 . Íåðàâåíñòâî �( ) � r � â òî÷êå ëîêàëüíîãî ìàêñèìóìà � X íå îçíà÷àåò, ÷òî øàðû íå ìîãóò áûòü óïàêîâàíû â P ( )�0 . Â çàâèñèìîñòè îò çíà÷åíèÿ �0 âîçìîæíû äâà ñëó÷àÿ óïàêîâêè: �( ) � r � � è �( ) � r �. Åñëè �( ) � r � �, òî ( , ) � � �0 �W (ñì. (3)). Â îáùåì ñëó÷àå ( , ) � � �0 íå ÿâëÿåòñÿ òî÷êîé ëîêàëüíîãî ìèíèìóìà çàäà÷è (2), (3). Ïîýòîìó, âçÿâ íà÷àëüíóþ òî÷êó ( , ) � � �0 , âû÷èñëÿåì òî÷êó ëîêàëüíîãî ìèíèìóìà ( , ) � � � � çàäà÷è (2), (3). Åñëè �( ) � r �, òî ëèáî âûáèðàåì X r r� ( , )� 0 ñíîâà ïðîèçâîëüíî è ðåøàåì ïîñëåäîâàòåëüíî çàäà÷è (4), (5) è (2), (3), ëèáî íà÷èíàåì âûïîëíÿòü ïåðåõîä èç òî÷êè � X â òî÷êó �� X òàê, ÷òîáû âûïîëíÿëîñü óñëîâèå � �( ) ( ) �� r r� . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 99 ÏÅÐÅÕÎÄ ÈÇ ÎÄÍÎÃÎ ËÎÊÀËÜÍÎÃÎ ÌÀÊÑÈÌÓÌÀ Â ÄÐÓÃÎÉ Ðàññìîòðèì âîçìîæíîñòü ïîñòðîåíèÿ â òî÷êå ëîêàëüíîãî ìàêñèìóìà çàäà- ÷è (4), (5) âåêòîðà, ïîçâîëÿþùåãî ïîëó÷èòü íîâóþ òî÷êó ëîêàëüíîãî ìàêñèìó- ìà, â êîòîðîé çíà÷åíèå ôóíêöèè öåëè �( )r óâåëè÷èâàåòñÿ. Ýòî èññëåäîâàíèå ÿâëÿåòñÿ îñíîâîé àëãîðèòìà JA. Ïóñòü � � � X r� ( , )� — òî÷êà ëîêàëüíîãî ìàêñèìóìà çàäà÷è (4), (5) è �( ) � r �, ò.å. ïî êðàéíåé ìåðå îäíî èç íåðàâåíñòâ �r ri i� � � 0, i I� , àêòèâíî. Îïðåäåëèì ïîçìîæíîñòü ïåðåõîäà èç òî÷êè � � � X r� ( , )� â äðóãóþ òî÷êó, â êî- òîðîé ôóíêöèÿ öåëè âîçðàñòåò. Òàêîé ïåðåõîä ìîæåò áûòü îñóùåñòâëåí, åñëè åñòü ðåçåðâ îáúåìà âîêðóã õîòÿ áû îäíîãî øàðà. Ñ ýòîé öåëüþ ñôîðìóëèðóåì âñïîìîãàòåëüíóþ çàäà÷ó max ( )V r ri i n � � � 3 1 , X M n� � R 4 , (6) M X r r i j I rn ij i j i j i i i� � � � �{ , ( , , , ) , , ( , , )R 4 00 0� �� , � �1 20 0i i i i i ir r r r r r i I( ) , ( ) ,max min� � � � � � � � }, (7) ãäå r rnmax �� è r rmin �� 1 . Çàìåòèì, ÷òî îáëàñòü äîïóñòèìûõ ðåøåíèé M îòëè- ÷àåòñÿ îò îáëàñòè D â çàäà÷å (4), (5), ò.å. íåðàâåíñòâà � i i i ir r r( ) �� 0 , ri � 0, â (5) çàìåíÿþòñÿ íåðàâåíñòâàìè �1 0i ir( ) � , � 2 0i ir( ) � , i I� . Ýòî îçíà÷àåò, ÷òî ðàäèóñû ri � 0 , i I� , ìîãóò ïðèíèìàòü ëþáûå çíà÷åíèÿ èç èíòåðâàëà [ , ]min maxr r . Ñëåäîâàòåëüíî, ðàäèóñû ìîãóò èìåòü çíà÷åíèÿ, áîëüøèå ÷åì íà- ÷àëüíûå �ri , i I� \ { }1 . Äàëåå âû÷èñëèì âåêòîð íàèñêîðåéøåãî ïîäúåìà Z 0 â òî÷êå � X äëÿ âñïîìîãà- òåëüíîé çàäà÷è (6), (7) è ïîñòðîèì òî÷êè X X Z � � � � 05 0. , � � �� { , , , ..., }0 1 2 q . (8) Åñëè Z 0 0� , òî ñóùåñòâóåò òàêîå m, ÷òî ïðè � m èìååì X M � . Ýòî ñïðà- âåäëèâî, òàê êàê M � � è � � � X r� ( , )� íå ÿâëÿåòñÿ òî÷êîé ëîêàëüíîãî ìàêñèìóìà. Ïîñêîëüêó çíà÷åíèÿ ri , i I� , îãðàíè÷åíû îòðåçêîì [ , ]min maxr r â çàäà÷å (6), (7), òî â íåêîòîðûõ ñëó÷àÿõ r r rj j j� � � , j I I� �1 , à â íåêîòîðûõ r r ri i i� � , i I I� �2 . Òàêèì îáðàçîì, ìîæåò îêàçàòüñÿ, ÷òî ÷àñòü íåðàâåíñòâ � i i i ir r r( ) �� 0 , i I� , â (5) íåàêòèâíû. Ïóñòü ìíîæåñòâà èíäåêñîâ I1 è I 2 ñî- ñòîÿò èç q è p ýëåìåíòîâ ñîîòâåòñòâåííî. Î÷åâèäíî, ÷òî I I1 2� � � è I I I1 2� � . Òåïåðü ïîëàãàåì, ÷òî � m , è çàäàäèì êîîðäèíàòû âåêòîðà ~ (~ , ~X m m m� � � 1 2 � ... ~ , ~ , ~ ~ )�n m m m n mr r r 1 2 � íà îñíîâå òî÷åê � � � X r� ( , )� è X m ñëåäóþùèì îáðàçîì. Åñëè äëÿ i I� 2 è j I� 1 íåðàâåíñòâà � � , ,r r r r r rj i j i m i j m� � � � (9) âåðíû, òî ~ min{� , }, ~ , ~ min{� , }, ~r r r r r ri m i j m i m j m j m j i m j m� � � �� i m . Åñëè äëÿ i I� 2 íàðóøàåòñÿ ïî êðàéíåé ìåðå îäíî èç íåðàâåíñòâ (9), òî ~ , ~r ri m i m i m i m� �� . Çàìåòèì, ÷òî òî÷êå ~ X Xm m� ñîîòâåòñòâóåò äîïóñòèìàÿ óïàêîâêà øàðîâ, ïîëó÷åííàÿ èç óïàêîâêè, ñîîòâåòñòâóþùåé òî÷êå � X , â êîòîðîé íåêîòîðûå èç øà- ðîâ S j , j I� , ïîìåíÿëèñü ìåñòàìè. 100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 Ìîæåò îêàçàòüñÿ, ÷òî ~ X Xm m� , ò.å. ñóùåñòâóåò òàêîå öåëîå ÷èñëî N , êîã- äà ïðè m N� èìååì ~ X Xm m� . Ýòî îçíà÷àåò, ÷òî ~ X m íå íàõîäèòñÿ â «çîíå ïðè- òÿæåíèÿ» òî÷êè ëîêàëüíîãî ìàêñèìóìà � X , åñëè m N� . Ïóñòü ~ � X m — òî÷êà ëîêàëüíîãî ìàêñèìóìà, ïîëó÷åííàÿ èç íà÷àëüíîé òî÷êè ~ X m ïðè ðåøåíèè çàäà÷è (4), (5) . Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà. Òåîðåìà 1. Åñëè m N� , òî � �( ~ ) ( ) � � X Xm � . Äîêàçàòåëüñòâî òåîðåìû àíàëîãè÷íî äîêàçàòåëüñòâó, ïðèâåäåííîìó â [12]. ÑÒÐÀÒÅÃÈß ÐÅØÅÍÈß Ñòðàòåãèÿ ðåøåíèÿ çàäà÷è (2), (3) ñîñòîèò èç ÷åòûðåõ ýòàïîâ: 1) ôîðìèðóåòñÿ íà÷àëüíàÿ òî÷êà è âû÷èñëÿåòñÿ ëîêàëüíûé ìèíèìóì çàäà÷è (2), (3); 2) îñóùå- ñòâëÿåòñÿ ïëàâíûé ïåðåõîä èç îäíîé òî÷êè çàäà÷è (4), (5) â äðóãóþ; 3) óìåíü- øàåòñÿ ðàçìåðíîñòü ïðîñòðàíñòâà ðåøåíèé çàäà÷è (4), (5) (ýòîò ýòàï ðåàëèçî- âàí íà îñíîâå àëãîðèòìà, îïèñàííîãî â ðàáîòå [12]); 4) îñóùåñòâëÿþòñÿ ïåðå- ñòàíîâêè ïàð øàðîâ, ÷òî èíîãäà ïîçâîëÿåò óëó÷øèòü çíà÷åíèå ôóíêöèè öåëè (ýòàï ðåàëèçîâàí àíàëîãè÷íî àëãîðèòìó, îïèñàííîìó â ñòàòüå [13]). 1. Âû÷èñëåíèå ëîêàëüíîãî ìèíèìóìà çàäà÷è. Äëÿ âû÷èñëåíèÿ ëîêàëüíî- ãî ìèíèìóìà çàäà÷è ðàçðàáàòûâàåòñÿ ïîøàãîâàÿ ïðîöåäóðà, âêëþ÷àþùàÿ ðåøå- íèå çàäà÷ (2), (3) è (4), (5). Âíà÷àëå âûáèðàåì çíà÷åíèå � �� 0 , ãàðàíòèðóþùåå óïàêîâêó øàðîâ S i ðà- äèóñîâ �ri , i I� , â êîíòåéíåðå P ( )�0 . Çàòåì ñëó÷àéíî âûáèðàåì òî÷êó X r r� ( , )� 0 òàê, ÷òîáû � �i r P� ( )0 , i I� , è, èñïîëüçóÿ íà÷àëüíóþ òî÷êó X r , ðåøàåì çàäà÷ó (4), (5). Â ðåçóëüòàòå íàõîäèì òî÷êó ëîêàëüíîãî ìèíèìóìà � � � X r� ( , )� . Âñëåä- ñòâèå âûáîðà � �� 0 âñåãäà èìååì �( ) � r � � ( � r r� �� ( � , � � )r r rn1 2 � ). Ýòî îçíà÷àåò, ÷òî ( , ) � � �0 �W . Ïîýòîìó, âçÿâ íà÷àëüíóþ òî÷êó ( , ) � � �0 , ðåøàåì çàäà÷ó (2), (3) è âû÷èñëÿåì íîâóþ òî÷êó ëîêàëüíîãî ìèíèìóìà ( , ) � � � �0 0 . 2. Àëãîðèòì JA. Îñíîâîé àëãîðèòìà JA ÿâëÿåòñÿ òåîðåìà 1. Àëãîðèòì ïî- çâîëÿåò âûïîëíèòü ïëàâíûé ïåðåõîä èç îäíîé òî÷êè ëîêàëüíîãî ìàêñèìóìà çàäà- ÷è (4), (5) ê äðóãîé, â êîòîðîé çíà÷åíèå �( )r âîçðàñòàåò. Ïóñòü ( , ) � � � �0 0 — òî÷êà ëîêàëüíîãî ìèíèìóìà çàäà÷è (2), (3). Âû÷èñëèì r r r ri i i i � � � � �� . � � ( . )05 1 052 2 , i I� , � 0 1, , ... Ïðåäïîëîæèì, ÷òî ðàäèóñû øà- ðîâ ðàâíû ri , i I� . Âìåñòî çàäà÷è (2), (3) ðåøèì çàäà÷ó � � �� min , Y W n� � � �( , )� � R 3 1, (10) W Y x x y y z zn ij i j i j i j i j � �� { : ( , ) ( ) ( ) ( )R 3 1 2 2 2� � � �( ) ,r ri j 2 0 i j I i Ii i � � �, ( , ) , }� � � 0 , �i i � �( , ) � � � � � � � � � � �min{ , , , , ,x r y r z r a x r b y r h z ri i i i i i i i i i i i B i i i i S P P x y z R r P P x }, , ( ) , , min{ åñëè åñëè � � � � � � � � 2 2 2 2 i i i i i i i C i y R r z r h z r P P x 2 2 2 2 � � � � � � � � ( ) , , }, , min{ åñëè � � � � � � � � �y R r x y r z r h z ri i i i i i i i i 2 2 2 2 2( ) , ( ) , , }, � åñëè P P x y z r x y z R r CC i i i i i i i � � � � � � � � � � , min{ ( ) , (2 2 2 2 2 2 2� i SSP P ) }, .2 åñëè � � � � � � � � � ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 101 Ïîñêîëüêó r ri i � , i I� , òî ( , ) � � � � 0 0 �W è ( , ) � � � �0 0 íå ÿâëÿåòñÿ òî÷êîé ëî- êàëüíîãî ìèíèìóìà çàäà÷è (10). Ðåøàåì çàäà÷ó (10) äëÿ íà÷àëüíîé òî÷êè ( , ) � � � �0 0 . Â ðåçóëüòàòå ïîëó÷àåì òî÷êó ëîêàëüíîãî ìèíèìóìà ( , ) �� 0 0 . Òàê êàê rii n �� 1 , òî, ðåøàÿ çàäà÷ó (4), (5) äëÿ íà÷àëüíîé òî÷êè X r D0 0� �( , ) �� , âû÷èñëÿåì òî÷êó ëîêàëüíîãî ìàêñèìóìà � � � X r �� ( , ) . Âîçìîæíû äâà ñëó÷àÿ ïîâåäåíèÿ ôóíêöèè � â òî÷êå � r : �( ) � r �� è �( ) � r � . Åñëè �( ) � r �� , òî � r ri i � � , i I� , è, ñëåäîâàòåëüíî, ( , ) � �� 0 �W (ñì. (3)). Âçÿâ íà÷àëüíóþ òî÷êó ( , ) � �� 0 , ðåøàåì çàäà÷ó (2), (3). Â ðåçóëüòàòå âû÷èñëÿåì íîâóþ òî÷êó ëîêàëüíîãî ìèíèìóìà — ( , ) � � � �1 1 . Â ýòîì ñëó÷àå ñíîâà âû÷èñëÿåò- ñÿ òî÷êà ëîêàëüíîãî ìèíèìóìà ( , ) �� 1 1 çàäà÷è (10) äëÿ íà÷àëüíîé òî÷êè ( , ) � � � �1 1 . Ïðîöåññ ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà íè âûïîëíèòñÿ óñëîâèå �( ) � r � , ò.å. ïîêà ïîñëå k èòåðàöèé íè áóäåì èìåòü � r i n �� 1 , � � � X r �� ( , ) è ( , ) � � � � �W . Åñëè �( ) � r � , òî âû÷èñëÿåì âåêòîð íàèñêîðåéøåãî ïîäúåìà Z 0 â òî÷êå � X äëÿ çàäà÷è (6), (7), îïðåäåëÿåì � m è ñòðîèì òî÷êó X r Dm m m� �( , )� â ñîîòâåòñòâèè ñ (8) è âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòüþ (ñì. (1)) r r r i m i m i m n1 2 � � �.... . Ïîñêîëüêó ìîæåò îêàçàòüñÿ, ÷òî V r V rm( ) ( � )� , òî, èñïîëüçóÿ ýòó ïîñëåäîâàòåëüíîñòü, âû÷èñëÿåì r r r i m i m j j j 0 � min{ , � } , j I� . Ýòî ãàðàíòèðóåò âûïîëíåíèå íåðàâåíñòâà V r V rm( ) ( � )0 � , ãäå r r r rm m m n m0 1 0 2 0 0� ( , )� . Íà îñíî- âàíèè óêàçàííîé ïîñëåäîâàòåëüíîñòè ñòðîèì äâå òî÷êè: ~~ (~ , ~~ )X rm m m� � , ãäå ~� �j m i m j � , ~~r rj m i m j � 0 , è òî÷êó ~ (~ , ~ )X rm m m� � , ãäå ~� �j m i m j � , ~r rj m i m j � , j I� . Åñëè V r V r V rm( � ) (~ ~ ) ( )� � � , òî âû÷èñëÿåòñÿ íîâûé âåêòîð íàèñêîðåéøåãî ïîäúåìà Z 0 â òî÷êå ~ X m äëÿ çàäà÷è (6), (7). Âçÿâ � X X m� ~ , ñòðîèì íîâûå òî÷êè X X Zm m� � � ( / )1 2 0 , ~~ (~ , ~~ )X rm m m� � è ~ (~ , ~ )X rm m m� � è ò.ä. Èòåðàöèîííûé ïðîöåññ ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íè âûïîëíèòñÿ îäíî èç óñëîâèé: V r V rm(~ ~ ) ( � )� èëè V r V r V rm(~ ~ ) ( ) ( � )� � . Åñëè V r V rm(~ ~ ) ( � )� , ò.å. ~~ �r ri m i� , i I� , òîãäà, çàäàâ íà÷àëüíóþ òî÷êó (~ , )� � i m � , ðåøàåì çàäà÷ó (2), (3) è âû÷èñëÿåì íîâóþ òî÷êó ëîêàëüíîãî ìèíèìó- ìà ( , ) � � � �0 0 . Ïðîöåññ ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà íè âûïîëíèòñÿ óñëîâèå V r V r V rm(~ ~ ) ( ) ( � )� � . Â ýòîì ñëó÷àå óâåëè÷èâàåì íà åäèíèöó, è îïèñàííàÿ âûøå ïðîöåäóðà ïîâòîðÿåòñÿ äëÿ íîâîãî çíà÷åíèÿ , ïîêà íè îêàæåòñÿ, ÷òî 05 102 3. � � . (Ñõåìà àëãîðèòìà JA èçîáðàæåíà íà ðèñ. 1.) Äëÿ ïîëó÷åíèÿ õîðîøåãî ïðèáëèæåíèÿ ê ãëîáàëüíîìó ìèíèìóìó çàäà÷è (2), (3) ïîâòîðÿåì � ðàç ïîøàãîâóþ ïðîöåäóðó, ñîñòîÿùóþ èç ïîñòðîåíèÿ íà÷àëü- íîé òî÷êè è ïîèñêà ëîêàëüíîãî ìèíèìóìà çàäà÷è (2), (3) ñ ïîìîùüþ àëãîðèò- ìà JA. Â ðåçóëüòàòå âû÷èñëÿþòñÿ òî÷êè ëîêàëüíûõ ìèíèìóìîâ ( , )* � �t t , t T� � �{ , , ..., }1 2 10� . Çàòåì âûáèðàåì èç íèõ òî÷êó ( , ) � �0 0 , ñîîòâåòñòâóþ- ùóþ çíà÷åíèþ � � min{ , }0 � �t t T . Ýòà òî÷êà âûáèðàåòñÿ â êà÷åñòâå ïðèáëè- æåíèÿ ê ãëîáàëüíîìó ìèíèìóìó çàäà÷è (2), (3). 102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 ×ÈÑËÅÍÍÛÅ ÐÅÇÓËÜÒÀÒÛ Ýôôåêòèâíîñòü àëãîðèòìà JA áûëà ïðîâåðåíà íà ðÿäå òåñòîâûõ ïðèìåðîâ óïà- êîâêè øàðîâ â êóáîèä [3, 5] è â øàð [10]. Êðîìå òîãî, áûëè ðåøåíû ïðèìåðû äëÿ êàæäîãî òèïà êîíòåéíåðà. Pàñ÷åòû ïðîâîäèëèñü íà ïåðñîíàëüíîì êîìïüþ- òåðå ñ ïðîöåññîðîì AMD Athlon 64 X2 6000+ (3.1Ghz). Äëÿ ðåøåíèÿ çàäà÷ (2), (3); (4), (5) è (6), (7) èñïîëüçîâàëèñü ïàêåò ïðîãðàìì Interior Point Optimizer (IPOPT), â êîòîðîì çàäàåòñÿ èíôîðìàöèÿ î ÿêîáèàíàõ è ãåññèàíàõ [14], è êîíöåïöèÿ �-àêòèâíûõ íåðàâåíñòâ [15]. Â òàáë. 1 ïðèâîäèòñÿ ñðàâíèòåëüíàÿ õàðàêòåðèñòèêà àëãîðèòìà JA è äðóãèõ àëãîðèòìîâ [4, 5] äëÿ ãðóïïû ïðèìåðîâ óïàêîâêè øàðîâ â êóáîèä (SYS1–SYS6), âïåðâûå ïðåäñòàâëåííûõ â [3]. Â ïåðâîé êîëîíêå èìååì íàçâàíèå ïðèìåðîâ, à âî âòîðîé — ÷èñëî øàðîâ. Â ñëåäóþùèõ òðåõ êîëîíêàõ ïðåäñòàâëåíû ëó÷øèå çíà- ÷åíèÿ âûñîòû, ïîëó÷åííûå ñ ïîìîùüþ äðóãèõ àëãîðèòìîâ: hBS (àëãîðèòì Birgin è Sobral) [4], hK (àëãîðèòì Kubach è äð.) [5], h�� (àëãîðèòì Hifi è Yousef) [8]. Òàê êàê âðåìÿ ïîäñ÷åòà ñ ïîìîùüþ àëãîðèòìà JA áîëüøå, ÷åì âðåìÿ ïîäñ÷åòà óêàçàííûìè àëãîðèòìàìè, â øåñòîé êîëîíêå ïðèâîäèòñÿ ðåçóëüòàò ïîäñ÷åòà âû- ñîòû h1 àëãîðèòìîì JA çà îäèí ÷àñ. Â ñëåäóþùèõ òðåõ êîëîíêàõ ïðåäñòàâëåíû ðåçóëüòàò ïîäñ÷åòà âûñîòû h0 (äëÿ àëãîðèòìà JA), ëèìèò âðåìåíè ïîäñ÷åòà è ïðîöåíò óëó÷øåíèÿ àëãîðèòìà JA ïî ñðàâíåíèþ ñ ëó÷øèì çíà÷åíèåì âûñîòû, ïîëó÷åííûì äðóãèìè àëãîðèòìàìè. Êàê âèäíî èç òàáë. 1, óëó÷øàþòñÿ ðåçóëüòà- òû äëÿ n � 40 äàæå ïîñëå îäíîãî ÷àñà âû÷èñëåíèé. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 103 Ðèñ. 1. Ñõåìà àëãîðèòìà JA Ðåçóëüòàòû ïîäñ÷åòà äðóãèõ ïðèìåðîâ ìîãóò áûòü çàãðóæåíû ñ âåá-ñòðàíèö: http://f-bit.ru/uploads/250612.zip è http://www.math.tu-dresden.de/~scheith /ABSTRACTS/PREPRINTS/13-spheres.pdf ÇÀÊËÞ×ÅÍÈÅ Èäåÿ ðàññìàòðèâàòü ðàäèóñû øàðîâ â êà÷åñòâå ïåðåìåííûõ ïîçâîëèëà ðàçðà- áîòàòü íîâûé ñïîñîá ðåøåíèÿ çàäà÷è, áëàãîäàðÿ êîòîðîìó óëó÷øåíû èçâåñò- íûå ðåçóëüòàòû. Â àëãîðèòìå JA âûïîëíÿåòñÿ ïëàâíûé ïåðåõîä èç îäíîé òî÷- êè ëîêàëüíîãî ýêñòðåìóìà ê äðóãîé, â êîòîðîé óëó÷øàåòñÿ çíà÷åíèå ôóíêöèè öåëè. Àëãîðèòì îñîáåííî ýôôåêòèâåí, åñëè ðàäèóñû øàðîâ â ïîñëåäîâàòåëü- íîñòè (1) îòëè÷àþòñÿ íåçíà÷èòåëüíî. Óìåíüøåíèå ðàçìåðíîñòè çàäà÷è ïóòåì ôèêñèðîâàíèÿ çíà÷åíèé ðàäèóñîâ øàðîâ ïîçâîëÿåò èíîãäà óëó÷øèòü çíà÷åíèÿ öåëåâîé ôóíêöèè çàäà÷è (2), (3). Ïðåäñòàâëåííûå ÷èñëåííûå ðåçóëüòàòû ïîêà- çûâàþò, ÷òî ïðåäëîæåííûé ïîäõîä áîëåå ýôôåêòèâåí, ÷åì èçâåñòíûå âåðîÿò- íîñòíûå è ýâðèñòè÷åñêèå ìåòîäû. Ðàññìîòðåííûå îïòèìèçàöèîííûå ïîäõîäû è ðàçðàáîòàííûå àëãîðèòìû ìî- ãóò áûòü òàêæå ïðèìåíåíû ïðè ðåøåíèè çàäà÷ óïàêîâêè íåðàâíûõ øàðîâ â êîí- òåéíåðû, êîòîðûå ÿâëÿþòñÿ ìíîãîñâÿçíûìè îãðàíè÷åííûìè ìíîæåñòâàìè. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. C o n w a y J . H . , S l o a n e N . J . A Sphere packings, lattices, and groups. — New York: Springer-Verlag, 1999. — 681 p. 2. S u t o u A . , D a y Y . Global optimization approach to unequal sphere packing problems in 3D // Journal of Optimization Theory and Applications. — 2002. — 114, N 3. — P. 671–694. 3. S t o y a n Y u . , Y a s k o v G . , S c h e i t h a u e r G . Packing of various solid spheres into a parallelepiped // Central European Journal of Operational Research. — 2003. — 11, N 4. — P. 389–407. 4. B i r g i n E . G . , S o b r a l F . N . C . Minimizing the object dimensions in circle and sphere packing problems // Computers & Operations Research. — 2008. — 35. — P. 2357–2375. 5. K u b a c h T . , B o r t f e l d t A . , T i l l i T . , G e h r i n g H . Parallel greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid // Technical Report, Diskussionsbeitrag Nr. 440, Fakult��at f��ur Wirtschaftswissenschaft, FernUniversit��at in Hagen, 2009. — 20 p. 6. K u b a c h T . , B o r t f e l d t A . , T i l l i T . , G e h r i n g H . Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid // Asia Pac. J. Oper. Res. — 2011. — 28, N 6. — P. 739–753. 7. H u a n g W . Q . , L i Y . , A k e b H . , L i C . M . Greedy algorithms for packing unequal circles into a rectangular container // Journal of the Operational Research Society. — 2005. — 56, N 5. — P. 539–548. 8. H i f i M . , Y o u s e f L . Width beam and hill-climbing strategies for the three-dimensional sphere packing problem // In Proceedings of the 2014 Federated Conference on Computer Science and Information Systems, ACSIS. — 2014. — 2. — P. 421– 428. 9. L i u J . , Y a o Y . , Z h e n g Y u . , G e n g H . , Z h o u G . An effective hybrid algorithm for the circles and spheres packing problems // Combinatorial Optimization and Applications. Lecture Notes in Computer Science. — 2009. — 5573. — P. 135–144. 104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 Ò à á ë è ö à 1 . Ñðàâíåíèå ðåçóëüòàòîâ äëÿ ïðèìåðîâ SYS1–SYS6 Íàçâàíèå ïðèìåðà ×èñëî øàðîâ, n Ðåçóëüòàòû ðåøåíèÿ ïðèìåðîâ ñ ïîìîùüþ àëãîðèòìîâ Âðåìÿ, ÷àñ Óëó÷- øåíèå, %hBS hK h�� h1 h*0 SYS1 25 9.7942 9.2656 9.1796 9.4212 9.1604 4 1,1 SYS2 35 – 8.9301 8.8922 8.9957 8.8195 6 1,2 SYS3 40 9.3090 8.7178 8.6702 8.7137 8.4108 8 3,5 SYS4 45 11.0962 10.4042 10.2012 10.2324 9.9288 8 4,6 SYS5 50 11.6211 10.9865 10.8954 10.6505 10.5905 8 3,6 SYS6 60 12.7215 11.8399 11.7943 11.7588 11.5708 8 2,3 10. Z e n g Z . Z . , H u a n g W . Q . , X u R . C . , F u Z . H . An algorithm to packing unequal spheres in a larger sphere // Advanced Materials Research. — 2012. — 546–547. — P. 1464–1469. 11. H i f i M . , M ’ H a l l a h R . A literature review on circle and sphere packing problems: Models and methodologies // Advances in Operations Research. — 2009. — 2009. — 22 p. 12. S t o y a n Y u . , Y a s k o v G . Packing unequal circles into a strip of minimal length with a jump algorithm // Optimization Letters. — 2014. — 8, N 3. — P. 949–970. 13. S t o y a n Y u . G . , Y a s k o v G . N . A mathematical model and a solution method for the problem of placing various-sized circles into a strip // European Journal of Operational Research. — 2004. — 156. — P. 590–600. 14. W ��a c h t e r A . , B i e g l e r L . T . On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming // Mathematical Programming. — 2006. — 106, N 1. — P. 25–57. 15. S t o y a n Y u . G . , Y a s k o v G . N . Packing identical spheres into a cylinder // International Transactions in Operational Research. — 2010. — 17, N 1. — P. 51–70. Íàä³éøëà äî ðåäàêö³¿ 30.11.2015 Þ.Ã. Ñòîÿí, Ã. Øàéòõàóåð, Ã.Ì. ßñüêîâ ÏÀÊÓÂÀÍÍß ÍÅÐ²ÂÍÈÕ ÊÓËÜ Ó Ð²ÇÍ² ÊÎÍÒÅÉÍÅÐÈ Àíîòàö³ÿ. Ðîçãëÿíóòî îïòèì³çàö³éíó çàäà÷ó ïàêóâàííÿ ð³çíèõ êóëü ó êîí- òåéíåðè òèïó êóáî¿ä, êóëÿ, ïðÿìèé êðóãîâèé öèë³íäð, ê³ëüöåâèé öèë³íäð ³ ñôåðè÷íé øàð. Ââàæàºòüñÿ, ùî ðàä³óñè êóëü çì³íí³. Öå äîçâîëÿº çàïðîïî- íóâàòè íîâèé ñïîñ³á îòðèìàííÿ ïî÷àòêîâèõ òî÷îê, ùî íàëåæàòü îáëàñò³ äî- ïóñòèìèõ ðîçâ’ÿçê³â çàäà÷³, à òàêîæ çä³éñíþâàòè ïåðåá³ð ëîêàëüíèõ åêñòðå- ìóì³â, âèêîðèñòîâóþ÷è ìîäèô³êàö³þ àëãîðèòìó JA (jump-àëãîðèòì), ÿêèé ðåàë³çóº ïëàâíèé ïåðåõ³ä â³ä îäíîãî ëîêàëüíîãî ì³í³ìóìó äî ³íøîãî ç êðà- ùèì çíà÷åííÿì ôóíêö³¿ ö³ë³. Çìåíøåííÿ ðîçì³ðíîñò³ çàäà÷³ òà ïîïàðí³ ïåðå- ñòàâëåííÿ êóëü äîçâîëÿþòü ïîêðàùèòè çíà÷åííÿ ôóíêö³¿ ö³ë³. Îòðèìàí³ ðå- çóëüòàòè ïîð³âíþþòüñÿ ç êðàùèìè â³äîìèìè. Êëþ÷îâ³ ñëîâà: ïàêóâàííÿ, ïàêóâàííÿ êóëü, íåîïóêëà çàäà÷à îïòèì³çàö³¿, jump-àëãîðèòì. Yu.G. Stoyan, G. Scheithauer, G.N. Yaskov PACKING NON-EQUAL SPHERES INTO CONTAINERS OF DIFFERENT SHAPES Abstract. The paper considers the optimization problem of packing different solid spheres into containers of types: a cuboid, a sphere, a right circular cylinder, an annular cylinder, and a spherical layer. The radii of spheres are assumed to be variables. This allows us to propose a new technique to derive initial points belonging to the feasible region of the problem, as well as to carry out a non-exhaustive search of local extrema, using a modification of the jump algorithm (JA), which implements a continuous transition from one local minimum to another with a better value of the objective. A reduction of the solution space dimension of the problem and rearrangements of sphere pairs allow improving the objective function value. The results obtained are compared with benchmark ones. Keywords: packing, sphere packing, non-convex optimization problem, jump algorithm. Ñòîÿí Þðèé Ãðèãîðüåâè÷, ÷ëåí-êîððåñïîíäåíò ÍÀÍ Óêðàèíû, äîêòîð òåõí. íàóê, ïðîôåññîð, çàâåäóþùèé îòäåëîì Èíñòèòóòà ïðîáëåì ìàøèíîñòðîåíèÿ èì. À.Í. Ïîäãîðíîãî ÍÀÍ Óêðàèíû, Õàðüêîâ, e-mail: stoyan@ipmach.kharkov.ua. Øàéòõàóåð Ãþíòðàì, Dr., assistant professor, Institute of Numerical Mathematics, Dresden University of Technology, Germany, e-mail: Guntram.Scheithauer@tu-dresden.de. ßñüêîâ Ãåîðãèé Íèêîëàåâè÷, êàíäèäàò òåõí. íàóê, äîöåíò, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà ïðîáëåì ìàøèíîñòðîåíèÿ èì. À.Í. Ïîäãîðíîãî ÍÀÍ Óêðàèíû, Õàðüêîâ, e-mail: yaskov@ukr.net. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 105

Упаковка неравных шаров в различные контейнеры

Institution

Ähnliche Einträge