差分進化: 基礎と応用

By Fouad Sabry

微分進化とは

進化計算の分野において、DE とも呼ばれる微分進化は、候補の改善を繰り返し試みることによって問題を最適化する方法です。 特定の品質基準に関連したソリューション。 DE は「差分進化」という用語の略語です。 この種の手順は、対処されている問題についてほとんどまたはまったく仮定を行わず、潜在的な解決策の非常に広大な空間を検索できるため、通常はメタヒューリスティックと呼ばれます。 ただし、DE のようなメタヒューリスティックは、最適なソリューションが発見されることを保証するものではありません。

メリット

(I) 洞察と検証 以下のトピックについて説明します。

第 1 章: 差分進化

第 2 章: 人工蜂コロニー アルゴリズム

第 3 章: 進化計算

第 4 章: 進化戦略

第 5 章: CMA-ES

第 6 章: 遺伝的アルゴリズム

第 7 章: 並列コンピューティング

第 第 8 章: 多目的最適化

第 9 章: 制約付き最適化

第 10 章: 準ニュートン法

(II) 微分進化に関する一般のよくある質問に答える

(III) 多くの分野での差分進化を使用する実際の例。

(IV) 360 の各業界の 266 の新興テクノロジーを簡潔に説明する 17 の付録 - 程度の差分進化のテクノロジーを完全に理解している方。

本書の対象者

専門家、学部生、大学院生、愛好家、愛好家、および以下のような人々 あらゆる種類の差異進化について、基本的な知識や情報を超えたいと考えています。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jul 1, 2023

Book preview

第1章:ディファレンシャル進化

進化的コンピューティングの分野では、しばしばDEとして知られる微分進化は、特定の品質尺度に関連して候補解の改善を繰り返し試みることによって問題を最適化する手法です。DEは「分化進化」という用語の略語です。これらの種類の手順は、対処されている問題についてほとんどまたはまったく仮定せず、潜在的な解決策の非常に巨大な領域を探索できるため、メタヒューリスティクスと呼ばれることがよくあります。ただし、DEのようなメタヒューリスティクスでは、最良の解決策が見つかるとは限りません。

DEは多次元実数値関数に使用されますが、最適化される問題の勾配は使用しません。これは、DEが最適化問題を微分可能であることを要求しないことを意味し、これは勾配降下法や準ニュートン法などの従来の最適化法の要件です。DEは、多次元実数値関数を最適化するために使用されます。その結果、DEは、連続的ではない問題、ノイズが多い問題、時間の経過とともに変化する問題、およびその他の同様の問題の最適化にも使用できます。

DE は、最初に候補解の母集団を保存し、次に既存の解を簡単な式に従って組み合わせて新しい候補解を生成し、最後に現在作業中の最適化問題に関連して最高のスコアまたは適合度を達成する候補解を選択することで、問題を最適化します。このため、最適化の問題はブラックボックスであるかのように処理され、候補ソリューションが与えられた場合の品質の尺度のみを提供します。この問題の処理のため、勾配は必要ありません。

1990年代に、ストーンとプライスが最初にDEを提示した人でした。

DEアルゴリズムの基本的な実装は、潜在的なソリューション(エージェントと呼ばれる)の母集団の存在によって特徴付けられます。これらのエージェントは、単純な数式を使用して、母集団からの既存のエージェントの位置を組み合わせることにより、検索空間で操作されます。エージェントの新しく提案された位置が以前のものよりも改善を表す場合、それは受け入れられ、母集団に追加されます。それ以外の場合は、新しく提案されたポジションは単に削除されます。この手順は数回実行され、保証されていませんが、そうすることで最終的に適切な解決策の発見につながることが期待されています。

正式には、 f:\mathbb {R} ^{n}\to \mathbb {R} 最小化しなければならない適応度関数とする(代わりに関数を考慮することで最大化を行うことができることに注意 h := -f )。

この関数は、引数として実数のベクトルの形式の候補解を受け入れ、出力として実数を返します。この実数は、提供された候補解が適しているかどうかを示します。

の勾配は f 不明です。

