Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

An evolutionary algorithm for large traveling salesman problems.

Huai-Kuang Tsai1, Jinn-Moon Yang, Yuan-Fang Tsai

  • 1Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan, ROC. d7526010@csie.ntu.edu.tw

IEEE Transactions on Systems, Man, and Cybernetics. Part B, Cybernetics : a Publication of the IEEE Systems, Man, and Cybernetics Society
|October 7, 2004
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

DNA-DETR: sequence representation matters in object detection for functional genomic elements.

Briefings in bioinformatics·2026
Same author

Blue laser turbinate reduction with vs. without posterior nasal neurolysis for refractory rhinitis: a retrospective comparative study.

European archives of oto-rhino-laryngology : official journal of the European Federation of Oto-Rhino-Laryngological Societies (EUFOS) : affiliated with the German Society for Oto-Rhino-Laryngology - Head and Neck Surgery·2026
Same author

Clinical Performance of a Smartphone-Based Sound Amplification Device Versus a Personal Sound Amplification Product in Elders with Mild-to-Moderate Hearing Loss: A Prospective Cohort Study.

Medicina (Kaunas, Lithuania)·2026
Same author

Blue laser inferior turbinate reduction for medically refractory chronic rhinitis: a retrospective analysis of clinical outcomes and optimal energy settings.

Lasers in medical science·2026
Same author

Complete end-to-end learning from protein feature representation to protein interactome inference.

GigaScience·2025
Same author

Integrated Genomic Approaches to Elucidate the Genetic Basis of Brugada Syndrome in Taiwanese Patients.

Bioinformatics and biology insights·2025
Same journal

Strategic Ability Updating in Concurrent Games by Coalitional Commitment.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2015
Same journal

Meta-Analysis of the First Facial Expression Recognition Challenge.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

Adjustable model-based fusion method for multispectral and panchromatic images.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

Face Feature Weighted Fusion Based on Fuzzy Membership Degree for Video Face Recognition.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

A New Adaptive Fast Cellular Automaton Neighborhood Detection and Rule Identification Algorithm.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

Human-arm-and-hand-dynamic model with variability analyses for a stylus-based haptic interface.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
See all related articles

A new evolutionary algorithm, the heterogeneous selection evolutionary algorithm (HeSEA), effectively solves large Traveling Salesman Problems (TSP). It combines edge assembly crossover (EAX) and Lin-Kernighan (LK) for robust and near-optimal tour discovery.

Area of Science:

  • Computational Intelligence
  • Operations Research
  • Combinatorial Optimization

Background:

  • Traveling Salesman Problems (TSP) are computationally challenging, especially for large instances.
  • Existing evolutionary algorithms and local search methods have limitations in solving large-scale TSPs.
  • Analysis of genetic operators and local search techniques reveals opportunities for improvement.

Purpose of the Study:

  • To propose a novel evolutionary algorithm, the heterogeneous selection evolutionary algorithm (HeSEA), for large Traveling Salesman Problems (TSP).
  • To integrate effective genetic operators and local search methods to overcome individual limitations.
  • To enhance population diversity and maintain solution quality for large TSP instances.

Main Methods:

  • Development of the heterogeneous selection evolutionary algorithm (HeSEA).

Related Experiment Videos

  • Integration of edge assembly crossover (EAX) and Lin-Kernighan (LK) local search.
  • Implementation of family competition and heterogeneous pairing selection strategies for population diversity.

    • Main Results:

    • HeSEA demonstrates strong performance on 16 benchmark TSPs with up to 13,509 cities.
    • The algorithm achieves near-optimal solutions, within 0.0074% of the optimum on average.
    • HeSEA successfully finds optimal paths for TSPs with fewer than 10,000 cities.

    Conclusions:

    • HeSEA effectively compensates for the disadvantages of EAX and LK through synergistic integration.
    • Family competition and heterogeneous pairing selection are crucial for maintaining population diversity in large TSPs.
    • HeSEA offers a robust and efficient approach for solving large Traveling Salesman Problems within reasonable computational time.