Pencarian Jalur Terbaik Menggunakan ParticleSwarm Optimization untuk mengoptimasi Lalu

Lintas KendaraanSafril Rizki Waluyo¹, Mochamad Hariadi², I Ketut Eddy Purnama³

Abstrak—Particle Swarm Optimization merupakan salah satuAlgoritma optimasi yang bisa di aplikasikan pada permasalahanpath finding. Basic PSO dapat digunakan pada proses optimisasiruang bebas untuk menemukan suatu target koordinat x dany. Basic PSO sangat baik untuk digunakan pada permasalahanruang bebas. Namun Basic PSO tidak cocok untuk digunakandi permasalahan ruang terbatas seperti pada pencarian jalan.Modifikasi perlu dilakukan untuk diaplikasikan ke obyek pelakupada simulasi. Penerapan Modified PSO pada obyek memilikikeuntungan obyek pelaku dapat bertindak sebagai muti agentyang secara otomatis mencari jalur menuju goal.

Kata Kunci—Particle Swarm Optimization, Multi agent, PathFinding algorithm.

I. PENDAHULUAN

S IMULASI Pencarian jalan terbaik adalah suatu prosesyang dilakukan dalam bidang komputasi agar dapat

mencapai suatu tujuan secara tepat dan cepat. Pencarian jalanterbaik dimulai dari satu node menuju ke node yang lainnyadengan menggunakan parameter parameter yang ada. Darinilai yang parameter yang didapat, keputusan pengambilanrute dapat dilakukan dengan cara membandingkan nilai yangdi dapat untuk setiap jalur dan dipilih nilai yang palingoptimum.

Algoritma path finding yang handal dibutuhkan agar prosespencarian jalur dapat diselesaikan secara tepat dan cepat.Aplikasi navigasi terkini banyak yang masih menggunakanmetode path finding dengan tipe penelusuran node pernode. sehingga dibutuhkan waktu yang lumayan lama untukmengalkulasi rute yang akan ditempuh. Dengan metodepencarian jalur tipe eksplorasi graph secara keseluruhandiharapkan dapat mengurangi waktu kalkulasi rute menjadilebih singkat atau juga bisa digunakan secara realtime.

II. DASAR TEORI

Swarm intelijen adalah disiplin ilmu yang berkaitan denganalam dan sistem buatan yang terdiri dari banyak individuyang mengkoordinasi menggunakan kontrol desentralisasi danself-organization. Secara khusus, disiplin ini berfokus padaperilaku kolektif bahwa hasil dari interaksi lokal dari individusatu sama lain dan dengan lingkungan mereka. Contoh

(1) Safril Rizki Waluyo, Bidang Studi Teknik Komputer & Telematika,Jurusan Teknik Elektro ITS Surabaya.

(2) Mochammad Hariadi, ST, MSc, PhD., Dosen Pembimbing I, BidangStudi Teknik Komputer & Telematika, Jurusan Teknik Elektro ITS Surabaya.

(3) Dr.I Ketut Eddy Purnama ST., MT., Dosen Pembimbing II, Bidang StudiTeknik Komputer & Telematika, Jurusan Teknik Elektro ITS Surabaya.

dari sistem dipelajari dengan kecerdasan berkelompok adalahkoloni semut dan rayap, segerombolan ikan (schools of fish),sekawanan burung (flocks of bird), kumpulan dari hewandarat. Beberapa artefak manusia juga jatuh ke dalam domainkecerdasan berkelompok, terutama beberapa sistem multi-robot, dan program komputer juga tertentu yang ditulis untukmengatasi masalah optimasi dan analisis data.

Particle Swarm Optimization(PSO) adalah suatupopulasi yang berdasarkan teknik optimasi stokastik yangdikembangkan oleh Dr Eberhart dan Dr Kennedy padatahun 1995, terinspirasi oleh perilaku sosial dari burungberkelompok (flock of bird) atau sekumpulan ikan (school offish)[2].

Setiap partikel yang melacak koordinat dalam ruangmasalah yang berhubungan dengan solusi terbaik (kebugaran)yang telah dicapai sejauh ini. (Nilai kebugaran juga akandisimpan) Nilai ini disebut pbest. "terbaik" lainnya, nilai yangdilacak oleh Particle Swarm Optimizer adalah nilai terbaik,sejauh yang diperoleh oleh setiap partikel di tetangga partikel.Lokasi ini disebut lbest. saat sebuah partikel mengambil semuapopulasi sebagai tetangga topologi nya, nilai terbaik adalahsebuah global terbaik dan disebut gbest.

