並列メタヒューリスティック

並列メタヒューリスティックとは、メタヒューリスティックの数値的労力^{[説明が必要]}と実行時間の両方を削減できる一連の技術です。このために、コンピュータサイエンスにおける並列処理の分野の概念と技術が、既存のメタヒューリスティックの動作を強化し、場合によっては完全に変更するために使用されます。進化アルゴリズム、粒子群、アントコロニー最適化、シミュレーテッドアニーリングなど、メタヒューリスティックの長いリストが存在するのと同様に、これらのアルゴリズムに強くまたは緩く基づいたさまざまな技術の大規模なセットも存在し、その動作は、特定の並列ハードウェアプラットフォーム上で問題を解決するために何らかの方法で連携するアルゴリズムコンポーネントの複数の並列実行を網羅しています。

背景

実際には、最適化 (および探索および学習) の問題は、NP 困難で、複雑で、時間がかかることがよくあります。これらの問題への取り組みには、従来、正確な方法とメタヒューリスティックという 2 つの主要なアプローチが使用されています。^{[異論あり–議論]}正確な方法を使用すると正確な解決策を見つけることができますが、現実世界の問題 (大規模、制約がほとんどない、マルチモーダル、時間変動、エピスタティックな問題) には非常に時間がかかるため、実用的ではないことがよくあります。逆に、メタヒューリスティックは、妥当な時間内に次善の (場合によっては最適な) 解決策を提供します。したがって、メタヒューリスティックは通常、産業分野で課せられる解決遅延に対応することを可能にするだけでなく、特定の問題インスタンスではなく一般的な問題クラスを調査することもできます。一般に、複雑で現実世界の問題を解決するための精度と労力の面で最も優れた手法の多くは、メタヒューリスティックです。その応用分野は、組み合わせ最適化、バイオインフォマティクス、電気通信から経済学、ソフトウェアエンジニアリングなどにまで及びます。複雑なアプリケーションの詳細については[1]を参照してください。

メタヒューリスティックスは、軌跡ベースのメタヒューリスティックスと集団ベースのメタヒューリスティックスの 2 つのカテゴリに分類されます。これら 2 種類の方法の主な違いは、(反復) アルゴリズムの各ステップで使用される暫定的なソリューションの数にあります。軌跡ベースの手法は、単一の初期ソリューションから開始し、検索の各ステップで、現在のソリューションがその近傍で見つかった別の (多くの場合、最適な) ソリューションに置き換えられます。軌跡ベースのメタヒューリスティックスでは、通常、局所的に最適なソリューションを迅速に見つけることができるため、検索空間での強化を促進する活用指向の手法と呼ばれます。一方、集団ベースのアルゴリズムでは、ソリューションの集団が使用されます。この場合、初期集団はランダムに生成され (または貪欲アルゴリズムを使用して作成され)、反復プロセスによって強化されます。プロセスの各世代で、集団全体 (またはその一部) が新しく生成された個体 (多くの場合、最適な個体) に置き換えられます。これらの手法は、主な能力が検索空間の多様化にあるため、 探索指向の方法と呼ばれます。

基本的なメタヒューリスティックのほとんどは逐次的です。逐次的なメタヒューリスティックを利用することで、探索プロセスの時間的複雑さを大幅に軽減できますが、学術分野と産業分野の両方で発生する現実の問題においては、この時間的複雑さは依然として高いままです。そのため、並列化は探索時間を短縮するだけでなく、提供される解の質を向上させる自然な方法として考えられます。

並列処理とメタヒューリスティックスをどのように組み合わせることができるかについての包括的な議論については[2]を参照してください。

並列軌道ベースのメタヒューリスティック

最適化問題を解決するためのメタヒューリスティクスは、問題の解決領域を通る探索軌跡をたどりながら 近傍を歩くことと見ることができます。

アルゴリズム: 順次軌道ベースの一般的な擬似コード
    Generate( s (0)); // 初期解
    t  := 0; // 数値ステップ
    while  not Termination Criterion(s(t)) do 
        s′( t ) := SelectMove(s( t )); // 近傍の探索
        if AcceptMove(s′( t )) then 
            s( t ) := ApplyMove(s′( t ));
             t  := t + 1;
     endwhile

