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...
Saved in:
Published in: | Computational Intelligence and Neuroscience 2017-01, Vol.2017 (2017), p.1-7 |
---|---|
Main Authors: | , , , , , |
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 & 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 & 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 & Communications Abstracts</collection><collection>Engineered Materials Abstracts</collection><collection>Materials Business File</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>Neurosciences Abstracts</collection><collection>Solid State and Superconductivity Abstracts</collection><collection>Health & 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 & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies & 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 & Africa Database</collection><collection>ProQuest Central</collection><collection>ANTE: Abstracts in New Technology & 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 & 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 & Medical Collection (Alumni Edition)</collection><collection>Medical Database</collection><collection>ProQuest Biological Science Journals</collection><collection>ProQuest Engineering Database</collection><collection>ProQuest advanced technologies & aerospace journals</collection><collection>ProQuest Advanced Technologies & 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 |