Разработка и исследование гибридного алгоритма решения сложных задач оптимизации

 

КВАЛИФИКАЦИОННАЯ РАБОТА

БАКАЛАВРА

Разработка и исследование гибридного алгоритма

решения сложных задач оптимизации

Оглавление

Введение

Глава 1 Теоретическая часть

1.1 Постановка задачи оптимизации показателей эффективности функционирования технологического контура системы управления космическим аппаратом

1.2 Алгоритмы целочисленной оптимизации

.3 Генетический алгоритм

.4 Искусственные нейронные сети

Глава 2. Практическая часть

2.1 Исследование свойств показателей эффективности функционирования технологического контура

.2 Оптимизация показателей эффективности технологического контура генетическим алгоритмом

.3 Настройка нейронной сети на целевые функции отдельно от процесса оптимизации и ее проверка в ГА

2.4 Настройка НС в процессе оптимизации с помощью ГА

2.5 Проверка настройки НС во время оптимизации ГА одномерных функций

.6 Гибридизация генетического алгоритма с алгоритмами локального поиска

Заключение

Список используемой литературы

Список публикаций автора

Приложение А

Приложение Б

Приложение В

алгоритм гибридный нейронная оптимизация

Введение

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

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

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

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

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

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

Поставленная цель исследования предопределила следующую совокупность решаемых задач:

1.Исследовать свойства целевых функций в рассматриваемой задаче оптимизации сложной системы.

2.Выбрать и реализовать подходящие алгоритмы для решения поставленных задач оптимизации.

.Провести исследование эффективности алгоритмов и установить их оптимальную структуру.

.Проанализировать достоинства и недостатки алгоритмов.

.Используя современные технологии и методы выполнить модификацию алгоритмов с целью устранения выявленных недостатков.

.Программно реализовать разработанный модифицированный алгоритм и исследовать его эффективность на решаемой практической задаче.

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

Научная новизна работы заключается в следующем:

1.Установлено, что показатели эффективности технологического контура системы управления космическим аппаратом в общем случае являются многоэкстремальными и немонотонными.

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

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

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

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

Основные положения, выносимые на защиту:

1.Показатели эффективности технологического контура системы управления космическим аппаратом являются многоэкстремальными и немонотонными.

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

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

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

ü41-я научно-практическая конференция студентов, аспирантов и молодых ученых посвященная Всемирному дню авиации и космонавтики, Красноярск, 2003г.,

üМежвузовская конференция молодых ученых, Красноярск, 2003г.

üВсероссийская научно-практическая конференция Решетневские чтения, Красноярск, 2003г.

üXXXVII Краевая научная студенческая конференция по математике, Красноярск, 2004г.

üХХХI Научная практическая конференция студентов и молодых ученых химического, физического и математического факультетов, Кемерово, 2004г.

üРегиональная конференция "Молодежь и наука - третье тысячелетие", Красноярск, 2004г.

üV международная конференция молодых ученых и студентов «Актуальные проблемы современной науки», Самара, 2004г.

üМеждународная научно-практическая конференция «Актуальные проблемы информатики и информационных технологий», Тамбов, 2004г.

Публикации. По результатам квалификационной работы опубликовано 8 научных работ, среди которых 4 статьи в Вестниках ВУЗов и 4 тезисов докладов. Список трудов автора приведен в конце текста работы после списка литературы.

Структура работы. Квалификационная работа состоит из введения, двух глав, заключения, списка литературы из 8 наименований и содержит 46 страниц основного текста, 12 таблиц, 25 рисунков и 3 приложения.

Глава 1 Теоретическая часть

.1 Постановка задачи оптимизации показателей эффективности функционирования технологического контура системы управления космическим аппаратом

Отработка алгоритмов и методов проводилась на задаче оптимизации показателей эффективности технологического контура (ТК) системы управления космического аппарата (КА).

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

В простейшем случае систему управления космическим аппаратом можно условно представить состоящей из трех подсистем: наземный комплекс управления (НКУ), целевая аппаратура (ЦА) и бортовой комплекс управления (НКУ). Систему управления космическим аппаратом можно представить в виде следующей схемы приведенной на рисунке 1.1:

Рис. 1.1 Схема представления системы управления КА в простейшем случае

При моделировании процесса функционирования ТК используется теория Марковских процессов [1]. В данной задаче математическая модель функционирования ТК представляет собой Марковский процесс с дискретными состояниями и непрерывным временем [2]. При условии, что НКУ абсолютно надежен, соответствующий Марковский процесс имеет граф состояний, представленный на рисунке 1.2 [3].

Рис. 1.2 Граф состояний технологического контура управления в простейшем случае

Описание состояний технологического контура:

. Все подсистемы работоспособны.

. Целевая аппаратура отказала, БКУ работоспособен и занят восстановлением работоспособности ЦА, НКУ свободен.

. Целевая аппаратура работоспособна, БКУ отказал, НКУ восстанавливает работоспособность БКУ.

. Целевая аппаратура отказала, БКУ работоспособен и свободен, НКУ занят восстановлением работоспособности ЦА.

. Целевая аппаратура и БКУ отказали, НКУ восстанавливает работоспособность ЦА, БКУ ожидает окончания восстановления ЦА.

В графе через обозначены интенсивности выхода из строя, а через mi - интенсивности восстановления подсистем. Соответствующая система уравнений Колмогорова-Чэпмена имеет следующий вид (1.1.1):

P1(l1+l2) - m1p0P2 - m3P3 - m2P4 = 0,

P2(m1+l2) - l1P1 = 0,3(l1+m3) - l2P1 - m2P5 = 0,4(l2+m2) - (1-p0)m1P2 = 0,(1.1.1)5m2 - l2P2 - l1 P3 - l2P4 = 0,