目標は、検索空間内のすべての人にとっての解決策を見つけることであり {\mathbf {m}} {\displaystyle f(\mathbf {m} )\leq f(\mathbf {p} )} \mathbf {p} 、これはそれが {\mathbf {m}} グローバルな最小値であることを意味します。

母集団内の候補解(エージェント)を指定し \mathbf {x} \in \mathbb {R} ^{n} ましょう。

最も基本的な形式のDEアルゴリズムは、次のように説明できます。

パラメータ、 \text{NP} \geq 4 \text{CR} \in [0,1] 、および F \in [0,2] を選択します。

{\displaystyle {\text{NP}}} は人口規模、すなわち

潜在的なエージェントの量。多くの場合、「親」と呼ばれます。一般的な設定は 10 です。 n

パラメータはクロスオーバー確率 \text{CR} \in [0,1] と呼ばれ、パラメータは微分重み F \in [0,2] と呼ばれます。

一般的な設定は {\displaystyle F=0.8} と {\displaystyle CR=0.9} です。

最適化のパフォーマンスは、これらのオプションの結果として大幅に変更される可能性があります。下記参照。

検索空間内のランダムな位置を持つ \mathbf {x} すべてのエージェントを初期化します。

終了基準の1つが満たされるまで(たとえば、適切なレベルのフィットネスが達成された場合)、以下の手順を必要な回数繰り返します。

人口内の各エージェントについて \mathbf {x} 、次のことを行います。

3つのエージェントを選び \mathbf{a},\mathbf{b} \mathbf {c} 、無作為に母集団から、それらは互いに、そしてエージェントから区別されなければならない \mathbf {x} 。

