本稿ではfloptのSolverサイドであるソルバの話をします。 floptでは内部で実装されたアルゴリズムと外部ライブラリのソルバを用いて最適化を実行することができます。
Solver実装のキホン
最適化問題は (決定変数, 目的関数, 制約) から構成されており、floptのSystemサイドではユーザーが定義した問題からこの3つ組の情報を取り出します。 Solverはこの3つ組の情報を用いて求解します。 最もシンプルな実装であるRandomSearchを例にその内部を説明します。 RandomSearchはランダムサンプリングを繰り返すだけのアルゴリズムですね。
def search(self, solution, *args): for _ in range(int(self.n_trial)): # generate new solution solution.setRandom() # update best solution if needed self.registerSolution(solution) # execute callbacks self.callback([solution]) # check time limit self.raiseTimeoutIfNeeded() return SolverTerminateState.Normal
解の登録
Solutionオブジェクトにはユーザが定義した問題の変数のベクトル表現です。
まず、解をランダムサンプリングします。.setRandom()によりSolution内部の変数にランダムに値が割り振られます。
# generate new solution
solution.setRandom()
次に解の登録を行います。registerSolution内部ではもしローカルの暫定解よりもsolutionの方が良い目的関数値を持つならば、暫定解が更新されます。 また更新情報はsolver_logに格納され、アルゴリズム終了後にユーザーに提供されます。 もし複数の回を保存する設定であれば、上位k個の解が保存されます。
# update best solution if needed
self.registerSolution(solution)
コールバック関数の実行
次にコールバックの実行を行います。ユーザーがコールバック関数を設定していれば、その関数が実行されます。引数はそのフェイズにおける解のリストです。 このコールバックは何に使うのか、それはユーザーの工夫次第ですが、主には暫定解の取り出しや描写などに使用できます。 例えば、コールバックを用いた解の履歴の描写例がこのドキュメントページに記載されています。
ちなみに、なぜ解のリストにしているのかというと、群最適化の場合は最適化の最中に複数の解を管理するためそれに対応するためです。
# execute callbacks
self.callback([solution])
時間制限の確認
次に時間制限を超えていないかをチェックします。もしアルゴリズムの実行時間が実行時間を超えている場合はTimeoutErrorを発生させます。 Timeout例外はSolverのベースクラスでcatchされソルバの終了処理が行われます。
# check time limit
self.raiseTimeoutIfNeeded()
終了ステータス
ソルバの実行が終了したら、アルゴリズムの実行に応じた終了ステータスを返します。
SolverTerminateState
| state | 説明 |
|---|---|
| Normal | 正常終了 |
| Timelimit | 時間制限により終了 |
| Lowerbound | 目的関数値が指定した下限値を下回ったため終了 |
| Interrupt | ユーザーからの停止命令により終了 |
| Infeasible | 実行可能解なし |
| Unbounded | 非有界のため不能 |
| Abnormal | 異常終了 |
| Error | 何らかのエラー |
問題変換
外部ライブラリのソルバを実行する場合は、それに合わせた入力データに変換する必要があります。 例えばScipy.optimize.milpでMIP(混合整数線形計画法)を解こうとすると、ユーザーが不等式標準形で問題を表現し、そのときの制約行列とベクトルを関数に与える必要があります。そのためflopt.convertを用いて問題から線形計画の標準形のデータを取り出します。
# lp structure lp = LpStructure.fromFlopt( self.prob, x=solution.getVariables(), option="all_neq", )
この変換はCVXOPTソルバを用いる前にも用いられます。
