книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей

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

Такое «размещение с ограничениями» естественно уменьшает число перестановок, которые нужно просмотреть. Тем не "менее при достаточно больших п это число, чрезвычайно велико.

Задача 1.1 в свою очередь может оказаться многоэкстремальной. При этом имеется в виду следующее. Перестановка р0 является ло­ кальной минималью, если существует такая нетривиальная (содер­ жащая отличные от р0 точки) окрестность U перестановки р0, что для всех р £ U справедливо неравенство

f i P o X f (Р)-

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

На рис. 6 показан график функции f (х), на котором точками 1—8 указаны значения, соответствующие перестановкам.

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

1. Задачи являются комбинаторными и с е о д я т с я к просмотру значений функционала на перестановках из п символов.

2. Число этих перестановок настолько велико, что, несмотря на дискретный характер задачи, полный перебор значений не возмо­ жен.

§ 2. Постановка задач размещения геометрических объектов и обсуждение некоторых особенностей этих задач

Методы решения многоэкстремальных задач, изложенные в дан­ ной монографии, первоначально развивались в связи с решением задач размещения геометрических объектов. Ограничимся здесь

21

самым общим изложением некоторых задач размещения геометри­ ческих объектов, отсылая за подробностями к работам [54—56].

В различных отраслях легкой промышленности, в судостроении, авиастроении и в других областях часто встречаются практические

задачи,

которые

можно поставить

ш

ш

т

следующим образом.

W

M M ,

S2

S2

S2

Имеем

несколько

видов

кон­

груэнтных

геометрических объек­

7

Si

Si

Si

тов и набор

областей,

из

которых

их можно вырезать. Задана комп­

s2

Si

Si

лектность,

т. е.

указано,

сколько

фигур

каждого

вида

следует

вы­

Si

$2

Si

i

брать для получения полного ком­

/

S’

плекта фигур. Объекты необходимо

vy,

а

б

расположить в заданных

областях

так, чтобы можно было вырезать

t

максимальное число

комплектов.

П р и м е р.

Пусть область,

в

которой проводится

размещение,

представляет

собой

набор из

че­

тырех

прямоугольников

(рис.

7).

Размещается три вида

фигур:

тре­

угольники, круги и квадраты. Ком­

плект состоит из двух треуголь­

ников, пяти кругов и шести квадра­

тов. Н а рис. 7,а — г показан такой

способ

размещения,

при

котором

Следующая

задача

можно вырезать два комплекта.

размещения имеет

чрезвычайно

широкий

спектр приложений. К ней можно свести задачи центровки при за­ грузке кораблей и самолетов, задачи минимизации длины связы­ вающих сетей в радиоэлектронике и в строительстве, задачи компо­ новки блоков энергетических комплексов и многие другие.

Необходимо в заданной области разместить некоторый набор объектов так, чтобы наилучшим образом удовлетворить некоторым дополнительным требованиям. Такими требованиями могут, на­ пример, быть: минимизация отклонения центра тяжести размещен­ ных объектов от заданной точки, минимизация длины связывающей размещенные объекты сети (электрической, газовой или др.), полу­ чение максимально надежной конструкции или наиболее дешевой и т. д. Не исключаются и такие задачи, когда функция цели содер­ жит в себе комбинацию из любых перечисленных критериев.

В строительстве, энергетике и многих других отраслях часто возникает следующая задача. Разместить заданный набор объектов так, чтобы область, в которой они размещены, обладала какими-то экстремальными свойствами. Так, при разработке генерального плана промышленного предприятия существует набор цехов и про­ изводств, представленных в виде геометрических объектов. Их нужно

22

разместить на плоскости так, чтобы общая площадь, занимаемая предприятием, была минимальной. Более точной оценкой варианта схемы генерального плана можно считать сумму затрат (единовре­ менных, эксплуатационных или приведенных) на территорию и коммуникации. Возможны и другие варианты целевой функции в

