2024-02-04

数理最適化ソルバー SCIP を用いてあなたの理想のミリオン10th Act-4 セットリストをつくってみよう

1. はじめに
2. 先に結果の一例だけ
3. 使用した一次データについて
4. コードおよび二次データの置き場所
5. 背景： Act-4楽しみ
6. 目的：『理想』のセットリストを考えてみたい
7. 手法：数理最適化
8. 定式化の準備
- 8-1. 各楽曲の「披露期待ポイント」の定義
- 8-2. 最適化対象の最終候補曲の絞り込み
9. （制約条件以外の）定式化
10. 制約条件の定式化、実験
11. 最終結果とまとめ
12. おまけ
謝辞

1. はじめに

こんにちは。お久しぶりです。星島航です。おかげさまでミリオンを追い始めて3年ほど経ちました。変わらずロコを応援しています。ミリアニ、とても良かったですよね。

さて、今回は実に1年9か月ぶり、2本目の記事を書きました。~~研究者ならクビになっているペースですね。~~よろしくお願いします。

2. 先に結果の一例だけ

今回のタイトルは、

数理最適化ソルバーSCIPを用いてあなたの理想のミリオン10th Act-4 セットリストをつくってみよう

です。ここで早めに注釈を入れておく必要がありますが、この後に紹介するのは『私の理想』の一例です。そして、何なら出来上がったセットリストは私の理想にすらまだ少し遠いです。これからまだまだ改善の余地がありますが、公開することで「理想のセットリストとは？」という議論の下地にしていただければと思います。

前提として、以下の点を念頭においてご覧ください。

全体曲は別枠で考えているので入っていません
全曲フルサイズでの披露を想定し、1日あたり（全体曲を除き）27曲としています
- 今回の想定と一番形式が似ている（何が披露されるか予想しづらい、全曲フルサイズ）ミリオン7th Reburnの曲数を参考にしました
全曲（ASメンバーを除く）オリジナルメンバーでの披露を想定しています

では、前回記事同様、まずは最終結果を掲載します。

（サイズが小さくなってしまうので元画像リンク）

各列の説明は以下の通りです。

一番左の列の2つ1組の数値
- 「何日目の何曲目か」を表しています。
左から2列目
- 楽曲名です。
以降の39列
- 各キャストさんの楽曲披露タイミングを表しています。
- セルに記載されている3つの数値は、「その楽曲までを含めたその日の累計披露回数、（その楽曲までを含めた2日間の累計披露回数）；その楽曲の披露メンバー数」を表しています。

いかがでしょうか。良い悪いは色々なご意見があると思いますが、ここでは「数理最適化によってセットリストを作ると一例としてこんな感じになるよ」ということだけ伝わればよいかなと思います。

では、ここから上記のセットリストはどのような手順で作られたかをご説明していきます。

3. 使用した一次データについて

今回の取り組みにあたり、

ミリオンライブ！の楽曲の一覧および過去のライブ披露実績

のデータが必要でした。これらのデータは、music765plus様が運営されている『アイドルマスター楽曲メモ』に掲載されている情報を使用させていただきました。欲しい情報が全て掲載されており、大変助かりました。ありがとうございました。

4. コードおよび二次データの置き場所

こちらのリポジトリ

github.com

に置いておきました。コードは1つのJupyter Notebookファイルのみです。一応前回の反省を活かして少しだけ可読性にも気を使いましたが、まだ読みづらいと思います。使ってみたい人は頑張ってください。

今回もいくつかパラメータがあり、調整すると異なる結果が得られて面白いと思うので、実行環境がある方はcloneしてそれらのパラメータを調整して実行してください。その際は結果をTwit... Xで共有してくれると嬉しいです。

5. 背景： Act-4楽しみ

さて、いよいよミリオン10th Act-4が迫って来ましたね。

idolmaster-official.jp

なんといってもこの公演で特筆すべきは出演キャストです。Day1は32名、Day2はなんとミリオンスターズ39名全員参加！すごい。

このことが発表された時、みなさんは最初に何を考えたでしょうか。私は「Day2にMS全員いるということは、あの曲もこの曲も全部、オリジナルメンバーで聴けるかも！」でした。

常々「全楽曲、一度はオリジナルメンバーで披露して欲しい…」と思っている私にとってはまたとないチャンスです。普段の周年ライブ同様今回もASメンバーは不在なので完全なオリジナルメンバーが揃わない曲もありますが、それでもせめてMSメンバーが揃った状態での披露が観たい。

それに、Day2に目が行きがちですが、近年の周年ライブでは2日間でキャストを半分に分けて1日十数名の参加という形が定番となっていたことを考えるとDay1の32名も相当多いです。

そこで私は考えました。

「2日とも『全曲オリジナルメンバーでの披露』縛りでセットリストを作れるのでは…？」

と。

6. 目的：『理想』のセットリストを考えてみたい

思い立ったら、やってみましょう。

上記の背景も踏まえ、セットリストを作成してみます。

ただし、上記の通り「オリジナルメンバー縛り」だけで楽曲を並べるのはそれほど難しくありません。2日目はMSのキャストが全員いるので物理的にはASを含まない楽曲は全て可能ですし、1日目も32名でできる楽曲は相当数あります。

よって、もう少し考慮する事項を増やし、以下のように目的を定めます。

以下の条件を満たすセットリストを作成する
1. 全楽曲オリジナルメンバーでの披露縛り
  - 前述の通り、私の希望
2. 現実的である
  - 各キャストの楽曲披露回数に偏りがない
  - 各キャストの楽曲披露間隔に無理がない
  - 特定の楽曲同士の曲順が不自然でない（MTS Final曲など）
  - など
3. なるべく、披露が期待されている楽曲を多く含む
  - 盛り上がりを考慮して、ライブ後半に含んでいるとなお良い

あれ、急に難しくなりましたね。

7. 手法：数理最適化

先ほど「それほど難しくない」と書いたばかりですが、条件に「現実的である」を入れると一気に難易度が上がります。なぜなら、ミリオンはユニットが固定されていないからです。

これは私がミリオンの良いところだと思っている点であり、このおかげで色々な組合せでの楽曲が楽しめるのですが、今回挑戦する「全楽曲オリジナルメンバーでの披露縛り」とは非常に相性が悪いです。

なぜなら、ある楽曲をセットリストに加えると複数のキャストの楽曲披露回数が同時に増え、代わりに別の楽曲を取り除くとと別の複数のキャストの披露回数が同時に減り、…となるからです。セットリストに含めたい楽曲を選びつつキャスト全員のトータルの楽曲披露回数を調整するのがとても大変だということがイメージできるかと思います。これを人手で行うのはとても大変で、私にはちょっとできません。

しかし、私も一応エンジニアの端くれ。コンピュータと数学の力を借りてなんとかできないか…

…

あれ、よく見ると、これは組合せ最適化問題じゃないですか。そうです。みんな大好き（？）、数理最適化の出番です。

最適化問題とは、

設定された「制約条件」をすべて満たし、「目的関数」の値が最小（または最大）となる解（「変数」の集合）を求める問題

であり、その最適化問題を解くにあたりよく使われる手法として「メタヒューリスティクス」とともによく挙げられるのが「数理最適化」です。

両者にはそれぞれ特徴がありますが、ここでは割愛します。「数理最適化の方が厳密だが使うのがめんどくさい」くらいに思っておいてください。それぞれ一長一短であり、問題の大きさや複雑さによって使い分けられています。

前回の記事では「斬新なユニット組合せ」をメタヒューリスティクス（の一種であるタブーサーチ（を中途半端に改造した局所探索法））を使用して解きました。

wtr-hshjm.hatenablog.com

