< prev

Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8Page 9Page 10Page 11Page 12

Page 6 of 12
next >

Majalah Ilmiah UNIKOM

Vol.8, No. 1

6

H a l a m a n

days). Table 1 shows the example of TSP

problem. And Figure 3 shown the distributin

city from that problem.

INTEGRATION OF SIMULATED ANNEALING

AND GENETIC ALGORITHM

In Annealing-Genetic Algorithm (AG), use-

ful features from both methods are com-

bined : the convergence property from simu-

lated annealing and explicit parallelism from

genetic algorithms. AG starts with a very

high temperature and generates a large

number of random solutions (initial popula-

tion). Then crossover and mutation opera-

tors are applied to generate a new popula-

tion. Figure 4 shows the pseudocode of AG.

This algorithm captures the essence and

spirit of SA. Suppose we simultaneously run

multiple, independent SA on a problem, but

we synchronize cooling across process. The

only thing missing is to reconcile the inde-

pendent solutions. This is where crossover

comes in. Crossover can be viewed as an

extension to the common SA neighborhood

operator.

The algorithm starts with a high tempera-

ture, which is then reduced in steps :

where :

T

t+1

next temperature

T

t

current temperature

k

k

0.5. The number of iteration for one tem-

perature step has been chosen to be 100 x

number of city. This number was determined

by experiment: smaller number resulted in

worse solutions, larger number only in-

creased the computation time.

At step 9, we use inversion mutation for

permutation. The procedure is pock two al-

leles at random and then invert the sub-

string between them.

At step 18, we use order 1 crossover. The

idea is to preserve relative order that ele-

ments occur. The informal procedure is :

 choose an arbitrary part from the first

parent,

 copy this part to be first child,

 copy the numbers that are not in the first

part, to the first child starting right from

cut point of the copied part using the

order of the second parent and wrapping

around at the end

The algorithm has been implemented in

LabVIEW. Figure 5 shows Front Panel of Lab-

VIEW program and Figure 6 shows the Block

Diagram.

EXPERIMENT RESULTS

To evaluate the proposed architecture, we

applied AG, SA and GA to TSP problem. We

tested it on the following six set of data :

Ulysses16 (16 city), Bays29 (29 city), Eil51

(51 city), KroA100 (100 city), Tsp225 (225

city) and Pcb442 (442 city). For every

method we run three trial and take the aver-

age solution. Table 2 shows the results. The

Muhammad Aria

City

x

y

1

38.24

20.42

2

39.57

26.15

3

40.56

25.32

4

36.26

23.12

5

33.48

10.54

6

37.56

12.19

7

38.42

13.11

8

37.52

20.44

9

41.23

9.1

10

41.17

13.05

11

36.08

-5.21

12

38.47

15.13

13

38.15

15.35

14

37.51

15.17

15

35.49

14.32

16

39.36

19.56

Table 1.

TSP Problem from Ulyssess16 (16 cities)

T

t+1

= k.T

t

(1)