日記です。なんかあれば書こうと思いますです…。
2006年09月13日(水) 巡回セールスマン問題
高専時代はORの授業でわりとよくやっていたものに巡回セールスマン問題というものがある。これは数ある経路と,ところどころに絶対に立ち寄るポイントを設けて,全部のポイントを通り,かつ一番コストの低い経路をみつけなさいというもの。
例えば,東京都庁をスタート地点として,全国の県庁所在地すべてを一度は必ずとおり,一番安い(もしくは短い)経路をみつけなさいという途方もない問題のこと。
これを解くためには色々と解き方はある。ひとつはGA。遺伝的アルゴリズム。もしくは遺伝的アタックともいう。数ある経路を個体群として,評価関数と乱数による突然変異を用いて,最終的な解をみつけようというもの。これはブームだから手をだしている学者さんがいる。前のところでも2人かぶってたし。今のところでも多分2,3人はこれでかぶっていると思う。評価関数の決め方が重要で,この評価の部分には例えばグリーディー法に準じた関数を使うのがいい。グリーディー法というのは,その地点において一番最適の(最大なり最小なりってことね)解をそれぞれ選んでいくことで全体でも最適になるでしょ,っていういわれてみればそうだと思う関数。これを発明した学者さんって本当にすごいと思う!
でも,GAは今否定されつつある。GAは対象モデルが静止空間じゃないと評価できないといわれている。現在のように,その瞬間で道路事情がかわる(渋滞による交通混雑とか)ようなモデルだと,評価関数を作れないので�世箸いΔ海箸蕕靴ぁ�
これにかわる方法をみつけた人は多分学会賞くらいはもらえる。ほしい人はがんがるんだっ。漏れは致命的なことに別に…そういうのはいいや。学会賞より単位や卒業証書がほしい。そのために勉強がんがる。
ではでは。
前の日の日記を読む
次の日の日記を読む
目次へ
Webページへ