M FILE Cun

ARI Research Note 87-04

-- w

CM

o>

<

i

Q

<

ADDRESSING THE TRAVELLING SALESMAN PROBLEM

THROUGH EVOLUTIONARY ADAPTATION

David B. Fogel

Titan Systems

for

Contracting Officer's Representative

George H. Lawrence

BASIC RESEARCH LABORATORY

Milton R. Katz, Director

fe

i

DTIC

ELECTE'

APR2 9t987

U. S. Army

Research Institute for the Behavioral and Social Sciences

January 1987

5

Approvad for public release, dutnbution jnhmitad.

sr 4 28 141

'*- - - ^- ^.i^t ^i *. i •_-« •_ v
f\n\nVtnv*W»\JTTrr\rrwr.'<i\,~*\~*\--rr*i-w»nr>nrw irw»

U. S. ARMY RESEARCH INSTITUTE

FOR THE BEHAVIORAL AND SOCIAL SCIENCES

A Field Operating Agency under the Jurisdiction of the

Deputy Chief of Staff for Personnel

EDGAR M. JOHNSON

Technical Director

WM. DARRYL HENDERSON

COL. IN

Commanding

Research accomplished under contract

for the Department of the Army

Titan Systems

Technical review by

Steve Kronheim

Thii t*pon, •« Mbmititd by ito con rtctor, h«» '»«»nc'ttfed 4c' rtl«»if to D«<«n»« Ttc^niul ln<o"Tiaiion Cent"

