Искусственный интелект. Генетические алгоритмы

     Конечно, такие предположения не предсказывают  строго, когда ГА будет эффективной процедурой поиска, конкурирующей с другими процедурами. Эффективность ГА сильно зависит от таких деталей, как метод кодировки решений, операторы, настройки параметров, частный критерий успеха. Теоретическая работа, отраженная в литературе, посвященной Гамам, не дает оснований говорить о выработки каких-либо строгих механизмов для четких предсказаний.

     Цель  в оптимизации с помощью ГА состоит в том, чтобы найти лучшее возможное решение или решения задачи по одному или нескольким критериям. Чтобы реализовать генетический алгоритм нужно сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска, экземпляр этой структуры данных представляет точку в пространстве поиска всех возможных решений.

     Структура данных генетического алгоритма  состоит из одной или большее  количество хромосом (обычно из одной). Как правило, хромосома - это битовая  строка, так что термин строка часто  заменяет понятие "хромосома". В принципе, ГА не ограничены бинарным представление. Известны другие реализации, построенные исключительно на векторах вещественных чисел (L. Davis, 1991b; Eshelman и Schaffer, 1993; Goldberg, 1991a, 1991b). Несмотря на то, что для многих реальных задач, видимо, больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены. Пока и мы ограничимся только структурам, которые являются одиночными строками по l бит.

     Каждая  хромосома (строка) представляет собой  конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных  позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными  строками, ген - бит, локус - его позиция  в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует  структуре в ГА. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример - задача максимизации следующей функции двух переменных:

     f (x₁, x₂) = exp(x₁x₂), где 0 < x₁< 1 и 0 < x₂ < 1.

     Обычно, методика кодирования реальных переменных x₁ и x₂ состоит в их преобразовании в двоичные целочисленные строки достаточной длины - достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10-разрядное кодирование достаточно и для x₁, и x₂. Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное целое число - на 2¹⁰-1. Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных - 20-битная строка, представляющая конкатенацию кодировок x₁ и x₂. Переменная x₁ размещается в крайних левых 10-разрядах, тогда как x₂ размещается в правой части генотипа особи (20-битовой строке). Генотип - точка в 20-мерном хеммининговом пространстве, исследуемом ГА. Фенотип - точка в двумерном пространстве параметров.

     Чтобы оптимизировать структуру, используя  ГА, нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. В функциональной максимизации, целевая функция часто сама выступает в качестве функции приспособленности (например наш двумерный пример); для задач минимизации, целевую функцию следует инвертировать и сместить затем в область положительных значений.

     Простой ГА случайным образом генерирует начальную популяцию структур. Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении ГА реализуется отбор пропорционально приспособленности, одноточечный кроссовер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции:

     Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор - рулетка (roulette-wheel selection, Goldberg, 1989c) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

     После отбора, n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятность Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

     Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва - участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

     Например, предположим, один родитель состоит  из 10 нолей, а другой - из 10 единиц. Пусть  из 9 возможных точек разрыва выбрана  точка 3. Родители и их потомки показаны ниже.

     После того, как закончится стадия кроссовера, выполняются операторы мутации. В каждой строке, которая подвергается мутации, каждый бит с вероятностью Pm изменяется на противоположный. Популяция, полученная после мутации записывает поверх старой и этим цикл одного поколения завершается. Последующие поколения обрабатываются таким же образом: отбор, кроссовер и мутация.

     В настоящее время исследователи  ГА предлагают много других операторов отбора, кроссовера и мутации. Вот лишь наиболее распространенные из них. Прежде всего, турнирный отбор (Brindle, 1981; Goldberg и Deb, 1991). Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

     Элитные методы отбора (De Jong, 1975) гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссовера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора.

     Двухточечный  кроссовер (Cavicchio, 1970; Goldberg, 1989c) и равномерный кроссовер (Syswerda, 1989) - вполне достойные альтернативы одноточечному оператору. В двухточечной кроссовере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. В равномерном кроссовере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. И наоборот.

    История развития метода генетических алгоритмов.

     Природа поражает своей сложность и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, которые стали более очевидны, когда мы стали глубже исследовать себя самих и мир вокруг нас. Наука - это одна из сменяющих друг друга систем веры, которыми мы пытается объяснять то, что наблюдаем, этим самым изменяя себя, чтобы приспособиться к новой информации, получаемой из внешнего мира. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.

     Теория  эволюции повлияла на изменение мировоззрения  людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение  Видов", в 1859 году, стала началом  этого изменения. Многие области  научного знания в настоящее время  наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и  развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась  неправильной. Это было на пятьдесят  лет до того, как теория наследственности начала распространяться по миру, и  за тридцать лет до того, как "эволюционный синтез" укрепил связь между  теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью  или, как он его называл, "спуск  с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все  еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых  в Природе.

     Поэтому неудивительно, что ученые, занимающиеся компьютерными исследованиями, обратились к теории эволюции в поисках вдохновения. Возможность того, что вычислительная система, наделенная простыми механизмами  изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в природных системах, была очень привлекательна. Эта надежда стала причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.

     История эволюционных вычислений началась с  разработки ряда различных независимых  моделей. Основными из них были генетические алгоритмы и классификационные  системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

     Главная трудность с возможностью построения вычислительных систем, основанных на принципах естественного отбора и применением этих систем в прикладных задачах, состоит в том, что природные  системы достаточно хаотичны, а все  наши действия, фактически, носят четкую направленность. Мы используем компьютер  как инструмент для решения определенных задач, которые мы сами и формулируем, и мы акцентируем внимание на максимально  быстром выполнении при минимальных  затратах. Природные системы не имеют  никаких таких целей или ограничений, во всяком случае нам они не очевидны. Выживание в природе не направлено к некоторой фиксированной цели, вместо этого эволюция совершает шаг вперед в любом доступномее направлении.

     Возможно  это большое обобщение, но я полагаю, что усилия, направленные на моделирование  эволюции по аналогии с природными системами, к настоящему времени  можно разбить на две большие  категории: 1) системы, которые смоделированы  на биологических принципах. Они  успешно использовались для задач  типа функциональной оптимизации и  могут легко быть описаны на небиологическом  языке, 2) системы, которые являются биологически более реалистичными, но которые не оказались особенно полезными в прикладном смысле. Они больше похожи на биологические системы и менее направлены (или ненаправлены вовсе). Они обладают сложным и интересным поведением, и, видимо, вскоре получат практическое применение.

     Конечно, на практике мы не можем разделять  эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как  Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

     Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные  процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

     Область применения генетических алгоритмов.