多目的遺伝的アルゴリズムにおける近傍交叉の効果

• 吉井, 健吾

• 廣安, 知之

• 三木, 光範

書誌事項

タイトル別名

• タモクテキ イデンテキ アルゴリズム ニ オケル キンボウ コウサ ノ コウカ
• Effectiveness of Neighborhood Crossover in EMO Algorithms

抄録

本稿は進化的多目的最適化（Evolutionary Multiobjective Optimization: EMO）における近傍交叉の効果を数値実験を通してまとめたものである．近傍交叉は目的関数空間において近接している個体どうしで交叉を行う．すべての個体は目的関数空間において近接している順にソートされた後，母集団のある一定間隔の幅において個体をランダムに入れ替える近傍シャッフルが行われる．この近傍シャッフルは，複数の世代にわたって繰り返し同じペアで交叉が行われることを防ぐために行われる操作である．ここで近傍シャッフルを行う幅はパラメータであり，この近傍シャッフル幅の大きさによって個体間の近傍度合いは変化し，解の探索への影響も変化する．そこで，本研究では代表的なEMO の手法であるNSGA-II に近傍交叉を組み込み，テスト関数により近傍シャッフル幅の変化による探索能力の検討を行った．数値実験の結果，メイティング選択としてコピー選択により生成された母集団に近傍交叉を適用するとき，母集団の多様性を維持しながら探索を行うことが可能となることが分かった．そして対象問題によって最適な近傍シャッフル幅が異なって存在し，最適な大きさの近傍シャッフル幅による近傍シャッフルを行ったとき，最も優れたパレート最適解集合が得られることを確認した．

In this work, the effectiveness of the neighborhood crossover of EMO algorithms is discussed through the numerical experiments. The neighborhood crossover chooses two parents which are close to each other in the objective space. All individuals are sorted with along to their distances and the neighborhood shuffle which changes individuals randomly in certain width of population is carried out. This operation prevents crossing over repeatedly between the same pair of individuals. The width of neighborhood shuffle is the parameter of this operation and this parameter determines the range of the population where individuals are shuffled. Therefore, this parameter affects the quality of the solutions. We implemented the NSGA-II with the neighborhood crossover and examined the effect of the width of neighborhood shuffle. The results of the numerical experiment indicated that the effect of neighborhood crossover can be achieved by applying neighborhood crossover to the search population created through copy selection as mating selection. In addition, we found that the optimal width of neighborhood shuffle differs by the objective problems, and the best pareto optimal solutions are obtained when the neighborhood shuffle is conducted with the optimal width of neighborhood shuffle.

収録刊行物

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

  情報処理学会論文誌数理モデル化と応用（TOM） 48 (SIG2(TOM16)), 40-48, 2007-02-15

  東京 : 情報処理学会

キーワード

• シンポジウム特集論文

詳細情報

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