01 « 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.» 03

Orfeon Blog

読んだ本の要約、感想など。 他にも日々思ったことをつれづれと書き連ねます。

スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Posted on --/--/-- --. --:-- [edit]

category: スポンサー広告

TB: --    CM: --

--

遺伝的アルゴリズムを用いたTSPデモ 



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

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

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

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

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

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

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

遺伝的アルゴリズムの基礎―GAの謎を解く遺伝的アルゴリズムの基礎―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: 自作プログラム

TB: 0    CM: 2

25

コメント

 

はじめまして。

不勉強で申し訳ないのですが、

遺伝的アルゴリズムや、ニューラルネットワークなどと、プログラミングとの違い

を教えていただきたいです。大学で学習してるのですが、イマイチ分かってないです(>_<)

URL |  #- | 2008/05/13 15:30 | edit

 

遺伝的アルゴリズムやニューラルネットワークは、問題の解決のための(広義の)アルゴリズムであり、アルゴリズムは問題の解き方の手順をあらわします。プログラミングとはそのアルゴリズム(手順)どおりにコンピュータを動かして問題の解決を図るためのコンピュータに対する命令文のようなものと考えてもらえればと思います。
学校の講義などで勉強するのは一般にはどう解くかの手順であるアルゴリズムまでの場合が多く、習ったアルゴリズムを実際にコンピュータで動かしてみたい時に初めてプログラミングが必要になります。プログラミングは命令文といいましたが、命令の記述を行うための言語にはいろいろとあり、C言語やJava、Rubyなど、それぞれ特徴を持った様々なプログラミング言語があります。
因数分解の方法(アルゴリズム)は世界共通ですが、それを人に説明して解いてもらうための言葉(プログラミング言語)は国によって異なることと似ています。
プログラミングの入門書はたくさんありますので、まずは気に入った言語を選んで勉強してみてはいかがでしょうか。

URL | YOTTI #- | 2008/05/13 23:49 | edit

Comment
list

コメントの投稿

Secret

Comment
form

トラックバック

トラックバックURL
→http://orfeon.blog80.fc2.com/tb.php/68-14cfd723
この記事にトラックバックする(FC2ブログユーザー)

Trackback
list

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。