組合せ最適化問題における内挿/外挿的な領域への遺伝的多段階探索の有効性

• Item type: Journal(1)
• 公開日: 2006-10-15
• タイトル: 組合せ最適化問題における内挿/外挿的な領域への遺伝的多段階探索の有効性
• タイトル / 言語: en
• タイトル: Effectiveness of Genetic Multi-step Search in Interpolation and Extrapolation Domain for Combinatorial Optimization Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: アルゴリズム理論
• 著者所属: 同志社大学大学院/日本学術振興会特別研究員
• 著者所属: 同志社大学工学部
• 著者所属: 同志社大学工学部
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Doshisha University/JSPS Research Fellow
• 著者所属(英): en
• 著者所属(英): Department of Engineering, Doshisha University
• 著者所属(英): en
• 著者所属(英): Department of Engineering, Doshisha University
• 著者名: 花田, 良子; 廣安, 知之; 三木, 光範
• 著者名(英): Yoshiko, Hanada; Tomoyuki, Hiroyasu; Mitsunori, Miki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: dMSXF はJSP における有効な交叉の1 つであるMSXF を改良した交叉であり，TSP において非常に良好な解探索性能を示している．MSXF，dMSXF はいずれも，順序付け問題において問題固有の近傍構造および距離を導入し，両親の形質遺伝を目的とした多段階交叉である．これらは内挿的な交叉であるため両親の距離が近すぎる場合には有効に働かない．そのためMSXF ではその相補的な操作として外挿的な領域への多段階探索であるMSMF を併用することで，その性能を向上させている．一方，dMSXF は多段階探索交叉を決定的に行う手法であり，MSMF の仕組みについては採用されていない．本論文ではdMSXF の相補的な操作である外挿領域への決定的な多段階探索dMSMF を提案する．異なる構造を持つ2 種の代表的な組合せ最適化問題TSP，JSP においてdMSXF+dMSMF の有効性を示すことで，内挿領域および外挿領域への決定的な多段階探索を組み合わせることで有効な探索が実現できることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The dMSXF is an improved crossover method of MSXF which is one of promising methods of JSP, and it shows high availability in TSP. Both of these crossover methods introduce a neighborhood structure and distance in each permutation problem and perform multi-step searches in the interpolation domain focusing on inheritance of parents’ characteristic. They cannot work effectively when parents stand close each other since they search in interpolation domain. Therefore in the case of the MSXF, the MSMF, which is the multi-step search in the extrapolation domain, is combined as the complementary search to improve their search performance. On the other hand, the dMSXF just performs deterministic multi-step search and the mechanism of the MSMF is not applied. In this paper, we introduce a deterministic MSMF mechanism as complementary multi-step extrapolation search. We apply dMSXF+dMSMF to TSP and JSP, which have structural difference between their landscapes. Through the experiments it was shown that the deterministic multi-step search in interpolation/extrapolation domain performed effectively in combinatorial problems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 47, 号 10, p. 2897-2908, 発行日 2006-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764