виде взвешенной суммы различ­
ных	затрат.
Еще одной аналогичной зада­
чей является			следующая. Имею­
щийся набор			объектов		размес­
тить в полосе заданной ширины
так,	чтобы длина L занятой					ча­
сти	полосы		была наименьшей
(рис.	8).
Общая формальная постанов­
ка задачи размещения п геомет­
рических объектов содержит три
элемента.
1.	Условия взаимного непере-
сечения объектов. Их можно за­
писать в виде —				п (п — 1)		не­
равенств
	М'*/ (■**'>			Фм	Фх	/>	Уr	?ь Ф/> Ф/» 0/) >	0.
				U / =	1,	2, ..	/г,	*’> / ,	(1.5)
где xh yh		zt — координаты полюса (фиксированной точки) объек­
та, а срh		0* — углы, определяющие ориентацию объекта в про­
странстве.		Как известно,			положение твердого тела в пространстве

определяется шестью параметрами. Для того чтобы ограничиться указанным числом неравенств для построения функций pty, опре­ деляющих условия взаимного непересечения объектов сложной геометрической формы, следует использовать ^-функции [45]. Аппарат /^-функций позволяет учитывать размеры объектов, их форму и т. п. Если не прибегать к использованию /^-функций,

то ~ п (п — 1) неравенств достаточно для описания условий взаим­

ного непересечения, например, в том случае, если все размещаемые объекты являются шарами. Для объектов более сложной формы

величина -у (п — 1) п является нижней оценкой числа неравенств,

описывающих условия взаимного непересечения			объектов.
2.	Условия размещения объектов	внутри	области. Их можно
описать с помощью п неравенств вида
	Мч(х£, Ун zi9 ф*, Ф*, 6 t ) > 0,	/ = 1 , 2,	/I.	(1.6).

При этом также можно воспользоваться аппаратом /^-функций.

23

3.	Функцию цели, представляющую собой				функцию	6п пере­
менных
	^ (^1* • • • э	-X/J*	• • • , Уп* ^1» **• »	Ф1*	»• м фв»
	Фг..........Ф„,	01,	. . . , е„) = х (X , У,	Z, Ф,	У, в).	(1.7)

Решение задачи размещения геометрических объектов в такой постановке сводится к определению точки в области G независимых переменных, в которой достигается минимум или максимум функ­ ции х (X , У, Z, Ф, Чг, 0). Область G определяется системой нера­ венств (1.5)—(1.6).

Отметим ряд особенностей, присущих задачам размещения гео­ метрических объектов 154].

1.В общем случае функция цели (1.7) является кусочно-гладкой

ипритом нелинейной на каждом гладком куске.

2. Функции и pi в левых частях неравенств (1.5) и (1.6), как правило, имеют довольно сложное аналитическое выражение, так что, вообще говоря, область G невыпукла.

3.Пространство независимых переменных, в котором проводит­ ся минимизация функции х, является 6я-мерным.

4.Область допустимых решений G определяется не менее, чем

^+ п неравенствами.

5.Каждое неравенство системы (1.5)—(1.6) связывает не более чем 12 переменных.

6.Поставленная задача является многоэкстремальной, причем экстремумы могут достигаться как во внутренних точках области G, так и на ее границах.

7.Если ограничения на наибольшие расстояния между объек­ тами не накладываются, то количество локальных минимумов не

меньше п\ Простое перечисление особенностей задач размещения позволя­

ет сделать вывод о том, что применение известных методов оптими­ зации для их решения невозможно или крайне неэффективно. В частности, метод градиентного спуска при решении задач размеще­ ния использовать нельзя. Это связано с тем, что как целевая функ­ ция, так и левые части неравенств (1.5)—(1.6) представляются недифференцируемыми функциями. Чтоже касается применения традиционных способов случайного поиска, то они крайне неэф­ фективны. Дело в том, что при случайной генерации точки из бл-мерного пространства вероятность получения точки из области G обычно очень мала.

