大規模な最大多様性問題に対する遺伝的局所探索

• Item type: Trans(1)
• 公開日: 2004-02-15
• タイトル: 大規模な最大多様性問題に対する遺伝的局所探索
• タイトル / 言語: en
• タイトル: A Genetic Local Search for Large Maximum Diversity Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 局所探索
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 岡山理科大学工学部情報工学科
• 著者所属: 岡山理科大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Engineering, Okayama University of Science
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Engineering, Okayama University of Science
• 著者名: 片山, 謙吾; 成久, 洋之
• 著者名(英): Kengo, Katayama; Hiroyuki, Narihisa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最大多様性問題（maximum diversity problem，MDP）とは，与えられたn個の要素からm個の要素を選ぶとき，できるだけ多様性を有するように要素を選定する問題である．本論文では，MDPに対する遺伝的局所探索法（genetic local search，GLS）を示す．本GLSでは，交叉および突然変異の各操作後に生成される解に対して実行可能解変換操作（リペア法）を施し，解の実行可能性を保証する．その後，LinとKernighanによる可変深度探索のアイデアに基づくk-flip局所探索法を適用することで，高品質な局所最適解の集団を構成しながら探索を進める．既存研究で対象とされた問題規模よりもはるかに大規模な2500変数までの問題例に対して本GLSをテストし，2-flip局所探索法をベースにした変形GLS よりも平均的に良好な解を算出可能であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a genetic local search (GLS) - genetic algorithm incorporating local search - for the maximum diversity problem (MDP). To guarantee feasibility of solutions, a repair method is used in the GLS and is applied to a solution after crossover or mutation operator. In a process of local search of the GLS, we perform a sophisticated, k-flip local search based on an idea of variable depth search by Lin and Kernighan. Computational results show that the GLS with k-flip local search is capable of finding better solutions on average than a GLS with a simple 2-flip local search for large-sized problem instances of up to 2500 variables.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 45, 号 SIG02(TOM10), p. 99-109, 発行日 2004-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会