Proximity and priority: applying a gene expression algorithm to the Traveling Salesperson Problem
Saved in:
| Title: | Proximity and priority: applying a gene expression algorithm to the Traveling Salesperson Problem |
|---|---|
| Authors: | Burkowski, Forbes J.1 fjburkow@plg.uwaterloo.ca |
| Source: | Parallel Computing. May2004, Vol. 30 Issue 5/6, p803-816. 14p. |
| Subjects: | Gene expression, Algorithms, Foundations of arithmetic, Sales personnel |
| Abstract: | We describe an environment for evolutionary computation that supports the movement of information from genome to phenotype with the possibility of one or more intermediate transformations. Our notion of a phenotype is more than a simple alternate representation of the binary genome. The construction of a phenotype is sufficiently different from the genome as to require its generation by a procedure that we call a gene expression algorithm. We discuss various reasons why benefits should accrue when combining gene expression algorithms with conventional genetic algorithms and illustrate these ideas with an algorithm to generate approximate solutions to the Traveling Salesperson Problem. As in most genetic algorithms dealing with the TSP we run into the problem of an appropriate crossover operation for the strings that specify a permutation. To handle this issue we introduce a novel genome representation that admits a natural crossover operation and produces a permutation vector as an intermediate representation. The gene expression strategy offers an excellent opportunity for parallelization of the computation since the gene expression processing for each genome and the subsequent evaluation of the fitness function are computations that can be spread across many processors. [Copyright &y& Elsevier] |
| Copyright of Parallel Computing is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 13236838 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Proximity and priority: applying a gene expression algorithm to the Traveling Salesperson Problem – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Burkowski%2C+Forbes+J%2E%22">Burkowski, Forbes J.</searchLink><relatesTo>1</relatesTo><i> fjburkow@plg.uwaterloo.ca</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Parallel+Computing%22">Parallel Computing</searchLink>. May2004, Vol. 30 Issue 5/6, p803-816. 14p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Gene+expression%22">Gene expression</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Foundations+of+arithmetic%22">Foundations of arithmetic</searchLink><br /><searchLink fieldCode="DE" term="%22Sales+personnel%22">Sales personnel</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We describe an environment for evolutionary computation that supports the movement of information from genome to phenotype with the possibility of one or more intermediate transformations. Our notion of a phenotype is more than a simple alternate representation of the binary genome. The construction of a phenotype is sufficiently different from the genome as to require its generation by a procedure that we call a gene expression algorithm. We discuss various reasons why benefits should accrue when combining gene expression algorithms with conventional genetic algorithms and illustrate these ideas with an algorithm to generate approximate solutions to the Traveling Salesperson Problem. As in most genetic algorithms dealing with the TSP we run into the problem of an appropriate crossover operation for the strings that specify a permutation. To handle this issue we introduce a novel genome representation that admits a natural crossover operation and produces a permutation vector as an intermediate representation. The gene expression strategy offers an excellent opportunity for parallelization of the computation since the gene expression processing for each genome and the subsequent evaluation of the fitness function are computations that can be spread across many processors. [Copyright &y& Elsevier] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Parallel Computing is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=13236838 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.parco.2003.12.017 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 14 StartPage: 803 Subjects: – SubjectFull: Gene expression Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Foundations of arithmetic Type: general – SubjectFull: Sales personnel Type: general Titles: – TitleFull: Proximity and priority: applying a gene expression algorithm to the Traveling Salesperson Problem Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Burkowski, Forbes J. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2004 Type: published Y: 2004 Identifiers: – Type: issn-print Value: 01678191 Numbering: – Type: volume Value: 30 – Type: issue Value: 5/6 Titles: – TitleFull: Parallel Computing Type: main |
| ResultId | 1 |