(OTICI to comply with rcguUlory r< 9ui'«rr»«n1l. .1 hat b*tr\ given no iirimary ditlnbuTion oth»' thin to OTIC

•f»d will b* «vnUbl« only through „(TIC o» ©thai rafarcne« larvicai Mch at the National Tachmcal Information

$ar»(c« (NTISI. Tha «iewt. cprrti'.nt, and/or finding» contained in thit rapon ara thott of the authorli' and

•hould not ba conitruaw at an otficia- Oapaitman« of th« Army petition, policy, or daemon, unlfti to dtngnated

by othar official documantation.

t-a n ^ A n JB KB « ft ft a KM ^ k f »« ." »• ft « .» .>. » .-. 

> .VW.V.V »>\0^^>.'\>.'l/^^X.»^»j Vi '* UUULMUI
'*>******'*****'*'*}*:* ."w^mmmmammmmam^mm^m nfW^>v<i«u^flP>iRrw>winti«un< w^wn »P-BW»W»WWH I. w^mmmm^mm^

UNCLASSIFIED

SECURITY CLASSIFICATION OF THIS PAGE (Hfian Oat* Bnfnd)

| REPORT DOCUMENTATION PAGE READ INSTRUCTIONS 1

BEFORE COMPLETING FORM 1

It. REPORT NUMBER

ARI Research Note 87-04 A

2. OOVT ACCESSION NO. L. RECIPIENT'S CATALOG NUMBER 1

I* TITLE raid SubMII«; '

1 Addressing the Travelling Salesman Problem

1 Through Evolutionary Adaptation

S. TYPE OF REPORT • PERIOD COVERED f

Interim Report I

April - July 1986

C. PERFORMING ORG. REPORT NUMBER

j?. AuTMORf»;

1 David B. Fogel

8 CONTRACT OR GRANT NUMBER! •; |

P0-9-X56-1102C-1

|» PERFORMING ORGANIZATION NAME AND ADDRESS

j Titan Systems

P.O. Box 12139

La Jolla, CA 92037

10. PROGRAM ELEMENT. PROJECT, TASK 1

AREA 4 WORK UNIT NUM'JERS t

(Not Applicable)

III. CONTROLLING OFFICE NAME AND ADDRESS

1 U.S. Army Research Institute for the Behavioral

1 and Social Sciences, 5001 Eisenhower Avenue,

Alexandria, VA 22333-5600

12. REPORT DATE |

January 1987

13. NUMBER OF PACES t

36

I U MONITORING AGENCY NAME » ADDRCSV" dllUnnl Itom Controlllnt O/f/c»' IS. SECURITY CLASS. Cef (MaraporO 1

Unclassified

ISs. DECLASSIFICATION/DOWNGRADING

SCHEDULE 1

116 DISTRIBUTION STATEMENT (ol Oil» Kmpott)

j Approved for public release, distribution unlimited.

1 17. DISTRIBUTION STATEMENT (ol th» mbmtrmel tntmnd In Block 20, II dlllormtl from Mmport)

1 ••. SUPPLEMENTARY NOTES 1

1 George H. Lawrence, contracting officer's representative

1 It. KEY WORDS (Conllnuo on torotoo otäo II nocommary mid Idonllly by block numbor) |

1 Algorithm Evolutionary Programming

1 Problem Solving Iterative Mutation

Logic j

120. AMTHACT (Ctmt^ua mx roror— U* If w——> «orf Idmntllf by block numbt) |

1 Optimizing the "travelling salesman" problem continues to receive attention j

for three reasons: its solution is computationally difficult, although the

algorithm itself is easily expressed; it is broadly applicable to a variety of

engineering problems; and it has become somewhat of a comparison "benchmark"

problem.

The task contained in the problem is to arrange a tour of n cities in such a

way that each city is visited only once, and the length of the tour (or some

I (OVER) 1

Do^rUMn EDtTION OF • NOV •> IS OBSOLETE UNCLASSIFIED

1 SECURITY CLASSIFICATION OF THIS PAGE ( Dmlm Bnlmod)

JS.'A»\ • »,r ,\s--V.v-AV.-.V.-.v .-.V. ..•.-. .V^-.'vV BmSttAS ffl.../ .. . V1-1-."."»^OöN»/^^ -^^«.V-l^^vL^
mäinnMaHHBBHurvwr r

v nr maa^HHH^a^pn«<isB

UNCLASSIFIED

' SCCURITY CLASSIFICATION Of THIS RAOKfW»«« 0«<« «tilfO

ARI Research Note 87-04

20. Abstract (ccntinued)

other cost function) is minimized. For an exact solution, the only known algorithms require the number of steps to grow at least exponentially with the

number of elements in the problem. Brute force methods of finding the shortest

path require the compilation of a list of (n-l)!/2 alternative tours, a number

which grows faster than any finite power of n, so the task quickly becomes

unmanageable.

Accession For

"NTISGRAtI

DTIC TAB

Unannounced

Justification.

1

D

By

Distribution/

Availability Codes

Avail and/or~

Dlst Special

M

UNCLASSIFIED

i i SKCUKITV CLASSIFICATION OF TMIS P*GEfl*»>»" 0«e« Bnitfd)

&tt^':v^^^^^
MM m*jrjfjmM*M*ß*M*MtlM*MnM*Mm

Ji*ß''jWM,*M*M'wnw^mim*MHM'yM}w*mHMi\Mim\\mimiwnwnwmmimmmmmmm^mm

E

^

ADDRESSING

THE TRAVELING SALESMAN PROBLEM

THROUGH EVOLUTIONARY ADAPTATION

By David Fogel

INTRODUCTION

The optimization of the traveling salesman problem continues to

receive attention for three reasons: (1) Its solution ts computationally

| difficult although the algorithm itself Is easily expressed; (2) It is

broadly applicable to a variety of engineering problems; and (3) it has

become somewhat of a comparison 'benchmark" problem. The task is to

arrange a tour of n cities such that each city is visited only once and the

length of the tour (or some other cost function) is minimized. For an exact

solution the only known algorithms require the number of steps to grow at

least exponentially with the number of elements in the problem. Brute

force methods of finding of the shortest path by which a traveling

salesman can complete a tour of n cities requires compiling a list of

(n-i )l/2 alternative tours, a number that grows faster than any finite

power of n. The task quickly becomes unmanageable.

i i
'irwv'y^Kwy.irw»TljT\y\rT

v^rT.>^ WTT Tvr-vrw^^y^oi^w^TwrTwwwi—»»» www—■■■ » ww *F-W»I-»I.-W i^-vvr«<

L

;

9

§

.-.•

la

P

I

RACKGRQUNn

Two recenl papers (Goldberg, Lingle, Jr., 1985; Grefenstette et al.,

1985) addressed the traveling salesman problem through use of the

genetic algorithm as proposed by Holland (1975). This algorithm Is an

offshoot of the evolutionary programming concept offered by Fogel (1962,

> 1964, Fogel et.->!., 1966).

In Fogers evolutionary procedures the process of Iterative mutation

and selection Is simulated to evolve a logic most suitable for resolving

the problem at hand. Intelligent behavior Is viewed as requiring prediction

of an environment coupled with the use of such predictions for the sake of

controlling that environment (to the greatest extent possible). The

behavior of each artificial organism is constructed as a finite state

machine, a general mathematical function that does not constrain the

represented transduction to be linear, passive, or without hysteresis.

The evolutionary process is simulated in the following mannen an

original "machine" (an arbitrary logic or a "hint") is measured in its ability

to predict each next event in its "experience" with respect to whatever

payoff function has been prescribed. Progeny are now created through

random mutation of this "parent" machine. They are scored in a similar

manner to the parent in predictive ability. If the parent is better than its

offspring, the parent Is used to generate other offspring. If, however, an

offspring is better than its parent, that offspring becomes the new parent.

teu&v^^
g

I

K

This assures non-regressive evolution. An actual prediction is made when

the t,redictive fit score demonstrates that a sufficient level of credibility

has been achieved. The surviving machine generates a prediction, indicates

the logic of this prediction and becomes the progenitor for the next

* sequence of progeny, this in preparation for the next prediction. Thus,

randomness is selectively incorporated into the surviving logic. The

DC

<: sequence of predictor machines demonstrates phyletic learning, an

<s

£

inductive generation of sequences of hypotheses concerning the relevant

regularities found within the experienced environment, in the context of

the given payoff function.

Holland's approach differs from that of Fogel's. Rather than describe

each organism only in terms of its behavior, Holland emphasizes the coding

structures which generate such organisms. Holland's genetic algorithms

search a parameter space where "any point in the parameter space can be

represented as an n bit vector." "There are two primary operations applied

to the population by a genetic algorithm. Reproduction changes the

contents of the population by adding copies of genotypes with aboveaverage figures of merit." "Crossover is the primary means of generating

plausible new genotypes for addition to the population" (Ackley, 1985).

Holland defines crossover as taking two coding structures,

A

r

a

l l

a

12

a

ln

anö A

2

= ^l^-^n« and at a ranclom Polnt "x

" between

I and n, exchanging the set of attributes to the right of this position

yielding offspring of the form: A* = a. |a 12 .a 1 xa2(x*)) a2n "

Th's

'offspring" is added to the population, displacing some other genotype

I 3 .
n^^^vwrv^^.^v,

.V'K"w.ryi».'»/,i.^v,^vTv<v'y'^"^^^'^^^^^^^^

r':

K

.'.

according to various criteria where It has the opportunity to flourish or

perish depending on its fitness. Mutation provides a chance for any allele

to be changed to another randomly chosen value. If the mutation rate is too

low, possibly critical alleles missing from the initial population will have

only a small chance of getting...lnto the population. However, if the

probability of a mutation is not low enough, informatlon...will be steadily

lost to random noise" (Ackley, 1985).

Holland likens the actual code being mutated to that of the genetic

c code that defines a natural organism. While Fogel et al. (1966) only used

small degrees of "background" mutation, Holland Incorporates the

operations of gene "crossover" and "Inversion" among other actual biologic

genetic recombinations. Although Holland's work has gone largely

unnoticed for some time, today renewed attention is being given to genetic

Jj algorithms.

Goldberg and Lingle (1985) offered several )bservations of the

