Simulasi & Permodelan 2

Membangkitkan Bilangan Acak Menggunakan Matlab

GambaranPermasalahanGambaranPermasalahan

Traveling salesman problem(TSP) adalahsuatupermasalahanuntukmendapatkanruteterpendekyang harusdilaluiseorangsales yagharusmelewatisemuakota(n) dengansetiapkotaharusdilaluisatu kali sampaidiakembalikekotaasalnya.

•TSP banyakdigunakandalampenerapannyauntukbidangtransportasi, komunikasidanteknologiinformasi.

•DalamTSP, tujuanyang dicapaiadalahrutedenganjarakterpendek, danbatasannyaadalahsemuakotaharusdilaluidansetiapkotahanyadilaluisatukali.

•Simulated Annealing padaTSP digunakanuntukmenelusuridanmencarisetiapruteyang mungkin, kemudianmendapatkanruteyang jaraknyapaling pendek.

•Model Simulated Annealing untukmenyelesaikanTSP adalahmodel state yang dibangununtukmenyatakanruteyang mungkindandefinisienergiyang dinyatakandengantotal jarakyang ditempuh.

Simulated Annealing PadaTSPSimulated PadaTSP

•State didefinisikandenganruteyang ditempuhuntukmelewatisemuakotasampaikembalikekotaasaldengansyaratsetiapkotaharusdilaluisatukali.

•Bilasetiapkotadinyatakandenganindeks1,2,3,4,…,n makastate didefinisikansebagaipermutasidariindekskota.

•Definisistate adalah:

DefinisiStateDefinisiState(){}jijiissNsS≠≠∈=

Contohstate untukTSP dengan8 kota, dimanasetiapkotadinyatakandenganindeks1,2,3,4,5,6,7, dan8 adalahsebagaiberikut:

1 –2 –3 –4 –5 –6 –7 –8 –1

1 –2 –5 –7 –8 –6 –4 –3 –1 ContohState 1234567812345678

•KarenadidalamTSP dicarirutedenganjarakterpendek, makaenergididefinisikandengantotal jarakyang ditempuh.

•Energididefinisikan:

diadalahjarakkotakes(i) dans(i+1), bilaposisidinyatakansebagaikoordinat2 dimensi(x,y) makadidapatdihitungdengan:DefinisiEnergiDefinisiEnergiΣ==niidE1()()22)1()()1()(+−++−=isisisisdyyxxi

FlowchartFlowchart

StartBangkitkanstate awal(S)HitungEnergi(E)Sopt􀃅SEopt􀃅EUpdate state (S)HitungEnergi(E)prob=exp-(E-Eopt)/TSopt􀃅SEopt􀃅EKriteriaStopTYStopCooling Schedulle

•Prosesmembangkitkanstate awaldapatdilakukandenganmengurutkannomorindekskotamisalkan1,2,3,4,….,n (carainiyang dijelaskandalammodulinikarenasangatmudahdilakukan)

•Cara lain yang bisadilakukandenganmenggunakanacakpermutasi.

MembangkitkanState AwalMembangkitkanState Awal

•Update state adalahsuatuprosesuntukmengubahsusunanrutedenganmemilihsebagiankomposisiurutan(nomorkotak1 sampaidengannomorkotak2) secaraacak.

•Pengubahandapatdilakukandengancaraswap padakomposisiyang ditentukan.

k1

k2

Sebelum Update

Sesudah Update1 –2 –5 –7 –8 –6–4 –3 –1 1 –2 –6 –8 –7 –5–4 –3 –1 Update StateUpdate State

#include <fstream>

#include <stdlib.h>

#include <math.h>

float x[100], y[100];

int s[100], sOpt[100], nKota;

float e, eOpt;

// Membangkitkan data kota

// dan koordinatnya secara acak

void BangkitkanDataKota(){

cout << “Jumlah kota = “; cin >> nKota

for(int i=0;i<n;i++){

x[i]=(float)(10*rand()/RAND_MAX);

y[i]=(float)(10*rand()/RAND_MAX);

}

}MembangkitkanData KotaMembangkitkanData Kota

// Membangkitkanstate awal

// denganmengurutkanlangsung

void BangkitkanStateAwal(){

for(inti=0;i<n;i++) s[i]=i;

hitungEnergi();

}

// State Optimal

void StateOptimal() {

for(inti=0;i<n;i++) sOpt[i]=s[i];

eOpt=e;

}

// MenampilkanState

Void TampilkanState() {

for(inti=0;i<n;i++) cout<< sOpt[i] << “ “;

cout<< “ energi= “ << eOpt<< endl;

}MembangkitkanState AwalMembangkitkanState Awal

float hitungEnergi(){

float jarak=0;

inti,j;

for(i=0;i<n-1;i++){

dx=sqr(x[s[i]]-x[s[i+1]]);

dy=sqr(y[s[i]]-y[s[i+1]]);

d=sqrt(dx+dy);

jarak=jarak+d;

}

dx=sqr(x[s[n-1]]-x[s[0]]);

dy=sqr(y[s[n-1]]-y[s[0]]);

d=sqrt(dx+dy);

jarak=jarak+d;

return jarak;

}MenghitungEnergiMenghitungEnergi

// Update state

void UpdateState(){

intk1,k2,i;

for(i=0;i<n;i++) s[i]=sOpt[i];

k1=int(nKota*(float)rand()/RAND_MAX);

k2=int((nKota-k1)*(float)rand()/RAND_MAX)+k1;

for(i=k1;i<k2;i++){

s[i]=sOpt[k2+k1-i];

}

hitungEnergi();

}ProsesUpdate StateProsesUpdate State

void main(){

inti, maxIter;

float p, To, Tn, T;

cout<< “jumlahiterasimax = “;

cin>> maxIter;

To=0.1; Tn=0.0001;

BangkitkanDataKota();

BangkitkanStateAwal();

StateOptimal();

TampilkanState();

for(i=0;i<maxIter;i++){

UpdateState();

p=rand;

if(p<exp(-(e-eOpt)/T)) StateOptimal();

TampilkanState();

T=To*(float)pow(Tn/To,i/n);

}

}Program UtamaProgram Utama

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s


%d blogger menyukai ini: