サブロウ丸

サブロウ丸

主にプログラミングと数学

flopt 仕様 v0.5.5: Solverサイド

本稿では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ソルバを用いる前にも用いられます。

関連記事

inarizuuuushi.hatenablog.com