P1 + P2 + P3 + P4 + P5 = 1.

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

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

1.2Алгоритмы целочисленной оптимизации

В силу того, что требуется решить задачу целочисленной оптимизации

,

где ,

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

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

Определение 2. D - допустимая область определения целевой функции.

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

Пусть мы имеем допустимую точку X Î D для некоторой конкретной задачи оптимизации. Было бы весьма полезно определить некоторое множество точек, "близких", в некотором смысле, к этой точке X.

Определение 3. Пусть задана задача оптимизации (D, f), где D - допустимая область, f - целевая функция. Тогда системой окрестностей или окрестностной функцией называется отображение N : D ® 2D, определенное для каждой индивидуальной задачи (2D есть множество всех подмножеств множества D).

Для задачи оптимизации на дискретной решетке будут применяться следующие системы окрестностей:

N1(X) = ,(X) = ,

где n - длина целочисленного вектора (точки допустимой области определения).

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

Определение 4. Две точки Х и Y из области D пространства булевых переменных будем называть k-соседними, если они отличаются друг от друга значениями k своих координат.

Примечание: множество точек, k-соседних к точке Х будем обозначать как Ok(X).

Определение 5. Пусть дана индивидуальная задача оптимизации (D,f) и система окрестностей N. Тогда некоторое допустимое решение Х* называется локально оптимальным или оптимальным относительно системы окрестностей N, если f(X*) < f(Y) " Y Î N(X*).

Определение 6. Решение X задачи (D, f) называется глобально оптимальным, если f(X) < f(Y) "Y Î D.

Определение 7. Если любая точка Х Î D, локально оптимальная относительно системы окрестностей N, является глобально оптимальной, то система окрестностей N называется точной.

Ниже приведены используемые в данной работе алгоритмы прямого локального поиска [4].

Неулучшаемый алгоритм локального поиска на целочисленной решетке

1. Выбираем X0 Î Dn произвольно.

. Поочередно просматриваем 1-соседние точки X0 и вычисляем значения функции в получаемых точках. Запоминаем изменение, приведшее к улучшению.

. Если ни одно улучшение не найдено, то X0 - точка минимума, остановиться и вывести ответ.

. Заменяем все координаты X0 на те, которые приводили к улучшению, и вычисляем значение функции в полученной точке. Обозначаем полученную точку через X0.

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

. Если ни одно улучшение не найдено, то проверяем остальные точки окрестности.

7.Перейти к шагу 3.

Алгоритм локального поиска на целочисленной решетке по системе окрестностей N2(X)

1. Стартовую точку выбрать произвольно.

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

. Если изменение всех координат на два не дает улучшения функции, то начинать просмотр всех пар координат в порядке 1-2, 1-3, … , 2-3, 2-4, …, увеличивая и уменьшая каждую координату пары на единицу. Если получено улучшение целевой функции, то переходить в точку, дающую улучшение, и продолжать с шага 2.

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

. Вывести наилучшее значение целевой функции и точку, в которой это значение получено.

Неулучшаемый алгоритм псевдобулевой оптимизации

1. Произвольно выбираем точку X0ÎD.

. Последовательно инвертируем координаты булева вектора, определяя все точки Xj Î Ol(X), j = 1, …, n, 1-соседние к X0 (n - длина битовой строки).

. Координаты оптимальной точки Х* получаем по правилу:

Примечание. Данному алгоритму требуется ровно n+1 вычислений целевой функции для получения точки локального оптимума произвольной монотонной псевдобулевой функции.

Обобщенный алгоритм локального поиска для оптимизации унимодальных псевдобулевых функций

1. Произвольно выбираем точку X1 и определям ее (n/2)-соседние точки X2, X3, … , Xn, вычисляем значения функции в этих точках.

2. Генерируем точки Yj = (), j = 1, 2, …, n и вычисляем значения функции в этих точках.

. Определяем точку X* по правилу

и вычисляем значение функции в ней.

. Если f(X*)<f(Xj) " j = 1, 2, …, n и f(X*)<f(Yj) "j = 1, 2, …, n, то необходимо определить все точки Zi Î O1(X*) и вычислить значения функции в них. Далее выполнять с шага 6.

. Если f(X*)<f(Zi) "i = 1, 2, …, n, то вывести X*, f(X*) и остановиться (X* - точка минимума, функция f - унимодальная и монотонная).

. Выбрать точку X0 из условия