ウォークは、解空間内のある解から別の解へと移動することを可能にする反復的な手順によって実行されます（上記のアルゴリズムを参照）。この種のメタヒューリスティックスは、現在の解の近傍内で移動を実行します。つまり、摂動的な性質を持ちます。ウォークは、ランダムに生成された解、または別の最適化アルゴリズムによって得られた解から開始されます。各反復において、現在の解は、近傍候補の集合から選択された別の解に置き換えられます。探索プロセスは、所定の条件（生成回数の上限、目標品質の解の探索、一定時間停止など）が満たされると停止します。

軌跡ベースの手法で高い計算効率を達成する強力な方法は、並列処理の利用です。軌跡ベースのメタヒューリスティックスには様々な並列モデルが提案されており、文献ではそのうち3つが一般的に用いられています。並列マルチスタートモデル、近傍の並列探索と評価（または並列移動モデル）、そして単一解の並列評価（または移動加速モデル）です。

並列マルチスタートモデル：これは、より優れた堅牢な解を計算するために、複数の軌道ベースの手法を同時に起動するものです。これらの手法は、異種または同種、独立または協調的、同じ解から開始する場合も異なる解から開始する場合も、同じパラメータまたは異なるパラメータで設定される場合があります。
並列移動モデル：これは低レベルのマスター・スレーブモデルであり、ヒューリスティックの挙動を変えません。シーケンシャルサーチでも同じ結果が計算されますが、速度は遅くなります。各反復処理の開始時に、マスターは分散ノード間で現在の解を複製します。各ノードは個別に候補/解を管理し、結果はマスターに返されます。
手加速モデル：各手の質は、並列集中的に評価されます。このモデルは、評価関数自体がCPU時間を消費したりI/Oを集中的に使用したりする場合に特に興味深いものです。評価関数自体が並列化できる場合、評価関数は並列実行可能な一定数の部分関数^{（[説明が必要]）の集合体と見なすことができます。}

並列集団ベースメタヒューリスティック

集団ベースのメタヒューリスティックは、多くの現実的で複雑なアプリケーション（エピスタティック、マルチモーダル、多目的、および制約の厳しい問題）に適用され、成功を収めてきました。集団ベースのアルゴリズムは、個体のプール、つまり集団（以下のアルゴリズムを参照）に確率的演算子を適用する反復的な手法です。集団内のすべての個体は、暫定的な解のエンコードされたバージョンです。評価関数は、問題への適合性を示す適応度値をすべての個体に関連付けます。選択された個体に対する変動演算子の確率的適用を反復的に行うことで、集団はより高品質の暫定的な解に導かれます。解の集団の操作に基づく最も有名なメタヒューリスティックファミリには、進化アルゴリズム（EA）、アントコロニー最適化（ACO）、粒子群最適化（PSO）、散布探索（SS）、微分進化（DE）、推定分布アルゴリズム（EDA）があります。

アルゴリズム: シーケンシャルポピュレーションベースメタヒューリスティック擬似コード
    Generate(P(0)); // 初期人口
    t  := 0; // 数値ステップ
    while not Termination Criterion(P( t )) do 
        Evaluate(P( t )); // 集団の評価
        P′′( t ) := Apply Variation Operators(P′( t )); // 新しい解の生成
        P( t + 1) := Replace(P( t ), P′′( t )); // 次の集団を構築
        t  := t + 1;
     endwhile

非自明な問題の場合、長い個体や大規模な集団に対して単純な集団ベース手法の繁殖サイクルを実行するには、通常、膨大な計算リソースが必要になります。一般的に、すべての個体の適応度関数の評価は、このアルゴリズムの中で最もコストのかかる操作となることがよくあります。そのため、効率的な手法を設計するために、様々なアルゴリズム上の課題が研究されています。これらの課題には、通常、新しい演算子の定義、ハイブリッドアルゴリズム、並列モデルなどが含まれます。

