エージェント型並列分散メタヒューリスティックアルゴリズムの研究

点击翻译按钮获取中文摘要

本研究ではインターネットなどのネットワークにつながれた多くの計算資源を利用することによる並列分散型メタヒューリスティック手法の新たなアプローチを試みる。ここでは、ネットワークを介して並列分散処理の実現をはかり、その上で、有効なネットワーク型並列分散メタヒューリスティックアルゴリズムの開発を試みる。特に、探索空間や、問題自身を分割するデータ分割型探索に着目し、よりスピーディな計算を行うと同時により質の高い解を生成する新たなアルゴリズムの提案する。このとき多くの問題が介在するが、たとえば、各部分問題間の移動可能性が限られることにより、良質な解は生成されない。そこで、ネットワーク上を自由に動き回るエージェントを検討し、それに各種の能力を持たせることにより多様性の高い部分解の生成を行わせる。この提案方法により質の高い解を生成させるとともに、自由度の高い計算環境のもとで並列アルゴリズムを実現させるものである。特に本年度では、本研究における並列化における大きな問題であった各部分問題の移動可能性が限定される問題に対して、近傍操作にエージェント処理を組み込み、エージェントの働きにより、解の整合性を考慮し多様性のある子部分問題の分割生成を実現しこの問題を打開した。また、よりスピーディーに探索を行うためデータ分割の工夫を行い、さらに、アトラクティブな移動戦略を用いるなど効果的な解探索を実現し、より強力な並列メタヒューリスティック手法を提案した。さらに、以上で構成した並列分散メタヒューリスティックアルゴリズムの各種のデータを収集し分析を行い、その特性を示しエージェント技法の有効性、並列化に優位な近傍集合、あるいは探索手法の新たな展開を示した。また、既存のアルゴリズムと比較することにより本並列分散メタヒューリステックスアルゴリズムの優位性を証明した。