Введение в эволюционные алгоритмы. Комбинаторная оптимизация методом генетического поиска.
Нейронные сети с нечеткой логикой. Конечные автоматы и нейронные сети.
Методы анализа информации при помощи ЭВМ постоянно совершенствуются.
При этом, наряду с прочно устоявшимися и широко применяемыми методиками математического
моделирования все шире развиваются и используются другие, нетрадиционные подходы.
Один из них, связанный с искусственными нейронными сетями, составляет главный предмет этой
книги.
Для полноты картины автор счел необходимым дать краткий обзор прочих
методов, и, прежде всего, генетических алгоритмов, систем с нечеткой логикой и клеточных
автоматов. Чтобы не нарушать цельность изложения, эти методы будут рассматриваться в их
соотношении с нейросетевыми алгоритмами.
Генетический поиск.
Успех в развитии нейронных
сетей не в последнюю очередь связан глубокими биологическими основаниями, заложенными во
многих архитектурах. Некоторые особенности биологической эволюции, на уровне механизма
кодирования и наследования в ДНК, легли в основу так называемых генетических
алгоритмов, предложенных в начале 70-х годов (J.H.Holland, 1975) и получивших
интенсивное развитие в последнее время.
Произвольный объект или система (в биологии - организм) могут
быть описаны совокупностью признаков или черт, которые кодируются цепочкой символов или
битов и составляют генотип объекта. Несколько объектов формируют популяцию,
характеризующуюся набором цепочек каждого из объектов, совокупность которых определяет
генофонд популяции.
Различные объекты могут иметь, вообще говоря, разные наборы признаков. О
большом разнообразии признаков и популяции говорят как о богатом генофонде. При эволюции
популяции в ней появляются новые объекты, наследующие те или иные признаки от своих
предков. При этом размер популяции в целом изменяется мало, что обеспечивается конкурентным
отбором объектов. В процессе отбора производится направленный поиск таких признаков
или их совокупностей (кодонов и генов), которые являются ценными в смысле некоторой
заданной целевой функции, например уровня адаптации объекта к условиям
существования. Поэтому эволюционные алгоритмы также называют методами генетического
поиска.
Обработка информации
генетическим алгоритмом использует два основных механизма отбора полезных признаков,
заимствованных из современных представлений о естественном отборе: мутации в
отдельной цепочке и скрещивание (кроссинговер) между двумя цепочками. Рассмотрим эти
механизмы подробнее.
|
001110101100001001
000110100001101001
|
а) Исходные генетические цепочки |
|
0011101
.......01100001001
.......00001101001
0001101
|
б) Случайное образование области для последующего скрещивания |
|
0011101
.......00001101001
.......01100001001
0001101
|
в) Обмен фрагментами кода |
|
001110100001101001
000110101100001001 |
г) Цепочки после скрещивания |
Рис П2.1. Процесс скрещивания двух генетических цепочек.
На рисунке П2.1 представлены
последовательные этапы обмена информацией между двумя цепочками при скрещивании. Полученные
новые цепочки (или одна из них) могут быть в дальнейшем включены в популяцию, если
задаваемый ими набор признаков дает лучшее значение целевой функции. В противном случае они
будут отсеяны, а в популяции останутся их предки. Мутация в генетической цепочке носит
точечный характер: в некоторой случайной точке цепочки один из кодов заменяется другим
(ноль - единицей, а единица - нулем).
С точки зрения искусственных систем обработки информации генетический
поиск представляет собой специфический метод нахождения решения задачи оптимизации. При
этом такой итерационный поиск является адаптирующимся к особенностям целевой функции:
рождающиеся в процессе скрещивания цепочки тестируют все более широкие области пространства
признаков и примущественно располагаются в области оптимума. Относительно редкие мутации
препятствуют вырождению генофонда, что равносильно редкому, но не прекращающемуся поиску
оптимума во всех остальных областях признакового пространства.
Генетический алгоритм может быть применен для обучения нейронной сети.
При этом цепочкой кодируется состояние сети - совокупность всех весовых коэффициентов. Код
может быть устроен следующим образом. Первые восемь элементов цепочки соответствуют
8-битному представлению первого элемента матрицы весов, следующие восемь - второму, и так
далее. Целевой функцией выступает полная ошибка обучения. Популяция нейронных сетей
эволюционирует к обученному состоянию, при этом в процессе отбора выживают цепочки,
кодирующие нейронные сети с малыми ошибками.
Генетический алгоритм является примером задачи, допускающей высокую
степень параллельности при моделировании на современных векторных ЭВМ. Простота выполняемых
операций открывает также широкие перспективы для разработки специализированных
генетических процессоров.
Системы нечеткой логики.
Нечеткая логика (fuzzy logic)
является обобщением привычной булевой логики, оперирующей с двоичными числами, которые
соответствуют понятиям истина и ложь. В нечеткой логике эти понятия
обобщаются и на все промежуточные между истиной и ложью состояния. В соответствии с этим
нечеткая логика оперирует числами из интервала [0,1], которые отражают степень истинности
высказывания. Впервые теория нечетких множеств была сформулирована профессором
Калифорнийского университета Заде.
Нечеткая логика опирается на многие практические потребности прикладных
наук, оперирующих с не полностью достоверной и противоречивой информацией. К ним относятся
теория управления и принятия решений по неполной информации, системная экология,
занимающаяся оценками риска от техногенного воздействия промышленных производств и
последствиями аварий, макроэкономика и другие.
Переход от двоичного представления чисел к интервальному требует
обобщения логических операций на соотвествующие операции с нечеткими числами. При этом
обобщеные операции должны переходить в классические, если операнды имеют значения 0 или 1.
Рассмотрим пример такого обобщения. Пусть имеются нечеткие числа a и b.
Суммой двух нечетких чисел называется нечеткое число, совпадающее с максимальным операндом:
c = a + b = max(a,b). Произведением двух нечетких чисел называется нечеткое число, равное
минимальному операнду: c = a * b = min(a,b). В соответствии с введенными определениями
множество нечетких чисел является
замкнутым относительно данных операций.
Одним из важных примененний нечеткой логики выступают нечеткие
экспертные системы (НЭС), в которых логические правила вывода оперируют с нечеткими
операциями. Для знакомства с НЭС и другими приложениями нечеткой логики можно
порекомендовать книгу японских авторов Т.Тэрано, К.Асаи и М.Сугэно.
В этой части книги мы
остановимся на формулировке нейросетевых моделей на языке нечеткой логики. В модели
Хопфилда (Лекция 8) с обучением сети по правилу Хэбба все
вычисления основаны на операциях
сложения и умножения. Если описывать значения весов и активности нейронов нечеткими
числами, то правило Хэбба может быть сформулировано на языке нечетких операций. Вклад в
матрицу связей от образа
x(k) принимает вид:
Полная матрица связей
получается нечетким суммированием отдельных вкладов:
Вычисление активности
нейронов производится на с использованием скалярного произведения:
Представленная в нечеткой
арифметике нейронная сеть Хопфилда очень удобна для моделирования с использованием обычной
теневой оптики. Операнды могут представляются прямоугольными отверстиями, площади которых
пропорциональны величинам чисел.
Для умножения чисел отверстия
следует наложить друг на друга, при этом пропускание света будет ограничено
минимальным отверстием, которое и дает требуемое произведение. При сложении следует
фокусировать на одну плоскость два параллельных луча света, каждый из которых пропущен
независимо через одно из отверстий. Полученное световое пятно будет соответствовать
максимальному отверстию. Соотвествующая оптическая схема сети Хопфилда была
предложена и опубликована в журнале Optics Letters.
Необходимо отметить, что
оптическая реалиазация нейронной сети Хопфилда с нечетким правилом Хэбба естественным
образом обладает большой скоростью вычислений и высоким уровнем параллелизма.
Клеточные автоматы и нейронные сети.
Клеточным автоматом называют
сеть из элементов, меняющих свое состояние в дискретные моменты времени в зависимости от
состояния самого элемента и его ближайших соседей в предшествующий момент времени.
Различные клеточные автоматы могуть демонстрировать весьма разнообразное
поведение, которое может быть адаптировано для целей обработки информации за счет выбора
(а) закона изменения состояния элемента и (б) конкретного определения понятия “ближайшие
соседи”. Внимательный читатель без труда заметит, что, например, нейронная сеть Хопфилда
вполне может рассматриваться, как клеточный автомат, элементами которрого являются
формальные нейроны. В качестве закона изменения состояния нейро-автомата используется
пороговое преобразование взвешенной суммы входов нейронов, а ближайшими соседями каждого
элемента являются все прочие элементы автомата.
В мире клеточных автоматов имеется класиификация (S. Wolfram, 1983),
согласно которой все автоматы делятся на четыре класса, в зависимости от типа динамики
изменяющихся состояний. Автоматы первого класса по истечении конечного времени
достигают
однородного состояния, в котором значения всех элементов одинаковы и не меняются со
временем. Ко второму классу автоматов относятся системы, приводящие к локализованным
структурам стационарных или периодических во времени состояний элементов. Третий
класс составляют “блуждающие” автоматы, которые с течением времени посещают
произвольным (непериодическим) образом все возможные состояния элементов, не
задерживаясь ни в одном из них. И, наконец, четвертый класс составляют “странные” автоматы,
характер динамики которых зависит от особенностей начального состояния элементов. Некоторые
начальные состояния приводят к однородному вырождению автомата, другие - к возникновению
циклической последовательности состояний, третьи - к непрерывно меняющимся (как “по
системе”, так и без видимой системы) картинам активности элементов.
К автоматам четвертого типа относится знаменитая игра “Жизнь” Дж.
Конвея. Каждый элемент (организм) колонии “Жизни” может находиться в состоянии покоя или
активности. Ближайшими к данному элементу объявляются четыре его соседа на квадратной
решетке. Покоящийся элемент может возродиться к активности, если рядом с ним находится
ровно три активных соседа. Активный элемент сохраняет “жизнеспособность” при двух активных
соседях. Если соседей больше чем два, то элемент гибнет от тесноты, а если их меньше, чем
два, то гибель наступает от скуки. Хотя наблюдение за сложной эволюцией начального
состояния “Жизни” может дать определенную пищу для мыслительной исследовательской
деятельности, в целом этот автомат остается не более чем математическим курьезом.
Существуют, однако, более серьезные приложения клеточных автоматов.
Среди них прежде всего следует выделить автоматы, реализующие дискретные разностные схемы
для решения разнообразных задач математической физики. Для этих целей используются автоматы
второго рода.
Активность популяции элементов автомата может также описывать такие
сложные явления, как рост кристаллов из зародышевых состояний, диффузию и миграцию жидкости
в неоднородной пористой среде, особенности возникновения и развития турбулентности о
потоках жидкостей и газов, распространение импульса в нервной системе, рост опухоли в
биологической ткани, развитие лесных пожаров и другие явления. Описание разнообразных
применений клеточных автоматов заслуживает отдельного пристального внимания.
Однако это уже составляет предмет другой книги.
Задачи.
1. Сформулируйте задачу
поиска минимума функции f(x)=(x-0.5)2 на отрезке [0,1] для генетического
алгоритма.
2. К какому типу клеточных
автоматов относится классическая нейронная сеть Хопфилда? Каков тип автомата, задаваемого
вероятностным обобщением сети Хопфилда (Лекция 9) при очень
высоких температурах?
Почему?
|
материалы 