Pada kondisi awal setiap Partikel terbang bebas dalamposisi yang acak. Konsep optimasi partikel terdiri darikerumunan, pada setiap langkah waktu, mengubah kecepatan(mempercepat) setiap partikel terhadap perubahan pbest danlokasi lbest (versi lokal dari PSO). Percepatan dibobot denganistilah acak, dengan nomor acak terpisah yang dihasilkan untukpercepatan ke arah pbest dan lokasi lbest.

Pada Basic PSO parameter yang pasti digunakan adalahposisi partikel, inertia weight, konstanta, kecepatan partikel,posisi terbaik partikel dan posisi global terbaik. dari beberapaparameter yang di gunakan diatas dapat membentuk

Gambar 1: Update Posisi pada Particle Swarm Optimization(http://www.uni-leipzig.de/~vignesh/research.html)

update posisi dilakukan secara serempak di tiap tiappartikel. update partikel dilakukan dengan menggunakanpersamaan dasar PSO

V(t + 1) =wV(t)+C1(P (t)−X(t))+C2(G(t)−X(t)) (1)

Pemutakhiran Posisi Partikel dapat dilakukan denganmenggunakan persamaan

X(t + 1) = X(t) + V(t + 1) (2)

Pada Pengimplementasian Program PSO secara dasar. adabeberapa langkah dasar yang selalu dilakukan yaitu:

1) Inisialisasi posisi partikel secara acak2) Inisialisasi kecepatan partikel secara acak3) Pencarian global best partikel position4) Pemutakhiran kecepatan setiap partikel5) pemutakhiran posisi setiap partikel6) pencarian global best partikel position kembali

III. DESAIN SISTEM

Desain dari Penelitian ini dibagi menjadi beberapa tahapanpengerjaan yaitu pembuatan environment, penulisan scriptpada Matlab dan Python, dan pengimplementasian kedalam lingkungan Blender. komponen komponen pentingyang menyusun penelitian implementasi Particle SwarmOptimization untuk mengoptimasi lalu lintas kendaraanini adalah, lingkungan environment, obyek pelaku berupakendaraan, sensor, actuator, dan controller yang berupascript Python. sebelum di implementasikan dalam lingkungan3D. Script terlebih dahulu di uji coba yaitu dengan caradisimulasikan pada program simulasi matematika matlab.

A. Desain obyek Simulasi

obyek yang bentuknya terlalu rumit ,memiliki banyakvertex, bisa dapat memperberat sistem. Partikel disini adalahsuatu obyek yang multi agent. Partikel ini dapat di tambahkanke dalam environment tanpa mengurangi sifat sifat yangdimilikinya. semakin banyak partikel yang ditambahkan,semakin berat pula proses yang dikerjakan. Untuk mengatasimasalah sistem yang bekerja terlalu berat, maka digunakanlahobyek yang sederhana obyek tersebut adalah cube.

Desain jalur lalu lintas di desain secara sederhana dalamsumbu axis x dan y sebagai tempat jalur mobil. Bagiansamping jalur lalu lintas di beri badan pembatas agar obyekkendaraan tetap berada di jalur. Sehingga mobil tidak bergerakliar pada saat diimplementasikan algoritma PSO. Berikutadalah beberapa contoh bentuk jalur lalu lintasnya. pada sistemdirancang agar algoritma PSO dapat berjalan pada setiapdesain jalur lalu lintas yang ada. berikut adalah desain jalurlalu lintas yang dihasilkan oleh blender.

B. Desain Sistem PSO

Penerapan sistem PSO dilakukan dalam tiga tahapan.Tahapan tersebut adalah pensimulasian dalam matlab,Penganalisaan sifat sifat partikel dan menerjemahkan dalampermasalahan lalu lintas, dan pengimplementasian PSO dalamBlender dengan menggunakan bahasa python dan BlenderGame Engine.

Tahapan pertama yang di lakukan adalah pensimulasiandalam Matlab. setelah pensimulasian dalam Matlab berhasilmaka sifat difat partikel dapat dianalisa dan di terapkan padapermasalahan lalu lintas. setelah tahap kedua diselesaikanmaka metode siap diimplementasikan dalam game padaBlender.

Pada Pengimplementasian Program PSO secara dasar. adabeberapa langkah dasar yang selalu dilakukan yaitu:

1) Inisialisasi posisi partikel secara acak2) Inisialisasi kecepatan partikel secara acak3) Pencarian global best partikel position4) Pemutakhiran kecepatan setiap partikel5) pemutakhiran posisi setiap partikel6) pencarian global best particle position kembali

update posisi dilakukan secara serempak di tiap tiap partikel.update partikel dilakukan dengan menggunakan persamaandasar PSO

V(t + 1) =wV(t)+C1(P (t)−X(t))+C2(G(t)−X(t)) (3)

Pemutakhiran Posisi Partikel dapat dilakukan denganmenggunakan persamaan

X(t + 1) = X(t) + V(t + 1) (4)

1) Desain Sistem PSO pada Matlab: Tujuan dariimplementasi PSO dalam matlab ini adalah untukmensimulasikan apakah PSO telah dapat bekerja secarabaik atau tidak untuk permasalahan pencarian titik targetberupa koordinat. Data pada koordinat partikel di gambarkanpada Plot sehingga pergerakan sekawanan partikel dapatterlihat langkah demi langkah. langkah selanjutnya adalahmenguji permasalahan yang sama, yaitu pencarian titikkoordinat tujuan. Pengaplikasian PSO di Matlab memilikitarget untuk mencari titik tujuan yang telah di tentukan. padapengaplikasian PSO pada matlab ini dapat juga diketahui sifatsifat dari PSO sehingga pada saat pendesainan pada pythonuntuk Blender bisa diketahui sifat partikel. setelah diketahuisifat-sifat partikel, sifat tersebut di terjemahkan dalam bahasadan perilaku obyek di Blender.

2) Desain Sistem PSO pada Blender Game Engine:Sama halnya dengan implementasi dalam Matlab namunimplementasi PSO dalam Blender Game Engine digunakanuntuk simulasi yang real time. Bahasa python merupakanbahasa yang digunakan dalam blender untuk membuat sebuahsistem yang lebih kompleks. Blender memiliki sebuah gameengine yang digunakan untuk mengatur sistem didalamnya.Namun game engine dari Blender ini memiliki kekuranganyaitu walaupun penggunaannya sangat mudah namun diamemiliki keterbatasan dalam penggunaan. karena hal tersebutscripting python PSO sangat membantu dalam penerapanParticle Swarm Optimization. Penulisan script PSO padapython berbeda dengan penulisan pada matlab. Pada Matlabdata yang diolah adalah suatu larik, sedangkan pada BlenderGame Engine yang di olah adalah sensor dan aktuator suatuobyek yang di gunakan untuk berinteraksi dengan obyek yanglain.

Game Engine pada Blender bersifat berorientasi obyek.Game Engine pada Blender ini dapat membuat setiap obyekmenjalankan perilaku obyek masing masing yang berbeda.Pemrograman pada Python harus memperhatikan 3 kondisisensor obyek, aktuator obyek, dan obyek di scene padaBlender.

C. Desain Perilaku Partikel

Individu partikel pada Particle swarm memiliki sifat sifatyang dimiliki individu pada sekawanan burung atau jugaindividu pada sekelompok ikan. setiap individu bisa bekerjasecara individu namun tidak melupakan tugasnya sebagaikelompok.

Partikel pintar multi agent ini di desain untuk memiliki sifatsifat dan kemampuan individu pada burung ataupun ikan ini.sifat ini akan terus di turunkan apabila ada obyek baru yangsatu tipe dengan partikel, yaitu berjenis partikel juga, sehinggaindividu baru dapat berperilaku layaknya partikel yang lain.

Ada beberapa sifat dasar yang harus dimiliki setiap partikel1) Partikel dapat melihat posisi sekitarnya2) Partikel dapat merasakan partikel lain yang berada di

sekitarnya3) Partikel dapat mengetahui apa yang sedang dicari4) Partikel dapat mengetahui Posisinya pada suatu

environment5) partikel dapat mengenali mana obyek lain yang

bertindak sebagai partikel6) partikel dapat mengetahui jaraknya dengan partikel lain7) partikel dapat mengumpulkan informasi dari

