非常に興味深いアルゴリズムの1つにとして、遺伝的アルゴリズムがあります。遺伝的アルゴリズムは、ダーウィンの自然淘汰を摸したもので、「適応度 (fitness)」によって、個体の生存、繁殖、したがって、適応的突然変異 (adaptive mutation) が選択されるというものです。私は、前回のコラムで、これの背景を説明し、これをPerlで実装したものを2つ紹介しました。1つは、バイト列を繁殖させるプログラムで、もう一つは、単語を繁殖させるプログラムでした。

本稿では、Perlによる遺伝的アルゴリズムについて、もっと高度な内容を扱いたいと思います。なお、本稿を読む前に、1回目の記事を読まれるとよいかもしれません。遺伝的アルゴリズムは、緻密に定義された手順で構成されており、今回紹介するコードの中には、前回の記事を利用していて、詳細説明を省略している部分もあります。

まずは、Perl 5.6.0以上をシステムにインストールしておいてください。以下で紹介する例は、Perlのそれ以前のバージョンや一般的なUNIX以外のプラットフォーム (Windowsなど) でも動くかもしれませんが、そうした環境でのテストは行っておりませんので、そうした環境で動かすには何か手を加える必要があるかもしれません。

今回も単語で

前回の記事では、個体中のDNAから小さな辞書記載単語の集合を検索する例を紹介し、DNAに単語 (長ければ長いほど良い) が何個含まれているかによって、個体をランク付けしました。

今回は、まず、この辞書の例から始めることにして、これをリスト1 のように修正します (全体のソースは、commands.pl からダウンロードできます)。今度は、個々の単語 (DNA中の単語はスペースで区切られている) は個体の適応度を増加または減少させる命令となっています。もし、規則を厳しくしすぎて適応度を上げられないようにしてしまうと、初めに選んだグループは生き残れないでしょう。一方、ルールを緩くしすぎると、時間が経過しても適応度が順調に上がらず、遺伝的アルゴリズムを無用のものとしてしまいます。

まったく規則性がない状態から始めても、個体がこれらの新しいルールにすぐに適応し、それらのルールを活用して高い得点を上げることは、驚くようなことではありませんでした。驚いたのは、それらのルールが予期しない形で利用されたという点でした。たとえば、個体の適応度を自身の値に設定する数値を命令とするルールを設けると、DNAは、他のすべての命令を無視して、その数字の命令を偏重するようになりました。DNAが数字だけにならないようにするために、無効命令の適応度を小さくしたところ、個体は、DNAの中でも無効命令の影響を受けない最後のほうに数値命令を移動しました。

                
# calculate the fitness of the DNA
sub fitness
{
 my $dna = shift @_;  my @words = split ' ', dna_to_words($dna);
 my $fitness = 0;			# start with 0 fitness
 my $max_entry_length = 20;		# longest word we accept
 # note that the 'words' here are command words or numbers
 foreach my $word (@words)		# execute all the words as "instructions"
 {
  if ($word eq 'M')	# 'multiply' instruction
  {
   $fitness *= 2;
  }
  elsif ($word =~ /^A\D*(\d+)/)	# 'amplify' instruction
  {
   $fitness *= $1;
  }
  elsif ($word =~ /(\d+)/)	      # if the instruction is a number
  {
   $fitness += length($1); # increase the fitness depending on the run of digits
  }
  else
  {
   $fitness *= 0.80;	      # the punishment for a 'bad' instruction
  }
 }
 return $fitness;
}					# end of fitness()

私は、DNAや個体が、まるで生きものであるかのように話していますが、ある意味では、実際そうでした。過酷なルールを設けたときのDNAや個体の無反応 (apathy) や、私の予期しなかった形で適応度を急激に高めることができるようなルールを与えたときの繁栄 (exuberance) は、決して忘れることはできません。皆さんも、fitness() 関数に新しいルールを設けてみて、個体が生存するためにどんな進化を遂げるのかを自分の目で確認してみてください。

上に戻る

さらに難しいパズル

前のセクションで、コマンド構造を考察し終わった時点で、私は、次に何をすべきか自問しました。表現型 (phenotypes) やさらに自由度の高いルールなど、付属的な機能を追加して、アルゴリズムを改良することも考えられますし、fitness() 関数で、さらにいろいろなことを試してみることも考えられます。

稿末の参考文献に、遺伝的アルゴリズム・アプリケーション用の高度なPerlモジュールであるMyBeastiesへのリンクを掲げておきます。このモジュールでは、遺伝的アルゴリズムを実装するためにありとあらゆる技法を駆使していますので、さらに別の技法を試すことは望めませんでしたが、これまで組み立ててきた枠組みの範囲内で、高度な遺伝的アルゴリズムの技法を必要としない面白い例をいろいろと作成することはできました。

私は、次の適応度テストのような (A地点からB地点に移動する) 一連の命令を実装してみました。すべての個体は、地点Aの適応度から開始し、地点Bにどれだけ近いかによって、その適応度を上げることができます。コマンドU、D、L、Rは、それぞれ上、下、左、右への移動を行います。コマンドBは、後戻りの移動です。コマンドに続く数値は、何回実行すべきかを指定します。

移動の際、個体は、経路をたどらなければなりません。経路から外れた場合、個体は、経路からどれだけ遠ざかったかに比例した適応度が与えられます。リスト2 をご覧ください。全体のソースは、motion.pl にあります。個体は、110バイトのDNAを使って、定期的に経路上を9ステップ進みます。当然のことながら、長いDNAのほうが、経路上を遠くまで進めるようです。数値パラメーターがないほうが、個体は、よりよく振る舞うようでした。これは、おそらく、命令が単純な場合のほうが、突然変異によってDNAに損傷を与えることが少ないからのようです。人のDNAの場合、基本的な構築要素 (building blocks) は4つだけですので (通常、G、A、T、Cで表される)、これは飛躍した説ではありません。

コマンドの実装方法に注目してください。自由度の高い移動スタック (motion stack)、および (%instructionsハッシュのメンバーとして) 他の命令と調和した形で起動される「後戻り」コマンドを実装しています。また、Math::Complex モジュールを使うことで、2次元の移動のシミュレーションも非常に簡単に実現しています。さらに命令を増やすのも、何でもないことでしょう。(皆さんは、「最後の命令の繰り返し」関数を実装してみてはどうですか。) また、経路をたどる命令で適応度が劇的に上がることにも注意してください。

                
# calculate the fitness of the DNA
sub fitness
{
 my $dna = shift @_;  my @words = split ' ', dna_to_words($dna);
 my $fitness  = 2;			# start with a small fitness
 my $location = Math::Complex->make(0,0); # starting coordinates
 # "ideal" coordinates
 my $goal     = Math::Complex->make(10,10);
 # the path to the goal the DNA instructions must follow
 my @path = split ' ', 'U U U R R R U U U R R R U U U R R R U R';
 my $path_followed = 1;
 # keep track of motion stack (array)
 my @motion_stack;
 # set up motion instructions
 my $instructions = {
		     U  => Math::Complex->make( 0, 1),
		     D  => Math::Complex->make( 0,-1),
		     L  => Math::Complex->make(-1, 0),
		     R  => Math::Complex->make( 1, 0),
		     B =>		# move back
		     sub {
		      my $location = shift @_;
		      my $motion_stack = shift @_;
		      my $instructions = shift @_;
		      my $old_motion = pop @$motion_stack;
		      $location += $instructions->{$old_motion} if defined $old_motion;
		      return $location;
		     },
		    };
 # note that the 'words' here are command words or numbers
 foreach my $word (@words)		# execute all the words as "instructions"
 {
  # only handle legitimate instructions (they can be embedded in bigger words)
  my ($motion, $mag) = $word =~ m/([A-Z])(\d*)/;
  if ($motion && exists $instructions->{$motion})
  {
   $mag = 1 unless $mag;		# always run at least once
   my $instruction = $instructions->{$motion};
   foreach (1..$mag)
   {
    if (ref $instruction eq 'Math::Complex')
    {
     $location += $instruction;		# use the motion vector
     push @motion_stack, $motion;
    }
    elsif (ref $instruction eq 'CODE')
    {
     $location = $instruction->($location,\@motion_stack, $instructions);
       # use the subroutine
    }
   }
  }
 }
 # now see if the individual followed the necessary path
   # (if he didn't, he "fell off the cliff")
 foreach my $path_instruction (@path)
 {
  my $instruction = shift @motion_stack;
    # get the actually executed instruction
  if (defined $instruction && $instruction eq $path_instruction)
  {
   # increase fitness, this individual followed the proper path
   $fitness *= 2;
   $path_followed = 1;			# the individual has not strayed
  }
  else
  {
   # increase fitness a little, so the individual is rewarded for
     # having followed the path this far
   $fitness++;
   $path_followed = 0;	# the individual has strayed, though
   last;
  }
 }
 if ($location == $goal && $path_followed)
 {
  # no point continuing, the individual found the target
  die "Individual [@words] reached the target!"; }
 return $fitness;
}					# end of fitness()
                    

上に戻る

再び単語を扱う

1回目の記事では、単語のソースにDNAを使用し、辞書に含まれる単語に基づき、かつ単語の長さにしたがって、個体の適応度を決定しました。リスト3 (全体のソースは、words2.pl にあります) は、この最初の考え方にしたがいながらも、String::Approx モジュールを使って、近似によるマッチングを採用しています (このモジュールは、別途インストールする必要があるかもしれません)。ぴったり一致した場合にだけ得点を与えるのではなく、近似的な (パーセントで表しての) 一致にも得点を与えようという考え方です。連続的な尺度で得点を与えるのが最もよいのでしょうが、そうすると、アルゴリズムもかなり複雑なものになってしまいます。

最初のコードをこのように書き換えることで、決まって40世代以内で3文字の単語が得られるという、非常に報いの多い結果となりました。近似的一致により、成功する可能性を潜めているDNAパターンが、それ相応に得点が与えられるようになったということです。一致だけでなく、単語の長さによっても得点を決定することで、DNA中の単語は長くなっていきました。

fitness() 関数は、一番最初の例のそれと似ていますが、報酬構造は異なっており、ループは単純化されています。正確な一致が近似的一致よりも格段に高い価値をもっていることに注意してください。

                
# this is a closure block!
{                               # private static variable @dictionary in closure for fitness() only
 my @dictionary;
 # calculate the fitness of the DNA
 sub fitness
 {
  my $dna = shift @_;  my @words = split ' ', dna_to_words($dna);
  my $fitness = 0;			# start with 0 fitness
  my $max_entry_length = 20;		# longest word we accept
  my $precision = 90;			# matching precision, in percent
  my $imprecision = 100 - 90;
  die "Can't use a negative imprecision (your precision must
                       be less than 100 but it's $precision)"
   if $imprecision < 0;
  # you can use any word list at the end of the program
  # do the @dictionary initialization just once
  unless (@dictionary)
  {
   @dictionary = <DATA>;
   foreach (@dictionary)
   {
    chomp;
   }   # eliminate words over $max_entry_length letters, and uppercase them
   @dictionary = grep { length($_) > 1  && length($_) < $max_entry_length }
    map { uc } @dictionary;
  }
  # there is no easy way to avoid this exhaustive check of the dictionary
  # without complicating this example too much
  foreach my $word (@words)
  {
   next unless length $ word > 1;	# don't use single letters
   # note we use "S#%", we don't want insert/append similarities,
     # only replacement similarities
   my @matches = amatch($word, "$imprecision%", @dictionary); my @precise_matches = grep { $word eq $_ } @dictionary;
   $fitness += scalar @matches;
   $fitness += (10 ** length $_) foreach @precise_matches;
     # reward longer words significantly more
  }
  return $fitness;
 } # end of fitness()
}

上に戻る

まとめ

本稿で紹介した例を実行することで私が感じた面白みを皆さんにも感じていただければと思います。恐れずにパラメーターやfitness() 関数に手を加えてみてください。皆さんのアプリケーションの中で遺伝的アルゴリズムを応用してみたいと思われる方は、MyBeastiesも試してみてください (稿末の参考文献参照)。遺伝的アルゴリズムの実装に関しては、しばしば、速度がネックとなり、そのため、ほとんどの場合、かなりの最適化を施す必要がありますので、どんな言語のものであれ、実用に耐える汎用的な遺伝的アルゴリズムのツールキットは、ほとんど存在しません。MyBeastiesは、便利で、かなり高速なツールキットの良い例です。

遺伝的アルゴリズム・アプリケーションの分野は、無限の可能性を秘めています。量子スーパーコンピューター (quantum supercomputers) が開発されれば、遺伝的アルゴリズムは、突然現実的なものとなるだけでなく、いろいろな問題を解決するための1つの手法として好んで使われることになるでしょう。量子コンピューティングは、それが1つの問題に対する数多くの潜在的な解法を同時に評価できるということを前提にすると、非常に大きなサンプル集団を使って進化的なコンピューティングを行うことを前提とする遺伝的アルゴリズムにちょうど応用できるように生み出されたものであるかのように思われます。

参考文献

• 本稿で紹介したコードは、ダウンロードが可能です。
  • commands.pl
  • motion.pl
  • words2.pl
  
  
  
• 今回の記事は、私の遺伝的アルゴリズムについての最初の記事をベースにしています。
  
  
• CPAN には、皆さんがほしいと思うようなありとあらゆるPerlモジュールが紹介されています。
  
  
• PerlおよびPerl関連の情報は、Perl.com でも紹介されています。
  
  
• MyBeasties は、遺伝的アルゴリズム・プログラミング用のPerlモジュールを網羅的に集めたものです。これらのモジュールは、遺伝的アルゴリズムのフレームワークを構築することに関しては、本稿で紹介した例よりも、はるかに高度な内容のものですが、おそらく、初心者のPerlプログラマーにとっては、複雑すぎることと思います。
  
  
• ゲノム配列に関係する人々が直面しているコンピューター利用に関する興味深い障害のいくつかを詳細に概観したものが、Computational challenges in structural and functional genomics (IBM Systems Journal 40:2、2001) です。
  
  
• 私が「洗練されたPerl」の連載で執筆したPerl関係の記事には、以下のものがあります。
  • Perlモジュールによる構文解析 (developerWorks、2000年4月)
  • 全体的な眺望に関する小さな考察 (developerWorks、2000年6月)
  • Perlでデータ保管 (developerWorks、2000年7月)
  • 平易な英語によるPerlプログラムの作成 (developerWorks、2000年8月)
  • 「Programming Perl, Third Edition」のレビュー (developerWorks、2000年9月)
  • 楽々Perlデバッグ (developerWorks、2000年11月)
  • Perlでのアプリケーション構成 (developerWorks、2000年10月)
  • CおよびJavaプログラマーのためのPerl 5.6 (developerWorks、2001年1月)
  • あるプログラマーのLinux指向セットアップ (developerWorks、2001年3月)
  • ワンライナー101 (developerWorks、2001年4月)
  • PerlによるUNIXのシステム管理の自動化 (developerWorks、2001年7月)
  • JAPHのすばらしさ (developerWorks、2001年7月)
  • Perlでの遺伝的アルゴリズムの使用 (developerWorks、2001年8月)
  • PerlによるExcelファイルの読み取り / 書き込み (developerWorks、2001年9月)
  • システム管理用cfengine入門 (developerWorks、2002年2月)
  • Perlによるアプリケーションの設定 第2回 (developerWorks、2002年7月)
  
  
  
• developerWorks のLinuxゾーンには、他にもLinux関係の記事が掲載されています。
  
  

著者について

この記事を評価する

コメント

上に戻る

目次

• 今回も単語で
• さらに難しいパズル
• 再び単語を扱う
• まとめ
• 参考文献
• 著者について
• コメント