(X0) = min {f(X*), f(Xj), f(Yj), f(Zj), "j = 1, 2, ..., n}

. Определять точки Xj Î O2(X0), j = 1, 2, …, и вычислять f(Xj) до тех пор, пока не будет найдена такая точка Xj, что f(Xj)<f(X0).

. Если точка найдена, тогда X0 = Xj и вернуться к шагу 7.

. Среди точек Xk Î O1(X0) выбрать точку X*, дающую наименьшее значение функции.

. Если f(X*)<f(X0), то X*- точка минимума, иначе это - X0., переходим на шаг 7.

1.3Генетический алгоритм (ГА)

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

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

Пропорциональная селекция

Пропорциональная селекция может быть выполнена в виде алгоритма колеса рулетки. В данной селекции каждому индивиду из текущей популяции назначается пригодность быть отобранным пропорционально его пригодности. Пусть N - число индивидов в популяции и fi - пригодность i- го индивида в популяции тогда, например, если N = 4, f1 = f2 = 10, f3 = 15, и f4 = 25 колесо рулетки представлено на рисунке 1.3:

Рис. 1.3 Пример колеса рулетки

Проблемы с пропорциональной селекцией:

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

Стагнация

Ранговая селекция

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

Затем каждому индивиду назначается вероятность pi быть отобранным.

Используемое распределение вероятностей:

1. Линейное: pi = a×i + b (a < 0).

Преимущества:

1. Нет преждевременной сходимости, т.к. нет индивидов с Ni >> 1.
2. Нет стагнации, так как и к концу работы алгоритма N1 ¹ N2 ¹ … .
3. Нет необходимости в явном вычислении пригодности, т.к. для упорядочения индивидов достаточно иметь возможность их по парного сравнения.

Недостатки: значительные накладные расходы на переупорядочивание и трудность теоретического анализа сходимости.

Турнирная селекция

Одна из самых простых в реализации и эффективных в оптимизации является турнирная селекция. Для отбора индивида создается группа из M (M ³ 2) индивидов, выбранных из текущей популяции случайным образом

Индивид с наибольшей пригодностью в группе отбирается, остальные - игнорируются

Преимущества:

1. Нет преждевременной сходимости
2. Нет стагнации
3. Не требуется глобальное переупорядочивание
4. Не требуется явное вычисление функции пригодности

Элитарная селекция

В данной селекции один или несколько лучших индивидов популяции всегда проходит в следующее поколение

Преимущество: гарантия сходимости, т.е. если глобальный максимум будет обнаружен, то ГА сойдется к этому максимуму

Недостаток: слабая глобальная сходимость, большой риск найти локальный минимумом

Скрещивание в ГА

Оператор скрещивание предназначен для поиска новых решений на основе отобранных селекцией родителей.

·Одноточечное скрещивание представляет собой разделение родительских хромосом в выбранной случайным образом общей точке и обмен правыми частями. (ТС - точка скрещивания). Пример одноточечного скрещивания представлена на рисунке 1.4.

Рис. 1.4 Пример одноточечного скрещивания

1. При двухточечном скрещивании хромосому можно рассматривать как кольцо со связанными первым и последним генами. Кольцо рассекается на две части и полученные части обмениваются. Графическое представление двухточечного скрещивания представлено на рисунке 1.5, пример на рисунке 1.6.

Рис. 1.5 Двухточечное скрещивание

Или

Рисунок 1.6 Пример двухточечного скрещивания

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

Замечание: в этом случае родителей может быть больше двух, в том числе возможно участие всей популяции родителей в целом (gene pool recombination) [5].

Мутация в ГА

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

В двоичных хромосомах мутация состоит в инвертировании случайным образом выбранного бита генотипа, например 1010 à 1000.

1. В ГА мутация является методом восстановления потерянной генетической информации, а не методом поиска лучшего решения.

В ГА мутация применяется к генам с очень низкой вероятностью pm Î [0.001, 0.01]. Хорошим эмпирическим правилом считается выбор вероятности мутации из соотношения pm = , где H - число бит в хромосоме. На основе этого правила можно произвести классификацию мутации таким образом:

.Слабая (pm < ),

.Средняя (pm =)

.Сильная (pm > )

Обобщенная пошаговая структура ГА

.Сгенерировать случайным образом начальную популяцию.

2.Оценить полученную популяцию.

.Генерировать популяцию потомков.

Селекция (выбор двух индивидов из текущей популяции).

Рекомбинация (скрещивание выбранных индивидов).

Мутация (генетическое изменение полученного потомка).

4.Если не все поколения пройдены, то перейти на шаг 2, иначе выдать наилучшего найденного индивида и его значение целевой функции в качестве решения оптимизации.

Схема генетического алгоритма представлена на рисунке 1.7.

Рис. 1.7 Схема ГА

1.4 Искусственные нейронные сети (ИНС)

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

Модель нейрона

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

Нетрудно построить математическую модель описанного процесса. Рассмотрим модель нейрона с тремя входами (дендритами), причем синапсы этих дендритов имеют веса w1, w2, w3. Пусть к синапсам поступают импульсы силы x1, x2, x3 соответственно, тогда после прохождения синапсов и дендритов к нейрону поступают импульсы w1x1, w2x2, w3x3. Нейрон преобразует полученный суммарный импульс.

Следовательно аргумент для функции активации равен x=w1x1+w2x2+w3x3 в соответствии с некоторой передаточной функцией f(x). Сила выходного импульса равна y=f(x)=f(w1x1+w2x2+w3x3).

Таким образом, нейрон полностью описывается своими весами wk и передаточной функцией f(x). Получив набор чисел (вектор) xk в качестве входов, нейрон выдает некоторое число y на выходе.

Рисунок 1.8 а) функция единичного скачка; б) линейный порог (гистерезис); в) сигмоид - гиперболический тангенс; г) сигмоид - формула (3)

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

(1.2.1)

При уменьшении a сигмоид становится более пологим, в пределе при a=0 вырождаясь в горизонтальную линию на уровне 0.5, при увеличении a сигмоид приближается по внешнему виду к функции единичного скачка с порогом T в точке x=0. Из выражения для сигмоида очевидно, что выходное значение нейрона лежит в диапазоне [0,1]. Одно из ценных свойств сигмоидной функции - простое выражение для ее производной, применение которого будет рассмотрено в дальнейшем.

(1.2.2)

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

Структура нейросетей

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

Как построить такую сеть? Этот вопрос решается в два этапа:

1.Выбор типа (архитектуры) сети.

2.Подбор весов (обучение) сети.

На первом этапе следует выбрать следующее:

·какие нейроны мы хотим использовать (число входов, активационные функции);

·каким образом следует соединить их между собой;

·что взять в качестве входов и выходов сети.

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

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

Обучение сети

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

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

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

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

Глава 2. Практическая часть