(「 \mathbf {a} ベース」ベクトルと呼ばれます。

ランダムインデックスを選択します R \in \{1, \ldots, n\} ここで n 、 は最適化される問題の次元です。

エージェントの新しい可能性のある位置を \mathbf{y} = [y_1, \ldots, y_n] 次のように計算します。

それぞれについて i \in \{1,\ldots,n\} 、一様に分布した乱数を選択します {\displaystyle r_{i}\sim U(0,1)}

If {\displaystyle r_{i}

(インデックスの位置 R は確実に置き換えられます。

その場合 {\displaystyle f(\mathbf {y} )\leq f(\mathbf {x} )} 、母集団内のエージェントを改善された、または同等の候補ソリューションに \mathbf {x} 置き換えます \mathbf {y} 。

適合度が最も高い母集団のメンバーを選択し、検出された最適な候補ソリューションとして送信します。

DEパラメータの選択 \text{NP} は、 {\text{CR}} F 最適化のパフォーマンスに大きな影響を与える可能性があります。

その結果、好ましい結果をもたらす可能性が最も高いDE因子を決定することにかなりの量の研究が向けられてきました。

Stornらは、パラメータを選択する際に従うべきいくつかの一般的なガイドラインを考え出しました。

最適化プロセスの機能を強化するための継続的な試みとして、DEアルゴリズムの新しい反復が継続的に作成されています。前述の基本的なアルゴリズムは、エージェントのクロスオーバーおよび突然変異を実行するときに多種多様なアプローチを使用することを可能にする(例えば、

{第 1 章終了}

第2章:人工蜂コロニーアルゴリズム

コンピュータサイエンスとオペレーションズリサーチの分野に関しては、ミツバチの群れのインテリジェントな採餌行動に基づく最適化手法は、2005年にDervişKaraboğa(Erciyes大学)によって提案された人工ミツバチコロニーアルゴリズム(略してABC)と呼ばれます。

ABCモデルによると、ミツバチのコロニーは、働きバチ、観察ミツバチ、スカウトミツバチの3種類のミツバチで構成されています。人工的に育てられたミツバチは、各食料源に作用しているミツバチが1匹だけいると推定されます。別の言い方をすれば、コロニー内で積極的に餌を探しているミツバチの数は、巣箱周辺の食料源の総量に比例します。働きバチは食料源に行き、巣箱に戻り、ここでダンスを披露します。食料源が放棄された働きバチは、スカウトの役割を引き受け、新しい食料源を探すプロセスを開始する必要があります。働きバチによって行われる踊りは見物人によって観察され、見物人は踊りに基づいて食料源を選択します。アルゴリズムの主なフェーズは、便宜上以下に概説されています。

すべての働きバチは、初期の食料源の生産に貢献しています。

繰り返す

各働きバチは、その記憶に保存されている食物源に移動し、地理的に最も近い供給源を見つけ、それに含まれる蜜の量を評価し、巣箱の中で踊ります。

各観察者は、彼らが行うダンスに基づいて、雇用されたミツバチの供給源の1つを選択し、訪問するソースを決定した後、そのソースに移動します。近くの隣人を選択した後、彼女はそれが生産する蜜の総量を計算します。

どの食料源が放棄されたかが特定され、それらの資源はスカウトによって発見された新しい食料源に置き換えられます。

これまでに発見された最高級の食料源の登録。

まで(要件が満たされている)

人口ベースの方法であるABCアルゴリズムにおける食物源の位置は、最適化問題の潜在的な解決策を表し、食物源が生産する蜜の量は、その食物源に関連する溶液の品質(適合性)を表します。雇われたミツバチのそれぞれには、人口全体とまったく同じ数の選択肢があります。プロセスの最初の段階では、ランダムな分布を使用して食料源サイトの初期母集団が形成されます。個体群の初期化が完了した後、雇用されたミツバチ、観察者、スカウトミツバチがそれぞれ使用する検索手順の多くの反復が行われます。活動的な働き蜂は、彼女の記憶に保存されているソースの位置を変更し、新しい食物ソースの場所の発見につながります。新しい供給源から得られた蜜の量が以前の供給源の量よりも多い場合、ミツバチは新しい供給源の場所を記憶し、以前の供給源の場所を忘れます。それとは別に、彼女はその人が彼女の記憶のどこに位置していたかを覚えています。雇われたすべてのミツバチが情報源を探すプロセスを終えるとすぐに、彼らはこの情報をダンスエリアにいる観察者に伝えます。すべての働きバチから収集された蜜情報は、各観察者によって分析され、各供給源によって生産された蜜の総量に応じて食料源を選択します。彼女は、働きバチがしたように、記憶のソースポイントを変更し、その場所にあった蜜の量を調べます。ミツバチは新しい場所を覚えており、新しい場所での蜜の供給が前の場所の蜜の供給よりも大きい限り、古い場所を忘れます。どのソースを放棄するかが決定され、人工スカウトは、使用しなくなったソースを置き換えるために、ランダムに新しいソースを開発します。

人工ミツバチコロニー(ABC)アルゴリズムは、ミツバチの採餌活動を複製する最適化の方法です。この方法は、実社会のさまざまな問題に効果的に適用されています。Karabogaは2005年にABCアルゴリズムを初めて導入しました。これは、群知能アルゴリズムのカテゴリのメンバーです。

ミツバチは、群れと呼ばれる社会的コラボレーションを使用してタスクを効果的に完了することができます。ABC アルゴリズムに参加するミツバチには、採用ミツバチ、観察ミツバチ、スカウトミツバチの 3 種類があります。雇われたミツバチは、記憶に蓄えられている食料源の周辺で餌を探し、その間に見物人であるミツバチに食料源の情報を伝えます。見物人のミツバチは、雇われたミツバチによって発見されたものの中から好ましい食料源を選ぶ傾向があります。見物人のミツバチは、低品質の食料源を選択するよりも、高品質の食料源(フィットネス)を選択する可能性が高くなります。スカウトミツバチは、潜在的な新しいミツバチを調査するために現在の食料源を離れる少数の働きバチに由来します。

ABCアルゴリズムによると、群れの前半は働きバチで構成され、後半は観察ミツバチで構成されています。

群れの中のミツバチの総数は次のように分類できます:雇用されたミツバチの数と観察ミツバチの数の合計は、解決策の総数に等しくなります。ABCは、ランダムに広がるSNソリューション(食料源)の初期母集団を生成します。ここで、SNは群れのサイズを表します。

群れの解 {\displaystyle X_{i}=\{x_{i,1},x_{i,2},\ldots ,x_{i,n}\}}