c10-9 (779547), страница 2
Текст из файла (страница 2)
The relative importance that it assigns tolength of path versus river crossings is determined by our choice of λ. Figure 10.9.1shows the results obtained. Clearly, this technique can be generalized to includemany conflicting goals in the minimization.4. Annealing schedule. This requires experimentation.
We first generate somerandom rearrangements, and use them to determine the range of values of ∆E thatwill be encountered from move to move. Choosing a starting value for the parameterT which is considerably larger than the largest ∆E normally encountered, weproceed downward in multiplicative steps each amounting to a 10 percent decreasein T . We hold each new value of T constant for, say, 100N reconfigurations, or for10N successful reconfigurations, whichever comes first. When efforts to reduce Efurther become sufficiently discouraging, we stop.The following traveling salesman program, using the Metropolis algorithm,illustrates the main aspects of the simulated annealing technique for combinatorialproblems.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).has many local minima. In practical cases, it is often enough to be able to choosefrom these a minimum which, even if not absolute, cannot be significantly improvedupon. The annealing method manages to achieve this, while limiting its calculationsto scale as a small power of N .As a problem in simulated annealing, the traveling salesman problem is handledas follows:1.
Configuration. The cities are numbered i = 1 . . . N and each has coordinates(xi , yi ). A configuration is a permutation of the number 1 . . . N , interpreted as theorder in which the cities are visited.2. Rearrangements. An efficient set of moves has been suggested by Lin [6].The moves consist of two types: (a) A section of path is removed and then replacedwith the same cities running in the opposite order; or (b) a section of path is removedand then replaced in between two cities on another, randomly chosen, part of the path.3. Objective Function. In the simplest form of the problem, E is taken justas the total length of journey,.50.501.50Figure 10.9.1.
Traveling salesman problem solved by simulated annealing. The (nearly) shortest pathamong 100 randomly positioned cities is shown in (a). The dotted line is a river, but there is no penalty incrossing. In (b) the river-crossing penalty is made large, and the solution restricts itself to the minimumnumber of crossings, two. In (c) the penalty has been made negative: the salesman is actually a smugglerwho crosses the river on the flimsiest excuse!Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).110.510.51(c).5(b)0(a)44710.9 Simulated Annealing Methods1448Chapter 10.Minimization or Maximization of Functions#include <stdio.h>#include <math.h>#define TFACTR 0.9Annealing schedule: reduce t by this factor on each step.#define ALEN(a,b,c,d) sqrt(((b)-(a))*((b)-(a))+((d)-(c))*((d)-(c)))nover=100*ncity;Maximum number of paths tried at any temperature.nlimit=10*ncity;Maximum number of successful path changes before conpath=0.0;tinuing.t=0.5;for (i=1;i<ncity;i++) {Calculate initial path length.i1=iorder[i];i2=iorder[i+1];path += ALEN(x[i1],x[i2],y[i1],y[i2]);}i1=iorder[ncity];Close the loop by tying path ends together.i2=iorder[1];path += ALEN(x[i1],x[i2],y[i1],y[i2]);idum = -1;iseed=111;for (j=1;j<=100;j++) {Try up to 100 temperature steps.nsucc=0;for (k=1;k<=nover;k++) {do {n[1]=1+(int) (ncity*ran3(&idum));Choose beginning of segmentn[2]=1+(int) ((ncity-1)*ran3(&idum));..and..
end of segment.if (n[2] >= n[1]) ++n[2];nn=1+((n[1]-n[2]+ncity-1) % ncity);nn is the number of cities} while (nn<3);not on the segment.idec=irbit1(&iseed);Decide whether to do a segment reversal or transport.if (idec == 0) {Do a transport.n[3]=n[2]+(int) (abs(nn-2)*ran3(&idum))+1;n[3]=1+((n[3]-1) % ncity);Transport to a location not on the path.de=trncst(x,y,iorder,ncity,n);Calculate cost.ans=metrop(de,t);Consult the oracle.if (ans) {++nsucc;path += de;trnspt(iorder,ncity,n);Carry out the transport.}} else {Do a path reversal.de=revcst(x,y,iorder,ncity,n);Calculate cost.ans=metrop(de,t);Consult the oracle.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).void anneal(float x[], float y[], int iorder[], int ncity)This algorithm finds the shortest round-trip path to ncity cities whose coordinates are in thearrays x[1..ncity],y[1..ncity]. The array iorder[1..ncity] specifies the order inwhich the cities are visited. On input, the elements of iorder may be set to any permutationof the numbers 1 to ncity.
This routine will return the best alternative path it can find.{int irbit1(unsigned long *iseed);int metrop(float de, float t);float ran3(long *idum);float revcst(float x[], float y[], int iorder[], int ncity, int n[]);void reverse(int iorder[], int ncity, int n[]);float trncst(float x[], float y[], int iorder[], int ncity, int n[]);void trnspt(int iorder[], int ncity, int n[]);int ans,nover,nlimit,i1,i2;int i,j,k,nsucc,nn,idec;static int n[7];long idum;unsigned long iseed;float path,de,t;10.9 Simulated Annealing Methodsif (ans) {++nsucc;path += de;reverse(iorder,ncity,n);}449Carry out the reversal.}if (nsucc >= nlimit) break;}}#include <math.h>#define ALEN(a,b,c,d) sqrt(((b)-(a))*((b)-(a))+((d)-(c))*((d)-(c)))float revcst(float x[], float y[], int iorder[], int ncity, int n[])This function returns the value of the cost function for a proposed path reversal.
ncity is thenumber of cities, and arrays x[1..ncity],y[1..ncity] give the coordinates of these cities.iorder[1..ncity] holds the present itinerary. The first two values n[1] and n[2] of arrayn give the starting and ending cities along the path segment which is to be reversed. On output,de is the cost of making the reversal. The actual reversal is not performed by this routine.{float xx[5],yy[5],de;int j,ii;n[3]=1 + ((n[1]+ncity-2) % ncity);n[4]=1 + (n[2] % ncity);for (j=1;j<=4;j++) {ii=iorder[n[j]];xx[j]=x[ii];yy[j]=y[ii];}de = -ALEN(xx[1],xx[3],yy[1],yy[3]);de -= ALEN(xx[2],xx[4],yy[2],yy[4]);de += ALEN(xx[1],xx[4],yy[1],yy[4]);de += ALEN(xx[2],xx[3],yy[2],yy[3]);return de;Find the city before n[1] ....
and the city after n[2].Find coordinates for the four cities involved.Calculate cost of disconnecting the segment at both ends and reconnectingin the opposite order.}void reverse(int iorder[], int ncity, int n[])This routine performs a path segment reversal. iorder[1..ncity] is an input array giving thepresent itinerary.
The vector n has as its first four elements the first and last cities n[1],n[2]of the path segment to be reversed, and the two cities n[3] and n[4] that immediatelyprecede and follow this segment. n[3] and n[4] are found by function revcst. On output,iorder[1..ncity] contains the segment from n[1] to n[2] in reversed order.{int nn,j,k,l,itmp;nn=(1+((n[2]-n[1]+ncity) % ncity))/2;for (j=1;j<=nn;j++) {k=1 + ((n[1]+j-2) % ncity);l=1 + ((n[2]-j+ncity) % ncity);itmp=iorder[k];iorder[k]=iorder[l];iorder[l]=itmp;}}This many cities must be swapped toeffect the reversal.Start at the ends of the segment andswap pairs of cities, moving towardthe center.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Finish early if we have enough suc}cessful changes.printf("\n %s %10.6f %s %12.6f \n","T =",t,"Path Length =",path);printf("Successful Moves: %6d\n",nsucc);t *= TFACTR;Annealing schedule.if (nsucc == 0) return;If no success, we are done.450Chapter 10.Minimization or Maximization of Functions#include <math.h>#define ALEN(a,b,c,d) sqrt(((b)-(a))*((b)-(a))+((d)-(c))*((d)-(c)))n[4]=1 + (n[3] % ncity);n[5]=1 + ((n[1]+ncity-2) % ncity);n[6]=1 + (n[2] % ncity);for (j=1;j<=6;j++) {ii=iorder[n[j]];xx[j]=x[ii];yy[j]=y[ii];}de = -ALEN(xx[2],xx[6],yy[2],yy[6]);de -= ALEN(xx[1],xx[5],yy[1],yy[5]);de -= ALEN(xx[3],xx[4],yy[3],yy[4]);de += ALEN(xx[1],xx[3],yy[1],yy[3]);de += ALEN(xx[2],xx[4],yy[2],yy[4]);de += ALEN(xx[5],xx[6],yy[5],yy[6]);return de;Find the city following n[3]....and the one preceding n[1]....and the one following n[2].Determine coordinates for the six citiesinvolved.Calculate the cost of disconnecting thepath segment from n[1] to n[2],opening a space between n[3] andn[4], connecting the segment in thespace, and connecting n[5] to n[6].}#include "nrutil.h"void trnspt(int iorder[], int ncity, int n[])This routine does the actual path transport, once metrop has approved.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