今回は「セットリスト作成」を（最適化問題の一種である）組合せ最適化問題と解釈し、数理最適化ソルバー SCIP を使用して解いていくことにします。

数理最適化を用いて課題を解決するには、課題を定式化する必要があります。

定式化に必要なのは、

定数
変数
制約条件
目的関数

の設定です。

今回のセットリスト作成問題に当てはめてみると、

定数 → 変数の定義および制約条件の表現に必要な値の集合
- ライブの日数、1日あたりの披露楽曲数、候補曲数、キャスト視点で必要な楽曲披露間隔などを用意する
変数 → 「あるセットリスト1つ」を表す1組の変数の集合
- 「具体的な値を持った変数の集合1つ」と「あるセットリスト1つ」が1対1に対応するように定義する
- 制約を表現しやすい形で定義すると良い
制約条件 → セットリストが満たすべき条件の集合
- 変数同士もしくは変数と定数の関係式で表現する
目的関数 → 「どのようなセットリストが『理想』のセットリストであるか」を表す関数
- より『理想』に近いセットリストを表す変数の集合を入力すればするほど出力が大きく（もしくは小さく）なるような関数を、変数および定数を用いて定義する

となります。

文字だけの説明だとイメージしにくいかもしれませんが、定式化、実験の章で図をたくさん使って詳しく説明します。

さて、早速実際にこの課題を定式化していきましょう…と言いたいところですが、ちょっと待ってください。

定式化の経験がある方であれば、もうこの時点で変数の置き方は何パターンかイメージができていると思います。

しかし、現時点では目的関数＝「どのようなセットリストが『理想』のセットリストであるか」自体が定まっていません。

そして、実は変数の定義に必要な「候補曲数」も定まっていません。

次章ではまず、これらを定めるために必要な材料集めをしていきましょう。

8. 定式化の準備

8-1. 各楽曲の「披露期待ポイント」の定義

ところで、「目的」に何気なく書いた「披露が期待されている楽曲」ってどのような楽曲でしょうか。

もちろん人によって違うと思いますが、もし楽曲ごとに「この楽曲が披露されれば○○ポイント」のような数値があれば、目的関数を「セットリスト全体で披露される楽曲のポイントの合計値」のように定義することができます。

まずは各楽曲に対する「Act-4での披露を期待されている度合い」を定量化してみましょう。

（ここからは私の願望が強く反映されているので、心の中で突っ込みでも入れながらお読みください。Notebookでは各種パラメータを調整できるように作ってあるので、異なる考えをお持ちの方はパラメータを変更して遊んでみてください。）

私がAct-4で披露を期待する楽曲については、以下のように整理できます。

楽曲のオリジナルメンバーにおけるMSメンバーの割合が高い楽曲ほど優先してほしい
楽曲の新旧に関わらず、キャストによって披露されていない曲はまず最優先とし、しばらく披露されていない楽曲も優先してほしい
以下の条件に合致する楽曲ほど優先してほしい
- 周年ライブで披露されていない
- オリジナルメンバーで披露されていない
- オリジナルかつフルサイズ（Remixやショートバージョンではない）音源で披露されていない

これらの希望を反映させる形で、全ての楽曲 $u$ に対する「披露期待ポイント $e_{u}$ 」を以下のように定義します。

$\displaystyle e_{u} = r_{u} \times \{ a - \max_{v \in W_{u}}(n_{uv} \times b_{uv} \times o_{uv} \times z_{uv}) \}$

ここで、

$r_{u}$ : 楽曲 $u$ のオリジナルメンバーにおけるMSメンバーの割合
$a$ : 現在の周年数(=10)
$W_{u}$ : 楽曲 $u$ の過去に行われた全ての（キャストによる）披露 $v$ に関する情報の集合（MRなどは含まない）
$n_{uv}$ : 楽曲 $u$ の披露 $v$ が行われた周年期間を表す数値（例：「8周年ライブ初日～9周年ライブ初日の前日」の間の披露の場合、8）
$b_{uv}$ : 楽曲 $u$ の披露 $v$ が周年ライブでの披露だった場合1、そうでなかった場合0.5
: 楽曲の披露が（MSの）オリジナルメンバー全員を含む披露だった場合1、そうでなかった場合0.5
- ただし、楽曲のオリジナルメンバーが7人以上の場合は（揃うのが難しいので）常に1とする
$z_{uv}$ : 楽曲 $u$ の披露 $v$ がオリジナル音源かつフルサイズでの披露だった場合1、そうでなかった場合0.5

とします。

（定式化の方で使いたい文字を避けたため内容と関連のない文字だらけになってしまっています。分かりにくくてすみません。）

また、「オリジナルメンバー」について、基本的には初出のオリジナル音源の歌唱メンバーとしていますが、以下の楽曲については記載の通りとしています。

『アイル』：Harmonized ver.（Machicoさん、阿部里果さん、愛美さん）とする
『リフレインキス』：Brand New Ver.（種田梨沙さん、村川梨衣さん、上田麗奈さん、雨宮天さん）とする
LTFチーム曲：Brand New Ver.（南早紀さん、香里有佐さんを含む）とする
MTG属性曲：音源歌唱メンバーに加え、各属性のMSのメンバー全員を含む
MTS Finalチーム曲：音源歌唱メンバーに加え、各チームのダンスメンバー全員を含む

なお、 $W_{u} = \emptyset$ 、つまり楽曲 $u$ が過去に一度もキャストによって披露されていない場合、 $e_{u} = r_{u} \times 10$ とします。

式に文字がたくさん出てややこしそうですが計算自体は簡単です。例えば『dans l'obscurité』の場合、過去6回の披露機会がありますが、maxの中身が最大となる披露機会は8thライブでの披露で、 $8 \times 1 \times 0.5 \times 1 = 4$ （8周年期間、周年ライブ、メンバー揃っていない、オリジナルフル音源）となります。

直近の披露であるMOIW2023は $9 \times 0.5 \times 0.5 \times 1 = 2.25$ （9周年期間、周年ライブでない、メンバー揃っていない、オリジナルフル音源）となり、8thライブの値よりも小さくなるので、必ずしも直近の披露が計算対象となるわけではないことに注意してください。

Chrono-Lexicaはメンバー5人中5人がMSメンバーであるので、 $u=$ dans l'obscuritéについて、 $e_{u} = 5/5 \times (10 - 4) = 6$ ポイントとなります。

他にもいくつか例を出すと、10th Act-1で待望の（MS）オリジナルメンバーで披露された『ココロがかえる場所』は $e_{u} = 3/4 \times (10 - 10) = 0$ ポイント、8周年期間にSEASON-@IR!!!!の配信・一部メンバーで披露された『産声とクラブ』は $e_{u} = 3/4 \times (10 - 2) = 6$ ポイントとなります。

この「披露期待ポイント $e_{u}$ 」を、2024/01/08時点で「ミリオンライブ！の楽曲」に掲載されている楽曲（+MILLION C@STING!!!の結果によって制作および歌唱メンバーが決定している楽曲）全338曲（※）について計算しました。

※以下の楽曲を取り除いた曲数です。

バージョン違い（ソロバージョンなど）
- オリジナル縛りなので。
Remix
- 同上。
ZWEIGLANZの楽曲
- 多分やらないと思うので。
合同曲、スタマス、ポプマス、MOIW・アイラブ歌合戦楽曲
- 多分やらないと思うので。
- ただし『VOY@GER』は~~私が聴きたいので~~MS 3人だけのバージョンの音源があるので残しました。

計算式については異論もあるかと思いますが、これでひとまず全楽曲について「どの程度披露が期待されているか」を定量化することができました。

8-2. 最適化対象の最終候補曲の絞り込み

次に、前述の338曲の中からさらに以下の楽曲を除外します。

全体曲15曲
- 具体的には、周年曲11曲、『DIAMOND DAYS』、『EVERYDAY STARS!!』、『Rat A Tat!!!』、『セブンカウント』
- 理由は少し長くなるので後述。
ラジオ曲4曲、カバー曲1曲（『IGNITE』）
- やらないと思うので。~~先ほど取り除かなかった理由は、途中で気が変わったからです。~~
（MSソロ曲以外で、）ASメンバーを除くとオリジナルメンバーが1人以下となる楽曲
- 具体的には、LTD曲のうちASとMSのペアである楽曲、ASのMTG曲、ASのソロ曲、『World Changer』
- 理由は、今回のコンセプトである「オリジナルメンバー縛り」を適用すると不可能もしくはソロ披露となってしまうためです。
互いにメンバーが完全一致する楽曲のうち、披露期待ポイントが一番高い楽曲以外の楽曲
- 具体的には、ソロ曲やMTG, MTWの曲は同じメンバーで複数曲が存在するので、それぞれ1曲に絞ります。
  - 例①：（キャストで書いて、）メンバーが「中村温姫さん」である楽曲は4曲ありますが、そのうち披露期待ポイントが最も高いのは4点の『STEREOPHONIC ISOTONIC』であるので、それ以外の3曲を除外します。
  - 例②：メンバーが「中村温姫さん、戸田めぐみさん、斉藤佑圭さん、渡部恵子さん」である楽曲は『月曜日のクリームソーダ』、『I did+I will』の2曲ありますが、（どちらも披露期待ポイントが4点なので五十音順で早い）『I did+I will』を残し、『月曜日のクリームソーダ』を除外します。最適化の都合上片方のみを残しましたが、今回は楽曲の長さは考慮していないので、得点が同じ場合は最適化結果を見るときに入れ替えても大丈夫です（？）。
- 理由は単純に、2曲あるユニットの楽曲をAct-4だけで2曲やることはないと思うからです。ソロも同様です。もしあったらすみません。

全体曲について書いておきます。

冒頭の結果でも言及した通り、全体曲はセットリスト作成の対象から除外します。

理由は、今回の取り組みではキャストごとの披露曲数や披露間隔を考慮します（後述）が、全体曲は「全キャストが同じ披露タイミングで披露する」ということを考えると、

披露によって曲数は全員一律に増える
間隔は誰かが2曲連続（全体曲→個別曲、もしくはその逆）となってしまうことが避けられない

ので、最適化対象に含めて披露曲順を考慮することにあまり意味というか関心がないからです（MCのタイミングまで考慮すると意味が出てきますが、Act-4はMCほとんど無いだろうと想定しています）。そもそも曲順は大体1曲目、アンコール前ラスト、アンコール数曲、と決まっていますし。

「どの全体曲が披露されるか」は気になるところですが、~~披露期待ポイントをもとに考えると『Welcome!!』が最有力候補です~~ まあそれは置いておきましょう。

決して今回のAct-4で全体曲が披露されないと予想しているわけではなく（そんなことあり得ないですね）、あくまで最適化の対象からは外すということでご了承ください。

以上の処理により、最適化対象である最終候補曲が決定しました。残った楽曲数は176曲です。

これら176曲を「五十音順」および「披露期待ポイント（同率の場合は五十音）順」に並べた結果をこちらに出力しているので、ご興味のある方はご覧ください。

これで、定式化の準備が完了しました。

9. （制約条件以外の）定式化

では、早速定式化をしていきましょう。

おさらいですが、定式化には

定数
変数
制約条件
目的関数

が必要です。

なお、「制約条件」については「実験」の章で1つずつ説明しながら加えていくことにします。その方がいろいろなセットリストをお見せできて面白いので。

それでは、文字がたくさん出てきますが頑張りましょう（？）。

9-1. 定数

まずは「どのようなセットリストを作るのか」を決定する定数を決めていきます。

定数は文字通り、一度定めたら最適化実行中は値が変わりません。今回は、（自明であるものも含め）以下のように定めました。

キャスト数：
- 嬉しいですね。
- キャスト識別子の集合を、とします。
  - 具体的には、キャスト識別子1は山崎はるかさん、2は田所あずささん、…を表しています。
ライブ日数：
- これは決定事項です。
- ライブ日数識別子の集合を、とします。
  - 自明ですが、識別子がそのまま何日目かを表しています。
1日あたりの（全体曲を除いた）披露楽曲数：
- プラス全体曲3曲で1日30曲を想定しています。
- 各日の披露曲順識別子の集合を、とします。
  - 自明ですが、識別子がそのまま曲順を表しています。
候補楽曲数：
- 「8. 定式化の準備」で決定した値です。
- 候補楽曲識別子の集合を、とします。
  - 具体的には、候補曲を期待ポイント順に並べたこちらをそのまま使用しており、識別子1は『Clover Days』、2は『Dual Style Idol』、…を表しています。
- キャスト識別子がメンバーに含まれている楽曲識別子の集合を、とします。
  - $S_m \subseteq S, \forall m \in C$
  - 例えば、中村温姫さん（キャスト識別子12）に着目すると、 $S_{12} = \lbrace 7, 21, 40, ..., 168, 176 \rbrace$ となります。
キャスト識別子の（全体曲以外の）合計楽曲披露数の下限、上限
- 両日参加のキャスト：,
  - 1日あたりの披露数は $a'_{m_{\min}} = 2$ , $a'_{m_{\max}} = 3$ 、つまり1日2～3曲、2日合計で5曲と設定します。
- Day2のみ参加のキャスト：,
  - 1日あたりの披露数は（当然） $a'_{m_{\min}} = 3$ , $a'_{m_{\max}} = 3$ 、つまりDay2で3曲です。
  - ただし、戸田めぐみさん（キャスト識別子21）は公式から「一部の楽曲のみ参加」とアナウンスがあるので、, とします。当然, です。
    - 出てくれるだけで嬉しいです。実際は全体曲のみの参加となるかもしれませんが、期待を込めて1としています。
各キャストに必要な、楽曲披露の間隔：
- 1曲披露したら、次の担当楽曲の披露まで最低3曲は間を空けなければいけない、という設定とします。

9-2. 変数

変数には、人間から見た分類として

決定変数
- 具体的にその値が解を決定する変数
補助変数
- 決定変数に複雑な制約条件を設定するために用意される変数

がありますが、今回の問題は単純なので（正確には、補助変数を使わなければ表現できないような複雑な制約条件を考えてないようにしているので）、決定変数のみが必要となります。

今回の決定変数は、「あるセットリスト1つ」を表す1組の変数の集合です。セットリストを表すには、どのように定義すればよいでしょうか。

ちょっと天下り式ですが、今回は $d \times p \times s$ 個のバイナリ変数（0か1のいずれかの値を取る変数） $x_{ijk}$ の集合 $\boldsymbol{x}$ を用いることにします。数式で書くと、

$\displaystyle x_{ijk} \in \lbrace 0, 1 \rbrace \\ \forall i \in D, \forall j \in P, \forall k \in S$

です。つまり、 $2 \times 27 \times 176 = 9504$ 個のバイナリ変数の集合で1つのセットリストを表すことになります。

「手法：数理最適化」で記載した

「具体的な値を持った変数の集合1つ」と「あるセットリスト1つ」が1対1に対応するように定義する

についてですが、今回は

$x_{ijk} = 1$ の場合、 $i$ 日目の $j$ 曲目に楽曲 $k$ が披露される
（つまり $x_{ijk} = 0$ の場合、 $i$ 日目の $j$ 曲目に楽曲 $k$ が披露されない）
（＋前提として後述の制約01が成り立つ）

というように変数をみることで、1組の $\boldsymbol{x}$ が1つのセットリストを表すようにします。

視覚化すると以下の通りとなります。

1つのマスが1つの $x_{ijk}$ を表しており、図全体が1つのセットリスト $\boldsymbol{x}$ を表しています。

上記の図1枚で、1日目の1曲目に楽曲識別子 $s-2$ の楽曲を、2曲目に識別子 $2$ の楽曲を、…2日目の $p$ 曲目（27曲目）に識別子 $1$ の楽曲を披露するような1つのセットリストを表しています。

もしかすると、鋭い方は「バイナリ変数ではなく整数変数（仮に $x'_{ik}$ とします）の集合を使って、『 $x'_{ik} = j$ の場合、 $i$ 日目の $j$ 曲目に楽曲 $k$ が披露される』とすれば、変数も少なくなるし良いのでは？」と考えたかもしれません。

もちろんそのように考えることも正しいです。1つのセットリストを表すような変数の定義の仕方は1通りではありません。

さらにいうと、確かに一部の制約条件（後述の制約06とか）の設定ではその方が都合が良いこともあります。

しかし、セットリストに加えたい（と多くの人が思うであろう）制約条件は、そのほとんどがバイナリ変数を使用した方が簡単に表現することができます。

後ほど説明する制約条件の定式化で、バイナリ変数の表現力の高さを楽しんでください。

9-3. 目的関数

さて、目的関数ですが、これがどんな関数とすべきかを改めて確認すると、

「どのようなセットリストが『理想』のセットリストであるか」を表す関数
- より『理想』に近いセットリストを表す変数の集合を入力すればするほど出力が大きく（もしくは小さく）なるような関数を、変数および定数を用いて定義する

です。

ここで、「各楽曲の「披露期待ポイント」の定義」で定義した「披露期待ポイント $e_{k}$ 」（ $k$ は候補曲識別子）を使いましょう。

前提として、披露期待ポイントはその楽曲の披露期待度が高いほど大きい値となるように設計しています。このことを考慮すると、一番最初に思いつくのは「セットリスト $\boldsymbol{x}$ に含まれた楽曲の披露期待ポイントの合計」を目的関数とし、その値が大きいほど『良い』セットリストとみなす、という問題設定です。

これを式で表すと、

$\displaystyle \sum\limits_{i \in D} \sum\limits_{j \in P} \sum\limits_{k \in S} e_{k} x_{ijk}$

となります。 $x_{ijk}$ は $i$ 日目の $j$ 曲目に楽曲 $k$ が披露される時に1となるので、セットリストのどこかで楽曲 $k$ が披露されていれば、 $e_{k}$ ポイントが加算されるようになっています。

しかし、単純にこれで良いでしょうか。もう少しだけ『理想』について考えてみましょう。

例えば、今まで完全未披露ながらDay2にメンバーが揃っており、今回多くの方が披露を期待しているであろう楽曲『Clover Days』。この曲が、もしDay2の（全体曲を除いて）1曲目や2曲目に披露されたらどう思うでしょうか。まあやってくれるだけ嬉しいですけどちょっと拍子抜けというか、できればトリに近いところで聴きたくないでしょうか。主観と言われればそれまでですが、私はそう思います。

これを一般化して、

披露期待ポイントが高い楽曲ほど、なるべく終盤に披露されてほしい

という要求を、目的関数に反映させていきましょう。

上記の要求を反映させるには、披露期待ポイントが高い楽曲がセットリストの各日の後半に配置されているセットリストほど値が大きくなるように目的関数を設計すれば良さそうです。

そこで、新たな定数 $h$ （1以上）を用意します。そして、目的関数の計算の際に、その楽曲が披露されているか否かだけでなく、その披露曲が何曲目に配置されているかによって楽曲の披露期待ポイントに $1$ ～ $h$ を掛けて和を取るようにしてみましょう。

式で表すと、

$\displaystyle \sum\limits_{i \in D} \sum\limits_{j \in P} \sum\limits_{k \in S} ((1 + (h-1)j / p) \times e_{k} x_{ijk})$

となります。

これは、例えば $h=2$ とすると、Day1, 2それぞれで、1曲目に披露される楽曲の披露期待ポイントを1.037倍、2曲目は1.074倍、…、27曲目は2.0倍にして足し合わせたものがそのセットリストの目的関数の値となります。

このように設定することで、「できるだけ披露期待ポイントが高い楽曲を後半に配置しているセットリスト」＝「目的関数の値が大きいセットリスト」＝「『良い』セットリスト」と判断されます。

まあ「披露期待ポイントが高い楽曲が後半にあるほど良いセットリストである」とは一概には言えないと思いますが、今回はこのような設定としたいと思います。

さあ、ようやく（制約条件以外の）準備が整いました。次章からいよいよセットリストを作っていきます。

10. 制約条件の定式化、実験

さて、「目的」に記載した、セットリストを作成するにあたっての条件をおさらいしましょう。

再掲：以下の条件を満たすセットリストを作成する
1. 全楽曲オリジナルメンバーでの披露縛り
  - 前述の通り、私の希望
2. 現実的である
  - 各キャストの楽曲披露回数に偏りがない
  - 各キャストの楽曲披露間隔に無理がない
  - 特定の楽曲同士の曲順が不自然でない（MTS Final曲など）
  - など
3. なるべく、披露が期待されている楽曲を多く含む
  - 盛り上がりを考慮して、ライブ後半に含んでいるとなお良い

まず1.についてですが、こちらは、常に満たされています。

今回の問題設定は「どの楽曲をいつ披露するか」です。「ある楽曲 $k$ が披露される場合、その披露は必ず（MSの）オリジナルメンバーによる披露」を前提としており、「どの楽曲を誰が歌うか」は最適化の対象ではありません。よって、この条件は問題設定の段階でクリアしています。

次に2.の前に3.について先に書くと、前節の「目的関数」の項で設定した目的関数によって実現されます。

本章の本題である2.については、各節で追加する制約条件で実現していきます。

さて、ここでさらっと大事なことを書くのですが、今回使用する数理最適化ソルバー SCIP は混合整数最適化問題に特化したソルバーです（説明には「非線形もいける」みたいなことも書いていますがおそらく求解性能は落ちると思います）。

「混合整数最適化問題」の定義を順を追って説明すると、

最適化問題：与えられた制約条件の下で目的関数の値を最小（もしくは最大）にする解を求める問題
- 線形最適化問題：目的関数が線形関数で、全ての制約条件が線形の等式または不等式で表された最適化問題
  - 組合せ最適化問題：線形最適化問題のうち、変数が離散的な値を持つ最適化問題
    - 混合整数最適化問題：組合せ最適化問題のうち、一部の変数が整数値のみをとる最適化問題

となっています。つまり、混合整数最適化問題は線形最適化問題の一部なので、SCIPを使用するためには

目的関数を線形関数で表さないといけない
全ての制約条件を線形の等式または不等式で表さないといけない

ということを守る必要があります。

ここでいう「線形」とは、変数とそれにかかる係数が1次の多項式で表現されること、つまり変数同士の掛け算や累乗などが含まれていない状態を指します。

後追いでの確認になってしまいますが、先ほど設定した目的関数

$\displaystyle \sum\limits_{i \in D} \sum\limits_{j \in P} \sum\limits_{k \in S} ((1 + (h-1)j / p) \times e_{k} x_{ijk})$

は、この条件を満たしているので大丈夫ですね（大丈夫なように設定したのですが）。

