Содержание


Cultured Perl

Генетические алгоритмы моделируют многоклеточный организм

Создайте жизнь или что-то на нее похожее

Comments

Серия контента:

Этот контент является частью # из серии # статей: Cultured Perl

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Cultured Perl

Следите за выходом новых статей этой серии.

Две мои первые статьи по генетическим алгоритмам (ГА) на Perl (смотрите Ресурсы) рассматривали мутации и жизненные циклы отдельных клеток, приспособленность которых полностью зависела от их собственной ДНК. В этой статье будет показано, как моделировать многоклеточный организм. Конкретным применением будет генерация буквенных головоломок, которые оцениваются по их сложности и правильности. Для получения основ знаний по ГА вам следует обратиться к двум первым статьям.

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

Итак, давайте начнем конструировать!

Конструирование модели

Есть две существенных части конструирования. Первая – это конструирование отдельной клетки, и вторая – конструирование взаимодействия клеток. Я начну с отдельных клеток.

Каждая клетка будет по существу буквой в кроссворде. Это будет один кусок ДНК. Кроме того, ДНК будет определять, насколько хорошо клетка подходит другим буквам. Так, для английских слов комбинации вроде "an" и "he" будут подходящими, а комбинации типа "xz" -- неподходящими. Это не говорит о том, что сочетание "xz" невозможно, а только о том, что кроссворды с этим сочетанием не будут высоко оцениваться. Я буду использовать словарь слов, находящийся по умолчанию в /usr/share/dict/words на GNU/Linux системах (по крайней мере на моем Debian, используйте команды whereis или locate, чтобы найти его, и измените $words_file соответствующим образом).

Взаимодействие клеток будет происходить в головоломке N на N, где N задается командной строкой и равно 10 по умолчанию. Будет N^2 клеток, выбранных в любой момент времени, и N*2 клеток, не включенных (так что в цикле головоломки 10х10 будет в сумме 120 клеток). Эти числа произвольны и не имеют слишком большого значения, за исключением того, что большой «праздношатающийся» пул будет делать менее выразительным клеточный отбор, в то время как маленький пул будет лимитировать элемент случайности.

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

Отбор клеток из исходного клеточного пула выполняется на основе сродства букв. Если нет других клеток на полке=доске головоломки, подойдет любая клетка. Однако, если программа выбирает клетку для элемента, соседствующего с "A" и "Q", тогда сродство и к "A", и к "Q" будет иметь значение. Поэтому сродство клетки является существенной частью ДНК и будет мутировать точно также, как и буква клетки. Сродство клетки имеет диапазон от 0 до 255, так что оно условно соответствует одному байту ДНК.

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

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

Что касается таблицы, она представляет собой простой хэш. Я испытывал вложенные массивы для моделирования матрицы, но не нужно было проходить через все эти злоключения. Оказывается, что простой хэш с ключом x y был единственным, что мне было нужно, чтобы выполнить моделирование. Функция xy2index() была нужна только в виде отображения; я написал обратную функцию, названную index2xy(), но мне не надо было ее использовать.

Изменения по сравнению с предыдущими статьями

Программа в этой статье представляет собой улучшенную версию программ, моделирующих ГА, которые я изложил в двух предыдущих статьях. Я сделал некоторые изменения, основанные на предложениях читателя Метта Нейберга (Matt Neuberg) и моих собственных наблюдениях.

select_parents() был небрежен в том, что он оставлял в популяции неприспособленных родителей, даже несмотря на то что они имели приспособленность 0 и поэтому не могли быть отобраны. Чтобы исправить это, я добавил дополнительный grep().

Функция recombine()

Я должен напомнить, что популяция родителей содержит множественные ссылки на родителей, основанные на их приспособленности. Чем более приспособленным является родитель, тем больше шансов он имеет для воспроизводства, попадая в родительскую популяцию множество раз.

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

Листинг 1. Функция recombine()
sub recombine
{
 my $population = shift @_;
 my $pop_size = scalar @$population;	# размер популяции
 my @parent_population;
 my @new_population;

 my $total_parent_slots = 0;

 $total_parent_slots += $_->{parent}
  foreach @$population;

 my $position = 0;

 foreach my $individual (@$population)
 {
  foreach my $parenting_opportunity (1 .. $individual->{parent})
  {
   push @parent_population, $individual;
  }
  $individual->{parent} = 0;
 }

 @parent_population = shuffle @parent_population;

 while (1)
 {
  # это может привести к размножению родителей самих по себе, но это не беда 
  my $parent = shift @parent_population;
  my $parent2 = shift @parent_population;
  my $out_of_parents = 0;

  # когда мы вышли из из популяции родителей...
  unless (defined $parent2)
  {
   $parent2 = $parent;
   $out_of_parents = 1;
  }

  my $child = { survived => 1, parent => 0, fitness => 0, dna => 0 };

  # это размножение!
  my $dna1 = $parent->{dna};
  my $dna2 = $parent2->{dna};

  # заметьте, что мы делаем операции с байтами, а не с битами. 
  # Это происходит потому, что байты являются единицами информации 
  # (и сохранение их есть ускорение метода размножения) 
  foreach my $byte (1 .. $dna_byte_length)
  {
   # получить один байт от любого из родителей (выбор родителей произволен)
   # и добавить его ребенку 
   vec($child->{dna}, $byte-1, 8) = vec(((rand() < 0.5) ? $dna1 : $dna2), $byte-1, 8);
  }

  push @new_population, $child;		# ребенок теперь является частью нового поколения 
  push @parent_population, $parent2;	# использовать второго родителя снова,
  					# но только в конце очереди 
  last if $out_of_parents;
 }

 return \@new_population;
}

Обратите внимание на то, как устанавливается $out_of_parents, если последний родитель был только что взят из популяции родителей; это единственный способ вырваться из цикла выбора родителей.

Построение головоломки

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

Для каждой клетки у меня был также атрибут ID, но я использовал его только для проверки правильности алгоритма.

В build_puzzle() я изготовлял всех индивидуумов в @puzzle_population. Я сделал копию @puzzle_population, так что я мог удалять из нее индивидуумов, но не так, что изменения, сделанные в индивидуумах, не будут сохраняться – это поверхностное копирование. Затем я выбрал клетки с помощью choose_tile(). Порядок отбора ячеек случайный, опять с использованием List::Util::shuffle(). Заметьте, что все позиции сохраняются в [x,y] массиве. При этом способе данные можно легко просматривать как одиночные параметры, а не как множественные.

Листинг 2.Функция build_puzzle()
sub build_puzzle
{
 my $population = shift @_;

 my @puzzle_population = @$population;	# сделать локальную копию, мы можем изменить 

 my $i = 0;
 foreach (@puzzle_population)
 {
  $_->{id} = $i++;
  $_->{position} = undef;
  $_->{words} = [];
 }

 my $puzzle = {};

 my @positions;

 foreach my $row (0 .. $size-1)
 {
  foreach my $column (0 .. $size-1)
  {
   push @positions, [$row, $column];
  }
 }


 foreach my $p (shuffle @positions)
 {
  my $row    = $p->[0];
  my $column = $p->[1];

  my $cell =  choose_tile(\@puzzle_population, $puzzle, $p);
  $cell->{position} = $p;
  $puzzle->{xy2index($p)} = $cell;
 }

 return $puzzle;
}

Обратите внимание на отсутствие счетчиков типа $i в recombine() и build_puzzle() выше, плюс во всех остальные местах в программе. Так как у Perl нет проблем с распределением памяти, основным источником ошибок было неправильное отслеживание переменных счетчика (неправильная инициализация, неправильные приращения, неправильные границы). Это не значит, что у меня было много ошибок при написании на Perl, я только нашел, что счетчик переменных увеличивает вероятность ошибок в окрестности его использования.

Теперь вступает в игру choose_tile(). Он будет вызываться для каждой позиции в сетке головоломки для того, чтобы выбрать клетку, которая будет элементом головоломки, расположенным рядом. Я принял во внимание соседние буквы (помня, что некоторые из них еще не инициализированы), когда я вычислял сродство кандидатных клеток для этой позиции в сетке. Я также остерегался неопределенных элементов популяции, потому что таковые встречаются, когда я удаляю клетки из @puzzle_population (проходящий как ссылка на массив, обозначаемая $population в choose_tile()), для того чтобы они стали элементами. Неопределенные элементы популяции получают вес ноль, так что они не будут выбраны функцией sample(), которая выбирает наиболее подходящие клетки для конкретной позиции в сетке.

Листинг 3. Функция choose_tile()
sub choose_tile
{
 my $population = shift @_;
 my $puzzle 	= shift @_;
 my $coords    	= shift @_;

 # раскомментировать это, чтобы получить случайную популяцию 
 # return $population->[int(rand($size**2))];

 my $neighbors =
     puzzle_position_neighbors($puzzle, $coords);

 my @neighbor_letters;

 foreach my $n (@$neighbors)
 {
  next unless defined $n;
  push @neighbor_letters, dna_cell_letter($n);
 }

 my $offset;

  # теперь мы должны использовать сродство 
  my @weights;

  foreach my $p (@$population)
  {
   my $weight = 0;

   if (scalar @neighbor_letters)
   {
    if (defined $p)
    {
     $weight +=
      dna_letter_affinity($p->{dna}, $_)
       foreach @neighbor_letters;
    }
    push @weights, $weight;
   }
   # нет соседних букв
   else
   {
    if (defined $p)
    {
     $weight = ord(dna_cell_letter($p));
    }
    push @weights, $weight;
   }
  }

  # теперь мы имеем массив весов, мы можем производить выборку 
  $offset = sample(\@weights);

 # удалить элемент из популяции и сохранить его в  $cell
 # (да, это может быть сделано в один шаг)
 my $cell = $population->[$offset];
 delete $population->[$offset];

 return $cell;
}

Функция dna_letter_affinity() является ключевой для быстрого отбора клеток, так как она опирается, насколько это возможно, на встроенные функции Perl такие как vec(). Если программу multicell.pl надо оптимизировать по скорости, это первое, на что я обращу внимание.

Теперь, когда головоломка построена, я сканирую ее для поиска слов и вычисляю приспособленность клеток, основываясь на словах, которые они сформировали.

Сканирование и оценка головоломки

Я сканирую головоломку для поиска слов, как горизонтально, так и вертикально, как я уже объяснял раньше. Функция puzzle_scan_words() имеет параметр $flip, который может инвертировать сканирование с горизонтального на вертикальное. Сканирование собирает слова до разрыва (или конца ряда или колонки, или небуквенного элемента) и затем добавляет слова во все буквенные клетки, которые были найдены вдоль пути.

Листинг 4.Функция puzzle_scan_words()
sub puzzle_scan_words
{
 my $puzzle = shift @_;
 my $flip   = shift @_;

 my @words;
 my @trail;

 foreach my $row (0 .. $size-1)
 {
  my $word = '';
  foreach my $column (0 .. $size-1)
  {
   my $p = ($flip) ? [$column, $row] : [$row, $column];
   my $cell = puzzle_cell_at($puzzle, $p);

   croak "Unexpected undefined tile at $row, $column"
    unless defined $cell;

   if (is_cell_letter($cell))
   {
    push @trail, $cell;
    $word .= dna_cell_letter($cell);
   }
   else
   {
    puzzle_add_word($puzzle, $word,
                    @trail);
    @trail = ();
    $word = '';
   }
  }
  puzzle_add_word($puzzle, $word,
                  @trail);
  @trail = ();
 }
}

Заметьте, что могут быть добавлены пустые слова. Функция puzzle_add_word() будет отбрасывать пустые слова – в этом способе логика проще, даже несмотря на то, что в этом способе производится некоторое количество дополнительных вызовов puzzle_add_word().

Список @trail является наиболее важной частью puzzle_scan_words(). Он сохраняет все найденные вдоль пути клетки, которые составляют слово.

После сканирования головоломки я могу оценить приспособленность каждой клетки, основываясь на словах, которые она сделала. Во-первых, всем неразмещенным клеткам дается приспособленность 10. Затем $factor присваивает клетке 5 за буквы и 2 за не-буквы, плюс начальная приспособлеенность 1 за не-буквы.

За каждое слово, которое сделала ячейка, она получает $factor в виде прибавки к счету. Далее, если слово является словарным словом с длиной 2 или больше, то $factor увеличивается в степени, равной длине слова. Это приводит к тому, что клетки, которые делают длинные слова, будут с большой вероятностью выбраны снова. Небуквенные ячейки являются специальным случаем: для них возвращаются слова всех их соседей. Так, пустая ячейка без букв вокруг имеет приспособленность 1, в то время как пустая ячейка, окруженная восемью словами (максимум – 4 с каждой стороны), имеет гораздо большую приспособленность. Таким способом я награждаю пустые ячейки, которые имеют сродство к буквам, особенно к буквам, которые имеют вероятность создать пригодные английские слова.

Листинг 5. Функция fitness()
# вычислить приспособленность ДНК клеток 
# глядя на то, что происходит в головоломке
sub fitness
{
 my $puzzle = shift @_;
 my $cell   = shift @_;

 return 10 unless exists $cell->{position}; # исключить все клетки, 
 					       # не входящие в головоломку 

 my @words = cell_words($puzzle, $cell); # какие слова использует эта клетка? 

 # print "Cell ", $cell->{id}, " uses words @words\n";

 # начать с приспособленности 0 
 my $fitness = 0;
 my $factor;

 if (is_cell_letter($cell))
 {
  $factor = 5; # Наградить более длинные слова значительно больше 
 }
 else
 {
  # наградить немного пустые клетки, но они 
  # получают все соседние слова и начинают достойно 
  $factor = 2;

  $fitness = 1;
 }

 foreach my $word (@words)
 {
  # некоторая минимальная приспособленность для всех клеток 
  $fitness+=$factor;
  next unless exists $dictionary{$word};
  next unless length $word > 1;
  # помните, это производит слово! 
  $generated_words{$word} = 1;
  $fitness += $factor ** length $word;
 }

 return $fitness;
}					# конец fitness()

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

Листинг 6. Эволюция
# История начинается (случайная инициализация) 

Generated: HG
YYYYV@ZOBJ
YTGX@P@GU@
HMNQMTTIXP
PEZQJA@FPP
YX@E@XPHLH
EBZVGM@@XG
VL@Y@ZUBCL
FYFHEFTVYV
TDNLGOXHZG
@@QZJTYFPQ

# нашествие Оtto

Generated: BOY BY FE GO LO LT MB MY OTTO OW PA TB TL TO TOO TOOT TOT TOW TOY TY
YB YE
OOOOTTOTOO
OOOOOOTOOO
OTOOTOOOOO
OTTOTOTOTT
OOTOOOTOOT
OOTOOOOOTO
TOTOOOOOOO
TTOOTTOOOT
OOTTTOOOOT
OOOOTOOTOT

# После 1000 поколений, мгновение мира 

Generated: AN ANA ANN ANNA ANY AR ARA AS AT ATS AU AY BI CS DR GS HI
ID IN IT KR LU NA NAN NAT NB ND NI NU NUN OAT OR OS OTTO PB PI PIP PIT
PT PU RA RAN RB RD RH RN RS RU SN SO SOOT SOT SOTO SOTS SR ST TA TC TI
TO TOO TOOT TOSS TOST TOT TOTO TOTS TS UR US WU YA ZN

TTTTTTTTTT
TTTTTTTTTT
TTTVTTTTTT
VTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT

Выводы

Является ли эта реализация ГА эффективной? Я тестировал случайный выбор букв по сравнению с выбором букв в ГА и выяснил, что выбор букв ГА дает всегда более длинные слова. Случайный выбор дает двух- и трехбуквенные слова, в то время как ГА доходит до шестибуквенных слов в сетке 20х20 после смены нескольких сотен поколений.

Запустите multicell.pl и понаблюдайте за превращениями головоломки. Вы можете увидеть, как пустые ячейки тонут за бортом, затем вторжение букв "I" и "S" (конечно, ISIS было одним из первых произведенных слов). Затем буквы "U" и "T" и небольшая мутация вводит "L" и произведено "LULL". Это очаровательно. Буквы приспосабливаются и начинают отбираться по их пригодности для английского языка; редко случается атака букв типа "Q" или "Z".

В заключение мне хотелось бы обратиться к некоторым комментариям, которые появились в процессе обсуждения в Slashdot первых двух статей по ГА (смотрите ссылку на эту дискуссию в Ресурсах). Многие считают, что Perl работает слишком медленно для моделирования ГА. Я же считаю, что Perl полностью подходит для этого, и обычно проблемы со скоростью возникают из-за плохого программирования на Perl, а не из-за присущих этому языку ограничений. Да, Perl медленнее, чем несовершенный С, но, с другой стороны, мне бы хотелось увидеть эквивалент multicell.pl на С – и я сомневаюсь, что это будет 1) менее 700 строк в длину, 2) без ошибок и 3) что это будет приятно писать. Multicell.pl отвечает все этим трем требованиям.

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

ГА на Perl является полезным обучающим инструментом в качестве прототипа сложных ГА моделирований и для демонстрации простых моделей ГА. Безусловно, также как и многие другие Perl проекты, ГА будет более быстрым на С – вопрос только в том, какого количества времени и усилий на разработку (включая исправление ошибок!) будет стоить это ускорение. И ответ всегда в пользу Perl.


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=240236
ArticleTitle=Cultured Perl: Генетические алгоритмы моделируют многоклеточный организм
publish-date=07132007