Разработка и исследование гибридного алгоритма решения сложных задач оптимизации
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Рис. 1.4 Пример одноточечного скрещивания
- При двухточечном скрещивании хромосому можно рассматривать как кольцо со связанными первым и последним генами. Кольцо рассекается на две части и полученные части обмениваются. Графическое представление двухточечного скрещивания представлено на рисунке 1.5, пример на рисунке 1.6.
Рис. 1.5 Двухточечное скрещивание
Или
Рисунок 1.6 Пример двухточечного скрещивания
- Равномерное скрещивание предполагает, что каждый ген потомка выбирается случайным образом из соответствующих генов родителей.
Замечание: в этом случае родителей может быть больше двух, в том числе возможно участие всей популяции родителей в целом (gene pool recombination) [5].
Мутация в ГА
Мутация состоит из выполнения (обычно небольших) изменений в значениях одного или нескольких генов в хромосоме. Мутация обеспечивает исследование пространства поиска.
В двоичных хромосомах мутация состоит в инвертировании случайным образом выбранного бита генотипа, например 1010 1000.
- В ГА мутация является методом восстановления потерянной генетической информации, а не методом поиска лучшего решения.
В ГА мутация применяется к генам с очень низкой вероятностью 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)
Следует отметить, что сигмоидная функция дифференцируема на всей оси абiисс, что используется в некоторых алгоритмах обучения. Кроме того, она обладает свойством усиливать слабые сигналы лучше, чем большие, и предотвращает насыщение от больших сигналов, так как они соответствуют областям аргументов, где сигмоид имеет пологий наклон.
Структура нейросетей
Искусственная нейронная сеть (ИНС, нейросеть) - это набор нейронов, соединенных между собой [7]. Как правило, передаточные функции всех нейронов в сети фиксированы, а веса являются параметрами сети и могут изменяться. Подавая любые числа на входы сети, мы получаем какой-то набор чисел на выходах сети. Таким образом, работа нейросети состоит в