サインコサインアルゴリズム
1. 序章
このチュートリアルでは、ごく最近のアルゴリズムである正弦-余弦アルゴリズムまたはSCAを見ていきます。
これは、母集団ベースのメタヒューリスティック手法のファミリーに属する最適化手順です。 これらの中で、それは数学ベースのアルゴリズムに属しています。
2.正弦-余弦アルゴリズム
SCAアルゴリズムは、2016年にSeyedaliMirjaliliによって提案されました。 これは、最適化問題に適用される人口ベースのメタヒューリスティックアルゴリズムです。
同じファミリに属するアルゴリズムに共通するように、最適化プロセスは、問題の近似を表す、検索空間内の母集団の個人の移動で構成されます。
この目的のために、SCAは三角関数の正弦関数と余弦関数を使用します。 計算の各ステップで、次の方程式に従って解を更新します。
一般に、上記の式は次のように組み合わされます。
ここで、は反復時の現在の個人を表し、は反復時の最良の個人の位置を示し、はランダムなパラメーターです。
SCAは後者のパラメーターを使用して、次善のソリューションへの閉じ込めを回避し、探索プロセスと活用プロセスのバランスを取ります。
- ソリューションの更新におけるシフトを、最良のソリューションに向けて（）またはそれを外側に向けて（）条件付けます。 特定の定数値からゼロまで直線的に減少します。
ここで、は定数、は現在の反復、は許可される最大反復を表します。 上記の方程式は、探査と開発の間のバランスを考慮に入れています。
- 範囲内の値を持ち、目的地に向かう、または目的地の外側へのソリューションの動きの大きさを決定します。
- 範囲内の値を持ち、宛先に重みを割り当てるために使用され、他のソリューションの更新プロセスに対する宛先ポイントの影響を強化または抑制します。
- の範囲の値を持つ、は、正弦関数と余弦関数の間のスイッチです。
3. 実際のSCA
SCAは、一連の初期ランダムソリューションから最適化手順を開始します。 達成された最良のソリューションは、他のソリューションを更新するために使用される宛先ポイント（ターゲット）になります。 SCAは、正弦関数と余弦関数の範囲を更新して、反復回数が増えるにつれて検索スペースの活用を維持します。 SCAは、反復回数が最大反復回数に達すると、最適化手順を停止します。
次の図は、プロセス全体を示しています。
3.1. 例：特徴選択
Belazzoug et al。は、SCAを使用してテキスト分類の機能を選択しました。
この問題の目的は、機能の最適なサブセットを見つけることです。 各ソリューションは固定サイズのベクトルで構成され、各次元は範囲内の各特徴の値をエンコードします。 0.5以上の値を持つ機能は、その選択を意味します。
各ソリューション（機能サブセット）の評価では、分類の精度と選択したサブセットのサイズの両方が考慮されます。 これは多目的最適化の例であり、目的は分類エラーとサブセットサイズの最小化です。
どこ：
- 機能の数に対するエラー率の相対的な重要性を表します。
- 分類のエラーです。
- 次元の現在のソリューションの特徴の数です。
- 機能の総数です。
この目的関数により、上の図で示した一般的な手順で各個人を評価できます。
もちろん、分類誤差の値を計算する必要があります。 Belazzougの研究の文脈では、この値は情報ゲイン（相互情報量）によって取得されます。これは、カテゴリ予測のために取得された情報のビット数を測定します。資料。
3.2. 数値計算
このセクションでは、SCAを使用した最適化の数値例を示します。 テストとしてよく使用される、実際の2変数関数6ハンプキャメル関数の最小値を見つけてみましょう。
この関数には、次の最小値があります。
使用する
4.探索vs. 搾取
一般的なすべての最適化アルゴリズム、特にメタヒューリスティックアルゴリズムに起こるように、 SCAソリューションの良さは、探索と活用の最適なバランスに依存します。 このバランス調整の方法を説明するために、次の図から始めます。これは、独立変数の間隔内の正弦と余弦に依存する2つの関数を表し、関数の値は次の範囲内にあります。
変数は、検索空間を定義する独立変数のセットを表します。
ご覧のとおり、曲線の上部と下部にある関数の値は、中央のセクションと比較して、ドメインの変動範囲がはるかに大きくなっています。 この事実により、次のヒューリスティックルールを述べることができます。
- 区間内の正弦関数と余弦関数の値については、SCAが問題空間内の多くの異なる点をテストするため、探索プロセスが優勢です。
- 範囲内の正弦関数と余弦関数の値については、悪用フェーズが優勢です。
5. SCAが機能するのはなぜですか？
SCAアルゴリズムの効率の理由は異なり、他のメタヒューリスティック手法に共通するものもあります。
- SCAは、並行探索現象の恩恵を受けるソリューションの母集団と連携します
- 範囲外の正弦関数と余弦関数の値について、解空間のいくつかの領域を同時に調査します
- 悪用プロセス中に、正弦値と余弦値が範囲内にある場合、SCAはいくつかの有望なソリューションを同時に調査します
- パラメータの適応値により、探索的プロセスと搾取的プロセスの間で有望な戦略と領域を転送できます
- 計算の特定の時点での最良の解は変数に保存され、問題のターゲットになるため、最適化フェーズで失われることはありません。
- 最適化プロセスは収束しています
6. 結論
このチュートリアルでは、正弦-余弦アルゴリズムを簡単に分析しました。 これは、メタヒューリスティック手法のファミリーに属する他の従来のアルゴリズムに関して独自の特性を持つ最適化手順です。
Seyedali Mirjaliliによる最初の提案から生じたアルゴリズムの変形を含む、多くの興味深い機能を省略しました。 これらのバリアントの分析はこのチュートリアルの範囲外ですが、読者にそれらを探索することをお勧めします。