以降で設定していく制約条件についても、線形性を意識していきましょう。

10-1. 「制約01：ある日のある曲順では1曲のみが披露される」

「何を言っているんだ、当たり前じゃないか」と思われるかもしれませんが、今のところ決定変数 $\boldsymbol{x}$ の各要素 $x_{ijk}$ は

$x_{ijk} = 1$ の場合、 $i$ 日目の $j$ 曲目に楽曲 $k$ が披露される
（つまり $x_{ijk} = 0$ の場合、 $i$ 日目の $j$ 曲目に楽曲 $k$ が披露されない）

という前提しか置かれていません。つまり、変数に何の制約も掛けなければ、例えば

かつというセットリスト
- つまり「1日目の1曲目に楽曲識別子1の楽曲が披露される」かつ「1日目の1曲目に楽曲識別子2の楽曲が披露される」というセットリスト

が許されてしまいます。1つの披露枠で2曲やるなんて、そんなことは普通のライブではあり得ません。例えば、「2日目の5曲目は『フェスタ・イルミネーション × 鳥籠スクリプチュア BATTLE MIX』です」と言われるようなものです。え、他ブランドではあった…？知りませんね…

今回はこのような披露形式は考えないこととします。

もちろん、逆に「1日目の10曲目はどの楽曲も披露されない」というような事態も発生しないようにしたいです。

上記をまとめると、「ある日のある曲順では必ず1曲のみが披露される」という制約を設定する必要があります。

これを式で表すと、以下の通りとなります。

$\displaystyle \sum_{k \in S} x_{ijk} = 1 \\ \forall i \in D, \forall j \in P$

例として、 $i=1, j=1$ 、つまり1日目の1曲目の披露曲を1曲とする制約を可視化すると以下の通りとなります。

赤枠で囲まれた $s$ 個の決定変数 $x_{ijk}$ の合計が必ず1でなければいけない、という制約条件です。 $x_{ijk}$ は0か1しかとらないので、この合計が1ということは赤枠のうち1つの $x_{ijk}$ のみが1となっていることと同じことを意味します。線形性も問題ないですね。これを、全ての $(i, j)$ の組合せに対して課すのが制約01です。

では、一旦この制約01のみを課して、目的関数の値を最大化させるセットリストを作ってみましょう。どうなるか予想してみてください。

ちなみに、以降は断りがなければ解の最大探索時間を10分とします。つまり、10分探した中で、制約条件を全て満たし目的関数の値が最大となるセットリストが出力されるようします。

…

結果は以下の通りとなります。

（元画像リンク）

本記事冒頭でも見方を記載しましたが、改めて説明すると、

一番左の列の2つ1組の数値
- 「何日目の何曲目か」を表しています。
左から2列目
- 楽曲名です。
以降の39列
- 各キャストさんの楽曲披露タイミングを表しています。
- セルに記載されている3つの数値は、「その楽曲までを含めたその日の累計披露回数、（その楽曲までを含めた2日間の累計披露回数）；その楽曲の披露メンバー数」を表しています。

となります。

はい、『Clover Days』を2日間で54回披露するセットリストが出来上がりました。1秒で出来上がりました。目的関数の値は、820ポイントです！（ポイントはこちらのCSVの最終行で確認できます。）

…すみません、茶番でした（想定外の桁数で文字がセルを突き破ってますし…）。問題だらけのセットリストです。というかこれをセットリストというのも憚られます。

どうしてこうなってしまったのでしょうか。SCIPくんは強火のBlooming Cloverファンなのでしょうか。もちろんそうではありません。SCIPは言われた通りに制約条件を守り、言われた通りに目的関数の値が最大となるようにセットリストを組んだだけです。

そうです、明らかに制約条件が足りないからですね。

ここから、制約条件を少しずつ加えて記事冒頭に掲載した（まだ良さそうな）セットリストに近づけていきましょう。

10-2. 「制約02：すべての候補楽曲はAct-4を通じて1回以下だけ披露される」

（他にもあるかもしれませんが、）先ほどのセットリストを見て真っ先に思い浮かぶ問題点は、「同じ曲を何回も披露している」でしょう。これを防ぐように、「すべての候補楽曲はAct-4を通じて1回以下だけ披露される」という制約条件を設定しましょう。

これを式で表すと、以下の通りとなります。

$\displaystyle \sum_{i \in D} \sum_{j \in P} x_{ijk} \le 1 \\ \forall k \in S$

例として、 $k=1$ 、つまり楽曲識別子1の披露回数を1回以下とする制約を可視化すると以下の通りとなります。

赤枠で囲まれた $d \times p$ 個の決定変数の合計が必ず1以下でなければいけない、という制約条件です。1以下であるということは、1回披露されるか0回披露される（つまり披露されない）かに限定されるということです。線形性も問題ないですね。これを、全ての楽曲 $k$ に対して課すのが制約02です。

では、制約01～02を課して、目的関数の値を最大化させるセットリストを作ってみましょう。今回もどうなるか予想してみてください。

…

結果は以下の通りとなります。

（元画像リンク）

今回も1秒で出来上がりました。まあ1曲1回までの縛りが増えただけで、披露期待ポイントが高い順にセットリストの下から並べていくだけですからね。目的関数の値は626ポイントです。当然ですが、制約が増えているので前回と比べて下がりました。確認はこちらから。

さて、『Clover Days』54連続よりははるかにまともなセットリストができましたが、まだまだ突っ込みたいところは満載です。次は何を考えましょうか。

まずは物理的に可能なセットリストにしたいですよね。今回のセットリストでは、Day2のみ出演のキャストさんがメンバーに含まれている楽曲がDay1に入ってきてしまっています。本記事ではオリジナルメンバーでの披露縛りを前提としているので、このセットリストは受け入れられません。次の制約を考えましょう。

10-3. 「制約03：すべてのキャストは各日に設定された回数上下限を守って楽曲を披露する」

次の制約として、キャストさん視点での各日の披露曲数の上下限を設定しましょう。

ただ、決定変数 $x_{ijk}$ にはキャスト識別子は直接表れません。どうすればよいでしょうか。こちらは先に制約式と可視化の図を見て頂いた方がわかりやすいかもしれません。

$\displaystyle a_{m_{\min}} \le \sum_{i \in D} \sum_{j \in P} \sum_{k \in S_{m}} x_{ijk} \le a_{m_{\max}} \\ \forall m \in C$

「定数」の節で定義した通り、 $S_{m}$ はキャスト識別子 $m$ がオリジナルメンバーに含まれている楽曲の集合（ $S$ の部分集合）であり、これは既知の情報です。

よって、「キャスト識別子 $m$ が含まれている楽曲のうちセットリストに含まれている楽曲数」＝「キャスト識別子 $m$ の披露曲数」（全楽曲オリジナルメンバー披露縛りという前提があるのでイコールとなります）を表す上記の制約式の真ん中の値（図の赤枠の合計）は問題なく計算することができます。

そして、各キャストに対してはライブ全体での披露曲数の上下限を定数で設定しているので、赤枠の合計値がその上下限に収まっているという制約条件を設定することで、キャストの披露曲数に対する制約を掛けることができます。

（なお、これは制約01, 02が成立しているという前提を置く必要がありますが、数理最適化では「設定された制約が全て満たされるような解」のみを解とするので、このように他の制約条件の成立を前提として別の制約条件を設定できます。）

上記の図では一例として、楽曲識別子 $1, 4, 5, ..., s-1$ のオリジナルメンバーであるキャストに対してライブ全体の披露曲数の制約を掛ける際の合計値計算範囲を赤枠で示しています。

