![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
柴原?
柴原?
Continuous Swarm Optimization Technique with
Stability Analysis
最適化アルゴリズムを紹介する。まず、古典的なPSOの表記法を紹介する、 次に新しいPSOを紹介する。提案するPSOには2つの形式があり、1つはリアプノフ 安定であることが証明され、もう一つは漸近的に安定であることが証明される。 漸近安定であることが証明できる。新しいPSOのパラメータの を調べた。適切なシミュレーション結果を提供する。
I. Introduction
決定論的手法は、数十年にわたりオプティマイゼーションの分野を支配してきた。決定論的手法では大域的極小値を見つけることができず、その複雑さが確率的・発見的アルゴリズムの動機となった。ほとんどの ヒューリスティック・アルゴリズムの大半は、シミュレーテッド・アニーリングのような自然シミュレーション・アニーリングのような自然な最適化プロセスのモデリングに基づいている、これらのアルゴリズムは、モデル化された自然過程に応じて特定の行動挙動を持つ個体群に基づいている。
最初の発見的アルゴリズムのうち、ランダム探索 (RS)は、探索空間における個体のランダムなテスト移動に基づく単純な手法である[1]。 に基づく単純な手法である [1]。 個体は、新しい位置のコスト関数がより良ければ、実際に新しい位置に移動する。 新しい位置のコスト関数がより良い場合、個体は実際に新しい位置に移動する。遺伝学と遺伝学的アルゴリズム（genetics algorithm）と記憶論的アルゴリズム（memetics algorithms）は、より最近の例である。遺伝的アルゴリズム(GA)は、その名の通り、自然の遺伝的進化をモデル化したものである。GAは１つの個体（親）の間でコード化された情報（遺伝子）の文字列の一部を交換することに基づいている。 ミメティックス・アルゴリズムのモデルグループ間のアイデアの交換
近年、粒子群最適化 (PSO)という概念が提案された。これは動物 集団（魚の群れ、鳥の群れ、昆虫の群れ)。 集団のメンバーは、探索中に見つけた最良の位置に関する情報 集団の成員は、餌を探すときに見つけた最良の位置に関する情報を共有する を共有することが知られている。従って、PSOモデルは個体的経験と社会的経験の両方を探索に組み込んでいる。を組み込んだモデルである。PSOは は、特に電力システム[4電力システム・アプリケーション[4]や電磁 場計算[5]に応用されている。基本的なPSOを修正することができる[6]。パラメータがPSOに与える影響は[7]で研究されている。システムの観点からは、標準的なPSOアルゴリズムは離散的である。であり、粒子運動は時間ステップごとに更新される。
本論文では、PSOのための新しい連続時間モデルを開発した。 を開発した。連続PSO（CPSO）モデルは、自然PSOが連続的な運動をする（ジャンプしない）という事実に動機づけられている。さらに、システム の観点からは、離散化は安定性を低下させる効果がある。 オリジナルのPSOアルゴリズムのレビューを第2節に示す。 第2節では、新しいコンパクトな表記法を用いて、オリジナルのPSOアルゴリズムのレビューを行う。開発した CPSOモデルをセクション3に示す。セクション4では、CPSOがLy、 CPSOがリアプノフ安定であることを示す。漸近安定性を確保するために 漸近安定性を確保するために、修正されたCPSOがセクション5で示され でその大域的漸近安定性が証明される。 セクション6で証明される。セクション7ではPSO のパラメータとCPSOのパラメータを比較する。シミュレーション結果は セクション8で示すシミュレーション結果は、開発したモデルが古典的な離散PSOよりも優れた性能を持つことを示している。 であることを示す。
II. Discrete Swarm Algorithm
自然の群れから着想を得たように、PSO技法は、フィー ルド内を移動する粒子群（集団）を用いて最適探索を行う。 各粒子（鳥）の任意の時点における位置は、解の候補を表す。 における各粒子（鳥）の位置が解の候補となる。一定期間ごとに 各バードは現在の位置でコスト関数を評価し と比較する。もちろん、自己ベストとはは、鳥の探索中にコスト関数が最良の値を示した位置である。である。鳥はそれぞれの自己ベストに関する情報を交換し鳥はそれぞれの自己ベストに関する情報を交換し、鳥が発見した最高の位置、グローバルベストを決定する。鳥のの運動方向には、社会性のみの要素と認知性のみの要素の両方が含まれる。社会的な要素のみが鳥をグローバル・ベストに引き寄せる。のみが各鳥を自己ベストの方向に引っ張る。したがって、各鳥の速度には3つの要素がある、すなわち同じ探索方向を保とうとする運動量成分、鳥の自己ベストに向かう成分自己ベストに向かう成分、そしてグローバルな群ベストである。第 1 バードの PSO 更新方程式は次のようになる。 であり、ベクトル方程式
vi(k + 1) = αd * vi(k) + βd * (xlbi - xi(k)) + γd * (xgb - xi(k)) (1)
xi(k + 1) = xi(k) + vi(k + 1) (2)
ここで、xi は鳥の位置、vi は鳥の速度を表す、 xlbi はローカルベスト、xgb は群グローバルベスト、αd、βdとγd はゼロでない正の実数である。前述の式が示すように基本的なPSOアルゴリズムは離散時間である。 時間であり、各鳥は以下の単純なセットを持つ。 2の運動方程式を持つ。これらの方程式は これらの方程式は、群れ全体をコンパクトに記述するために並べ替えることができる。一般性を損なうことなく、以下の問題を考える。関数を最小化する問題を考える。 Ωは実行可能領域を表し、 n は鳥の数を表し、 f : Ω → R は最小化される関数である。また、コンパクト化のためコンパクト化のために，以下のベクトルと行列を定義する
X , £ x1 ... xn ¤ ∈ (Ω×R n) 位置行列
V , £ v1 ... vn ¤ ∈ ¡Rd×R n¢ 速度行列
Xlb , £ xlb1 ... xlbn ¤ ∈ (Ω×R n) 局所最良位置行列
Xgb ∈Rd 全体最良位置行列
F , £ f(x1) ... f(xn) ¤ : (Ω×R n) → Rn スタックされた目的関数ベクトル
T ∈Rd すべての要素が1の行ベクトル
Qi ∈ Rn i番目の要素が1で他はすべて0の列ベクトル
In ∈(Rn×Rn) サイズnの単位行列
したがって、古典的な離散時間PSOアルゴリズムの新しい優雅な表現は次のとおりです：
V(k + 1) = αd * V(k) + βd * (Xlb(k) - 
k)) + γd * (Xgb(k)T - k)) (1)
X(k + 1) = k) + V(k + 1) (2)
Xlb(k + 1) = 1/2 * (X(k + 1) + Xlb(k)) (3)
[X(k + 1) - Xlb(k)] * ζ (4)
ここで: ζ = diag[sgn(F(Xlb(k)) - F(X(k + 1)))] (5)
diag[y] は、ベクトル y の要素によって与えられる対角要素を持つ対角行です sgn( ) は符号関数を示し、次のように定義されます: sgn(y) = { 1 (y ≥ 0) { -1 (y < 0)
III. Continuous Swarm Algorithm
しかし、自然界の群れは連続的である。 その動きは実に滑らかである。この事実は連続時間モデルを開発することで、PSOの性能を向上させることができる。もう一つの重要な動機は離散化現象が安定性を低下させるという事実である。現象が学習手順に影響を与える可能性があるという事実である。 完全な連続モデルを開発するためには、式(3)および(4)式を連続等価式に置き換える必要がある。離散モデルと同じ記法を用いると、次のように記述できる。 運動方程式を記述することができる：
V=-αV +β(Xlb-X)+γ(XgbT -X) (8) X=V(9) ここで、X、V、Xlb、Xgb、Tの次元は上で定義したとおりである。α、β、γはゼロでない正の実数。
しかし、XとVだけがシステム状態ではないことに注意すべきである。 Xlbもまた状態である。 メモリ」を持っているので、Xlbも状態である。例えば、Xlb の第 1 列は Xlbの鳥がより良い位置を見つけない限り、Xlb の第 1 列は変化しない。より良い位置が見つかると、その位置はXlbの第Xlbのi番目の列の前の値に置き換わる。 モデルの観点からは、行列Xlbは追加状態として扱われなければならない。 を追加状態として扱うべきである。これらの状態の時間微分局所的な最良位置が変化しない限りゼロである。新しいベスト・ポジションが見つかれば、インパルスになる。値を無時間で変更する。 このようなゼロ／衝動的な微分状態の実装は、標準的なソフトウエアを使えば可能である。 微分状態の実装は標準的なソフトウェア の実装は可能であるが、その安定性解析は容易ではない。 そこで、aを正の定数と仮定しに対してxlbi を最小化する：
·xlbi = a(xi - xlbi) + a(xi - xlbi) * [sgn(f(xlbi) - f(xi))] (10)
この方程式は行列形式で次のように表すことができます： Xlb = a(X - Xlb) * [In + diag[sgn(F(Xlb) - F(X)]]] (11)
備考1: 方程式(11)をよりよく理解するために、方程式(10)を以下のケースで考えます： もし f(xlbi) - f(xi) ≥ 0 なら、sgn(f(xlbi) - f(xi)) = 1 となり、· xlbi = 2a(xi - xlbi) となります。これは、現在の点で評価された目的関数の値が局所最良での値よりも小さい場合、局所最良が現在の点に引き寄せられることを意味します。 もし f(xlbi) - f(xi) < 0 なら、sgn(f(xlbi) - f(xi)) = -1 となり、· xlbi = 0 となります。これは、局所最良での目的関数の値が現在の点での値よりも小さい場合、局所最良が変わらないことを意味します。
備考2: 上記の方程式に基づくと、Xlbは必ずしも局所最良ではなく、近似に過ぎないことを指摘する価値があります。これは、この連続時間アルゴリズムで衝動的な導関数が使用されていないためです。
最後に、全体最良Xgbを特徴付ける必要があります。これは次のように定義できます： Xgb = XlbQj で j = arg inf_{0 < i ≤ n}(f(xlbi)) (12)
システムの観点から、Xgbはセッティングポイントと見なすことができ、その唯一の効果は群れによって定義された動的システムの平衡点を変えることです。
定義3: 先に定義した記法を使用して、連続群れは次のような動的システムΣで表されます： X = V V = -αV + β(Xlb - X) + γ(XgbT - X) Xlb = a(X - Xlb) * [In + diag[sgn(F(Xlb) - F(X))]] Xgb = XlbQj で j = arg inf_{0 < i ≤ n}(f(xlbi)) (13)
備考4: 上記で使用されている記法は、標準的な状態空間の記法ではなく、状態変数X, V, Xlbがベクトルではなく、適切な次元の行列であることに注意してください。この選択は、明確さを失うことなく、単純さとコンパクトさを提供することによって動機付けられています。
IV. StabilityAnalysisoftheContinuous Swarm
連続時間の群れに進むにあたり、導入された修正が全体最良を唯一の平衡点にすることをまず確認しましょう。平衡点は次の方程式を満たす必要があります：
V + δ(XgbT - X) = 0 (24)
a(X - Xlb)ϕ + ε(XgbT - Xlb) = 0 (26)
明らかに、V = 0, X = Xlb = XgbT は平衡点ですが、これは唯一の平衡点でしょうか？この事実を確認するために、詳細な調査が必要です。方程式(24)と(25)から、次のことが得られます：
(αδ + γ)(XgbT - X) - β(X - Xlb) = 0 (27)
方程式(26)は、εXを加減した後、次のように整理できます：
ε(XgbT - X) + (a + ε)(X - Xlb)ϕ = 0 (28)
方程式(27)と(28)で使用される行列の各列について、ϕの値に応じて2つのケースが発生する可能性があります。線形システムを定義する行列は次のようになります：
A = | αδ + γ -β | | ε λ(a + ε) |
ここで、λ = 0 または 2 です。その行列式は次のように与えられます：
|A| = λ(αδ + γ)(a + ε) + βε (29)
この式は、λのすべての可能な値に対して常に正の非ゼロです。これにより、方程式(27)と(28)によって定義される線形方程式の唯一の解は、X = Xlb = XgbT であることが示されます。
したがって、修正された連続時間群れの唯一の平衡点は全体最良です。
この唯一の平衡点の安定性を研究するために、(20)で使用される別の座標系でその動的方程式を表現します： ˜X = V - δ˜X
V = -αV + β(˜Xlb - ˜X) - γ˜X
˜Xlb = a - ε˜Xlb [ (˜X - ˜Xlb) [In + diag[sgn(F(Xlb) - F(X)]]] ] (31)
そして、方程式(21)で提案された同じ候補リャポノフ関数を考慮します。このリャポノフ関数の解に沿った導関数は次のように与えられます：
˙W = tr(-αVTV - aβ(˜X - ˜Xlb)T(˜X - ˜Xlb)ϕi - δ˜XT˜X - ε˜XTlb˜Xlb) (32)
Wが全体的に正定義であり、放射状に無限大に発散するため、˙Wが全体的に負定義であることから、全体最良のグローバル非漸近安定性が示されます。
