Генетические алгоритмы

Вы решили заняться ГА. Что делать?

Группа исследований эволюционных алгоритмов (ТПУ)

Дискуссионная группа по эволюционным вычислениям

Написать письмо

Итак, по той или иной причине, вы решили разобраться в генетическом алгоритме, а, может быть, даже написать его. Первый вопрос: с чего начать?

Прежде всего, рекомендую понять как вообще ЭТО все работает, забыв на некоторое время про кодирование параметров, генетические операторы и прочее. Уверяю, у вас еще будет достаточно времени и возможностей, чтобы вдоволь попугать себя этими страшностями. Чтобы легче было понять, можно представить, как работает простой селекционер от сохи Иван Карпович Ложноножкин из села Нижние Подмышки, разводящий например, свиней. Вполне возможно, он понятия не имеет о всяких там терминах и действует по старинке: нашел свиней получше (пожирнее, или, наоборот, попостнее, а может быть с мягкой и шелковистой щетиной, это уж как у Ивана Карповича душа ляжет) и давай их скрещивать. Если свиньи будут одного пола, то тут, конечно, осечка получится, и максимум, что из этого выйдет: стадо свиней-гомосексуалистов (хорошо еще, если они на людей нападать не будут). А вот ежели свиньи попались разного пола, то счастливый дядя Ваня получает потомство чуть получше, чем их родители, с точки зрения вкуса или шелковистости. Последовательно издеваясь подобным макаром над этим потомством, а затем над следующим и так далее, через некотоое время Иван Карпович может получить хрюнделей с умопомрачительным беконом, из щетины которых можно будет вязать носки и варежки. И тогда в обиход войдет фраза, что "свиньи, это не только ценный мех...".

Все это словоблудие исключительно для того, чтобы в дальнейшем поговорить о более серьезных вещах (хотя, если честно, я просто упражнялся в остроумии, но вы ведь умеете хранить тайны, правда?). В генетических алгоритмах все очень похоже. Набравшись смелости можно даже сказать, что мы занимаемся селекцией, только животные у нас не живые (и даже не мертвые), а представлены как программные модели. Но суть остается та же: выбираются особи получше, скрещиваются, дают потомство. В общем популяция развивается и с течением времени все хорошеет и хорошеет. Напервый взгляд, все очень абстрактно и не имеет отношения к каким-то задачам оптимизации, про необходимость решения которых так много говорят (большевики?). Но! Особи скрещиваются не "абы" какие, а те, которые лучше подходят для ДАННОЙ задачи. Подробнее об этом, а также о том, то из себя должны представлять особи, как они скрещиваются и т.д. читайте в соответствующих разделах по генетическому алгоритму. Здесь я постараюсь дать только общую концепцию и рассмотреть другие вещи, которые редко обсуждаются.

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

Для тех же, кому недосуг, рекомендую поискать на следующих сайтах:

1. www.basegroup.ru - готовая компонента на Дельфи.
2. www.paklin.newmail.ru - компонента для Real-Coded GA (RCGA).
3. www.generation5.org - примеры ГА на С и вообще много всякого полезного добра.
4. www.sourceforge.net - для самых жадных. Есть реализации практически на всех распространенных языках программирования с самыми разными программными архитектурами. Хотите попроще? Пожалуйста. А, может быть, нужно чтобы было наворочено, и один только вид вызывал вздох восхищения и приводил к выпадению нижней челюсти на пол? Запросто. Кстати, в одном из проектов GA Framework for .Net немного поучавствовал и ваш покорный слуга. Зачинатель проекта Илья Левченко, более подробно о проекте можно узнать на сайте или форуме.

Для тех же кто хочет написать ГА сам могу посоветовать следующее:

