(Message references:20) -- using template mhl.format -- Date: Wed, 26 Oct 94 19:27:00 +0100 To: D.M.Hammuda@brighton.ac.uk cc: evolutionary-computing@mailbase.ac.uk From: Frank Herrmann Subject: TSP Return-Path: In-Reply-To: D.M.Hammuda@bton.ac.uk's message of Wed, 26 Oct 1994 12:37:41 GMT ***<94102612374094@alpha1.bton.ac.uk> X-List: evolutionary-computing@mailbase.ac.uk Reply-To: Frank Herrmann Sender: evolutionary-computing-request@mailbase.ac.uk Precedence: list Hi, here are some references for the traveling salesman problem: 1- pp 170-174,204-206 @book{goldberg, author={David E. Goldberg}, title={Genetic algorithms in search, optimization, and machine learning}, publisher={Addison-Wesley Publishing Company, Inc.}, year=1989} 2- pp 160- @proceedings{icga1, title={Proceedings of the first international Conference of Genetic Algorithms} , editor= publisher= address= year=} 3- pp 224- @proceedings{icga2, title={Proceedings of the second international Conference of Genetic Algorithms }, editor= publisher= address= year= 4- pp 69-, 143- @proceedings{icga4, title={Proceedings of the fourth international Conference of Genetic Algorithms }, editor={Richard K. Belew and Lashon B. Booker}, publisher={Morgan Kaufmann Publishers, Inc.}, address={San Mateo, CA}, year=1991} 5- pp 316- @book{foundations, editor={Gregory J. E. Rawlins}, title={Foundations of Genetic Algorithms}, publisher={Morgan Kaufmann Publishers}, year=1991} 6- pp 332-, 350- @book{handbook, editor={Lawrence Davis}, title={Handbook of Genetic Algorithms}, publisher={Van Nostrand Reinhold}, year=1991} 7- pp 43- @book{davis, editor={Lawrance Davis}, title={Genetic Algorithms and Simulated Annealing}, publisher={Morgan Kaufmann Publishers}, year=1987} 8- found in GA List: { Genetic Algorithms Digest Tuesday, October 18, 1994 Volume 8 : Issue 40 - Send submissions (articles) to GA-List@AIC.NRL.NAVY.MIL - Send administrative (subscribe, unsubscribe, change of address, etc.,) requests to GA-List-Request@AIC.NRL.NAVY.MIL - Do not send email to gadistr@aic.nrl.navy.mil - For GA code, papers, conference announcements, GA-List back issues, etc., please use our anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL [192.26.18.68] Information is in /pub/galist/FTP } ======================================== Title of Book: "Genetic Algorithms + Data Structures = Evolution Programs" Author: Zbigniew Michalewicz Publisher: Springer-Verlag, (Artificial Intelligence Series) Publication date: June, 1992. ISBN#: 0-387-55387-8 Other: Hardcover, 250pp., 48 figures, 29 tables. Price: approx. $41.00 TABLE OF CONTENTS: Preface Table of Contents Introduction Part I Genetic Algorithms 1. GA: What Are They? 2. GA: How Do They Work? 3. GA: Why Do They Work? 4. GA: Selected Topics Part II Numerical Optimization 5. Binary or Float? 6. Fine Local Tuning 7. Handling Constraints 8. Evolution Strategies and Other Methods Part III Evolution Programs 9. The Transportation Problem 10. The Traveling Salesman Problem 11. Graph Problems, Scheduling, and Partitioning 12. Machine Learning Conclusions ======================================== There is a new paper available that continues the research of N.L.J. Ulder, E.H.L. Aarts, H.L. Bandelt, P.J.M. van Laarhoven, and E. Pesch: Genetic local search algorithms for the traveling salesman problem. Proc. 1st. Int. Workshop on Parallel Problem Solving from Nature (H.-P. Schwefel and R. Maenner, eds.), Lecture Notes in Computer Science 496 (1991), 109-116 The paper is: A. Kolen and E. Pesch: Genetic local search in combinatorial optimization, Discrete Applied Math. (to appear) Abstract: The most common application of genetic algorithms to combinatorial optimization problems has been restricted to the traveling salesman problem. We review some of these ideas and present some new results, especially in th cas e that severe time constraints are imposed on the running time of the algorithm. Another paper is available: U. Dorndorf and E. Pesch: Evolution based learning in a job shop scheduling environment. Abstract: A class of approximation algorithms is described for solving the minim um makespan problem of job shop scheduling. A common basis of these algorithms is the underlying genetic algorithm that serves as a meta-strategy to guide an optimal design of local decision rule sequences. Computational experiments show that our algorithm can find shorter makespans than the shifting bottleneck heuristic or a simulated annealing approach with the same running time. Requests to Erwin Pesch Faculty of Economics, KE University of Limburg P.O. Box 616 6200 MD Maastricht The Netherlands e-mail:EFKWEPES@HMARL5.Bitnet ======================================== \item ``A `Memetic' Approach for the Traveling Salesman Problem. Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems'', P. Moscato and M.G. Norman (Edinburgh Parallel Computing Centre), Proceedings of PACTA '92 - International Conference on Parallel Computing and Transputer Applications (Barcelona, 21-25 September 1992). ======================================== Mathias, Keith and Whitley, Darrell [1992], ``Genetic operators, the fitness landscape and the traveling salesman problem'' ======================================== 2: Litke, J.D.: An Improved Solution to the travelling salesman problem with thousands of nodes, Communications of the ACM, Vol.27, No.12, pp1227-1236, 1984 ======================================== From: Peter Ross Date: Fri, 20 May 94 12:00:38 BST Subject: benchmarks for various OR problems (Re: v8n16) In GA-List v8n16, Birgit Fahl (d10m@zfn.uni-bremen.de) asks for the whereabouts of benchmark problems for lotsizing with capacity constraints. A range of benchmark problems for various well-known OR tasks can be obtained by FTP from the OR library at Imperial College, London, address scmga.ms.ic.ac.uk (currently 155.198.66.4). The `info' file from there is reproduced below. You will need access to various well-known OR journals; the on-line files typically refer you to journal articles for details of optimal solutions or current best solutions. Peter Ross Department of AI University of Edinburgh ................................................................. Welcome to OR-Library. The following table gives the relationship between problem area and the appropriate file: Problem area File Assignment problem assigninfo Crew scheduling cspinfo Data envelopment analysis deainfo Generalised assignment problem gapinfo Integer programming mipinfo Linear programming lpinfo Location: capacitated warehouse location capinfo p-median pmedinfo uncapacitated warehouse location uncapinfo Multiple knapsack problem mknapinfo Quadratic assignment problem qapinfo Resource constrained shortest path rcspinfo Scheduling: flow shop flowshopinfo job shop jobshopinfo open shop openshopinfo Set covering scpinfo Set partitioning sppinfo Steiner: Euclidean Steiner problem esteininfo Rectilinear Steiner problem rsteininfo Steiner problem in graphs steininfo Travelling salesman problem tspinfo Two-dimensional cutting: assortment problem assortinfo constrained guillotine cgcutinfo constrained non-guillotine ngcutinfo unconstrained guillotine gcutinfo Vehicle routing: fixed areas areainfo fixed routes fixedinfo period routing periodinfo single period vrpinfo spare feasibility graph vrpfeasinfo Instructions on how to use OR-Library can be found in the file paper or in the article J.E.Beasley, "OR-Library: distributing test problems by electronic mail", Journal of the Operational Research Society 41(11) (1990) pp1069-1072. J.E.Beasley, June 1990. Revised June 1992, April 1993, March 1994. All the files in OR-Library are available via anonymous ftp to mscmga.ms.ic.ac.uk The numeric equivalent of this ftp address is 155.198.66.4 ======================================== From: mdlm@ai.mit.edu (Michael de la Maza) Date: Wed, 3 Aug 94 16:31:18 EDT Subject: Dynamic Hill Climbing papers available Dynamic hill climbing is an optimization algorithm that has outperformed the standard genetic algorithm, Ingber & Rosen's adaptive simulated annealing, and Powell's method on several problems, both artificial and real-world. A packet of three papers that describe dynamic hill climbing is available by sending a physical mail address to: dhc@ai.mit.edu. The abstract of one of those papers reads: The work described began as an inquiry into the nature and use of optimization programs based on "genetic algorithms." That inquiry led, eventually, to three powerful heuristics that are broadly applicable in gradient-ascent programs: First, remember the locations of local maxima and restart the optimization program at a place distant from previously located local maxima. Second, adjust the size of probing steps to suit the local nature of the terrain, shrinking when probes do poorly and growing when probes do well. And third, keep track of the directions of recent successes, so as to probe preferentially in the direction of most rapid ascent. These algorithms lie at the core of a novel optimization program that illustrates the power to be had from deploying them together. The efficacy of this program is demonstrated on several test problems selected from a variety of fields, including De Jong's famous test-problem suite, the traveling salesman problem, the problem of coordinate registration for image guided surgery, the energy minimization problem for determining the shape of organic molecules, and the problem of assessing the structure of sedimentary deposits using seismic data. ======================================== -------------------------------------------------- Frank Herrmann, Dept. of Molecular Biophysics 0810 German Cancer Research Center Im Neuenheimer Feld 280, D-69120 Heidelberg Tel: (49) 6221-422336, FAX: (49) 6221-422333 email: F.Herrmann@dkfz-heidelberg.de