Оценка эффективности генетического алгоритма при изменении размерности задачи

Математические методы моделирования, управления и анализа данных.

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

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

(п(р), у = 1, 2). Матрицы коэффициентов уравнений связи для этого типа связи имеют следующий вид:

Ор = (0|- п(р)т), Ос = (01 (АсАрТп(рУ),

ъср = п/р)т (щ(рр) АрТ АсЩс) - АрТ Ас1иСс)1иСс)).

Таким образом, использование тех или иных алгоритмов формирования уравнений движения систем твердых тел определяется характером рассматривае-

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

Библиографические ссылки

1. Колесников К. С., Козлов В. И., Кокушкин В. В. Динамика разделения ступеней летательных аппаратов. М. : Машиностроение, 1977.

2. Виттенбург Й. Динамика систем твердых тел. М. : Мир, 1980.

3. Асланов В. С., Круг лов Г. Е., Юдинцев В. В. Матричная форма уравнений движения систем РКТ // Полет. 2006. № 4.

V. V. Andreev, G. E. Kruglov, V. V. Yudintsev SRPSRC «TsSKB-Progress», Russia, Samara

MODELLING MOVING ELEMENTS OF SPACECRAFT MECHANICAL SYSTEMS

The problem of modeling moving elements of spacecraft mechanical systems as solid bodies system is considered. The peculiarity of the systems is in changing their structures in a process of time. Modeling these mechanical systems requires applying computer that defines a motion equation recording format suitable for constructing a computer simulator of spacecraft mechanical systems with changing structures.

© Андреев В. В., Круглов Г. Е., Юдинцев В. В., 2010

УДК 004.021

О. В. Ахтямов

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Россия, Красноярск

ОЦЕНКА ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПРИ ИЗМЕНЕНИИ РАЗМЕРНОСТИ ЗАДАЧИ

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

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

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

Основные методы, использованные в работе - это изучение, анализ, эксперимент, сопоставление.

Решетневские чтения

В рамках данной работы была создана программа для тестирования генетического алгоритма [2; 3]. Для экспериментальных исследований были взяты три тестовые функции: функция Гриванка, функция Рас-тригина и функция Розенброка [4]. Для всех этих тестовых функций проведены исследования изменения надежности решения задачи оптимизации генетическим алгоритмом при увеличении размерности задачи и с фиксированным ресурсом (произведение числа поколений на размер популяции). Для функций Гри-ванка и Растригина проведены исследования динамики изменения ресурса генетического алгоритма при увеличении размерности для сохранения высокого уровня надежности, а также исследования зависимости среднего номера поколения для нахождения решения алгоритмом от размерности.

На основании проведенных исследований сделаны следующие выводы:

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

2. На функции Гриванка наблюдается кусочно-линейное увеличение ресурса и линейное увеличение числа поколений для отыскания решения с ростом размерности при сохранении уровня надежности 0,9. Следует отметить, что при увеличении размерности на один, объем поискового пространства увеличивался в 3 200 раз, а ресурс только в 1,5-2 раза. Это свидетельствует о превосходных характеристиках алгоритма при решении данной задачи.

3. На функции Растригина наблюдается параболическое увеличение ресурса и параболическое увели-

чение числа поколений для отыскания решения при сохранении уровня надежности 0,9. Это свидетельствует о неплохих характеристиках алгоритма для решения данной задачи.

4. На функции Розенброка наблюдается катастрофическое экспоненциальное увеличение ресурса и числа поколений для отыскания решения при сохранении уровня надежности 0,9. Надо также отметить, что объем поискового пространства при увеличении размерности на один увеличивается в 400 раз, а это меньше, чем в первых двух случаях. Результаты свидетельствуют о практически полной непригодности алгоритма для решения данной задачи.

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

Тем не менее, существуют задачи, при увеличении размерности которых ГА перестает быть эффективным («теорема о бесплатных обедах» - не существует алгоритма, эффективного абсолютно для любых задач) [5].

Библиографические ссылки

1. Семенкин Е. С., Семенкина О. Э., Коробейников С. П. Адаптивные поисковые методы оптимизации сложных систем. Красноярск : СИБУП, 1997.

2. Шилдт Г. Теория и практика С++. СПб. : БИУ-Санкт-Петербург, 1996.

3. Подбельский В. В. Язык С++. М. : Финансы и статистика, 2003.

4. Гмурман В. Е. Теория вероятностей и математическая статистика : учеб. пособие. М. : Высш. образование, 2006.

5. Рубан А. И. Методы оптимизации : учеб. пособие. Красноярск : НИИ ИПУ, 2001.

O. V. Ahtyamov

Siberian State Aerospace University named after academician M. F. Reshetnev, Russia, Krasnoyarsk

EVALUATING OF THE EFFICIENCY OF A GENETIC ALGORITHM FOR PROBLEM DEMENSION CHANGING

The features of changing efficiency of the genetic algorithm with changing demension in solving of the problem of test function optimum discovering are described. The regularity and degree of influence of the «demension curse» are detected.

© AXTAMOB O. B., 2010