この記事はTokyo City University Advent Calendar 2019の11日目の記事です。
全部の記事はこちらから

はじめに

本記事ではタイトル通り、大谷研究室内で2019年の夏に行われたコンペに関して、私の努力とその時の気持ちをつづっています。数学的考え方に違反しているものもあるかもしれませんし、記事自体の日本語がおかしい時もあるかもしれません。そういう時は優しくコメントをしたうえでコメントの最後に「お前それでも大谷研か！？！？！？！？」とつけていただけると私は喜びます。

経緯(読み飛ばしても支障はありません)

皆さん、こんにちは。東京都市大学大谷研究室所属、情報システム学科、学部3年の山口です。ご存じの方も多いかもしれませんが、都市大では学部3年より研究室に所属しなければなりません。嫌ですね。
まぁ、私は大学に入ったときから人工知能やりたかったし、周りからも評判の良かった大谷研究室入りたかったので本望なのですが。

さて、この研究室では今年から夏休みに3年生に対して課題を出して、その結果をコンペするというシステムが導入されました(今年から)。

私はこの課題が出される前に行われた懇親会でその場の悪ノリでゼミ長になってしまい、また周りの人よりもプログラミング経験が豊富であるという印象を持たれたことから変なプライドが誕生していました。そのため、この戦いには何としても勝たなければならないという使命感に駆られていたのです。

おかげさまで私の夏休みは見事に消え去りました...

コンペスタート！！

それではコンペについてお話しさせていただきましょう！！！(やってること自体が学問的で退屈なのでさっくりとやります。)
コンペを隅々まで読んで内容理解したいよう☀という方はこちら

また、github公開しておきますのでコード見たい方はこちらから

背景

この課題では政府が行っている高齢者の生活支援に対する財政支出に関して解きます。
今なおも進む高齢化社会では、政府が高齢者の介護施設までの移送時間や費用に関して、高齢者の方々にどのように支援すべきか手を焼いている状態です。対策として高齢者に移転の補助金を支払うことで都心部に近い位置に移転させ、施設をその周辺に集中させることで財政支出を抑えられるのではないかという考え方があり、いろいろな状況が考案されています。ですが、施設を建てるなら建てるでお金がかかるため、施設をどこに立てるという組み合わせや移転補助金をいくら出すかという組み合わせは本当にえげつない量になります。

そこで大谷先生が他大学の教授や企業の方と協力してこの問題に取り組みました。

まず高齢者の住む地域一体をメッシュX*Yのマス数の土地として定義し、そこに高齢者が均等に住んでいるものと仮定。
次に高齢者それぞれに私たちがお金を渡して移転させる。移転するかどうかはガウス分布という方法を用いた確率からモンテカルロシミュレーション(=50%だったら100人中50人は動くよねみたいな)という手法を用いて高齢者は移動する。(深く考えなくてもいいです。確率論から高齢者動かしたんだくらいに考えておいてもらえれば)
そして移動した後に施設をお好きなマス(複数可能)に建設する。
最終的な財政支出をたたき出す。

・・・なんかさっくりとしすぎている感じしますが、なるべくさっくり伝えたいのでこれ以上言及しません。サクサクパンダ🐼です。

もちろんこれでも組み合わせはえげつないです。
高齢者にいくら渡すのか？高齢者の施設はどれくらいたてるのか？この二つだけでも組み合わせなんか無限大に等しい！マジ無理ゲー！！！！
ですが、ここで大谷先生の専門分野である「進化計算アルゴリズム」の技術により、圧倒的に早く最適解をたたき出せるのです。

進化計算アルゴリズムについて
進化的アルゴリズム（しんかてきアルゴリズム、evolutionary algorithm、EAと略記）は進化的計算の一分野を意味し、人工知能の一部である。個体群ベースのメタヒューリスティックな最適化アルゴリズムの総称である。そのメカニズムとして生殖、突然変異、遺伝子組み換え、自然淘汰、適者生存といった進化の仕組みに着想を得たアルゴリズムを用いる。最適化問題の解の候補群が生物の個体群の役割を果たし、コスト関数によってどの解が生き残るかを決定する。それが繰り返された後、個体群の進化が行われる。
Wikipediaより

総当たりに比べると格段に速いのが特徴ですが、局所的になりやすい特徴も兼ね備えており工夫が必要になってきます。

本問題では進化計算アルゴリズムの一つである「ハーモニーサーチ」と呼ばれる手法がとられています。
ハーモニーサーチの特徴は以下の通りです。

ほかの進化計算アルゴリズムに比べて最適解にめちゃくちゃゆっくり近づく。(処理時間めっさかかる)
ほかの進化計算アルゴリズムに比べて最適解に着実に近づく。

この状態での結果は財政支出と処理速度が以下の通りです。

財政支出	処理速度
58万円前後	18秒程度

しかし、大谷先生が言うには、 もっと早く解探索できるはず とのことで、参加者がそれぞれ進化計算アルゴリズムを用いてこの課題に挑むというのが今回のコンペの目的です。

コンペの中身

コンペではこの課題に対する各々のプログラムがどれほど速いかとどれほどいい結果をたたき出せるかで比べることとなりました。

コンペの中身もわかったところでいっちょ頑張るかーとなっていた私だったのですが、インターンシップの関係もあり最初はかなり忙しくてコンペに手を付けている場合でもありませんでした。そうやって夏季休業を忙しなく過ごして2週間がたったころある事件が起きます。
同じ研究室3年の学生の一人(N君と呼びます)が「俺はもう終わった」と言い出しました。
私は「！？！？！？！？！？！？」と声にならない感情に苛まれながら彼からその詳細を聞くと、進化計算アルゴリズムの「GA」と呼ばれる手法を使い、めちゃくちゃいい結果をたたき出していました。

GA(遺伝的アルゴリズムについて)
遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。
Wikipediaより

実際にN君がたたき出した結果が以下の通りです。

財政支出	処理速度
48万円前後	2秒程度

これ、やばいでしょ。

GAは確かに進化計算アルゴリズムの中でかなり優れていると言って過言でないアルゴリズムです。加えてこんなに早く結果を出してくるとは思いませんでした。
しかも結果も素晴らしいだと！？くそ～～～～～～！！！！
もちろんここで折れていればサマーバケーションをパーティーピーポーでエンジョイできていた私でしょうが、案の定、私の負けず嫌いが火を噴きました。
「ゼミ長としても普段からプログラミングできると思われている身からしても絶対に負けられん！！！」そう思った私でした。
ですが、GAは素晴らしい進化計算アルゴリズム。もう敗北不可避なわけです。

・・・突然神が私にささやきました。
「単純な進化計算アルゴリズムで勝てないのであれば、独自のものを作るしかない...。」

そういうわけです。
なので、私は進化計算アルゴリズムに縛られずに打開策はないかを考えました。

そこで私が思いついたのが「そもそも最初の組み合わせを生み出す時点で解の候補を絞ればいいんじゃないか？」ということでした。
そうです。実はこの課題 高齢者がどれくらい都心部に移動したか分かった最初の地点で組み合わせを絞ることができるのです。 汎用化された進化計算アルゴリズムには初期で組み合わせを絞るということはしておらず、最初の組み合わせを出す際には本当にランダムだったのです。
私は自身の考え付いたアルゴリズムをとにかく実装しまくりその中から良いものを模索しました。
まぁ最終的には移転率と高齢者が施設を利用する割合それぞれ掛け合わせこれを用いて都心とその周辺に施設を生成するというアルゴリズムを作り出しました。
$都心ゾーンの施設生成確率＝　移転率 \times (1 - 施設利用割合) + 調整値$
$周辺ゾーンの施設生成確率＝　1 - 都心ゾーンの施設生成確率 + 調整値$

さらに進化計算アルゴリズムをハーモニーサーチから「人工蜂コロニーアルゴリズム」に変えました。

人工蜂コロニーアルゴリズムについて
ABCモデルでは、コロニーはミツバチの3つのグループで構成されています：雇用蜂、見物人、偵察兵。各食物源に1匹の人工的に使用されたミツバチがいると想定されます。言い換えれば、コロニーで使用されているミツバチの数は、巣箱の周りの食物源の数に等しい。雇用されたミツバチは食料源に行き、巣に戻ってこの地域で踊ります。食料源が放棄されたハチは、偵察者となり、新しい食料源を見つけるために捜索を開始します。
Wikipediaより

人工蜂コロニーアルゴリズムは「一つの組み合わせに対して、少し改変した組み合わせを作り出し、もとより良いのではないか」と徹底的に調べつくします。私の作ったアルゴリズムはそもそも解を絞って近づけるという物なので、めちゃくちゃシナジーがあるのです。

財政支出	処理速度
43万円前後	20秒程度

結果としてはめちゃくちゃ財政支出を減らせたし、時間も短くなったし、しかも最終的な結果にぶれが生じることが少なくなり安定するというめちゃくちゃ良い記録をとることができました。
これには私も思わずにんまり( ^)o(^ )
しかし、N君もN君でかなりしぶとくGAをとことん極めていきました。(どうやら島モデルとかいう異次元なものに手を出して結果をもりもりよくしていっているようでした。)
さすがの私もこれ以上アルゴリズムに手を加えたいと思えず、「もうやだぁ...負けるぅ...」という気持ちで当日を迎えました。
(この時の私は就活やら他の大会やらこの課題やらで心を病み切って情緒がチューチュートレインでした。)

結果

さて結果はどうなることやら、私が勝つのか。N君が勝つのか。はたまた他の参加者か。ドキドキです。

まぁここまで引っ張っておいて結果はあっさりしていました。

僕が優勝です。技術的にダントツで1位でした。

いやー、当日結果を聞いてびっくりでしたよ。N君のプログラムはなぜか3回ぐらい正常に動作しなかったらしいです。なんでだろ？
・・・全くハラハラさせやがって・・・！

まぁｗ私の事ですしｗやっぱ一位かなーｗ

ちなみにN君は技術はダメでしたが、プレゼンはめちゃくちゃ優れていて1位、僕が2位でした。発表の制限時間守れなかった...どうせならこっちも1位欲しかったなー(´・ω・`)

ま、大谷先生から技術的に1位ということで賞状もらえましたし満足ですね。

終わりに

ここまで読んでいただいた方も飛ばしながら見てくれた方も笑ってくれた方も(いたら)ありがとうございました。
こんなに長い記事になるとは思いませんでした。
技術的な話ばかりで退屈だったと思いますが、これ読んで学問的になにかするの面白いと思えた方はぜひ一度一緒になんかしてみたいですね！
というわけで私の記事は以上にさせていただきたいと思います。ありがとうございました！

昨日の記事：個人シンクライアント運用のすゝめ　 @mikuta0407さん
明日の記事：mikuta0407 @わかさん