environment maupun dari partikel lain8) partikel dapat menghindari tabrakan dengan lingkungan.9) partikel memiliki kecepatan untuk mencapai suatu posisi

10) partikel dapat terbang bebas apa bila tidak tahu apa yangdicari

IV. IMPLEMENTASI SISTEM

Langkah-langkah implementasi adalah sebagai berikut:

A. Penerjemahan Behaviour ke Dalam Particle

1) Partikel dapat melihat keadaan sekitarSebagai pengganti mata pada obyek, sensor yang digunakan adalah sensor RAY

2) Partikel dapat merasakan partikel disekitarnyaPartikel menggunakan near sensor yang di settingmemiliki kedalaman tertentu untuk merasakan partikeldi sekitarnya

3) Partikel dapat mengenali targetPartikel mengetahui apa yang di cari. Tujuan utama daripartikel tersebut adalah mencapai titik tercepat menujugoal.

4) Partikel dapat mengetahui letak koordinat diriPartikel dapat mengetahui letak koordinat dirinya padasistem dengan menggunakan fungsi Python list [x,y,z]getPosition()

5) Partikel dapat mengenali mana obyek lain yangbertindak sebagai partikel

Partikel dapat mengetahui mana benda lain yangmemiliki karakteristik yang sama dengan dirinya. Sensornear, touch, ray dan radar menggunakan properties danmaterial untuk mengetahui target yang tepat.

6) Partikel dapat mengetahui jaraknya dengan partikel lainPartikel dapat menghitung dan memperkirakan jarakdengan partikel lainnya dengan cara menghitung denganfungsi pada library Game Logic getDistanceTo();

7) Partikel dapat mengumpulkan informasi darienvironment maupun dari partikel lainPada game Logic dibuat suatu hubungan yang berfungsisebagai pencarian data dari environment denganmenggunakan kombinasi touch sensor dan propertiessensor.

8) Partikel dapat menghindari tabrakan dengan linkungan.Metode menghindari tabrakan dapat dilakukan dengankombinasi radar sensor dan move actuator.

9) Partikel memiliki kecepatan untuk mencapai suatu posisiSetiap partikel memiliki kecepatan untuk meng-updateposisi dirinya

10) Partikel dapat terbang bebas apa bila tidak tahu apa yangdicariPada fungsi ini apabila partikel tidak menemukanapapun pada sekitarnya partikel akan terbang bebas padaruangan tersebut.

B. Penggunaan Game Engine BlenderPengaturan interaksi dari satu obyek ke obyek lain

diperlukan suatu controller untuk setiap obyek yang ada.Controller Obyek dibuat pada Game Engine yang telahdisediakan program Blender. Ada dua metode pengaturanobyek pada Game Engine yaitu pengaturan dengan logic brickdan pengaturan dengan menggunakan Python script controller.

Obyek yang ada diatur dan diberi kemampuan bertindakdengan menggunakan logic brick dan script Pythondari gameengine Blender sehingga proses dapat dilakukan. Obyek utamaakan mengikuti partikel pada ruang bebas yang paling dekatdengan obyek tersebut. Proses akan berlanjut sampai obyekdapat menemukan titik tujuannya.

Untuk membentuk kondisi sebagai pensimulasian kondisinyata diperlukan suatu parameter khusus yang dapatmerepresentasikan hambatan hambatan yang ada di lalu lintas.Keamanan, kemacetan, dan kualitas jalan adalah problemyang harus diperhatikan dalam simulasi. Informasi mengenaikondisi lalu lintas diberikan pada Obyek jalan. Map padaenvironment dapat di bagi menjadi beberapa sektor. Di setiapsektor diberikan suatu property untuk membawa informasiinformasi kualitas jalan. Setiap sektor dari jalan dapat dideteksipartikel yang masuk dan memberikan informasi tentangkondisi jalan dan juga tingkat kepadatan.

actuator, controller, dan sensor didesain untuk berinteraksiantara satu dengan yang lainya. semakin komplek AI semakinbanyak pula logic brick yang dibutuhkan

V. PENGUJIAN SISTEM

Ada dua tahap pengujian sistem, pertama adalah tahapsimulasi pada Matlab dan kedua adalah tahap simulasi padaLingkungan Virtual 3D Blender.

Pengujian dilakukan dengan cara simulasi dengan komputeryang memiliki spesifikasi sebagai berikut:

