サブツアー交換交叉に対する2つのコメント

柳浦 睦憲, 永持 仁, 茨木 俊秀
アブストラクト
Given two tours of n cities, a pair of subtours of these tours consisting of the same set of cities is called a common subtour. The operation of subtour exchange crossover used in the genetic algorithm of Yamamura et al. [Yamamura et al. 92] is based on such common subtours. In this note, we present an O(n2) time algorithm to enumerate all common subtours, and show that the expected number of common subtours for two random tours is at most 4+o(1).

Key Words: genetic algorithm, subtour exchange crossover.

人工知能学会誌, Vol. 10 (1995) 464-467.

PSファイル


論文リストへ