genetic algorithm (GA) as it relates to the traveling salesman problem:

' I) Simple genetic algorithms work well in problems which can be

coded so the underlying building blocks (highly fit, short defining

length schemata) lead to improved performance.

ft "2) There are problems (more properly codings for problems) that are

GA-hard — difficult for the normal reproduction crossover

mutation processes of the simple genetic algorithm.

*3) Inversion is the conventional answer when genetic algorithmists

^wv:;^^-^^^
WIVIHI^H^HBWBWW

c •

E are asked how they intend to find good string ordering, but inversion

has never done much in empirical studies to date.

£5

^

3

Si

"4) Despite numerous rumored attempts, the traveling salesman

problem has not succumbed to genetic algorithm-like solution."

They suggested a new type of crossover operator, the "partially-mapped

crossover (PMX)," which they believe will lead to a more efficient solution

of the traveling salesman problem.

PMX would proceed as follows: consider two possible codings of a tour

of eight cities. A! and A2. a return to the initial city being implicit:

A|:3 5 I 2 7 6 8 4

A2: I 8 5 4 3 6 2 7

Two positions are determined randomly along the Aj coding. The actual

cities located between these positions along Aj are exchanged with the

cities located between the same positions along A2. For example, if the

positions three and five are chosen, the sub-coding along A| is 1-2-7, and

the sub-coding along A2 is 5-4-3. Each of these cities is then exchanged,

leading to the new tours. A*| and A^:

A*,: 7 15 4 3 6 8 2

A*o: 5 8 1 2 7 6 4 3.
Goldberg and Llngle (1985) reported two experiments on ten cities

where the PMX operator enabled the search to efficiently discover either

the absolute or near optimum solution.

Grefenstette et al. (1965) addressed the traveling salesman problem

using Holland's "simple crossover.' This required the formation of a

special coding structure Clearly, using this operator on two valid tours

could result in an "offspring" that was not a valid tour. As Dewdney (1985)

has commented, the authors' method for devising the appropriate coding

was ingenious.

"The representation for a five-city tour such as a, c, et d, t> turns out

to be 12321. To obtain such a numerical string reference is made to

some standard order for the cities, say. a, d, c, d, e. Given a tour such

as a, c, e, d, t>, systematically remove cities from the standard list

in the order of the given toun remove 4 then ct e and so on. As each

city is removed from the special list, note its position Just before

removal, jis first, rls second, ^is third, d is second and, finally ö

is first. Hence the chromosome 12321 emerges. Interestingly, when

two such chromosomes are crossed over, the result is always a tour."

Unfortunately the experiments with this representation were "not very

encouraging" (Dewdney, 1985). Grefenstette et al. conducted larger

experiments than those of Goldberg and Llngle, including 50, 100 and 200

^; cities. In the three reported experiments, after a large number of trials

/•

P

%

(approximately 14000,20000 and 25000, respectively), the best tours

were still far away from the expected optimal solutions.
r

^

At this point It Is natural to ask "why?". After all, the traveling

salesman problem only requires discovery of a logical pattern. This seems

completely analogous to what occurs In nature. If the crossover of genes

works In natural evolution, why shouldn't It worK here?

The answer Is, In fact, that suggested by Goldberg and tingle's second

observation: the traveling salesman problem is difficult to address using

j' Holland's crossover mutation. This is because the crossover operation, as

defined by Holland, does not mimic the biological crossover of genes.