1) Komputer Desktopa) Komputer Desktop 1

• Processor : AMD(R)Athlon(R) 64 4200• Memori : 512 MB• VGA Card : GeForce 8500 GT 512Mb• Sistem Operasi : Microsoft (R) Windows (R) XP

(R)b) Komputer Desktop 2

• Processor : Intel(R) Core2(R) Duo CPU @3GHz• Memori : 1 MB• VGA Card : Intel Q35 Expresss 256Mb• Sistem Operasi : Microsoft (R) Windows (R) XP

(R)c) Komputer Desktop 3

• Processor : Intel i7 @2.4Ghz• Memori : 2 GB• VGA Card : GeForce• Sistem Operasi : Ubuntu 9.10 (karmic koala)

2) Komputer Laptop• Processor : Intel(R) Pentium(R) 4 CPU 1.50GHz• Memori : 768 MB• VGA Card : ATI (R) Radeon(R) 9200 64 MB• Sistem Operasi : Ubuntu 9.04 (Jaunty Jackalope)

Particle Swarm Optimization untuk mengoptimasi lalu lintaskendaraan berhasil dibuat pada dua bahasa yang berbedadisimulasikan dan diimplementasikan menggunakan Matlab,Blender Game Engine, dan Python scripting. Hasil pengujiandapat dilihat pada subbab berikutnya

A. Pengujian pada Matlab

Simulasi pertama dilakukan pada Matlab. Program dapatberjalan dengan lancar. Setelah program dapat dijalankandengan lancar hasil tersebut di bandingkan dengan algoritmayang lain.

Pada pengujian di Matlab ini. Ada beberapa parameter yangharus diketahui. Target berupa titik tujuan bernilai tertentuyang menunjukkan koordinat. Jumlah Partikel di uji coba dandiberi nilai tertentu. Koordinat awal partikel, kecepatan awalpartikel bernilai random. konstanta C1 dan C2 diberi nilai yangrandom antara 0-1. Inertia weight diset secara manual antara0.1-0.9

1) Nilai Parameter untuk Pengujian• Banyak partikel : 32• Inertia Weight : 0.6• konstanta C1 dan C2 bernilai Random antara 0-1• posisi awal partikel dan kecepatan awal partikel

bernilai random• target bernilai (5, 6)

2) Hasil PengujianPada hasil gambar hasil pengujian perulangan ke-1(gambar 2a) , partikel mencari targetnya denganmencari informasi posisi terbaik partikel yang pernahdilalui. Semakin banyak iterasi yang dilakukan hasil

(a) Pengujian

(b) Hasil Konvergen padaperulangan ke 20

Gambar 2: Hasil Pengujian pada Matlab

makin lama akan mendekati hasil konvergen pada titik(5,6)hasil konvergen didapat pada perulangan ke 20 (gambar2b)

B. Pengujian pada Blender

1) Pengujian Sifat PSO pada Partikel: Pengujian inidilakukan pada sifat sifat PSO pada partikel.

Tabel I: Tabel Pengujian SifatNo Sifat Status

1 Dapat melihat keadaan sekitar v2 Merasakan partikel disekitarnya v3 Mengenali target v4 Mengetahui letak koordinat diri v5 Mengenali obyek lain v6 Dapat mengukur jarak dengan obyek lain v7 Dapat mengumpulkan informasi properti obyek v8 Menghindari Tabrakan dengan lingkungan x9 Memiliki Kecepatan v

10 Dapat terbang bebas v

Pada tabel I, dari pengujian sifat ada satu sifat yang belumbisa di implementasikan kedalam partikel, yaitu sifat dapatmenghindari tabrakan dengan lingkungan sekitar. Sifat initidak dimasukkan ke dalam sifat partikel karena terbatasnyalebar ruang jalan. ketika diimplementasikan ke dalam sifatpartikel partikel bergerak berputar putar disebabkan karenajarak dinding pembatas jalan dengan partikel terlalu dekat.

2) Pengujian Pencarian Jalan : Simulasi keduadilaksanakan dengan menggunakan Blender game engine danjuga Script Python. Program dapat berjalan.

