Journal of the Japanese Society for Artificial Intelligence
Online ISSN : 2435-8614
Print ISSN : 2188-2266
Print ISSN:0912-8085 until 2013
Two Comments on the Subtour Exchange Crossover Operator
Mitusnori YAGIURAHiroshi NAGAMOCHIToshihide IBARAKI
Author information
MAGAZINE FREE ACCESS

1995 Volume 10 Issue 3 Pages 464-467

Details
Abstract

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. [山村92] is based on such common subtours. In this note, we present an O(n^2) 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).

Content from these authors
© 1995 The Japaense Society for Artificial Intelligence
Previous article Next article
feedback
Top