Solving the Traveling Salesman Problem Using Kuramoto Oscillators

DOI

Abstract

In this study, a single Kuramoto oscillator was considered as a city, and the traveling salesman problem was tackled using exclusive interactions between oscillators. Computer experiments showed that the phase relations that converged regardless of the number of oscillators were broadly classi-fied into two types: solutions that reflected the shortest path or a path close to it and two-cluster solutions that were divided into two groups with a phase difference π. In both cases, the solutions obtained were determined by the distance between the cities implemented as the strength of the exclusivity between the oscillators and did not depend on the initial value of the calculation. The results of these computer experiments and the discussion of the potentials indicate that the oscillator system always converges to a global solution. Since oscillatory phenomena are widely observed in living systems, the results of this study sug-gest that the interaction between oscillators is crucial for obtaining a globally good solution/state for a living sys-tem.

Journal

  • IEICE Proceeding Series

    IEICE Proceeding Series 76 362-365, 2023-09-21

    The Institute of Electronics, Information and Communication Engineers

Keywords

Details 詳細情報について

  • CRID
    1390297847284654208
  • DOI
    10.34385/proc.76.b4l-31
  • ISSN
    21885079
  • Text Lang
    en
  • Data Source
    • JaLC
  • Abstract License Flag
    Disallowed

Report a problem

Back to top