.1 Исследование свойств показателей эффективности ТК КА

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

Данные алгоритмы были применены при решении задачи оптимизации коэффициентов готовности КА, БКУ, ЦА в технологическом контуре КА. Для этого автором был разработан пакет программ, начальное рабочие окно которого представлено на рисунке 2.1.

Рис. 2.1 Начальное окно программы

Единственным управляемым параметром является выбор того или иного алгоритма оптимизации. После того, как алгоритм выбран и запущен, пользователю предоставляется рабочее окно конкретного алгоритма. Например, выбран алгоритм 1, тогда результирующее и начальное окно можно увидеть на рисунке 2.2.

Рис. 2.2 Начальное и результирующее окно алгоритма 1

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

Рис. 2.3 Ввод стартовой точки

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

·функции расчета коэффициента готовности КА как на целочисленной решетке, так и в пространстве булевых переменных унимодальные и монотонные,

·функции расчета коэффициентов готовности целевой аппаратуры (ЦА) и бортового комплекса управления (БКУ) - полимодальные и немонотонные,

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

2.2 Оптимизация показателей эффективности технологического контура генетическим алгоритмом

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

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

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

Рис 2.4. Ввод числа индивидов в турнирной группе

В разделе Остальные параметры (Other parameters) указывается размеры популяции и число поколений, при этом число поколений является критерием остановки алгоритма.

Дополнительной опцией является возможность в разделе Мутация (Mutation) пользователю самому устанавливать значение вероятности мутации.

В разделе Вид оптимизируемой функции (Kind of test function) можно устанавливать по какой функции проводится оптимизация, то есть функцию вычисления определенного коэффициента готовности. При выборе любой из функций в строке Объективный оптимум (The Objective optimum Y), еще до запуска алгоритма, выводится значение функции в точке оптимума, известное в результате выполненной ранее целочисленной оптимизации. Это сделано с целью удобства сравнения решений найденных генетическим алгоритмом с целочисленной оптимизацией.

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

Рис. 2.5 Начальное окно программной системы ГА

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

Рис. 2.6 Файл отчета по работе программной системы ГА

На рисунке 2.7 представлено результирующее окно программы. На нем изображены графики сходимости ГА по нескольким запускам: значения целевой функции лучшего индивида популяции (верхний график), среднее значение целевой функции по популяции (средний график), значение целевой функции худшего индивида по популяции(нижний график). А также вычислены величины эффективности работы запущенной структуры ГА, скорость ее сходимости (на каком в среднем поколении был найден заданный оптимум) и интервал поколений, на котором гарантированно при всех установленных запусках, был найден оптимум. Рассмотрим это более подробно позже. В случае необходимости можно сохранить (кнопка Save as) полученные графики или вывести на принтер (кнопка Print).

Рис. 2.7 Результирующее окно программной системы ГА

Результаты оптимизации с помощью ГА

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

Постоянные параметры генетического алгоритма: численность популяции равна 25, число поколений равно 30. То есть число вычислений целевой функции равно 750, что составило порядка 0.3% от всей области определения функции (т.к. аргумент функции был представлен в виде булевого вектора (хромосомы) длиной 18 бит.) Размер в элитарной и турнирной группах был равен 5.

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

Выводы:

·оптимальной структурой ГА в данной задаче является: турнирная селекция, слабая (средняя см. табл. 3. приложения А) мутация, равномерная рекомбинация,

·ГА успешно справился с задачей оптимизации (т.к. показатели надежности равны 1),

·для всех оптимальных структур (для каждой из функций) для нахождения глобального максимума не потребовалось выполнения всех отведенных поколений (т.е. глобальный максимум был найден уже после 20-21 поколения).

2.3 Настройка нейронной сети на целевые функции отдельно от процесса оптимизации и ее проверка в ГА

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

Для настройки сети автором была разработана и реализована на языке высокого уровня программа в основе которой был положен уже известный алгоритм обратного распространения [7] с адаптивным шагом обучения на основе простого алгоритма локального поиска.

Общая схема обучения выглядит так:

1.Случайно генерируется битовая строка заданной длины (закодированный шаг обучения).

2.Битовая строка декодируется в вещественное число - шаг обучения.

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

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

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

.Если инвертирование невозможно тогда переходим на этап 1.

Начальное окно программы изображено на рисунке 2.8.

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

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

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

Рис. 2.8 Начальное окно программы Настройка сети

Рис. 2.9 Окно установки архитектуры НС

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

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

Рис. 2.10 Кривая обучения сети

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

Запустив данную программу несколько раз, была получена НС. Аппроксимация по сети для одного из коэффициентов готовности КА изображена на рис 2.11.

Рис. 2.11 Окно программы после завершения настройки сети

После того как полученная НС была применена в качестве функции вычисления коэффициента готовности КА в ГА, последний нашел точку оптимума, которая совпала с объективной оптимальной точкой, найденной целочисленной оптимизацией, но при вычислении целевой функции по системе уравнений Колмогорова-Чепмена. Таким образом, можно сделать вывод о том, что нейронная сеть достаточно хорошо настроена для вычисления коэффициента готовности по ней, так как время вычисления по НС. значительно ниже, чем по системе уравнений. Недостатком данного метода замены целевой функции на обученную НС является разделение оптимизации на два этапа, где в ходе первого этапа ведется настройка сети, а уже потом оптимизация как таковая. Неизвестно, насколько это разделение оправдано с точки зрения экономии времени по сравнению с оптимизацией, где вычисление целевой функции ведется по системе уравнений. Поэтому было предложено совместить эти два этапа в один.

Выводы

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

Рис. 2.12 Окно программы ГА и Нейронная сеть (НС)

