こんにちはやましんです。
今更ながらChatGPTのインパクトはすごいですねぇ。
もう、インターネットと同様に完全に依存しちゃってます。
先日、いつものように、主催する賞金付きのアイデアソンイベントのネタを検討するために、組合せ最適化問題の例題についてChatGPT-4に相談していたんですよ。
その内容がこちら
え？！あのChatGPT-4でも解けないの？？
なるほど、これが組合せ最適化問題の難しさなんだ。
この問題を刹那に解けるかチャレンジしてみよう！
問題定義
ChatGPT-4に相談していた問題は次のとおりです。
「1から50の数字の中から数字を最大1回ずつ選択して合計が500になる組み合わせをできるだけ見つける」
問題解決を急ぐの前に、組合せ最適化問題や量子アニーリングについて簡単に説明したいと思います。
もし、読むのが面倒、もっと詳しく簡単に知りたい方は、5/25(土)「アイデアソン：日常の組合せ最適化問題を解く！」というテーマで都内でイベントを実施するので、参加をご検討くださーい。
428lab.connpass.com
組合せ最適化問題ってなんだっけ？
一言でいうと「組合せ最適化問題は、いくつかの選択肢から最良の組み合わせを見つけ出す問題」です。
例えば、どんなものが組合せ最適化問題なの？
例えば、次の問題は「組合せ最適化問題」と言えるでしょう。
あなたが学校の遠足に持っていくおやつを次の中から選ぶ状況を考えてみましょう。
※実在のお菓子とは一切関係ありません（コンプラ対応💦）
おやつの予算が500円と決まっている場合、その範囲内で最も満足できる組み合わせを選ぶことが目標です。
満足できるためのルールを次のようにしましょう。
- 予算（500円）をできるだけ使い切る
- 銘柄の重複なくお菓子をできるだけ多く選ぶ
- 同じカテゴリーのお菓子を選ばない
では、順を追ってルールを適用していきます。
３つのルール順に適用すると
３つのルールを左から順に適用すると、次のようなお菓子選択になりますね。
- 予算（500円）をできるだけ使い切る：左端表のように、5つの銘柄のお菓子を選択すると合計500円となり、ルールを満足させることができますね。
- さらに、銘柄の重複なくお菓子をできるだけ多く選ぶ：中央表のように、6つの銘柄のお菓子を選択できますが、合計額は490円となっちゃいました。
- 最後に、同じカテゴリーのお菓子を選ばない：右端表のように選択すると、同じカテゴリーのお菓子はなくなりますね。その代わり、銘柄は５種類になり、合計額は450円になりました。
この例は、お菓子の選択肢の中から満足のいく組み合わせを見つけ出す問題なので、立派な（？）組合せ最適化問題と言えるね。
上述のようなロジックで、遠足に持っていくおやつを選択している人がいるとすれば、将来科学者になることを期待できるんじゃないかな。
遠足のおやつの例では、選択に失敗しても、友達とおやつを交換することで、むしろ、楽しい時間を過ごせるかもね。
日常に組合せ最適化問題はたくさん転がっていて、遠足のおやつと比較して、もっともっと選択肢が多く、選択に失敗すると時間を無駄にしたり、お金を失ったりするものもあるんだよね。
著者は、数十年前の人類は、そういった問題について、組合せ数が爆発することが分かっていたので、思考することをあきらめていたんじゃないかなと思うのです。
そこで登場するのが量子アニーリングです。
日本生まれ、カナダ育ち
ググれば（ジピれば）多くの情報があるけど、その歴史は古く、1998年に東京工業大学の門脇正史氏と西森秀稔氏によって提案され、2011年に量子アニーリングを実行する商用ハードウェアD-Wave（カナダ）が発表されたんです。
量子の振る舞いを利用した、量子コンピューターの一種なんだけど、押さえておきたいのは、組合せ最適化問題を解くことに特化したマシンなのです。
動作原理なんか詳しく知りたい人は、量子アニーリングイベントに参加してみてね。
では、そろそろ本題に入りましょう。
問題
「1から50の数字の中から数字を最大1回ずつ選択して合計が500になる組み合わせをできるだけ見つける」
この問題は、部分和問題（subset-sum problem）というそうです。
変数の定義
：対象となる数値の最大値
：目的とする合計値
：1から50数字の集合
：1のとき:数字
を選択したこと、0のとき:を選択しなかったことを意味する（バイナリ変数）
目的関数の定義
上述の問題の目的関数を定式化すると次のようになります。
QUBO作成
def _initialize_qubo(self):
"""初期化と目的関数の二次係数の計算"""
# QUBO行列を構築する
Q = np.zeros((self.N, self.N))
# 目的関数の二次項と線形項の計算
for i in range(self.N):
for j in range(self.N):
Q[i, j] = (i+1) * (j+1) * self.lam
# 目的関数の線形項を引く
linear_term = -1000 * np.arange(1, self.N+1) * self.lam
# 対角要素（線形項）に加算
np.fill_diagonal(Q, Q.diagonal() + linear_term)
return Q
出力例
下記は良い結果が得られた出力例です。Found exact solutionの行が合計500になる組合せ。
Found solution with deviationの行は、惜しかった組み合わせです。
量子アニーリングでは、正しい答えだけでなく、惜しい解が得られるのが面白い特徴といえます。
Found exact solution: [1, 2, 10, 17, 18, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 3, 8, 17, 18, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [1, 6, 14, 15, 17, 18, 20, 21, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [8, 9, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [1, 2, 6, 8, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [1, 2, 6, 8, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 14, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49]
Found exact solution: [3, 6, 8, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [5, 8, 17, 18, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [4, 8, 9, 15, 17, 18, 20, 21, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found exact solution: [2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49]
Found solution with deviation: [1, 14, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 3, 9, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [14, 17, 18, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [7, 8, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 14, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [15, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 14, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 9, 17, 18, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [8, 9, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [8, 14, 15, 17, 18, 20, 21, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [15, 17, 20, 21, 24, 25, 30, 33, 38, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [2, 6, 8, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 8, 9, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [2, 6, 8, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
Found solution with deviation: [1, 8, 9, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 6, 8, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 2, 14, 15, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [14, 17, 18, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 501
Found solution with deviation: [1, 3, 4, 8, 14, 17, 20, 21, 23, 24, 25, 30, 33, 42, 44, 46, 47, 48, 49] Sum: 499
github.com
最後まで読んでくれた方へ
- その後、ChatGPT-4と繰り返しチャットすることで、別のアルゴリズムを適用して、いくつかの組合せを出力してくれました。
- 実は、量子アニーリング方式で安定的に解を得られるパラメーターの探索に苦労しました。
