コラム
遺伝的アルゴリズムに関する文献
最初に、本稿執筆に関して参考にした文献としては
小林 重信：遺伝的アルゴリズムの現状と課題，計測と制御，32-1，1993
畝見 達夫：GAの制御への応用，計測と制御，32-1，1993
長久 勝：NPC動作アルゴリズムの自動生成に関する考察，情報処理学会「数理モデルと問題解決」研究会第18回研究報告会，1998
が挙げられます。論文誌を見る事のできる環境の方は、情報処理学会の論文誌や計測制御関連の学会の論文誌から、GAに関する最新の研究動向を窺い知る事ができます。GAに関する研究は、特にここ数年日本国内で活発に行われており、国際的に高い評価を受けている研究者もおられますので、大抵の場合、日本語の文献だけでなんとかなっちゃうのがうれしいところです。GAに限らず、情報処理に関する研究動向に興味のある方には、いろいろ見れるという意味で、情報処理学会への入会をお勧めします。
書籍としましては……、すいません、私がGAに関心を持った6,7年前には、まだ今のようにGAに関する入門書が豊富にある時代ではありませんでしたので、論文ばかりを漁っていました。そういうわけで、残念ながら私自身あまり書籍を読んでいないのですが、精力的にGAに関する書籍を執筆されている伊庭斉志先生の
伊庭斉志「遺伝的アルゴリズムの基礎-GAの謎を解く-」オーム社 A5判 268頁 定価(本体3700円【税別】) 1994/09
は大変読みやすく、ページ数も手頃で、入門書としてオススメです。
また最近は、WebPage上に講義概要や論文を載せておく大学の先生方もたくさんおられるので、検索エンジンを使って少し探せば、かなりの情報を入手できます。是非、有効に利用して下さい。
乱数について
GAをはじめ、非線型最適化手法の多くは、乱数を利用する事でランダムサーチ的な側面を持ちます。したがって、こうした分野のプログラムでは、乱数の質が問題になるケースがあります。
そもそも乱数を利用したアルゴリズムは、適用範囲が一般的とはいえないでしょう。実務でソフトウェアの開発を行っておられる方で、日常的にrand()を使われている方はそうおられないと思います。いくつかの先端分野に関連するプログラムを組んでおられる方か、ゲームプログラマの方ぐらいだと思います。この事からも分かるように、基本的にrand()は頻繁に利用される事が想定されていません。rand()が使用できないC言語環境は既にないと思いますが、実はこのrand()に落とし穴が潜んでいる場合があるのです。
乱数を発生させるアルゴリズムにはいくつかありますが、少し前まで実際にいくつかの環境でrand()の実装に使われていた線形合同法というアルゴリズムがあります。このアルゴリズムは、得られる乱数の上位の桁は一様乱数なのですが、下位の値が偏る事が知られています。この場合、乱数を利用する上でよく使う
rand() % N
という操作を行うと、一様乱数である上位の値は捨てられる事になり、偏った値を持つ下位の値を利用する事になってしまいます。これに気付かずに一様乱数を期待したプログラムで利用すると、期待した動作を行わない可能性があるのです。
また、アルゴリズムによって発生させる乱数は擬似乱数なので、1次元の数列としてみた場合の分布が一様であったとしても、特定の周期で値を評価すると、規則性が存在する場合があります。極端にいえば、乱数列からある周期で値を取り出しグラフを描くと、直線が描けたりする可能性があるのです。これは、ループ処理の中で毎回決まった回数のrand()呼び出しを行う場合、ループ内の特定の処理部分が取得する乱数は、乱数列からある周期で値を取り出す事になるので、その部分で一様な乱数を期待できない危険性があるという事なのです。
あらゆる周期で乱数列から値を取り出しても、偏りのない一様な乱数になっているかどうかで、乱数生成アルゴリズムの品質を評価する事が可能ですが、この観点から優れた評価を受けている「Mersenne Twister(以下、本文中では"MT"と表記)」というアルゴリズムがあります。詳しくは開発者の手によるWebPageをご覧ください。有り難い事に、MTのCによる実装がDownLoadできます。