Введение в математические основы систем автоматизации проектных работ (САПР)

Задача удовлетворения ограничениям представляет собой обобщение понятия системы алгебраических уравнений (или геометрических ограничений) на случай произвольных ограничений над произвольными областями значений. Многосортная сигнатура определяет набор сортов (имен областей или типов, например int, real, bool, point, line и т.п.), а также типизированные (по сортам) наборы константных, функциональных и предикатных символов (например, 0, 3.14, true, origin, sin, +, *, distance, =, <, coincidence и т.п.). Набор константных символов расширяется типизированными символами переменных из множества X.

На основе константных символов и символов переменных с помощью функциональных символов можно строить термы (например, 2.5*x + sin(3.6 + y), distance(origin, p1)), а на основе термов с помощью предикатных символов - атомарные формулы, называемые также ограничениями (например, 2*distance(origin, p1) <10*x). Моделью заданной сигнатуры является алгебраическая структура, состоящая из множеств-носителей значений каждого сорта (например, R, Z, E3), а также функций и предикатов, определенных на этих множествах. Тем самым, в модели каждый константный, функциональный и предикатный символ получает определенную математическую интерпретацию. Соответственно каждое ограничение в заданной модели либо удовлетворяется, либо нет.

Удовлетворение ограничения означает наличие такого означивания переменных (отображения символов переменных в значения из носителей их сортов), после подстановки которого в формулу, задающую ограничение, и вычисления всех термов получается набор совместных значений для предиката. Задача удовлетворения ограничениям (ЗУО, Constraint Satisfaction Problem, CSP) определяется как набор ограничений заданной сигнатуры и множества переменных, для которых требуется проверить одновременную выполнимость в заданной модели. Решение ЗУО - это означивание переменных, которое удовлетворяет всем ограничениям. В общем случае множество решений ЗУО может быть пустым или содержать больше одного элемента (означивания переменных). Задача оптимизации в ограничениях (ЗОО, Constraint Optimization Problem, COP) задается в сигнатурах, в которых для выделенного сорта s существует предикатный символ <, который в моделях данной сигнатуры трактуется как предикат полного порядка (транзитивное упорядочивание множества значений в носителе сорта s).

Для задания ЗОО необходимо задать ЗУО и указать целевую переменную выделенного сорта s. Решением ЗОО является такое решение соответствующей ЗУО, которому соответствует минимальное (в смысле интерпретации предикатного символа <) значение целевой переменной. Предикат упорядочивания на носителе сорта s позволяет также упорядочить все решения ЗУО (назовем соответствующий предикат на множестве всех означиваний «лучше»). Тем самым имеет смысл говорить о суб-оптимальном решении ЗОО, которое не является оптимальным (то есть решением ЗОО в смысле данного выше определения), но будет лучше некоторого известного решения ЗУО.

Задача безусловной оптимизации (ЗБО) задается одним ограничением вида x = f(t1, …, tn), где t1, …, tn - произвольные термы, а x - целевая переменная.

Во многих сигнатурах предикатные символы над любыми сортами могут быть преобразованы в функции над сортом real, которые достигают значения 0 только при выполнении предиката. Такие функции называются невязками, или штрафными функциями, соответствующих ограничений. Например, ограничение t1 = t2 эквивалентно t1 - t2 = 0, coincidence(p, l) эквивалентно distance (p, l) = 0 и т. п. В таком случае задача удовлетворения ограничений может быть сведена к задаче безусловной оптимизации, в которой роль единственного ограничения вида x = f(t1, …, tn) играет равенство целевой переменной сумме квадратов невязок всех ограничений.

Классификация методов поиска и оптимизации решения

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

Метод координатного спуска

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

Метод градиентного спуска

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

Метод градиентного спуска, пожалуй, - самый популярный оптимизационный алгоритм и является, например, основным инструментом оптимизационного пакета системы CATIA V5 - Product Engineering Optimizer.

Жадный алгоритм

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

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

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

Методы перебора

Простейшим методом поиска решения является полный перебор. На практике такой метод никогда не используется из-за своей высокой сложности - решить этим методом даже простейшие задачи за ограниченное время невозможно.

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

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

Методы редукции областей

