Адиабатическое условие р Стекло (нет теплопереноса через край) г-1 -

Алюминий

Адиабатическое условие (нет теплопереноса через край)

Скругление \ /о 2 радиусом 0.2 \ Ri = 0 1 R0 = 0.2

Получите решение для окна из задачи 2, к которому приложена нагрузка в соответствии с приведенным ниже рисунком. Постройте распределение температуры.

Внешняя атмосфера

Температура = 0°F Коэффициент теплопереноса = 0,0347 BTU/hr-in2-°F

Внешние

Внутренняя атмосфера

Температура = 70°F Коэффициент теплопереноса = 0,0139

4. Постройте модель втулки, показанной на рисунке, и выполните статический анализ методом конечных элементов. Модель можно построить из трех примитивов, например цилиндра, призмы и кирпича, соединив их двумя булевскими операциями. Все размеры указаны в дюймах.

О радиус цилиндра: 0,55; О длина цилиндра: 2,0; О сила: 100 фунтов.

Глава 9

Оптимизация

Оптимизация, как мы говорили в главе 1, - это один из этапов процесса разработки, то есть часть жизненного цикла продукта, а потому технологии оптимизации также относят к средствам автоматизированного проектирования. В принципе, весь процесс проектирования можно считать оптимизацией, потому что в этом процессе создается несколько альтернативных проектов, из которых выбирается один лучший. Это утверждение становится верным, если понимать слово оптимизация в очень широком смысле. Однако обычно под оптимизацией понимается не выбор одной из нескольких альтернатив (таких, например, как заклепка, болт и скоба), а скорее, выбор оптимального размера одной из них (например, заклепки). Понимаемая в этом смысле оптимизация уже является частью процесса проектирования, а не самим этим процессом.

9.1. Постановка задачи

Оптимизация конструкции требует ее параметризации, дающей возможность рассматривать альтернативные конструкции, изменяя значения параметров. Например, при разработке цилиндрического сосуда для хранения газов под давлением параметрами были бы средний диаметр, толщина, высота и используемый материал. Различные наборы значений параметров будут давать разные сосуды. В зависимости от ситуации .некоторые параметры могут не иметь степеней свободы из-за ограничений. Например, у нас может быть только один материал, так что для оптимизации сосуда остались бы только средний диаметр, толщина и высота. Мерой качества сосуда может быть максимально допустимое давление, поделенное на вес. Средний диаметр, толщина и высота будут варьируемыми параметрами конструкции. Можно попытаться найти оптимальное сочетание параметров, которое приведет к максимальному значению показателя качества. Показатель качества может быть выражен в виде функции параметров, если мы воспользуемся знаниями, полученными при изучении сопротивления материалов. Оптимизируемые параметры называются переменными оптимизации (optimization variables), а показатель качества, вычисляемый по этим переменным, называется целевой функцией (objective function). Очевидно, что переменные оптимизации и целевая функция выбираются конструктором в соответствии с тем, для чего предназначается его творение.

Оптимизацию конструкции можно описать на математическом языке. Обозначив переменные оптимизации символом X (n-мерный вектор, компонентами которого являются переменные оптимизации), а целевую функцию символом F(X), мы можем записать задачу просто: минимизировать (максимизировать) F(X).

Однако реальный процесс оптимизации от этого не упростится. Очень редко показатель качества задачи может быть выражен одной-единственной целевой функцией. Чаще всего приходится выбирать между разными показателями или строить объединенный показатель с какими-либо весовыми коэффициентами. Этот процесс называется построением сложной целевой функции (composite objective function). Мы можем использовать некоторые показатели качества как ограничения. Например, вместо того чтобы максимизировать допустимое давление на единицу веса и внутренний объем сосуда одновременно, мы можем ограничить объем некоторым минимальным значением, а максимальности потребовать только от давления на единицу веса. В этом случае ограничения придется каким-то образом включить в математическую формулировку задачи (ниже мы покажем, как это делается).

Можно ожидать, что в большинстве случаев переменные оптимизации будут иметь ограниченную область определения. Например, высота сосуда не может превышать определенного значения из-за ограниченности высоты помещения. Поэтому вектор X должен удовлетворять определенным требованиям. Компонентами вектора, разумеется, являются переменные оптимизации. Проект, удовлетворяющий всем требованиям, называется приемлемым (feasible design или acceptable design). Ограничение, задающее верхнюю или нижнюю границы области определения переменной оптимизации, называется ограничением области (regional constraint или side constraint). Ограничение, выведенное из явного рассмотрения функционального требования или показателя качества, называется функциональным, или поведенческим, ограничением (functional, behavior constraint).

С учетом ограничений простая задача оптимизации может быть записана следующим образом: найти

X е Л , такой что F(X) = minF(X) (9.1)

при условии, что

X, <Х-<Х„; (9.2)

G,(X*)>0 t = l,2.....т; (9.3)

Я,.(Х*) = 0 j = l,2,...q, (9.4)

где т - количество ограничений-неравенств, a q - количество ограничений-равенств. Знак неравенства в формуле (9.3) может быть заменен на противоположный, если условия G, выражены через отрицания. Символ R обозначает пространство конструкций, получаемое варьированием всех переменных оптимизации. Ограничения области, наложенные на переменные оптимизации, записаны в уравнении (9.2), где X/ и Х„ - нижний и верхний пределы переменных оптимизации соответственно. Обратите внимание, что функциональные ограничения могут быть записаны как в виде равенств, так и в виде неравенств ((9.3) и (9.4)). Задача оптимизации, выраженная через максимизацию целевой функции, легко преобразуется к задаче минимизации инвертированием или отрицанием исходной целевой функции.

Целевая функция F(X) в формуле (9.1) может быть интерпретирована как уравнение поверхности размерности п в пространстве п + 1 переменных. Для задач с двумя переменными оптимизации такую поверхность легко представить в обыч-

ном трехмерном пространстве. Координата z точки поверхности - это значение целевой функции, соответствующее координатам х и у, подставленным вместо параметров. Процесс оптимизации можно, таким образом, сравнить с восхождением на гору в плотном тумане [149]. Альпинист может определить свою высоту при помощи альтиметра и смотреть вокруг себя, выбирая направление подъема или спуска, но не может обнаружить хребты и провалы, затрудняющие продвижение по маршруту. Ему приходится следить и за тем, чтобы не свалиться в пропасть, что эквивалентно нарушению ограничений в формулах (9.2)-(9.4).

9.2. Ограничения

Большинство задач оптимизации ставятся вместе с ограничениями, о чем говорилось в предыдущем разделе. Ограничения могут быть трех типов. Ограничения первого типа задают область определения переменных оптимизации. Эти ограничения легко выполнить, потребовав, чтобы в процессе поиска переменные не выходили за установленные рамки. Ограничения второго типа - равенства - сокращают размерность пространства решений. Лучшим методом обработки этих ограничений является исключение переменных алгебраическим путем. Однако метод исключения переменных применим только до тех пор, пока уравнения ограничений допускают решение относительно независимых переменных. При наличии нескольких ограничений процесс исключения может стать достаточно громоздким. В некоторых случаях явное решение уравнений может оказаться невозможным. Альтернативой является использование штрафных функций (penalty function), о которых речь пойдет ниже [6].

К третьему типу относятся ограничения-неравенства. Стандартный подход к задачам оптимизации с такими ограничениями состоит в том, чтобы изменить целевую функцию для учета влияния этих ограничений. Целевая функция модифицируется добавлением штрафной функции, увеличивающей ее на большую величину при нарушении ограничений. Идея всех методов штрафных функций проста: при нарушении ограничения к целевой функции добавляется бесконечно большое число, в противном случае (ограничение не нарушено) целевая функция остается прежней. Следовательно, штрафную функцию Р(Х) можно определить так:

Р(Х) = \° ц%; (9.5)

где R - подмножество R , соответствующее только допустимым конструкциям, то есть таким, которые удовлетворяют всем ограничениям. Теперь мы можем без ограничений решать задачу минимизации дополненной целевой функции, или функции спуска {descent function) D(X):

D(X) = F(X)+P(X). (9.6)

Однако оптимизация без ограничений в данном случае невозможна (за исключением, быть может, некоторых тривиальных случаев) из-за разрывов в D(X) на границе R , а также бесконечности значений вне R . Замена бесконечности на большой , но конечный штраф не упростила бы задачу, поскольку все равно остались бы численные трудности. Для решения этих проблем предложено было использовать две штрафные функции: внутреннюю и внешнюю.

9.2.1. Внешние штрафные функции

Внешние штрафные функции используются для решения уравнения (9.1). Метод подразумевает использование задач на минимизацию без ограничений, оптимальные решения которых стремятся к решению уравнения (9.1) извне области допустимых конструкций. В последовательности задач на оптимизацию без ограничений на каждое значение X г R/ накладывается штраф, в результате чего оптимальное значение стремится к области допустимого.

В качестве аппроксимации штрафной функции из уравнения (9.5) можно предложить приведенную ниже функцию, учитывающую ограничения в виде равенств и неравенств:

= ! 8,1 С,(Х)Г +£!Я,.(Х)Р, (9.7)

6,={°G0; (9.8)

[1, G;(X)<0. }

Ограничения а и В обычно имеют значения 1 и 2, а функции Gt и Н, взяты из уравнений (9.3) и (9.4). Обратите внимание, что

S(X) = 0 XeR f; (9.9)

5(Х)>0 Xei?;. (9.10)

Для произвольного положительного числа дополненная целевая функция может быть определена как

D(X,p) = F(X) + -S(X). (9.11)

Р

Заметьте, что D(X, р) = F(X) тогда и только тогда, когда X соответствует приемлемому проекту, в противном случае D(X,p) > F(X). Слагаемое S(X)/p аппроксимирует разрывную функцию Р(Х) из уравнения (9.5) при стремлении р -> 0. Итак, метод внешней штрафной функции состоит в решении последовательности неограниченных задач на оптимизацию при k = 0, 1,2,...:

F(X) + -L(8,\G,(XT + £ЯДХ)р]

minD(X,pt) = min

при строго уменьшающейся последовательности положительных чисел pt. Оптимальные значения Xk для pk будут сходиться к настоящему оптимуму X* при увеличении k и приближении рк к нулю. Эту сходимость мы подтвердим приведенным ниже примером.

Пример 9.1

Найти минимум функции F(х) = х2 (х е R) при условии х - 1 > 0. Оптимальное решение очевидно: х' = 1, поэтому нам нужно только показать, что решение, полученное методом внешних штрафных функций, стремится к тому же числу.

Решение

Построим дополненную целевую функцию, используя выражение (9.12) с а = 2. Мы получим задачу оптимизации без ограничений:

mii\D(x,pk) = min

дг2 +

6(дг-1)2

Здесь 6 равно 1 при х < 1 и 0 для прочих х.

Для любого положительного рк функция D выпукла вниз (рис. 9.1) и ее минимум находится в точке

** =--Ц--

р* + 1

Заметьте, что для любого положительного pt эта точка не удовлетворяет ограничению исходной задачи, поскольку значение х оказывается меньше единицы. При стремлении рк к нулю последовательность точек хк стремится к дг = 1 извне разрешенной области значений дг. На практике описанная процедура выполняется численным алгоритмом. Любой численный алгоритм останавливается при удовлетворении некоторого критерия сходимости, поэтому решение, найденное методом внешних штрафных функций, будет оптимальным, но не удовлетворяющим ограничению исходной задачи. Это внутренняя проблема самого метода внешних штрафных функций, который вообще действует только в том случае, когда ограничения нарушаются (ведь штрафные функции являются внешними по отношению к области допустимых значений).

РЙЛ

Рис. 9.1. Дополненная целевая функция

9.2.2. Внутренние штрафные функции

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

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

Итак, рассмотрим задачу оптимизации

minf(X) (9.13)

при условиях

СДХ)>0 1 = 1,2.....т. (9.14)