集団を扱う際には、集団に属する個々の個体が独立した単位であるため、並列処理が自然に発生します（少なくともピッツバーグ方式ではそうなりますが、ミシガン方式のように個体を独立した単位と見なさないアプローチもあります）。実際、集団ベースのアルゴリズムは並列実行することでパフォーマンスが向上することがよくあります。集団ベースのアルゴリズムに特化した並列化戦略として、以下の2つがあります。

計算の並列化。各個体に共通して適用される演算が並列に実行される。
集団の並列化。集団は、単純に交換したり別々に進化させることができる異なる部分に分割され、後で結合されます。

これらのアルゴリズムの並列化の歴史の初期には、よく知られたマスタースレーブ（グローバル並列化またはファーミングとも呼ばれる）手法が使用されていました。このアプローチでは、中央プロセッサが選択操作を実行し、関連付けられたスレーブプロセッサ（ワーカー）が変動演算子と適合度関数の評価を実行します。このアルゴリズムは、特に時間のかかる目的関数に対して計算効率が向上している点において、シーケンシャルアルゴリズムと同じ動作をします。一方、多くの研究者は、独立した実行を単一のプロセッサを使用するよりも複数のプロセッサを使用する方が迅速に行うことができるという理由だけで、シーケンシャルアルゴリズムの実行を高速化するためにプロセッサプールを使用しています。この場合、独立した実行間に相互作用はまったく存在しません。

しかし実際には、文献に見られる並列集団ベース手法のほとんどは、個体群に何らかの空間配置を適用し、その結果得られたチャンクをプロセッサプール内で並列化します。最も広く知られている構造化メタヒューリスティックスの中でも、分散（または粗粒度）アルゴリズムとセルラー（または細粒度）アルゴリズムは、非常によく知られた最適化手法です。

分散型の場合、個体群は複数のサブ個体群（島）に分割され、各サブ個体群では独立した逐次アルゴリズムが実行されます。これらの島間では、個体の疎な交換が行われ、サブ個体群に多様性をもたらし、探索が局所最適解に陥るのを防ぎます。分散型メタヒューリスティックを設計するには、^{[誰が？ ]}がいくつかの決定を下す必要があります。その中でも、最も重要な決定は、移動ポリシーを決定することです。移動ポリシーとは、トポロジ（島間の論理的なリンク）、移動率（各交換で移動する個体数）、移動頻度（連続する2回の交換間の各サブ個体群におけるステップ数）、そして移動個体の選択/置換です。

セルラー法では近傍の概念が導入され、個体は繁殖ループにおいて近傍個体とのみ相互作用するようになります。このアルゴリズムにおける重なり合った小さな近傍は、集団全体にわたる解の緩やかな拡散が一種の探索をもたらし、各近傍内では利用が行われるため、探索空間の探索に役立ちます。セルラー遺伝的アルゴリズムと関連モデルの詳細については、[3]を参照してください。

また、2段階の並列化アプローチを採用したハイブリッドモデルも提案されています。一般的に、上位レベルの並列化では粗粒度の実装が採用され、基本アイランドではセルラー方式、マスタースレーブ方式、あるいはその他の分散方式が実行されます。

参照

参考文献

G. Luque, E. Alba, Parallel Genetic Algorithms. Theory and Real World Applications, Springer-Verlag, ISBN 978-3-642-22083-82011年7月
Alba E.、Blum C.、Isasi P.、León C. Gómez JA (編)、複雑な問題を解決するための最適化テクニック、Wiley、ISBN 978-0-470-29332-4、2009年
E. Alba、B. Dorronsoro、Cellular Genetic Algorithms、Springer-Verlag、ISBN 978-0-387-77609-5、2008年
N. Nedjah、E. Alba、L. de Macedo Mourelle、並列進化計算、Springer-Verlag、ISBN 3-540-32837-8、2006年
E. Alba、Parallel Metaheuristics: A New Class of Algorithms、Wiley、ISBN 0-471-67806-62005年7月
マルバ
JGDS
デメ
xxGA
プサルヘ・エア
パラダイソ