Заметим еще, что вследствие многоэкстремальности задач разме­ щения геометрических объектов решение естественно распадается на два этапа: определение локальных экстремумов функции цели и организация их перебора.

24

§ 3. Способ последовательно-одиночного размещения

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

Проблема точного построения локальных минимумов становится актуальной, когда определены начальные точки для построения лучших локальных минимумов. В этом параграфе ограничимся построением приближений к локальным минимумам. Для этого используем метод последовательно-одиночного размещения [56, 64], представляющий собой модификацию метода Гаусса — Зайде­ ля или, точнее, метода частичного улучшения по группам пере­ менных [18]. Изложим суть указанных методов и обсудим их до­ стоинства и недостатки [561.

Пусть задана функция многих переменных F (х,, х2, .... хп), ми­ нимум которой необходимо найти. Процедура оптимизации функ­ ции F (xlt х2, .... хп) по методу Гаусса — Зайделя состоит в после­ довательной циклической минимизации функции по каждой из переменных хх, х2.......хп. При обычном методе поочередного изме­ нения переменных у оптимизируемой функции F (х1г х2, ..., хп) фик­ сируются все переменные, кроме одной, например, хх. Это значит, что F (хх, хг, ..., х~) является функцией одной переменной xlt ос­

тальные же переменные остаются неизменными:				X/ — const (J Ф
Ф 1), Находится значение х? переменной хг такое, что
F (xi, х3,	• • •, xn) =	min F (Xj, х2, • • .,		х„),
		*,£0
где G — область допустимых значений			переменных, определяемая
некоторой системой неравенств
f i (х^, х2,	• • *, х^] ^	0, i	= 1, 2, . . . ,	tti.
Далее фиксируется значение x i		и значения переменных х3, х4, ...,х".
Находится такое значение х® переменной Хг, что
F(x1, 4 ,	*Л) = m in/7(я?, *2, ... » *я),

И т. д.

Первый цикл ^читается законченным, если найдены все значе­ ния переменных х°, xj>, .... х°, каждое из которых в отдельности

25

оптимизирует исходную функцию F (хъ х2, ..., хп). После этого на­ чинается следующий цикл, т. е. фиксируются все переменные, кро­

ме Хи и находится значение х\ переменной х? такое, что

F(x1, х\, . . . , х% = minF (xv х\, . . . . хйп), х,ео

Ит. д.

Вболее общей постановке метод Гаусса — Зайделя (метод час­

тичного улучшения по группам переменных) формулируется следую­

щим образом		[18].
Существует функция F (Хъ Х2, ...,ХЯ), зависящая от п векторов
Хъ X2t	ХпУ каждый из которых имеет размерность sl9 s2,					sn
соответственно,		т. е.
	X, =	4°, . . . . 4;')	(/ =	1 , 2 , . . . ,	л).
Пусть	Gt — замкнутое ограниченное			множество	в Sj-мерном

пространстве, характеризующее область допустимых значений век­

тора X,-. Положим, что	функция	F (Хъ Х 2, ..., Х п) определена
в области, содержащей	множество
G =	х G2 х	• • • X <?„,

где знаком умножения обозначено прямое (декартово) произведение множеств.

Необходимо найти
min F (Х1У Х2..........Х п), Xt £Gi,	/ = 1, 2, . . . , л.
Будем считать, что при фиксированных значениях		векторов
Хх, Х2, ..., Xi—1, Xi+\, ..., Х п существует достаточно простой спо­
соб нахождения минимума функции одной переменной X,-
F(Xlt Х2, . . . . Z - n Х„	Z + t..........*„)•	(1.8)
Для нахождения минимального значения исходной		функции
F (Хи Х2, ..., Х„) используется следующая процедура. Произволь­

но выбираются значения	векторов X t — Xj0) (/ = 1, 2.......л) при
условии
X f e G ,	( / = 1, 2, . . . . л).

Соответствующим образом находится вектор Х)1*, являющийся ре-

шением	задачи минимизации функции (1.8) при		i = 1,
(k Ф 1). Далее определяется вектор Х ^ £ (?2, при			котором функ­
ция F (Х\1\ Х2, Хз0)........ Х^0)) принимает минимальное значение,
и т. д.	Таким образом находится система векторов			Х)1*, Х ^, ...
Х ^,	на основании которой определяются векторы			X f \	Х®, ...
Х(„2). В общем случае нахождение вектора X*+i		сводится			к реше­
нию задачи минимизации функции (1.8) при / =		г -f- 1 и

| Xjf>,

k ~ \ x t l\ k > r + 2.

26

В работе [18] доказана сходимость такого процесса, т. е. пока­ зано, что последовательность значений Ft = F (Xf, Х 21, ...

.... Х%) не увеличивается с ростом t и, кроме того, стремится к ми­ нимуму функции F (Х1э Хг........ Х„) при условии Х ( £ G ( / == 1,

2, ..., п).

Достоинством метода Гаусса — Зайделя является прежде всего простота его практической реализации. Наиболее эффективно при­ менение метода к оптимизации сепарабельных (или близких к ним) функций, т. е. к таким функциям, в которых отсутствует перекрест­ ное влияние переменных. Как пример сепарабельной функции можно рассматривать эллиптическую функцию

П

F (хъ хг, . . . . хп) = Г * + £ а,- (х{— x 'f.

i—\

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

Однако помимо перечисленных достоинств метод Гаусса — Зай­ деля обладает рядом недостатков, снижающим его практическую ценность.

Во-первых, неудобство метода заключается в его зависимости от выбора системы координат. Например, для квадратичной функ­ ции двух переменных с эллипсовидными линиями уровня нахож­ дение минимума функции осуществляется за один цикл, если оси координат параллельны осям эллипсов уровня. В противном случае оптимизация сводится к бесконечной последовательности циклов.

Во-вторых, применение метода поочередного изменения пере­ менных связано с большими трудностями при оптимизации несепа­ рабельных функций, а также при наличии ограничений. В этих случаях с помощью данного метода можно вообще не найти точного решения. Кроме того, при использовании метода Гаусса — Зайделя довольно часто попадаем в «ловушку». Одной из таких «ловушек» является так называемый овраг с острым дном. Например, функция вида

F (*!, х2) = -i- 1*1 + * 2 I + | * 1 — * 2 I

имеет такой овраг, дно которого совпадает с прямой xt = лг2. Если в процессе оптимизации на некотором цикле точка попадает на линию хх = хг (на дно оврага), то метод не разрешает данную проб­ лему.

Способ последовательно-одиночного размещения геометрических объектов является некоторой разновидностью описанного выше метода частичного улучшения по группам переменных (метода Гаус­ са — Зайделя).

27

Подробное изложение метода последовательно-одиночного раз­ мещения можно найти в работах [54, 56]. Здесь же ограничимся рассмотрением одного частного случая.

Пусть задана плоская область Q, в которой размещаются плос­ кие объекты Ти Тг, ..., Т п, сохраняющие постоянную ориентацию (рис. 9). В этом случае функция цели (1.7) принимает вид

^ (^1» l/l*

^2» • • • »

Уп)>

где xit yt— координаты полюса i-ro объекта. В данном случае два числа полностью определяют положение объекта.

Первый объект размещаем таким образом, чтобы минимизиро­ вать функцию цели, т. е. находим такие числа х* и у\, что

и (*Г, у\) < х (х1г ус), (xit yJtGc.

Здесь Gi — область, которую может занимать полюс первого объек­ та при условии, что объект полностью лежит в области Q. Весь­ ма существенно наличие эффективных способов определения облас­ ти Gj. Именно это обстоятельство и предопределяет высокую эффек­ тивность метода последовательно-одиночного размещения в задачах размещения геометрических объектов.

Для построения области Gx нет необходимости решать неравен­ ство типа (1.5)—(1.6). Вместо этого используется аппарат годо­ графов вектор-функций плотного размещения. Точное определение понятия годографа содержится в работе [561. Здесь же назовем годо­ графом замкнутую линию, ограничивающую область возможных положений первого объекта. Годограф Yi первого объекта относи­ тельно области £2 показан на рис. 10.

После выбора положения первого объекта размещаем второй объект. Область его размещения Ga определяется с помощью годо­ графов второго объекта относительно области Q и относительно объекта 7\, который считается неподвижным. Полюс второго объек­

та размещается в точке (xj, yl) такой, что

х (х \ Уи *2, у\) < х (*i, Уи *2, у2)

(х2, у2) € Ga.

Вообще, при размещении k-ro объекта положение предыдущих объ­ ектов считается фиксированным, и параметры его размещения вы­ бираются такими, чтобы выполнялось условие

^ (^1 > {/it	* • • I	Xk—l , Ук—\ , 'Xky	Ук) ^ ^	(X l, yit » • i
• • • ,	Xb~l t	Ук—11 Xfr Уkit	(Xkt	Ук) €

где Gk — область возможного размещения k-ro объекта. Рассмотрим следующий пример. Пусть область размещения Q

представляет собой полосу шириной L, а размещается четыре объек­ та — круги радиусов гх, г2, г3 и г4. Объекты нужно разместить так, чтобы длина занятой части была минимальной.

Систему координат выберем как показано на рис. 11, а в каче­ стве полюсов объектов — центры кругов. Тогда функция цели при­ нимает вид

и = max (хс + г()	(1.9)
i

{xt и yt — координаты полюса /-го объекта). Параметр yt не вхо­ дит в функцию цели, хотя и входит в систему ограничений, описы­ вающую область возможных решений. Условия принадлежности области Q в данном случае можно представить в виде следующей

29

системы неравенств:
’ x i — гt > 0,		i =	1,	2,	3,	4,
Уь — ri > 0,		i =	l,	2,	3,	4,		(1.10)
„^	(f/f 4“ ^*i) ^ 0,		^ ==		1, 2, 3,		4.
Условия взаимного непересечения имеют вид
(xt — Xff + (yt — yj)2> (rt + r,)2,				*,	/ =	1, 2,	3,	4, i > /.
В соответствии с методом последовательно-одиночного размеще­
ния первый круг установим		таким образом, чтобы функция к (Xj)
приняла минимальное значение.
Поэтому целевая функция (1.9) принимает минимальное зна­
чение при		*? = /!.						(1.11)
Годограф уг первого	объекта	относительно				полосы		показан на

рис. 11, а. Вторую координату можно выбирать произвольно в пре­ делах от гх до L — гх. Для определенности дополним список тре­ бований таким: помещать объект в нижнее из положений с равными первыми координатами. Тогда

У* =* rv

Заметим, что для установки первого объекта не было необходимос­ ти пользоваться годографом. Можно было воспользоваться нера­ венствами (1.10), которые в данном случае сводятся к следующим:

> г 19 < #i < L — гг.

(1.12)

Существенно, что при экстремальном значении функции (1.11) пер­ вое из неравенств (1.12) обращается в равенство. Таким образом, минимум достигается на границе области допустимых решений.

Для установки второго объекта нужно построить его годограф относительно полосы и первого объекта. Этот годограф у2 изобра­ жен на рис. 11, б. Полюс второго объекта выбирается в точке 02. Заметим, что в аналитической постановке задача выглядит доста­ точно сложно. Именно, нужно найти минимальное значение коор­ динаты х2, ПРИ котором

*2 ^ Г2> ^2 ^ Уг ^

Г2>

(х2— rxf + (yz — rx)2 > (rx + ra)2.

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

Годографы уд и у4 для третьего и четвертого объектов показаны на рис. 11, в и 11, г. Окончательное размещение кругов по методу последовательно-одиночного размещения представлено на рис. 11, г.

80