多資源計算環境下での遺伝的アルゴリズムのためのローカルサーチメカニズムを有するデータベースの提案

• 花田, 良子

• 廣安, 知之

• 三木, 光範

書誌事項

タイトル別名

• タシゲン ケイサン カンキョウ カ デ ノ イデンテキ アルゴリズム ノ タメ ノ ローカルサーチメカニズム オ ユウスル データベース ノ テイアン
• The Database with Local Search Mechanism for Genetic Algorithms under Large-scale Computing Environments

抄録

近年，膨大な計算ノードを有するPC クラスタやグリッドを利用することにより，多資源環境下で遺伝的アルゴリズム（GA）を実行することが可能となってきた．大規模計算環境が利用可能な場合にはGA に膨大な計算リソースを有効に扱え，効率良く探索できるメカニズムが必要となる．本研究では，計算資源の増加に対して探索性能のスケーラビリティを保証する1 つのアプローチとして，GA のためのローカルサーチメカニズムを有するデータベースを提案する．提案するデータベースでは既探索領域の情報を保存しながら，未探索領域を重点的に探索し既探索領域の拡張を行うローカルサーチを行う．データベースをGA に組み込むことにより，既探索領域の大きさを定量的に把握することが可能である．また，計算資源あるいは計算コストを増加させれば必ず既探索領域が拡張し，有限の計算コストの下で全探索を保証して探索を終了することが可能となる．提案するデータベースを原始的なビットの問題，および連続最適化問題のテスト問題に適用した結果，計算コストを制限しない場合，全探索により得られた解が最適解であることを保証すること，計算コストを制限した場合においても従来のGA と同等の結果を得られることを示した．

Recently, GA that uses large-scale computer systems comprised of massive processors has become feasible because of the emergence of super PC clusters and Grid computation environments. Mechanisms to use massive computation resources laconically and to search effectively are necessary if large-scale computer systems are available. In this study, a new GA-specific database with the local search mechanism to assure the scalability of search performances against the number of computing resources is proposed. Our proposed database possesses information of space that has been already searched with limited number of individuals. At the same time the local search for the space that is not searched is applied using individuals stored in the database. To embed such mechanisms in a GA enables us to comprehend the quantitative rate of a searched region during the search. Using this information, the searched space can be expanded linearly as the number of computing resources increases. Moreover GA can be terminated under guarantee of the exhaustive search. First, our database was applied to primitive functions and shown to ensure an effective exhaustive search. This method was then applied to the test functions of continuous optimization problems under restricted computing costs. Through such experiments, it was clear that this method has the same performance as a conventional GA.

収録刊行物

• 情報処理学会論文誌数理モデル化と応用（TOM）

  情報処理学会論文誌数理モデル化と応用（TOM） 47 (SIG1(TOM14)), 19-28, 2006-02-15

  東京 : 情報処理学会

キーワード

• 進化的計算

詳細情報

• CRID: 1050001337891755520
• NII論文ID: 110004078693
• NII書誌ID: AA11464803
• ISSN: 18827780
• ISSN: 03875806
• NDL書誌ID: 7842427
• Web Site: http://id.nii.ac.jp/1001/00017167/
• Web Site: http://id.ndl.go.jp/bib/7842427
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7842427
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles