Автоматика и телемеханика, Л- 5, 2007
РАС Б 02.60.Pri
© 2007 г. Л.Н. КОРОЛЕВ, чл.-корр. РАН (Московский государственный университет им. Ломоносова)
ОБ ЭВОЛЮЦИОННЫХ АЛГОРИТМАХ, НЕЙРОСЕТЕВЫХ ВЫЧИСЛЕНИЯХ, ГЕНЕТИЧЕСКОМ ПРОГРАММИРОВАНИИ МАТЕМАТИЧЕСКИЕ ПРОБЛЕМЫ1
Рассматриваются в общих чертах некоторые проблемы, связанные с применением эволюционных и генетических алгоритмов, генетического программирования. пейросетевых вычислений при решении прикладных задач, сводящихся к анализу функций, заданных па перестановках. Отмечается естественный параллелизм этих алгоритмов и возможность их реализации па современных вычислительных машинах.
1. Введение
Начиная с 80-х годов прошлого столетия получило развитие направление научных и прикладных исследований, получившее название в смысловом русском переводе "обучение вычислительных машин". В англоязычной литературе это направление относят к Computer Science или к IT-технологиям и называют "Machino Learning" (ML). Цель статьи попытаться разобраться с теми допущениями, ограничениями и математическими проблемами, которые возникают в этой области исследований. основанной главным образом на эвристиках и на гипотезах, в той или иной степени адекватных предметной области, в рамках которой решаются задачи методами ML. В это направление исследований и применений входят эволюционные н генетические алгоритмы, генетическое программирование, нейросотевыо вычисления (нейрокомиыотинг). клеточные автоматы. Появление обобщающего термина Machino Loaning связывают с именем К. Самюэль, опубликовавшего в 1963 г. статью [1] о некоторых проблемах обучения машины на примере игры в шахматы.
2. О нейронных сетях
С формальной точки зрения нейронную сеть можно представить как частный случай параметризованного преобразователя, на вход которого поступает вектор значений, а на выходе которого появляется другой вектор, возможно из другого векторного пространства. Такого типа преобразование в обычной математической
1 Работа поддержана грантами РФФИ № 06-01-00586 и 06-01-00046, грантом № НШ-4774."2006.1 программы "Ведущие научные школы", грантом Президента РФ .N-" МК-1777.'2005.1, грантом 1NTAS .N-" 05-109-5267, грантом Лавреитьевского конкурса молодежных проектов СО РАН.
символике можно записать как систему из т функций вида
(хЬ . . . ,Хп ,Шц, . . . (Х1, . . .,Хп,Ш12, . . .,ик2),
.............................;
Ет (х1, ..., xn, и1т, ..., икт ):
где - некоторые параметры.
Визуализировать систему функций (1) можно в виде схемы рис. 1. которая очень похожа на однослойную нейронную сеть.
В отличие от преобразователя общей формы в нейронной сети все функции Ег имеют одинаковый вид. например [2] такой простейший:
п
г=1 п
^2(хг,шг) < V,
г=1
где V - некоторая константа, называемая порогом.
Существенно отметить, что значения всех функций в системе (1) могут вычисляться одновременно. Это означает, что преобразованиям этого типа присущ внутренний. естественный параллелизм.
Сделаем следующее важное замечание. Рисунок 1 можно трактовать как представление однослойной параллельно работающей вычислительной сети. На практике чаще всего используются многослойные сети по той причине, что при использовании только одного слоя при вычислении результирующих значений функций Ег теряется информация о параметрах сети, связанных с другими функциями.
Впервые работы по формальному анализу математических моделей нейроподоб-ных сетей относятся к 1943 г.. имеется в виду работа В. Маккуллока и В. Питтса [3] "Логическое исчисление идей, относящихся к нервной активности". На русский язык эта работа переведена в 1956 г.
Фундаментальный анализ математических моделей нейронных сетей был проведен рядом известных специалистов в области математической логики, включая С. Клини, М. Минского, С. Пейперта и ряда др.
Важным шагом в развитии идей нейрокомпыотинга явилось появление в 1962 г. модели персептрона Розенблатта [4], которая с успехом была использована для решения некоторых задач распознавания образов.
(1)
V —
У2 =
V —
т
1, если
Е |
0, если
Рг
Р т
У
У
2
У
х
т
п
Рис. 1.
Модель персептрона Розенблатта была подвергнута всестороннему математическому анализу в работе М. Минского и С. Пейиерта [5]. которые доказали невозможность использования персептрона для решения некоторых простых задач распознавания геометрических объектов, в частности невозможность распознавать геометрически подобные образы.
Затем были предложены многочисленные усовершенствованные модели нейронных сетей, которые снимали ряд ограничений персептрона и расширяли возможный круг решаемых задач. Однако мощностей существовавшей на тот период вычислительной техники было явно недостаточно для решения многих реальных задач распознавания и классификации.
Анализируя первый этап развития исследований нейронных сетей, можно вполне определенно сказать, что эта область относилась к математике, к исследованиям некоторого класса математических моделей, отражающих, в том числе и в терминологии. физиологические реалии.
Сложность и необычность этих исследований заключалась в том. что нейронные сети по своей сути являются моделями параллельного ироцессирования, в которых все узлы (нейроны) работают одновременно и одновременно обмениваются информацией между собой.
Замечательным свойством математических моделей нейронных сетей, используемых для вычислений, является принцип их "обучения" и "самообучения", их настройки на решение определенного класса задач.
Процесс "обучения" и "самообучения" состоит в подборе параметров так. чтобы "выходное" векторное пространство обладало предопределенными свойствами.
В ряде задач множество выходных значений Y должно обозначать номер класса, к которому отнесен входной вектор, в других задачах это множество представляет собой сжатую информацию, в третьих аппроксимированное значение некоторой функции и т.п.
Как уже отмечалось, идеи генетического программирования (Genetic Programming) возникли в конце 50-х годов прошлого столетия [6]. Большую роль в развитии этих идей сыграл профессор Дж. Коза, опубликовавший в 1992 г. первую монографию, посвященную многим аспектам этого нового направления в автоматизации программирования [7, 8].
Прежде чем говорить о генетическом программировании следует ввести в круг идей, связанных с эволюционными алгоритмами вообще и с генетическими алгоритмами в частности.
3. Эволюционные алгоритмы
Эволюционные алгоритмы можно отнести к известному методу "проб и ошибок", связанному с решением переборных задач, возникающих при поисках правильных решений нлн экстремальных значений, в случае отсутствия знания или теории о поведении изучаемого объекта, процесса или функции.
Способ решения таких плохо формализованных, плохо определенных задач это направленный перебор.
В непрерывной математике широко используется метод градиентного спуска для поиска экстремумов функций, в дискретной математике используется метод ветвей и границ, позволяющий отсечь большое число вариантов, которые заведомо не приведут к нахождению правильного решения.
В том и в другом случаях отыскания экстремума направленным перебором необходимы сведения о характеристиках функции или функционала, экстремум которых
надлежит отыскать. При решении практических задач эти сведения можно получать в ходе решения.
Пусть задано конечное множество из N уникальных элементов. Уникальность элементов означает, что каждый из них имеет свое присущее только ему имя и обладает некоторым набором приданных ему характеристик. Каждому элементу этого множества может быть приписан свой порядковый номер. Если в множестве N элементов, то можно присвоить им порядковые номера N! различными способами. Пусть с каждой нумерацией связано некоторое значение и существует алгоритм вычисления этого значения. Функцию, зависящую от способа нумерации элементов множества, будем называть функцией, заданной на перестановках или просто функцией перестановок Г (р).
В качестве имен элементов можно выбрать номера от 1 до N и назвать эту последовательность начальной перестановкой р1 = (1, 2, 3,..., N). Как известно, любую другую перестановку можно получить последовательной переменой мест двух соседних элементов перестановок, соответственно все перестановки можно перенумеровать от 1 до М = N!.
Многие задачи сводятся к поиску экстремумов функций перестановок. Классическим примером функции, заданной на перестановках, является задача коммивояжера. Если перенумеровать все города, которые должен обойти коммивояжер, и задать расстояния между любой парой городов, то перестановку можно считать порядком обхода городов, а сумму пройденного расстояния можно считать значением функции на выбранной перестановке. При небольшом числе городов эту задачу можно решить прямым перебором. Но если N большое, например 300, то по формуле
ров не справится ни один компьютер в мире, так как число элементарных частиц во вселенной не превышает 10200!
Другим примером задачи, сводящейся к поиску экстремума функции на перестановках, является хорошо известная задача о рюкзаке.
Ее формулировка в простейшем случае сводится к следующему. Дано N предметов, каждый из которых обладает своим весом и стоимостью. Рюкзак может быть нагружен только до определенного веса. Следует из имеющихся N предметов положить в рюкзак наиболее ценные, не превысив допустимый вес. Здесь с каждым предметом связано уже два значения вес и стоимость (ценность).
И ту, и другую задачу можно попытаться решать, выбирая перестановку одну за другой наугад, в надежде случайно наткнуться на удачную перестановку, доставляющую искомый экстремум функции или приближающую к экстремуму.
Здравый смысл подсказывает, что подобные задачи нужно решать направленным перебором, отбрасывая сразу недопустимые варианты последовательности обхода городов или последовательности загрузки рюкзака. Необходимо найти законы, определяющие правила построения "хороших" перестановок.
Для этого можно поступить так. Выбрать наугад несколько перестановок, подсчитать для всех соответствующие значения функции, внимательно проанализировать их состав и выработа
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.