В программе ГА и Нейронная сеть генетический алгоритм решает задачу оптимизации коэффициентов готовности подсистем КА. Особенностью является то, в программу включена обученная НС. Недостаток обученной НС: значение в точке полученного оптимума отлично от объективного (для коэффициента готовности КА объективное равно 0.99992905, полученное сетью 0.999915555), а положительным моментом является то, что точка оптимума равна объективной (для коэффициента готовности КА она равна 000000111111111111).

.4 Настройка НС в процессе оптимизации с помощью ГА

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

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

Алгоритм ГА+НС:

1.Проводится оптимизация ГА по n1 первым точкам, которые записываются в обучающую выборку.

2.По записанным в обучающую выборку n1 точкам проводится настройка НС.

.По следующим n2 точкам проводим соответствующие шаги ГА.

.Вновь полученные n2 точек используем в качестве экзамена для обучающейся НС.

.Если ошибка экзамена НС недопустимая, то дописываем k (k<n2) точек дающих наибольшую ошибку в обучающую выборку и если целевая НС выполняет роль вычисления целевой функции, то необходимо заменить ее на систему уравнений Колмогорова-Чепмена. Получаем n1 = n1 +k . Переходим на шаг 2.

.Иначе заменяем целевую функцию (систему уравнений Колмогорова-Чепмена) на обученную НС при выполенении оптимизации ГА. Переходим на шаг 3.

Описанный алгоритм был реализован автором на языке высокого уровня С++ в оболочке Builder 5.0. Начальное окно программы изображено на рис 2.13.

Рис. 2.13 Начальное окно программы Гибрид ГА и НС

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

Новый раздел Параметры обучающей выборки включает следующие настройки:

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

·Число точек экзамена это количество точек, которое ГА просматривает после настройки сети и на которых проверяется, насколько хорошо сеть была настроена.

В этой программе-гибриде соединены две вышеописанных программы - генетический алгоритм и нейронная сеть, в ее основе лежит алгоритм ГА+НС.

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

Выводы:

Нейронную сеть в ходе процесса оптимизации ГА не удалось настроить. Автором предполагаются следующие возможные причины:

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

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

.Приведенные исследования показали, что при оптимальной структуре ГА требуется около 800 вычислений для нахождения точки оптимума, а НС была настроена при 1000 точек в обучающей выборке. Причем эти точки были случайно сгенерированы, а ГА, как известно, делает все-таки неравномерный разброс по поисковому пространству. То есть, возможно не хватило точек в обучающей выборке.

.5 Проверка настройки НС во время оптимизации ГА одномерных функций

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

Рис. 2.14 Начальное окно программы настройки сети

В ходе многократных запусков программы было замечено, что функция которую представляет собой НС, настроенная по точкам пройденным ГА, не отражает собой глобальный оптимум (то есть не применима в качестве замены для «настоящей» целевой функции) до тех пор, пока точки ГА не захватят реальный глобальный оптимум. Только тогда можно применять НС, когда она отражает реальный глобальный оптимум. Но остается вопрос: «Как определить что НС начала отражать глобальный оптимум или что ГА нащупал область глобального оптимума?». Ответ на этот вопрос на данный момент еще не найден. По величине ошибки обучения нейронной сети ответить на этот вопрос невозможно. Это доказано многократными запусками программы с одними и теми же настройками.

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

Рис. 2.15 Результирующее окно программы настройки сети

Следовательно вопрос о целесообразности применения НС в качестве аппроксиматора целевой функции при оптимизации ГА остается открытым. Из проведенных исследований следует, что ответ на этот вопрос скорее «Нет», чем «Да». Во всяком случае, это можно, конечно не уверенно, но хоть как-то обосновать результатами тех исследований, которые были проведены на данный момент. Во всяком случае, попытка решить данный вопрос порождает серию не менее сложных и важных вопросов, чем исходный.

Выводы

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

.6 Гибридизация ГА с алгоритмами локального поиска

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

Один из видов гибридизации ГА заключается в следующем. На каждом поколении ГА отбираются несколько (перспективных) индивидов для того, чтобы из них были выполнены несколько шагов ЛП (моделирование прижизненной адаптации индивидов). В зависимости от типа моделируемой эволюции, индивид после локального спуска в следующую популяцию переходит: либо таким же, каким он был перед ЛП, но с «новой» пригодностью (прижизненная адаптация делает индивида более пригодным, но по наследству не передается - эволюция по Дарвину), или таким, каким он стал после ЛП (прижизненная адаптация делает индивида более пригодным и передается по наследству - эволюция по Ламарку). Обе концепции гибридного алгоритма были реализованы совместно с обыкновенным ГА. Для этого была разработана соответствующая программная система, начальное и финальное окна которой представлены на рисунках 2.16 и 2.17.

Рис. 2.16 Начальное окно программы ГА + локальный поиск

Рис. 2.17 Финальное окно программы ГА + локальный поиск

Необходимо обратить внимание на различие в поведении графиков пригодности на рис. 2.7 и 2.17. Очевидно, что гибридный алгоритм намного быстрее выходит на экстремум, чем обычный ГА. Кроме того, он сглаживает осцилляции целевой функции.

Как и в исследованиях с обыкновенным ГА, постоянными параметрами гибридного алгоритма были: численность популяции - 25, число поколений - 35.

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

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

1.Оптимальной структурой гибридного ГА при использовании концепции ЛП по Дарвину является: турнирная селекция, слабая или сильная мутация, двухточечная рекомбинация.

2.Оптимальной структурой гибридного ГА при использовании концепции ЛП по Ламарку является: турнирная селекция, слабая или средняя мутация, скрещивание может быть различным.

