|
сли же пространство поиска небольшое, то решение может быть найдено методом полного перебора, и можно быть уверенным, что наилучшее возможное решение найдено, тогда как генетический алгоритм мог с большей вероятностью сойтись к локальному оптимуму, а не к глобально лучшему решению. Если пространство гладкое и унимодальное любой градиентный алгоритм, такой как, метод скорейшего спуска будет более эффективен, чем генетический алгоритм. Если о пространстве поиска есть некоторая дополнительная информация (как, например, пространство для хорошо известной задачи о коммивояжере), методы поиска, использующие эвристики, определяемые пространством, часто превосходят любой универсальный метод, каким является генетический алгоритм. При достаточно сложном рельефе функции приспособленности методы поиска с единственным решением в каждый момент времени, такой как простой метод спуска, могли "затыкаться" в локальном решении, однако считается, что генетический алгоритм, так как они работают с целой "популяцией" решений, имеют меньше шансов сойтись к локальному оптимуму и робастно функционируют на многоэкстремальном ландшафте. Конечно, такие предположения не предсказывают строго, когда генетический алгоритм будет эффективной процедурой поиска, конкурирующей с другими процедурами. Эффективность генетического алгоритма сильно зависит от таких деталей, как метод кодировки решений, операторы, настройки параметров, частный критерий успеха. Теоретическая работа, отраженная в литературе, посвященной генетическим алгоритмам, не дает оснований говорить о выработки каких-либо строгих механизмов для четких предсказаний. Символьная модель простого генетического алгоритмаЦель в оптимизации с помощью генетического алгоритма состоит в том, чтобы найти лучшее возможное решение или решения задачи по одному или нескольким критериям. Чтобы реализовать генетический алгоритм нужно сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска, экземпляр этой структуры данных представляет точку в пространстве поиска всех возможных решений. Структура данных генетического алгоритма состоит из одной или большее количество хромосом (обычно из одной). Как правило, хромосома - это битовая строка, так что термин строка часто заменяет понятие "хромосома". В принципе, генетические алгоритмы не ограничены бинарным представлением. Известны другие реализации, построенные исключительно на векторах вещественных чисел . Несмотря на то, что для многих реальных задач, видимо, больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены. Пока и мы ограничимся только структурам, которые являются одиночными строками по l бит. Каждая хромосома (строка) представляет собой конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример - задача максимизации следующей функции двух переменных: (1) f (x1, x2) = exp(x1x2), где 0 < x1< 1 и 0 < x2 < 1. (1) Обычно, методика кодирования реальных переменных x1 и x2 состоит в их преобразовании в двоичные целочисленные строки достаточной длины - достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10-разрядное кодирование достаточно и для x1, и x2. Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное целое число - на 210-1. Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных - 20-битная строка, представляющая конкатенацию кодировок x1 и x2. Переменная x1 размещается в крайних левых 10-разрядах, тогда как x2 размещается в правой части генотипа особи (20-битовой строке). Генотип - точка в 20-мерном хеммининговом пространстве, исследуемом генетическим алгоритмом. Фенотип - точка в двумерном пространстве параметров. Чтобы оптимизировать структуру, используя генетический алгоритм, нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. В функциональной максимизации, целевая функция часто сама выступает в качестве функции приспособленности (например наш двумерный пример); для задач минимизации, целевую функцию следует инвертировать и сместить затем в область положительных значений. Работа простого генетического алгоритмаПростой генетический алгоритм случайным образом генерирует начальную популяцию структур. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении генетического алгоритма реализуется отбор пропорционально приспособленности, одноточечный кроссовер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции.Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор - рулетка - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью. После отбора, n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятность Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва - участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков. Например, предположим, один родитель состоит из 10 нолей, а другой - из 10 единиц. Пусть из 9 возможных точек разрыва выбрана точка 3. Родители и их потомки показаны ниже в табл.1: КроссоверРодитель 0000000000 000~0000000 - 111~0000000 1110000000 Потомок 1 1 >Родитель 1111111111 111~1111111 - 000~1111111 0001111111 Потомок 2 - 2 - > Схема 2После того, как закончится стадия кроссовера, выполняются операторы мутации. В каждой строке, которая подвергается мутации, каждый бит с вероятностью Pm изменяется на противоположный. Популяция, полученная после мутации записывает поверх старой и этим цикл одного поколения завершается. Последующие поколения обрабатываются таким же образом: отбор, кроссовер и мутация. В настоящее время исследователи генетических алгоритмов предлагают много других операторов отбора, кроссовера и мутации. Вот лишь наиболее распространенные из них. Прежде всего, турнирный. Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2. Элитные методы отбора гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссовера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора. Двухточечный кроссовер и равномерный кроссовер - вполне достойные альтернативы одноточечному оператору. В двухточечном кроссовере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. В равномерном кроссовере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. И наоборот.Шима (schema)Хотя внешне кажется, что генетический алгоритм обрабатывает строки, на самом деле при этом неявно происходит обработка шим, которые представляют шаблоны подобия между строками. Генетический алгоритм практически не может заниматься полным перебором всех точек в пространстве поиска. Однако он может производить выборку значительного числа гиперплоскостей в областях поиска с высокой приспособленностью. Каждая такая гиперплоскость соответствует множеству похожих строк с высокой приспособленностью. Шима - это строка длины l (что и длина любой строки популяции), состоящая из знаков алфавита {0; 1; *}, где {*} - неопределенный символ. Каждая шима определяет множество всех бинарных строк длины l, имеющих в соответствующих позициях либо 0, либо 1, в зависимости от того, какой бит находится в соответствующей позиции самой шимы.. Например, шима, 10**1, определяет собой множество из четырех пятибитовых строк {10001; 10011; 10101; 10111}. У шим выделяют два свойства - порядок и определенная длина. Порядок шимы - это число определенных битов ("0" или "1") в шиме. Определенная длина - расстояние между крайними определенными битами в шиме. Например, вышеупомянутая шима имеет порядок o(10**1) = 3, а определенная длина d(10**1) = 4. Каждая строка в популяции является примером шим. Строящие блоки Строящие блоки - это шимы обладающие: - высокой приспособленностью, - низким порядком, - короткой определенной длиной. Приспособленность шимы определяется как среднее приспособленностей примеров, которые ее содержат. После процедуры отбора остаются только строки с более высокой приспособленностью. Следовательно строки, которые являются примерами шим с высокой приспособленностью, выбираются чаще. Кроссовер реже разрушает шимы с более короткой определенной длиной, а мутация реже разрушает шимы с низким порядком. Поэтому, такие шимы имеют больше шансов переходить из поколения в поколение. Голланд показал, что, в то время как генетический алгоритм явным образом обрабатывает n строк на каждом поколении, в тоже время неявно обрабатываются порядка таких коротких шим низкого порядка и с высокой приспособленностью (полезных шим, "useful schemata"). Он называл это явление неявным параллелизмом. Для решения реальных задач, присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей. Теорема шимПростой экспоненциально увеличивает число примеров полезных шим или строящих блоков. Доказательством этого служит следующая теорема, известная как "теорема шим". Пусть m(H,t) - число примеров шимы H в t-ом поколении. Вычислим ожидаемое число примеров H в следующем поколении или m(H,t+1) в терминах m(H,t). Простой генетический алгоритм каждой строке ставит в соответствие вероятность ее "выживания" при отборе пропорционально ее приспособленности. Ожидается, что шима H может быть выбрана m(H,t)Ч (f(H)/fср.) раз, где fср. - средняя приспособленность популяции, а f(H) - средняя приспособленность тех строк в популяции, которые являются примерами H. Вероятность того, что одноточечный кроссовер разрушит шиму равна вероятности того, что точка разрыва попадет между определенными битами. Вероятность же того, что H "переживает" кроссовер не меньше 1-Pc_ (d(H)/l-1). Эта вероятность - неравенство, поскольку шима сможет выжить если в кроссовере участвовал также пример похожей шимы. Вероятность того, что H переживет мутацию - (1-Pm) o(H), это выражение можно аппроксимировать как (1-o(H)) для малого Pm и o(H). Произведение ожидаемого число отборов и вероятностей выживания известно как теорема шим (3): m (H, t+1) (3) Теорема шим показывает, что строящие блоки растут по экспоненте, в то время шимы с приспособленностью ниже средней распадаются с той же скоростью. В своих исследованиях теоремы шим Goldberg выдвигает гипотезу строящих блоков, которая состоит в том, что "строящие блоки объединяются, чтобы сформировать лучшие строки". То есть рекомбинация и экспоненциальный рост строящих блоков ведет к формированию лучших строящих блоков. В то время как теорема шим предсказывает рост примеров хороших шим, сама теорема весьма упрощенно описывает поведение генетических алгоритмов. Прежде всего, f(H) и fср. не остаются постоянными от поколения к поколению. Приспособленности членов популяции знаменательно изменяются уже после нескольких первых поколений. Во-вторых, теорема шим объясняет потери шим, но не появление новых. Новые шимы часто создаются кроссовером и мутацией. Кроме того, по мере эволюции, члены популяции становятся все более и более похожими друг на друга так, что разрушенные шимы будут сразу же восстановлены. Наконец, доказательство теоремы шим построено на элементах теории вероятности и следовательно не учитывает разброс значений, в многих интересных задачах, разброс значений приспособленности шимы может быть достаточно велик, делая процесс формирования шим очень сложным. Существенная разница приспособленности шимы может привести к сходимости к неоптимальному решению. Несмотря на простоту, теорема шим описывает несколько важных аспектов поведения генетических алгоритмов. Мутации с большей вероятностью разрушают шимы высокого порядка, в то время как кроссовера с большей вероятность разрушают шимы с большей определенной длиной. Когда происходит отбор, популяция сходится пропорционально отношению приспособленности лучшей особи, к средней приспособленности в популяции; это отношение - мера давления отбора. Увеличение или Pc, или Pм., или уменьшении давления отбора, ведет к увеличенному осуществлению выборки или исследованию пространства поиска, но не позволяет использовать все хорошие шимы, которыми располагает генетический алгоритм. Уменьшение или Pc, или Pм., или увеличение давления выбора, ведет к улучшению использования найденных шим, но тормозит исследование пространства в поисках новых хороших шим. Генетический алгоритм должен поддержать тонкое равновесие между тем и другим, что обычно известно как проблема "баланса исследования и использования". Некоторые исследователи критиковали обычно быструю сходимость генетического алгоритма, заявляя, что испытание огромных количеств перекрывающихся шим требует большей выборки и более медленной, более управляемой сходимости. В то время как увеличить выборку шим можно увеличив размер популяции, методология управления сходимость простого генетического алгоритма до сих пор не выработана. Перспективные направления развития нейрокомпьютерных технологийДетальный анализ зарубежных разработок нейрокомпьютеров позволил выделить основные перспективные направления современного развития нейрокомпьютерных технологий: нейропакеты, нейросетевые экспертные системы, СУБД с включением нейросетевых алгоритмов, обработка изображений, управление динамическими системами и обработка сигналов, управление финансовой деятельностью, оптические нейрокомпьютеры, виртуальная реальность. Сегодня разработками в этой области занимается более 300 зарубежных компаний, причем число их постоянно увеличивается. Среди них такие гиганты как Intel, DEC, IBM и Motorolla. Сегодня наблюдается тенденция перехода от программной эмуляции к программно-аппаратной реализации нейросетевых алгоритмов с резким увеличением числа разработок СБИС нейрочипов с нейросетевой архитектурой. Резко возросло количество военных разработок, в основном направленных на создание сверхбыстрых, "умных" супервычислителей. Если говорить о главном перспективном направлении - интеллектуализации вычислительных систем, придания им свойств человеческого мышления и восприятия, то здесь нейрокомпьютеры - практически единственный путь развития вычислительной техники. Многие неудачи на пути совершенствования искусственного интеллекта на протяжении последних 30 лет связаны с тем, что для решения важных и сложных по постановке задач выбирались вычислительные средства, не адекватные по возможностям решаемой задаче, в основном из числа компьютеров, имеющихся под рукой. При этом как правило не решалась задача, а показывалась принципиальная возможность ее решения. Сегодня активное развитие систем MPP создало объективные условия для построения вычислительных систем, адекватных по возможностям и архитектуре практически любым задачам искусственного интеллекта. В Японии с 1993 года принята программа "Real world computing program",. Ее основная цель - создание адаптивной, эволюционирующей ЭВМ. Проект рассчитан на 10 лет. Основой разработки является нейротехнология, используемая для распознавания образов, обработки семантической информации, управления информационными потоками и роботами, которые способны адаптироваться к окружающей обстановке. Только в 1996 году было проведено около сотни международных конференций по нейрокомпьютерам и смежным проблемам. Разработки нейрокомпьютеров ведутся во многих странах мира и даже в Австралии создан свой образец коммерческого супернейрокомпьютера. В 1996 году московская компания "Тора-Центр" начинает беспрецедентную акцию - продажу в России лицензионного пакета моделирования нейронных сетей BrainMaker производства California Scientific Software. Пакет предназначался для моделирования многослойных нейронных сетей с полными последовательными связями, обучаемыми по методу обратного распространения ошибки (error backpropagation), оказался прост в использовании и предоставлял много возможностей по изменению топологии многослойной сети и алгоритма обучения, хотя и был несколько сложен для первого восприятия. В пакете не было предусмотрено защиты от копирования, он размещался на стандартной 3,5-дюймовой дискете. При этом разработчиком было особо оговорено, что BrainMaker ориентирован в первую очередь на решение финансовых задач, и основными его потребителями должны стать банки и крупные финансовые компании - сектор рынка, где в то время были сосредоточены основные отечественные финансовые ресурсы. Расчет оказался верным - благодаря мощной рекламной поддержке нейропакет BrainMaker приобрел в России небывалую популярность; спустя некоторое время он даже появился на пиратских компакт-дисках.В тот период появились и другие нейропакеты, например, AI Trilogy от Ward Systems Group и в продажу поступил нейрокомпьютерный ускоритель CNAPS компании Adaptive Solutions, представляющий собой аппаратный ускоритель, построенный на базе одного или нескольких нейрочипов того же производителя. По оценкам, для некоторых задач он может дать выигрыш в производительности до 1000 раз по сравнению с самым передовым на тот момент компьютером с процессором Pentium. Выпускался CNAPS до 1997-1998 годов, после чего был снят с производства, скорее всего, по причине нерентабельности.Слово "нейро" становится в России модным - почти каждый уважающий себя банк считает долгом купить лицензионный нейропакет и поставить красивую белую коробку на полку. К сожалению, политика компании "Тора" не предусматривала дальнейшего информационного и методического сопровождения своего детища, а консультации по разработке нейросетевых алгоритмов с использованием этого нейропакета пропагандировались, в основном, на бумаге. Поэтому большое количество купленных нейропакетов так и осталось пылиться на полках. Несмотря на это и, невзирая на то, что отдельные пользователи восприняли нейропакет как "средство от всех бед", который сам по себе может решить любую задачу, а бездумное использование нейропакета привело к определенной дискретизации нейрокомпьютинга, проведенная акция стала громадным шагом на пути нейрокомпьютеризации страны, ибо массовый разработчик узнал, что существует новый класс алгоритмов под названием "нейронные сети" и что с их помощью можно эффективно решать различные задачи.Судьба же аппаратного нейрокомпьютерного ускорителя CNAPS более печальна. Мощный нейроускоритель был нужен для решения только суперзадач, которых не так уж и много, а для решения подавляющего большинства задач достаточно ПК и пакета моделирования нейронных сетей, того же BrainMaker, например. Поэтому нейроускоритель оказался просто невостребован рынком, к тому же его цена в несколько тыс. долл. и необходимость освоения специфичного программного обеспечения отпугивала потенциальных потребителей. Фактически вопрос был поставлен ребром - "а нужен ли нейроускоритель для решения обычных задач", и на него был получен отрицательный ответ. Количество проданных экземпляров нейроускорителя можно было пересчитать по пальцам. Правда, компания "ОГО", занимавшаяся зерновыми поставками, активно доказывала, как она эффективно использует нейроускоритель для решения своих задач, но, по всей видимости, это была в основном рекламная акция. Постепенно интерес к CNAPS затих. Когда позднее в Siemens попытались повторить этот путь и внедрить на российский рынок свой нейрокомпьютер Synaps-1 стоимостью 400 тыс. долл., то натолкнулась на ту же самую проблему - нейрокомпьютер оказался невостребованным.Это, конечно, не означает, что аппаратные нейроускорители и нейрокомпьютеры не нужны - просто они используются узким кругом коллективов, занимающихся решением именно суперзадач, а массовому пользователю они действительно ни к чему. Для справки, в России ряд научных коллективов имеют в своем распоряжении и нейрокомпьютеры и супермашины для моделирования нейронных сетей, но их мало.ЗаключениеЧто же касается прогнозов, которые, как известно, дело неблагодарное, то попробую их сделать. На мой взгляд, есть два объективных критерия, по которым можно оценивать будущее тех или иных разработок: использование в военной сфере, а также применение в ширпотребовской бытовой технике. Так было и с обычными компьютерами, появившись на свет в середине века, которые поначалу использовались для военных целей, а затем стали массовым явлением, найдя свое место среди предметов широкого потребления. То же самое происходит и с нейрокомпьютерами - вначале использование в военных целях, а затем в быту. Уже сейчас в открытой печати иногда попадаются заметки, что та или иная фирма создала и внедрила нейросетевой блок системы управления истребителем, использовала нейрочипы в системах наведения ракет или применила нейросетевые методы обработки для распознавания целей в радиолокаторах и так далее. Скорее всего, это означает, что область применения нейросетевых технологии гораздо шире, поскольку большинство разработок все же засекречены. С другой стороны, уже сейчас наблюдается внедрение нейрокомпьютеров в обычные бытовые приборы - примерами могут служить кондиционеры LG со встроенным нейросетевым блоком интеллектуального управления, стиральные машины Samsung с чипом нечеткой логики внутри (это хоть и не "нейро", но близко), бытовые видеокамеры Panasonic с нейронечеткой системой наводки на резкость (список при желании можно продолжить) и, наконец, исследования Microsoft по созданию нейросетевой системы распознавания речи для будущих операционных систем.Все это свидетельствует о том, что нейрокомпьютеры занимают все более прочные позиции в нашей повседневной жизни. Конечно, было бы глупо утверждать, что в ближайшем будущем нейрокомпьютеры заменят собой обычные компьютеры. Этого не произойдет ни сейчас, ни потом, поскольку "нейроподход" эффективен не для всех задач. Но там, где нейротехнологии имеют неоспоримые преимущества перед другими алгоритмическими методами неизбежно постепенно произойдет замена существующих аппаратных средств и программ на нейрокомпьютеры и нейросетевое программное обеспечение.Литература1. Галушкин А. Современные направления развития нейрокомпьютерных технологий в России // Открытые системы. - 1997 г., №4.2. Каллан Р. Основные концепции нейронных сетей. М.: Вильямс 2002 г.3. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 400 с: ил.4. Логовский А. Новейшая история нейрокомпьютинга в России //Открытые системы. - 2001 г., №3.5. Оссовский С. Нейронные сети для обработки информации / Пер. с польского И.Д. Рудинского. - М.: Финансы и статистика, 2002. - 344 с: ил.6. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского. - М.: Горячая линия -Телеком, 2006. - 452 с: ил.7. Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход. 2-е издание М., Вильямс 2006 г.8. Тархов Д.А. Нейронные сети. Модели и алгоритмы. Изд: Радиотехника. 2005 г.9. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. М.: Мир, 1992 г.10. Яхъяева Г. Э. Нечеткие множества и нейронные сети: Учебное пособие /Г. Э. Яхъяева. - М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006.
Страницы: 1, 2, 3
|
