Генетическое программирование
Идею ГП - впервые предложил Коза в 1992 году, опираясь на концепцию генетических алгоритмов (ГА).
Эта идея заключается в том, что в отличие от ГА в ГП все операции производятся не над строками, а над деревьями.
При этом используются такие же операторы, как и в ГА: селекция, скрещивание и мутация.
В ГП хромосомами являются программы.
Программы представлены как деревья с функциональными (промежуточные) и терминальными (конечные) элементами.
Терминальными элементами являются константы, действия и функции без аргументов, функциональными - функции, использующие аргументы.
Пример.
Функция d -x/(21* b ) .
Терминальные элементы T = {d ,x,21, b } ,
Функциональные F = {-,/,*} .
Древовидное представление функции d -x/(21* b )
Для того чтобы применить ГП к какой-либо проблеме, необходимо определить:
¾ Множество терминальных элементов.
¾ Множество функциональных элементов.
¾ Меру приспособленности (fitness).
¾ Параметры, контролирующие эволюцию.
¾ Критерий останова эволюции.
О собенности операторов ГП
Алгоритм работы ГП такой же как и ГА:
¾ селекция,
¾ скрещивание и
¾ мутация.
Особенности: поскольку ГП оперирует над деревьями, а не над строками, то операторы скрещивания и мутации имеют отличия.
Скрещивание - выбираются случайные части родительских деревьев и
эти части меняются местами.
В ГП размер хромосомы меняется.
Чтобы предотвратить чрезмерное разрастание дерева, вводят:
• максимальное количество функциональных элементов в дереве или
• максимальную глубину дерева.
Однако при операции скрещивания возможна ситуация, когда при скрещивании двух деревьев получится одно из деревьев, превосходящее заданный лимит.
В этом случае вместо конфликтного дерева копируется родительское дерево.
Мутация
Оператор мутации случайно удаляет часть дерева и заменяет ее новым деревом
Примеры использования ГП
(Просто почитать)
Игра Змейка.
Игра начинается с фиксированного количества сегментов тела змейки. Змейка может менять направления движения влево или вправо либо двигаться вперед. В течении игры на доске находится только один кусок еды. Если змейка съедает его, то у нее увеличивается хвост и на доске появляется в случайном месте другая еда. Игра заканчивается, когда змейка врезается в свой хвост или в бордюр.
Робот собирающий еду.
Робот гуляет в двумерном мире. Каждая клетка может быть стеной, травой, едой или миной. Программа берет на вход данные с сенсоров робота. Ее запуск делает один шаг робота, при многократном выполнении (прогон) происходит ходьба. В качестве поощрения используется еда. В частности, рассмотрен гуляющий вдоль стен робот [Koza 1992].
44. Искусственные нейронные сети.
Иску́сcтвенная нейро́нная се́ть — это математическая модель, а также устройства параллельных вычислений, представляющие собой систему соединённых и взаимодействующих между собой простых процессоров (искусственных нейронов). Как математическая модель искусственная нейронная сеть представляет собой частный случай методов распознавания образов или дискриминантного анализа.
Такие процессоры обычно довольно просты, особенно в сравнении с процессорами, используемыми в персональных компьютерах.
Каждый процессор подобной сети имеет дело только с сигналами, которые он периодически получает, и сигналами, которые он периодически посылает другим процессорам. И тем не менее, будучи соединёнными в достаточно большую сеть с управляемым взаимодействием, такие локально простые процессоры вместе способны выполнять довольно сложные задачи.
Понятие возникло при изучении процессов, протекающих в мозге при мышлении, и при попытке смоделировать эти процессы. Полученные модели называются искусственными нейронными сетями (ИНС).
Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения — одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что, в случае успешного обучения, сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке.
Область применения
Распознавание образов и классификация
В качестве образов могут выступать различные, по своей природе, объекты: символы текста, изображения, образцы звуков и т. д. При обучении сети предлагаются различные образцы образов с указанием того, к какому классу они относятся. Образец, как правило, представляется как вектор из его признаков. При этом совокупность всех признаков должна однозначно определять класс, к которому относится образец. В случае, если признаков недостаточно, сеть может соотнести один и тот же образец с несколькими классами, что неверно.По окончании обучения сети можно предъявлять неизвестные ей ранее образы и получать от нее ответ о принадлежности к определенному классу. Топология такой сети характеризуется тем, что количество нейронов в выходном слое, как правило, равно количеству определяемых классов. При этом устанавливается соответствие между выходом нейронной сети и классом, который он представляет. Когда сети предъявляется некий образ, на одном из ее выходов должен появится признак того, что образ принадлежит этому классу. В то же время на других выходах должен быть признак того, что образ данному классу не принадлежит. Если на двух или более выходах есть признак принадлежности к классу, считается что сеть «не уверена» в своем ответе.
Принятие решений и управление
Эта задача близка к задаче классификации. Классификации подлежат ситуации, характеристики которых поступают на вход нейронной сети. На выходе сети при этом должен появится признак решения, которое она приняла. При этом в качестве входных сигналов используются различные критерии описания состояния управляемой системы.
Кластеризация
Под кластеризацией понимается разбиение множества входных сигналов на классы, при том, что ни количество, ни признаки классов заранее неизвестны. После обучения такая сеть способна определять, к какому классу относится входной сигнал. Сеть также может сигнализировать о том, что входной сигнал не относится ни к одному из выделенных классов — это является признаком новых, отсутствующих в обучающей выборке, данных. Таким образом, подобная сеть может выявлять новые, неизвестные ранее классы сигналов. Соответствие между классами, выделенными сетью, и классами, существующими в предметной области, устанавливается человеком.
Прогнозирование и аппроксимация
Способности нейронной сети к прогнозированию напрямую следуют из ее способности к обобщению и выделению скрытых зависимостей между входными и выходными данными. После обучения сеть способна предсказать будущее значение некой последовательности на основе нескольких предыдущих значений и/или каких-то существующих в настоящий момент факторов. Следует отметить, что прогнозирование возможно только тогда, когда предыдущие изменения действительно в какой-то степени предопределяют будущие. Например, прогнозирование котировок акций на основе котировок за прошлую неделю может оказаться успешным (а может и не оказаться), тогда как прогнозирование результатов завтрашней лотереи на основе данных за последние 50 лет почти наверняка не даст никаких результатов.
Сжатие данных и Ассоциативная память
Способность нейросетей к выявлению взаимосвязей между различными параметрами дает возможность выразить данные большой размерности более компактно, если данные тесно взаимосвязаны друг с другом. Обратный процесс — восстановление исходного набора данных из части информации — называется (авто)ассоциативной памятью. Ассоциативная память позволяет также восстанавливать исходный сигнал/образ из зашумленных/поврежденных входных данных. Решение задачи гетероассоциативной памяти позволяет реализовать память, адресуемую по содержимому.
