Combinatorial Optimization by Iterative Partial Transcription

Details Combinatorial Optimization by Iterative Partial Transcription Combinatorial Optimization by Iterative Partial Transcription

1999-02-02

arxiv.org/abs/cond-mat/9902034v1

Phys. Rev. E 59, 4667 (1999)

Physics

Condensed Matter

Disordered Systems and Neural Networks

RevTex-file: 18 pages, 3 Postscript figures. Accepted for publication in Phys. Rev. E

Scientific paper

10.1103/PhysRevE.59.4667

A procedure is presented which considerably improves the performance of local search based heuristic algorithms for combinatorial optimization problems. It increases the average `gain' of the individual local searches by merging pairs of solutions: certain parts of either solution are transcribed by the related parts of the respective other solution, corresponding to flipping clusters of a spin glass. This iterative partial transcription acts as a local search in the subspace spanned by the differing components of both solutions. Embedding it in the simple multi-start-local-search algorithm and in the thermal-cycling method, we demonstrate its effectiveness for several instances of the traveling salesman problem. The obtained results indicate that, for this task, such approaches are far superior to simulated annealing.

Affiliated with

Also associated with

No associations

Rating

Combinatorial Optimization by Iterative Partial Transcription does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial Optimization by Iterative Partial Transcription, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Optimization by Iterative Partial Transcription will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147613