Loading…

Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator

Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for NP-hard problems, especially the travel...

Full description

Saved in:
Bibliographic Details
Published in:Computational Intelligence and Neuroscience 2017-01, Vol.2017 (2017), p.1-7
Main Authors: Mohamd Shoukry, Alaa, Hussain, Ijaz, Nauman Sajid, M., Shad, Muhammad Yousaf, Hussain, Abid, Gani, Showkat
Format: Article
Language:English
Subjects:
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-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493
cites cdi_FETCH-LOGICAL-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493
container_end_page 7
container_issue 2017
container_start_page 1
container_title Computational Intelligence and Neuroscience
container_volume 2017
creator Mohamd Shoukry, Alaa
Hussain, Ijaz
Nauman Sajid, M.
Shad, Muhammad Yousaf
Hussain, Abid
Gani, Showkat
description Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. The genetic algorithm depends on selection criteria, crossover, and mutation operators. To tackle the traveling salesman problem using genetic algorithms, there are various representations such as binary, path, adjacency, ordinal, and matrix representations. In this article, we propose a new crossover operator for traveling salesman problem to minimize the total distance. This approach has been linked with path representation, which is the most natural way to represent a legal tour. Computational results are also reported with some traditional path representation methods like partially mapped and order crossovers along with new cycle crossover operator for some benchmark TSPLIB instances and found improvements.
doi_str_mv 10.1155/2017/7430125
format article
fullrecord <record><control><sourceid>gale_pubme</sourceid><recordid>TN_cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_5676484</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A546404588</galeid><airiti_id>P20160527002_201712_201810240007_201810240007_1_7_090</airiti_id><sourcerecordid>A546404588</sourcerecordid><originalsourceid>FETCH-LOGICAL-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493</originalsourceid><addsrcrecordid>eNqNkk1vEzEQhlcIREvhxhlZ4oIEobbXnxekKIKCFNRKFHG0HO84cbVrp95Nqv57vE1IKCdOtuVHjz3zTlW9JvgjIZyfU0zkuWQ1JpQ_qU6JUHLCqayfHvaCn1Qv-v4GYy45ps-rE6op1rVgp9WvC4gwBIem7TLlMKw65FNG19luoQ1xiX7YFvrORnSV06KFDt0VCH1PTfABGjS7dy2gWU59n7aQ0eUash1Sflk987bt4dV-Pat-fvl8Pfs6mV9efJtN5xPLhRomsLCWadYwSTUB8MpJTxiTQD1vvCgn5bjmxCrKnVaYEOGcYFo0ltae6fqs-rTzrjeLDhoHcci2NescOpvvTbLBPL6JYWWWaWu4kIIpVgTv9oKcbjfQD6YLvYO2tRHSpjdEy5rxmtaqoG__QW_SJsdSXqEEKRFozI7UsnTOhOhTedeNUjPlTDDMuBpdH3aUG1uXwR--TLAZczVjrmafa8Hf_F3mAf4TZAHe74BViI29C_-pg8KAt0eaMIKVKMB8B9hQhiIcC70qHoHLfGFMH5zkYVEEU4Yxlo8PxEhTmlL_BszWyAE</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1961430904</pqid></control><display><type>article</type><title>Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator</title><source>Wiley-Blackwell Open Access Collection</source><source>Publicly Available Content Database</source><creator>Mohamd Shoukry, Alaa ; Hussain, Ijaz ; Nauman Sajid, M. ; Shad, Muhammad Yousaf ; Hussain, Abid ; Gani, Showkat</creator><contributor>Conforto, Silvia</contributor><creatorcontrib>Mohamd Shoukry, Alaa ; Hussain, Ijaz ; Nauman Sajid, M. ; Shad, Muhammad Yousaf ; Hussain, Abid ; Gani, Showkat ; Conforto, Silvia</creatorcontrib><description>Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. The genetic algorithm depends on selection criteria, crossover, and mutation operators. To tackle the traveling salesman problem using genetic algorithms, there are various representations such as binary, path, adjacency, ordinal, and matrix representations. In this article, we propose a new crossover operator for traveling salesman problem to minimize the total distance. This approach has been linked with path representation, which is the most natural way to represent a legal tour. Computational results are also reported with some traditional path representation methods like partially mapped and order crossovers along with new cycle crossover operator for some benchmark TSPLIB instances and found improvements.</description><identifier>ISSN: 1687-5265</identifier><identifier>EISSN: 1687-5273</identifier><identifier>DOI: 10.1155/2017/7430125</identifier><identifier>PMID: 29209364</identifier><language>eng</language><publisher>Cairo, Egypt: Hindawi Limiteds</publisher><subject>Algorithms ; Approximation ; Chromosomes ; Computer applications ; Computer science ; Cooperative learning ; Crossovers ; Cybernetics ; Evolutionary algorithms ; Genetic algorithms ; Heuristic ; International conferences ; Mutation ; Neural networks ; Operations research ; Population ; Traveling salesman problem</subject><ispartof>Computational Intelligence and Neuroscience, 2017-01, Vol.2017 (2017), p.1-7</ispartof><rights>Copyright © 2017 Abid Hussain et al.</rights><rights>COPYRIGHT 2017 John Wiley &amp; Sons, Inc.</rights><rights>Copyright © 2017 Abid Hussain 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 © 2017 Abid Hussain et al. 2017</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493</citedby><cites>FETCH-LOGICAL-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493</cites><orcidid>0000-0002-3541-6220 ; 0000-0001-8988-4946 ; 0000-0002-1586-1503 ; 0000-0003-4141-0359</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1961430904/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1961430904?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>230,314,780,784,885,25753,27924,27925,37012,37013,44590,75126</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/29209364$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><contributor>Conforto, Silvia</contributor><creatorcontrib>Mohamd Shoukry, Alaa</creatorcontrib><creatorcontrib>Hussain, Ijaz</creatorcontrib><creatorcontrib>Nauman Sajid, M.</creatorcontrib><creatorcontrib>Shad, Muhammad Yousaf</creatorcontrib><creatorcontrib>Hussain, Abid</creatorcontrib><creatorcontrib>Gani, Showkat</creatorcontrib><title>Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator</title><title>Computational Intelligence and Neuroscience</title><addtitle>Comput Intell Neurosci</addtitle><description>Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. The genetic algorithm depends on selection criteria, crossover, and mutation operators. To tackle the traveling salesman problem using genetic algorithms, there are various representations such as binary, path, adjacency, ordinal, and matrix representations. In this article, we propose a new crossover operator for traveling salesman problem to minimize the total distance. This approach has been linked with path representation, which is the most natural way to represent a legal tour. Computational results are also reported with some traditional path representation methods like partially mapped and order crossovers along with new cycle crossover operator for some benchmark TSPLIB instances and found improvements.</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Chromosomes</subject><subject>Computer applications</subject><subject>Computer science</subject><subject>Cooperative learning</subject><subject>Crossovers</subject><subject>Cybernetics</subject><subject>Evolutionary algorithms</subject><subject>Genetic algorithms</subject><subject>Heuristic</subject><subject>International conferences</subject><subject>Mutation</subject><subject>Neural networks</subject><subject>Operations research</subject><subject>Population</subject><subject>Traveling salesman problem</subject><issn>1687-5265</issn><issn>1687-5273</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNqNkk1vEzEQhlcIREvhxhlZ4oIEobbXnxekKIKCFNRKFHG0HO84cbVrp95Nqv57vE1IKCdOtuVHjz3zTlW9JvgjIZyfU0zkuWQ1JpQ_qU6JUHLCqayfHvaCn1Qv-v4GYy45ps-rE6op1rVgp9WvC4gwBIem7TLlMKw65FNG19luoQ1xiX7YFvrORnSV06KFDt0VCH1PTfABGjS7dy2gWU59n7aQ0eUash1Sflk987bt4dV-Pat-fvl8Pfs6mV9efJtN5xPLhRomsLCWadYwSTUB8MpJTxiTQD1vvCgn5bjmxCrKnVaYEOGcYFo0ltae6fqs-rTzrjeLDhoHcci2NescOpvvTbLBPL6JYWWWaWu4kIIpVgTv9oKcbjfQD6YLvYO2tRHSpjdEy5rxmtaqoG__QW_SJsdSXqEEKRFozI7UsnTOhOhTedeNUjPlTDDMuBpdH3aUG1uXwR--TLAZczVjrmafa8Hf_F3mAf4TZAHe74BViI29C_-pg8KAt0eaMIKVKMB8B9hQhiIcC70qHoHLfGFMH5zkYVEEU4Yxlo8PxEhTmlL_BszWyAE</recordid><startdate>20170101</startdate><enddate>20170101</enddate><creator>Mohamd Shoukry, Alaa</creator><creator>Hussain, Ijaz</creator><creator>Nauman Sajid, M.</creator><creator>Shad, Muhammad Yousaf</creator><creator>Hussain, Abid</creator><creator>Gani, Showkat</creator><general>Hindawi Limiteds</general><general>Hindawi Publishing Corporation</general><general>Hindawi</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>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-3541-6220</orcidid><orcidid>https://orcid.org/0000-0001-8988-4946</orcidid><orcidid>https://orcid.org/0000-0002-1586-1503</orcidid><orcidid>https://orcid.org/0000-0003-4141-0359</orcidid></search><sort><creationdate>20170101</creationdate><title>Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator</title><author>Mohamd Shoukry, Alaa ; Hussain, Ijaz ; Nauman Sajid, M. ; Shad, Muhammad Yousaf ; Hussain, Abid ; Gani, Showkat</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Chromosomes</topic><topic>Computer applications</topic><topic>Computer science</topic><topic>Cooperative learning</topic><topic>Crossovers</topic><topic>Cybernetics</topic><topic>Evolutionary algorithms</topic><topic>Genetic algorithms</topic><topic>Heuristic</topic><topic>International conferences</topic><topic>Mutation</topic><topic>Neural networks</topic><topic>Operations research</topic><topic>Population</topic><topic>Traveling salesman problem</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mohamd Shoukry, Alaa</creatorcontrib><creatorcontrib>Hussain, Ijaz</creatorcontrib><creatorcontrib>Nauman Sajid, M.</creatorcontrib><creatorcontrib>Shad, Muhammad Yousaf</creatorcontrib><creatorcontrib>Hussain, Abid</creatorcontrib><creatorcontrib>Gani, Showkat</creatorcontrib><collection>Chinese Electronic Periodical Services (CEPS)</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</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>Health &amp; Medical Collection (Proquest)</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 UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>Biological Science Collection</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest 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>ProQuest Biological Science Collection</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>ProQuest Biological Science Journals</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</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>Mohamd Shoukry, Alaa</au><au>Hussain, Ijaz</au><au>Nauman Sajid, M.</au><au>Shad, Muhammad Yousaf</au><au>Hussain, Abid</au><au>Gani, Showkat</au><au>Conforto, Silvia</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator</atitle><jtitle>Computational Intelligence and Neuroscience</jtitle><addtitle>Comput Intell Neurosci</addtitle><date>2017-01-01</date><risdate>2017</risdate><volume>2017</volume><issue>2017</issue><spage>1</spage><epage>7</epage><pages>1-7</pages><issn>1687-5265</issn><eissn>1687-5273</eissn><abstract>Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem. The genetic algorithm depends on selection criteria, crossover, and mutation operators. To tackle the traveling salesman problem using genetic algorithms, there are various representations such as binary, path, adjacency, ordinal, and matrix representations. In this article, we propose a new crossover operator for traveling salesman problem to minimize the total distance. This approach has been linked with path representation, which is the most natural way to represent a legal tour. Computational results are also reported with some traditional path representation methods like partially mapped and order crossovers along with new cycle crossover operator for some benchmark TSPLIB instances and found improvements.</abstract><cop>Cairo, Egypt</cop><pub>Hindawi Limiteds</pub><pmid>29209364</pmid><doi>10.1155/2017/7430125</doi><tpages>7</tpages><orcidid>https://orcid.org/0000-0002-3541-6220</orcidid><orcidid>https://orcid.org/0000-0001-8988-4946</orcidid><orcidid>https://orcid.org/0000-0002-1586-1503</orcidid><orcidid>https://orcid.org/0000-0003-4141-0359</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1687-5265
ispartof Computational Intelligence and Neuroscience, 2017-01, Vol.2017 (2017), p.1-7
issn 1687-5265
1687-5273
language eng
recordid cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_5676484
source Wiley-Blackwell Open Access Collection; Publicly Available Content Database
subjects Algorithms
Approximation
Chromosomes
Computer applications
Computer science
Cooperative learning
Crossovers
Cybernetics
Evolutionary algorithms
Genetic algorithms
Heuristic
International conferences
Mutation
Neural networks
Operations research
Population
Traveling salesman problem
title Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T00%3A40%3A12IST&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=Genetic%20Algorithm%20for%20Traveling%20Salesman%20Problem%20with%20Modified%20Cycle%20Crossover%20Operator&rft.jtitle=Computational%20Intelligence%20and%20Neuroscience&rft.au=Mohamd%20Shoukry,%20Alaa&rft.date=2017-01-01&rft.volume=2017&rft.issue=2017&rft.spage=1&rft.epage=7&rft.pages=1-7&rft.issn=1687-5265&rft.eissn=1687-5273&rft_id=info:doi/10.1155/2017/7430125&rft_dat=%3Cgale_pubme%3EA546404588%3C/gale_pubme%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a568t-ebaa494d47291eef8c7f1447e2f5df6c7f8c5951a825c980116cc6496da23f493%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1961430904&rft_id=info:pmid/29209364&rft_galeid=A546404588&rft_airiti_id=P20160527002_201712_201810240007_201810240007_1_7_090&rfr_iscdi=true