同じ原理で、赤枠の範囲を1日目もしくは2日目のみに限定して、その日・そのキャスト用の上下限設定値を使うことで、1日あたりの披露曲数の制約も掛けることができます。これにより、例えば「田所あずささんがメンバーに含まれている楽曲は1日目で合計0曲の披露とする」＝「田所あずささんが1日目不在である」という制約も表現できます。

なお、様々な思惑（？）により、「オリジナルメンバーが7人以上の楽曲」についてはMSメンバーが全員揃わなくてもDay1に披露可能としました。

では、制約01～03を課して、目的関数の値を最大化させるセットリストを作ってみましょう。ちなみに、この制約の追加によって、到達できる目的関数の最大値が自明ではなくなるため、10分では最適解が見つからなくなります。もともと選択肢自体は $2^{9504}$ と膨大ですからね。このあたりから人間視点での予想も難しくなってきます。

結果は以下の通りとなります。

（元画像リンク）

ひとまず、物理的に実行可能となりました。Day2のみ参加のキャストさんがオリジナルメンバーに含まれている楽曲は、Day1では披露されないセットリストになっています。また、各キャストさんの楽曲披露回数も、全キャストさんについて設定を守ることができています。かつ、披露期待ポイントが高い楽曲がたくさん含まれたセットリストにもなっています。目的関数の値は573ポイント（確認はこちら）。だいぶ良くなってきましたね。でももう少しキャストさんに配慮してみましょう。

10-4. 「制約04：すべてのキャストは設定された曲数以上に楽曲披露間隔が空いている」

「物理的に実行可能」とは言ったものの、全節の結果を見ると、キャストさんによっては楽曲披露間隔が狭い箇所があるのが気になります。

例えば、種田梨沙さんはDay2の20, 21, 23曲目に出番となっています。これは厳しい。キャストさんに良いパフォーマンスをしてもらうためにも、ある程度の披露曲同士の間隔は欲しいところです。

今回は、「1曲披露したら最低3曲は休める」という設定をしてみましょう（なぜ3曲かというと、3曲までなら後述の制約と共存しやすいからです）。

この制約条件はどのように式で表せばよいでしょうか。少しだけ考えてみてください。

…

答えは、以下の通りです。

$\displaystyle \sum_{l = 0}^{g} \sum_{k \in S_{m}} x_{i(j+l)k} \le 1 \\ \forall i \in D, \forall m \in C, \forall j \in P'$

ただし、空けたい間隔 $g = 3$ とし、 $P' = \lbrace 1, ..., p - g \rbrace$ とします。

可視化の図は以下の通りです。

各キャストについて「そのキャストがオリジナルメンバーに含まれている楽曲」を対象に合計を取る、という点は制約03と似ていますが、 $j$ 方向については全ての和ではなく、「開けたい間隔+1」の範囲の和となっています。具体的には、今回は3曲以上空けたいので、1～4曲目の和、ということになります（作図の都合上、図は「2曲以上空けたい」の場合となっていますがご了承ください）。

一見よくわからないかもしれませんが、少し考えてみましょう。自身が担当する楽曲について、1～4曲目の合計が1以下という制約を掛けることは、1～4曲目での出番を1回以下に抑えるということです。この「合計1回以下」という制約を、2～5曲目、3～6曲目、…24～27曲目の全てで設定すれば、1日を通して、どの出演箇所に着目しても出番と出番の間隔が3曲以上空くことが保証されます。

この制約を、全ての日付、全てのキャストさんについて設定すれば、全員の負担が抑えられたセットリストになります。

では、制約01～04を課して、目的関数の値を最大化させるセットリストを作ってみましょう。

結果は以下の通りとなります。

（元画像リンク）

期待通り、全キャストさんについて、日ごとに見ると出番と出番の間隔が3曲以上空いています。キャストさんの負担という観点では、結構良いセットリストになっているのではないでしょうか。ちなみに、目的関数の値は539ポイントです（確認はこちら）。

10-5. 「制約05：指定した2曲について披露される日付を一致させる」

さて、前節の結果を見ると、MTS Final楽曲4曲全てが1日目のセットリストに入ってきていますね。セットリストに入ってくること自体は、披露期待ポイントの観点からみると妥当です。ただ、条件によっては、4曲のうち1曲だけが披露がなかったり、1曲だけ2日目に披露されるようなセットリストが出力される可能性はあります。たまたま前節はそうなっていませんが、MTS Finalの楽曲はひとまとまりという印象が強い（主観です）ので、明示的に「披露されるのであれば同じ日に披露される」という制約を掛けておきたいところです。

「特定の楽曲2曲 $k_{1}$ , $k_{2}$ が披露されるか否かを各日付で一致させる」という制約条件は、以下のように表せます。

$\displaystyle \sum_{j \in P} x_{ijk_{1}} = \sum_{j \in P} x_{ijk_{2}} \\ \forall i \in D$

今までの制約条件と比べると簡単ですね。一応可視化の図も載せておきましょう。

図は、楽曲識別子 $1$ と $s-1$ について、1日目で披露されるか否かを一致させる（両方披露するか、両方披露しないか）制約条件を設定するために使用する変数の範囲を示しています。

3曲以上の複数曲について一致させたい場合は、1曲目と2曲目、2曲目と3曲目、…の全ての組合せに対して制約を掛ければ期待する結果が得られます。

では、制約01～05を課して、目的関数の値を最大化させるセットリストを作ってみましょう。制約05の対象は、

MTSチーム曲4曲
- 『ダイヤモンド・クラリティ』、『Shamrock Vivace』、『空色♡ Birthday Card』、『ESPADA』
MTS Final曲4曲
- 『サウンド・オブ・ビギニング』、『Supersonic Booster!』、『オレンジ・エピソード』、『Like twinkling STARS』

の2グループで、それぞれのグループに対して「同じ日に全曲披露する、もしくは1曲も披露しない」という制約を掛けます。

結果は以下の通りとなります。

（元画像リンク）

前節の時点でも偶然満たされてはいましたが、今回も期待通りに満たされていますね。目的関数の値は564ポイントです（確認はこちら）。

10-6. 「制約06：指定した2曲について披露順を指定する」

前節まででまあまあ良いセットリストになってきた気がしますが、まだ少し気になる点もあります。それは、特定の楽曲同士の披露順の前後関係です。

前節では偶然大丈夫でしたが、前々節の結果を見ると、Day2の24曲目がミリアニTeam6thの『Unknown Boxの開き方』、26曲目がTeam3rdの『オレンジノキオク』となっています。ちょっと気にならないでしょうか。

Act-3では、間に他の楽曲を挟みつつ、1日の中で楽曲披露順が1th→2nd→4th→5th→7th→8thのように、Teamの順番が守られていました。まあAct-3はアニメがテーマの公演であり、Act-4はそうではないのでそこまで気にしなくても良いかもしれませんが、今回もこれを踏襲するため、「特定の楽曲2曲 $k_{1}$ , $k_{2}$ について、どちらも同日に披露される場合は披露順の前後関係を指定する」という制約を設定してみましょう。

さて、この制約は今までと比べると少しだけ難しくなります。なぜなら、今までの制約で考えてきたような「決定変数そのものの足し算」だけでは「曲順」が表現できないからです。どうすればよいでしょうか。

結論としては、以下のような制約式となります。

$\displaystyle \sum_{j \in P} jx_{ijk_{1}} \le \sum_{j \in P} jx_{ijk_{2}} + p(1 - \sum_{j \in P} x_{ijk_{2}}) \\ \forall i \in D$

可視化の図は以下の通りとなります。

ちょっと難しいですね。ある日付に対して楽曲 $k_{1}$ , $k_{2}$ が披露されるか否かで場合分けして説明します。

