![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2024-11-12T03:35:47+01:00","","") #author("2024-11-12T03:50:57+01:00","","") [[柴原]] 群知能（Swarm Intelligence：SI）とは、主に自然または芸術的な自己組織化システムの振る舞いとして定義される、 分散型システムである。群れは互いに局所的に、あるいは外部エージェント、すなわち環境と相互作用する。 鳥の群れ、アリ、ハチなどである。連続非線形関数を最適化するために によって導入された粒子群最適化（PSO）は、SIに新時代をもたらした。PSO は、最適化のための集団ベースの手法である。潜在的な解の集団は その中の個体を粒子と呼ぶ。 粒子は群れの中を飛び回り、自分自身や同じ群れの他の粒子の経験に基づき、最適な解を探索する。 を探索する。PSOは多くの研究者の間で注目を集め始め、導入後すぐに最も人気のあるSI 手法となったが、単一の目的のみの最適化という制約があるため、新しい概念であるマルチO しかし、単一目的のみの最適化という制約があるため、新しいコンセプトの多目的PSO(MOPSO)が導入された。 が導入された。MOPSOは [129]によって提案された。MOPSOでは、単一の解ではなく、解の集合が決定される。 パレート最適集合とも呼ばれる。多目的最適化(MOO)は、ベクトル最適化と呼ばれることもある。 ベクトル最適化と呼ばれることもある。 と呼ばれることもある。多目的最適化問題（MOP）は、基本的に線形MOPと非線形MOPに分類される。 と非線形MOP、凸MOPと非凸MOPに分類される。すべての目的関数と制約条件が がすべて線形である場合、線形MOPと呼ばれるが、目的関数や制約関数のいずれかが非線形である場合、非線形MOPと呼ばれる、 非線形MOPとなります。同様に、すべての目的関数が凸で、実行可能領域 が凸であれば凸MOP、非凸MOPであればその逆となる。 今日まで MOPSOの多くのバリエーションとアプリケーションが開発されてきた。開発されたアプリケーションは 環境、産業、ジョブショップスケジューリング、工学、生物学、その他多くの分野である。 MOPSOの全てのバリエーションとアプリケーションを1つの記事で論じることは不可能である。 の研究は、MOPSOの応用とMOPSOの変種の2つの部分に分けられる。本稿では この論文では、MOPSOのすべての応用分野を要約しようと試みた。 を提供することができる。本稿の残りの部分は以下のように構成されている： セクション2と3は、それぞれMOPと標準PSOの基本概念とアルゴリズムを示す。 セクション4では、MOPSOのアルゴリズム、定式化、概念を示す。セクション5では セクション5では、MOPSOの応用分野別にサーベイを行う。セクション6では、調査から得られた知見と を考察し、今後の方向性について述べ、結論を述べる。 MOP（多目的最適化問題）には、目的関数と通常いくつかの制約条件があります。これらの制約条件は、最適解を含むすべての実行可能な解において満たす必要があります。MOPは次のように定式化されます： 目的関数： 最小化または最大化 Minimize/Maximize fₙ(x), n = 1, 2, ..., N 制約条件： 不等式制約： gⱼ(x) ≤ 0, j = 1, 2, ..., J 等式制約： hₖ(x) = 0, k = 1, 2, ..., K 変数の境界制約： xᵢ(L) ≤ xᵢ ≤ xᵢ(U), i = 1, 2, ..., m ここで、x は m 個の決定変数のベクトルで、x = (x₁, x₂, ..., xₘ)ᵀ と表されます。最初の制約は最小化問題の場合の不等式制約で、最大化問題の場合には「≤」の形に変わります。次の制約は等式制約で、最後は変数の境界制約です。これにより、各決定変数 xᵢ は、それぞれの下限 xᵢ(L) と上限 xᵢ(U) の間に収まるように制限されます。 MOP を解くためには、従来の手法や人工知能（AI）技術がよく使われます。MOPを解くための代表的なAI技術は、進化的アルゴリズム（EAs）と粒子群最適化（PSO）です。このセクションでは、進化的アルゴリズム（EAs）と従来の手法について説明し、次のセクションでは PSO について説明します。 2.1. 古典的な方法 古典的な方法は、嗜好情報の使用量が多い順に次のとおりである。 である： 加重合計法、制約法、加重計量法、ベンソンズ法、価値関数法、ゴール・プログラミング法である。 関数法、ゴール・プログラミング法である。重み付き和法では、目的をスカラー化する。 加重和法では、各目的にユーザーが提供した重みをあらかじめ乗算することで、目的をスカラー化する。制約 制約法は、非凸の目的空間を持つ問題を解く際に重み付き和法が直面する問題を軽減する。 MOPを再定式化することにより、非凸の目的空間を持つ問題を解く際に重み付き和法が直面する困難を軽減する。 ユーザが指定した値の範囲内で残りの目的を制限する。重み付きメトリック法では の加重和を用いる代わりに、lpやl1距離メトリックのような加重メトリックを用いることが多い。 そのため、加重メトリックは複数の目的を1つの目的にまとめる手段となる。 Bensons法は、参照解を実行可能な非平均最適解とすることを除けば、加重計量法に似ている。 ただし、参照解は実現可能な非平均最適解とする。価値関数法では、ユーザーは数学的価値 関数 U : RM ！Rの数学的価値関数U を提供する。この価値関数は 実現可能な探索空間全体にわたって有効でなければならない。目標計画法は、1つまたは複数の目的関数について、あらかじめ設定された目標を達成する解を求めるのに役立つ。 を達成する解を求めるのに役立つ。 すべての目的関数において、あらかじめ指定された目標を達成する解が存在しない場合 すべての目的関数において事前に指定された目標を達成する解が存在しない場合、課題は目標からの偏差を最小化する解を見つけることである。 である。しかし、望ましい目標を達成する解が存在する場合、タスクはその特定の解を特定することである。 2.2. 進化的アルゴリズム EAに基づくアプローチは、基本的に以下の3つのタイプに分類される。 タイプに分類される[40]： 集約関数、母集団ベースのアプローチ、パレートベースのアプローチである。集約関数 集約関数は、任意の算術演算によって、すべての目的を1つの目的に統合する概念である。 により、すべての目的を1つの目的に統合するという概念を持つ。線形集計関数のため、これらの方法はあまり印象的ではない。 母集団ベースのアプローチは、探索を多様化するためにEAの母集団を利用する。[1]はVector Eval uated Genetic Algorithm (VEGA)を発表した。 アプローチである。VEGAでは、各世代で比例選択により部分集団が生成される。もし 母集団の総サイズがNで、目的の総数をnとすると、部分母集団のサイズは N/nとなる。母集団ベースのアプローチは採用が簡単であるが、その主な限界は選択スキームである。 パレート最適性に基づいていないことである。パレートに基づくアプローチは、[63]によって最初に提案された。 [63]. その後、多様性を維持し収束を避けるために、ニッチングとtness sharingが提案された。 50]によって提案された。パレートに基づくアプローチは最も一般的なアプローチであり、2つの世代に分けられる。第一世代 第一世代はtness sharing、ニッチングとパレートランキングを組み合わせたもの、第二世代はエリート主義の概念を用いたものである。 エリート主義の概念。 2.3. 粒子群最適化と進化アルゴリズムの比較。PSOはEA とは、親の表現、個体の選択、パラメータチューニングのアプローチにおいて異なる。 8]に示されているように、パラメータチューニングのアプローチに違いがある： PSOでは親情報は各粒子内に含まれるのに対し、進化的最適化（EO）では共有される。 最適化. 42 Trans. Comb. 2 no. 1 (2013) 39-101 S. Lalwani, S. Singhal, R. Kumar and N. Gupta PSOは、EOのように処理から明示的な選択関数を関与させない。 PSOでは個体操作に指向性の高い突然変異操作を用いるが、EOでは全方位的である。 は全方位的である。 PSOには、速度ステップサイズを局所領域探索空間に適した値に適応させるメカニズムがない。 一方、EOでは各個体の構成要素の変異の度合いを含む。 を含む。 異なる手法による異なる解は、異なる対象間で矛盾するシナリオを生み出す可能性がある。 の間で矛盾するシナリオを生み出す可能性がある。ある目的に対して最適な解は、他の目的に対しては妥協が必要である。 となる。このため、ユーザーは1つの目的に対してのみ最適な解を選択することが重要である。 49]。MOOの主な目標は、最適解に近く、真の目的を表すのに十分多様な解の集合を見つけることである。 最適解に近く、最適解の真の広がりを表すのに十分な多様性を持つ解の集合を見つけることである。MOPSOアルゴリズム は、先に述べた両方の条件をより直接的に満たす。シンプルで計算コストが低く とMOPSOの人気の高まりにより、単純な問題だけでなく、複雑な性質を持つ実問題の解 実問題を解決する能力を高めている。 ### PSO（粒子群最適化）のアルゴリズム PSO（Particle Swarm Optimization）は、進化的アルゴリズムの一種で、複数の粒子（個体）が解空間を探索し最適解を見つける手法です。以下に、PSOの基本的な動作と数式を説明します。 --- #### 概要： PSOでは、d次元の検索空間と、n個の粒子が存在します。それぞれの粒子は次の情報を持っています： - **位置** Xi = (x_i1, x_i2, ..., x_id) - **速度** Vi = (v_i1, v_i2, ..., v_id) - **個人最良位置** Pi = (p_i1, p_i2, ..., p_id) ：粒子自身の最良の位置 - **全体最良位置（グローバル最良）** gbest ：スウォーム全体の最良の位置 各粒子は、次の2つの目標を持って移動します： 1. **個人最良** Piとの距離を縮めること。 2. **グローバル最良** gbestとの距離を縮めること。 粒子は、現在の位置、速度、個人最良の位置 Pi、およびグローバル最良の位置 gbest を使って位置を更新します。 --- #### 速度と位置の更新式： - **速度更新式**： V_i^(t+1) = wV_i^t + c1 * r1 * (P_i - X_i^t) + c2 * r2 * (gbest - X_i^t) ここで： - V_i^t ： 時刻 t における粒子 i の速度 - X_i^t ： 時刻 t における粒子 i の位置 - P_i ： 粒子 i の個人最良位置 - gbest ： スウォーム全体の最良位置（グローバル最良） - w ： 慣性重み（粒子の慣性を制御するパラメータ） - c1, c2 ： 認知加速係数および社会的加速係数（それぞれ個人の影響、スウォームの影響を制御） - r1, r2 ： ランダムな値（0～1の範囲で生成され、探索にランダム性を加える） - **位置更新式**： X_i^(t+1) = X_i^t + V_i^(t+1) これは、粒子 i の位置を新しい速度に従って更新する式です。 --- #### パラメータ： - **w** ： 慣性重み。粒子の「慣性」を調整します。小さな w は探索を細かく、大きな w は広範囲に探索します。 - **c1** ： 認知加速係数。粒子が個人最良に従う強さを示します。 - **c2** ： 社会的加速係数。粒子がグローバル最良に従う強さを示します。 - **r1, r2** ： ランダムな値で、探索にランダム性を加えます。これにより粒子はランダムに探索範囲を広げることができます。 --- #### 最適化問題の定式化： PSOは通常、最小化問題に適用され、次のように定式化されます： Minimize/Maximize f(x) ただし、x = (x1, x2, ..., xm)^T は決定変数のベクトルであり、制約条件は次のように表されます： x_i^(L) ≤ x_i ≤ x_i^(U), i = 1, 2, ..., m ここで： - x_i^(L) は変数 x_i の下限 - x_i^(U) は変数 x_i の上限 PSOアルゴリズムは、この最小化問題（または最大化問題）を解くために、粒子の位置と速度を反復的に更新し、最適解を見つけます。 --- PSOは、探索空間内で粒子が自分自身とスウォーム全体の情報を使って解を探索し、最適解を見つけるための効率的な手法です。特に、非線形・非凸な最適化問題に対して効果的な方法として広く利用されています。 --- MOPSOの速度更新と位置更新の式は、PSOの式(2)と式(3)と同じである。 と同じである。パラメータの宣言も目的関数以外はすべて同じである。目的関数 には、式(1)で定式化された複数の目的が含まれている。 アプローチとアプリケーションに基づく論文の分離は、以下の基準で行った。 応用MOP問題を基本問題とし、それを解くために既に開発された変種を応用した場合 を基本問題とし、それを解くために既に開発された変種を適用した場合、または同じ問題に対するアルゴリズムに変更を取り入れた場合、または変種を開発した場合、その論文は応用MOP問題に含まれる。 一方、その論文が、より応用的なMOP問題の開発に含まれていれば、その論文は応用分野に含まれる。 もしその論文が、より変種を開発することに含まれるなら、あるいは主に変種を開発した後に含まれるなら また、その論文に実世界の問題の例が続いている場合は、アプローチに分類される。中には 新しく開発された変種のために、アプリケーションとアプローチの両方に属する記事もある、 両方において議論されることになっている。このセクションは、図3に示すように、応用分野のサブセクションに分かれている。 図3に示す。2012年10月中旬までに発見されたMOPSOを用いた論文は189件であった。 であった。図3は、MOPSOの産業工学、電気工学、そしてその他の分野への幅広い適用性を示しています。 図3は、MOPSOの産業工学、電気工学、その他の分野への幅広い適用性を示しています。
