Cultured Perl: Генетические алгоритмы, выполненные на Perl

Создайте ваши собственные Дарвинские питомники

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

Теодор Златанов, программист, Gold Software Systems

Теодор Златанов (Teodor Zlatanov) получил диплом магистра по вычислительной технике в Boston University в 1999. Он работает программистом с 1992, используя Perl, Java, C, и C++. Он интересуется работами с открытым исходным кодом по синтаксическому анализу текста, трехуровневыми архитектурами клиент-серверных баз данных, системным администрированием UNIX, CORBA и управлением проектами.



12.07.2007

Вы можете запускать примеры из этой статьи, если в вашей системе есть Perl версии 5.005 или более поздней. Желательно, чтобы у вас была современная (2000 или более поздняя) UNIX-система (Linux, Solaris, BSD), но также подойдут и другие типы операционных систем. Примеры могут быть выполнены и на более ранних версиях Perl и UNIX, а их сбои в функционировании можно рассматривать как упражнения для читателей.

История

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

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

Другие эволюционные алгоритмы пытаются имитировать эволюцию по Ламарку, в которой поведение как механизм выживания может передаваться между поколениями, и даже есть эволюционные программы, которые сами себя пишут для каких-то конкретных целей. Все это выходит за рамки данной статьи.

Основной недостаток Perl для генетических алгоритмов -- это скорость. Из-за необходимости вычислений в генетических алгоритмах они более эффективны на С или других компилируемых языках низкого уровня. Показанные ниже примеры на Perl не обладают таким быстродействием, как их эквиваленты на С, но эти примеры покажут вам, как работает генетический алгоритм, и они обладают достаточным быстродействием для некоторых задач.


Итак, что такое генетический алгоритм?

Генетический алгоритм достаточно прост для понимания при использовании биологических терминов, которым обучают в средней школе. Возьмем популяцию индивидуумов, причем каждый имеет свою собственную ДНК. Затем измеряем приспособленность каждого индивидуума (измеряется как функция, применяемая к ДНК индивидуума) и считаем, что индивидуум с большей вероятностью произведет потомство, если его приспособленность выше. Индивидуумы с очень малой приспособленностью уничтожаются. Каждый выживший получает возможность произвести потомство (и важно, что это никогда не запрещено выжившим, только оно менее вероятно для тех, у кого приспособленность ниже). Слияние родительских ДНК и применение затем случайных мутаций к слившимся ДНК моделирует процесс производства потомства. Новый индивидуум будет теоретически таким же приспособленным, как родители, плюс-минус небольшие вариации, вызванные мутациями. Затем цикл повторяется.

Часто задаваемые вопросы по генетическим алгоритмам
Смотрите раздел в Ресурсы по часто задаваемым вопросам о генетических алгоритмах. В FAQ есть алгоритм GA (генетический алгоритм), и обращено внимание на комплект программного обеспечения по генетическому алгоритму, как бесплатному, так и коммерческому.

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

Также существуют и некоторые недостатки алгоритма. Он лучше работает, если функция приспособленности применяется к ДНК как набор битов. Иными словами, лучше, если ДНК представляет собой набор бинарных опций: да или нет. Голубые глаза? Карие глаза? Рыжие волосы? Черные волосы? Слияние родительских ДНК и последующие мутации не должны разрешать некоторые комбинации битов, так как получающаяся в результате ДНК не будет допустимым решением исходной задачи. Вспомним, что "ДНК" является ни чем иным, как решением для математической формулировки приспособленности. Некоторые величины, используемые в этой формулировке, могут быть несправедливыми – например, деление на ноль.

Кроме того, генетический алгоритм не связан со временем. Вы отбираете количество поколений. Вы можете определить некоторую цель – например, "найти индивидуума с приспособленностью 0.99999" и остановиться, но тогда алгоритм никогда не закончит работу, так как он не сможет найти такого индивидуума. Если вы ставите нереальные цели или задаете слишком мало поколений, то могут возникнуть проблемы. Метод проб и ошибок и хорошее чутье являются лучшими помощниками в этой области.

Формула приспособленности должна выдавать число с плавающей точкой от 0 до 1. Могут быть использованы и другие диапазоны, но, по моему опыту, числа с плавающей точкой работают лучше. Вы можете захотеть интервал от 0 до 32767, если вы хотите для оптимизации использовать 7-битовое число для приспособленности.

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

Существуют три "хороших" способа выхода из генетического алгоритма. Во-первых, вы можете решить выйти из алгоритма, если больше нет разнообразия в фонде ДНК. Это, в действительности, хитрый тест, и модуль CPAN для нахождения протяженности строк может быть полезным в случае, если вы можете представлять ДНК как строку. Во-вторых, вы можете выйти, если вы достигли заданной приспособленности. Пока вы хорошо не поймете формулу приспособленности (для этого вам вообще может быть не нужен генетический алгоритм) постановка задач по приспособленности будет приводить к одному из двух результатов: или бесконечные циклы, или индивидуум, который является всего лишь "довольно хорошим". В третьих, вы можете выйти после заданного числа итераций или "поколений".

