книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей
..pdfАКАДЕМИЯ НАУК УКРАИНСКОЙ ССР
ИНСТИТУТ ПРОБЛЕМ МАШИНОСТРОЕНИЯ
ю .г . с т о я н
В.3.С О К О Л О В С К И Й
РЕШЕНИЕ НЕКОТОРЫХ МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ МЕТОДОМ СУЖАЮЩИХСЯ ОКРЕСТНОСТЕЙ
КИЕВ «НАУКОВА ДУМКА» 1980
УДК 62—50 : 519.2
Решение некоторых многоэкстремальных задач методом сужа ющихся окрестностей / Стоян Ю. Г., Соколовский В. 3 .— Киев : На ук. думка, 1980.“ 208 с.
Предлагается новый подход к решению широкого круга опти мизационных задач, которые встречаются в практике автоматизации проектирования и имеют важное народнохозяйственное значение. Рассматриваемые задачи возникают практически на всех уровнях принятия проектных решений. Показано, что решение многих за дач — размещения геометрических объектов, уравновешивания вра
щающихся частей |
машин, календарного планирования и других — |
|
сводится к выбору |
наилучшего |
значения функционала, заданно |
го на множестве перестановок. |
Все теоретические выводы под |
|
крепляются большим количеством численных примеров, связан ных с минимизацией конкретных функционалов. Предлагаемые ме тоды решения задач оптимизации представлены в виде подробных алгоритмов и текстов программ на языке ФОРТРАН. Это позволяет использовать результаты исследований непосредственно в практике.
Предназначена для математиков, |
инженеров, конструкторов |
|
и технологов, занятых проектированием |
сложных технических |
сис |
тем в строительстве, авиастроении, турбостроении, химической |
про |
|
мышленности, экономике, радиоэлектронике, легкой промышлен ности, а также для студентов и аспирантов, специализирующихся по прикладной математике и технической кибернетике.
Ил. 1—54. Табл. 1—27. Список лит.: с. 201—204 (86 назв).
Ответственный редактор И. В. С е р г и е н к о
Рецензенты В. Л . Р в а ч е в, В. А. Щ е р б и н а , Ю. В. Г а н д е л ь
Редакция физико-математической литературы
„20204-462
СM22l704H(. 165-80' 1702070000
@ Издательство «Наукова думка», 1980
ПРЕДИСЛОВИЕ
Слова П. Л. Чебышева о том, что «...общая и важнейшая для всей практической деятельности человека мысль: как располагать средствами своими для достижения по возможности большей вы годы» на современном этапе развития науки подчеркивают необ ходимость разработки и использования оптимизационных методов для решения различных прикладных задач.
Существующие математические методы оптимизации позволя ют решать достаточно широкий класс народнохозяйственных за дач, связанных с экономикой, планированием, технологией, разра боткой и функционированием АСУ, проектированием и т. д. Одна ко задачи дискретно-континуальной оптимизации при всей их важности вследствие некоторых трудностей, в том числе постано вочного плана (отсутствие адекватных математических моделей), остаются малоизученными.
Поэтому авторы данной книги считают, что необходимо си стематическое изложение методов, алгоритмов и программ реше ния такого класса задач, которые разработаны в последние годы в Институте проблем машиностроения АН УССР.
Предлагаемый в данной книге метод сужающихся окрестностей первоначально разрабатывался в связи с задачами размещения гео метрических объектов. При решении этих задач возникала необхо димость в организации перебора многочисленных локальных экстре мумов, однако приемлемых способов такого перебора не сущест вовало.
Дальнейшие исследования расширили рамки применения метода сужающихся окрестностей. Оказалось, что его можно использовать для решения разнообразных задач, среди которых размещение гео метрических объектов занимает некоторое промежуточное поло жение.
Наиболее «простыми» являются задачи, в которых необходимо оптимизировать функционал, заданный на множестве всех возмож ных перестановок (гл. 1, § 1; гл. 4, §1, 3, 4). Затем следуют задачи, в которых наложены ограничения на рассматриваемые перестановки (гл. 1, § 1; гл. 4, § 2), и задачи, в которых удается установить взаимно
3
однозначное соответствие между перестановками и локальными эк стремумами. Именно к последнему классу относятся задачи разме щения геометрических объектов (гл. 1, §2 —4; гл. 4, § 6 —8). Нако нец, назовем задачи континуальной минимизации, которые не* сводятся к дискретной модели (гл. 5), и притом такие, что для их решения целесообразно использовать метод сужающихся окрестно стей, поскольку они сохраняют некоторое сходство с упомянутыми выше задачами.
Все отмеченное выше послужило толчком к написанию данной книги и вселяет надежду, что класс задач, решаемых рассматривае мым методом, можно значительно расширить, а сам метод решения улучшить как с точки зрения скорости решения, так и точности по лучаемых решений.
В работе над книгой большую помощь оказал авторам Л. Д . По номаренко, который написал § 3, 4 гл. 2 и сделал существенные за мечания по содержанию ряда глав, а также принял участие в под борке литературы. В. Н. Литвинов и В. Г. Ещенко произвели необходимые вычисления по задачам в гл. 4, § 6 и 5 соответственно,
Н.И. Гиль и Е. Б. Яловкина сделали ряд существенных исправлений
изамечаний, С. В. Яковлев активно участвовал в программной реа лизации предложенных алгоритмов и проведении численных экспе риментов. Всем им авторы выражают глубокую признательность.
Ценные замечания и ряд интересных предложений сделаны ре цензентами В. Л. Рвачевым, КХ В, Ганделем и В. А. Щербиной. Ав торы выражают им искреннюю и сердечную благодарность.
ВВЕДЕНИЕ
1. За последние десятилетия роль математики в проектирова нии и планировании существенно изменилась. Раньше инженер на основе своей технической интуиции предлагал варианты новых конструкций, и вычисления по известным формулам использова лись для проверки пригодности этих вариантов и сравнения их достоинств. На современном этапе одной из основных в технических науках стала проблема оптимизации. Это связано с повсеместным переходом к автоматизированным системам проектирования, а также с усложнением и удорожанием проектируемых конструкций.
•Как отмечает Д. Дж. Уайлд, «совершенно очевидно, что опти мизация, т. е. нахождение способов делать все наилучшим образом, должна интересовать практичных представителей промышленности, торговли и политики. Ведь в любом предприятии, большом или ма лом, подчас незначительная разница в результатах может привести от процветания к краху» [65].
Может показаться, что в классической математике уже существу ет аппарат для решения задач оптимизации — дифференциальное
ивариационное исчисления. Выяснилось, однако, что применение вариационных методов даже в сравнительно простых технических
иэкономических задачах вызывает принципиальные трудности [3].
Линейное и выпуклое программирование [19, 20, 47], принцип максимума Понтрягина [33], динамическое программирование [2, 3], случайный поиск [35, 44] — таков далеко не полный список нетрадиционных методов минимизации. Новые методы помогли устранить многие возникающие трудности (или «проклятия», если пользоваться терминологией Р. Веллмана [2]).
Меньше всего в этом смысле повезло многоэкстремальным зада чам. Часто они просто не рассматривались специалистами по опти мизации. Так, в книге [65] говорится: «Мы оставили в стороне муль тимодальные, или многоэкстремальные задачи, так как их исследо вание пока не дало существенных результатов. Будем надеяться, что вскоре появятся специальные методы решения этих задач».
• Авторы пытаются внести свой вклад в борьбу с «проклятием многоэкстремальности» и предлагают методы, которые позволяют найти
5
удовлетворительные решения для некоторых классов многоэкстре мальных задач.
2. |
Прежде чем описать эти классы задач, остановимся на понятии |
|
экстремума и уточним смысл, который вкладывается в слово «много |
||
экстремальный». |
|
|
Рассмотрим функционал /, который отображает множество X |
||
из метрического пространства во |
множество вещественных чисел |
|
|
f : X |
R. |
Будем говорить, что точка х0 является локальной минималыо функционала /, если существует такое положительное число е, что для всех точек х, удовлетворяющих условию
Р (X, х0) < 8, |
(1) |
справедливо неравенство |
|
/(* 0) < /(* ) . |
(2) |
Здесь р (*, •) — функция расстояния между элементами множества X. Число / (х0) называется локальным минимумом функционала /.
Будем говорить, что точка х0 является глобальной минималью функционала /, если для всех точек х, принадлежащих множеству
X, выполняется неравенство |
|
/ (*0) < / (*)- |
(3) |
Число / (хг0) называется глобальным минимумом функционала /. •Заметим, что используемая здесь терминология не является об щепринятой. К ней пришлось обратиться для того, чтобы под черкнуть разницу между точкой области определения, в которой достигается минимум, и самим минимумом, который является чис лом. Термин «минималь» заимствован из работы [21 ] и выбран по аналогии с понятием «экстремали» — функции, вдоль которой вы
полняется уравнение Эйлера.
-В книге рассматриваются лишь задачи минимизации. Это ограни чение не существенно, поскольку поиск максимума функционала / эквивалентен поиску минимума функционала —/.
•Интерпретируем введенную терминологию для простейшего случая, когда в качестве множества X используется сегмент [а, 61. Функционал / при этом сводится к функции^одной переменной. График ее изображен на рис. 1. Точки хи х2 и х3 = 6 являются локальными минималями, а числа / (xj, / (х2) и / (х3) — локальными минимумами. При этом х2есть глобальная минималь, а / (х2) — гло бальный минимум.
Отметим также, что в качестве множества X всюду выбирается компакт, т. е. замкнутое ограниченное подмножество метрического пространства. Все точки компакта можно разделить на внутренние точки и границу.
Точка х компакта X называется внутренней, если существует такое положительное число е, что все точки **, для которых выпол-
«
няется неравенство
р (х, .г*) < е,
принадлежат множеству X.
Точка х, принадлежащая компакту X, называется граничной, если в любой ее окрестности найдутся точки, не принадлежащие ком пакту.
Рие. 1.
В связи с этим минимали можно делить на такие, которые нахо дятся во внутренности [26] области X, и такие, которые расположе ны на границе. Если минималь является внутренней точкой, то соот ветствующий минимум называется абсолютным, а если минималь лежит на границе, то минимум называется относительным.
Такая классификация отражает существенную разницу в «про исхождении» абсолютных и относительных минимумов. Дело в том,
что область определения функционала f, как правило, шире области, в которой ищутся минимали. Для примера рассмотрим функции од ной переменной. Пусть функция f {х) имеет график, представленный на рис. 2. Областью определения этой функции является сегмент [а, о]. Допустим, что минимум функции f (х) ищется на сегменте [с, й]. Локальный минимум f (d) является относительным, a f (е) —
^абсолютным. Какой бы ни была область, в которой определяется
7
минимум функций / (*), точка е будет минималью, если она войдет в эту область. Напротив, точка d будет минималью только в том случае, когда она принадлежит границе области, в которой ищется минимум*
Таким образом, абсолютные минимумы определяются только свойствами минимизируемого функционала и не зависят от области,
вкоторой определяются минимумы (они могут лишь выпасть из рассмотрения). Относительные минимумы тесно связаны с областью,
вкоторой ищутся минимумы, поскольку соответствующие минимали находятся на границе этой области.
Заметим, что в неравенствах (2) и (3) используются знаки нестро гих неравенств. Поэтому иногда соответствующие минимумы назы вают нестрогими. Строгие минимумы можно определить следующим образом.
Число / (х0) называется строгим локальным минимумом функ
ционала / (х), если для всех точек х> удовлетворяющих условию (/), за исключением точки x0f справедливо неравенство
f (х0) <f(x).
Будем говорить, что f (д:0) — строгий глобальный минимум, если для всех точек х, принадлежащих X, кроме точки х01 справед ливо неравенство
/(*о) < f (X).
3.Уточним, какой смысл вкладывается здесь в слова «многоэк стремальные задачи». Дело в том, что этот термин можно понимать по-разному. Так, Уайлд [65] делит экстремальные задачи на унимо дальные (одноэкстремальные) и мультимодальные (многоэкстре мальные). В такой классификации задача с двумя экстремумами от носится к многоэкстремальным.
В данной книге предлагаются методы решения таких задач, у которых локальных экстремумов «очень» много [6, 38, 70, 71 ].
Предметом рассмотрения являются такие задачи оптимизации, в которых сравнительно просто найти локальные минимумы, однако полный их перебор не осуществим. Понятия простоты и осуществи мости тесно связаны с машинными методами решения. Речь идет о задачах, в которых локальные минимумы (или приближения к ним) находятся с помощью ЭЦВМ. Считается, что локальный мини мум определяется просто, если на это уходит достаточно мало вре мени. Неосуществимость полного перебора означает, что за «разум ное» время на ЭЦВМ нельзя перебрать все экстремумы.
Число практических задач, многоэкстремальных в указанном смысле, достаточно велико. Заметим, что при таком подходе многоэкстремальность связана с возможностями ЭЦВМ. С развитием вы числительной техники, увеличением быстродействия и памяти ЭЦВМ, а также с разработкой новых математических методов ло кальной оптимизации увеличивается число задач, в которых не сложно найти локальные минимумы. Между тем, количество этих
8
минимумов обычно столь велико, что даже самые смелые гипотезы о перспективах развития вычислительной техники не позволяют надеяться на то, что полный перебор удастся провести за приемлемое время (подробнее об этом см. в § 1 главы 3).
Таким образом, речь идет о задачах, в которых количество ло кальных экстремумов предполагается настолько большим, что к задаче их перебора допустйм вероятностный подход. Имеется в виду, что получение различных локальных экстремумов можно рассмат ривать как независимые испытания и, кроме того, эти экстремумы представляют собой такое множество элементарных событий, где
справедлив закон |
больших чисел [14, 32]. |
|
4. |
В связи |
со сказанным напомним некоторые определения из |
теории вероятностей и математической статистики [28].
Пусть имеем некоторый случайный эксперимент, который можно повторить большое число раз при неизменных условиях. Будем пред полагать, что результат каждого отдельного эксперимента задается некоторой действительной величиной g. Переменная точка g назы вается случайной величиной.
В рассматриваемой задаче случайный эксперимент |
состоит |
в следующем. Случайным образом выбирается точка х £ X. |
Затем |
ищется локальная минималь, ближайшая к точке х. Величина соот ветствующего минимума и будет переменной точкой на веществен ной оси.
Рассмотрим некоторое точечное множество S в пространстве У?. Пусть событие g £ 5 может произойти либо не произойти при каж дом отдельном осуществлении эксперимента. Слова «вероятность события S в эксперименте равняется Р» означают следующее: прак тически несомненно, что частота события 5 в длинном ряду пов торений да ного эксперимента приблизительно равна Р.
Таким образом, вероятность события интерпретируется с частот ной точки зрения, что существенно используется далее.
Пусть заданы две случайные величины g и т) и два множества 5 и Т в пространстве R. Условной вероятностью события г) £ 7* при условии g £ S называется число
|
P ( 4 £ T \U S ) = |
P & F S , J\ £ T ) |
|
|
|
P&(zS) |
|
Если для любых множеств S и Т удовлетворяется условие муль |
|||
типликативности |
|
|
|
|
p ( t t s 9 л е г ) = p g ^ s ) p (лег), |
||
то будем говорить, что g и г] — независимые |
случайные величины |
||
и что события g £ S и т] £ Т суть независимые |
события. |
||
Рассмотрим |
функцию множества Р (S) и соответствующую не |
||
убывающую, всюду непрерывную справа функцию точки F (х). Если |
|||
эти функции |
такие, что |
|
|
F (х) = Р (С < X),
9
0 < F W < 1 ,
F (— oo) = 0, F (+oo) = 1,
то функцию P (S) будем называть вероятностной функцией распреде ления, а функцию F (л:) — функцией распределения для случайной величины
Если функция распределения дифференцируема, то ее произ водная р (х) = Р' (х) называется плотностью вероятности.
Рассмотрим случайную величину | с функцией распределения
00
F (х). Интеграл j xdF (х) называется средним значением или мате- —оо
матическим ожиданием случайной величины £. Математическое ожидание величины Е будем обозначать угловыми скобками
оо
<£> = J xdF (х).
—оо
В случае распределения дискретного типа среднее значение сво дится к конечной или бесконечной сумме
<£> = S р а .
к
а для распределений непрерывного типа — к интегралу
оо
<£) = \xp{x)dx.
— оо
Через d (g) будем обозначать дисперсию случайной величины gv d(D = a i - ( D f) .
5. Укажем причины, по которым многие практические задачи оптимизации имеют такое большое число локальных экстремумов, что можно говорить о законе их распределения.
Первая причина связана с «проклятием многомерности» [2], из которого очень часто следует «проклятие многоэкстремальности» (представляется, что сложности, связанные с огромным количеством экстремумов, настолько велики, что выражение Веллмана здесь вполне уместно).
Вторая причина объясняется сложной формой области, в которой ищется минимум. С этим связано появление большого числа относи тельных локальных экстремумов.
Известен широкий класс практических задач, решение которых сводится к минимизации функционалов, заданных на множестве перестановок. Речь идет о задачах построения кратчайших связы вающих сетей [69], задачах уравновешивания вращающихся час тей [5] и некоторых задачах календарного планирования [15, 22].
Еще одним важным классом задач, для решения которых ис пользуется минимизация в пространстве перестановок, является
10