1. 自己紹介
初めまして。星島航と申します。
私は2020年11月ごろに友人に進められてミリオンライブ！の楽曲を聴くようになり、2021年3月ごろから本格的にミリシタを始めた新人です。現在は、各イベントの累積イベントpt報酬およびイベント曲クリア回数報酬を全て獲得する程度に遊んでいます。ミリシタではわたる（ゲームID: 5XRK5G8S）という名前です。
ロコを応援しています。「STEREOPHONIC ISOTONIC」、「fruity love」、「産声とクラブ」が特に好きです。
元々アイカツ！のオタクだったこともあり、ミリオンにはまる前から作詞家安藤紗々さんのファンです。Jelly PoP Beansありがとうございます。最近だと「あたためますか？」もとても良かったですね。
そんな感じです。よろしくお願いします。
2. 先に結果の一例だけ
突然ですが、MTG, MTWに続く次のシリーズ、劇場組は以下の組み合わせでどうでしょうか。
(2, 0) ['真壁瑞希', '豊川風花'] (2, 1) ['北沢志保', '福田のり子'] (2, 2) ['篠宮可憐', '春日未来'] (3, 0) ['北上麗花', '百瀬莉緒', '高坂海美'] (3, 1) ['箱崎星梨花', '中谷育', 'ジュリア'] (3, 2) ['高山紗代子', '桜守歌織', 'ロコ'] (3, 3) ['永吉昴', '佐竹美奈子', '宮尾美也'] (4, 0) ['野々原茜', '田中琴葉', '天空橋朋花', '横山奈緒'] (4, 1) ['エミリー', '望月杏奈', '所恵美', '馬場このみ'] (4, 2) ['最上静香', '矢吹可奈', '周防桃子', '島原エレナ'] (4, 3) ['徳川まつり', '木下ひなた', '七尾百合子', '白石紬'] (5, 0) ['二階堂千鶴', '松田亜利沙', '伊吹翼', '舞浜歩', '大神環']
これは一例なのですが、どのユニットも、少なくともこれまでのCDシリーズではほとんど見たことのない組み合わせになっていて面白いのではないでしょうか。例えばロコは、紗代子、歌織さんとの組み合わせは相当珍しいですよね。
※本記事執筆時点である2022/05/29時点で終了していないCDシリーズについては考慮していません。例外として、MTSについては現時点で判明しているスートでのチーム分けのみ考慮しています。
本記事は、メタヒューリスティックの探索アルゴリズムの1つである「タブーサーチ」を利用して（カタカナが多いですがロコ語ではありません）、劇場組39人をなるべく斬新な「2人組×3、3人組×4、4人組×4、5人組×1」の組み合わせに分けてみた結果のご報告となります。
3. コードおよび使用したデータの置き場所
こちらのリポジトリに置いておきました。コードは全編Jupyter Notebookで完結させており、あまり可読性の高い実装ではありませんが、興味がある方は覗いてみてください。後ほど説明しますが、私（と友人）が独断で決めたハイパーパラメータがあるので、実行環境がある方はcloneしてそれらのパラメータを調整して実行してみると違う結果が得られて面白いかもしれません。というか見たいのでぜひ使ってみて連絡ください。
4. 背景
ミリオンライブ！、良いですよね。私が1年強、このコンテンツを追ってみて、良いなと思ったところは以下の点です。
- 楽曲が良い。
- メンバー52(劇場組だと39)人全員に、ほぼ等しく楽曲が与えられている。ひとりも手放さない。
- ユニットが固定されておらず、CDシリーズのたびに様々なメンバーの組み合わせを楽しめる。
特に3.について、私がコンテンツを追い始めたのはMTWシリーズ終盤からなのであまりその感覚は分からなかったのですが、古参でMTG, MTWシリーズもリアルタイムで追っていた友人はユニット発表時に意外な組み合わせに驚くこともあったようです。私も後にTwitterやアイドルマスターチャンネルのミリオンに関する配信で
- 「Cleaskyが発表された時は『やられた』と思った」
- 「Jelly PoP Beansは発明」
- 「≡君彩≡は最初意外だった」
といったコメントを目にしたことがあります。しかし、いずれのユニットもメンバーに合った素晴らしい楽曲を披露してくれました。今となっては組み合わせに何の違和感もないのではないでしょうか。
少し前にMTWシリーズが無事に完結し、現在はMTSシリーズが進行中です。今後も未だ見ぬ斬新な組み合わせがどんどん提示され、私達を楽しませてくれることでしょう。
～おしまい～
…
ではなく、本記事で書きたいのはここからです。
私は8thライブ2日目の配信視聴を終えた後、ふと思いました。
「次のシリーズでは、どんな組み合わせを見せてくれるんだろう」と。
そして、その思いは数日後には
「組み合わせ、それも今まで見たことない組み合わせを自分で作ってみるの面白そうだな」
というものに変わっていきました。
私はちょうど最近お仕事の関係で組み合わせ最適化のお勉強をしているところだったので、趣味を題材にお勉強ができる良い機会だとも思いました。
ミリオンは9年目に突入したものの、劇場組だけで39人もいるのだからまだ関わりの浅い組み合わせがたくさんあるはず。それを見つけて新たなユニットとし、なるべく斬新な架空のMTXシリーズを作ってみたら面白いのではないか。
思い立ったので、やってみました。
5. 目的
目的は、
- 「なるべく斬新な組み合わせのユニットからなる、劇場組39人全員が参加する架空のMTXシリーズを作る」
です。
具体的な各ユニットの人数構成は、MTG, MTW（の劇場組）に準拠して、
- 2人組ユニット×3
- 3人組ユニット×4
- 4人組ユニット×4
- 5人組ユニット×1
とします。
6. 準備
本記事における「斬新な組み合わせ」の定義ですが、
- 各メンバーが、過去のCDシリーズで「関係が深い」メンバーと同じユニットになっていない
- 各メンバーが、過去（今回はMTG, MTWに限定）の所属ユニットと同じメンバー数のユニットに所属していない
ほど、「斬新な組み合わせ」とします。
6-1. 集計対象CDシリーズおよび集計用データ
今回の集計対象のCDシリーズは、古い順に
- LIVE THE@TER PERFORMANCE
- LIVE THE@TER HARMONY
- LIVE THE@TER DREAMERS
- LIVE THE@TER FORWARD
- THE@TER ACTIVITIES
- MILLION THE@TER GENERATION
- M@STER SPARKLE
- THE@TER BOOST
- THE IDOLM@STER MILLION THE@TER WAVE
- THE@TER CHALLENGE
- なんどでも笑おう
- VOY@GER
- 聖ミリオン女学園
- MILLION THE@TER SEASON（※）
としています。基本的には、少し前に出た以下の動画で紹介されているCDを対象としています。
ただし、以下のCDシリーズは対象外としています。
- ZWEIGLANZ アライアンス・スターダスト
- 52人が関係していないため
- STAR EQUINOX
- （少し悩みましたが）Cleaskyの再登場であり、52人以外のメンバーも含むため
- M@STER SPARKLE2
- 未完結のため
- MILLION THE@TER VARIETY
- すみません忘れていました許してください
- 構想を開始した2月時点ではリリースされていなかったので漏れてしまいました…
また、全体曲（「Welcome!!」、「DIAMOND DAYS」、「EVERYDAY STARS!!」など）やコミカライズ作品の付属CD収録曲（オリジナル・カバー）は集計から外しています。そして、MTG02～04のいわゆる属性曲（「FairyTaleじゃいられない」など）は、CDに収録されている歌唱メンバーだけでなくその属性のミリオンスターズメンバー（各曲13人）全員が歌唱している扱いとしています。
（※）MTSについては、未完結であるものの、第3シーズンまで発表がされており実質4シーズン全てのグループ（スート）の組み合わせが判明しているので、グループの曲のみ集計対象としました。
上記の対象曲を集計用に整理したデータがこちらです。少し探しましたが適当なものがネット上に見つからなかったので、ランティスのサイトを見ながら手打ちでJSONファイルを作成しました。この記事を書くにあたり、この作業が一番しんどかったです。
6-2. 関係評価値の定義
まず、「関係の深さ」の設計が必要です。本記事では、「関係評価値」という値を定義します。関係評価値については、
- 全ての2メンバー間に1つの値として与える
- ミリオンの過去のCDに収録されている各楽曲の歌唱メンバーの組み合わせを参照して算出する
- 値が大きいほど、その2メンバーは「関係が深い」ことを意味する
とします。
次に、関係評価値の算出方法です。詳細はコードを見ていただければと思いますが、おおまかに説明すると、過去の各CDシリーズで
- 同じCDに参加している数が多いほど関係が深い（☆）
- 同じグループで楽曲を歌唱しているほど関係が深い
- 名前なしグループよりも名前ありグループの方が関係が深い
- グループの人数が少ないほど関係が深い
- 一緒に歌っている曲数が多いほど関係が深い
- 同じグループで楽曲を歌唱しているほど関係が深い
- より直近のシリーズで上記に該当するほど関係が深い
といった感じになっており、「～ほど」の度合いは主観で重みづけしたハイパーパラメータで決定しています。 （☆）部分の補足ですが、今回の設定では「同じCDに歌唱曲が収録されているが、同じ曲は歌っていない」場合もわずかに「関係がある」とみなしています。例えば、ロコと風花はLIVE THE@TER DREAMERSで「関係がある」と評価しています。
※まず結果を公開したかったので、詳しい計算方法は需要がありそうであれば後日追記という形にします。コードを読めばなんとなくわかると思います。
もっとも、この算出方法およびハイパーパラメータは大いに議論の余地があるところです。前述の友人にも意見をもらいながら調整していきましたが、納得いかない方もいらっしゃるかもしれません。ご意見がある方はコメントを頂けると幸いです。
上記の集計用データおよび集計ルールから算出した、劇場組39人の任意の2メンバー間の関係評価値を以下のヒートマップに図示します。なお、図示時は小数点以下は四捨五入されています。
ここで値が0となっている2メンバーは、今までのCDシリーズでは一切関わりがない（全体曲以外で同じCDのメンバーになったことすらない）ということになります。例えばロコに着目すると、未来、琴葉、まつり、紗代子、美也、麗花、歌織とは今まで関わりが一切無く、風花ともかなり浅い関係だということが分かります。
※参考として、AS13人も含めた52人版のヒートマップも掲載しておきます。
余談ですが、本記事の設定では歩はミリオンスターズの中で唯一、関係評価値が最大である相手がASメンバー（真）でした。
このマップ、自分で言うのもあれですが見ているだけで楽しいですよね。ゆくゆくはコミカライズの特典CDやミリシタのコミュに一緒に出た組み合わせなども組み込んでいきたいところです（どなたかデータ作ってくださいお願いします）。今回はランティスのCDのみの考慮としているので「○○と△△の評価値が不当に低い！」というご意見もあるかと思いますが、ご容赦ください。
6-3. 過去ユニット人数評価値の定義
次に、「過去ユニット人数評価値」の定義もしておきましょう。こちらは、
- （メンバー、ユニット人数）につき1つの値として与える
- ユニット人数は2, 3, 4, 5
- 各メンバーがMTG, MTWで何人ユニットに所属していたかを参照して算出する
- MTGよりMTWのほうが新しいので、差をつけるためそれぞれ値を0.99, 1.00とする
- 値が大きいほど、そのメンバーはその人数のユニットに「最近なったことがある」ことを意味する
とします。
算出結果は以下のようになります。
| 2 | 3 | 4 | 5 | |
|---|---|---|---|---|
| 天海春香 | 0.00 | 1.00 | 0.00 | 0.00 |
| 如月千早 | 0.00 | 1.00 | 0.00 | 0.00 |
| 星井美希 | 0.00 | 0.00 | 1.00 | 0.00 |
| 萩原雪歩 | 0.00 | 0.00 | 1.00 | 0.00 |
| 高槻やよい | 0.00 | 1.00 | 0.00 | 0.00 |
| 菊地真 | 0.00 | 0.00 | 1.00 | 0.00 |
| 水瀬伊織 | 0.00 | 0.00 | 1.00 | 0.00 |
| 四条貴音 | 0.00 | 1.00 | 0.00 | 0.00 |
| 秋月律子 | 0.00 | 1.00 | 0.00 | 0.00 |
| 三浦あずさ | 0.00 | 1.00 | 0.00 | 0.00 |
| 双海亜美 | 0.00 | 1.00 | 0.00 | 0.00 |
| 双海真美 | 0.00 | 1.00 | 0.00 | 0.00 |
| 我那覇響 | 0.00 | 1.00 | 0.00 | 0.00 |
| 春日未来 | 0.00 | 1.99 | 0.00 | 0.00 |
| 最上静香 | 0.99 | 1.00 | 0.00 | 0.00 |
| 伊吹翼 | 0.00 | 1.99 | 0.00 | 0.00 |
| 田中琴葉 | 0.00 | 0.99 | 1.00 | 0.00 |
| 島原エレナ | 0.99 | 0.00 | 1.00 | 0.00 |
| 佐竹美奈子 | 1.00 | 0.00 | 0.00 | 0.99 |
| 所恵美 | 0.00 | 1.00 | 0.99 | 0.00 |
| 徳川まつり | 0.99 | 0.00 | 1.00 | 0.00 |
| 箱崎星梨花 | 0.00 | 0.00 | 1.99 | 0.00 |
| 野々原茜 | 1.00 | 0.99 | 0.00 | 0.00 |
| 望月杏奈 | 0.00 | 0.00 | 0.99 | 1.00 |
| ロコ | 0.00 | 0.00 | 0.99 | 1.00 |
| 七尾百合子 | 0.00 | 0.99 | 0.00 | 1.00 |
| 高山紗代子 | 0.00 | 0.00 | 1.00 | 0.99 |
| 松田亜利沙 | 0.00 | 1.99 | 0.00 | 0.00 |
| 高坂海美 | 0.00 | 0.00 | 1.00 | 0.99 |
| 中谷育 | 0.00 | 1.99 | 0.00 | 0.00 |
| 天空橋朋花 | 0.00 | 1.00 | 0.99 | 0.00 |
| エミリー | 0.99 | 1.00 | 0.00 | 0.00 |
| 北沢志保 | 0.00 | 0.99 | 1.00 | 0.00 |
| 舞浜歩 | 0.00 | 0.00 | 1.99 | 0.00 |
| 木下ひなた | 0.00 | 0.00 | 1.99 | 0.00 |
| 矢吹可奈 | 0.00 | 1.99 | 0.00 | 0.00 |
| 横山奈緒 | 1.00 | 0.00 | 0.00 | 0.99 |
| 二階堂千鶴 | 0.00 | 0.00 | 1.99 | 0.00 |
| 馬場このみ | 1.00 | 0.00 | 0.99 | 0.00 |
| 大神環 | 0.00 | 1.00 | 0.99 | 0.00 |
| 豊川風花 | 0.00 | 0.00 | 1.99 | 0.00 |
| 宮尾美也 | 0.99 | 0.00 | 1.00 | 0.00 |
| 福田のり子 | 0.00 | 0.00 | 1.00 | 0.99 |
| 真壁瑞希 | 0.00 | 0.99 | 0.00 | 1.00 |
| 篠宮可憐 | 0.00 | 0.99 | 1.00 | 0.00 |
| 百瀬莉緒 | 1.00 | 0.00 | 0.99 | 0.00 |
| 永吉昴 | 0.00 | 0.00 | 0.99 | 1.00 |
| 北上麗花 | 1.00 | 0.00 | 0.99 | 0.00 |
| 周防桃子 | 0.00 | 1.00 | 0.99 | 0.00 |
| ジュリア | 0.99 | 0.00 | 1.00 | 0.00 |
| 白石紬 | 0.00 | 1.99 | 0.00 | 0.00 |
| 桜守歌織 | 0.00 | 0.00 | 1.99 | 0.00 |
ひとまず任意の2メンバー間の関係評価値、各メンバーの過去ユニット人数評価値を定量化することができました。 こちらの値を使用して、「斬新な組み合わせ」を定量化していきます。
6-4. 組み合わせ評価値の定義
組み合わせ同士の「斬新さ」を定量評価するために、「組み合わせ評価値」を定義していきます。「組み合わせ評価値」およびその算出に必要な値の定義は以下のようにします。
- 「組み合わせ評価値」は、評価対象の1つの組み合わせに対して1つの値として算出する
- 具体的には、各メンバー個人に対して評価対象の組み合わせにおける「個人ペナルティ値」を算出し、「組み合わせ評価値」は全メンバーの「個人ペナルティ値」の合計値とする
- 「斬新な組み合わせ」ほど、「組み合わせ評価値」が低くなるように設計する
- 「個人ペナルティ値」は、「個人関係ペナルティ値」と「個人過去ユニット人数ペナルティ値」の重み（こちらも主観で決定したパラメータ）付き和から算出する
- 「個人関係ペナルティ値」は、該当の個人と同じユニットに属しているメンバー間の「関係評価値」およびそのユニット人数から算出する
- 「個人過去ユニット人数ペナルティ値」は、該当の個人が属しているユニットの人数に対応する「過去ユニット人数評価値」から算出する
※こちらも、詳しい計算方法は需要がありそうであれば後日追記という形にします。コードには記載しています。
上記の定義によって、組み合わせ同士を「組み合わせ評価値」という1つの指標で比較することができるようになりました。例として、完全にランダムに作成した2つの組み合わせを「組み合わせ評価値」で比較してみましょう（なお、以降の説明では組み合わせのことを「解」と表記することもあります。ご了承ください）。
初期解サンプル00 # 組み合わせ (2, 0) ['桜守歌織', '馬場このみ'] (2, 1) ['伊吹翼', '天空橋朋花'] (2, 2) ['松田亜利沙', '豊川風花'] (3, 0) ['七尾百合子', '宮尾美也', '北沢志保'] (3, 1) ['高坂海美', '大神環', '望月杏奈'] (3, 2) ['ジュリア', '真壁瑞希', '篠宮可憐'] (3, 3) ['野々原茜', '田中琴葉', '舞浜歩'] (4, 0) ['ロコ', '徳川まつり', '福田のり子', '横山奈緒'] (4, 1) ['木下ひなた', '矢吹可奈', '春日未来', '所恵美'] (4, 2) ['最上静香', '北上麗花', '二階堂千鶴', '百瀬莉緒'] (4, 3) ['箱崎星梨花', '佐竹美奈子', '島原エレナ', 'エミリー'] (5, 0) ['周防桃子', '高山紗代子', '永吉昴', '白石紬', '中谷育'] # 個人ペナルティ値 春日未来 ... 31.73（関係：31.73、過去ユニット：0.0） 最上静香 ... 36.99（関係：36.99、過去ユニット：0.0） 伊吹翼 ... 41.97（関係：41.97、過去ユニット：0.0） 田中琴葉 ... 5.30（関係：4.31、過去ユニット：0.99） 島原エレナ ... 10.50（関係：9.50、過去ユニット：1.0） 佐竹美奈子 ... 8.23（関係：8.23、過去ユニット：0.0） 所恵美 ... 31.81（関係：30.82、過去ユニット：0.99） 徳川まつり ... 5.64（関係：4.64、過去ユニット：1.0） 箱崎星梨花 ... 7.42（関係：5.43、過去ユニット：1.99） 野々原茜 ... 8.14（関係：7.15、過去ユニット：0.99） 望月杏奈 ... 64.40（関係：64.40、過去ユニット：0.0） ロコ ... 8.76（関係：7.77、過去ユニット：0.99） 七尾百合子 ... 1.89（関係：0.90、過去ユニット：0.99） 高山紗代子 ... 15.29（関係：14.30、過去ユニット：0.99） 松田亜利沙 ... 8.62（関係：8.62、過去ユニット：0.0） 高坂海美 ... 56.13（関係：56.13、過去ユニット：0.0） 中谷育 ... 27.31（関係：27.31、過去ユニット：0.0） 天空橋朋花 ... 41.97（関係：41.97、過去ユニット：0.0） エミリー ... 7.61（関係：7.61、過去ユニット：0.0） 北沢志保 ... 5.30（関係：4.31、過去ユニット：0.99） 舞浜歩 ... 4.63（関係：4.63、過去ユニット：0.0） 木下ひなた ... 4.95（関係：2.96、過去ユニット：1.99） 矢吹可奈 ... 58.10（関係：58.10、過去ユニット：0.0） 横山奈緒 ... 46.91（関係：46.91、過去ユニット：0.0） 二階堂千鶴 ... 47.67（関係：45.68、過去ユニット：1.99） 馬場このみ ... 115.24（関係：114.24、過去ユニット：1.0） 大神環 ... 66.78（関係：65.78、過去ユニット：1.0） 豊川風花 ... 8.62（関係：8.62、過去ユニット：0.0） 宮尾美也 ... 3.41（関係：3.41、過去ユニット：0.0） 福田のり子 ... 44.82（関係：43.82、過去ユニット：1.0） 真壁瑞希 ... 30.80（関係：29.81、過去ユニット：0.99） 篠宮可憐 ... 27.32（関係：26.33、過去ユニット：0.99） 百瀬莉緒 ... 54.65（関係：53.66、過去ユニット：0.99） 永吉昴 ... 49.22（関係：48.22、過去ユニット：1.0） 北上麗花 ... 19.48（関係：18.49、過去ユニット：0.99） 周防桃子 ... 73.45（関係：73.45、過去ユニット：0.0） ジュリア ... 10.51（関係：10.51、過去ユニット：0.0） 白石紬 ... 30.85（関係：30.85、過去ユニット：0.0） 桜守歌織 ... 114.24（関係：114.24、過去ユニット：0.0） # 組み合わせ評価値：1236.6676321841906
初期解サンプル01 # 組み合わせ (2, 0) ['松田亜利沙', '周防桃子'] (2, 1) ['白石紬', '七尾百合子'] (2, 2) ['伊吹翼', '永吉昴'] (3, 0) ['ロコ', '島原エレナ', '春日未来'] (3, 1) ['北上麗花', '横山奈緒', 'ジュリア'] (3, 2) ['野々原茜', '中谷育', '北沢志保'] (3, 3) ['高山紗代子', '田中琴葉', '百瀬莉緒'] (4, 0) ['宮尾美也', '天空橋朋花', '箱崎星梨花', '馬場このみ'] (4, 1) ['大神環', '福田のり子', 'エミリー', '望月杏奈'] (4, 2) ['矢吹可奈', '真壁瑞希', '所恵美', '高坂海美'] (4, 3) ['徳川まつり', '佐竹美奈子', '豊川風花', '二階堂千鶴'] (5, 0) ['木下ひなた', '篠宮可憐', '最上静香', '桜守歌織', '舞浜歩'] # 個人ペナルティ値 春日未来 ... 1.99（関係：0.00、過去ユニット：1.99） 最上静香 ... 18.94（関係：18.94、過去ユニット：0.0） 伊吹翼 ... 42.04（関係：42.04、過去ユニット：0.0） 田中琴葉 ... 8.21（関係：7.22、過去ユニット：0.99） 島原エレナ ... 54.06（関係：54.06、過去ユニット：0.0） 佐竹美奈子 ... 2.32（関係：2.32、過去ユニット：0.0） 所恵美 ... 77.90（関係：76.91、過去ユニット：0.99） 徳川まつり ... 20.00（関係：19.00、過去ユニット：1.0） 箱崎星梨花 ... 82.75（関係：80.76、過去ユニット：1.99） 野々原茜 ... 52.87（関係：51.88、過去ユニット：0.99） 望月杏奈 ... 32.85（関係：31.86、過去ユニット：0.99） ロコ ... 54.06（関係：54.06、過去ユニット：0.0） 七尾百合子 ... 3.77（関係：3.77、過去ユニット：0.0） 高山紗代子 ... 3.48（関係：3.48、過去ユニット：0.0） 松田亜利沙 ... 48.24（関係：48.24、過去ユニット：0.0） 高坂海美 ... 34.16（関係：33.16、過去ユニット：1.0） 中谷育 ... 9.46（関係：7.47、過去ユニット：1.99） 天空橋朋花 ... 26.21（関係：25.22、過去ユニット：0.99） エミリー ... 7.63（関係：7.63、過去ユニット：0.0） 北沢志保 ... 52.87（関係：51.88、過去ユニット：0.99） 舞浜歩 ... 8.99（関係：8.99、過去ユニット：0.0） 木下ひなた ... 21.23（関係：21.23、過去ユニット：0.0） 矢吹可奈 ... 42.92（関係：42.92、過去ユニット：0.0） 横山奈緒 ... 0.93（関係：0.93、過去ユニット：0.0） 二階堂千鶴 ... 39.03（関係：37.04、過去ユニット：1.99） 馬場このみ ... 14.49（関係：13.50、過去ユニット：0.99） 大神環 ... 39.76（関係：38.77、過去ユニット：0.99） 豊川風花 ... 54.51（関係：52.52、過去ユニット：1.99） 宮尾美也 ... 53.43（関係：52.43、過去ユニット：1.0） 福田のり子 ... 23.96（関係：22.96、過去ユニット：1.0） 真壁瑞希 ... 37.43（関係：37.43、過去ユニット：0.0） 篠宮可憐 ... 28.49（関係：28.49、過去ユニット：0.0） 百瀬莉緒 ... 3.74（関係：3.74、過去ユニット：0.0） 永吉昴 ... 42.04（関係：42.04、過去ユニット：0.0） 北上麗花 ... 54.88（関係：54.88、過去ユニット：0.0） 周防桃子 ... 48.24（関係：48.24、過去ユニット：0.0） ジュリア ... 55.81（関係：55.81、過去ユニット：0.0） 白石紬 ... 3.77（関係：3.77、過去ユニット：0.0） 桜守歌織 ... 13.43（関係：13.43、過去ユニット：0.0） # 組み合わせ評価値：1220.895189119667
初期解サンプル02 # 組み合わせ (2, 0) ['横山奈緒', '野々原茜'] (2, 1) ['真壁瑞希', '春日未来'] (2, 2) ['白石紬', '最上静香'] (3, 0) ['豊川風花', '馬場このみ', '木下ひなた'] (3, 1) ['篠宮可憐', '島原エレナ', '天空橋朋花'] (3, 2) ['高坂海美', '徳川まつり', '北沢志保'] (3, 3) ['北上麗花', '所恵美', 'エミリー'] (4, 0) ['望月杏奈', '佐竹美奈子', '松田亜利沙', 'ロコ'] (4, 1) ['舞浜歩', '田中琴葉', '福田のり子', '桜守歌織'] (4, 2) ['二階堂千鶴', '宮尾美也', '百瀬莉緒', '矢吹可奈'] (4, 3) ['大神環', '高山紗代子', '中谷育', '箱崎星梨花'] (5, 0) ['永吉昴', '周防桃子', '七尾百合子', '伊吹翼', 'ジュリア'] # 個人ペナルティ値 春日未来 ... 41.41（関係：41.41、過去ユニット：0.0） 最上静香 ... 15.43（関係：14.44、過去ユニット：0.99） 伊吹翼 ... 43.09（関係：43.09、過去ユニット：0.0） 田中琴葉 ... 30.05（関係：29.05、過去ユニット：1.0） 島原エレナ ... 25.12（関係：25.12、過去ユニット：0.0） 佐竹美奈子 ... 25.74（関係：25.74、過去ユニット：0.0） 所恵美 ... 5.41（関係：4.41、過去ユニット：1.0） 徳川まつり ... 66.43（関係：66.43、過去ユニット：0.0） 箱崎星梨花 ... 49.47（関係：47.48、過去ユニット：1.99） 野々原茜 ... 2.79（関係：1.79、過去ユニット：1.0） 望月杏奈 ... 31.96（関係：30.97、過去ユニット：0.99） ロコ ... 40.44（関係：39.45、過去ユニット：0.99） 七尾百合子 ... 66.30（関係：65.30、過去ユニット：1.0） 高山紗代子 ... 4.54（関係：3.54、過去ユニット：1.0） 松田亜利沙 ... 34.51（関係：34.51、過去ユニット：0.0） 高坂海美 ... 53.54（関係：53.54、過去ユニット：0.0） 中谷育 ... 43.18（関係：43.18、過去ユニット：0.0） 天空橋朋花 ... 32.45（関係：31.45、過去ユニット：1.0） エミリー ... 1.00（関係：0.00、過去ユニット：1.0） 北沢志保 ... 65.93（関係：64.94、過去ユニット：0.99） 舞浜歩 ... 26.85（関係：24.86、過去ユニット：1.99） 木下ひなた ... 32.30（関係：32.30、過去ユニット：0.0） 矢吹可奈 ... 19.75（関係：19.75、過去ユニット：0.0） 横山奈緒 ... 2.79（関係：1.79、過去ユニット：1.0） 二階堂千鶴 ... 40.67（関係：38.68、過去ユニット：1.99） 馬場このみ ... 114.56（関係：114.56、過去ユニット：0.0） 大神環 ... 88.11（関係：87.12、過去ユニット：0.99） 豊川風花 ... 91.02（関係：91.02、過去ユニット：0.0） 宮尾美也 ... 17.97（関係：16.97、過去ユニット：1.0） 福田のり子 ... 28.19（関係：27.19、過去ユニット：1.0） 真壁瑞希 ... 41.41（関係：41.41、過去ユニット：0.0） 篠宮可憐 ... 55.70（関係：54.71、過去ユニット：0.99） 百瀬莉緒 ... 75.19（関係：74.20、過去ユニット：0.99） 永吉昴 ... 84.54（関係：83.54、過去ユニット：1.0） 北上麗花 ... 4.41（関係：4.41、過去ユニット：0.0） 周防桃子 ... 42.88（関係：42.88、過去ユニット：0.0） ジュリア ... 29.27（関係：29.27、過去ユニット：0.0） 白石紬 ... 14.44（関係：14.44、過去ユニット：0.0） 桜守歌織 ... 27.53（関係：25.54、過去ユニット：1.99） # 組み合わせ評価値：1516.3729691648741
初期解サンプル03 # 組み合わせ (2, 0) ['徳川まつり', '福田のり子'] (2, 1) ['真壁瑞希', '周防桃子'] (2, 2) ['所恵美', '桜守歌織'] (3, 0) ['松田亜利沙', '高山紗代子', '田中琴葉'] (3, 1) ['白石紬', '篠宮可憐', '豊川風花'] (3, 2) ['舞浜歩', '二階堂千鶴', '百瀬莉緒'] (3, 3) ['春日未来', '永吉昴', '七尾百合子'] (4, 0) ['北上麗花', 'ジュリア', '横山奈緒', 'エミリー'] (4, 1) ['高坂海美', '島原エレナ', '大神環', '矢吹可奈'] (4, 2) ['野々原茜', '馬場このみ', '中谷育', '箱崎星梨花'] (4, 3) ['佐竹美奈子', '宮尾美也', '木下ひなた', '天空橋朋花'] (5, 0) ['伊吹翼', 'ロコ', '北沢志保', '最上静香', '望月杏奈'] # 個人ペナルティ値 春日未来 ... 28.01（関係：26.02、過去ユニット：1.99） 最上静香 ... 59.07（関係：59.07、過去ユニット：0.0） 伊吹翼 ... 49.50（関係：49.50、過去ユニット：0.0） 田中琴葉 ... 33.98（関係：32.99、過去ユニット：0.99） 島原エレナ ... 34.89（関係：33.89、過去ユニット：1.0） 佐竹美奈子 ... 32.98（関係：32.98、過去ユニット：0.0） 所恵美 ... 7.47（関係：7.47、過去ユニット：0.0） 徳川まつり ... 7.95（関係：6.96、過去ユニット：0.99） 箱崎星梨花 ... 46.10（関係：44.11、過去ユニット：1.99） 野々原茜 ... 57.27（関係：57.27、過去ユニット：0.0） 望月杏奈 ... 42.98（関係：41.98、過去ユニット：1.0） ロコ ... 23.98（関係：22.98、過去ユニット：1.0） 七尾百合子 ... 107.74（関係：106.75、過去ユニット：0.99） 高山紗代子 ... 10.70（関係：10.70、過去ユニット：0.0） 松田亜利沙 ... 38.71（関係：36.72、過去ユニット：1.99） 高坂海美 ... 49.25（関係：48.25、過去ユニット：1.0） 中谷育 ... 16.29（関係：16.29、過去ユニット：0.0） 天空橋朋花 ... 4.08（関係：3.09、過去ユニット：0.99） エミリー ... 35.87（関係：35.87、過去ユニット：0.0） 北沢志保 ... 16.62（関係：16.62、過去ユニット：0.0） 舞浜歩 ... 11.41（関係：11.41、過去ユニット：0.0） 木下ひなた ... 57.26（関係：55.27、過去ユニット：1.99） 矢吹可奈 ... 19.03（関係：19.03、過去ユニット：0.0） 横山奈緒 ... 22.69（関係：22.69、過去ユニット：0.0） 二階堂千鶴 ... 65.05（関係：65.05、過去ユニット：0.0） 馬場このみ ... 42.08（関係：41.09、過去ユニット：0.99） 大神環 ... 39.31（関係：38.32、過去ユニット：0.99） 豊川風花 ... 12.84（関係：12.84、過去ユニット：0.0） 宮尾美也 ... 26.37（関係：25.37、過去ユニット：1.0） 福田のり子 ... 6.96（関係：6.96、過去ユニット：0.0） 真壁瑞希 ... 105.51（関係：105.51、過去ユニット：0.0） 篠宮可憐 ... 12.94（関係：11.95、過去ユニット：0.99） 百瀬莉緒 ... 60.60（関係：60.60、過去ユニット：0.0） 永吉昴 ... 80.74（関係：80.74、過去ユニット：0.0） 北上麗花 ... 37.57（関係：36.58、過去ユニット：0.99） 周防桃子 ... 105.51（関係：105.51、過去ユニット：0.0） ジュリア ... 52.01（関係：51.01、過去ユニット：1.0） 白石紬 ... 12.34（関係：10.35、過去ユニット：1.99） 桜守歌織 ... 7.47（関係：7.47、過去ユニット：0.0） # 組み合わせ評価値：1481.1436244558306
初期解サンプル04 # 組み合わせ (2, 0) ['箱崎星梨花', '松田亜利沙'] (2, 1) ['真壁瑞希', '木下ひなた'] (2, 2) ['徳川まつり', '所恵美'] (3, 0) ['伊吹翼', '高坂海美', '北沢志保'] (3, 1) ['佐竹美奈子', '大神環', 'エミリー'] (3, 2) ['野々原茜', '周防桃子', '二階堂千鶴'] (3, 3) ['春日未来', '中谷育', '望月杏奈'] (4, 0) ['永吉昴', '最上静香', '宮尾美也', '福田のり子'] (4, 1) ['百瀬莉緒', 'ジュリア', '高山紗代子', '田中琴葉'] (4, 2) ['白石紬', '桜守歌織', '天空橋朋花', '篠宮可憐'] (4, 3) ['島原エレナ', '豊川風花', '舞浜歩', 'ロコ'] (5, 0) ['馬場このみ', '七尾百合子', '横山奈緒', '矢吹可奈', '北上麗花'] # 個人ペナルティ値 春日未来 ... 45.61（関係：43.62、過去ユニット：1.99） 最上静香 ... 38.42（関係：38.42、過去ユニット：0.0） 伊吹翼 ... 33.21（関係：31.22、過去ユニット：1.99） 田中琴葉 ... 5.81（関係：4.81、過去ユニット：1.0） 島原エレナ ... 76.76（関係：75.76、過去ユニット：1.0） 佐竹美奈子 ... 7.89（関係：7.89、過去ユニット：0.0） 所恵美 ... 7.47（関係：7.47、過去ユニット：0.0） 徳川まつり ... 8.46（関係：7.47、過去ユニット：0.99） 箱崎星梨花 ... 45.42（関係：45.42、過去ユニット：0.0） 野々原茜 ... 25.65（関係：24.66、過去ユニット：0.99） 望月杏奈 ... 43.65（関係：43.65、過去ユニット：0.0） ロコ ... 62.32（関係：61.33、過去ユニット：0.99） 七尾百合子 ... 10.87（関係：9.87、過去ユニット：1.0） 高山紗代子 ... 48.61（関係：47.61、過去ユニット：1.0） 松田亜利沙 ... 45.42（関係：45.42、過去ユニット：0.0） 高坂海美 ... 56.31（関係：56.31、過去ユニット：0.0） 中谷育 ... 8.99（関係：7.00、過去ユニット：1.99） 天空橋朋花 ... 51.44（関係：50.45、過去ユニット：0.99） エミリー ... 9.82（関係：8.82、過去ユニット：1.0） 北沢志保 ... 27.94（関係：26.95、過去ユニット：0.99） 舞浜歩 ... 66.56（関係：64.57、過去ユニット：1.99） 木下ひなた ... 7.47（関係：7.47、過去ユニット：0.0） 矢吹可奈 ... 19.52（関係：19.52、過去ユニット：0.0） 横山奈緒 ... 8.10（関係：7.11、過去ユニット：0.99） 二階堂千鶴 ... 46.24（関係：46.24、過去ユニット：0.0） 馬場このみ ... 20.38（関係：20.38、過去ユニット：0.0） 大神環 ... 1.93（関係：0.93、過去ユニット：1.0） 豊川風花 ... 7.40（関係：5.41、過去ユニット：1.99） 宮尾美也 ... 14.86（関係：13.86、過去ユニット：1.0） 福田のり子 ... 20.59（関係：19.59、過去ユニット：1.0） 真壁瑞希 ... 7.47（関係：7.47、過去ユニット：0.0） 篠宮可憐 ... 26.82（関係：25.82、過去ユニット：1.0） 百瀬莉緒 ... 6.44（関係：5.45、過去ユニット：0.99） 永吉昴 ... 45.14（関係：44.15、過去ユニット：0.99） 北上麗花 ... 34.55（関係：34.55、過去ユニット：0.0） 周防桃子 ... 29.41（関係：28.41、過去ユニット：1.0） ジュリア ... 49.24（関係：48.24、過去ユニット：1.0） 白石紬 ... 48.07（関係：48.07、過去ユニット：0.0） 桜守歌織 ... 20.39（関係：18.40、過去ユニット：1.99） # 組み合わせ評価値：1140.6603801180522
本記事で定義した評価値によると、（いずれも評価値が大きいですが）この中では解サンプル04が一番「斬新な組み合わせ」ということになります。
あとは、すべての組み合わせの中から「評価値が最も小さい組み合わせ」＝「本記事の定義する『斬新な組み合わせ』」を見つけられれば目的達成です。簡単ですね！
…
本当に簡単でしょうか。
6-5. 全組み合わせの数の確認
さて、ここで1点確認しておきましょう。
39人を「2人組×3、3人組×4、4人組×4、5人組×1の計12ユニット」に分ける場合の全組み合わせ数はいくつになるでしょうか。
始めに39人から2人を選び、残った37人から2人を選び、…、残った5人から5人を選ぶ、という考え方をすると、
を計算すれば良さそうです。各行は、1つ前までの行の結果残っているメンバーからn(n=2, 3, 4, 5)人組ユニットを規定数（それぞれ3, 4, 4, 1）分作る場合の数を表しています。各行の最後でユニット数の階乗による除算が必要なのは、その前までの計算で区別されてしまっている「作成したn人組ユニットの中で何番目のユニットか」の区別をなくすためです。
これを計算すると、
14298488868238422216189113532416通り。
…
1429穰8488𥝱8682垓3842京2216兆1891億1353万2416通りとなります。穰。
仮に1秒に100万個の組み合わせを評価できるひゃくまんパワー計算機があったとしても、すべての組み合わせを評価するには大体2700京年かかります。
7. 手法：タブーサーチ
※ここからは最適化アルゴリズムのお話になります。結果だけ見たい方は読み飛ばしても大丈夫です。
上述の通り、いわゆる全探索を行い「すべての組み合わせのうち厳密に評価値が最小（＝最も斬新）となる組み合わせ」を得るのは現実的ではないことがわかりました。
では、現実的な量の探索で「評価値がなるべく最小に近い組み合わせ」を探す方法はないでしょうか。
あります。それが、ヒューリスティクス（発見的手法）です。
本記事では、メタヒューリスティクス（ヒューリスティクスの中でも様々な問題に対応できるように設計されたもの）の1つである「タブーサーチ」というアルゴリズムを使用します。
7-1. タブーサーチの概要
タブーサーチのアルゴリズムの流れについては、上記のWikipediaのページに非常にわかりやすく書いてあるので興味がある方は一度読んでみてください。ざっくりと流れを説明すると、
- 適当に初期解（＝現在解）を作成する
- 最適解を用意する（開始時は、＝現在解とする）
- 最適解と現在解の評価値を計算する
- タブーリスト（この時点では要素0）を用意する
- タブーリストの1つの要素を何にすると効率的かについては様々な研究があるが、本記事では「（解その1→解その2）」の形とする
- リストの最大サイズを決定しておく（本記事では固定値とする）
- 以下を、期待する評価の解が得られるか設定した回数に達するまで繰り返す
- 現在解をわずかに変化させた解（近傍解）を規定数分作成する
- すべての近傍解の評価値を計算し、最も良い評価の近傍解（最良近傍解）を選択する
- もし最良近傍解が最適解より良い評価だった場合
- もしタブーリストに要素「現在解→最良近傍解」が含まれていた場合
- その要素をタブーリストの末尾に移動する
- もしタブーリストに要素「現在解→最良近傍解」が含まれていなかった場合
- その要素をタブーリストの末尾に追加する
- 現在解および最適解を最良近傍解に更新する
- もしタブーリストに要素「現在解→最良近傍解」が含まれていた場合
- もし最良近傍解が最適解より良くない評価だった場合
- もしタブーリストに要素「現在解→最良近傍解」がない場合
- 要素「現在解→最良近傍解」をタブーリストの末尾に加える
- 現在解を最良近傍解に更新する
- もしタブーリストに要素「現在解→最良近傍解」がある場合
- 何も行わない
- もしタブーリストに要素「現在解→最良近傍解」がない場合
- もしタブーリストのサイズが設定した最大サイズを上回っている場合
- タブーリストの先頭の要素を削除する
- もし最良近傍解が最適解より良い評価だった場合
これだけです。非常に実装が簡単そうなアルゴリズムですね。
タブーサーチの特長としては、
- 「（これまでの探索における）最適解」と「現在解」を別々に保持することで、探索全体で発見した最適解が保存される
- 現在解の遷移はタブーリストで制限されつつ、「評価が悪くなる方向」にも発生するので、探索が局所解に陥りにくい
という点が挙げられます。こちらを使っていきましょう。
7-2. MTXユニット組み合わせ最適化への適用
では、タブーサーチをMTXユニット組み合わせ最適化に適用していきます。前章で示したアルゴリズムを実行するために決定すべき要素は以下の通りです。
- 解の形式と初期解
- 解の評価方法と「良い解」の定義
- ある解に対する近傍解の作成方法
- その他、探索用ハイパーパラメータ
順番に見ていきましょう。
7-2-1. 解の形式と初期解
始めに、解の形式を決定します。今回の場合、「各メンバー39人がどのようにユニット分けされたか」がわかる形式にする必要があります。実は記事中で何度か出てきているのですが、以下のような形式とします。
{
（ユニット識別子）：\[メンバーのリスト\],
（ユニット識別子）：\[メンバーのリスト\],
...
}
※実は実装では一部違う形式を使用したりしていますが、本記事では見やすさを優先してこのように表示します。気になる方はコードをご覧ください。
初期解についてですが、今回は完全ランダムに作ることにしましょう。問題設定によっては、初期解を丁寧に作ることで探索の収束を大幅に早められることもあるようですが、今回の規模ではまあランダムで良いでしょう。
再掲ですが、以下に初期解の一例を示しておきます。
(2, 0) ['桜守歌織', '馬場このみ'] (2, 1) ['伊吹翼', '天空橋朋花'] (2, 2) ['松田亜利沙', '豊川風花'] (3, 0) ['七尾百合子', '宮尾美也', '北沢志保'] (3, 1) ['高坂海美', '大神環', '望月杏奈'] (3, 2) ['ジュリア', '真壁瑞希', '篠宮可憐'] (3, 3) ['野々原茜', '田中琴葉', '舞浜歩'] (4, 0) ['ロコ', '徳川まつり', '福田のり子', '横山奈緒'] (4, 1) ['木下ひなた', '矢吹可奈', '春日未来', '所恵美'] (4, 2) ['最上静香', '北上麗花', '二階堂千鶴', '百瀬莉緒'] (4, 3) ['箱崎星梨花', '佐竹美奈子', '島原エレナ', 'エミリー'] (5, 0) ['周防桃子', '高山紗代子', '永吉昴', '白石紬', '中谷育']
7-2-2. 解の評価方法と「良い解」の定義
解の評価方法は、「準備」 > 「組み合わせ評価値の定義」で既に定義しています。繰り返しになりますが、例えば先ほどの初期解の評価値は1236.6676321841906となります。
また、ここまでの説明で自明かと思いますが、「良い解」は「評価値が小さい解」とします。
7-2-3. ある解に対する近傍解の作成方法
こちらは、
- 元の解のあるメンバーをランダムに1人選択する
- 1.の所属ユニット以外のユニットからメンバーをランダムに1人選択する
- 1.と2.で選択したメンバーの所属ユニットを入れ替えて得られる解を近傍解とする
とします。
ただし、探索の収束を早めるために少し工夫しています。具体的には1.のランダム選択は完全ランダムではなく、元の解における各メンバーの「個人ペナルティ値」の大きさに応じて選択確率に傾斜をつけています。何故かというと、「個人ペナルティ値」が大きいメンバーほど、入れ替えによって別のユニットに移ることでそのメンバー及び元ユニットの別メンバーの個人ペナルティ値が減少し、ひいては解の評価値が減少する可能性が高いからです。ただし、反対に2.で選ばれる確率には傾斜をつけないことで解遷移の多様性を確保し、局所解に陥る可能性を低くしています。詳しくはコードをご覧ください。
7-2-4. その他、探索用ハイパーパラメータ
タブーサーチにおけるハイパーパラメータはそれぞれ以下のように設定しました。
- 探索ループ回数：5000回
- 1回のループで作成する近傍解の数：256個
- タブーリストのサイズ：16
つまりこの設定では、約1429穰通り（）の解のうち、重複を含めて延べ5000×256=128万通りの解しか評価値を確認しないということになります。ちなみに、探索時間は私のノートパソコンで約8分です。さすがに1秒に100万個の解を評価するマシンパワーはないですが、もし全探索で2700京年かかるのと遜色のない解が8分で得られるならば十分ですね。
8. 結果
上述した初期解サンプル00～04からそれぞれ探索をスタートして発見した最適解を掲載します。
最適解サンプル00 (2, 0) ['真壁瑞希', '豊川風花'] (2, 1) ['北沢志保', '福田のり子'] (2, 2) ['篠宮可憐', '春日未来'] (3, 0) ['北上麗花', '百瀬莉緒', '高坂海美'] (3, 1) ['箱崎星梨花', '中谷育', 'ジュリア'] (3, 2) ['高山紗代子', '桜守歌織', 'ロコ'] (3, 3) ['永吉昴', '佐竹美奈子', '宮尾美也'] (4, 0) ['野々原茜', '田中琴葉', '天空橋朋花', '横山奈緒'] (4, 1) ['エミリー', '望月杏奈', '所恵美', '馬場このみ'] (4, 2) ['最上静香', '矢吹可奈', '周防桃子', '島原エレナ'] (4, 3) ['徳川まつり', '木下ひなた', '七尾百合子', '白石紬'] (5, 0) ['二階堂千鶴', '松田亜利沙', '伊吹翼', '舞浜歩', '大神環'] 評価値:73.21418807356075
最適解サンプル01 (2, 0) ['真壁瑞希', '野々原茜'] (2, 1) ['天空橋朋花', '高坂海美'] (2, 2) ['豊川風花', '福田のり子'] (3, 0) ['中谷育', '宮尾美也', 'ジュリア'] (3, 1) ['北上麗花', '徳川まつり', 'ロコ'] (3, 2) ['田中琴葉', '木下ひなた', '永吉昴'] (3, 3) ['百瀬莉緒', '箱崎星梨花', '高山紗代子'] (4, 0) ['北沢志保', '篠宮可憐', '七尾百合子', '横山奈緒'] (4, 1) ['島原エレナ', '周防桃子', '矢吹可奈', '最上静香'] (4, 2) ['馬場このみ', '望月杏奈', '所恵美', 'エミリー'] (4, 3) ['松田亜利沙', '二階堂千鶴', '白石紬', '伊吹翼'] (5, 0) ['春日未来', '舞浜歩', '佐竹美奈子', '桜守歌織', '大神環'] 評価値:76.3118842498055
最適解サンプル02 (2, 0) ['七尾百合子', '野々原茜'] (2, 1) ['高坂海美', '篠宮可憐'] (2, 2) ['松田亜利沙', '二階堂千鶴'] (3, 0) ['豊川風花', '真壁瑞希', '福田のり子'] (3, 1) ['舞浜歩', '桜守歌織', '佐竹美奈子'] (3, 2) ['春日未来', '木下ひなた', '永吉昴'] (3, 3) ['北上麗花', 'ロコ', '徳川まつり'] (4, 0) ['矢吹可奈', '周防桃子', '島原エレナ', '最上静香'] (4, 1) ['北沢志保', '宮尾美也', '横山奈緒', '天空橋朋花'] (4, 2) ['白石紬', '高山紗代子', '大神環', '伊吹翼'] (4, 3) ['望月杏奈', '馬場このみ', 'エミリー', '所恵美'] (5, 0) ['田中琴葉', '中谷育', '箱崎星梨花', '百瀬莉緒', 'ジュリア'] 評価値:73.84226692687639
最適解サンプル03 (2, 0) ['天空橋朋花', '春日未来'] (2, 1) ['木下ひなた', '永吉昴'] (2, 2) ['佐竹美奈子', '豊川風花'] (3, 0) ['所恵美', 'エミリー', '馬場このみ'] (3, 1) ['ロコ', '桜守歌織', '高山紗代子'] (3, 2) ['舞浜歩', '望月杏奈', '徳川まつり'] (3, 3) ['百瀬莉緒', '北上麗花', '高坂海美'] (4, 0) ['矢吹可奈', '島原エレナ', '周防桃子', '最上静香'] (4, 1) ['二階堂千鶴', '伊吹翼', '白石紬', '松田亜利沙'] (4, 2) ['田中琴葉', 'ジュリア', '中谷育', '箱崎星梨花'] (4, 3) ['宮尾美也', '福田のり子', '野々原茜', '真壁瑞希'] (5, 0) ['横山奈緒', '北沢志保', '大神環', '篠宮可憐', '七尾百合子'] 評価値:75.74277516070342
最適解サンプル04 (2, 0) ['二階堂千鶴', '望月杏奈'] (2, 1) ['矢吹可奈', '箱崎星梨花'] (2, 2) ['周防桃子', '篠宮可憐'] (3, 0) ['馬場このみ', 'エミリー', '所恵美'] (3, 1) ['北上麗花', '高坂海美', '百瀬莉緒'] (3, 2) ['桜守歌織', '佐竹美奈子', '舞浜歩'] (3, 3) ['七尾百合子', '北沢志保', '木下ひなた'] (4, 0) ['宮尾美也', 'ジュリア', '真壁瑞希', '中谷育'] (4, 1) ['徳川まつり', '横山奈緒', '野々原茜', '天空橋朋花'] (4, 2) ['大神環', '高山紗代子', '白石紬', '伊吹翼'] (4, 3) ['永吉昴', '島原エレナ', '春日未来', '松田亜利沙'] (5, 0) ['豊川風花', '最上静香', '福田のり子', 'ロコ', '田中琴葉'] 評価値:78.79260589698794
評価値で見ると、今回の5回の探索から得られた最適解はサンプル00の組み合わせということになります。もちろん、前述の通りすべての組み合わせを評価しているわけではないので00より評価値が良い解もあるかもしれません（ある可能性が高いです）。しかし、結果を眺めてみると00～04のどの組み合わせもなかなか「斬新」ではないでしょうか。このように、「厳密な解ではなくても『ある程度求めている解』を短い時間で得たい」という場合にヒューリスティクスは有効といえます。
それはそうと、スポ食が反映されていないせいで美奈子と歩の組み合わせが出てきていますね。申し訳ない…そのうちやり直します…
8-1. 探索の推移
サンプル00の探索の推移を評価値で見てみましょう。
このように、最適解は保存しつつ現在解は改悪の方向にも遷移することで局所解に陥ることを防いでいます。
8-2. 個人ペナルティ値
最適解サンプル00の個人ペナルティ値も見てみましょう。
少し見づらくて申し訳ないですが、左の軸が個人ペナルティ値（青色の棒グラフ）、右の軸が今回の所属ユニットの人数（緑色のプロット）に対応しています。
個人関係ペナルティ値が0となったのは17人、そのうち個人ペナルティ値すべてが0となったのは15人という結果でした。
また、（絶対ではないですが）4人または5人ユニットに属するメンバーは個人関係ペナルティ値が0となりづらいことがわかります。これは当たり前で、属性曲による関係ペナルティ値があり、39人は必ず3属性のいずれかに属しているので、4人ユニットを作ると最低2人、5人ユニットを作ると最低3人は関係ペナルティ値が0より大きいメンバーが生じるからです。今回の設定では、属性曲を考慮に入れる時点で最低でも4人ユニットの数×2人+5人ユニットの数×3=11人はペナルティ値が0より大きくなってしまいます。 かの有名な鳩の巣原理（ロコが好きそう）から自明ですね。よく見ると、属性曲によるペナルティ値を防いだ結果として、得られた2人または3人ユニットでは全て属性が異なっていますね。探索はかなり最善を尽くしたのではないでしょうか。
ペナルティ値を「ユニット内の各メンバーとの関係評価値の『平均』」ではなく『最大値』とすると、得られる組み合わせ結果は変わってくるかもしれません。近傍探索において、元の解と近傍解で評価値が大きく変化するような設計は良しとされていないのであまり思わしい探索ができなくなるかもしれませんが、そのうち取り組んでみたいです。
9. おわりに
いかがだったでしょうか。あなたの担当が所属するユニットは斬新でしたか？
例えばロコに関して言うと、今回の設定では[紗代子と歌織さん]もしくは[まつり、麗花]と3人ユニットとなる結果が2パターンずつ出てきて面白かったです。初期値が違っていてもある程度同じ解に収束するのかもしれません。今回は掲載していませんが、未来と2人ユニットとなるパターンも現れがちでした。いずれの組み合わせも、CDでは全体曲以外では1回も同じ曲を歌っていないので、納得感のある結果ではないでしょうか。
逆に今後のライブやCDシリーズで今回提示されたユニットが観られたら、自信を持って「斬新！見たことない！」と叫べて楽しいかもしれません。ミリオンにはまだまだ無限の可能性がありますね。
本記事が面白かったら、ご感想を頂けると嬉しいです。
最後に、私が8th終了後この構想を思いついてから3か月にわたって様々な助言をしてくれた友人（私をミリオンに引き込んだ張本人）に感謝します。
皆様、お読みいただきありがとうございました。
