Algorithm

本ソルバーの最適化アルゴリズムは、「全手法で共通のアルゴリズム部分」と「各手法で異なるアルゴリズム部分」に分かれています。「全手法で共通のアルゴリズム部分」はカスタマイズできませんが、「各手法で異なるアルゴリズム部分」はカスタムマイズすることができます。また、本ソルバーでは、ペナルティ係数調整手法という名称で最適化手法を提供しています。

Common Algorithm

Algorithm of OptSolver

共通アルゴリズムは、下記のようなステップのアルゴリズムです。

1. 初期解の生成

num_to_select_init_answerで指定した数、ランダムな解を生成します。ランダムな解は、変数毎に上界/下界またはカテゴリ値からランダムに選択した値です。生成したランダムな解を各変数のスケールを正規化し、簡易的なアルゴリズムによって選択した解群間のユーグリッド距離の合計が最大となるようなround_times個の解群を初期解群として採用します。ただし、引数のinit_answersに初期解が設定されている場合は、ランダムな解を生成せずに、指定された初期解を利用します。

2. 最適化の実行

採用した初期解毎に最適化の実行します。また、このときn_jobs引数によって並列処理の実行を設定している場合は、初期解毎に並列処理が実行されます。全ての初期解に対する最適化が完了したら、返された最適化処理の結果から実行可能解がある場合はその中から最も目的関数の値が最も良い解を、実行可能解がない場合はその中から目的関数の値に制約違反ペナルティを加えた値が最も良い解を選択して、最適化の実行結果として返します。（制約違反ペナルティのペナルティ係数は、共通ではなく、各最適化処理内で決定している値を利用する。結果、フェアな比較ではないが、実行可能解がない場合の解は参考程度の解なので、現状このような仕様となっている。また今後、細かな結果など含めて最適化結果を返せるようなインタフェースを検討する予定です。。）

Algorithm of Optimizer

1. ペナルティ係数の調整

初期解（最適化試行）毎に、answer_num_to_tune_penaltyで指定した数、ランダムな解を生成します。ランダムな解は、変数毎に上界/下界またはカテゴリ値からランダムに選択した値とする。生成したランダムな解群から各制約式の違反量の違反量を計算し、「生成したランダムな解群における目的関数の最大値と最小値の差分のpenalty_strength倍」と「各制約式のペナルティスコア」が等しくなるような各制約式のペナルティ係数に調整します。

2. 初期解のスコア計算

初期解から目的関数の値と制約違反のペナルティの値を計算し、合算して初期解のスコアとして採用します。また、初期解を現状の最適解として採択します。

3. method.initialize_of_step実施

設定したmethodのinitialize_of_step関数を呼び出します。

4. method.propose実施

設定したmethodのpropose関数を呼び出し、解の遷移案を取得します。

5. 提案された解のスコア計算

解の遷移案を実行した場合のスコア（目的関数の値と制約違反のペナルティの値の合算）を計算します。

6. method.judge実施

設定したmethodのjudge関数を呼び出し、解の遷移を実施有無を決定します。解の遷移が決定した場合は、現状の解を遷移させる。

7. 最適性確認

6で解が遷移した場合は、新たな解の最適性の確認を行います。最適解は、実行可能解を優先し、その上でスコアが良い方を優先するように選択します。現状の最適解より良い場合は、最適解を変更します。

8. method.finalize_of_step実施

設定したmethodのfinalize_of_step実施関数を呼び出します。

9. 終了判定

3-8を繰り返した回数を計算する。methodで設定したsteps数に達した場合は、終了とし、現状の最適解を返す。達していない場合は、3に戻り、同様に処理を繰り返していきます。

Method

Penalty Adjustment Method

1. method.initialize_of_step

ステップ開始時の処理はありません。

2. method.propose

random_movement_rateの確率で、ランダム遷移を提案する。また、(1-random_movement_rate)の確率で、ペナルティが小さくなる遷移を提案します。 ランダム遷移を提案する時は、最適化問題内の1つの変数をランダムに選択し、上界から下界値またはカテゴリ値から1つの値を選択し、提案します。ただし、変数が数値かつデータ遷移履歴がhistory_value_size以上のデータ件数の場合は、対象変数のデータ遷移履歴値の平均値と標準偏差値を計算し、「平均値 - 標準偏差値 * range_std_rate」から「平均値 + 標準偏差値 * range_std_rate」までの値の範囲からランダムで値を選択して、提案します。またペナルティが小さくなる遷移を提案する時は、最適化問題内の1つの変数をランダムに選択し、その変数を動かすことでペナルティが減るような値を計算によって求め、提案します。また、ペナルティが最小になる複数の値が存在した場合は、その中からランダムに選択し、提案します。（＊この計算において、UserDefineConstraintは対象になりません。）

3. method.judge

スコアを比較し、現状の解より良い場合は遷移するという判定結果を、それ以外の場合は遷移しないという判定結果を返します。

4. method.finalize_of_step

「最後に解が遷移してから経過したStep数」と「最後にペナルティ係数を更新してから経過したStep数」を計算し、小さな方の値を採用し、その値がsteps_while_not_improve_score以上に達していたらペナルティ係数を調整します。 現状の解が実行可能解である場合は、ペナルティ係数に「現状の解のペナルティ違反量を正規化した値」と(1 + self._delta_penalty_rate)を積算し、ペナルティ係数をあげます。また、現状の解が実行可能解ではない場合は、一律にペナルティ係数に(1 - delta_penalty_rate)を積算し、ペナルティ係数を下げます。