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

Page 1 of 12
next >

Majalah Ilmiah UNIKOM

Vol.8, No. 1

1

H a l a m a n

INTRODUCTION

Simulated Annealing (SA) and Genetic

Algorithms (GA) are similar, naturally moti-

vated, general purpose optimization proce-

dure [13]. Both techniques work reasonably

well on a variety of problems and require

little problem-specific knowledge other than

fitness or energy (cost) information. The two

techniques generate new points in the

search space by applying operators to cur-

rent points, and move probabilistically to-

wards more optimal regions of the search

space.

Some difference between GA and SA is GA

are naturally parallel. They iterate an entire

population using a binary recombination

operator (crossover) as well as a unary

neighborhood operator (mutation). SA, on

the other hand, iterates a single point (using

only a neighborhood operator), it is not eas-

ily run on parallel processors. It would thus

be desirable to transfer the parallel process-

ing capabilities of GA to SA.

SA maintains only one solution at a time,

whenever it accepts a new structure, it must

discard the old one. There is no redundancy

and no history of past structures. The end

result is that good structures and substruc-

tures (in the extreme case the global opti-

mum) can be discarded, and if cooling pro-

ceeds too quickly, may never be regained.

prone. SA compensates by increasingly sam-

pling good solutions as temperature de-

This paper presents a new algorithm based on integrating simulated annealing

and genetic algorithm to solve travelling salesman problem. We called the pro-

posed architecture as The Annealing-Genetic Algorithm (AG). The core of the AG

is based on genetic algorithms. Simulated annealing method is used to acceler-

ate the convergence of the genetic algorithm by applying the simulated anneal-

ing test for all the population members. In order to evaluate the AG, we applies

the proposed architecture to Travelling Salesman Problem especially for the

larges data problem. The algorithm has been implemented in LabVIEW and

tested on several sets of TSP data. For the largest data instance used is 1002

cities (i.e., pr10022), the actual population size used is only 8. For small sets of

data (less than 100 cities), AG can find the optimal solutions. These experiment

results prove that AG improves the distance 2.25% over SA and 3.09% over GA.

But AG computation time is more complex than both SA and GA algorithm, so

AG takes 6.47 times slower than SA and 1.3 times than GA algorithm. In appli-

cation, AG needs 13.88 bytes units of memory, while SA only needs 10.67 bytes

unit memory and GA algorithm needs 31.33 bytes units memory.

Index Terms – Crossover, Genetic algorithm, Simulated Annealing, Travelling

Salesman Problem

bidang

REKAYASA

AN INTEGRATION OF SIMULATED ANNEALING AND GENETIC ALGORITHM

MUHAMMAD ARIA

Department of Electrical Engineering

Engineering and Computer Science Faculty

Universitas Komputer Indonesia