楽曲 $k_{1}$ , $k_{2}$ がともに披露されない場合

制約式の左辺は0、右辺第1項も0、右辺第2項は $p$ となります。 $p$ は「1日あたりの披露曲数」なので正の整数です。よって、この制約式は常に成立します。

楽曲 $k_{1}$ のみが披露される場合

制約式の左辺は $x_{ijk_{1}}=1$ となる時の $j$ 、つまり $k_{1}$ の披露曲順なので1以上 $p$ 以下の値となります。そして、右辺第1項は0、右辺第2項は $p$ となります。よって、この制約式は常に成立します。

楽曲 $k_{2}$ のみが披露される場合

制約式の左辺は0、右辺第1項は $x_{ijk_{2}}=1$ となる時の $j$ 、つまり $k_{2}$ の披露曲順なので1以上 $p$ 以下の値となります。そして、右辺第2項は0となります。よって、この制約式は常に成立します。

楽曲 $k_{1}$ , $k_{2}$ がともに披露される場合

制約式の左辺は $k_{1}$ の披露曲順、右辺第1項は $k_{2}$ の披露曲順、右辺第2項は0となります。よって、この制約式を成立させるためには、 $k_{1}$ の披露曲順を $k_{2}$ の披露曲順より小さく（＝早く）する必要があります。

以上により、上記の制約式が今回の「指定した2曲について披露順を指定したい」という希望を叶えるために適切な制約条件であることが確認できました。

3曲以上の複数曲、例えば7曲について披露順を指定させたい場合は、楽曲1→楽曲2、楽曲1→楽曲3、…、楽曲1→楽曲7、楽曲2→楽曲3、…、楽曲6→楽曲7、というように、 ${}_{7} \mathrm{C}_{2}=21$ 通りの組合せに対して制約を掛ければ期待する結果が得られます。

ちょっと独り言ですが、この制約式はなかなかテクニカルで面白いですよね。

まず、ある日・ある楽曲の決定変数 $x_{ijk}$ 全てに対して $j$ との積の和を取ることで（ $x_{ijk}$ が1となるような $j$ はそのうち1つだけなので）その楽曲の披露曲順を取り出すことができる、というのは勉強になりました（『整数計画法による定式化入門』という資料を参考にしました）。

また、特定の条件、今回は「 $k_{1}$ , $k_{2}$ がともに披露される場合」にのみ制約を掛けたい場合に、大きな整数値（今回は $p$ ）を制約式に利用する方法も、「Big-M法」と呼ばれるテクニックの一つです（『定式化技法集』というサイトの該当ページを参考にしました）。私も教科書では読んだことがあったのですが、実問題の定式化で使用したのは初めてです。こちらも勉強になりました。

式の見た目は複雑ですが、 $j$ も $p$ も定数なので、制約式の線形性も保たれています。

では、制約01～06を課して、目的関数の値を最大化させるセットリストを作ってみましょう。制約06の対象は、

MTSチーム曲4曲
- 『ダイヤモンド・クラリティ』、『Shamrock Vivace』、『空色♡ Birthday Card』、『ESPADA』
MTS Final曲4曲
- 『サウンド・オブ・ビギニング』、『Supersonic Booster!』、『オレンジ・エピソード』、『Like twinkling STARS』
ミリアニチーム曲7曲
- 『Star Impression』、『海風とカスタネット』、『オレンジノキオク』、『catch my feeling』、『バトンタッチ』、『Unknown Boxの開き方』、『トワラー』、『REFRAIN REL@TION』

の3グループで、それぞれのグループ内に対して「同じ日に披露する場合は並びの通りに披露順を守る」という制約を掛けます。

結果は以下の通りとなります。

（元画像リンク）

前節の時点でも偶然満たされてはいましたが、今回も期待通りに満たされていますね。目的関数の値は560ポイントです（確認はこちら）。

10-7. 「制約07：指定した2曲について披露順を連続とする」

さて、出来上がるセットリストも（個人的には）かなり良くなってきたように思いますが、前節の結果で気になることはあるでしょうか。

ミリアニ曲は、2日目で14曲目『オレンジノキオク』(3rd)→15曲目『catch my feeling』(4th)→17曲目『バトンタッチ』(5th)→24曲目『Unknown Boxの開き方』(6th)となっており、いい感じだと思います。

ただ、1日目でMTS Final曲4曲は、1日目で12曲目『サウンド・オブ・ビギニング』、14曲目『Supersonic Booster!』、17曲目『オレンジ・エピソード』、22曲目『Like twinkling STARS』となっているのですが、順序は守られつつも披露順が離れているのはなんか変な感じがします。制約06で順序のみを指定したばかりで身もふたもないですが、MTS Final曲についてはさらに踏み込み、連続での披露となるようにしましょう。

この希望の実現のためには、「特定の楽曲2曲 $k_{1}$ , $k_{2}$ について、 $k_{1}$ が披露される場合は必ず次に $k_{2}$ が披露される」という制約を設定すればよいですね。

今回の制約式は簡単です。以下の通りとなります。

$\displaystyle x_{ijk_{1}} = x_{i(j+1)k_{2}} \\ \forall i \in D, \forall j \in P''$

ただし、 $P'' = \lbrace 1, ..., p - 1 \rbrace$ とします。

可視化の図は以下の通りとなります。

図では、「楽曲 $s-2$ が1曲目に披露される場合必ず楽曲 $2$ が2曲目に披露される、かつ楽曲 $s-2$ が1曲目に披露されない場合必ず楽曲 $2$ も2曲目に披露されない」という制約を表しています。これを、2, 3曲目、3, 4曲目…、26, 27曲目すべてに設定することで、「2つの楽曲は必ず連続でしか披露されない」を実現することができます。

3曲以上の複数曲を連続させたい場合は、1曲目と2曲目、2曲目と3曲目、…の全ての組合せに対して制約を掛ければ期待する結果が得られます。

では、制約01～07を課して、目的関数の値を最大化させるセットリストを作ってみましょう。制約07の対象は、

MTSチーム曲4曲
- 『ダイヤモンド・クラリティ』、『Shamrock Vivace』、『空色♡ Birthday Card』、『ESPADA』
MTS Final曲4曲
- 『サウンド・オブ・ビギニング』、『Supersonic Booster!』、『オレンジ・エピソード』、『Like twinkling STARS』

の2グループで、それぞれのグループに対して「4曲は連続で披露する、もしくは1曲も披露しない」という制約を掛けます。

結果は以下の通りとなります。

（元画像リンク）

期待通り、1日目で15曲目『サウンド・オブ・ビギニング』、16曲目『Supersonic Booster!』、17曲目『オレンジ・エピソード』、18曲目『Like twinkling STARS』と、4曲連続の披露となっていますね。

目的関数の値は558ポイントです（確認はこちら）。

以上で、本記事で用意した制約は全てとなります。お疲れさまでした。（ここまで読んでくれる方がいるのか不安ですが…）

11. 最終結果とまとめ

さて、前節では実験のため、1回のセットリスト作成の制限時間を10分に制限していました。しかし、当然10分では選択肢 $2^{9504}$ 個のセットリスト全ての目的関数を評価することはできません。というか何年かかるんでしょうね。おそらくSCIPは求解にランダム要素は入っておらず、理論上無限の時間があれば最適解を見つけるようにできているはずですが、実用上は時間を制限してその時間内に見つかった最も目的関数の値が良い解を出力させるように使うこととなります。

つまり、同じ定数・変数設定、制約条件、目的関数であれば、実行時間が長ければ長いほど目的関数の値が大きい＝『良い』セットリストが得られるはずです。

