Majalah Ilmiah UNIKOM
Vol.8, No. 1
2
H a l a m a n
creases. GA are also prone to the loss of
solutions and their
In this paper, we propose the new archi-
tecture for hybrid optimization based on GA
and SA. It achieves the searching not only
globally, but also locally. In order to evaluate
the proposed architecture, we applies the
proposed architecture to Travelling Sales-
man Problem (TSP). These experiment re-
sults prove that the proposed architecture
achieves superiority results compared to
genetic algorithms and simulated annealing.
The travelling salesman problem (TSP) is
the task of finding the shortest possible tour
through a given set of cities. It is a typical
optimization problem having many practical
applications such as routing, scheduling,
wiring, etc. In the standard TSP, the distance
ij
ji
asymmetric version of this problem and
some other variations, which can be theo-
retically transformed to the standard ver-
sion. In this work, we concentrate on the
standard TSP.
We called the hybrid architecture of Simu-
lated Annealing and Genetic Algorithm as
The Annealing-Genetic Algorithm (AG). Con-
tribution of this paper is to propose AG suit-
able for TSP and compare the performance
of AG between Simulated Annealing and
Genetic Algorithm.
The paper is arranged as follows. Theory of
GA, AS and TSP is provided in Section II. AG
algorithm is presented in Section III. The
simulation results are provided in Section IV.
In Section V, we conclude with conclusion
PRELIMINARIES
Simulated Annealing
Simulated Annealing is an optimization
technique, analogous to the physical proc-
ess of annealing. The method models the
physical process of heating a material and
then slowly lowering the temperature to de-
crease defects, thus minimizing the system
energy.
T
any initial state. A neighborhood operator is
i
E
i
jE
j
E
j
E
i
,
jj
becomes the current state with probability
E
i
E
j
Tji
the current state). The application of the
neighborhood operator and the propabilistic
acceptance of the newly generated state are
repeated either a fixed number of until a
quasi-equilibrium is reached. The entire
above-described procedure is performed
repeatedly, each time starting from the cur-
iT
T
ber of iterations always leads to equilibrium.
T
is accepted, so the algorithm visits a very
large neighborhood of the current state. At
T
become less frequent and the solution stabi-
lizes. Figure 1 shows the pseudocode of SA.
Theres is some SA terminology:
Objective Function. The objective func-
tion is the function we want to optimize.
Temperature. The temperature is the
control parameter in simulated anneal-
ing that is decreased gradually as the
algorithm proceeds. It determines the
probability of accepting a worse solution
at any step and is used to limit the extent
of the search in a given dimension.
Annealing Schedule. The annealing
schedule is the rate by which the tem-
perature is decreased as the algorithm
proceeds. The slower the rate of de-
crease, the better the chances are of
finding an optimal solution, but the
longer the run time.
Genetic Algorithm
Genetic algorithms are heuristics derived
from biological evolution. Whereas simu-
lated annealing at a time just goes from one
point of the solution space to another one,
genetic algorithms deal with many points
simultaneously. Each point represents one
individual (schedule). All individuals together
are called a population. New individuals are
created by genetic operators (mutation and
Muhammad Aria