1. Пишите так, чтобы вам самим было удобно разбираться в программе, при этом, по необходимости и возможности, старайтесь соблюдать приличия. Я имею в виду отступы, имена переменных, классов и функций и т.д., в общем то, что входит в культуру программирования (это полезно, клянусь).
2. Для удобства и экономии нервов не очень рекомендую писать ГА "линейно". Нет, конечно, если вам нужно просто лабораторную сдать или удовлетворить любопытство, в общем, когда программа пишется на один раз, а потом закидывается на самые разненужные кластеры жесткого диска, чтобы потом, возможно, торжественно передать ее младшим курсам, то пожалуйста. А в случае, если у вас серьезно, то лучше отдельный этап генетического алгоритма реализовывать в отдельной функции. У еще удобнее разработать библиотеку классов или воспользоваться решением, использующим объекты. Проще отлаживать и вносить изменения.
3. Вообще, прочитав два предыдущих совета, пришел к выводу, что самый ценный совет, это который первый. Наверное... Вокруг технологии программирования уже сломано множество копий, и советовать здесь дело не особенно благодарное. Просто скажу, что написав за 2,5 года около 8 реализаций ГА для разных задач, понял что мне это надоело. Поэтому сижу и ваяю нечто монструозное, но что позволит в перспективе сильно избавиться от рутины и больше сосредоточиться на исследовании. Более подробно об этом здесь и лучше смотреть презентацию, она посвежее, хотя, честно говоря, и там черновик на черновик. Как-нибудь я выложу то безобразие, которое получается с исходными кодами на C++, и будет всем счастье и великий пивной потоп.

Теперь программа тоже есть. В принципе в большинстве случаев на этом останавливаются, делают отчет и/или ставят "галочку" на личной доске достижений. Но если вам действительно интересны генетические алгоритмы, то здесь вылезает очень большой вопрос "А что дальше?". Ну, допустим, вы рассмотрели какую-то задачу (оптимизации, коммивояжера, расписание, не суть), получили результаты, возможно, где-то их опубликовали. А что же делать следующие 138 лет?

Прежде всего могу посоветовать поиграться с "простейшими" параметрами алгоритма: размер популяции, вероятность операторов скрещивания и мутации - и посмотреть как это отразится на результатах. При этом важен не столько конечный результат, а временные и вычислительные затраты, необходимые для его получения. Дело в том, что в большинстве случаев получить ответ за конечное время на некоторую корректную (!) задачу, т.е. такую задачу, для которой можно достоверно проверить правильность решения, не так уж и сложно, и помимо ГА существует еще целая куча методов оптимизации. Очевидно, что для утверждения целесообразности применения именно генетического алгоритма просто фразы типа "вот эта штуковина с перламутровыми пуговицами находит ответ" явно недостаточно. Необходимы либо видные невооруженным глазом преимущества перед другими методами, либо шаткий-валкий паритет с упором на то, что эволюционные методы достаточно универсальны и т.д. Вот тут уже, наверное, можно завернуть и про перламутровые пуговицы, воззвав к здоровому любопытству тех, кто будет оценивать вашу работу (помните "it's alive!!!" из Франкенштейна?). Последние предложения в большей степени верно для множества тестовых задач (benchmarks), решение реальных практических задач - вопрос совсем другого калибра, но об этом как нибудь в другой раз.

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

• использовать данные, усредненные по (мягко говоря) нескольким запускам. Часто усредняют по 20, 30, 50, 100,... запускам. На мой взгляд, 50 запусков более чем достаточно и в большинстве случаев позволяет обеспечить необходимую репрезентативность получаемых данных;
• использовать данные полученные для разноплановых задач. К примеру, можно взять пару простых задач и несколько сложных с различными характеристиками рельефа целевой функции (симметричность, наличие плато, присутствие шума, обманчивости и т.д.) чтобы охватить достаточно большой спектр проблем. Загвоздка в том, что результаты, полученные для 2-3 задач вряд ли могут претендовать на объективность или свидетельствовать о небывалых вычислительных мощях ГА, по крайней мере, выглядеть это будет достаточно сомнительно, если, конечно вы не предоставите аналитические выкладки, говорящие в вашу пользу.

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

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

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

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

• "чем больше популяция, тем лучше" - верно только до некоторого предела. Если интересно, проведите эксперименты с популяциями различного размера с ограничением на число поколений и посчитайте количество вычислений целевой функции, необходимое для достижения некоторого результата. Могу также посоветовать "повозиться" с ограничением на количество вычислений целевой функции FE и рассмотреть результаты запусков для популяций разных размеров N (время эволюции определяется как FE / N с округлением в большую сторону);
• "кроссовер лучше, чем мутация" или, наоборот, "мутация лучше, чем кроссовер" - совсем не очевидно, так как зависит не только от разновидности самих операторов, но и от задачи, и от того же размера популяции.

Строго говоря, в ГА вообще трудно делать какие бы то ни было обобщающие выводы. Частные, пожалуйста, а вот с общими трудно, т.к. есть вероятность, что всплывет задача, либо модель ГА, для которых сделанные заключения неверны. Есть, конечно, работы, разбирающие отдельные составляющие генетического алгоритма, к примеру статья Blickle и Thiele "A Comparison of Selection Schemes used in Genetic Algorithms (2nd Edition)", которой, кстати, (ура, ура!) в этом году будет 10 лет, однако однозначно сказать, какая стратегия селекции лучше, а какая хуже, на мой взгляд, нельзя.

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