Pengujian dilakukan dengan beberapa komputer denganspesifikasi yang berbeda. Obyek dapat menemukan targetdengan bantuan partikel yang lain. Obyek ini berupa multiagent sehingga sifat dari satu partikel dapat di turunkanke partikel lain. Setiap partikel memiliki perilaku yangsama dengan partikel lain. Perilaku dari partikel ini bersifat

umum dan dapat di gunakan dalam setiap bentuk peta danenvironment.

Pembacaan informasi property pada jalan dapat dilakukanoleh partikel sehingga setiap partikel dapat mengetahuikualitas lalu lintas yang dilewati, akan tetapi informasi yangdidapat oleh partikel ini belum bisa di olah lebih lanjut karenaketerbatasan penulisan perintah pada script Python yang dimiliki oleh Blender.

Blender memiliki kekurangan pada bagian transferinformasi. Transfer informasi bisa dilakukan antara satuobyek dengan obyek yang lain. Namun untuk permasalahanmulti agent. Informasi tidak bisa di-transfer begitu saja, karenasetiap agent memiliki penamaan yang berbeda. Sedangkanlogic brick pada Blender Game engine tidak memilikiscript penggantian nama obyek untuk mengambil property.Pengambilan informasi properties harus di modifikasi agarpengambilan nama script dapat berlaku secara global.

3) Lingkungan Jalan pada Pengujian: Setelah parameterpada area di set, script PSO untuk partikel kemudian dapatdijalankan.

1) contoh Blok jalan

(a) 1 Blok dengan 2 Properti (b) 3 Blok dengan 3 Property

Gambar 3: Jalan Lalu Lintas Satu Blok

Gambar 3 adalah gambar dari blok Jalan untuk simulasi.Blok tersebut terdiri dari bagian yang masing masingbagian memiliki nilai informasi tersendiri. Gambar 3adan gambar 3b menunjukkan pembagian bagian dengannilai yang berbeda

4) Hasil Simulasi:

• Hasil Simulasi Jalan 1Proses simulasi dapat dilihat pada gambar 4, gambar 4a,dan gambar 4b Pada hasil akhir simulasi didapatkan hasilakhir berupa gambar 5

• Hasil Simulasi Jalan 2– loop 1-Akhir

Gambar 6 dan gambar adalah gambar darihasil simulasi untuk jalan tiga blok. Simulasimembutuhkan waktu 1 menit 57 detik untukmencapai titik tujuan dan membutuhkan loopsebanyak 3000 kali.

• Tabel Jumlah Partikel Berhasil dan Gagal MencapaiTargetTabel II adalah hasil pengujian untuk jalan sederhana satublok dan tiga blok partikel yang berhasil mencapai titiktujuan dan tidak.

• Tabel Perhitungan Iterasi dan Waktu Simulasi

(a) Loop ke-245

(b) Loop ke-689

Gambar 4: Simulasi Dijalankan untuk Jalan 1

Gambar 5: Hasil Akhir Partikel pada Jalan 1

Tabel III adalah hasil yang didapatkan dari hasil simulasiyang memuat informasi tentang waktu yang dibutuhkanuntuk menempuh perjalanan.

C. Analisa Data

Dari hasil pengujian didapatkan hasil yang tidak berbedajauh pada spesifikasi komputer yang berbeda. Hal ini disebabkan karena pada pensimulasian kecepatan partikel di

(a) loop ke-750

(b) Loop ke-4321 (akhir)

Gambar 6: Simulasi Dijalankan untuk Jalan 2 (loop 1-Akhir)

Tabel II: Tabel Partikel Berhasil dan Gagal Mencapai TargetNo Media Pengujian Jenis Jalan Partikel Berhasil Gagal

1 Komputer Desktop 1 1 4 4 02 2 25 21 43 Komputer Desktop 2 1 4 4 04 2 25 20 55 Komputer Desktop 3 1 4 4 06 2 25 21 47 Komputer Laptop 1 4 4 08 2 25 18 7

Tabel III: Tabel Pengujian Waktu Tempuh

No Media Pengujian Jenis Jalan Iterasi Waktu

1 Komputer Desktop 1 1 1012 0m:29s2 2 3057 1m:57s3 Komputer Desktop 2 1 1032 0m:29s4 2 3102 2m:07s5 Komputer Desktop 3 1 1058 0m:27s6 2 2717 1m:57s7 Komputer Laptop 1 1014 0m:28s8 2 3102 1m:54s

(a) Pengujian 1

