ВВЕДЕНИЕ

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

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

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

ВВЕДЕНИЕ В ИНТЕРВАЛЬНЫЙ АНАЛИЗ

Интервальные числа. Основной идеей интервального анализа является окружение вещественных чисел интервалами, а вещественных векторов – интервальными векторами, или параллелотопами [1,2]. Для обозначения интервала будем использовать строчные латинские буквы в квадратных скобках () или привычное представление (), для параллелотопа – то же обозначение, только начертание букв полужирное ().

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

Для произвольного интервала определены: нижняя граница , верхняя граница , ширина (определена только для непустого интервала) .

Интервальные векторы. Интервальный анализ сопоставляет вещественному вектору интервальный вектор (параллелотоп), который определяется как прямое произведение интервалов (множество параллелотопов обозначается как )

Как и для интервала для параллелотопа определены: нижняя граница или , верхняя граница или , ширина (определена только для непустого параллелотопа) .

Определение операций над интервалами и интервальными векторами. Пусть - бинарная операция, тогда , пусть - унарный оператор, тогда .

Для параллелотопов унарные и бинарные операции определяются как соответствующие покомпонентные операции.

Функции включения. Пусть имеется некоторая функция , действующая из в . Назовем интервальной функцией включения для , действующей из в , если .

Функция включения позволяет гарантированно оценить образ функции независимо от того, каким бы он ни был: выпуклым или невыпуклым, связным или несвязным.

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

ВВЕДЕНИЕ В ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

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

Рис. 1. Схема генетического алгоритма

ПОСТАНОВКА ЗАДАЧИ

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

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

С помощью интервальных операторов, где

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

СТРАТЕГИЯ ИНТЕРВАЛЬНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА

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

Рис. 2. Кодирование параллелотопа

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

Для выполнения селекции необходимо оценить каждую из особей. Для этого используется понятие «функции приспособленности». Для данного алгоритма она была составлена следующим образом:

где , , и - весовые коэффициенты объема, ширины значения и значения соответственно (, , , ), - функция объема.

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

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

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

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

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

На основе алгоритма автором разработано программное обеспечение для поиска глобального минимума функций. Среда разработки – Microsoft Visual Studio, язык программирования – C#.

Рис. 3. Главное окно программы

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

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ

Jaulin L. Applied interval analysis // London: Springer-Verlag, 2001. 380 p.
Hansen E., Walster G. Global optimization using interval analysis // New York: Marcel Dekker, 2004. 515 p.
Holland J. H. Adaptation in natural and artificial systems // Ann Arbor: University of Michigan Press, 1975. 183 p.
Bäck T., Fogel D.B., Michalewicz Z. Evolutionary computation 1. Basic algorithms and operators // Bristol and Philadelphia: Institute of Physics Publishing, 2000. 339 p.