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

Download: **PDF**

Copyright © 2011 Unikom Center

Copyright © 2011 Unikom Center