r Natural crossover is a phenomenon where 'old linkages between genes on

homologous chromosomes are broken and new linkages are established.

Genes that reside on the same chromosome and move together are said to

be 'linked.' A linkage group is any group of genes physically linked on one

chromosome...Changes in linkage groups are not truly mutations, however,

since neither the amount nor the function of genetic material is altered"

(Levy, 1982).

Holland's crossover treats the entire tour as a chromosome and each

city in a tour somewhat as a gene. While this does not change the amount

of coding, it greatly alters the function of the coding. Natural crossover

allows for different combinations of alleles. Alleles. by definition, control

the same characteristic and occupy the same place on similar

chromosomes. A more appropriate biologic Interpretation of a tour would

be '.hat it is Itself a gene. Crossover inside a gene Is a nonsequetor. The

tour is not analogous to a chromosome and each city in a tour is not

analogous to a gene. These relations are In fact anomolous.

I

•

,
c

I

B The result of Holland's crossover Is therefore a near random search

" throughout the entire space of possible tours. This Is, of course, the

^ essence of the difficulty. Dewdney (1985) has commented that by using

Holland's crossover 'there Is so much Juggling of genes and cracking of

^ chromosomes that...(a parent)...is hard put to recognize Its own

grandchildren." As the number of cities grows larger, Hollands crossover

effectively destroys the link between each parent and its offspring. The

•^ results can even be worse than a complete enumeration of all possible

tours (Appendix). Adaptive plans must retain previous advances and

£ incorporate them Into future solutions.

£

I

ANALTFRNATIVFAPPRQAPH

An alternative solution is the adaptive aigorithmr so named because it

does not Include any of the genetic-mimicking operators that Holland has

suggested, but instead emphasizes the behavioral appropriateness

y (fitness) of the evolved trial solutions. The algorithm, which Is equivalent

vv to Fogel's evolutionary programming restricted to single state machines,

only slightly mutates the existing tour by removing just floft city from a

v given list and replacing it in a different randomly chosen position. This

mutation is only mildly more complicated than the simplest possible

mutation, that is, swapping adjacent cities. It Is clearly less complex than

- either the PMX operator or Holland's crossover; through multiple mutation,

this single alteration can be made equivalent to either of these crossover

operators. Holland (1975) has stated: 'If successive populations are

produced by mutation alone (without (genetic) reproduction), the result Is

8

fe
T

."'•

N

;J

'.".

I

W.

4

a random sequence of structures drawn from (all possible structures)."

This Is only par.tially correct. The adaptive algorithm does result in a

r?ddom search, but only in that portion of the space relatively close to the

parent which generates the offspring. This dramatically increases the

effectiveness of the search through the state space of all possible

constructions.

•'; Not only must advances be retained but "dead-ends" must be

circumvented. Because there is a finite number of offspring that can be

f generated through mutation evolutionary stagnation might well occur on a

M local optimum. To prevent this it is useful to randomh' alter the adaptive

'

s

topography (payoff function) that is being searched. This can be accompli lished by a variety of means. One of these is to occasionally allow for the

survival of offspring that are slightly worse than their parents. In effect,

<J the scoring function is made "noisy."

What results is analogous to the searching of a maze; when a dead-end

is react.ed some backtracking is allowed and the overall search is

reinitiated. Unfortunately, the topography is much like an upside-down bed

K of nails, with some nails being longer (better) than others. From any given

nail, it is possible to travel to n(n-1) other ^ails in a single mutation by

t randomly choosing a city and placing it in ? afferent position. Unlike a

maze, when the evolving phyletic line reaches a non-optimal nail from

which no single mutation results in a better tour, it is impossible to

determine the "direction" in which to backtrack. The complete prevention

of evolutionary stagnation is impossible unless all inheritance is given up

and the search made completely random.

^s^&&&k&^^ :NV^-" V

-
FyPFRIMFNTAl FINDINfiS

«

Experiments were performed to determine the effectiveness of the

adaptive algorithm. Initially, 126 independent trials were performed on a

24 city traveling salesman problem where the cities were positioned on

the periphery of a rectangle. Clearly, the minimum length tour is equal to

the perimeter of the rectangle. In this case, 250. The amount of noise that

was used is indicated in Table I. The same degree of noise was used

throughout all of the experiments described. Of the 128 trials performed.

Table I:

Number of Fvaluatgd Offspring Offspring ^cor<>/Parent Srnre Accept»

Less than 1,500

Between 1,500 and 5,000

Between 5,000 and 10,000

Between 10,000 and 20,000

<- 1.05 15«

<- I.I 10X

<- 1.2 5%

> 1.2 1*

<« 1.05 5%

<-l.1 2.5%

<-1.2 1%

>l.2 0.5% :

1

<- 1.05 2%

<-1.1 1%

<-l.2 0.5%

> 1.2 0.2%

<- 1.05 0.5%

> 1.05 0%

Greater than 20.000 Any ratio 0%

Table 1: The amount of noise.

10

tvxy.vivv-.s;V:-AVv^^ ^^vv^^ .T . MM, ,
GiN

