蟻コロニー最適化 for 第26回高専プロコン

第26回高専プロコンでは蟻コロニー最適化(ACO)を利用しました。
本番でのスコアはあまり揮いませんでしたが、
みなさんが使うといいスコアに仕上げてくれるものと考えています！

arukuka.hatenablog.com
こっちは参加記。

前置き

ACOはｲﾝﾀｰﾈｯﾂで調べるとよく出ます。一番最初はGAのWikipedia周辺を眺めていたときに見つけました。
学校の課題でTSPが出たとき、GAとACOを書いたのですがACOの方が圧倒的スコアを誇ったので、
それ以来、よく使うようになりました。

高専プロコンで優勝するには、このようなメタヒューリスティクスは使わないほうがいい、
と高専時代に先輩から言われたのですがねハハハ。進歩しないなあ（しみじみ）。
あのころが懐かしいです。

スコアの更新を眺めているのが好きなタイプで、
ACOは途中ぐっとスコアを落としてくれるときがあります。
これがたまらなくかわいい。
好きなアルゴリズムなので利用しています。

チームメイトの中にも、知らない方が多かったので、
高専生の勉強の一つになれれば幸いです。
名前だけでも覚えて帰ってください！

あ、このアルゴリズムは、より少ない石で配置しようとする努力はしません、
最終問題ではスコアで競うことになると思ったので。

内容

どうやって探索するか

ACOではヒューリスティック情報を重んじる係数と、フェロモン情報を重んじる係数が存在します。
初期状態ではフェロモン情報は0なので、ヒューリスティック情報をどこまで信頼するか、
という話になります。

ヒューリスティック

今までの自分の経験上、ヒューリスティック情報にガン積みしたほうがいいスコアになります。
なので、自然とヒューリスティックスコアについては、
最高のヒューリスティックスコアを持つルートのみが候補に残るようになり、それ以外は無視されます。
それでも、探索空間の豊富さ（と考えうるヒューリスティックの貧弱さ）から最高のヒューリスティックスコアを持つルートが複数個存在するので、
それでも十分探索になります。
もちろん、問題によっては変化しうると思いますが。

これをありんこ複数体で動かします。100もいれば安心。

iterate

とは言っても、石の数も多いのですからこれでおしまい、というわけにはいきません。
一度ルートを決めて、探索を行ったらスコアが分かります。
なので、これを利用して「こっちに行ったほうがいいぜ～」というフェロモン情報を
探索ルート（グラフ上の辺）に付与してあげます。
すると2回目以降のありんこ達は、よいスコアを持つルートの方を選びやすくなる、
という感じです。
これを何回も繰り返すことで探索の幅を狭めていき、収束させます。
その間、良い解となった周辺を探索することで、より良い解が見つかることを期待します。
自分は、ビームサーチで先頭からビーム幅を徐々に狭めていくイメージに近いかな、
と思うのですが、どうでしょうか。

フェロモン情報については、定石のようなものがまだ自分の中で確立していません。
多すぎるとすぐに収束するし、ありんこの数などによっても変わります。
なんというか、互いが互いに関係する係数が多くて、ムダの多いアルゴリズムです。
パラメータの多いアルゴリズムは嫌われます。
今回、自分はフェロモン量（スコアが小さいほど多く与えられるアレ）は排除し、
平均から差っ引いた値で更新しています。こうすることで、ムダな探索もしなくなってくれるかなと。

その他

探索グラフの設定

本来であれば、

graph[ 今の石番号 ][ x ][ y ][ 反転 ][ 回転 ][ 前の石番号 ][ x ][ y ][ 反転 ][ 回転 ]

が良いのでしょうが、当然ながらスタックから怒られます。
怒られなくても、広すぎて収束しなそう...。

妥協して、今のところと、今置く石が何手先かだけを見るようにしました。
これでも、置ける場所は限られているので、十分吸収されるかなあと判断しました。

graph[ 今の石番号 ][ 何手先？ ][ x ][ y ][ 反転 ][ 回転 ]

実装では3手先までしか保存せず、それ以外は、4以上です。
本当にそれでいいの？　と言われたら微妙なところです。

利用したヒューリスティック

人によっては、こっちのほうが知りてえよ！　と思うかも。実際の順位がどうだったであろうが、
自分は他の人々がどのような考え方をしてきたのか興味がありますので、
参加者さんは、ぜひ。

