вторник, 3 августа 2010 г.

Мягкие вычисления – Часть 2

Генетическое программирование - применение эволюционного подхода к популяции программ. Идею генетического программирования - впервые предложил Джон Коза в 1992 году, опираясь на концепцию генетических алгоритмов. В своей книге Джон Коза привел многочисленные примеры проблем, которые можно решить с помощью генетического программирования. Он разработал систематический подход, при котором конкретным проблемам сопоставляется канонический набор архитектурных решений, используемый разработчиком для моделирования проблемы.
Эта идея заключается в том, что в отличие от генетических алгоритмов в генетическом программировании все операции производятся не над строками, а над деревьями. При этом используются такие же операторы, как и в генетических алгоритмах: селекция, скрещивание и мутация. В генетическом программировании хромосомами являются программы. Программы представлены как деревья с функциональными (промежуточными) и терминальными (конечными) элементами. Терминальными элементами являются константы, действия и функции без аргументов, функциональными - функции, использующие аргументы. Генетическое программирование — одна из самых удобных и универсальных методик решения задач, встающих перед разработчиками. Оно применяется для решения широкого круга проблем: символьной регрессии(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].
Сегодня
Для задач, к которым обычно применяют эволюционные вычисления, характерен очень малый объем аналитических данных, высокий уровень шумов, изменения со временем и большая сложность. Поэтому невозможно определить заранее, как будет работать генетический алгоритм в конкретной системе. Генетические программы по своей сложности напоминают решения, возникающие в природе посредством редупликации генов, мутаций и модификаций структур, и, возожно поэтому ГА могут в будущем революционизировать программирование.
Эволюционные вычисления находят все более широкое применение для моделирования самых разных динамических процессов, от имитации социального поведения и индукции в психологии до эволюции в экосистемах и действия иммунных систем. Эволюционные методы уже показали, что они способны находить эффективные структуры нейронных сетей.
Процесс эволюции биологических организмов шел миллиарды лет. И если учесть скорость, с которой размножаются простейшие организмы, и подсчитать количество комбинаций, опробованных природой, то становится ясно, что современных вычислительные мощности просто несопоставимы с требуемыми.
Поэтому многие исследователи заняты сейчас проблемами оптимизации процесса эволюции. Это и создание представлений, которые могли бы сохранить и повторно использовать возникающие в сети функциональные блоки, специальные механизмы скрещивания, порождающие относительно большее количество хороших, не вырожденных особей. Создание таких механизмов позволит моделировать эффективную эволюцию, которая смогла бы порождать нужные нам особи с приемлемой для нас скоростью.


clip_image002


Нейронные сети
Наиболее полное описание истории развития нейронных сетей можно найти в книге Саймона Хайкина «Нейронные сети. Полный курс» [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]. Со своими единомышленниками он создал машину, которая обучалась на примере стохастического процесса.

Комментариев нет:

Отправить комментарий