.При решении данной задачи использование концепции по Ламарку оказалась значительно эффективней, чем по Дарвину.

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

.Скорость гибридного алгоритма по сравнению с обыкновенным ГА в два раза выше при оптимальных структурах (см. таблицы 2.1, 2.2 и 2.3).

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

Таблица 2.1. Сравнение показателей эффективности ГА и гибридного алгоритма при оптимизации коэффициента готовности КА

НадежностьСкоростьРазбросГибридный ГА14[2; 32]Обыкновенный ГА110[4; 21]

Таблица 2.2. Сравнение показателей эффективности ГА и гибридного алгоритма при оптимизации коэффициента готовности ЦА

НадежностьСкоростьРазбросГибридный ГА13[2; 11]Обыкновенный ГА17[3; 14]

Таблица 2.3. Сравнение показателей эффективности ГА и гибридного алгоритма при оптимизации коэффициента готовности БКУ

НадежностьСкоростьРазбросГибридный ГА12[2; 3]Обыкновенный ГА14[1; 7]

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

Заключение

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

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

Список литературы

1. Воловик М.А. Коэффициент готовности прибора со встроенной системой контроля // Системный анализ и исследование операций. - Новосибирск: ВЦ АН СССР, 1977.

. Семенкина О.Э. Оптимизация управления сложными системами методом обобщенного локального поиска. - М.: МАКС Пресс, 2002. - 215 с.

3. Semenkin E., Volovik M. Modelling and Optimization of Spacecrafts' Systems Design // Operations research'95. - Berlin: Springer, 1995. - Pp. 353-358.

. Semenkina O. Adaptive Search Algorithms for Solving Mixed Optimization Problems in CAD of Spacecraft Control Systems // Operations Research'97. - Jena: TU-Jena, 1997.

. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989.

. Семенкин Е.С., Семенкина О.Э., Терсков В.А. Методы оптимизации в управлении сложными системами // Учебное пособие. - Красноярск: СибЮИ МВД РФ, 2000. - 254 с.

. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. - М.: Мир, 1984.

Список публикаций автора

1.Бежитский С.С. О трудоемкости алгоритмов локального поиска для задачи выбора структуры технологического контура космического аппарата //Информатика и информационные технологии: Межвуз. сб. научн. тр./Красноярск: ИПЦ КГТУ, 2003. с.17-19.

2.Бежитский С.С. О свойствах целевой функции в задаче выбора структуры технологического контура космического аппарата // Тезисы докладов 7-й Всероссийской научной конференции «Решетневские чтения». Красноярск: СибГАУ, 2003. - С. 266.

.Бежитский С.С., Семенкин Е.С., Семенкина О.Э. Разработка и исследование эволюционного алгоритма для оптимизации управления сложными системами // Вестник Кемеровского государственного университета. Журнал теоретических и прикладных исследований. Выпуск 1(17) - Кемерово: КемГУ, 2004. - с.26-33.

.Бежитский С.С. Гибридный эволюционный алгоритм для решения сложных задач оптимизации // Вестник университетского комплекса. Сборник научных трудов. Выпуск 1(15). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2004. - с.166- 173.

.Бежитский С.С. Разработка и исследование гибридного эволюционного алгоритма для решения сложных задач оптимизации // Сборник научных трудов. Красноярск: СИБУП, 2004.

.Бежитский С.С. О монотонности показателей эффективности технологического контура системы управления космическим аппаратом / C.С. Бежитский //Вестник Сибирского государственного аэрокосмического университета. - Выпуск 5. - Красноярск: СибГАУ, 2004. - с. 19-26.

.Бежитский С.С. Модификация генетического алгоритма для решения задачи оптимизации показателей эффективности технологического контура системы управления космическим аппаратом / С.С. Бежитский // Труды пятой международной конференции молодых ученых и студентов «Актуальные проблемы современной науки». - Самара. 2004. - с.20-23.

.Бежитский С.С. Сравнение эффективности работы генетического алгоритма и алгоритма эволюционных стратегий на задачах оптимизации многоэкстремальных функций /С.С. Бежитский // Материалы международной «8-ой тамбовской межвузовской» научно-практической конференции.- Тамбов: ТГУ, 2004. - с. 81-82.

Приложение А

Результаты выполнения оптимизации с помощью ГА для каждой из целевых функций

Таблица А.1. Усредненные результаты работы ГА для коэффициента готовности КА

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0.3421[5;30]Турнирная111[5;25]Ранговая0.2722[12;30]Элитарная0.2122[9;30]СредняяПропорц.0.1316[1;29]Турнирная0.6816[2;28]Ранговая0.0916[3;28]Элитарная0.0520[9;30]Сильная Пропорц.0.038[3;14]Турнирная0.1717[5;29]Ранговая0.0219[16;21]Элитарная0.0518[4;29]ДвухточечнаяСлабаяПропорц.0.3220[11;30]Турнирная110[4;25]Ранговая0.3218[11;29]Элитарная0.5322[9;30]СредняяПропорц.0.0817[3;29]Турнирная0.7117[2;30]Ранговая0.0420[10;25]Элитарная0,1723[10;30]Сильная Пропорц.0.0615[8;24]Турнирная0.1419[7;30]Ранговая000Элитарная0.0425[22;25]РавномернаяСлабаяПропорц.0.3820[5;30]Турнирная110[4;21]Ранговая0.4419[7;30]Элитарная0.4621[6;30]СредняяПропорц.0.0722[7;30]Турнирная0.8517[4;30]Ранговая0.0619[16;25]Элитарная0.1123[5;30]Сильная Пропорц.0.0714[2;26]Турнирная0.2619[6;30]Ранговая0.0318[13;27]Элитарная0.0417[9;27]

Таблица А.2. Усредненные результаты работы ГА для коэффициента готовности ЦА

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0,5616[3;28]Турнирная18[4;20]Ранговая0.7119[4;30]Элитарная0.6922[10;30]СредняяПропорц.0.3215[5;30]Турнирная0.9912[4;30]Ранговая0.3115[3;30]Элитарная0.3819[8;30]Сильная Пропорц.0.0316[3;30]Турнирная0.6116[2;30]Ранговая0.0814[2;23]Элитарная0.1920[3;30]ДвухточечнаяСлабаяПропорц.0.5118[2;30]Турнирная18[3;16]Ранговая0.6817[8;29]Элитарная0.7721[5;30]Средняя Пропорц.0.4517[2;30]Турнирная0.9912[4;29]Ранговая0.2317[7;30]Элитарная0,3721[6;29]Сильная Пропорц.0.2216[3;30]Турнирная0.6114[4;29]Ранговая0.1516[8;24]Элитарная0.2220[7;29]РавномернаяСлабая Пропорц.0.6615[8;30]Турнирная17[3;14]Ранговая0.817[3;30]Элитарная0.7819[7;30]Средняя Пропорц.0.3615[4;29]Турнирная0.9710[2;27]Ранговая0.2917[6;30]Элитарная0.4120[5;30]Сильная Пропорц.0.2913[2;28]Турнирная0.6313[2;30]Ранговая0.1119[6;28]Элитарная0.1718[6;29]

Таблица А.3. Усредненные результаты работы ГА для коэффициента готовности БКУ

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0.997[1;26]Турнирная14[1;9]Ранговая16[1;15]Элитарная19[1;28]СредняяПропорц.0.987[1;29]Турнирная14[1;10]Ранговая17[1;24]Элитарная19[19;25]Сильная Пропорц.0.988[1;27]Турнирная14[1;14]Ранговая0.989[1;29]Элитарная111[1;30]ДвухточечнаяСлабаяПропорц.0.989[1;30]Турнирная14[1;10]Ранговая17[1;17]Элитарная19[1;26]Средняя Пропорц.17[1;27]Турнирная14[1;10]Ранговая0.998[1;26]Элитарная110[1;22]Сильная Пропорц.18[1;29]Турнирная14[1;14]Ранговая0.9810[1;30]Элитарная0.9911[1;29]РавномернаяСлабая Пропорц.0.987[1;30]Турнирная14[1;11]Ранговая16[2;15]Элитарная18[1;21]Средняя Пропорц.0.997[0;26]Турнирная14[1;7]Ранговая0.998[1;24]Элитарная110[1;26]Сильная Пропорц.0.998[1;30]Турнирная14[1;10]Ранговая0.997[1;27]Элитарная0.999[1;30]

Приложение Б

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

Таблица Б.1 Усредненные результаты работы гибридного ГА для коэффициента готовности КА

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0,2921[5;35]Турнирная0,2917[3;35]Ранговая0,2621[9;35]Элитарная0,0419[16;23]СредняяПропорц.0,1416[5;33]Турнирная0,314[5;30]Ранговая0,213[9;18]Элитарная0,0622[13;35]Сильная Пропорц.0,0519[10;35]Турнирная0,1717[2;30]Ранговая0,027[3;12]Элитарная0,0124[24;24]ДвухточечнаяСлабаяПропорц.0,2921[8;34]Турнирная0,3914[4;35]Ранговая0,2922[8;35]Элитарная0,1423[10;34]СредняяПропорц.0,1129[23;35]Турнирная0,3819[3;33]Ранговая0,124[8;35]Элитарная0,0720[5;33]Сильная Пропорц.0,0721[10;29]Турнирная0,2315[2;35]Ранговая0,0317[8;24]Элитарная0,0232[30;35]РавномернаяСлабаяПропорц.0,3420[7;34]Турнирная0,3816[3;34]Ранговая0,3223[7;35]Элитарная0,1318[10;32]СредняяПропорц.0,1524[6;34]Турнирная0,3916[3;34]Ранговая0,1423[9;35]Элитарная0,1424[16;33]Сильная Пропорц.0,0618[5;34]Турнирная0,1718[6;34]Ранговая0,0419[8;34]Элитарная0,0517[8;24]

Таблица Б.2 Усредненные результаты работы гибридного ГА для коэффициента готовности ЦА

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0,4817[2;35]Турнирная0,5511[2;34]Ранговая0,4820[3;34]Элитарная0,2216[3;35]СредняяПропорц.0,3719[3;34]Турнирная0,5513[2;35]Ранговая0,316[5;35]Элитарная0,1919[5;32]Сильная Пропорц.0,1516[4;35]Турнирная0,3912[3;32]Ранговая0,1715[6;24]Элитарная0,0816[8;33]ДвухточечнаяСлабаяПропорц.0,5816[4;34]Турнирная0,511[2;34]Ранговая0,4220[3;35]Элитарная0,1920[10;32]Средняя Пропорц.0,3718[4;32]Турнирная0,4411[3;34]Ранговая0,3217[3;35]Элитарная0,1114[2;32]Сильная Пропорц.0,2219[6;34]Турнирная0,511[2;32]Ранговая0,1419[7;33]Элитарная0,0517[3;34]РавномернаяСлабая Пропорц.0,5716[5;34]Турнирная0,5311[3;33]Ранговая0,5818[5;35]Элитарная0,3421[9;32]Средняя Пропорц.0,3615[2;34]Турнирная0,6312[2;35]Ранговая0,320[9;32]Элитарная0,322[5;32]Сильная Пропорц.0,2917[3;34]Турнирная0,5412[2;31]Ранговая0,1819[4;32]Элитарная0,1118[11;25]

Таблица Б.3 Усредненные результаты работы гибридного ГА для коэффициента готовности БКУ

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0.918[2;29]Турнирная0,96[2;33]Ранговая0,939[2;35]Элитарная0,711[2;35]СредняяПропорц.0,968[2;31]Турнирная0,935[2;34]Ранговая0,910[2;34]Элитарная0,7911[2;32]Сильная Пропорц.0,999[2;27]Турнирная0,976[2;35]Ранговая0,8911[2;35]Элитарная0,712[2;32]ДвухточечнаяСлабаяПропорц.0,917[2;35]Турнирная0,897[2;29]Ранговая0,910[2;34]Элитарная0,6212[2;35]Средняя Пропорц.0,969[2;32]Турнирная0,996[2;33]Ранговая0,9110[2;35]Элитарная0,8110[2;35]Сильная Пропорц.0,9810[2;33]Турнирная16[2;31]Ранговая0,919[2;34]Элитарная0,7811[3;35]РавномернаяСлабая Пропорц.0,969[2;34]Турнирная0,985[2;35]Ранговая0,899[2;33]Элитарная0,899[2;32]Средняя Пропорц.0.998[2;31]Турнирная0,985[2;33]Ранговая0.939[2;35]Элитарная0.7911[2;32]Сильная Пропорц.19[2;33]Турнирная0.934[2;35]Ранговая0.9410[2;34]Элитарная0.7711[2;33]

Приложение В

Результаты выполнения оптимизации с помощью гибридного ГА для каждой из целевых функций при использовании концепции эволюции по Ламарку

Таблица В.1 Усредненные результаты работы гибридного ГА коэффициента готовности КА

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.0,995[2;12]Турнирная14[2;33]Ранговая15[3;16]Элитарная0,976[2;35]СредняяПропорц.16[2;32]Турнирная0,975[2;33]Ранговая17[2;29]Элитарная0,957[2;33]Сильная Пропорц.0,989[2;35]Турнирная0,977[2;30]Ранговая0,9810[2;35]Элитарная0,896[2;31]ДвухточечнаяСлабаяПропорц.15[2;27]Турнирная0,964[2;23]Ранговая16[2;24]Элитарная0,997[2;32]СредняяПропорц.17[2;35]Турнирная0,985[2;33]Ранговая18[2;23]Элитарная0,967[2;34]Сильная Пропорц.0,998[8;33]Турнирная0,947[2;33]Ранговая0,949[3;31]Элитарная0,898[2;35]РавномернаяСлабаяПропорц.15[2;10]Турнирная14[2;32]Ранговая15[2;25]Элитарная0,946[3;28]СредняяПропорц.16[2;20]Турнирная0,985[2;35]Ранговая0,997[2;27]Элитарная0,927[2;33]Сильная Пропорц.0,977[2;25]Турнирная0,926[2;33]Ранговая0,958[2;26]Элитарная0,878[2;35]

Таблица В.2. Усредненные результаты работы гибридного ГА коэффициента готовности ЦА

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.14[2;11]Турнирная13[2;25]Ранговая14[2;10]Элитарная16[2;17]СредняяПропорц.14[2;13]Турнирная13[2;11]Ранговая15[2;21]Элитарная17[2;28]Сильная Пропорц.15[2;21]Турнирная15[2;32]Ранговая16[2;30]Элитарная17[2;28]ДвухточечнаяСлабаяПропорц.14[2;16]Турнирная13[2;30]Ранговая14[2;21]Элитарная16[2;28]Средняя Пропорц.14[2;14]Турнирная13[2;18]Ранговая15[2;30]Элитарная0.997[2;35]Сильная Пропорц.15[2;20]Турнирная0.994[2;32]Ранговая17[2;32]Элитарная0.987[2;33]РавномернаяСлабая Пропорц.14[2;18]Турнирная13[2;22]Ранговая14[2;17]Элитарная17[2;29]Средняя Пропорц.14[2;24]Турнирная13[2;20]Ранговая14[2;19]Элитарная17[2;23]Сильная Пропорц.15[2;16]Турнирная0.994[2;27]Ранговая17[2;31]Элитарная0.979[2;34]

Таблица В.3 Усредненные результаты работы гибридного ГА для коэффициента готовности БКУ

РекомбинацияМутацияСелекцияНадежностьСкоростьИнтервалОдноточечнаяСлабаяПропорц.12[2;4]Турнирная12[2;6]Ранговая13[2;8]Элитарная12[2;6]СредняяПропорц.12[2;6]Турнирная12[2;5]Ранговая12[2;7]Элитарная12[2;8]Сильная Пропорц.12[2;7]Турнирная12[2;17]Ранговая13[2;23]Элитарная13[2;6]ДвухточечнаяСлабаяПропорц.12[2;6]Турнирная12[2;4]Ранговая12[2;6]Элитарная13[2;9]Средняя Пропорц.12[2;6]Турнирная12[2;3]Ранговая12[2;8]Элитарная13[2;11]Сильная Пропорц.12[2;6]Турнирная12[2;5]Ранговая13[2;13]Элитарная13[2;14]РавномернаяСлабая Пропорц.12[2;5]Турнирная12[2;4]Ранговая12[2;10]Элитарная12[2;5]Средняя Пропорц.12[2;5]Турнирная12[2;33]Ранговая13[2;10]Элитарная13[2;8]Сильная Пропорц.12[2;6]Турнирная12[2;10]Ранговая12[2;9]Элитарная13[2;8]

КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА Разработка и исследование гибридного алгоритма решения сложных задач опти

Больше работ по теме: