research-article

Simulated annealing, its parameter settings and the longest common subsequence problem

Author:

Dennis WeylandAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 803 - 810

https://doi.org/10.1145/1389095.1389253

Published: 12 July 2008 Publication History

Get Access

Abstract

Simulated Annealing is a probabilistic search heuristic for solving optimization problems and is used with great success on real life problems. In its standard form Simulated Annealing has two parameters, namely the initial temperature and the cooldown factor. In literature there are only rules of the thumb for choosing appropriate parameter values. This paper investigates the influence of different values for these two parameters on the optimization process from a theoretical point of view and presents some criteria for problem specific adjusting of these parameters.

With these results the performance of the Simulated Annealing algorithm on solving the Longest Common Subsequence Problem is analysed using different values for the two parameters mentioned above. For all these parameter settings it is proved that even rather simple input instances of the Longest Common Subsequence Problem can neither be solved to optimality nor approximately up to an approximation factor arbitrarily close to 2 efficiently.

References

[1]

H.-G. Beyer, H.-P. Schwefel, and I. Wegener. How to analyze evolutionary algorithms. Theoretical Computer Science, 287(1):101--130, 2002.

Digital Library

Google Scholar

[2]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.

Digital Library

Google Scholar

[3]

O. Giel and I. Wegener. Maximum cardinality matchings on trees by randomized local search. In Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference (GECCO 2006), pages 539--546, 2006

Digital Library

Google Scholar

[4]

T. Hagerup and C. Rüb. A guided tour of chernoff bounds. Information Processing Letters, 33(6):305--308, 1990.

Digital Library

Google Scholar

[5]

B. Hinkemeyer and B. A. Julstrom. A genetic algorithm for the longest common subsequence problem. In Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference (GECCO 2006), pages 609--610, 2006.

Digital Library

Google Scholar

[6]

T. Jansen and D. Weyland. Analysis of evolutionary algorithms for the longest common subsequence problem. In GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 1, pages 939--946, London, 7-11 July 2007. ACM Press.

Digital Library

Google Scholar

[7]

B. A. Julstrom and B. Hinkemeyer. Starting from scratch: Growing longest common subsequences with evolution. In Proceedings of the 9th International Conference on Parallel Problem Solving From Nature (PPSN IX), pages 930--938, 2006.

Digital Library

Google Scholar

[8]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

Google Scholar

[9]

H. Mühlenbein. How evolutionary algorithms really work: Mutation and hillclimbing. In Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN II), pages 15--26, 1992.

Google Scholar

[10]

F. Neumann. Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Computers and Operations Research, 2007. To appear.

Digital Library

Google Scholar

[11]

F. Neumann and I. Wegener. Minimum spanning trees made easier via multi-objective optimization. Natural Computing, 5(3):305--319, 2006.

Digital Library

Google Scholar

[12]

J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, 3:349--366, 2004.

Crossref

Google Scholar

[13]

I. Wegener. Simulated annealing beats metropolis in combinatorial optimization. In ICALP, pages 589--601, 2005.

Digital Library

Google Scholar

[14]

K. Weicker. Evolutionäre Algorithmen. Teubner Verlag, 2002.

Google Scholar

Cited By

View all

Hammami F(2024)An efficient hybrid adaptive large neighborhood search method for the capacitated team orienteering problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123561249:PAOnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123561
Blackwell TSilva SPaquete L(2023)The Barrier Tree Benchmark: Many Basins and Double FunnelsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590478(13-20)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590478
Li SXu XTao RChen Y(2023)Binary array beam forming with simulated annealing methodSecond International Conference on Optoelectronic Information and Computer Engineering (OICE 2023)10.1117/12.2691253(10)Online publication date: 1-Aug-2023
https://doi.org/10.1117/12.2691253
Show More Cited By

Index Terms

Simulated annealing, its parameter settings and the longest common subsequence problem
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching

Recommendations

A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP - M-SA-QAP. The novelty of the ...
Beam-ACO for the Repetition-Free Longest Common Subsequence Problem
Artificial Evolution
Abstract
In this paper we propose a Beam-ACO approach for a combinatorial optimization problem known as the repetition-free longest common subsequence problem. Given two input sequences and over a finite alphabet , this problem concerns to find a longest ...
Solving the truck and trailer routing problem based on a simulated annealing heuristic

In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (...

Comments

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
573
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hammami F(2024)An efficient hybrid adaptive large neighborhood search method for the capacitated team orienteering problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123561249:PAOnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123561
Blackwell TSilva SPaquete L(2023)The Barrier Tree Benchmark: Many Basins and Double FunnelsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590478(13-20)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590478
Li SXu XTao RChen Y(2023)Binary array beam forming with simulated annealing methodSecond International Conference on Optoelectronic Information and Computer Engineering (OICE 2023)10.1117/12.2691253(10)Online publication date: 1-Aug-2023
https://doi.org/10.1117/12.2691253
Neumaier MKranemann SKazmeier BRudolph S(2022)Automated Piping in an Airbus A320 Landing Gear Bay Using Graph-Based Design LanguagesAerospace10.3390/aerospace90301409:3(140)Online publication date: 5-Mar-2022
https://doi.org/10.3390/aerospace9030140
Lee YCharitopoulos VThyagarajan KMorris IPinto JPapageorgiou L(2022)Integrated Production and Inventory Routing Planning of Oxygen Supply ChainsChemical Engineering Research and Design10.1016/j.cherd.2022.07.027Online publication date: Jul-2022
https://doi.org/10.1016/j.cherd.2022.07.027
Rojas JEspitia HBejarano L(2021)Design and Optimization of a Fuzzy Logic System for Academic Performance PredictionSymmetry10.3390/sym1301013313:1(133)Online publication date: 14-Jan-2021
https://doi.org/10.3390/sym13010133
Adi TBae HIskandar Y(2021)Interterminal Truck Routing Optimization Using Cooperative Multiagent Deep Reinforcement LearningProcesses10.3390/pr91017289:10(1728)Online publication date: 27-Sep-2021
https://doi.org/10.3390/pr9101728
Fabarisova AKartak V(2021)Tuning a Simulated Annealing Heuristic for Irregular Polyomino Tiling2021 Dynamics of Systems, Mechanisms and Machines (Dynamics)10.1109/Dynamics52735.2021.9653708(1-5)Online publication date: 9-Nov-2021
https://doi.org/10.1109/Dynamics52735.2021.9653708
Adi TIskandar YBae H(2020)Interterminal Truck Routing Optimization Using Deep Reinforcement LearningSensors10.3390/s2020579420:20(5794)Online publication date: 13-Oct-2020
https://doi.org/10.3390/s20205794
Huang CLi YYao X(2020)A Survey of Automatic Parameter Tuning Methods for MetaheuristicsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.292159824:2(201-216)Online publication date: Apr-2020
https://doi.org/10.1109/TEVC.2019.2921598
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

Beam-ACO for the Repetition-Free Longest Common Subsequence Problem

Solving the truck and trailer routing problem based on a simulated annealing heuristic

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations