Материал: 2426

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

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

Среди аналитических методов (п. 4.1) можно выделить отдельный класс методов поиска геодезических линий (линий наименьшей длины) на поверхностях с римановой метрикой. Для построения геодезических линий используются классические методики теории кривых на гладких многообразиях [52, 138].

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

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

35

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

[140].

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

4.2. Поиск траектории в виде вектора, состоящего из набора переменных, входящих в список аргументов целевой функции при явном аналитическом описании последней, проводится при помощи численных методов оптимизации [13, 21, 22, 32, 66, 146, 153, 191, 197]. При этом значение целевой функции вычисляется на каждом шаге оптимизации при помощи отдельного вычислительного алгоритма. На переменные целевой функции, которые для данной задачи являются одновременно координатами объекта в пространстве препятствий, накладываются нелинейные ограничения в виде неравенств. Поверхность препятствий, необходимая для определения ограничений, может описываться как аналитически, так и численно.

Поиск оптимальной траектории в приведенной выше общей постановке – это задача условной оптимизации, а именно задача нелинейного программирования. Наличие ограничений приводит к изменению точки минимума, так как в задаче без ограничений данная точка может оказаться вне допустимой области или внутри препятствий. Задача удовлетворения ограничений в англоязычной литературе встречается под названием Constraint Satisfaction Problem – CSP [222, 237].

Численные методики оптимизации для задачи поиска траектории классифицируются по следующим признакам:

36

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

-применение элементов случайного поиска (детерминированные, стохастические или вероятностные и комбинированные методики);

-вид целевой функции и ограничений (линейное программирование и нелинейное программирование);

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

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

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

Перспективным методом поиска траектории в виде вектора, состоящего из набора переменных, входящих в целевую функцию, является использование эволюционных методов, в частности генетических алгоритмов и алгоритмов роевого интеллекта [155, 199, 217].

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

37

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

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

Рис. 1.10. Задание переменных (пример в плоскости): а – в абсолютных значениях; б – в относительных смещениях

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

38

ся метод наискорейшего градиентного спуска, метод Флетчера-Ривса, метод Дэвидона-Флетчера-Пауэлла, метод кубической интерполяции, метод Ньютона, метод Ньютона-Рафсона, метод Марквардта и др.

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

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

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

гаемой точности [11, 16, 43, 51, 56, 74, 137, 149, 181, 188, 216, 234].

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

110, 199, 226].

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

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

39