List-Based Simulated Annealing Algorithm for Traveling Salesman Problem

Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. Parameters’ setting is a key factor for its performance, but it is also a tedious work. To simplify parameters setting, we present a list-based simulated annealing (...

Full description

Saved in:
Bibliographic Details
Published in:Computational Intelligence and Neuroscience 2016-01, Vol.2016 (2016), p.248-259-016
Main Authors: Zhong, Yiwen, Zhang, Ze-jun, Lin, Juan, Zhan, Shi-hua
Format: Article
Language:English
Subjects:
Algorithms
Cooling
Differential equations, Partial
Intelligence
Lists
Markov analysis
Mathematical research
Neighborhoods
Neural Networks (Computer)
Optimization
Schedules
Simulated annealing
Simulated annealing (Mathematics)
State of the art
Temperature
Travel
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3
cites cdi_FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3
container_end_page 259-016
container_issue 2016
container_start_page 248
container_title Computational Intelligence and Neuroscience
container_volume 2016
creator Zhong, Yiwen
Zhang, Ze-jun
Lin, Juan
Zhan, Shi-hua
description Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. Parameters’ setting is a key factor for its performance, but it is also a tedious work. To simplify parameters setting, we present a list-based simulated annealing (LBSA) algorithm to solve traveling salesman problem (TSP). LBSA algorithm uses a novel list-based cooling schedule to control the decrease of temperature. Specifically, a list of temperatures is created first, and then the maximum temperature in list is used by Metropolis acceptance criterion to decide whether to accept a candidate solution. The temperature list is adapted iteratively according to the topology of the solution space of the problem. The effectiveness and the parameter sensitivity of the list-based cooling schedule are illustrated through benchmark TSP problems. The LBSA algorithm, whose performance is robust on a wide range of parameter values, shows competitive performance compared with some other state-of-the-art algorithms.
doi_str_mv 10.1155/2016/1712630
format article
fullrecord <record><control><sourceid>gale_pubme</sourceid><recordid>TN_cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_4808530</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A510481683</galeid><airiti_id>P20160527002_201612_201709130017_201709130017_248_259_016</airiti_id><sourcerecordid>A510481683</sourcerecordid><originalsourceid>FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3</originalsourceid><addsrcrecordid>eNqNkktv1DAURiMEoqWwY40isUGC0Ou3s0EaKihIIzFSy9pykpsZV0lc7KSo_77OzDCUbqi8uH4cHdnXX5a9JvCRECFOKRB5ShShksGT7JhIrQpBFXt6mEtxlL2I8QpAKAH0eXZEFTAuBRxn50sXx-KzjdjkF66fOjum2WIY0HZuWOeLbu2DGzd93vqQXwZ7g9v9C9th7O2Qr4KvOuxfZs9a20V8ta8n2c-vXy7PvhXLH-ffzxbLwsqSjUXFua7bGjANBpQTgrxSijVQNViyUkhKoLWWYV2pplGqFpWFFlVdMYaiYifZp533eqp6bGocxmA7cx1cb8Ot8daZf08GtzFrf2O4Bi0YJMG7vSD4XxPG0fQu1th1dkA_RUMSB5JRQf6PKg281EywR6BKqyTm8wXePkCv_BSG1LSZkumP1Fa4p9ap0cYNrU-vqWepWQgCXKe_nakPO6oOPsaA7aERBMycDjOnw-zTkfA395t3gP_EIQHvd8DGDY397R6pw8Rga-_RZSm0TMBqB1iXMuT-PnQ1eyClFIBunWRbFJSEQaoPFlwbKkqTOHYHPQPexQ</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1776057753</pqid></control><display><type>article</type><title>List-Based Simulated Annealing Algorithm for Traveling Salesman Problem</title><source>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</source><source>Open Access: Wiley-Blackwell Open Access Journals</source><creator>Zhong, Yiwen ; Zhang, Ze-jun ; Lin, Juan ; Zhan, Shi-hua</creator><contributor>Franco, Leonardo</contributor><creatorcontrib>Zhong, Yiwen ; Zhang, Ze-jun ; Lin, Juan ; Zhan, Shi-hua ; Franco, Leonardo</creatorcontrib><description>Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. Parameters’ setting is a key factor for its performance, but it is also a tedious work. To simplify parameters setting, we present a list-based simulated annealing (LBSA) algorithm to solve traveling salesman problem (TSP). LBSA algorithm uses a novel list-based cooling schedule to control the decrease of temperature. Specifically, a list of temperatures is created first, and then the maximum temperature in list is used by Metropolis acceptance criterion to decide whether to accept a candidate solution. The temperature list is adapted iteratively according to the topology of the solution space of the problem. The effectiveness and the parameter sensitivity of the list-based cooling schedule are illustrated through benchmark TSP problems. The LBSA algorithm, whose performance is robust on a wide range of parameter values, shows competitive performance compared with some other state-of-the-art algorithms.</description><identifier>ISSN: 1687-5265</identifier><identifier>EISSN: 1687-5273</identifier><identifier>DOI: 10.1155/2016/1712630</identifier><identifier>PMID: 27034650</identifier><language>eng</language><publisher>Cairo, Egypt: Hindawi Limiteds</publisher><subject>Algorithms ; Cooling ; Differential equations, Partial ; Intelligence ; Lists ; Markov analysis ; Mathematical research ; Neighborhoods ; Neural Networks (Computer) ; Optimization ; Schedules ; Simulated annealing ; Simulated annealing (Mathematics) ; State of the art ; Temperature ; Travel ; Traveling salesman problem</subject><ispartof>Computational Intelligence and Neuroscience, 2016-01, Vol.2016 (2016), p.248-259-016</ispartof><rights>Copyright © 2016 Shi-hua Zhan et al.</rights><rights>COPYRIGHT 2016 John Wiley &amp; Sons, Inc.</rights><rights>Copyright © 2016 Shi-hua Zhan et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</rights><rights>Copyright © 2016 Shi-hua Zhan et al. 2016</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3</citedby><cites>FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3</cites><orcidid>0000-0002-9132-913X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1776057753/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1776057753?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>230,314,776,780,881,25731,27901,27902,36989,36990,44566,74869</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/27034650$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><contributor>Franco, Leonardo</contributor><creatorcontrib>Zhong, Yiwen</creatorcontrib><creatorcontrib>Zhang, Ze-jun</creatorcontrib><creatorcontrib>Lin, Juan</creatorcontrib><creatorcontrib>Zhan, Shi-hua</creatorcontrib><title>List-Based Simulated Annealing Algorithm for Traveling Salesman Problem</title><title>Computational Intelligence and Neuroscience</title><addtitle>Comput Intell Neurosci</addtitle><description>Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. Parameters’ setting is a key factor for its performance, but it is also a tedious work. To simplify parameters setting, we present a list-based simulated annealing (LBSA) algorithm to solve traveling salesman problem (TSP). LBSA algorithm uses a novel list-based cooling schedule to control the decrease of temperature. Specifically, a list of temperatures is created first, and then the maximum temperature in list is used by Metropolis acceptance criterion to decide whether to accept a candidate solution. The temperature list is adapted iteratively according to the topology of the solution space of the problem. The effectiveness and the parameter sensitivity of the list-based cooling schedule are illustrated through benchmark TSP problems. The LBSA algorithm, whose performance is robust on a wide range of parameter values, shows competitive performance compared with some other state-of-the-art algorithms.</description><subject>Algorithms</subject><subject>Cooling</subject><subject>Differential equations, Partial</subject><subject>Intelligence</subject><subject>Lists</subject><subject>Markov analysis</subject><subject>Mathematical research</subject><subject>Neighborhoods</subject><subject>Neural Networks (Computer)</subject><subject>Optimization</subject><subject>Schedules</subject><subject>Simulated annealing</subject><subject>Simulated annealing (Mathematics)</subject><subject>State of the art</subject><subject>Temperature</subject><subject>Travel</subject><subject>Traveling salesman problem</subject><issn>1687-5265</issn><issn>1687-5273</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNqNkktv1DAURiMEoqWwY40isUGC0Ou3s0EaKihIIzFSy9pykpsZV0lc7KSo_77OzDCUbqi8uH4cHdnXX5a9JvCRECFOKRB5ShShksGT7JhIrQpBFXt6mEtxlL2I8QpAKAH0eXZEFTAuBRxn50sXx-KzjdjkF66fOjum2WIY0HZuWOeLbu2DGzd93vqQXwZ7g9v9C9th7O2Qr4KvOuxfZs9a20V8ta8n2c-vXy7PvhXLH-ffzxbLwsqSjUXFua7bGjANBpQTgrxSijVQNViyUkhKoLWWYV2pplGqFpWFFlVdMYaiYifZp533eqp6bGocxmA7cx1cb8Ot8daZf08GtzFrf2O4Bi0YJMG7vSD4XxPG0fQu1th1dkA_RUMSB5JRQf6PKg281EywR6BKqyTm8wXePkCv_BSG1LSZkumP1Fa4p9ap0cYNrU-vqWepWQgCXKe_nakPO6oOPsaA7aERBMycDjOnw-zTkfA395t3gP_EIQHvd8DGDY397R6pw8Rga-_RZSm0TMBqB1iXMuT-PnQ1eyClFIBunWRbFJSEQaoPFlwbKkqTOHYHPQPexQ</recordid><startdate>20160101</startdate><enddate>20160101</enddate><creator>Zhong, Yiwen</creator><creator>Zhang, Ze-jun</creator><creator>Lin, Juan</creator><creator>Zhan, Shi-hua</creator><general>Hindawi Limiteds</general><general>Hindawi Publishing Corporation</general><general>John Wiley &amp; Sons, Inc</general><general>Hindawi Limited</general><scope>188</scope><scope>ADJCN</scope><scope>AHFXO</scope><scope>RHU</scope><scope>RHW</scope><scope>RHX</scope><scope>CGR</scope><scope>CUY</scope><scope>CVF</scope><scope>ECM</scope><scope>EIF</scope><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7QF</scope><scope>7QQ</scope><scope>7SC</scope><scope>7SE</scope><scope>7SP</scope><scope>7SR</scope><scope>7TA</scope><scope>7TB</scope><scope>7TK</scope><scope>7U5</scope><scope>7X7</scope><scope>7XB</scope><scope>8AL</scope><scope>8BQ</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FH</scope><scope>8FI</scope><scope>8FJ</scope><scope>8FK</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BBNVY</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>BHPHI</scope><scope>CCPQU</scope><scope>CWDGH</scope><scope>DWQXO</scope><scope>F28</scope><scope>FR3</scope><scope>FYUFA</scope><scope>GHDGH</scope><scope>GNUQQ</scope><scope>H8D</scope><scope>H8G</scope><scope>HCIFZ</scope><scope>JG9</scope><scope>JQ2</scope><scope>K7-</scope><scope>K9.</scope><scope>KR7</scope><scope>L6V</scope><scope>L7M</scope><scope>LK8</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M0S</scope><scope>M1P</scope><scope>M7P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PSYQQ</scope><scope>PTHSS</scope><scope>Q9U</scope><scope>7X8</scope><scope>5PM</scope><orcidid>https://orcid.org/0000-0002-9132-913X</orcidid></search><sort><creationdate>20160101</creationdate><title>List-Based Simulated Annealing Algorithm for Traveling Salesman Problem</title><author>Zhong, Yiwen ; Zhang, Ze-jun ; Lin, Juan ; Zhan, Shi-hua</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Algorithms</topic><topic>Cooling</topic><topic>Differential equations, Partial</topic><topic>Intelligence</topic><topic>Lists</topic><topic>Markov analysis</topic><topic>Mathematical research</topic><topic>Neighborhoods</topic><topic>Neural Networks (Computer)</topic><topic>Optimization</topic><topic>Schedules</topic><topic>Simulated annealing</topic><topic>Simulated annealing (Mathematics)</topic><topic>State of the art</topic><topic>Temperature</topic><topic>Travel</topic><topic>Traveling salesman problem</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Zhong, Yiwen</creatorcontrib><creatorcontrib>Zhang, Ze-jun</creatorcontrib><creatorcontrib>Lin, Juan</creatorcontrib><creatorcontrib>Zhan, Shi-hua</creatorcontrib><collection>華藝線上圖書館</collection><collection>الدوريات العلمية والإحصائية - e-Marefa Academic and Statistical Periodicals</collection><collection>معرفة - المحتوى العربي الأكاديمي المتكامل - e-Marefa Academic Complete</collection><collection>Hindawi Publishing Complete</collection><collection>Hindawi Publishing Subscription Journals</collection><collection>Hindawi Publishing Open Access Journals</collection><collection>Medline</collection><collection>MEDLINE</collection><collection>MEDLINE (Ovid)</collection><collection>MEDLINE</collection><collection>MEDLINE</collection><collection>PubMed</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Aluminium Industry Abstracts</collection><collection>Ceramic Abstracts</collection><collection>Computer and Information Systems Abstracts</collection><collection>Corrosion Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Engineered Materials Abstracts</collection><collection>Materials Business File</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Neurosciences Abstracts</collection><collection>Solid State and Superconductivity Abstracts</collection><collection>ProQuest - Health &amp; Medical Complete保健、医学与药学数据库</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Computing Database (Alumni Edition)</collection><collection>METADEX</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>Hospital Premium Collection</collection><collection>Hospital Premium Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>Biological Science Collection</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest One Community College</collection><collection>Middle East &amp; Africa Database</collection><collection>ProQuest Central</collection><collection>ANTE: Abstracts in New Technology &amp; Engineering</collection><collection>Engineering Research Database</collection><collection>Health Research Premium Collection</collection><collection>Health Research Premium Collection (Alumni)</collection><collection>ProQuest Central Student</collection><collection>Aerospace Database</collection><collection>Copper Technical Reference Library</collection><collection>SciTech Premium Collection</collection><collection>Materials Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>ProQuest Health &amp; Medical Complete (Alumni)</collection><collection>Civil Engineering Abstracts</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Biological Sciences</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>Health &amp; Medical Collection (Alumni Edition)</collection><collection>Medical Database</collection><collection>Biological Science Database</collection><collection>ProQuest Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ProQuest One Psychology</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><collection>MEDLINE - Academic</collection><collection>PubMed Central (Full Participant titles)</collection><jtitle>Computational Intelligence and Neuroscience</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Zhong, Yiwen</au><au>Zhang, Ze-jun</au><au>Lin, Juan</au><au>Zhan, Shi-hua</au><au>Franco, Leonardo</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>List-Based Simulated Annealing Algorithm for Traveling Salesman Problem</atitle><jtitle>Computational Intelligence and Neuroscience</jtitle><addtitle>Comput Intell Neurosci</addtitle><date>2016-01-01</date><risdate>2016</risdate><volume>2016</volume><issue>2016</issue><spage>248</spage><epage>259-016</epage><pages>248-259-016</pages><issn>1687-5265</issn><eissn>1687-5273</eissn><abstract>Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. Parameters’ setting is a key factor for its performance, but it is also a tedious work. To simplify parameters setting, we present a list-based simulated annealing (LBSA) algorithm to solve traveling salesman problem (TSP). LBSA algorithm uses a novel list-based cooling schedule to control the decrease of temperature. Specifically, a list of temperatures is created first, and then the maximum temperature in list is used by Metropolis acceptance criterion to decide whether to accept a candidate solution. The temperature list is adapted iteratively according to the topology of the solution space of the problem. The effectiveness and the parameter sensitivity of the list-based cooling schedule are illustrated through benchmark TSP problems. The LBSA algorithm, whose performance is robust on a wide range of parameter values, shows competitive performance compared with some other state-of-the-art algorithms.</abstract><cop>Cairo, Egypt</cop><pub>Hindawi Limiteds</pub><pmid>27034650</pmid><doi>10.1155/2016/1712630</doi><orcidid>https://orcid.org/0000-0002-9132-913X</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1687-5265
ispartof Computational Intelligence and Neuroscience, 2016-01, Vol.2016 (2016), p.248-259-016
issn 1687-5265
1687-5273
language eng
recordid cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_4808530
source Publicly Available Content Database (Proquest) (PQ_SDU_P3); Open Access: Wiley-Blackwell Open Access Journals
subjects Algorithms
Cooling
Differential equations, Partial
Intelligence
Lists
Markov analysis
Mathematical research
Neighborhoods
Neural Networks (Computer)
Optimization
Schedules
Simulated annealing
Simulated annealing (Mathematics)
State of the art
Temperature
Travel
Traveling salesman problem
title List-Based Simulated Annealing Algorithm for Traveling Salesman Problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-01T14%3A51%3A08IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_pubme&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=List-Based%20Simulated%20Annealing%20Algorithm%20for%20Traveling%20Salesman%20Problem&rft.jtitle=Computational%20Intelligence%20and%20Neuroscience&rft.au=Zhong,%20Yiwen&rft.date=2016-01-01&rft.volume=2016&rft.issue=2016&rft.spage=248&rft.epage=259-016&rft.pages=248-259-016&rft.issn=1687-5265&rft.eissn=1687-5273&rft_id=info:doi/10.1155/2016/1712630&rft_dat=%3Cgale_pubme%3EA510481683%3C/gale_pubme%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a693t-b448cfc0e0e0302411e4b773d0bde93956210faa3ecb7dd77c5ba0fe7cb33e5b3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1776057753&rft_id=info:pmid/27034650&rft_galeid=A510481683&rft_airiti_id=P20160527002_201612_201709130017_201709130017_248_259_016&rfr_iscdi=true