Разработка и исследование гибридного алгоритма решения сложных задач оптимизации
Оптимизация показателей эффективности функционирования технологического контура системы управления космическим аппаратом, исследование свойств его показателей. Настройка нейронной сети, гибридизация генетического алгоритма с алгоритмами локального поиска.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | дипломная работа |
Язык | русский |
Дата добавления | 02.06.2011 |
Размер файла | 4,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
2
3
КВАЛИФИКАЦИОННАЯ РАБОТА
БАКАЛАВРА
Разработка и исследование гибридного алгоритма
решения сложных задач оптимизации
Оглавление
Введение
Глава 1 Теоретическая часть
1.1 Постановка задачи оптимизации показателей эффективности функционирования технологического контура системы управления космическим аппаратом
1.2 Алгоритмы целочисленной оптимизации
1.3 Генетический алгоритм
1.4 Искусственные нейронные сети
Глава 2. Практическая часть
2.1 Исследование свойств показателей эффективности функционирования технологического контура
2.2 Оптимизация показателей эффективности технологического контура генетическим алгоритмом
2.3 Настройка нейронной сети на целевые функции отдельно от процесса оптимизации и ее проверка в ГА
2.4 Настройка НС в процессе оптимизации с помощью ГА
2.5 Проверка настройки НС во время оптимизации ГА одномерных функций
2.6 Гибридизация генетического алгоритма с алгоритмами локального поиска
Заключение
Список используемой литературы
Список публикаций автора
Приложение А
Приложение Б
Приложение В
алгоритм гибридный нейронная оптимизация
Введение
Актуальность. На сегодняшний день требования к качеству создаваемых систем значительно возросли. Анализ надежности функционирования весьма затруднен в силу того, что любая сложная система включает в себя десятки и сотни тысяч элементов. Поэтому, необходима разработка таких компьютерных систем, которые позволяют принимать ЛПР более обоснованные решения. В данной диссертационной работе предполагается разработка и исследование КС с целью поддержки принятия решений на стадии предварительного проектирования систем управления космическими аппаратами.
На современном этапе развития науки возрастают требования к качеству создаваемых систем. На данный момент любая сложная система состоит из десятков и сотен тысяч элементов. Анализ надежности и эффективности функционирования таких систем значительно затруднен, что заставляет разработчиков применять сложные модели и алгоритмы на стадии предварительного проектирования, а также для поддержки принятия проектных и управленческих решений.
Задачи оптимизации, которые требуется решать на этапе предварительного оценивания и проектирования сложных систем, обладают свойствами, существенно затрудняющими их решение: дискретные или смешанные переменные, алгоритмически заданные целевые функции, отсутствие удобных для оптимизации свойств или, по крайней мере, отсутствие информации о таких свойствах, и т.д. Поэтому в таких задачах зачастую могут быть применены только алгоритмы прямого поиска, не требующие информации о свойствах оптимизируемой функции. Наиболее перспективными в настоящее время признаны так называемые эволюционные алгоритмы, теоретический анализ и практические применения которых до настоящего времени испытывают серьезные трудности.
В этой связи можно утверждать, что разработка таких алгоритмов и оценивание их эффективности на реальных практических задачах, чему посвящена данная работа, являются актуальной научно-технической проблемой.
Целью квалификационной работы является разработка и исследование гибридного эволюционного алгоритма решения сложных задач оптимизации.
В качестве объекта исследований в данной работе рассматривается технологический контур системы управления космическим аппаратом связи и ретрансляции при предположении, что наземный комплекс управления является абсолютно надежным.
Поставленная цель исследования предопределила следующую совокупность решаемых задач:
1. Исследовать свойства целевых функций в рассматриваемой задаче оптимизации сложной системы.
2. Выбрать и реализовать подходящие алгоритмы для решения поставленных задач оптимизации.
3. Провести исследование эффективности алгоритмов и установить их оптимальную структуру.
4. Проанализировать достоинства и недостатки алгоритмов.
5. Используя современные технологии и методы выполнить модификацию алгоритмов с целью устранения выявленных недостатков.
6. Программно реализовать разработанный модифицированный алгоритм и исследовать его эффективность на решаемой практической задаче.
Методы исследования. При выполнении квалификационной работы использовался аппарат системного анализа, исследования операций, теории оптимизации, теории вероятностей и математической статистики, методика создания прикладных интеллектуальных систем.
Научная новизна работы заключается в следующем:
1. Установлено, что показатели эффективности технологического контура системы управления космическим аппаратом в общем случае являются многоэкстремальными и немонотонными.
2. Впервые проведено сравнение гибридного генетического алгоритма, моделирующего эволюцию по Дарвину и по Ламарку, со стандартным генетическим алгоритмом на задаче оптимизации показателей эффективности сложной системы.
3. Обоснована целесообразность использования нейросетевой аппроксимации показателей эффективности технологического контура системы управления космическим аппаратом в задаче выбора эффективного варианта технологического контура при использовании как стандартного, так и гибридного генетического алгоритма.
Практическая значимость. Предложенный в работе подход и разработанные алгоритмы могут быть использованы при проектировании и управлении сложными системами различного назначения. Программные системы и результаты численных расчетов переданы в НПО прикладной механики.
Разработанные в ходе выполнения работы программные системы использовались в процессе обучения студентов Красноярского государственного университета и Сибирского государственного аэрокосмического университета по курсам "Методы оптимизации", "Эволюционные методы оптимизации", "Управление сложными системами", "Адаптивные и эволюционные методы принятия решений", а также при выполнении курсовых работ.
Основные положения, выносимые на защиту:
1. Показатели эффективности технологического контура системы управления космическим аппаратом являются многоэкстремальными и немонотонными.
2. Генетический алгоритм в комбинации с локальным поиском, моделирующий эволюцию по Ламарку, превосходит по эффективности стандартный генетический алгоритм при решении сложных задач оптимизации.
3. Целевая функция может быть заменена в процессе оптимизации генетическими алгоритмами на ее нейросетевую аппроксимацию, что позволяет существенно снизить время оптимизации при сохранении надежности отыскания глобального экстремума.
Апробация работы. Процесс разработки и результаты, представленные в квалификационной работе докладывались и обсуждались на следующих конференциях:
ь 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:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
2
3
Рис. 1.1 Схема представления системы управления КА в простейшем случае
При моделировании процесса функционирования ТК используется теория Марковских процессов [1]. В данной задаче математическая модель функционирования ТК представляет собой Марковский процесс с дискретными состояниями и непрерывным временем [2]. При условии, что НКУ абсолютно надежен, соответствующий Марковский процесс имеет граф состояний, представленный на рисунке 1.2 [3].
Рис. 1.2 Граф состояний технологического контура управления в простейшем случае
Описание состояний технологического контура:
1. Все подсистемы работоспособны.
2. Целевая аппаратура отказала, БКУ работоспособен и занят восстановлением работоспособности ЦА, НКУ свободен.
3. Целевая аппаратура работоспособна, БКУ отказал, НКУ восстанавливает работоспособность БКУ.
4. Целевая аппаратура отказала, БКУ работоспособен и свободен, НКУ занят восстановлением работоспособности ЦА.
5. Целевая аппаратура и БКУ отказали, НКУ восстанавливает работоспособность ЦА, БКУ ожидает окончания восстановления ЦА.
В графе через обозначены интенсивности выхода из строя, а через i - интенсивности восстановления подсистем. Соответствующая система уравнений Колмогорова-Чэпмена имеет следующий вид (1.1.1):
P1(1+2) - 1p0P2 - 3P3 - 2P4 = 0,
P2(1+2) - 1P1 = 0,
P3(1+3) - 2P1 - 2P5 = 0,
P4(2+2) - (1-p0)1P2 = 0, (1.1.1)
P52 - 2P2 - 1 P3 - 2P4 = 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) = ,
N2(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 произвольно.
2. Поочередно просматриваем 1-соседние точки X0 и вычисляем значения функции в получаемых точках. Запоминаем изменение, приведшее к улучшению.
3. Если ни одно улучшение не найдено, то X0 - точка минимума, остановиться и вывести ответ.
4. Заменяем все координаты X0 на те, которые приводили к улучшению, и вычисляем значение функции в полученной точке. Обозначаем полученную точку через X0.
5. Поочередно изменяем координаты точки X0 таким образом, который приводил к улучшению на предыдущем шаге и вычисляем значения функции в получаемых точках.
6. Если ни одно улучшение не найдено, то проверяем остальные точки окрестности.
7. Перейти к шагу 3.
Алгоритм локального поиска на целочисленной решетке по системе окрестностей N2(X)
1. Стартовую точку выбрать произвольно.
2. Увеличивать каждую координату по очереди на два и вычислять значения целевой функции. Если улучшения не произошло, то уменьшать ту же координату на два и вычислять значение функции. В случае улучшения значения функции переходить в точку, дающую такое улучшение, и продолжать со следующей координаты.
3. Если изменение всех координат на два не дает улучшения функции, то начинать просмотр всех пар координат в порядке 1-2, 1-3, … , 2-3, 2-4, …, увеличивая и уменьшая каждую координату пары на единицу. Если получено улучшение целевой функции, то переходить в точку, дающую улучшение, и продолжать с шага 2.
4. Если на втором и третьем шаге не получено улучшения, то увеличивать и уменьшать каждую координату на единицу, вычисляя значение функции и запоминая лучшее из них вместе с дающей его точкой.
5. Вывести наилучшее значение целевой функции и точку, в которой это значение получено.
Неулучшаемый алгоритм псевдобулевой оптимизации
1. Произвольно выбираем точку X0D.
2. Последовательно инвертируем координаты булева вектора, определяя все точки Xj Ol(X), j = 1, …, n, 1-соседние к X0 (n - длина битовой строки).
4. Координаты оптимальной точки Х* получаем по правилу:
Примечание. Данному алгоритму требуется ровно n+1 вычислений целевой функции для получения точки локального оптимума произвольной монотонной псевдобулевой функции.
Обобщенный алгоритм локального поиска для оптимизации унимодальных псевдобулевых функций
1. Произвольно выбираем точку X1 и определям ее (n/2)-соседние точки X2, X3, … , Xn, вычисляем значения функции в этих точках.
2. Генерируем точки Yj = (), j = 1, 2, …, n и вычисляем значения функции в этих точках.
3. Определяем точку X* по правилу
и вычисляем значение функции в ней.
4. Если f(X*)<f(Xj) j = 1, 2, …, n и f(X*)<f(Yj) j = 1, 2, …, n, то необходимо определить все точки Zi O1(X*) и вычислить значения функции в них. Далее выполнять с шага 6.
5. Если f(X*)<f(Zi) i = 1, 2, …, n, то вывести X*, f(X*) и остановиться (X* - точка минимума, функция f - унимодальная и монотонная).
6. Выбрать точку X0 из условия
f(X0) = min {f(X*), f(Xj), f(Yj), f(Zj), j = 1, 2, ..., n}
7. Определять точки Xj O2(X0), j = 1, 2, …, и вычислять f(Xj) до тех пор, пока не будет найдена такая точка Xj, что f(Xj)<f(X0).
8. Если точка найдена, тогда X0 = Xj и вернуться к шагу 7.
9. Среди точек Xk O1(X0) выбрать точку X*, дающую наименьшее значение функции.
10. Если 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 быть отобранным.
Используемое распределение вероятностей:
Линейное: pi = ai + b (a < 0).
Преимущества:
Нет преждевременной сходимости, т.к. нет индивидов с Ni >> 1.
Нет стагнации, так как и к концу работы алгоритма N1 N2 … .
Нет необходимости в явном вычислении пригодности, т.к. для упорядочения индивидов достаточно иметь возможность их по парного сравнения.
Недостатки: значительные накладные расходы на переупорядочивание и трудность теоретического анализа сходимости.
Турнирная селекция
Одна из самых простых в реализации и эффективных в оптимизации является турнирная селекция. Для отбора индивида создается группа из M (M 2) индивидов, выбранных из текущей популяции случайным образом
Индивид с наибольшей пригодностью в группе отбирается, остальные - игнорируются
Преимущества:
Нет преждевременной сходимости
Нет стагнации
Не требуется глобальное переупорядочивание
Не требуется явное вычисление функции пригодности
Элитарная селекция
В данной селекции один или несколько лучших индивидов популяции всегда проходит в следующее поколение
Преимущество: гарантия сходимости, т.е. если глобальный максимум будет обнаружен, то ГА сойдется к этому максимуму
Недостаток: слабая глобальная сходимость, большой риск найти локальный минимумом
Скрещивание в ГА
Оператор скрещивание предназначен для поиска новых решений на основе отобранных селекцией родителей.
· Одноточечное скрещивание представляет собой разделение родительских хромосом в выбранной случайным образом общей точке и обмен правыми частями. (ТС - точка скрещивания). Пример одноточечного скрещивания представлена на рисунке 1.4.
Рис. 1.4 Пример одноточечного скрещивания
При двухточечном скрещивании хромосому можно рассматривать как кольцо со связанными первым и последним генами. Кольцо рассекается на две части и полученные части обмениваются. Графическое представление двухточечного скрещивания представлено на рисунке 1.5, пример на рисунке 1.6.
Рис. 1.5 Двухточечное скрещивание
Или
Рисунок 1.6 Пример двухточечного скрещивания
Равномерное скрещивание предполагает, что каждый ген потомка выбирается случайным образом из соответствующих генов родителей.
Замечание: в этом случае родителей может быть больше двух, в том числе возможно участие всей популяции родителей в целом (gene pool recombination) [5].
Мутация в ГА
Мутация состоит из выполнения (обычно небольших) изменений в значениях одного или нескольких генов в хромосоме. Мутация обеспечивает исследование пространства поиска.
В двоичных хромосомах мутация состоит в инвертировании случайным образом выбранного бита генотипа, например 1010 1000.
В ГА мутация является методом восстановления потерянной генетической информации, а не методом поиска лучшего решения.
В ГА мутация применяется к генам с очень низкой вероятностью pm [0.001, 0.01]. Хорошим эмпирическим правилом считается выбор вероятности мутации из соотношения pm = , где H - число бит в хромосоме. На основе этого правила можно произвести классификацию мутации таким образом:
1. Слабая (pm < ),
2. Средняя (pm =)
3. Сильная (pm > )
Обобщенная пошаговая структура ГА
1. Сгенерировать случайным образом начальную популяцию.
2. Оценить полученную популяцию.
3. Генерировать популяцию потомков.
Селекция (выбор двух индивидов из текущей популяции).
Рекомбинация (скрещивание выбранных индивидов).
Мутация (генетическое изменение полученного потомка).
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)
При уменьшении сигмоид становится более пологим, в пределе при =0 вырождаясь в горизонтальную линию на уровне 0.5, при увеличении сигмоид приближается по внешнему виду к функции единичного скачка с порогом T в точке x=0. Из выражения для сигмоида очевидно, что выходное значение нейрона лежит в диапазоне [0,1]. Одно из ценных свойств сигмоидной функции - простое выражение для ее производной, применение которого будет рассмотрено в дальнейшем.
(1.2.2)
Следует отметить, что сигмоидная функция дифференцируема на всей оси абсцисс, что используется в некоторых алгоритмах обучения. Кроме того, она обладает свойством усиливать слабые сигналы лучше, чем большие, и предотвращает насыщение от больших сигналов, так как они соответствуют областям аргументов, где сигмоид имеет пологий наклон.
Структура нейросетей
Искусственная нейронная сеть (ИНС, нейросеть) - это набор нейронов, соединенных между собой [7]. Как правило, передаточные функции всех нейронов в сети фиксированы, а веса являются параметрами сети и могут изменяться. Подавая любые числа на входы сети, мы получаем какой-то набор чисел на выходах сети. Таким образом, работа нейросети состоит в преобразовании входного вектора в выходной вектор, причем это преобразование задается весами сети.
Как построить такую сеть? Этот вопрос решается в два этапа:
1. Выбор типа (архитектуры) сети.
2. Подбор весов (обучение) сети.
На первом этапе следует выбрать следующее:
· какие нейроны мы хотим использовать (число входов, активационные функции);
· каким образом следует соединить их между собой;
· что взять в качестве входов и выходов сети.
Эта задача на первый взгляд кажется необозримой, но, к счастью, необязательно придумывать нейросеть «с нуля» - существует несколько десятков различных нейросетевых архитектур, причем эффективность многих из них доказана математически. Наиболее популярные и изученные архитектуры - это многослойный персептрон, нейросеть с общей регрессией, сети Кохонена и другие.
На втором этапе нам следует «обучить» выбранную сеть, то есть подобрать такие значения ее весов, чтобы сеть работала нужным образом. В используемых на практике нейросетях количество весов может составлять несколько десятков тысяч, поэтому обучение - действительно сложный процесс. Для многих архитектур разработаны специальные алгоритмы обучения, которые позволяют настроить веса сети определенным образом. Наиболее популярный из этих алгоритмов - метод обратного распространения ошибки (Error Back Propagation), используемый, например, для обучения персептрона.
Обучение сети
Способность к обучению является фундаментальным свойством мозга. В контексте ИНС процесс обучения может рассматриваться как настройка архитектуры сети и весов связей для эффективного выполнения специальной задачи. Обычно нейронная сеть должна настроить веса связей по имеющейся обучающей выборке. Функционирование сети улучшается по мере итеративной настройки весовых коэффициентов
Обучить нейросеть - значит, подобрать такие веса синапсам сети, чтобы на любой выходной вектор сеть выдавала адекватный (правильный) выходной вектор значений. При обучении на каждой итерации корректируются веса сети в направлении антиградиента ошибки E (Е - функция, зависящая от весов сети). Для этого на каждой итерации требуется рассчитывать компоненты градиента. Однако, для этого необходимо подать входной вектор и просчитать выходные значения для всех нейронов в сети. Это - очень большой объем вычислений. Если учесть, что требуется рассчитать все компоненты градиента, таким образом, неэффективность такого подхода становится очевидной.
Алгоритм обратного распространения - способ ускоренного расчета компонент градиента. Идея метода в том, чтобы представить E в виде сложной функции и последовательно рассчитать частные производные по формуле для сложной функции. Оказывается, что после многократного предъявления примеров веса сети стабилизируются, причем сеть дает правильные ответы на все примеры из обучающей выборки. В таком случае говорят, что «сеть выучила все примеры», «сеть обучена», или «сеть натренирована». В процессе обучения величина ошибки (сумма квадратов ошибок по всем выходам) постепенно уменьшается. Когда величина ошибки достигает нуля или приемлемого малого уровня, тренировку останавливают, а полученную сеть считают натренированной и готовой к применению на новых данных.
Качество обучения сети напрямую зависит от количества примеров в обучающей выборке, а также от того, насколько полно эти примеры описывают данную задачу. Считается, что для полноценной тренировки требуется хотя бы несколько десятков (а лучше сотен) примеров.
Глава 2. Практическая часть
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. Битовая строка декодируется в вещественное число - шаг обучения.
3. Сети предъявляются все образы. Происходит настройка сети с шагом обучения, полученным на этапе 2. Вычисляется ошибка сети.
4. Если сеть настроена с заданной точностью или число генерированных строк равно числу, указанному пользователем, то настройка сети считается законченной.
5. Если ошибка уменьшается, то инвертируем в битовой строке текущего шага обучения 0 на 1 (0 выбирается случайно) - увеличиваем шаг с целью более быстрого спуска в точку минимума ошибки сети, иначе инвертируем в битовой строке текущего шага обучения 1 на 0 (1 также выбирается случайно) - уменьшаем шаг с целью локализации найденного минимума ошибки сети и спуска в него. Переходим к этапу 2.
6. Если инвертирование невозможно тогда переходим на этап 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).
2.4 Настройка НС в процессе оптимизации с помощью ГА
Как уже говорилось выше необходимо совместить два этапа (оптимизацию и настройку сети) в одном процессе.
Известно, что ГА на первых шагах своей работы охватывает большую часть оптимизируемого пространства, поэтому предлагается использовать точки, сгенерированные ГА, в качестве точек, по которым проводится настройка НС. После обучения далее продолжается оптимизация, то есть генерируются новые точки ГА, по которым проверяется обученность НС, и так далее. Также для ускорения обучения было предложено использовать не все точки сгенерированные ГА в обучении НС, а только те которые дают наибольшую ошибку экзамена обучения. Такой алгоритм можно представить в виде пошаговой структуры так:
Алгоритм ГА+НС:
1. Проводится оптимизация ГА по n1 первым точкам, которые записываются в обучающую выборку.
2. По записанным в обучающую выборку n1 точкам проводится настройка НС.
3. По следующим n2 точкам проводим соответствующие шаги ГА.
4. Вновь полученные n2 точек используем в качестве экзамена для обучающейся НС.
5. Если ошибка экзамена НС недопустимая, то дописываем k (k<n2) точек дающих наибольшую ошибку в обучающую выборку и если целевая НС выполняет роль вычисления целевой функции, то необходимо заменить ее на систему уравнений Колмогорова-Чепмена. Получаем n1 = n1 +k . Переходим на шаг 2.
6. Иначе заменяем целевую функцию (систему уравнений Колмогорова-Чепмена) на обученную НС при выполенении оптимизации ГА. Переходим на шаг 3.
Описанный алгоритм был реализован автором на языке высокого уровня С++ в оболочке Builder 5.0. Начальное окно программы изображено на рис 2.13.
Рис. 2.13 Начальное окно программы “Гибрид ГА и НС”
Настройки в данном случае аналогичны приведенным ранее. Следует только отметить, что пользователь может остановить процесс, изменить настройки, запустить его заново, не закрывая программы (кнопка “Стоп”), или сделать паузу, то есть временно остановить работу программы с заданными настройками и, не меняя их продолжить, нажав на кнопку “Пауза”.
Новый раздел “Параметры обучающей выборки” включает следующие настройки:
· “Начальное число точек обучения” - это то количество начальных точек, которое просматривает ГА. После чего запускается в первый раз функция настройки сети.
· “Число точек экзамена” это количество точек, которое ГА просматривает после настройки сети и на которых проверяется, насколько хорошо сеть была настроена.
В этой программе-гибриде соединены две вышеописанных программы - генетический алгоритм и нейронная сеть, в ее основе лежит алгоритм ГА+НС.
Что касается результатов, то заранее предполагалось, что вычисление по нейронной сети сократит время оптимизации, но практика показывает иное. Мало того, что за время оптимизации сеть не удалось настроить, да еще пришлось потратить рабочее время программы на обучение НС, а она оказалась не нужной.
Выводы:
Нейронную сеть в ходе процесса оптимизации ГА не удалось настроить. Автором предполагаются следующие возможные причины:
Подобные документы
Исследование нечеткой модели управления. Создание нейронной сети, выполняющей различные функции. Исследование генетического алгоритма поиска экстремума целевой функции. Сравнительный анализ нечеткой логики и нейронной сети на примере печи кипящего слоя.
лабораторная работа [2,3 M], добавлен 25.03.2014Сравнение результатов работы генетического алгоритма по решению "несимметричной незамкнутой задачи коммивояжера" с результатами работы алгоритма динамического программирования по параметрам - время работы, точность результата и объем используемой памяти.
курсовая работа [65,3 K], добавлен 16.04.2014Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.
лабораторная работа [20,2 K], добавлен 03.12.2014Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа [784,0 K], добавлен 21.05.2015Основные положения, связанные с маршрутизацией компьютерных сетей и её видами, протоколами маршрутизации и их разновидностями, алгоритмами маршрутизации, их классификацией, типами и свойствами. Разработка программы и моделирование компьютерной сети.
курсовая работа [1,8 M], добавлен 04.11.2012Разработка алгоритма и программы для распознавания пола по фотографии с использованием искусственной нейронной сети. Создание алгоритмов: математического, работы с приложением, установки весов, реализации функции активации и обучения нейронной сети.
курсовая работа [1,0 M], добавлен 05.01.2013Основные этапы создания алгоритмов, представление в виде программы. Рассмотрение методов решения задач. Метод поэтапных уточнений. Различие между численными и логическими алгоритмами. Реализация цикла со счетчиком. Процесс разработки сложного алгоритма.
презентация [1,3 M], добавлен 22.10.2013Характеристика методов нечеткого моделирования и изучение системы кластеризации в пакетах прикладных программ. Разработка и реализация алгоритма для оптимизации базы правил нечеткого классификатора с помощью генетического алгоритма аппроксимации функции.
дипломная работа [1,9 M], добавлен 21.06.2014Исследование системы распределения ключей на основе линейных преобразований. Описание компонентов сети конфиденциальной связи. Характеристика отечественного алгоритма шифрования данных. Обзор результатов расчетов криптостойкости алгоритма шифрования.
контрольная работа [56,5 K], добавлен 26.09.2012Описание генетических алгоритмов. Применение генетического алгоритма для решения задачи коммивояжера. Постановка задачи безусловной оптимизации. Изучение распространения генетических алгоритмов на модель с несколькими взаимодействующими популяциями.
дипломная работа [979,1 K], добавлен 30.05.2015