Orfeon Blog

大学院時代に授業の課題で作った遺伝的アルゴリズムを使った巡回セールスマン問題のデモプログラム(当時はVisual C++で実装)を、ActionScript3.0で作ってみました。

ちなみに巡回セールスマン問題とは、地図上に配置された何箇所かの町があるとき、全ての町をちょうど１回ずつ経由してもとに戻る閉路のうち長さが最小のものを求める問題です。 遺伝アルゴリズムは生命の進化の仕組みを最適化問題に応用したもので、興味のある方は詳しくはwikipediaを参照ください↓
　・巡回セールスマン問題
　・遺伝的アルゴリズム

「使い方」
まず緑の画面に、町にあたる点を３箇所以上、左クリックして打ち込みます。各パラメータの設定を下のコントロールボックスで行います(各パラメータの意味は下記参照)。点を打ち込んでから「開始」を押すと、パラメータで設定した世代数に達するまでプログラムが走ります。停止したい場合は「開始」ボタンを押した後の「停止」ボタンを押してください。停止した状態からそのまま続けたい時は「継続」を押してください。ただし継続する場合は個体数のパラメータ変更はできません。町の位置を残したまま遺伝子コードだけ初期化したい場合は「リセット」を、町の位置から全て初期化したい場合は「クリア」を押してください。

・パラメータ
個体数：　　 遺伝子の総数で、多いほど探索能力が向上しますがその分計算時間がかかります。
世代数：　　 この世代に達するまでプログラムは動き続けます。
変異率：　　 この値が大きいと探索に広がりが出て局地解に陥りにくくなる反面、解が収束しづらくなります。

「仕様」
基本的にはGAを基本どおりにTSPに適用しただけで、遺伝子交配方式は２点交差を用いています。ただ次世代に残す遺伝子の選択方式が少し偏っていて、２位の遺伝子と１位の遺伝子で交配。３位と１位、２位。４位と１位、２位、３位…という感じで選択しています。ルーレット方式、ランキング方式、トーナメント方式だとなかなか収束しなかったのでこの方式を用いてみました。突然変異では変異率で選ばれた遺伝子の任意の２点を入れ替える操作を行っております。また、普通に入れ替えるだけでなく、突然変異が起きたときは半々の確率で任意の２点で切り離した経路を逆にしてつなげる"逆位"を行っています。これを用いることで結構収束が早まったように思います。

「実装」
前回C++で組んだプログラムと速度を比べたのですが、C++の方が５倍以上速いようでした。 あと、今回ActionScriptに移植する際、コアの部分は結構楽にできたのですが、自作でコントロールボックスを作った際などで制御が少し込み入って手間取ってしまいました。今回もガリガリ書いたコードをFlex2 SDKでコンパイルして作ったのですが、せっかくFlash CS3環境があるのでインタフェース実装の手間を考えるとそろそろそちらにも慣れ親しむ時なのかもしれません。mxmlについてももっと勉強したいと思いました。

「参考図書」
今回のプログラムのコアの部分は大学院時代に宿題として作ったものをベースにしているのですが、今見てみると当時書いたプログラムはかなり読みにくいものだったので、当時読んでいた以下の本を読み返しながらゼロから作り直しました。といっても自分は遺伝的アルゴリズムが専門というわけではないので、ここで紹介する本も、専門書というよりは、かなり入門書的な色合いが強い本になっています。

遺伝的アルゴリズムの基礎―GAの謎を解く 伊庭 斉志 オーム社 1994-09 売り上げランキング : 215402 Amazonで詳しく見る by G-Tools

ブックオフで100円で売っていたのでとりあえず買って読んでみた本なのですが、GAの基本的な最適化問題への適用方法が簡略な数式で説明されているため、GAの概略を知る意味で役立ちました。

進化論的計算手法 (知の科学) 伊庭 斉志 人工知能学会 JSAI= オーム社 2005-01 売り上げランキング : 169621 Amazonで詳しく見る by G-Tools

巡回セールスマン問題の具体的な解法はこの本を参考にしたのですが、こちらの本はGAの勉強のためというよりは、科学読み物的な感じで読んだ本で、遺伝的プログラミングが音楽情報処理に用いられる例や、蟻の協調性に注目した最適化問題の解法などが紹介されていてとても面白いです。各手法の説明では数式がほとんど用いられておらず、あっても簡単な式なので、手軽に幅広く進化論的な手法の応用例について知るには良い本だと思います。

Posted on 2007/11/25 Sun. 02:24 [edit]

category: 自作プログラム