Эта идея заключается в том, что в отличие от генетических алгоритмов в генетическом программировании все операции производятся не над строками, а над деревьями. При этом используются такие же операторы, как и в генетических алгоритмах: селекция, скрещивание и мутация. В генетическом программировании хромосомами являются программы. Программы представлены как деревья с функциональными (промежуточными) и терминальными (конечными) элементами. Терминальными элементами являются константы, действия и функции без аргументов, функциональными - функции, использующие аргументы. Генетическое программирование — одна из самых удобных и универсальных методик решения задач, встающих перед разработчиками. Оно применяется для решения широкого круга проблем: символьной регрессии(symbolic regression), анализа данных (data mining), оптимизации и исследования поведения появляющегося потомства (emergent behavior) в биологических сообществах.
Эволюционный алгоритм решает проблему, генерируя массу случайных программ — вариантов решения проблемы. Каждый вариант запускается и оценивается согласно критериям приспособленности, заданным разработчиком. Эволюционный алгоритм выбирает из каждого поколения лучшие варианты решения и получает от них потомство, что аналогично естественному отбору в природе, являющемуся двигателем эволюции.
Генетическое программирование и генетические алгоритмы — два разных вида эволюционных алгоритмов. В генетических алгоритмах используются кодированные строки, представляющие конкретные решения проблемы. Эти строки обрабатываются программой моделирования, и лучшие из них смешиваются, образуя новое поколение. В генетическом программировании, о котором идет речь, применяется другой подход. Здесь в селекции участвуют не кодированные представления решений, а исполняемые компьютерные программы.
Эволюционное программирование было впервые предложено Л.Дж. Фогелем в 1960 году для моделирования эволюции как процесса обучения с целью создания искусственного интеллекта. Он использовал конечные автоматы, предсказывающие символы в цифровых последовательностях, которые, эволюционируя, становились более приспособленными к решению поставленной задачи.
Методы эволюционных стратегий и эволюционного программирования уделяют значительно больше внимание самому процессу эволюции. Первым отличием от генетических алгоритмов является отсутствие ограничений на представление. Второе заключается в возможности обобщения процесса эволюции и на сами параметры эволюции. Помимо объекта эволюции выделяются некоторые такие параметры стратегии эволюции как вероятность мутации, сила мутаций и др. Выбирая лучших индивидов мы учитываем и оптимальность этих параметров, таким образом, неявно выделяя параметры, наиболее подходящие для данной задачи.
Открытия в биологии
На возникновение этих методов повлияли некоторые открытия в биологии.Сначала Чарльз Дарвин опубликовал в 1859 году свою знаменитую работу "Происхождение видов", где были провозглашены основные принципы эволюционной теории:
· Наследственность (потомки сохраняют свойства родителей)
· Изменчивость (потомки почти всегда не идентичны)
· Естественный отбор (выживают наиболее приспособленные).
Тем самым было показано, какие принципы приводят к эволюционному развитию флоры и фауны под влиянием окружающей среды. Однако вопрос о том, как генетическая информация передается от родителей потомкам, долгое время оставался открытым.
В 1944 году Эйвери, Маклеод и Маккарти опубликовали результаты своих исследований, доказывавших, что за наследственные процессы ответственна "кислота дезоксирибозного типа". Однако о том, как работает ДНК, стало известно позднее.
В 1953 году в номере журнала "Nature" вышла статья Уотсона и Крика, которые впервые предложили модель двухцепочной спирали ДНК.
Таким образом, стали известны все необходимые компоненты для реализации эволюционной модели.
Ключевые работы
Первые публикация, которые можно отнести к генетическим алгоритмам, принадлежат Баричелли Н.А. Его работы "Symbiogenetic evolution processes realised by artificial methods" (1957) [Barichelli 1957], "Numerical testing of evolution theories" (1962) [Barichelli 1962] были направлены прежде всего на понимание природного феномена наследственности.В 1966 году Л.Дж. Фогель, А.Дж. Оуэнс, М.Дж. Уолш предложили и исследовали эволюцию простых автоматов, предсказывающих символы в цифровых последовательностях.
Родителем современной теории генетических алгоритмов считается Д.Х. Холланд. Однако сначала его интересовала, прежде всего, способность природных систем к адаптации, а его мечтой было создание такой системы, которая могла бы приспосабливаться к любым условиям окружающей среды. В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems» [Holland]. В ней он впервые ввёл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического генетического алгоритма.
Ученики Холланда – Кеннет Де Йонг и Дэвид Голдберг – внесли огромный вклад в развитие генетических алгоритмов. Наиболее известная работа Голдберга – «Genetic algorithms in search optimization and machine learning» (1989) [Goldberg].
Сегодня
Для задач, к которым обычно применяют эволюционные вычисления, характерен очень малый объем аналитических данных, высокий уровень шумов, изменения со временем и большая сложность. Поэтому невозможно определить заранее, как будет работать генетический алгоритм в конкретной системе. Генетические программы по своей сложности напоминают решения, возникающие в природе посредством редупликации генов, мутаций и модификаций структур, и, возожно поэтому ГА могут в будущем революционизировать программирование.
Эволюционные вычисления находят все более широкое применение для моделирования самых разных динамических процессов, от имитации социального поведения и индукции в психологии до эволюции в экосистемах и действия иммунных систем. Эволюционные методы уже показали, что они способны находить эффективные структуры нейронных сетей.
Процесс эволюции биологических организмов шел миллиарды лет. И если учесть скорость, с которой размножаются простейшие организмы, и подсчитать количество комбинаций, опробованных природой, то становится ясно, что современных вычислительные мощности просто несопоставимы с требуемыми.
Поэтому многие исследователи заняты сейчас проблемами оптимизации процесса эволюции. Это и создание представлений, которые могли бы сохранить и повторно использовать возникающие в сети функциональные блоки, специальные механизмы скрещивания, порождающие относительно большее количество хороших, не вырожденных особей. Создание таких механизмов позволит моделировать эффективную эволюцию, которая смогла бы порождать нужные нам особи с приемлемой для нас скоростью.
Нейронные сети
Наиболее полное описание истории развития нейронных сетей можно найти в книге Саймона Хайкина «Нейронные сети. Полный курс» [Haykin]. Из этой книги почерпнуты основные сведения для этого раздела.
В истории исследований в области нейронных сетей, как и в истории любой другой науки, были свои успехи и неудачи. Современная эра нейронных сетей началась с новаторской работы Мак-Каллока и Питца «A logical calculus of the ideas immanent in nervous activity» [MKP]. Мак-Каллок по образованию был психиатром и нейроанатомом и более 20 лет занимался вопросами представления событий в нервной системе. Питц был талантливым математиком; он присоединился к исследованиям Мак-Каллока в 1942 году. В статье Мак-Каллока и Питца описаны результаты, полученные в течение 5 лет группой специалистов по нейромоделированию из университета Чикаго, возглавляемой Рашевским.
В своей классической работе Мак-Каллок и Питц описали логику вычислений в нейронных сетях на основе результатов нейрофизиологии и математической логики. Формализованная модель нейрона соответствовала принципу "все или ничего". Ученые показали, что сеть, составленная из большого количества таких элементарных процессорных единиц, соединенных правильно сконфигурированными и синхронно работающими синаптическими связями, принципиально способна выполнять любые вычисления. Этот результат был реальным прорывом в области моделирования нервной системы. Именно он явился причиной зарождения таких направлений в науке как искусственный интеллект и нейронные сети. В свое время работа Мак-Каллока и Питца широко обсуждалась. Она остается актуальной и сегодня. Эта работа оказала влияние на идеи фон Неймана, воплощенные в конструкции компьютера EDVAC (Electronic Discrete Variable Automatic Computer), разработанного на основе устройства ENIAC (Electronic Numerical Integrator and Computer). ENIAC был первым компьютером общего назначения. Он создавался с 1943 по 1946 год в университете штата Пенсильвания. Фон Нейман постоянно излагал теорию формальных нейронных сетей Мак-Каллока-Питца во второй из своих четырех лекции, которые он читал в Университете штата Иллинойс в 1949 году.
В 1948 году была издана знаменитая книга Винера под названием «Кибернетика». В ней были описаны некоторые важные концепции управления, коммуникации и статистической обработки сигналов. Вторая редакция этой книги вышла в 1961 году. В нее был добавлен материал, касающийся обучения и самоорганизации систем. Во второй главе обоих изданий этой книги Винер подчеркнул физическую значимость статистических механизмов в контексте излагаемой проблемы. Однако только через 30 лет в работах Хопфилда был построен мост между статистическими механизмами и обучаемыми системами.
Следующей важной вехой в развитии нейронных сетей стал выход в свет в 1949 году книги Хебба «The Organization of Behavior» (Организация поведения). В ней приводится четкое определение физиологического правила обучения для синоптической модификации. В частности, Хебб предположил, что, по мере того как организм обучается различным функциональным задачам, связи в мозге постоянно изменяются и при этом формируются ансамбли нейронов. Знаменитый постулат обучения Хебба гласит, что эффективность переменного синапса между двумя нейронами повышается при многократной активации этих нейронов через данный синапс. Эта книга оказала влияние на развитие психологии, но, к сожалению, практически не возымела влияния на сообщество инженеров.
Книга Хебба стала источником вдохновения при создании вычислительных моделей обучаемых и адаптивных систем. Результаты при попытке использования компьютерного моделирования для проверки формализованной теории нейронов, основанной на постулате обучения Хебба, четко показали, что для полноты этой теории к ней следует добавить торможение. В том же году Аттли(Uttley) продемонстрировал что нейронные сети с изменяемыми синапсами можно обучить классификации простейших двоичных образов (растровых изображений). Он ввел понятие и активации нейрона, которое было формально проанализировано Кайанелло (Caianielo) в 1961 году. В своей более поздней работе (1979)[Uttley] Аттли высказал гипотезу о том, что эффективность переменного синапса в нервной системе зависит от статистических связей между переменными состояниями на другом конце синапса, связав, таким образом теорию нейронных сетей с теорией информации Шеннона.
В 1953 году вышла в свет книга, которая не потеряла своей актуальности и сегодня – Anderson, Pellionisz, Rosenfeld, «Neurocomputing 2: Directions for Research» (Нейровычисления 2: Направление исследований) [Anderson 1990]. Идея, представленная в этой работе, состояла в том, что адаптивное поведение является не врожденным, а приобретенным, и с помощью обучения можно улучшить поведение системы. Эта книга фокусировала внимание исследователей на динамических аспектах живого организма как системы и на понятии устойчивости.
В 1954 году Минский написал докторскую диссертацию в Принстонском университете, посвященную теории нейроаналоговых систем обучения с подкреплением и ее применению в задачах моделирования мозга[Minsky 1954]. В 1961 году была опубликована его работа, посвященная искусственному интеллекту [Minsky 1961]. Она называлась «Steps Toward Artificial Intelligence» (На пути к искусственному интеллекту). Эта работа содержала большой раздел, посвященный области, которая сейчас называется теорией нейронных сетей. В своей работе «Computation: Finite and Infinite Machines» (Вычисления: конечные и бесконечные машины) [Minsky 1967] Минский расширил результаты, полученные в 1943 году Мак-Каллоком и Питцом, и поместил их в контекст теории автоматов и теории вычислений.
В том же 1954 году Габор, один из пионеров в теории коммуникации и первооткрыватель голографии, предложил идею нелинейного адаптивного фильтра [Gabor]. Со своими единомышленниками он создал машину, которая обучалась на примере стохастического процесса.
Комментариев нет:
Отправить комментарий