Хорошая барьерная функция, создающая стены на границах области допустимых значений, имеет следующий вид:

В(Х) =

(9.15)

Заметьте, что значения В(Х) стремятся к плюс бесконечности при приближении X к границе области изнутри, благодаря чему В(Х) и называется барьерной функцией. Чтобы учесть все т ограничений (9.14), мы можем просто поставить в формуле (9.15) знак суммирования по г. Как и для метода внешних штрафных функций, дополненная целевая функция определяется выражением

D(Xp) = F(X) + PB(X), (9.16)

где р - положительное число. Метод внутренних штрафных функций требует решения последовательности задач оптимизации без ограничений для k = 0, 1, 2,.... причем сами задачи даются формулой

minD(Xpt) = min

f(X) + Pt£-

(9.17)

i G;(X)J

где последовательность положительных рк строго убывает. Оптимальные^ значения X* для pt будут сходиться к реальным оптимальным значениям X при стремлении рк к нулю. Продемонстрируем эту сходимость на следующем примере.

Пример 9.2

Найти минимум функции

F(x)x (хеК)

при условии, что дг - 1 > 0. Оптимальное решение дг* = 1, так что нам остается показать, что промежуточные решения, полученные при помощи внутренних штрафных функций, будут стремиться к этому числу.

Решение

Построим дополненную целевую функцию вида (9.17). Мы должны решить задачу оптимизации без ограничений:

. 1 1 1 1

minD(x,pt) = mm -дг + р*-Ч.

Отсюда находим точку минимума функции D1:

хк = 1 + л/2р7 и значение функции D в этой точке:

1 Чтобы получить значения хк, продифференцируем функцию D по дг, приравняем производную нулю и решим получившееся уравнение относительно х.

Заметьте, что при положительных рк оптимальная точка находится внутри области допустимых значений исходной задачи, поскольку она больше единицы. При стремлении р* к нулю точки хк стремятся к д: = 1. Исходная и дополненная целевые функции для некоторых значений рк приведены на рис. 9.2. Если описанная процедура осуществляется численным алгоритмом, начальное значение обязательно должно находиться внутри области допустимых решений.

допустимых значении

Рис. 9.2. Дополненная целевая функция в методе внутренних штрафных функций

9.3. Методы поиска

Для поиска максимума или минимума целевой функции могут использоваться различные методы. Эти методы могут быть сгруппированы в три больших класса (рис. 9.3). Методы первого класса основываются на вычислениях, методы второго класса осуществляют направленный случайный поиск, а методы третьего класса являются перечислительными [95]. На рис. 9.3 показаны только те методы поиска, которые эффективны при решении задач оптимизации по нескольким переменным. Мы не стали указывать простейшие методы поиска, такие как метод Фибоначчи и метод золотого сечения, потому что они применяются главным образом для одномерных задач.

Метод поиска

на вычислениях

Прямой метод

Непрямой метод

Основанный на градиентах

Основанный на градиентах и матрице Гессе

Метод скорейшего спуска

Метод Ньютона

случайный поиск;

Метод модельной закалки

Генетический алгоритм

Рис. 9.3. Классификация методов поиска

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

Здесь F - целевая функция, а вектор переменных оптимизации X составлен из компонент Xj. В качестве примеров методов из этой категории можно назвать метод скорейшего спуска и метод сопряженных градиентов. Методы из второй категории используют матрицу Гессе, составленную из частных вторых производных

dXjdXj