Для того, чтобы исследования шли более плодотворно рекомендую время от времени читать публикации и отчеты исследовательских групп, причем не только свежие, но, пожалуйста, не "брезгуйте" и более древними работами, вних очень много интересного. Ссылки на некоторые из них можно найти здесь. Для чтения вам будет нужен Adobe Acrobat, Distiller или GS Aladdin и неплохие познания в английском. Подсказать, что лучше для каждого отдельно взятого человека сложно, однако могу написать с чего начинал я, возможно, это окажется кому-то полезным.

В самом начале я пытался найти работы, в которых бы оценивалась эффективность тех или иных генетических операторов, рассматривались бы особенности их работы. Вообще, отдавал предпочтение теоретическим работам, хотя по теории я знаю все еще довольно немного. По большому счету поиск информации по ГА начинал с сайта С.А.Исаева (сайт почему-то не работает, старая версия здесь), там нашел ссылку на W.Spears'а и K. De Jong'а. Потом узнал про D.Whitley, D.Goldberg'а и IlliGAL, откуда и сейчас беру немало информации. Вообще, советую время от времени навещать сайты с публикациями и отчетами, и проводить поиск на предмет свежих с пылу с жару работ и статей. Еще я пытался искать информацию о теореме шаблонов, но смысла в ней (как практического, так и теоретического) не так уж и много. Кстати, для охотников за знаменитой книгой J.Holland "Adaptation in natural and artificial systems", я тоже в свое время ее искал, не нашел, но могу с уверенностью сказать, что вы запросто сможете прожить и без этой книги. Я, например, ее в глаза не видел и даже не знаю, как выглядит обложка, хотя, признаюсь, любопытно было бы взглянуть. Очень полезной оказалась рассылка Evolutionary Computations Digest, благодаря которой есть возможно получать новости из мира эволюционных вычислений, в том числе информацию о мероприятиях за рубежом. Еще могу порекомендовать читать как можно больше обзорных статей как по ГА, так и по отдельным аспектам, т.к. можно выделить сразу два больших плюса:

1. узнаете в сжатом виде о том, что было, есть сейчас и перспективы, что очень актуально в условиях информационного ГА-голода в рунете;
2. можно быстро "накопить" хорошую библиографию, пользуясь списком литературы и сайтсиером.

И еще, в Гугле также можно найти много интересного, если вводить название статьи. Смысл не столько в поиске самой статьи (сайтсиер, на мой взгляд, в этом плане удобнее), сколько в поиске работ с похожими названиями, либо содержащими в тексте слова из запроса. Примерно половину интересных статей я нашел именно таким образом. И еще немного о поисковиках. Есть специальные системы для поиска научной информации, например, www.scirus.com (который, кстати, понимает по-русски) и недавно начал работу www.scholar.google.com. Информацию лучше сразу искать на английском, потому что на русском языке практически одно и то же, только разными словами, а статей с конференций и из журналов практически нет. Если кому-то все же интересно, советую посмотреть на ПИТИС'е. Я ни в коем случае не ругаю российскую науку и ученых, занимающихся ГА, но если вы сравните количество, а главное, качество информации на западных сайтах и российских, то, думаю, поймете о чем я говорю. Там выпускаются специализированные журналы, посвященные эволюционным вычислениям, проводятся десятки хороших конференций. Думается, одна только GECCO с 30 лекциями и десятком семинаров по информативности с лихвой перекроет все российские публикации по эволюционным вычислениям за год, вместе взятые, при том, что и в России попадаются исключительно хорошие работы. И дело не столько в деньгах, сколько, на мой взгляд, в банальном отсутствии организации и плохой информированности. Но, чтобы не заканчивать на грустном, хочется отметить неубывающий интерес к генетическим алгоритмам и, раз уж все довольно неказисто сейчас, предположить светлое будущее, до которого и мы все доживем).

Вот, вроде бы, и все. Если кому-то информация окажется полезной, буду очень рад. Хотите поспорить или обсудить? Пишите или, что полезнее для всех, пожалуйте на форум. Или, если желаете массовости, на форум Basegroup, мой ник - Qai.

[16 января 2005г.]