P EN Y ELESA I A N T RA V EL L I N G S AL ESMAN P RO BL EM (TSP ) A SI M ETR I S D EN GA N A LGOR I TM A GEN ETI K C O MMO N AL I T Y

Abstract

T rave ll ing Salesm an Problem

(T S P ) a da lah suatu

pe nc a ria n rut e

pe rja lan a n n

kota de n g a n

bia y a

ter mu ra h de n ga n men g unjun g i

se mua kota

ha n y a

sa tu

ka li . B ia y a

da pa t diasumsi ka n

se ba ga i jar a k, w a ktu, ba h a n b a ka r,

da n s e ba ga in y a . B e rda sa rka n

bia y a , pe rma sa lah a n

TS P

da pa t diba g i menj a di dua , y a it u TSP sim e tri s

da n

TSP a sim e tris.

P a da

TSP sim e tris,

bia y a

da ri

kota

1

k e

kota

2

a da lah

sa ma

de ng a n

bia y a

da ri

kota

2

ke

kota

1.

S e da n g ka n

pa d a

TSP a sim e tris,

bia y a

d a ri

kota

1

ke

kota

2

ti da k sama

de n g a n bia y a

da ri kota 2 k e

kota 1.

Alg or it ma

Ge ne ti k

C o mm onali ty

mer up a ka n

suatu

pe n g e mban ga n

d a ri

a lg or it ma

Ge ne ti ka .

J ika

da lam

a l g or it ma

g e n e ti ka

ba ku,

pr oses

re p roduk si

dil a kuka n

mela lui

ope ra to r

tukar

sil a ng

da n

mut a si.

S e ti a p

kr omos om

diev a luasi

de n g a n

mengg un a ka n

fun g si

fi tn e ss .

S e da ng k a n

pa da

a l goritm a

g e ne ti k

c omm ona li ty ,

ope ra si

tukar

sil a ng

dide finisi ka n

ke mbali

da lam

dua

ta ha p

(Che n

&

S tephe n,

1999)

:

1)

meme li ha ra

c om mon

sc he ma

maksim a l

da ri

dua

induk,

da n

2)

mele ngka pi

solus i

de nga n

c onst ruction

he uris ti c .

Ka re na

ke t ur una n

y a n g

dihasil ka n

a ka n

lebih

ba ik

dibanding ka n

de n ga n

ke dua

indukn y a ,

maka

e vo lusi

a ka n

ter jadi

tanpa

men y a t a ka n

se leksi a lam

se c a ra

e ks pli sit . De nga n ka t a

lain , e volus i ter j a di tanpa

melibatka n fung si fi tness .

P e ne li ti a n dil a kuka n de nga n be b e ra p a

l a ng k a h. L a n g k a h pe r tama

memba ng kit ka n populas i a wa l (r ute a w a l) me ngg una k a n c onst ruction

he uris ti c

de nga n metode

A I

( Arbit rary Inse rti on ). L a n g k a h ke dua

mela kuka n re p rod uksi

solus i

ba ru de n ga n ope r a si tukar

sil a n g . L a n g k a h ke ti g a

m e mbentuk pop ulasi ba ru (k umpul a n rute )Berdasarkan penelitian yang telah dilakukan, didapatkan hasil bahwa jarak perjalanan terpendeknya sepanjang 1007 km dengan rute 1-13-24-7-20-23-22-19-1621-25-4-11-9-15-18-14-2-17-8-10-12-5-3-6

dan diperoleh kesimpulan dapat dihasilkan jarak yang sama dengan rute yang berbeda disebabkan adanya proses penyisipan kota-kota yang tidak terdapat pada Graf Partial Order menggunakan metode AI. .