String World Applet

始めに

このアプレットは、簡単な進化シミュレーションを行うものです。遺伝的アルゴリズムの考え方の理解の助けになるでしょう。

動作の概要

このシミュレーションでは、進化する生物は文字列です。seedフィールドの文字列が少しづつ変化して、最終的にgoalフィールドの文字列になるまでの経過を観察することができます。

このシミュレーションは、おおよそ以下のように動作します。

各文字列はchildren #の数だけ子供（微妙に親と違っている）を作る。
もし全文字列の数がcandidate #を超えていた場合は、goalに最も近いものから順にcandidate #の分だけを残し、残りは消去される。
もしgoalに一致したものがあれば、そこで終了。
もし繰り返し回数がmax. cycleを超えていれば、そこで終了。
ユーザがcontinueを押すのを待って、steps回だけ繰り返す（終了条件が満たされた場合は途中でも終了する）。

画面の概要

画面上部（灰色の部分)はシミュレーションの設定を行う部分です。最大サイクル (max. cycle)、1つの候補が作る子供の数(children #)、候補を保持する数 (candidates #)、進化の目標(goal)、最初の候補(seed)、を設定できます。 seedは空欄のままか、goalと同じ文字数の文字列にしてください。

画面下部(青い部分)は実行中のシミュレーションの状態を表示する部分です。左に候補の一覧、右に選択された候補の祖先のリストが表示されます。また、この部分のcontinueボタンを押すことで、シミュレーションを次のサイクルに進めることができます。

簡単な試し方

とりあえず試してみるには、次のようにしてください。

startを押して開始。
continueを押して、進化をすすめる。
初期状態ではcontinueを押しても1サイクルしか進化が進まないので、適当にstepsの値を増やす（初期状態のパラメータでは、おおよそ500-700 サイクル程度で終了しますので目安にしてください）。
時々、候補をクリックして、その候補の祖先達を確認する。
終了すると、goalに到達した候補は赤く強調表示される。

アプレット

genetic.applet.StringWorldApplet will appear below in a Java enabled browser.

シミュレーションについて

全体の動作概要は冒頭を参照していただき、ここでは動作各部の詳細を説明します。

初期候補

初期状態では、seedフィールドは空欄になっています。空欄のまま実行を開始すると、プログラムは自動的に適当なランダムな文字列を生成して、それを最初の候補とします。この最初の候補は、ユーザが指定することも可能です。ただし、goal文字列と完全に文字数が一致している必要があります。また、使用可能な文字はいわゆるASCII文字のみです。

候補の再生産

各候補は、children #で指定された数だけ、子供を作成します。その際、文字列のうちいずれか1文字が、ASCIIコードで隣にある文字に変化します。文字の範囲は0x20-0x7Fで、0x20と0x7Fとは隣り合っているものとみなされます。文字の位置、およびどちら側の隣になるかはその都度ランダムに決定されます。

最適候補の選択

再生産が終了すると、候補の数は(children #) + 1倍に増えます。この中から、最適と思われる候補をcandidates #で指定された数だけに絞り込みます。選択の基準は、文字列中の各位置の文字と、goal文字列の同じ位置の文字とが、ASCIIコード表の中でどれだけ離れているか、を積算した数値です。0x20と0x7Fとは隣り合っているものとみなされます。当然、小さいほうが優位になります。

このアプレットは基本的なコアクラスだけを使って作られていますので、JDK1.1ベースの環境ならおそらくどこでも動くものと思います。動作確認はInprise JBuilder付属のJDK1.1.6およびSUNのJDK 1.2.1のappletviewer、InternetExplorer5.0(英語版・日本語版)、jview(5.00.3167)で行いました。テスト中、JBuilderのJDK1.1.6とSUNのJDK1.2.1でのAWTの動作の違いによる修正なども発生した事実から考えると、爛は言い過ぎかもしれません。

ダウンロード

このアプレットはアプリケーションとしても動作可能です。ここからJAR形式のアーカイブをダウンロードできます。実行は、

Java 2: java -jar genetic.jar
JRE 1.1.x: jre -cp genetic.jar genetic.applet.StringWorldAppet

で可能です。・・・と、思います。jviewがjarを扱えるのかどうか知らないのですが、少なくともjarを解凍（jarコマンドで解凍、もしくは拡張子を.jarから.zipに変えて、zip用の解凍ツールで解凍）すれば、

jview -cp . genetic.applet.StringWorldApplet

で実行可能です。

ソースコードが欲しい方は別途ご連絡ください。

クラス構成の概要

このプログラムのクラス群は、大きく2つに分かれています。汎用的なフレームワークとして設計した部分と、この文字列進化を表現するための部分です。

汎用的なフレームワークにするためのクラスには、以下のような抽象クラスやインターフェースが含まれます。できるだけ汎用的に、かつ自然な形に、というのを第一目標に設計しました。フレームワークですので、実際のプログラムではこれらのクラスやインターフェースを継承や実装して使用することになります。また、実際には、具体クラスのバリエーションの作成を簡単にするため、これらの抽象クラスを継承し、一部機能だけを実装した、より具体クラスに近い抽象クラスもいくつか存在しています。

Genome: 進化の対象となる情報をあらわすクラスです。このオブジェクトの内容の変化が進化となります。
Creature: Genomeを保持するクラスです。自分のGenomeから導出した新しいGenomeをもつ子供を作る機能があります。
Mutagen: Genomeの変化を行うクラスです。ひとつのGenomeを入力し、それを変化させて新しいGenomeを作成します。一般に遺伝情報の変異は内的な要因と外的な要因とがあるため、MutagenはCreatureとEnvironmentに保持されます。
Environment: ・をあらわすクラスです。Creatureが自己再生産を行う際、環境による遺伝情報の変異を行うMutagenを提供します。
Selecter: 進化圧、もしくは淘汰圧を表すクラスです。Creatureのセットの中から、次世代に残す者たちを選択します。
World: 上記のクラス群を統括し、シミュレーションを実行するクラスです。基本的には「Creature達に再生産を指示」(*1)－＞「Selecterに選択を指示」－＞「選択されなかったCreature達に自殺を指示」(*1)－＞「選択されたCreature達にs動」(*2)を指示」というサイクルを繰り返します。サイクル中の各ステップの間に、設定されたWorldObserverをキックします。
WorldObserver: Worldの動作のステップ間に呼び出され、観察や動作のコントロールなどを行うクラスです。EnvironmentやCreature達の状態のスナップショットを取ったり、ユーザの入力を待つ間シミュレーションを停止させたり、あるいは終了条件を調べて必要ならシミュレーションを終了させたりします。
WorldDivine: 上記のクラス群を生成し、しかるべき状態に設定し、シミュレーションを開始するクラスです。Worldを生成し、最初のCreature達やWorldObserver達をWorldに与えます。

今回のシミュレーションでは、これらのクラスをそれぞれ、StringGenome、StringCreature、StgringMutagen、などに継承させて使用しています。また、WorldDivineの具体クラスはアプレットと連携させて使うために、別スレッドで動作するようにしています。

(*1) WorldはCreatureに、再生産や自殺を指示するだけで、実際にCreatureを作ったり、削除したりはしません。指示されたCreatureの方が、子供を作ってWorldに登録したり、あるいは自分自身をWorldから削除したりします。これには2つの理由があります。
まず、これによって、柔軟性・汎用性が増します。Worldにコントロールされない、Creatureの自発的な再生産や自殺が可能になりますし、逆にWorldからの指示を無視できるCreatureも可能です。
また、このほうがより現実に沿ったモデルである、という判断もあります。たとえば心臓に突き立てられたナイフ、といった外的要因が、本当にその生物を殺すのでしょうか？　ナイフという外因を受けた生物が死ぬかどうかは、その生物自身に依存します。普通の人間なら、心臓のナイフは致命的ですが、彼がもし狼男なら結果は変わってくるということです。

(*2) Creatureは、特に内容を特定していない「live」というメソッドを持っており、Worldはサイクル中でそれを起動します。これは、たとえばCreatureに寿命を持たせたい場合の自殺用、再生産のための準備作業、あるいは、進化の頂点に達することだけが目的でなく、進化途上のCreatureたちにも何らかの作業をさせたい場合、などを想定してのものです。

スレッドに関して

GUIと協調させて動作させるため（AWTのイベントはもともと別スレッドで動作するので）、シミュレーションは別スレッドを生成して実行させています（もっとも、入力待ちの時はwaitさせ、スレッドが走っているときは入力を不可能にしているため、あまり意味がないかも知れませんが・・）。

本来はシミュレーション用スレッドをひとつ生成し、シミュレーションを何度実行してもそれを使いまわせばよさそうなものですが、JDK1.2.xからは、スレッドの停止・再開などの制御はobsoleteと宣言されています。使えないことはありませんが幸せではないので、使うのを止めました。その結果、スレッドを使いまわすのが面倒になりそうなため、新しくシミュレーションを実行するたびにスレッドを生成するようにしてしまいました。

前のスレッドが残ったりしないかと少々不安ですが、少なくともInternetExplorer5.0のJavaコンソールで見る限りでは、きちんと毎回古いスレッドは死んでいるようです。もし問題が発生するようでしたら、ご連絡ください。

99/05/12 KOIKE, T.