The influence of problem specific neighborhood structures in metaheuristics performance

DOI10.1155/2018/8072621MaRDI QIDQ2337103zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 19 November 2019

Published in Journal of Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2018/8072621

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: Metaheuristics (MH) aptitude to move past local optimums makes them an attractive technique to approach complex computational problems, such as the Travelling Salesman Problem (TSP), but there is lack of information on the parameterization procedure and the appropriate parameters to improve MHs' performance. In this paper the parameterization procedure of Simulated Annealing (SA) and Discrete Artificial Bee Colony (DABC) is addressed, with a focus on the Neighborhood Structure (NS). Numerous NS have been proposed for specific problems, which seem to indicate that the NS is a special parameter, whose optimization is independent of other parameters. The performance of eight NS was examined with SA and DABC under two optimization constraints, regarding computational time variation, to determine if there is one appropriate NS for the TSP problem, independent of the rest of the parameters of the optimization procedure. The computational study carried out for comparing the evaluation of the NS, including a statistical analysis, demonstrated a nonproportional increase in the performance of DABC with some NS. For SA the improvement of the solutions appeared to be more uniform with an almost nonexistent variance in improvement.

Recommendations

• A note on the effect of neighborhood structure in simulated annealing
• A new simulated annealing approach for travelling salesman problem
• Variable neighborhood search
• Variable neighbourhood structures for cycle location problems
• scientific article; zbMATH DE number 1488085

Cites work

• A method for solving traveling-salesman problems
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• A survey of very large-scale neighborhood search techniques
• A survey on optimization metaheuristics
• A systematic procedure for setting parameters in simulated annealing algorithms
• An Algorithm for the Traveling Salesman Problem
• Computer Solutions of the Traveling Salesman Problem
• Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search
• Fuzzy soft compact topological spaces
• Handbook of metaheuristics
• scientific article; zbMATH DE number 2134711 (Why is no real title available?)
• scientific article; zbMATH DE number 1054925 (Why is no real title available?)
• Improving genetic algorithm with fine-tuned crossover and scaled architecture
• Inner product over fuzzy matrices
• Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem
• Metaheuristics. From design to implementation.
• On complex intuitionistic fuzzy soft sets with distance measures and entropies
• Optimization by simulated annealing
• Particle swarm optimization-based algorithms for TSP and generalized TSP
• Scheduling. Theory, algorithms, and systems.
• Simulated annealing methods with general acceptance probabilities
• Simulated annealing: A tool for operational research
• Solution of a Large-Scale Traveling-Salesman Problem
• The traveling salesman problem: An overview of exact and approximate algorithms
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(2)

• Using group theory and transition matrices to study a class of metaheuristic neighborhoods
• Meta-analysis of metaheuristics: quantifying the effect of adaptiveness in adaptive large neighborhood search

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: The influence of problem specific neighborhood structures in metaheuristics performance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2337103)