というわけで、前節の最後の設定、つまり制約01～07を課して、10分ではなく90分で実行してみましょう。

結果は以下の通りとなります。

（元画像リンク）

変わらずすべての制約が守られていますが、セットリストが変わりましたね。こちらのセットリストの目的関数の値は568ポイントです（確認はこちら）。やはり時間をかければかけるほど『良い』セットリストが得られるようです。

本記事では、一旦このセットリストを『理想』のセットリストとして終えようと思います。

…

さて、この最終的に得られたセットリスト、いかがでしょうか。まあ私が設定した制約は全て守られていて、かつ私が設定した目的関数の値が大きい解が出力されているのだから、少なくとも私にとっては『理想』のセットリストとなっているはず…なのですが、やはりまだ気になる部分はあります。いくつか思いつくままに列挙すると、

ソロ曲やるキャストさんとやらないキャストさんがいるけど、いいの？
- Act-3でもそうだったから…
Act-2でもやったけど、Act-4でもJus-2-MintとD/Zealやるの？
- な、なくはないかな…
MTV曲多過ぎない？
- 未披露曲の披露期待ポイントを高くしてるから…
（全体曲を除く）ラストがソロ曲で良いのか？
- なくはないかな…
『Sweet Sweet Soul』、つい最近東京ドームで観た。
- 披露期待ポイントの計算対象が直近の披露じゃない場合があるから…
そもそもこんなに一生懸命未披露曲を消化する必要ある？
- 披露期待ポイントと目的関数の設計には改善の余地があると思います…
ライブの後半に披露期待ポイントが高い曲が集中するのって本当にうれしい？
- うーん…
キャストさん視点で最低3曲空けるのはよいけど、例えばDay2の愛美さんは6曲目で出番が終わってたり、種田さんの最初の出番が18曲目だったり、もうちょっとバランス考えられない？
- それはそう…
なんか、大人数曲を入れて各キャストさんの披露曲数を底上げした上で、披露期待ポイントが高い曲を詰め込んで、曲数足りない人にソロを割り振って調整してるように見えない？それが『理想』でいいの？
- 見える。多分よくない（直球）。

という感じで、まだまだ『理想』とは程遠いです。

ただ、これは世の中の実課題を最適化問題として解こうとしたときにはよくあることで、上記の「気になる点」の中には「気になる点があるセットリスト」を見せられて初めて気づく点も多々ありました。これは、「実装→結果の確認→制約条件や目的関数が本当に適切なのかのフィードバック」のサイクルをたくさん回すしか解決方法はないし、それが最適化の面白いところでもあります。

この記事も、ある程度まで出来上がったセットリストを公開することで、「こういう条件はあった方が良いんじゃないか」「この制約はいらない」「メドレーありにして入れて曲数増やせ」「そもそもオリジナルメンバーで縛るな」などの議論が生まれることを期待して作成したものです。

なので、公開するNotebookで各種パラメータを変えて好きに使ってみてほしいですし、少しプログラミングができる方ならもっと根本から披露期待ポイントや目的関数の計算ルールを変更することもできると思います。あなたの『理想』のセットリストもぜひ見せてください。

12. おまけ

最後に私欲盛り盛りの、具体的には私が聴きたい曲を披露必須指定にしたセットリストを掲載しておきます。

曲名の最後に<req.>が付いている15曲が必須指定となっています。制約式の説明は割愛しますが、指定の曲について制約02の不等号を等号に変えればよいだけです。Notebookでは制約99として実装しています。使ってみてください。

これが本当の私の『理想』のセットリストです。180分も時間をかけました。なお目的関数の値は511。さすがに前節の最終結果の方が多くの人に支持を得られるセットリストでしょう。でも良いんです。これは『私の理想』ですから。

（元画像リンク）

最後までお読みいただきありがとうございました。

謝辞

本文中でも言及しましたが、music765plus様が運営されている『アイドルマスター楽曲メモ』は、データの使用だけでなくちょっとした調べ物の際もとてもお世話になりました。ありがとうございました。

また、今回も公開前に記事を読んでコメントをくれた友人に感謝します。

2024/02/05追記：

この記事を呟いたツイー…ポストを、数理最適化の梅谷先生にリポストしていただいたようです。ありがとうございます。おそらくX上で「数理最適化」などのワードを自動で拾うようにされているだけなのだとは思いますが、この記事が読まれている可能性もわずかにあるので動揺しました。私は梅谷先生が書かれた『しっかり学ぶ数理最適化』という本で数理最適化を勉強しており、この記事も最適化についての説明や文字の置き方など多大な影響を受けています。

www.kspub.co.jp

ミリオンが好きなみなさんも、この本で数理最適化を勉強して私と一緒にミリオン×数理最適化を流行らせていきましょう（？？？）。

2022-05-29

ミリオンライブ！架空のMTXシリーズの提案～タブーサーチを用いたユニット組み合わせ最適化～

1. 自己紹介
2. 先に結果の一例だけ
3. コードおよび使用したデータの置き場所
4. 背景
5. 目的
6. 準備
7. 手法：タブーサーチ
- 7-1. タブーサーチの概要
- 7-2. MTXユニット組み合わせ最適化への適用
8. 結果
- 8-1. 探索の推移
- 8-2. 個人ペナルティ値
9. おわりに

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を対象としています。

www.youtube.com

ただし、以下の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人を選ぶ、という考え方をすると、

$\displaystyle \begin{equation} \begin{split} & \prod_{k=1}^{3} \{ {}_{39 - 2(k-1)} \mathrm{C}_2 \} / 3! \\ \cdot & \prod_{k=1}^{4} \{ {}_{33 - 3(k-1)} \mathrm{C}_3 \} / 4! \\ \cdot & \prod_{k=1}^{4} \{ {}_{21 - 4(k-1)} \mathrm{C}_4 \} / 4! \\ \cdot & \prod_{k=1}^{1} \{ {}_{5 - 5(k-1)} \mathrm{C}_5 \} / 1! \\ \end{split} \end{equation}$

を計算すれば良さそうです。各行は、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. 手法：タブーサーチ

※ここからは最適化アルゴリズムのお話になります。結果だけ見たい方は読み飛ばしても大丈夫です。

上述の通り、いわゆる全探索を行い「すべての組み合わせのうち厳密に評価値が最小（＝最も斬新）となる組み合わせ」を得るのは現実的ではないことがわかりました。

では、現実的な量の探索で「評価値がなるべく最小に近い組み合わせ」を探す方法はないでしょうか。

あります。それが、ヒューリスティクス（発見的手法）です。

ja.wikipedia.org

本記事では、メタヒューリスティクス（ヒューリスティクスの中でも様々な問題に対応できるように設計されたもの）の1つである「タブーサーチ」というアルゴリズムを使用します。

ja.wikipedia.org

7-1. タブーサーチの概要

タブーサーチのアルゴリズムの流れについては、上記のWikipediaのページに非常にわかりやすく書いてあるので興味がある方は一度読んでみてください。ざっくりと流れを説明すると、

適当に初期解（＝現在解）を作成する
最適解を用意する（開始時は、＝現在解とする）
最適解と現在解の評価値を計算する
タブーリスト（この時点では要素0）を用意する
- タブーリストの1つの要素を何にすると効率的かについては様々な研究があるが、本記事では「（解その1→解その2）」の形とする
- リストの最大サイズを決定しておく（本記事では固定値とする）
以下を、期待する評価の解が得られるか設定した回数に達するまで繰り返す
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か月にわたって様々な助言をしてくれた友人（私をミリオンに引き込んだ張本人）に感謝します。

皆様、お読みいただきありがとうございました。