Oddwit

http://www.oddwit.com/lab/flashminis/20070603solids/

ボールが飛び跳ねるだけの習作。本当はこの二つをつなぐ剛体が作りたかったのだが、それは次回に持ち越し。

最初はボールをドラッグしている間は座標を直接いじってマウスに吸着させていたが、このやり方はボールを投げたくなったときにダメだった。重力と同じく、マウスがボールを引くのも一つの力とみなす必要があった。

そこで、基本的には常に重力を受け続け、ドラッグしている間はマウスからの引力も受けることにした。簡単のためX軸だけで説明すると、

var dx = _root._xmouse - posx;	// マウスから自分（ボール）までの距離
var fxm = dx * fdamp;		// マウスの引力は距離に比例。fdampはその比例定数

比例定数fdampのfはforce、dampはdampen（鈍らせる）だ。

さて、この力を元に加速度を計算し、加速度を速度に足し合わせて新しい速度を得るが、このそれぞれの段階でも動きを調整する定数をかける。

var accelxm = (fxm/mass)*adamp;	// 加速度＝(力/質量)×加速度比例定数
velocx = (velocx+accelx)*vdamp;	// 速度＝(以前の速度＋加速度）×速度比例定数

あとは座標に足し込めば移動したことになる。

ここで三つの比例定数fdamp, adamp そしてvdamp が登場したが、この設定の仕方によって力に対する物体の挙動が変わってくる。今回の習作では二つのボールで速度比例定数の設定が異なっている。

左のボールは力：7、加速度：0.3、速度：0.9。
右のボールは力：7、加速度：0.3、速度：0.7。

この場合、左のボールのほうがボヨボヨと活発にはねまわる。

力比例定数が大きいと、単純に力が強くなる。これは今は特に問題ない。

加速度比例定数が大きいと、どうやら早送りしているように見えるようだ。逆に小さければスローモーションに見える。

速度比例定数が大きいと、弱い力でもよく動く。小さいければ動きが鈍る。

考慮する力がマウスの引力だけのとき、加速度と速度の定数はそれぞれ0.3、0.7、くらいがいいのだが、重力に対しては1、1がいいことが経験的にわかっている。そこで二種類の力に対して二セットの係数を使い分ける必要がある。

力と加速度は互いに独立した値だから、それぞれの定数を問題なくかけることができる。しかし速度の場合、全ての力を受けた結果としての一つの値しかない。つまり、何か一つの定数をかけなければいけない。

ではその「一つの定数」はどう求めるか。

特に根拠は無かったのだが、二種類の定数を混ぜる方法として加重平均のような正規化のような操作をしてみたところ、びっくりするくらい上手く行った。

重量と引っ張る力がたとえば1:4で、重力的には1がよくて、引っ張り的には0.7がいい場合、最終的な比例定数は
(1/5 * 1) + (4/5 * 0.7)
というわけ。

たぶんこのやり方には名前があるのだろうが、無知無教養な僕には分からない。

このやり方なら、力の源がいくつあっても、それぞれに対する挙動を独立した比例定数のセットとして定義できる。ということは色々なところから力を受ける剛体や紐のようなものもシミュレートできる…はず。それはまた今度。

あらすじ：
Flashで、遺伝的アルゴリズム（GA)で巡回セールスマン問題を解くアプリを実装してみた。GAではパラメータのチューニングがかなり重要な要素だということが理解できた。

実行はこちら。ソースもあるよ

巡回セールスマン問題

今回扱ったのは、いくつかの都市を全て一回ずつ巡回するとき、最短となるルートを発見しようという、いわゆる「巡回セールスマン問題」。

ごり押しで解こうとなると、12の都市で12!（じゅうにバン！と読む）≒4億7千万通りのルートを試さなければならない。できるだけ少ない試行でそれなりに短いルートを得るために、今回は遺伝的アルゴリズム（Genetic Algorithm, GA）を使う。この実装では、12箇所の場合、調べる回数が数万回にまで減らせることが分かった。

遺伝的アルゴリズム

GAは、生物の進化にヒントを得たおもしろいアルゴリズムだ。定義や一般的なやり方についてはWikipediaあたりを見てもらうとして、ごく簡単に説明すると、生物の進化を模倣したアルゴリズムだ。問題に対するさまざまな解を生き物に見立て、解どうしで交配させて子どもを作ったり、環境に適さないものを淘汰したりすることで、確率的に最適解を見つける。

構成

主なクラスは5つ。

• Agent - 一人のセールスマンをあらわすエージェント。DNAを保持
• Population - セールスマンの集まり。世代を経るなどの動作をする
• World - 都市がばらまかれたマップ。エージェントのDNAを評価する
• Node - 都市。
• GA - アルゴリズムを実行する。

まずはPopulationオブジェクトとWorldオブジェクトを作成・初期化し、それをGAオブジェクトに渡して、myGA.run() で実行するという流れだ。