Greedy Genetic Algorithms for Symmetric and Asymmetric TSPs (特集 進化的計算)

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents new enhancements to a multi-population GENITOR-type Genetic Algorithm (GA) for solving symmetric and asymmetric Traveling Salesman Problems (TSPs). First, improvements to the greedy subtour crossover are proposed so that it works more effectively at the stage of highly fit individuals. Next, local search heuristics are combined with GA to compensate for its lack of local search ability. The powerful Lin-Kernighan heuristic is used for symmetric TSPs and the fast 3-Opt heuristic is used for asymmetric TSPs. Various symmetric and asymmetric TSP benchmarks taken from the TSPLIB are used to validate the method. Experimental results show that the proposed method can find optimal solutions for problems ranging in size up to 3795 cities in a reasonable computing time. From the viewpoint of quality of solution, these results are the best so far obtained by applying GA to the TSP.

• 一般社団法人情報処理学会の論文
• 2002-11-15

著者

• Nguyen H

  Graduate School Of Engineering University Of Miyazaki:(present Office)frontier Science Research Cent

• NGUYEN Hung

  Graduate School of Engineering, University of Miyazaki

• YOSHIHARA Ikuo

  Faculty of Engineering, University of Miyazaki

• YAMAMORI Kunihito

  Faculty of Engineering, University of Miyazaki

• YASUNAGA Moritoshi

  Graduate School of Systems and Information Engineering, University of Tsukuba

• Yasunaga Moritoshi

  Institute of Information Sciences and Electronics, Tsukuba University

• Yasunaga Moritoshi

  Graduate School Of Systems And Information Engineering University Of Tsukuba

• Yasunaga Moritoshi

  Institute Of Information Sciences And Electronics Tsukuba University

• Yasunaga Moritoshi

  The Institute Of Information Sciences And Electronics University Of Tsukuba

• Yasunaga Moritoshi

  Institute Of Information Science And Electronics University Of Tsukuba

• Yoshihara Ikuo

  Faculty Of Engineering Miyazaki University

• Kamimai Yoshiyuki

  Faculty Of Engineering University Of Miyazaki

• Yamamori Kunihito

  Faculty Of Engineering Miyazaki University

• Nguyen Hung

  Graduate School Of Engineering Miyazaki University

関連論文

• Characteristics of International Grain Price Movements under the High Oil Prices : Toward Policy Implications
• A New Three-Level Tree Data Structure for Representing TSP Tours in the Lin-Kernighan Heuristic(Optimization,Nonlinear Theory and its Applications)
• A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic
• Greedy Genetic Algorithms for Symmetric and Asymmetric TSPs (特集 進化的計算)
• A GA-based method for multiple protein sequence alignment
• A parallel greedy GA for symmetric and asymmetric TSPs
• Directed Edge Recombination and Hybrid Genetic Algorithm for Asymmetric Traveling Salesman Problems
• Extracting Transcription Regulatory Elements in Dictyostelium Discoideum
• Finding Characteristic Patterns Embedded in Non-transcribed Region of Dictyostelium Discoideum by Computed Moire
• Feature Extraction from Non-transcribed Region of Dictyostelium Discoideum using Moire Picture
• The Kernel-Based Pattern Recognition System Designed by Genetic Algorithms(Special Issue on Function Integrated Information Systems)
• The Evolutionary Algorithm-Based Reasoning System(Special Issue on Function Integrated Information Systems)
• Development of Exon Region Extracting Method by GMDH and GA from DNA Sequences
• GMDH-GA Hybrid Model Extracting Exon Region from DNA Sequences
• Construction of GMDH-based Prediction model using GA
• GP-Based Method for Extracting Exons from DNA Sequence
• Evaluation of GP-based time series prediction
• Segmentation and GA-based Optimization of Transmission-Line on Printed Circuit Board
• English Pronunciation Reasoning by NN Considering Frequency Distribution of Phonemes
• Multi-Modal Neural Networks for Symbolic Sequence Pattern Classification(Biocybernetics, Neurocomputing)
• Prediction of Protein Secondary Structure Based on a Multi-modal Neural Network: with Modified Profiles of MSA and PSSM
• Development of a multi-modal nueral network for predicting protein secondary structure
• Research on identifying intron-exon boundaries in DNA sequences
• Performance Evaluation of Neural Network Hardware Using Time-Shared Bus and Integer Representation Architecture
• A Physiology Activity Value Prediction of Functional Foods Using Bayes Classifier
• An Efficient Job Scheduling Algorithm for Grid Environment with Communication Delay
• GA-based University Timetabling for Constraint Satisfaction
• Estimating Physiology Activity of Functional Foods with Self-Organizing Map
• Evaluation of Edge Assembly Crossover for Hybrid GA
• Timetabling for University Classes using Genetic Algorithm
• A High-Signal-Integrity PCB Trace Composed of Multiple Segments for GHz VLSI Packaging: Its Prototyping and Performance Analysis

もっと見る 閉じる

スポンサーリンク