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

IPSJ Web Site 1 Citations 25 References

Bibliographic Information

Other Title
  • クミアワセ サイテキカ モンダイ ニ オケル ナイソウ ガイソウテキ ナ リョウイキ エ ノ イデンテキ タダンカイ タンサク ノ ユウコウセイ
  • Effectiveness of Genetic Multi-step Search in Interpolation and Extrapolation Domain for Combinatorial Optimization Problems
  • アルゴリズム理論

Search this article

Abstract

dMSXF はJSP における有効な交叉の1 つであるMSXF を改良した交叉であり，TSP において非常に良好な解探索性能を示している．MSXF，dMSXF はいずれも，順序付け問題において問題固有の近傍構造および距離を導入し，両親の形質遺伝を目的とした多段階交叉である．これらは内挿的な交叉であるため両親の距離が近すぎる場合には有効に働かない．そのためMSXF ではその相補的な操作として外挿的な領域への多段階探索であるMSMF を併用することで，その性能を向上させている．一方，dMSXF は多段階探索交叉を決定的に行う手法であり，MSMF の仕組みについては採用されていない．本論文ではdMSXF の相補的な操作である外挿領域への決定的な多段階探索dMSMF を提案する．異なる構造を持つ2 種の代表的な組合せ最適化問題TSP，JSP においてdMSXF+dMSMF の有効性を示すことで，内挿領域および外挿領域への決定的な多段階探索を組み合わせることで有効な探索が実現できることを示す．

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.

Journal

Citations (1)*help

See more

References(25)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top