< prev

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

Page 2 of 12
next >

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