Бионика и Mathcad

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

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

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

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

На кафедре АСУТП МЭИ (В. Р. Сабанин) разработана модификация генетического алгоритма для универсального использования в задачах небольшой размерности. Модифицированный генетический алгоритм сохраняет в себе генетические качества статистической селекции популяции поисковых точек. Для исключения неудачных потомков при их генерировании в алгоритме реализована процедура регулярного поиска локальных экстремумов с использованием операций деформируемого многогранника.

Рис. 3.33. "Генетический" поиск минимума

На рис. 3.33 показано испытание "генетической" функции mga (текст функции можно увидеть на сайте http://twt.mpei.ac.ru/MASAVorksheets/ Minimum.mcd) на тестовой функции f (х), по которой мы уже "шагали" — см. рис. 3.26 и 3.27 градиентным методом "Два шага" (Two-step).

Рис. 3.34. Поиск глобального минимума на "страшной" функции

Рис. 3.35. Наблюдение за решением системы уравнений в Интернете

Аргументами функции mga являются переменныеи(см. их суть выше) и область поиска, а не начальная точка. Функция mga успешно нашла глобальный минимум функции f (х).

На рис. 3.34 отображен вышеупомянутый сайт с адресом http://twt.mpei.ac.ru/ MASAVorksheets/Minimum.mcd, на котором выложена по технологии MA/CS функция mga. Здесь функция тестируется на "страшной" очень многоэкстремальной функции, где сразу видна точка минимума— (х-5.5)2+(у-3.5)2, но на саму функцию наложен "синусоидальный" шум, призванный "сбить с пути" градиентные алгоритмы. Из рис. 3.34 видно, что функция mga с поставленной задачей успешно справилась.

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

На рис. 3.35 показана его реализация для решения системы двух алгебраических уравнений (см. http://twt.mpei.ac.ru/MAS/Worksheets/Newton_2.mcd). На сайте http://twt.mpei.ac.ru/MASAVorksheets/Newton_3.mcd дано решение данной задачи для системы до семи нелинейных аналитических уравнений.