自分はチームメイトの方々の意見を参考に作りました。
大ざっぱな話、置く石の周りが埋まっているほど高評価になります
（これ以上でもこれ以下でもないですが...）。
1個より2個、2個より3個埋まっているほうが嬉しいので、
評価値をべき乗して差を作っておきます。
これを上下左右に適用して、それぞれ足します。
あと、数手先も見る関係で、石の周りの個数で違いを吸収します。

足さずに全部かけたり～個数の多いほうに評価値をあげたり～
しましたが、自分の努力の中ではこれが一番よかったです。

以下は該当部分のソースコードです。GitHub - tut-cc/DiceTilingMeu: 第26回高専プロコン競技部門で、詳細が見れます。
気分でavx2のpopcnt利用しただけなので、高速化には寄与していません
（その前の10 \times 10をどうにかしないと...）。

template <class F, class S>
double Ritalgo<F, S>::Ant::h(std::shared_ptr<Stone> s, int x, int y, int rev, int ang) noexcept
{
  unsigned int raw_f[10] = {};
  unsigned int raw_s[10] = {};
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 10; ++j) {

      int dx = j - 1;
      int dy = i - 1;
      int nx = dx + x;
      int ny = dy + y;

      if (nx < 0 || 32 <= nx || ny < 0 || 32 <= ny) {
        raw_f[i] |= 1 << j;
        continue;
      }
      if (field->at(nx, ny)) {
        raw_f[i] |= 1 << j;
      }
      if (dx < 0 || 8 <= dx || dy < 0 || 8 <= dy) {
        continue;
      }
      if (s->at(dx, dy, rev, ang)) {
        raw_f[i] |= 1 << j;
        raw_s[i] |= 1 << j;
      }
    }
  }

  // up
  double up = [&]() {
    unsigned int score = 0;
    unsigned int count = 0;
    for (int i = 1; i <= 8; ++i) {
      unsigned int d1 = raw_s[i] & ~raw_s[i - 1];
      unsigned int sc = _mm_popcnt_u32(d1);
      d1 &= raw_f[i - 1];
      unsigned int ss = _mm_popcnt_u32(d1);

      count += sc;
      score += ss;
    }
    return std::pow((double)score / count, 4) * 5;
  }();
  // down
  double down = [&]() {
    unsigned int score = 0;
    unsigned int count = 0;
    for (int i = 1; i <= 8; ++i) {
      unsigned int d1 = raw_s[i] & ~raw_s[i + 1];
      unsigned int sc = _mm_popcnt_u32(d1);
      d1 &= raw_f[i + 1];
      unsigned int ss = _mm_popcnt_u32(d1);

      count += sc;
      score += ss;
    }
    return std::pow((double)score / count, 4) * 5;
  }();
  // right
  double right = [&]() {
    unsigned int score = 0;
    unsigned int count = 0;
    unsigned int arr[8];
    for (int i = 1; i <= 8; ++i) {
      unsigned int d1 = (raw_s[i] >> 1) & ~raw_s[i];
      unsigned int sc = _mm_popcnt_u32(d1);
      d1 &= raw_f[i];
      unsigned int ss = _mm_popcnt_u32(d1);

      arr[i - 1] = d1;

      count += sc;
      score += ss;
    }
    int line = 0;
    for (int i = 0; i < 8 - 1; ++i) {
      line += _mm_popcnt_u32(arr[i] & arr[i+1]);
    }
    return std::pow((double)score / count, 4) * 5;
  }();
  // left
  double left = [&]() {
    unsigned int score = 0;
    unsigned int count = 0;
    unsigned int arr[8];

    for (int i = 1; i <= 8; ++i) {
      unsigned int d1 = (raw_s[i] << 1) & ~raw_s[i];
      unsigned int sc = _mm_popcnt_u32(d1);
      d1 &= raw_f[i];
      unsigned int ss = _mm_popcnt_u32(d1);

      arr[i - 1] = d1;

      count += sc;
      score += ss;
    }
    int line = 0;
    for (int i = 0; i < 8 - 1; ++i) {
      line += _mm_popcnt_u32(arr[i] & arr[i + 1]);
    }
    return std::pow((double)score / count, 4) * 5;
  }();

  return (up + down + left + right);
}

以上になります。
ここまで読んでくれてありがとうございます。

自分は学力的にも現役高専生に劣るへなちょこ大学生ですが、
大学生たる以上、なんとかして勝ちたいところですね。
自分以外のチームメイトの方々は、推薦以上で入って来られた方々で、
とても強いです。教えてもらいながら自分も強くなれれば。

来年も参加できることを期待しています。
大学生チームも増えるとうれしいなあ。

そのときは、またどうぞおひとつよろしくお願いします。