В 1960-х гг. были изобретены методы редукции областей при переборе. Заметим для начала, что означивание переменной можно рассматривать как временное сужение области ее определения до единственного значения. В этом смысле частичное означивание ничем не отличается от начальной постановки задачи - у нас есть переменные, области их значений (некоторые из них, возможно, содержат единственный элемент) и набор ограничений. Требуется проверить, нет ли в каких-то из областей заведомо лишних значений. Предположим, что решаемая задача содержит в числе прочих три переменные x, y, и z с областями значений Dx = {0, 1, 2}, Dy = {3, 4, 5}, Dz = {6, 7, 8}, связанные ограничением x + y = z. Понятно, что значение 0 для переменной x несовместно ни с какими значениями из указанных областей для переменных y и z. Аналогично, переменная y не может быть означена значением 3, а переменная z - значением 8. Таким образом, без всякого перебора (рассмотрев только одно ограничение задачи) мы сократили области значений переменных x, y и z до Dx = {1, 2}, Dy = {4, 5}, Dz = {6, 7}. Подобный метод называется достижением совместности областей с ограничением. Сложность метода определяется арностью ограничения (количеством переменных, которые оно связывает) и размером областей значений. В большинстве реальных приложений ограничения бывают унарными, бинарными и тернарными, поэтому на практике сложность можно считать линейно, квадратично или кубически зависимой от размера максимальной области.

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

Настоящий алгоритм сформулирован впервые Маквортом (Macworth) в 1977 г. для случая дискретных областей и бинарных ограничений, под названием AC-3. Однако уже в 1981 г. отечественный математик А. Нариньяни, не знакомый в то время с работой Макворта, предложил значительно более общую концепцию, названную им недоопределенными моделями. Суть концепции в том, что область переменной трактуется как ее недоопределенное значение, которое может доопределиться во время работы алгоритма. Области могут быть как дискретными, так и непрерывными. Последние представляются парой вещественных чисел - нижней и верхней границей соответствующего отрезка вещественной прямой. Для редукции таких интер- вальных областей в соответствии с алгебраическими ограничениями можно использовать правила интервальной арифметики. Открытие Нариньяни оказалось незамеченным на Западе и было «переоткрыто» в начале 1990-х гг. под названием «интервальные ограничения». (Интервальные ограничения с тех пор ушли вперед - был предложен ряд специализированных методов, позволяющих более эффективно сужать интервалы).

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

Недоопределенные модели в комбинации с методами перебора, основанными на делении областей переменных (например, на бисекции вещественного интервала), представляют собой мощный аппарат для решения смешанных задач (содержащих как целочисленные, так и вещественные переменные), который по своей простоте и эффективности превосходит иные известные подходы. Кроме того, на основе той же технологии можно проводить оптимизацию (например, используя описанную ниже схему метода ветвей и границ). Конечно, как и любая универсальная технология, метод недоопределенных моделей проигрывает большинству специализированных алгоритмов (в частности, решение систем алгебраических уравнений над полем вещественных чисел лучше выполнять методом Ньютона). Однако в тех случаях, когда необходимо не только найти одно из решений задачи, но и эффективно оценить область, в которой лежат все решения, альтернативы недоопределенным моделям нет. Следует также отметить, что на основе этого аппарата в системе CATIA V5 было реализовано отношение базы знаний Set Of Equations, а также новый метод оптимизации (названный Constraint Satisfaction) в рамках продукта CATIA V5 Product Engineering Optimizer.

Метод ветвей и границ

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

Алгоритм модельной закалки

Алгоритм модельный закалки (simulated annealing) является типичным алгоритмом стохастического локального поиска. Исследуя все соседние конфигурации (то есть означивания переменных, близкие к текущему), в данном случае мы выбираем не ту, которая дает наилучшее значение целевой функции (как это делает жадный алгоритм), а в зависимости от датчика псевдослучайных чисел можем выбрать любую соседнюю конфигурацию. Однако вероятность выбора конфигурации, дающей лучшее значение целевой функции, больше, чем какой-либо другой конфигурации. Более того, с увеличением числа итераций вероятность выбрать конфигурацию, не являющуюся лучшей среди всех соседей, уменьшается. Более точно, эта вероятность для конфигурации S, соседней с S, равна , где T является настраиваемым параметром алгоритма, называемым «температурой». Этот параметр вначале устанавливается в некоторое большое значение и понижается каждый раз после серии итераций, когда падает темп снижения целевой функции при переходе от текущей к следующей конфигурации. Понятно, что при уменьшении температуры вероятность выбрать соседнюю конфигурацию, ухудшающую текущую, падает. Данный алгоритм является прямым аналогом математического моделирования физического процесса закалки (отжига) твердого тела, при котором изделие сначала нагревается до некоторой высокой температуры, которая затем скачкообразно снижается (позволяя системе достигать термодинамического равновесия на каждом шаге).

