メタヒューリスティクスと巡回セールスマン問題


つくば市内にはコンビニエンス・ストアがいったい何件あるだろう？

大学のサークルに入ってきた新入生が先輩から，つくばセンターのローソンを出発し，市内のコンビニ一件一件を巡ってそのサークルのポスターを貼り，再び先輩の待つセンターのローソンに戻ってくるように頼まれたとしよう． この新入生の移動距離を最小にするようなコンビニの巡回順序を決める問題が巡回セールスマン問題であり，答を求めることが困難な問題のチャンピオンである．
　仮に市内のコンビニの数がたった20件しかないとしても，巡回順序は全部で

(20 - 1)! = 121645100408832000

通りもあるので，１秒間で1億通りの距離を計算できても，その新入生の在学中には最小距離の巡回順序を求めることはできない． 38年後，ようやく答の見つかるころには，新入生の息子が大学生になって父親と同じサークルに入部しているかもしれない． そのときのコンビニの数が倍に増えていたとしたら，父親としてはサークルからの退部を勧めるだろう．

この例で，巡回セールスマン問題のセールスマン役を任されているのが新入生である． こんなことを新入生に頼むのは先輩のイジメにも等しいが，実際には20件くらいの問題は短時間で厳密に解けるし，コンビニが数百件あっても近似解ならばパソコンで数秒とかからずに求めることができる． その近似算法をいくつかプログラムし，計算時間や近似精度の点でどの算法がもっとも優れているかを明らかにするのが，この課題の目的である． 近似算法として実験を予定しているのは
  1. local search
  2. tabu search
  3. simulated annealing
などであるが，これらの詳しい説明は

http://www.is.tsukuba.ac.jp/~takahito/ucourse.html

上に用意してある．



実験に関する連絡事項

実験のスケジュールその他に関しては

http://www.is.tsukuba.ac.jp/~takahito/ucourse.html

で通知する．





システム数理研究室
久野 誉人
takahito*cs.tsukuba.ac.jp(内線5540, 3F932; "*"は"@")
最適化のすゝめ

個人的な関心は非凸関数の大域的な最小点を効率的に見つけることにあるが，それ以外のところでも卒研などに丁度よさそうな話題はいくつかある．例えば， これらを面白そうと思うかどうかはもちろん人によるだろうが，面白くなければ自分で面白いことを探せばよろしい． おそらく卒研で一番大切なことは，自分にとって面白いことを見つけ出すことで，そのこと自体が最適化問題でもある．

実は，日本の最適化研究はなかなかのもので，論文の数こそ最近は中国に抜かれてしまったが，内容では依然として科学超大国アメリカに次ぐ実力がある（と信じている）. ところが，日本の（特に若手）研究者の研究スタイルに十年ほど前から安直な方向へと変化が表れており，このことに一抹の不安を抱いている．

かつては，厄介な問題が与えられると，効率的に解決するためのアルゴリズムを自分で設計し，プログラムを自分で書いて計算実験を繰り返し，その実用性を検証するのが標準的な研究スタイルであった． それが，ソルバと呼ばれる強力な商用ソフトウェアの普及に伴い，「アルゴリズムを自分で設計し，プログラムを自分で書いて」というプロセスが「モデル化を工夫し，商用ソルバに任せて」にすっかり置き換わってしまった感がある．

もちろんモデル化も最適化の重要な一部ではあるが，このままでは商用ソルバに組み込まれたアルゴリズムを凌駕するようなものは生まれないし，商用ソルバの主な生産国であるアメリカに追いつき，追い越すことなど期待できない． 卒研は，凝ったものでなくてもいいから「アルゴリズムを自分で設計し，プログラムを自分で書いて」計算実験を行う正攻法で取り組んでもらいたい，と願っている． その経験が，ことによると将来，画期的なアルゴリズムの発明につながるかもしれない．

プログラムの得手不得手は確かにある． しかし，プログラマのプロをめざそうというわけではないので，苦手ならばMATLABやOctave, Schilabなどの数値演算パッケージを使えばよろしい． プログラムが得意な連中はとかく，これらのあんちょこソフトを馬鹿にするが，ならば試しに連立一次方程式を解くプログラムを高級言語で書いてMATLABなどと比較してみればいい． プロにご登場願うのは，設計したアルゴリズムの実用性をあんちょこで確認してからでも遅くはない． ちなみに，OctaveもScilabもフリーである．


配属に関する連絡事項