Ferix Canvasは貴方が創造する未来の世界を描くCanvasです。なにも無い、真っ白なCanvasですが、
実は貴方が絵を描きやすいような工夫がたくさんあります。
Canvasの工夫が足りない場合は、我々にリクエストしてくださればCanvasをどんどん変化させますよ。
G.A.Bean
2007.01.19 up
ある問題の最適解を得たいとします。全てのケースに関して順検索を行うには膨大な 計算を行う必要がある場合、どのような解決策があるでしょうか。答えのひとつに 「遺伝的アルゴリズム」があります。ここでは、遺伝的アルゴリズム(GA)の簡単な説 明と簡単なサンプルアプリのを紹介しましょう。
遺伝的アルゴリズムとは
遺伝的アルゴリズムとは、生物の進化の過程(交叉，突然変異，淘汰)を真似て作られ
たアルゴリズムで、確率的探索(抽出されたサンプルを評価しながら探索する方法)を
利用した経験的最適解抽出方法の一手法です。
遺伝的アルゴリズムとは何に使えるのか
あるデータ群に対して一定の評価式を設定することにより、そのデータ群内で優位な
データであるのか、劣位なデータであるのかを決定する事ができます。その環境適応
性質を利用して、次の世代を抽出する方法を遺伝的アルゴリズムと言います。とする
と適用可能範囲は以下が想定できます。
1.評価対象のデータが取得済み
2.評価式の設定が可能
3.全データ順評価を行うにはデータ数が膨大
データが上記のような条件を満たす場合、遺伝的アルゴリズムはでも利用可能となり
ます。具体的には、ある一定のナップザックの中に重さと価値
の異なる物体を出来るだけ価値が高いように詰め込みたいという問題を指すナッ
プザック問題、またはサラリーマンが複数の地点を巡回するためにはどのような
経路が最適であるかを評価する巡回サラリーマン問題などの解決に向いている
と一般的に言われています。
G.A.Bean(G.A.ビーン) の適用
弊社では GA(遺伝的アルゴリズム)エンジンを PHP で作成して
みました。名前は G.A.Bean(ちゃんとピリオドも発音(？)してくださいね)。例題とし
て最適バスケットメンバ選抜問題を作ってみました。
問題の要綱は以下です。
--------------
Q. チーム保有メンバが20人います。その中から10人のロースター(出場を許可されて
いる登録選手)を選抜してください。その10人の中からG.A.Beanが最も強いチーム
となるようにスターターを決定します。
--------------