90.625% found the optimum solution In an average of 5297.48 Iterations

tt (Figure 1) where the maximum number of Iterations was arbitrarily set at

14,000. Figure 2 Indicates the results of the remaining 9375% of the

trials In which the evolving tours were, at least temporarily, trapped on a

local optimum. Despite the seemingly non-complex arrangement of cities,

* the numerous local optima Inherent to this city-structure make this

particular traveling salesman problem somewhat recalcitrant.

f* To further Investigate the efficiency of the algorithm, 20 experl-

*

a

S

a

ments were conducted requiring a tour of 50 cities where the cities were

redistributed for each experiment. In each, no optimum tours were

discovered in 20,000 Iterations, but It was clear that the evolutionary

process was "solving the problem." Figure 3 Indicates the results of a

typical experiment. Figure 4 Indicates the mean and estimated two-slgma

limits of the evolutionary process as it discovered more and more suitable

tours as offspring were evaluated. Note that "backtracking" played an

Integral part of the search.

5^ Experiments were then performed requiring a tour of 100 cities under

similar conditions. Again, while none of the eight experiments found a

n

P perfect tour in 20,000 Iterations, the evolutionary process performed

A, well. Figure 5 Indicates the results of a typical experiment while

Figure 6 indicates the mean and two-slgma limit of the reduction in tour

length as offspring were evaluated.

»-

v. Further experiments required a tour of 90 cities. Here, 18 trials

ri I

1

j
=*:

I

i

CO

Q> o

o o

0) m

•

C—» • • o

c 0)

c o

o• •—^-' o

D L. o

o

0) 00

C^)

E o

D " h*

E CO

0)

GL

O GO o

CO o

c

C

o

0)

E

-

o

to

L.

0

b 0)

o

o

o

Ü 0} Q. o

> X

• _ o >^

o LxJ o ^f -M

o

CO

in

eg b

s il o

3 0) , n

H- u 1

co c t

CO o

0) •** o

Ü

o

m

Q

CM

13

00 E 1

l^_

E

o

o

0) ' *c "

Q.

E

o

x

2 r«!

ooooooooooo

OOOOI^COIO^-KJCMTÜJ r

1"

§

K

Figure I

^^^^^^^^^^^v^^^
Ii?::'

CO

0)

•—

L0)

00coüc

cno

CDc

a5 .1 O

0)

CLEX

Lü

"5

0)

Q. X

ÜJ

oo

oo

o

oo

oo

o O) GO r^ <o \n

^ ro 04

CO

0) oooo

Figure2

i^wjtä&:&tt&^^^^
s

SJ

V

I

a

s

^

I

CD • « —•

»>"—

o

o

LO

I

E

-Q

O

CL

c

o

CO

o

if)

CD

>

o

CO

c

0)

•E—> L.

Q.

X

Figure 3

U&SS&teSr&^^
tVmI

'XI

CO

CD

• -i i b

£

og

in-1 IE

.QO

:

Q_ :

Q) 5DOcÖ

0)

o

o

E

—i

CO

CDO •4-t

00

E

Li

en k_ c

0)

Q.

• •• • a.

CD

3

>O

CO - * * , c !

<ü

• «MM E 1

a> i

CLX l •

UJ

>^

.

c

•

(D 1 5

:

h-

/) i

//^^

//(

^,•

:

cp

j/s-