Алгоритм модельной закалки реализован во многих системах САПР, включающих средства оптимизации, например, в продукте CATIA V5 Product Engineering Optimizer. Кроме того, имеются успешные примеры использования алгоритма модельной закалки для решения таких задач, как оптимальная компоновка деталей на плоском листе заготовок, распознавание образов, оптимизация маршрутов, проектирование СБИС и др.

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

Генетические алгоритмы, относящиеся к группе алгоритмов стохастического поиска, моделируют на виртуальном уровне процесс эволюции биологической жизни. В таких алгоритмах каждое означивание переменных трактуется как живой организм (особь) со своей уникальной структурой хромосом. «Структура хромосом» в данном случае представляется в виде набора генов - числа фиксированной длины, записанного в двоичном виде. Таким образом, для работы с генетическими алгоритмами задачи с непрерывными областями должны быть дискретизированы, причем отображение множества дискретных означиваний в «хромосомы» должно быть биекцией. Набор конкретных особей образует популяцию (число особей в популяции является настраиваемым параметром). Работа генетического алгоритма состоит в том, что на каждом шаге по текущей популяции порождается следующая. Процесс останавливается, когда большинство особей в популяции становятся похожими друг на друга. Новая популяция порождается предыдущей с помощью процесса, называемого кроссовером. (Из школьного курса общей биологии известно, что в процессе мейоза при конъюгации гомологичных хромосом происходит обмен перекрестными участками гамет, который именуют английским словом crossover.) Виртуальный кроссовер в данном случае состоит в том, что две родительские хромосомы разбиваются в произвольном месте на части и обмениваются своими «хвостами», в результате чего получаются две новые особи. Согласно законам эволюции, более приспособленные организмы получают больше шансов произвести потомство. В терминах генетического алгоритма «более приспособленный организм» означает «означивание переменных, дающее лучшее значение целевой функции». Закон эволюции моделируется датчиком псевдослучайных чисел, при этом вероятность быть выбранным прямо зависит от значения целевой функции на данном означивании. Чтобы бороться с традиционной для алгоритмов локальной оптимизации проблемы сваливания в локальный минимум, генетические алгоритмы реализуют еще один прием, подсмотренный у природы, - возможность мутации. С некоторой небольшой вероятностью каждый организм может мутировать, то есть изменить свои гены. Реализуется это опять же с помощью датчика псевдослучайных чисел и инвертирования некоторых разрядов в двоичной записи числа, кодирующего означивание переменных.

Вопросы для самоконтроля

1. Дайте общее определение задаче удовлетворения ограничениям

2. Дайте общее определение задачам условной и безусловной оптимизации

3. Как можно классифицировать методы поиска и оптимизации решения?

4. Опишите метод координатного и градиентного спуска в применении к непрерывным и дискретным областям

5. Опишите метод Ньютона для решения оптимизационных задач. Что такое квазиньютоновские методы?

6. В чем отличие хронологического и нехронологических методов перебора? Приведите примеры

7. Для чего используются методы редукции областей? Опишите их

8. Опишите метод ветвей и границ. Каковы его достоинства и недостатки?

9. Опишите метод модельной закалки. Каковы области его применения?

10. Опишите общую схему работы генетического алгоритма

Дополнительная литература

Обзор методов оптимизации, применяемый в САПР, можно найти в девятой главе книги [8]. Методы редукции областей и перебора классифицируются в [15]. Использование интервальных ограничений при работе с «черным ящикам» описано в работах [13] и [9].

Лекция 10. Инженерный анализ кинематики