複雑なビルディングブロック重複を持つ問題に対する交叉手法の提案

情報処理学会 Web Site 被引用文献1件 参考文献21件

書誌事項

タイトル別名
  • A Proposal of Crossover Method for Complex Building Blocks Overlapping
  • フクザツナ ビルディング ブロック チョウフク オ モツ モンダイ ニ タイスル コウサ シュホウ ノ テイアン

この論文をさがす

説明

遺伝的アルゴリズムによる効率的な探索のために， 同一のビルディングブロック（building block，BB）を構成する遺伝子座の集合を検出する手法は多く提案されている（Heckendornら）．しかしながら，これらの手法から得られたリンケージ情報を利用して効果的に交叉を行う方法については，十分な検討がなされてこなかった．特に重複する BB を持つ問題では Yu ら（2005）の交叉手法のみが知られている．しかし，彼らの手法は BB の重複構造が複雑になったとき，頻繁に BB を破壊し，かつ十分な交叉パターンが得られないために，効率的に機能しない．本論文では，Yu らの手法を拡張し，BB 破壊をできるだけ抑えながら，新たな異なる探索点を与える交叉手法を提案する．提案される手法は，コンテクスト依存交叉（Context Dependent Crossover，CDC）と呼ばれ，与えられた親個体組の値を調査したうえで，交換する遺伝子座を決定する．CDC は，リンケージ同定手法と併用されることで，重複する BB を持つ問題を探索する強力なアルゴリズムを提供する．また，提案手法の性能を確認するために，重複の複雑さが制御可能なテスト関数を設計する．

In order to realize effective genetic algorithms, there have been several techniques to identify linkage sets of loci to form a building block (BB) (Heckendorn, et al.). By contrast, the way to realize effective crossover from the linkage information given by such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu, et al. (2005) is the first and only known research. However it cannot perform well for problems with complexly overlapping BBs due to BB disruptions and insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings to determine which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. Because the proposed method considers the context of parental strings, it is called context dependent crossover (CDC). Combining a scalable linkage identification technique and the CDC, an effective algorithm for problems with overlapping BBs is provided. Moreover, to test the proposed method, we design test functions with controllable complexity of overlaps.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (21)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