помимо первых производных и значений самой функции. Ко второй категории относится, в частности, метод Ньютона. Ниже мы обсудим идеи, на которых основаны прямые методы, применимые, вообще говоря, только к ограниченному набору хороших задач. Подробные сведения о методах и решении задач оптимизации приводятся в учебниках [62, 119, 6, 131].

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

Рис. 9.4. Осциллирующее поведение алгоритма скорейшего спуска

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

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

Рис. 9.5. Пример нескольких локальных минимумов

9.4. Метод модельной закалки

Еще в 1953 году Метрополис с коллегами предложили алгоритм эффективного моделирования эволюции системы к тепловому равновесию. Почти 30 лет потребовалось Керкпатрику, Гелатту и Веччи [85] и Церни [31], чтобы понять, что между медленным охлаждением твердого тела и минимизацией функции стоимости комбинаторной задачи на оптимизацию существует глубокая аналогия, а процесс оптимизации может осуществляться при помощи критерия Метропо-лиса. Заменив потенциальную энергию системы на стоимость и реализовав алгоритм Метрополиса при постепенно понижающейся температуре, Керкпатрик с коллегами смогли получить алгоритм комбинаторной оптимизации, который они называли методом модельной закалки (simulated annealing). С тех пор исследования этого алгоритма и его приложений образовали отдельную область знания [97].

9.4.1. Комбинаторная оптимизация

В 50-х и 60-х гг. основные прорывы в исследованиях по оптимизации были связаны с новыми алгоритмами поиска оптимумов функций непрерывно изменяющихся переменных. Во многих важных теоретических и практических задачах приходится выбирать лучшее решение из большого набора возможных решений. Если переменные оптимизации могут принимать только некоторые дискретные значения, задача оптимизации будет заключаться в том, чтобы найти лучшую комбинацию этих значений. Такие задачи называются задачами комбинаторной оптимизации (combinatorial optimization problems). Основные результаты в исследованиях по комбинаторной оптимизации были получены в 70-х гг. Для многих таких задач решение может рассматриваться как размещение набора дискретных объектов в соответствии с заданными ограничениями. Поэтому решение называется также конфигурацией (configuration). Набор всех решений называется пространством решений. Наша задача - разработать эффективные алгоритмы определения конфигурации, минимизирующей значение функции стоимости или целевой функции. Примером комбинаторной задачи оптимизации является хорошо известная задача коммивояжера (traveling salesman problem - TSP), которая состоит в определении обладающего минимальной стоимостью маршрута коммивояжера, проходящего через каждый город только один раз и возвращающегося в точку отправления. В этом случае размещаемыми объектами являются города, а то, что каждый город нужно посетить ровно один раз, является ограничением [158]. Эту проблему можно интерпретировать в терминах обычной оптимизации. Посещаемые города - это переменные оптимизации, причем дискретное значение переменной означает номер, под которым данный город войдет в список посещенных. Упомянутое выше условие может быть выполнено, если на дискретные значения, принимаемые переменными, наложить некоторое ограничение.

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

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

Один из методов решения NP-полных задач состоит в использовании алгоритма аппроксимации, позволяющего найти приближенное решение за разумное время. Общая стратегия разработки алгоритмов аппроксимации состоит в последовательном улучшении, основанном на методе проб и ошибок. Поиск начинается с некоторой произвольной конфигурации и продолжается проверкой соседних с ней конфигураций до тех пор, пока не будет найдена конфигурация с меньшей стоимостью. Алгоритм завершает работу, если он больше не может найти соседней конфигурации более низкой стоимости. Эта стратегия кажется разумной, но она имеет один серьезный недостаток: поиск решения оканчивается в ближайшем локальном минимуме (рис. 9.6). Решения, которые кажутся удачными по сравнению с их близкими соседями, не обязательно являются наилучшими в глобальном смысле. Стандартное итеративное улучшение позволяет лишь спускаться с холма, но не подниматься обратно, и потому не гарантирует хорошего результата [158, 134].

Конфигурации

Рис. 9.6. Пространство конфигураций с множеством локальных минимумов

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

9.4.2. Алгоритм

