はじめに
この記事はプロコンゼミ(SPC同好会) その２ Advent Calendar 2018 23日目の記事です。
また、この記事はCombMofで発表したスライドとほぼ同一の内容について扱っています。
スライド
これです
ないよう
上のスライドを見てください(書くことがないよう＞＜)
真面目な内容(補足)
上のスライドに載ってない内容をかきます、発表スライドの補足としてご覧ください。
焼きなましについて
「競技プログラミングっぽい事をしたい」「ビームサーチをする」の辺りで感づいて言及していた人を複数人観測しました。が、今回の発表では焼きなましの話をしませんでした。(ごめんなさい)
今回の発表で焼きなましを採用しなかった理由は簡単で、適当に焼きなましても山登りより悪い評価しか出ないからです。
焼きなまし法では評価が下がる方にも遷移をする事がありますが、山登り法より良いスコアを取るためにはスコアが悪化した後の遷移でさらに良い評価を獲得する必要があります。
今回は焼きなましでも山登りでも取る近傍を「ランダムに1枚画像を選んでランダムに選んだ画像と入れ替える」としています。 この近傍の取り方だとなんか無意味なスコアの悪化ばっかり出てきてしまってスコアがあまり良くなりません。かなしいね。詳しい説明をしようと思ったのですが現在時刻が12/23の23:40です。あと20分以内に公開しないといけません。時間が足りません。
スライドの内容について
今回の発表スライドの内容は割と無難なものになっている気がします。理由は簡単で、マサカリが飛んできたりスベったりしたくなかったからです。
ちなみにスライド作成にはこれを使いました。適当にやってもいい感じのスライドができてよかったです。
画像の前処理について
スライドでは説明をしていなかったのですが、各画像毎に特徴量を前計算する事で高速に探索をさせるようにしています。特徴量の計算には様々な手法がある気がするのですが、今回は画像をぼかしていくつかの画素の色を取る、みたいな感じでやっています。もちろん他にも方法はいろいろあります。
†パラメータ最適化†について
最近流行りのoptunaさんを使ってパラメータを最適化する事にします。(えらいので)(ネタになるので)(流行に乗りたいので)
今回のプログラムに用いるハイパーパラメータは特に存在しない(かなしい)のですが、焼きなましをする際の開始/終了温度ぐらいなら最適化できそうです。とりあえず温度を引数に計算をしてから評価値を返す関数を用意して、optunaさんに投げてみます。これすごい簡単に実装できるのでよいです。マラソンのパラメータ調整にもってこいだと思うので、みなさんも使ってみるといい木がします。
プログラムを書いたので実行して最適な温度を調べてみました。結果的に温度が低ければ低いほどよい事がわかりました。ようするに評価の下がる遷移はやめた方がいいという事になります。これはつまり焼きなましがあまり意味を持ってないという事ですね。死
二部マッチングについて
発表の終了後にけんちょんさんから教えて頂いた話なのですが、同じ画像を1枚しか使わない場合のモザイクアートの作成は二部マッチング問題に帰着できるらしいです。(すごい)
片側を元画像(大きい画像)の一部分、もう片側を素材画像(小さい画像)とし、全てのペアについて色差を重みにした辺を張る、みたいな感じにして最大重みの最大マッチング問題を解けばいいらしいです。すごい(ここ間違っていたら指摘おねがいします＞＜)
おわりに
これを書いている時点で12/23の23:58の30秒です。あと90秒で公開しないと遅刻扱いになってしまいます。急いでPublishボタンを押すことにします。こんな記事を見て頂き、ありがとうございました。