-sf"""'y

/

s ** - ^ • i <* •

^.

<^

C

r

DO

»

ooo

ro

oo

oo

OJ CM

oooo

00

oo

in

oo

CV4

CM ^- *- ^-

oo

oo

CO

oo

oooo

CMooo

COooo

COoooooo

CMoocoooo

GOooo

IDoooooo

CMo

o

c

L.

CL

COoo>

LJE

'

Figure4
I-i5g?ISy

CO

(DoooIE

0)

-QO

CLcoE

COo

00

CDc

•—>

COcE

0)

Q. X

UJ

CO

(D

+-»ocooo- -» o

oo

o

o

oooo

o

o

o O) co r^ CD in

^ to CN

Figure5

WMM^^
cI

?

W

CD • —

O

o

o

I

jQ

O

Qc

D

O

0)

CD '

O

CO

CD -M

O E

00 • —

en Lc CD

• CL

0) CL

> u

D

• CO Q^

Q.

»*—

o

a

o

>

LiJ

(D

E

oooooooooooo

oooooooooooo oioomomoinomom

>•

Figure 6
0- •

were performed on ten groups of nine cities that were randomly placed on

' the coordinate grid. The process was allowed to evolve 32,000 offspring.

r.-. While the optimum solution remained undiscovered, it is of interest to

note that the problem was evidently addressed at two distinct levels. The

^ evolutionary process initially solved the problem at a gross level,

discovering the minimum tour between the groups of cities (Figure 7 and

Efi Figure 8). Insufficient time was allowed to sort out the problem at a finer

I

level of detail. Figure 9 indicates the mean and estimated two-sigma

limits to the reduction of tour length up to the 20.000th iteration.

An extremely large traveling salesman problem was also analyzed.

Here, 256 cities were randomly distributed. Based on the previous results

it was not expected that the adaptive algorithm would discover the

optimum solution in 20,000 iterations; however, after only 10,000

S; iterations it had reduced the initial tour length by roughly 50 percent.

Figure 10 Indicates the "surviving" tour after evaluating 10,000 offspring

* while Figure 11 Indicates the success of the evolutionary process in

discovering better and better tours. The available computation time

0

limited the analysis, however the results were certainly encouraging.

i

The evolutionary program was also extended to allow for cities

[3 distributed in three dimensions. Here, 50 cities were randomly distributed.

^ As expected, the addition of the third dimension had little effect on the

^ adaptive algorithm. The initial tour length was reduced by 50 percent in

{K fewer than 6,000 iterations, see Figure 12. Figure 13 Indicates two views

of the surviving tour after evaluating 20,000 offspring.

I

12 . :
EI

CD

• ^—• • ^— O

1*

O

h

cni « E

0)

JDO 1 i_

11

n i cE

C/D

• CD 1 D

IT)

cn

CD>

c

Q.

CT CO

I*-

"^tfc H-o c

0)

ooo

E d"

•— CN 1»

CD L.

Q. X

a

Lü

GO

oo

GO

G0

II

0) oco

- -• QD>OE£

'c

o

to

CO

CD

4-»ocoOot •—a

.••

Figure7

^^-rt^6^^
CO

CD Oo

CDI O

CLO

CO

JDO

CD>o

CTc

cn

=^ (0

H-

•4-»

0

c

o

(Üo

E

q

i— ro

0)

u

Q. 0)

-4-<

X

o

LxJ lO

in

CD

0) Üco

CO ao

i3EE

^

cn

CDOOOa

^

Figure8
en

CD

•—o

^

o

c

CD

o

0)

A I ^ i E I

(D

• —•

JQ

r-

?:

O _I

L- L>

L'J CL 0) 1 ^ c o o

en

CDo

CO

-

1

.

L.

u^

o

L. CL

—

3

CD>O

K

enc

Q.

<D

^-»OO>

CDE

ooo

ooo

O IDO

ID^ -^iFigure

9

U^^tt:^.^:^::^^^^
en

CD

o

CD

(N

I

CD

o

L_

CL

c

in

o

•

o

E

to

in

in

en II

CD G)

O

o o

00ing

Q

r3

E

CD

>

12

O

Figure 10

tü&müü^^
t%ä^pI

if)

CDÜ

CD

ID

CM

-4-» 1 c 1 CD £ E

CD

CD

>

_Q

O

O CL

L_

F

n

>N

c L. o oC E o• •—

in -4-»

CD

O

O

>

if) LU

CTc

• •—

"03>ö

c3O

ooo

4 CN0

oc

o .h

HO

CDQ

ooo

CMOoo

CO

11111•*f•***********

o

oo

o

o

oo

o

o

o

o

O

o

oo

ooo

o

o

o

o

o

o

o

oo

ooo

o

o

o

o

o CJ

C>J •-

o o» co r- (O lO «r K) CN4 *"

Figure 11

\&®tä^^
5

-

1

E CO

s

0)

co

o COc

?

o 0)

s^_

——

H

n

•—

^

c

(D

«

o

L.

B

E

f-c

1

0) no

(ü

>:

- -'

Ö

00

13

H-J

c

CO

• •—Q

• —^— (0

s 0)

7i CD>

o

i

Ö

O

L_ LO

cn 0)

0)

c

£ •c

o» CL 0) CO

M—

o H—

CO

o

co

o

a

o

o

o•k

a:

o

(N

L.

0)

^

GOO

<D

ia) uO

to• • coo

en

O

<Do>

UJc• —"

LL.

s

Figure 12

jr... s.s-. •/
E

g

s

i

v

?s

CO

c

#o

'in

c

(

•E••-

Q

0)

<D

.E

CO

0)

• •-

•4-» • —

O

o

I

E

^D

O

C

o

E

CO

o

CO

0)

>

Ö

en

c* MM

Q.

o

0)

>

0)

E

oooooooooooooooo

ooooooooooooooo

OaDCO^CsJOCOCO^-CMOCOlD^C^

Figure 13

^ •.''%•'%• S^N'S" '.' V K": V •. r\*«.''v"I','"«.-'%,'%,'Vr%"rN

,r

- -
c

p

t*

I

*••

These experiments Indicated the approximately exponential learning

ability of the adaptive algorithm. However, the quality of the resulting

tours remained to be determined. This can be assessed only when the

distribution of the (n-1 )!/2 tour lengths can be approximated. Two

experiments were performed In this regard.

ö First, 28 cities were positioned In a square of perimeter 720 units.

w This, of course, corresponds to the optimum tour length. A computer

program was written to sample 2500 tours at random and found an

p estimated average tour length of (I - 636.8163 (an average error of

118.8163) with an estimated standard deviation of cr- 59.72235. Because

ä of its flexibility, a gamma function was fitted to describe the error

distribution:

(1) f(x) - (2 x 10"7)(x3)(e' x/30), x i 0.

*{£ Thirty trials were conducted with the adaptive algorithm which yielded an

average tour length of 798.613 after evaluating 20,000 offspring. The

average tour error was approximately 79 units. Integrating (I) from zero

to 79 yields the estimated percentage of tours that were of higher quality

than this average tour error. Here, this integral, calculated using

J5 Simpson's rule, was approximately 0.257. Thus, the average tour error of

the adaptive algorithm was superior to roughly 75 percent of the possible

£ tours, this after evaluating only 3.7 x 10'24 of the state space. It should

- be noted that 23 out of the 30 trials found perfect tours, but because the

^ square was large, locally optimal tours had great length as compared to

^ the optimum tour length. This dramatically increased the average length of

the 30 trials.

13
?.

I

.y

A more complicated experiment was also performed. Here, 36 cities

were organized in four groups of nine with a minimum length tour of 460

«

units. Again, 2500 tours were sampled at random and yielded an estimated

average tour length of 5 • 617.1259 (an average error of 157.1259) with a

^ estimated standard deviation of o - 29.43465. A gamma function was again

fitted to the error distribution;

(2) f(x) - ((5.528 5)(r(28.5))r' (x275)(e"x/5 5). x i 0.

Thirty trials were conducted with the adaptive algorithm which yielded an

average of 5? - 518.7947 for an average error of approximately 59 units.

Integrating (2) from zero to 59 yields the estimated percentage of tours

that were superior to the average results of the adaptive algorithm. This

was computed to be 0.0000006438, that is to say, the adaptive algorithm

produced tours that were generally superior to over 99.9999 percent of all

possible tours, this after examining only 3.87 x 10'36 of the entire tour

state space.

I

^ An additional set of experiments was conducted to directly compare

the adaptive algorithm to the PMX operation. Here, 100 cities were

distributed at random and 30 trials were performed using both methods.

The cities were redistributed for each trial to minimize the effect of an

unusual set of cities. Each algorithm was allowed to generate 20,000

offspring. The results were:

Adaptive Algorithm ££

x - 1454.403 units X • 4319.455 units

s- 110.951 units s- 165.807 units

where X is the average of the thirty trials and s is the standard deviation

,;>; of the sample.

i

14
As mentioned previously, the PMX operation does not retain sufficient

information between parent and offspring to perform effectively.

Essentially, the PMX operation Is equivalent to swapping a random number

of cities In a single tour. The number of cities to be swapped Is equal to

the length of the section of the tour chosen at random. The expected

number and variability of swaps per mutation are Indicated In Figures 14

& and 15. In relatively small problems, on the order of ten cities, the PMX

»v operation averages about three swaps with minimal variance. However, In

larger problems, such as the 100 city problem performed here, the PMX

£ averages more than 33 swaps per mutation with a rather high variance.

This prevents the required link between generations.

.■►

i

I

8

I

»

arousiotfi

Suv essful adaptation does not require sophisticated mutations. In an

evolutk ary scheme only the "behavior" of a coding structure is scored;

the code I*self is never scored. The bottom-up view that emphasizes

mutation operations as the key to adaptive plans Is Incorrect. Competition

occurs not between coding structures but between expressed behaviors.

The particular structure of the code Is generally unimportant.

Further, sophisticated mutation operations can be detrimental. For

-. adaptation to succeed, a sufficient link between parent and offspring must

" be maintained. When this link is destroyed the results can be worse than a

U random search of all possible coding structures. Since the traveling

15

üütääü^^
ciII

pn

co0o

0)

- -•c

CO

Q. O

CO

JQE

0)o

0)

CLX

Lü

0)

oo

•"o

O) o

00o CO

0)

-»-•

o

o

(D V4—o

i.

0)

o

in .DED o 2

^•ono

CN

Figure 14

&&ft&^^^^^

V
i

COO

CO

CD

JD

f—

z:

co

• —• a

"U

u

CÜ 0)

CL O

0)X

CL

2

X CL

LÜ 0)

_rT

0) -f-»

C" Oi

-M

c

M— en O 3

>N

•—O

L- o>

0)

T.

cosO>

a>

'

a

"U 1 • c € o

•oc

1.

0

m

(Si

-

a>\ o \ c \

-

o\ 1.

j.

o\

!•

>

N

\

tr

m

\

t

CL

\

o

\

-

(A

\

»

o

^

l_

\i

0)

\J

JQ

\

E

I

2 ^^1

...

J

oo

oo

oo

oo

oo

oo

oooo

coooomoo

CM

S»

Figure 15

tt^'rt&tt^^
i the code.

i

•J

5

St

salesman's tour is not analogous to an organism's chromosome, operations

of the form of Holland's crossover are unsjitaole. In general, little

emphasis should be placed on specific mutation operations. Modeling a

given mutation operation in order to elicit appropriate behavior is much

like requiring an airplane to possess feathers in order to fly. It is the

mutation and selection of behavior that is imporatant. not the structure of

Search by adaptive methods must avoid stagnation in local optima.

^ Stagnation can be prevented through the use of a noisy payoff function.

This concept Is similar to that suggested by Klrkpatrlck et al. (1983) for

K optimizing simulated annealing, but it is not necessary to resort to such

specific analogies. In a dynamic environment, the rewards and penalties

for different behaviors vary. The search for better and better solutions Is

everlasting. Evolution is a continuing process with no truly optimum

solution. Incorporating noise into the adaptive algorithm prevents

stagnation of the evolving phyletic line.

Clearly, evolutionary adaptation can effectively address the traveling

salesman problem. The experiments described here Indicate the efficiency

of this evolutionary search. But, In any given problem, there Is no

guarantee that the optimum solution will ever be found. Evolution

discovers only what it Is capable of discovering. New solutions that are

superior to old ones tend to survive. Despite this, the adaptive algorithm, a

reification of natural evolution, tends to discover exceedingly appropriate

behavior in the context of a given criteria.

16
* Literature Oted:

I

r

- I.D. Ackley, 'A Connectioi^st Algorithm for Genetic Search,' in Proceedings of en

<

^ Internetion§l Conference on Genetic Algorithms end Their Appliesfions , J.J.

< Orefenstette. Editor, Carnegie-MelIon University, July 1985.

•.' 2. A.K. Dewdney. "Computer Recreations: Exploring the field of genetic algorithms in a

primordial computer sea full of nibs." Scientific Americen, November 1985.

B

3. L.J. Fogel, "Autonomous Automata," IndustrieI Research, February 1962.

.

4. L.J. Fogel. "On the Organization of Intellect," PhD oissertation, U.C.LA 1964.

5. LJ. Fogel. AJ. Owens, M J.Walsh, ^/•////ir/tf/ //7/^///p?/7n? Through Simulated

evolution, John Wiley & Sons, New York, 1966.

6. D.E. Goldberg, R. Lingle, Jr., "Alleles, Loci, and the Traveling Salesman Problem," in

Proceedings of an Internetionel Conference on Genetic Algorithms end Their

Applications , J.J. Orefenstette, Editor, Carnegie-Mellon University. July 1985.

7. J.J. Orefenstette, R. Gopal, 8. Rosmalta. D. Van Gucht, "Genetic Algorithms for the

Treveling Salesman Problem," in ^raofl^//?^' of en Internetionel Conference on

Genetic Algorithms end Their Applications , J.J. Orefenstette, Editx, Carnegie-MelIon

University, July 1985.

•/ 8. J.H. Holland,/to&p/j//i(7/7 in Neturel and Artificial Systems ,\}i\\v*r*\\y iA

Michigan Press, Ann Arbor, 1975.

9. S. Kirkpotrlck, CD. Oelatt, Jr., M.P. Vecchi, "Optimization by Simulated Annealing."

Science,ftty 1983.

10. C.K. Levy. Elements of Biology, third edition. Addlson-Wesley Publishing Company

Inc., Reading, Massachusetts, 1982.

rvI

i

17
G

S AQfifiOdU

A completely random search (with replacement) will take roughly

twice as long to find the optimum solution as an enumeratlve search

(without replacement). To show this, consider the following two theorems:

Theorem 1: If there are ß possible solutions and only one

optimum solution, the expected number or trials that must be

made before the optimum solution Is found, using an enumeratlve

search, assuming one trial Is made at a time, is equal to

(D*l)/2.

:-:

Proof: In an enumeratlve search, sampling is made without replacement.

The probability, therefore, of discovering the optimum solution on any

given trial is equal to the product of the probabilities of not discovering

the optimum solution on any prior trial multiplied by the reciprlcal of the

number of untried solutions. The expected number of trials that would have

to be examined before finding the optimum solution would therefore be:

Ixf(x)- Iß"1 ^Kß-D/ßHß-ir1JKß-D/ßlKß^Aß-DHß^)-'

- (ß-l)((ß-1)/ß][2/3Hl/2l ßl(ß-l)/ßH2/3Hl/2] I

« Iß"12^"' Sß"1• (ß-lHT1 ßß'1

-ß-'d ^ J* • (ß-1)*ß)

ß"Hß(ßH)/2l

" (ß* 1 )/2. Q.E.D.
c •

s

.'

f

i?

Theorem 2: If there are B possible solutions and only one

optimum solution« the expected number of trials that must be

«

made before the optimum solution Is found. In a completely

random search, assuming one trial Is made at a time. Is equal to

D.

Proof: In a completely random search, sampling Is made with

^ replacement. The probability, therefore, of discovering the optimum

solution on any given trial is equal to the product of the probabilities of

i- not discovering the optimum solution on any previous trial multiplied by

the reciprical of the total number of possible solutions. The expected

*:• number of trials that would have to be examined before finding the optimal

solution would therefore be:

2xf(x)• 1 ß"1 21(ß-1 )/Dlß"' 3l(ß-1 VßJ2ß"

1

-

• ß"' (1 2l(ß-l)/ßl SKß-D/fll2)

-ß-'lIAHß-D/ß))]2

>. -ß. Q.E.D.

li&&&&&SÖi^^