На практике все эти три способа (или, по крайней мере, второй и третий) используются для контроля генетического алгоритма. Небольшое число прогонов, возможно 10 или 20, даст вам правильное ощущение того, как быстро сходится алгоритм и какую степень приспособленности вы можете ожидать.


Простой пример

Код в листинге 1 использует единичный байт как ДНК (величина между 0 и 255, 8 бит). Формула приспособленности применяется один раз к каждому новому индивидууму, для этого берется значение байта ДНК и делится на 256. Это означает, что формула приспособленности всегда будет выдавать число между 0 и 255/256, так что оно никогда не достигнет 1. Как вы думаете, какая ДНК будет наиболее приспособленной?

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

Мы строим весовой массив в функции select_parents() с помощью map() поверх grep(). Это могло бы быть написано как цикл, однострочное решение будет здесь более прозрачным и не будет существенно замедлять программу.

Листинг 2. Однострочное решение
my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;

Ссылка на массив $population разыменована. Тогда только элементы массива с «полем выживания» (установленного раньше с помощью функции survive()) пройдут сквозь grep. После этого выжившие отбираются по их номерам приспособленности, которые помещаются на свои места в весовом массиве.

Размер популяции был выбран равным 256, так как в этом случае легко инициализировать каждого индивидуума с номером, равным его индексу. Не стесняйтесь начинать с другим размером популяции.

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

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

Фактическое размножение выполняется случайной 8-битовой bitmask. Мы делаем AND bitmask к ДНК первого родителя (вспомните, что это просто байт) и AND инвертированную bitmask к ДНК второго родителя. Эффект состоит в том, что мы выбираем случайные биты у одного из родителей, а остальные биты приходят от второго родителя.

Мутация выполняется с помощью AND и OR для индивидуальной ДНК с помощью случайной 8-битовой bitmask.

Кстати, наиболее подходящая ДНК, конечно, 255. Вам не нужно ждать 100 000 поколений. Просто нажмите Ctrl-C, когда вы любуетесь строкой состояния.


Размножающиеся слова

В этом примере мы сделаем ДНК 32 бита (5 байт). Каждый байт будет представлять собой букву или пробел. Мы могли бы запаковать больше информации в каждый байт, но это сделало бы пример менее понятным. Каждое значение байта (численно 0-255) будет от А до Z (если величина находится между 65 и 90, условно выбранных, чтобы соответствовать набору ASCII), или пробелу (если величина находится от 0 до 64, или от 91 до 255).

Обратите внимание, насколько этот пример похож на пример в листинге 1. Словарь сопровождает программу.

Основная проблема в этом примере состоит в том, что ДНК длиной больше 32 бит трудно управлять. Я начинал делать свои собственные битовые операции, которые получились не только громоздкими, но и чрезвычайно медленными. Затем я попробовал пакет Math::BigInt, который оказался очень медленным для этой цели.

В конце концов я остановился на функции vec() -- она достаточно быстрая, и была правильным выбором для управления ДНК (по существу ДНК -- это битовый вектор, встроенная структура данных Perl ). Используйте "perldoc -f vec" для того, чтобы больше узнать о функции vec().

Можно закончить с 1024 индивидуумами с нулевой приспособленностью. Поэтому этот пример лучше защищен против такой "ситуации", чем первый пример.

Функции init_population(), recombine() и mutate() были изменены для того, чтобы обрабатывать битовые вектора вместо байтов.

Функция dna_to_words() несколько неэффективна, но она вызывается не слишком часто, чтобы это имело значение. Наибольшее замедление происходит от функции fitness(), которая пытается найти совпадения со всеми словами в словаре, плюс со всеми буквами алфавита.

Приспособленность вычислялась следующим образом: 2 за каждую букву в ДНК, плюс частотность буквы в словаре, плюс 2^N за каждое словарное слово длиной N в ДНК. Массив словаря и hash частотности букв получаются только однажды (используя closure). Пожалуйста, модифицируйте функцию приспособленности и словарь, для того чтобы создавать свои английские слова. Показанная Формула приспособленности сильно смещена в сторону букв и ленится объединяться в английские слова (хотя "on" и "in" появляются достаточно часто).


Выводы

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

Технологии, показанные в примерах, находятся в диапазоне от начального до самого передового уровня, так что постарайтесь как следует понять их. Часто можно сделать улучшения. Функция vec() особенно интересна. Она прекрасно подходит для длиннобитовых векторов, таких как ДНК и других численных данных.

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

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


  • Bluemix

    Узнайте больше информации о платформе IBM Bluemix, создавайте приложения, используя готовые решения!

  • developerWorks Premium

    Эксклюзивные инструменты для построения вашего приложения. Узнать больше.

  • Библиотека документов

    Более трех тысяч статей, обзоров, руководств и других полезных материалов.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=239939
ArticleTitle=Cultured Perl: Генетические алгоритмы, выполненные на Perl
publish-date=07122007