No Media Pengujian Jenis Jalan Iterasi Waktu

1 Komputer Desktop 1 1 1035 0m:28s2 2 3021 1m:59s3 Komputer Desktop 2 1 1021 0m:30s4 2 3025 2m:04s5 Komputer Desktop 3 1 1014 0m:28s6 2 2758 1m:57s7 Komputer Laptop 1 1000 0m:30s8 2 3200 1m:56s

(b) Pengujian 2

tentukan dengan kecepatan yang seragam. Optimisasi padasimulasi multi agent tidak terpengaruh oleh banyaknya iterasiyang dilakukan karena simulasi pada multi agent ini bersifatreal time. Hasil ini Berbeda dengan hasil yang di dapat padaMatlab. Pada Matlab data dapat diukur dengan jumlah iterasiketika partikel mencapai hasil yang konvergen.

Hasil pengujian jumlah partikel sebanding dengankomplekstivitas dari jalur lalu lintas. Semakin besar Blokjalan semakin banyak pula jumlah partikel yang dibutuhkanuntuk mendapatkan hasil optimisasi. Untuk permasalahanyang berukuran satu blok, jumlah partikel 4 buah sudah cukupuntuk menemukan titik goal. Sedangkan untuk permasalahan3 blok dibutuhkan lebih banyak partikel agar partikel dapatmenemukan titik goal, pada percobaan dibutuhkan partikelsejumlah 25.

Pada hasil pengujian didapatkan beberapa partikel yangtidak dapat menemukan jalan menuju goal. Hal ini disebabkankarena pada beberapa kasus ada partikel yang ketinggalanuntuk mengikuti partikel sebelahnya. Untuk partikel yangtertinggal, gerak yang di lakukan adalah gerak secara acak.

VI. PENUTUP

A. Kesimpulan

Particle Swarm Optimization untuk mengoptimasi lalu lintastelah berhasil dilakukan. dan dari pengujian sistem dapatditarik kesimpulan bahwa:

1) Penggunaan Particle Swarm Optimization sebagai obyekmulti agent pada proses pencarian jalur menuju titik goaldapat dilakukan pada Blender dengan waktu tempuhsesuai dengan kecepatan yang ditentukan

2) Dari hasil pengujian didapatkan rata rata waktu yangdigunakan untuk menempuh jalan 1 adalah 28.625 detikdan untuk menempuh jalan 2 adalah 1 menit 58 detik

3) Jumlah penggunaan partikel sebanding dengan besar dankerumitan jalan raya.

4) Pada Percobaan partikel yang dibutuhkan untukmenyelesaikan permasalahan jalan satu blok adalah 4buah dan untuk menyelesaikan permasalahan jalan 3blok dibutuhkan 25 buah

B. Saran

Untuk pengembangan lebih lanjut, dapat dilakukan inovasisebagai berikut:

1) Particle Swarm Optimization dapat dilakukan untukberbagai jenis permasalahan sehingga inovasi untukaplikasi PSO di bidang lain sangat dibutuhkan.contohnya dalam bidang robotika

2) Particle Swarm Optimization dapat menyelesaikanmasalah secara realtime sehingga cocok untukdigunakan pengembangan game pintar yangmembutuhkan pengambilan keputusan secara tepatdan cepat sesuai dengan kondisi yang berlaku padakondisi tertentu.

3) Pemodifikasian program untuk membaca dan mengolahinformasi perlu dilakukan.

REFERENCES

[1] Craig W. Reynolds, Flocks, Herds, and Schools: A Distributed BehavioralModel. Proceeding of SIGGRAPH .87, ACM, 1987.

[2] Eberhart,R.C., and Kennedy, J. A new optimizer using particle swarmtheory. Proceedings of the sixth International Symposium on MicroMachine and Human Science, Nagoya, Japan, 39-43. Piscataway,NJ:IEEE Service Center

[3] Guido van Rossum and Fred L.Drake,Jr. Python Tutorial Release 2.6.5.Python Software Foundation,2010.

[4] Ton Roosendaal and Carsten Wartmann. Blender gamekit. StichtingBlender Foundation, 2002.

[5] http://www.engr.iupui.edu/~shi/Coference/psopap4.html, Maret 2010[6] http://www.swarmintellegenc.org, Januari 2010[7] http://wiki.blender.org, Desember 2009