組合せ最適化でチーム分けする（焼きなまし法） - Qiita
はじめに 前回の記事でチーム分けの問題を平均偏差最小化問題として定式化し、Python+PuLPで厳密に解く方法を紹介しました。その中で、組合せ最適化問題は問題が大規模になると厳密に解くことが難しくなることを述べました。 そこで、今回はPython＋simannealを使った焼きなまし法による近似解法を紹介します。 simannealとは simannealは焼きなまし法のためのパッケージです。 インストール方法 基本的な使い方 Annealerクラスのサブクラスを作成する。 move()をオーバーライドし、探索点の移動ルールを実装 energy()をオーバーライドし、目的関数を実装 作成したクラスのコンストラクタに初期解を与えて問題オブジェクトを作成する。 問題オブジェクト.anneal()で焼きなまし法を実行する。 問題オブジェクト.stateで解を取得する。 最適化問題の制約はmov
組合せ最適化でチーム分けする（平均偏差最小化） - Qiita
はじめに 組合せ最適化でチーム分けする で紹介されている問題を別のモデルで解いてみます。 この問題は、バラツキを最小化する組合せ最適化問題です。 バラツキ具合の指標としては一般的に分散がよく使われますが、分散は二次関数で表されるため一次関数を最小化する線形計画問題に比べると難しくなってしまいます。そこで元の記事では最大値と最小値の差（範囲）を最小化する線形計画問題として定式化しています。 一方、範囲の代わりに平均偏差を最小化する方法もあります。 そこで本記事では、まず範囲と平均偏差のモデルの違いを比較します。 最後に平均偏差最小化問題の例題をPython＋PuLPで解いてみます。 問題設定 前提条件 $n$人のメンバーを$m$個のチームに分ける。 各メンバーが持つコミュニケーション能力の種類は$l$個あり、それぞれ点数が振られている。 目標 チーム内で能力が偏らないようにする。 チーム間の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
