книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей
..pdfвозможны ситуации, когда некоторые модули нельзя размещать слишком близко (при сближении, скажем, нарушается тепловой режим). При балансировке диска турбины вследствие технологи ческих ограничений иногда необходимо разместить вместе какие-то группы лопаток или зафиксировать некоторые лопатки на опре деленных местах.
Такое «размещение с ограничениями» естественно уменьшает число перестановок, которые нужно просмотреть. Тем не "менее при достаточно больших п это число, чрезвычайно велико.
Задача 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