Статистическая механика изучает поведение сложных систем, состоящих из большого числа взаимодействующих атомов, находящихся в тепловом равновесии при конечных температурах. Исследователи обнаружили, что вероятность обнаружить систему в некотором состоянии S равна е~£(*)/**зг, где £(5) - энергия данного состояния, а кь - постоянная Больцмана. Таким образом, наиболее вероятными в тепловом равновесии при любой температуре оказываются состояния атомов с минимальной энергией [158].

Аналогия между задачей комбинаторной оптимизации и определением основного состояния физической системы со множеством взаимодействующих частиц впервые была обнаружена Керкпатриком, Гелаттом и Веччи в 1983 г. [85] и, независимо от них, Церии [31]. Аналогия хорошо иллюстрируется табл. 9.1. Состояния системы соответствуют конфигурациям задачи комбинаторной оптимизации. Основные состояния системы соответствуют оптимальным конфигурациям, то есть таким конфигурациям, которые минимизируют функцию стоимости. Наконец, задача определения оптимальной конфигурации соответствует задаче поиска основного состояния системы при низкой температуре.

Таблица 9.1. Аналогия между физической системой и задачей оптимизации

В 1953 г. Метрополис [113] предложил процедуру вычислений, позволяющую моделировать равновесное состояние системы многих тел при конечной температуре. Алгоритм Метрополиса показан в листинге 9.1. На каждом шаге случайным образом выбирается небольшое возмущение текущей конфигурации, после чего вычисляется изменение энергии системы А. Новая конфигурация принимается с вероятностью 1, если А <0, и с вероятностью eti,kbT при А >0. Для этого выбрасывается случайное число от 0 до 1. Если оно оказывается меньшим е~А/кьТ, новая конфигурация принимается. Это обеспечивает заданную вероятность принятия.

Листинг 9.1. Алгоритм Метрополиса

begin

Выбрать случайную исходную конфигурацию S: repeat

S := произвольно выбранная конфигурация, соседняя с S:

Д :- E(S) - E(S):

Prob := minU.e-Д/кТ):

if random(O.l) s Prob then S := S:

Until false:

end:

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

Керкпатрик реализовал данный подход, рассматривая систему при постепенном понижении температуры . При каждой конкретной температуре система вы-

держивается до тех пор, пока она не достигнет теплового равновесия. Это обеспечивается алгоритмом Метрополиса. Общий алгоритм метода модельной закалки приведен в листинге 9.2. Обратите внимание, что в методе модельной закалки постоянная Больцмана включена в температуру, так что температурой мы называем их произведение. Температура в данном случае является только управляющим параметром процедуры оптимизации.

Листинг 9.2. Алгоритм модельной закалки begin

S :- начальное решение SO; Т :- начальная температура ТО: while (критерий завершения не выполнен) do begin

while (равновесие не достигнуто) do begin

S :- произвольно выбранная конфигурация, соседняя с S: Д :- E(S) - E(S): Prob :- min(l.e A/kT): if random(O.l) £ Prob then S :- S : end: Изменить T: end:

Вывести лучшее решение: end:

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

Теоретический анализ показывает, что алгоритм модельной закалки сходится к глобально оптимальному решению с вероятностью 1 при условии, что выполняются некоторые ограничения на количество итераций при каждом значении температуры и на изменение этой температуры от шага к шагу. Однако общего принципа, по которому можно было бы ставить эти ограничения для конкретных задач, пока не существует. Поэтому большинство современных приложений метода модельной закалки используют простой и эффективный подход Керкпат-рика и других [85] в различных разновидностях.

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

1. Нужно сформулировать задачу, точно описав различные конфигурации.

2. Требуется систематически порождать решения, соседние с текущим.

3. Нужно выбрать подходящую функцию стоимости.

4. Наконец, важно правильно определить график закалки , то есть начальную температуру, закон ее изменения, продолжительность выдержки при каждом значении температуры и условие завершения работы алгоритма.

9.4.3. Применения алгоритма модельной закалки

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

□ размещение и соединение компонентов СБИС;

□ разработка компоновочных планов;

□ маршрутизация и оптимизация маршрутов;

□ проектирование размещения;

□ двумерное уплотнение (компоновка);

□ разработка цифровых фильтров;

□ распознавание образов;

□ обработка изображений.

Мы рассмотрим два примера решения задач оптимизации при помощи алгоритма модельной закалки.

Задача коммивояжера

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

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

□ выбирается произвольная часть текущего маршрута и внутри нее порядок объезда городов меняется на противоположный;

□ либо выбранная часть перемещается в случайное место текущего маршрута. Четыре конфигурации, полученные в процессе решения задачи коммивояжера со 100 городами методом модельной закалки, показаны на рис. 9.7. Города расположены в вершинах правильной решетки. Начальная конфигурация на рис. 9.7, а задается случайной последовательностью городов, далекой от оптимальной. Конфигурация выглядит вполне хаотично, а стоимость объезда оказывается велика. В процессе оптимизации получаются конфигурации (рис. 9.7, б, в), которые ближе к минимуму стоимости. Они становятся менее хаотичными и стоимость их уменьшается. Наконец, на рис. 9.7, г показана конфигурация с минимальной стоимостью. Видно, что последовательность объезда городов в этой конфигурации строго упорядочена [97]. Еще один пример задачи коммивояжера, успешно решенной Керкпатриком и соавторами при помощи модельной закалки, показан на рис. 9.8.

Решение задачи коммивояжера для 100 городов

0.0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0

Рис. 9.8. Решение задачи коммивояжера для 400 городов, полученное с помощью метода модельной закалки

Оптимальная компоновка

Задача оптимальной компоновки (optimal nesting) состоит в минимизации использования исходных листов (заготовок) при производстве деталей различной формы. Типичные ограничения задачи состоят в том, что формы не должны перекрываться, но при этом должны целиком располагаться внутри границ листа.

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

F(S) = отходы + wx перекрытие.

Здесь 5 - текущая конфигурация компоновки, отходы - количество отходов с одного листа (или листов), то есть разность площади исходного листа и площади уместившихся на нем деталей. Перекрытие - суммарная площадь перекрывающихся частей деталей, a w - весовой коэффициент. В процессе оптимизации перекрытия не запрещаются, но большой весовой коэффициент исключает их в конечной конфигурации. Заметьте, что здесь мы, по сути, используем внутреннюю штрафную функцию из раздела 9.2.

Конфигурация S, соседняя с текущей конфигурацией 5, может быть построена небольшим возмущением текущей конфигурации. Например, можно случайным образом выбрать одну деталь из всех размещенных на листе и немного изменить ее положение и ориентацию. Изменение конфигурации с 5 на 5 называется перемещением и выполняется в соответствии с алгоритмом Метрополиса (листинг 9.2).

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

Доля отходов = 17,5%

Доля отходов = 28,4%

Рис. 9.9. Оптимальное размещение деталей для последовательной вырубки

Рис. 9.10. Размещение 36 выкроек на прямоугольном отрезе

Рис. 9.11. Размещение 36 выкроек на отрезе неправильной формы с внутренним дефектом

9.5. Генетические алгоритмы

Генетическими алгоритмами {genetic algorithms) называется группа адаптивных методов, которые могут использоваться для решения задач поиска и оптимизации. Они происходят от тех же основ, что и естественная эволюция и генетика. Популяции живых существ развиваются в течение многих поколений в соответствии с принципами естественного отбора и выживания наиболее приспособленных . Имитируя этот процесс, генетические алгоритмы способны решать реальные задачи, при условии, что те будут правильно закодированы [13]. Сила генетических алгоритмов в их устойчивости и в способности решать задачи самых разных типов, в том числе и трудноразрешимые другими методами. Хотя генетические алгоритмы не обязательно находят глобально-оптимальное решение, они обычно достаточно быстро находят достаточно хорошие решения. Разумеется, специализированные методы, ориентированные на конкретные задачи, по сравнению с генетическими алгоритмами почти наверняка дадут лучшую скорость и точность конечного результата. Превосходство генетических алгоритмов проявляется в таких областях, где специализированных методов не существует. Однако даже имеющиеся методы можно в некоторых случаях усовершенствовать, скрестив их с генетическими алгоритмами [56]. Основные принципы генетических алгоритмов были заложены Холландом [71], им посвящено достаточно много трудов. Эти алгоритмы имитируют то, чем обусловливается эволюция в живых популяциях. В природе выживают те, кто лучше приспособлен к конкуренции за ограниченные ресурсы, поэтому адаптация к изменяющейся конкурентной среде принципиально важна для выживания индивидуумов любого вида. Уникальные особенности индивидуума определяют его жизнеспособность, но сами они, в свою очередь, определяются генами индивидуума. Каждой особенности сопоставляется элемент наследственной информации - ген. Наборы генов, определяющих особенности организма, объединяются в хромосомы. Процесс воспроизводства создает разнообразие в генофонде, а начинается оно с рекомбинации хромосом родительских особей в момент объединения их половых клеток. Из исходных комбинаций генов создаются новые, в результате чего получается новый генотип. Происходит обмен генами между хромосомами, что дает хромосомы с новыми свойствами. Этот процесс называется

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

В начале 70-х гг. Холланд предложил обозначать термином генетические алгоритмы программы, имитирующие природный эволюционный процесс. Генетические алгоритмы работают с популяцией потенциальных решений задачи оптимизации (или поиска). Решения представляются в закодированном виде, подобно тому как в генетическом материале кодируется информация об особенностях индивидуума. В генетических алгоритмах Холланда решения кодировались в виде последовательностей битов двоичного алфавита. Как и в природе, механизмы отбора обеспечивали выживание наиболее совершенных решений. Каждому решению сопоставляется определенное значение приспособленности , отражающее качество данного решения по сравнению с другими решениями той же популяции. Чем больше значение приспособленности, тем больше шансы на выживание и воспроизводство, и тем больший вклад вносит данный индивидуум в последующее поколение. Рекомбинация генетического материала в генетических алгоритмах имитируется механизмом кроссовера, осуществляющим обмен участками строк. Дополнительная операция, называемая мутацией, вызывает спорадические случайные изменения битов строк. Мутация тоже существует в природе, где она обеспечивает восстановление утраченного генетического материала [56].

9.5.1. Основные принципы

В литературе генетический алгоритм Холланда обычно называется простым генетическим алгоритмом (simple genetic algorithm - SGA). В основе SGA лежит популяция двоичных строк. Каждая такая строка, состоящая из нулей и единиц, кодирует решение задачи оптимизации. По сути, она эквивалентна конфигурации в методе модельной закалки. Алгоритм начинает работу с определенного количества строк, которые называются популяцией первого поколения. При помощи генетических операторов (мутации и кроссовера) алгоритм создает следующее поколение из строк текущей популяции. Преимущество в воспроизводстве имеют более совершенные строки, так что в следующем поколении преобладает их потомство . Цикл воспроизводства повторяется до тех пор, пока не выполнится заданный критерий завершения. Общую схему генетического алгоритма демонстрирует рис. 9.12. Подробное описание важных составляющих этой схемы дается в последующих разделах.

Механизм кодирования

Структура генетического алгоритма во многом определяется механизмом кодирования, используемым для представления переменных задачи оптимизации. Эти переменные (называемые генами) объединяются вместе и образуют строку значений (называемую хромосомой). Например, если мы должны найти максимум функции трех переменных F(x, у, z), мы можем представить каждую переменную 10-разрядным двоичным числом (при условии правильного выбора масштаба). При этом хромосома будет содержать три гена, а ее длина будет равна 30 двоичным разрядам (битам).