Pencarian Jalur Terbaik Menggunakan Particle Swarm Optimization untuk mengoptimasi Lalu Lintas Kendaraan Safril Rizki Waluyo¹, Mochamad Hariadi², I Ketut Eddy Purnama³
Abstrak—Particle Swarm Optimization merupakan salah satu Algoritma optimasi yang bisa di aplikasikan pada permasalahan path finding. Basic PSO dapat digunakan pada proses optimisasi ruang bebas untuk menemukan suatu target koordinat x dan y. Basic PSO sangat baik untuk digunakan pada permasalahan ruang bebas. Namun Basic PSO tidak cocok untuk digunakan di permasalahan ruang terbatas seperti pada pencarian jalan. Modifikasi perlu dilakukan untuk diaplikasikan ke obyek pelaku pada simulasi. Penerapan Modified PSO pada obyek memiliki keuntungan obyek pelaku dapat bertindak sebagai muti agent yang secara otomatis mencari jalur menuju goal. Kata Kunci—Particle Swarm Optimization, Multi agent, Path Finding algorithm.
I. P ENDAHULUAN IMULASI Pencarian jalan terbaik adalah suatu proses yang dilakukan dalam bidang komputasi agar dapat mencapai suatu tujuan secara tepat dan cepat. Pencarian jalan terbaik dimulai dari satu node menuju ke node yang lainnya dengan menggunakan parameter parameter yang ada. Dari nilai yang parameter yang didapat, keputusan pengambilan rute dapat dilakukan dengan cara membandingkan nilai yang di dapat untuk setiap jalur dan dipilih nilai yang paling optimum. Algoritma path finding yang handal dibutuhkan agar proses pencarian jalur dapat diselesaikan secara tepat dan cepat. Aplikasi navigasi terkini banyak yang masih menggunakan metode path finding dengan tipe penelusuran node per node. sehingga dibutuhkan waktu yang lumayan lama untuk mengalkulasi rute yang akan ditempuh. Dengan metode pencarian jalur tipe eksplorasi graph secara keseluruhan diharapkan dapat mengurangi waktu kalkulasi rute menjadi lebih singkat atau juga bisa digunakan secara realtime.
S
dari sistem dipelajari dengan kecerdasan berkelompok adalah koloni semut dan rayap, segerombolan ikan (schools of fish), sekawanan burung (flocks of bird), kumpulan dari hewan darat. Beberapa artefak manusia juga jatuh ke dalam domain kecerdasan berkelompok, terutama beberapa sistem multirobot, dan program komputer juga tertentu yang ditulis untuk mengatasi masalah optimasi dan analisis data. Particle Swarm Optimization(PSO) adalah suatu populasi yang berdasarkan teknik optimasi stokastik yang dikembangkan oleh Dr Eberhart dan Dr Kennedy pada tahun 1995, terinspirasi oleh perilaku sosial dari burung berkelompok (flock of bird) atau sekumpulan ikan (school of fish)[2]. Setiap partikel yang melacak koordinat dalam ruang masalah yang berhubungan dengan solusi terbaik (kebugaran) yang telah dicapai sejauh ini. (Nilai kebugaran juga akan disimpan) Nilai ini disebut pbest. "terbaik" lainnya, nilai yang dilacak oleh Particle Swarm Optimizer adalah nilai terbaik, sejauh yang diperoleh oleh setiap partikel di tetangga partikel. Lokasi ini disebut lbest. saat sebuah partikel mengambil semua populasi sebagai tetangga topologi nya, nilai terbaik adalah sebuah global terbaik dan disebut gbest. Pada kondisi awal setiap Partikel terbang bebas dalam posisi yang acak. Konsep optimasi partikel terdiri dari kerumunan, pada setiap langkah waktu, mengubah kecepatan (mempercepat) setiap partikel terhadap perubahan pbest dan lokasi lbest (versi lokal dari PSO). Percepatan dibobot dengan istilah acak, dengan nomor acak terpisah yang dihasilkan untuk percepatan ke arah pbest dan lokasi lbest. Pada Basic PSO parameter yang pasti digunakan adalah posisi partikel, inertia weight, konstanta, kecepatan partikel, posisi terbaik partikel dan posisi global terbaik. dari beberapa parameter yang di gunakan diatas dapat membentuk
II. DASAR T EORI Swarm intelijen adalah disiplin ilmu yang berkaitan dengan alam dan sistem buatan yang terdiri dari banyak individu yang mengkoordinasi menggunakan kontrol desentralisasi dan self-organization. Secara khusus, disiplin ini berfokus pada perilaku kolektif bahwa hasil dari interaksi lokal dari individu satu 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, Bidang Studi Teknik Komputer & Telematika, Jurusan Teknik Elektro ITS Surabaya. (3) Dr.I Ketut Eddy Purnama ST., MT., Dosen Pembimbing II, Bidang Studi Teknik Komputer & Telematika, Jurusan Teknik Elektro ITS Surabaya.
Gambar 1: Update Posisi pada Particle Swarm Optimization (http:// www.uni-leipzig.de/ ~vignesh/ research.html) update posisi dilakukan secara serempak di tiap tiap partikel. update partikel dilakukan dengan menggunakan persamaan dasar PSO
V(t + 1) =wV(t)+C1(P (t)−X(t))+C2(G(t)−X(t)) (1) Pemutakhiran Posisi Partikel dapat dilakukan dengan menggunakan persamaan X(t + 1) = X(t) + V(t + 1)
(2)
Pada Pengimplementasian Program PSO secara dasar. ada beberapa langkah dasar yang selalu dilakukan yaitu: 1) Inisialisasi posisi partikel secara acak 2) Inisialisasi kecepatan partikel secara acak 3) Pencarian global best partikel position 4) Pemutakhiran kecepatan setiap partikel 5) pemutakhiran posisi setiap partikel 6) pencarian global best partikel position kembali
Tahapan pertama yang di lakukan adalah pensimulasian dalam Matlab. setelah pensimulasian dalam Matlab berhasil maka sifat difat partikel dapat dianalisa dan di terapkan pada permasalahan lalu lintas. setelah tahap kedua diselesaikan maka metode siap diimplementasikan dalam game pada Blender. Pada Pengimplementasian Program PSO secara dasar. ada beberapa langkah dasar yang selalu dilakukan yaitu: 1) Inisialisasi posisi partikel secara acak 2) Inisialisasi kecepatan partikel secara acak 3) Pencarian global best partikel position 4) Pemutakhiran kecepatan setiap partikel 5) pemutakhiran posisi setiap partikel 6) pencarian global best particle position kembali update posisi dilakukan secara serempak di tiap tiap partikel. update partikel dilakukan dengan menggunakan persamaan dasar PSO
III. D ESAIN S ISTEM Desain dari Penelitian ini dibagi menjadi beberapa tahapan pengerjaan yaitu pembuatan environment, penulisan script pada Matlab dan Python, dan pengimplementasian ke dalam lingkungan Blender. komponen komponen penting yang menyusun penelitian implementasi Particle Swarm Optimization untuk mengoptimasi lalu lintas kendaraan ini adalah, lingkungan environment, obyek pelaku berupa kendaraan, sensor, actuator, dan controller yang berupa script Python. sebelum di implementasikan dalam lingkungan 3D. Script terlebih dahulu di uji coba yaitu dengan cara disimulasikan pada program simulasi matematika matlab. A. Desain obyek Simulasi obyek yang bentuknya terlalu rumit ,memiliki banyak vertex, bisa dapat memperberat sistem. Partikel disini adalah suatu obyek yang multi agent. Partikel ini dapat di tambahkan ke dalam environment tanpa mengurangi sifat sifat yang dimilikinya. semakin banyak partikel yang ditambahkan, semakin berat pula proses yang dikerjakan. Untuk mengatasi masalah sistem yang bekerja terlalu berat, maka digunakanlah obyek yang sederhana obyek tersebut adalah cube. Desain jalur lalu lintas di desain secara sederhana dalam sumbu axis x dan y sebagai tempat jalur mobil. Bagian samping jalur lalu lintas di beri badan pembatas agar obyek kendaraan tetap berada di jalur. Sehingga mobil tidak bergerak liar pada saat diimplementasikan algoritma PSO. Berikut adalah beberapa contoh bentuk jalur lalu lintasnya. pada sistem dirancang agar algoritma PSO dapat berjalan pada setiap desain jalur lalu lintas yang ada. berikut adalah desain jalur lalu 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 dalam permasalahan lalu lintas, dan pengimplementasian PSO dalam Blender dengan menggunakan bahasa python dan Blender Game Engine.
V(t + 1) =wV(t)+C1(P (t)−X(t))+C2(G(t)−X(t)) (3) Pemutakhiran Posisi Partikel dapat dilakukan dengan menggunakan persamaan X(t + 1) = X(t) + V(t + 1)
(4)
1) Desain Sistem PSO pada Matlab: Tujuan dari implementasi PSO dalam matlab ini adalah untuk mensimulasikan apakah PSO telah dapat bekerja secara baik atau tidak untuk permasalahan pencarian titik target berupa koordinat. Data pada koordinat partikel di gambarkan pada Plot sehingga pergerakan sekawanan partikel dapat terlihat langkah demi langkah. langkah selanjutnya adalah menguji permasalahan yang sama, yaitu pencarian titik koordinat tujuan. Pengaplikasian PSO di Matlab memiliki target untuk mencari titik tujuan yang telah di tentukan. pada pengaplikasian PSO pada matlab ini dapat juga diketahui sifat sifat dari PSO sehingga pada saat pendesainan pada python untuk Blender bisa diketahui sifat partikel. setelah diketahui sifat-sifat partikel, sifat tersebut di terjemahkan dalam bahasa dan perilaku obyek di Blender. 2) Desain Sistem PSO pada Blender Game Engine: Sama halnya dengan implementasi dalam Matlab namun implementasi PSO dalam Blender Game Engine digunakan untuk simulasi yang real time. Bahasa python merupakan bahasa yang digunakan dalam blender untuk membuat sebuah sistem yang lebih kompleks. Blender memiliki sebuah game engine yang digunakan untuk mengatur sistem didalamnya. Namun game engine dari Blender ini memiliki kekurangan yaitu walaupun penggunaannya sangat mudah namun dia memiliki keterbatasan dalam penggunaan. karena hal tersebut scripting python PSO sangat membantu dalam penerapan Particle Swarm Optimization. Penulisan script PSO pada python berbeda dengan penulisan pada matlab. Pada Matlab data yang diolah adalah suatu larik, sedangkan pada Blender Game Engine yang di olah adalah sensor dan aktuator suatu obyek yang di gunakan untuk berinteraksi dengan obyek yang lain.
Game Engine pada Blender bersifat berorientasi obyek. Game Engine pada Blender ini dapat membuat setiap obyek menjalankan perilaku obyek masing masing yang berbeda. Pemrograman pada Python harus memperhatikan 3 kondisi sensor obyek, aktuator obyek, dan obyek di scene pada Blender. C. Desain Perilaku Partikel Individu partikel pada Particle swarm memiliki sifat sifat yang dimiliki individu pada sekawanan burung atau juga individu pada sekelompok ikan. setiap individu bisa bekerja secara individu namun tidak melupakan tugasnya sebagai kelompok. Partikel pintar multi agent ini di desain untuk memiliki sifat sifat dan kemampuan individu pada burung ataupun ikan ini. sifat ini akan terus di turunkan apabila ada obyek baru yang satu tipe dengan partikel, yaitu berjenis partikel juga, sehingga individu baru dapat berperilaku layaknya partikel yang lain. Ada beberapa sifat dasar yang harus dimiliki setiap partikel 1) Partikel dapat melihat posisi sekitarnya 2) Partikel dapat merasakan partikel lain yang berada di sekitarnya 3) Partikel dapat mengetahui apa yang sedang dicari 4) Partikel dapat mengetahui Posisinya pada suatu environment 5) partikel dapat mengenali mana obyek lain yang bertindak sebagai partikel 6) partikel dapat mengetahui jaraknya dengan partikel lain 7) partikel dapat mengumpulkan informasi dari environment maupun dari partikel lain 8) partikel dapat menghindari tabrakan dengan lingkungan. 9) partikel memiliki kecepatan untuk mencapai suatu posisi 10) partikel dapat terbang bebas apa bila tidak tahu apa yang dicari IV. I MPLEMENTASI S ISTEM Langkah-langkah implementasi adalah sebagai berikut: A. Penerjemahan Behaviour ke Dalam Particle 1) Partikel dapat melihat keadaan sekitar Sebagai pengganti mata pada obyek, sensor yang di gunakan adalah sensor RAY 2) Partikel dapat merasakan partikel disekitarnya Partikel menggunakan near sensor yang di setting memiliki kedalaman tertentu untuk merasakan partikel di sekitarnya 3) Partikel dapat mengenali target Partikel mengetahui apa yang di cari. Tujuan utama dari partikel tersebut adalah mencapai titik tercepat menuju goal. 4) Partikel dapat mengetahui letak koordinat diri Partikel dapat mengetahui letak koordinat dirinya pada sistem dengan menggunakan fungsi Python list [x,y,z] getPosition() 5) Partikel dapat mengenali mana obyek lain yang bertindak sebagai partikel
6)
7)
8)
9)
10)
Partikel dapat mengetahui mana benda lain yang memiliki karakteristik yang sama dengan dirinya. Sensor near, touch, ray dan radar menggunakan properties dan material untuk mengetahui target yang tepat. Partikel dapat mengetahui jaraknya dengan partikel lain Partikel dapat menghitung dan memperkirakan jarak dengan partikel lainnya dengan cara menghitung dengan fungsi pada library Game Logic getDistanceTo(); Partikel dapat mengumpulkan informasi dari environment maupun dari partikel lain Pada game Logic dibuat suatu hubungan yang berfungsi sebagai pencarian data dari environment dengan menggunakan kombinasi touch sensor dan properties sensor. Partikel dapat menghindari tabrakan dengan linkungan. Metode menghindari tabrakan dapat dilakukan dengan kombinasi radar sensor dan move actuator. Partikel memiliki kecepatan untuk mencapai suatu posisi Setiap partikel memiliki kecepatan untuk meng-update posisi dirinya Partikel dapat terbang bebas apa bila tidak tahu apa yang dicari Pada fungsi ini apabila partikel tidak menemukan apapun pada sekitarnya partikel akan terbang bebas pada ruangan tersebut.
B. Penggunaan Game Engine Blender Pengaturan interaksi dari satu obyek ke obyek lain diperlukan suatu controller untuk setiap obyek yang ada. Controller Obyek dibuat pada Game Engine yang telah disediakan program Blender. Ada dua metode pengaturan obyek pada Game Engine yaitu pengaturan dengan logic brick dan pengaturan dengan menggunakan Python script controller. Obyek yang ada diatur dan diberi kemampuan bertindak dengan menggunakan logic brick dan script Pythondari game engine Blender sehingga proses dapat dilakukan. Obyek utama akan mengikuti partikel pada ruang bebas yang paling dekat dengan obyek tersebut. Proses akan berlanjut sampai obyek dapat menemukan titik tujuannya. Untuk membentuk kondisi sebagai pensimulasian kondisi nyata diperlukan suatu parameter khusus yang dapat merepresentasikan hambatan hambatan yang ada di lalu lintas. Keamanan, kemacetan, dan kualitas jalan adalah problem yang harus diperhatikan dalam simulasi. Informasi mengenai kondisi lalu lintas diberikan pada Obyek jalan. Map pada environment dapat di bagi menjadi beberapa sektor. Di setiap sektor diberikan suatu property untuk membawa informasi informasi kualitas jalan. Setiap sektor dari jalan dapat dideteksi partikel yang masuk dan memberikan informasi tentang kondisi jalan dan juga tingkat kepadatan. actuator, controller, dan sensor didesain untuk berinteraksi antara satu dengan yang lainya. semakin komplek AI semakin banyak pula logic brick yang dibutuhkan V. P ENGUJIAN S ISTEM Ada dua tahap pengujian sistem, pertama adalah tahap simulasi pada Matlab dan kedua adalah tahap simulasi pada Lingkungan Virtual 3D Blender.
Pengujian dilakukan dengan cara simulasi dengan komputer yang memiliki spesifikasi sebagai berikut: 1) Komputer Desktop a) 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 lintas kendaraan berhasil dibuat pada dua bahasa yang berbeda disimulasikan dan diimplementasikan menggunakan Matlab, Blender Game Engine, dan Python scripting. Hasil pengujian dapat dilihat pada subbab berikutnya A. Pengujian pada Matlab Simulasi pertama dilakukan pada Matlab. Program dapat berjalan dengan lancar. Setelah program dapat dijalankan dengan lancar hasil tersebut di bandingkan dengan algoritma yang lain. Pada pengujian di Matlab ini. Ada beberapa parameter yang harus diketahui. Target berupa titik tujuan bernilai tertentu yang menunjukkan koordinat. Jumlah Partikel di uji coba dan diberi nilai tertentu. Koordinat awal partikel, kecepatan awal partikel bernilai random. konstanta C1 dan C2 diberi nilai yang random antara 0-1. Inertia weight diset secara manual antara 0.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 Pengujian Pada hasil gambar hasil pengujian perulangan ke1(gambar 2a) , partikel mencari targetnya dengan mencari informasi posisi terbaik partikel yang pernah dilalui. Semakin banyak iterasi yang dilakukan hasil
(a) Pengujian
(b) Hasil Konvergen pada perulangan 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 (gambar 2b) B. Pengujian pada Blender 1) Pengujian Sifat PSO pada Partikel: Pengujian ini dilakukan pada sifat sifat PSO pada partikel. Tabel I: Tabel Pengujian Sifat No
Sifat
Status
1 2 3 4 5 6 7 8 9 10
Dapat melihat keadaan sekitar Merasakan partikel disekitarnya Mengenali target Mengetahui letak koordinat diri Mengenali obyek lain Dapat mengukur jarak dengan obyek lain Dapat mengumpulkan informasi properti obyek Menghindari Tabrakan dengan lingkungan Memiliki Kecepatan Dapat terbang bebas
v v v v v v v x v v
Pada tabel I, dari pengujian sifat ada satu sifat yang belum bisa di implementasikan kedalam partikel, yaitu sifat dapat menghindari tabrakan dengan lingkungan sekitar. Sifat ini tidak dimasukkan ke dalam sifat partikel karena terbatasnya lebar ruang jalan. ketika diimplementasikan ke dalam sifat partikel partikel bergerak berputar putar disebabkan karena jarak dinding pembatas jalan dengan partikel terlalu dekat. 2) Pengujian Pencarian Jalan : Simulasi kedua dilaksanakan dengan menggunakan Blender game engine dan juga Script Python. Program dapat berjalan. Pengujian dilakukan dengan beberapa komputer dengan spesifikasi yang berbeda. Obyek dapat menemukan target dengan bantuan partikel yang lain. Obyek ini berupa multi agent sehingga sifat dari satu partikel dapat di turunkan ke partikel lain. Setiap partikel memiliki perilaku yang sama dengan partikel lain. Perilaku dari partikel ini bersifat
umum dan dapat di gunakan dalam setiap bentuk peta dan environment. Pembacaan informasi property pada jalan dapat dilakukan oleh partikel sehingga setiap partikel dapat mengetahui kualitas lalu lintas yang dilewati, akan tetapi informasi yang didapat oleh partikel ini belum bisa di olah lebih lanjut karena keterbatasan penulisan perintah pada script Python yang di miliki oleh Blender. Blender memiliki kekurangan pada bagian transfer informasi. Transfer informasi bisa dilakukan antara satu obyek dengan obyek yang lain. Namun untuk permasalahan multi agent. Informasi tidak bisa di-transfer begitu saja, karena setiap agent memiliki penamaan yang berbeda. Sedangkan logic brick pada Blender Game engine tidak memiliki script penggantian nama obyek untuk mengambil property. Pengambilan informasi properties harus di modifikasi agar pengambilan nama script dapat berlaku secara global. 3) Lingkungan Jalan pada Pengujian: Setelah parameter pada area di set, script PSO untuk partikel kemudian dapat dijalankan.
(a) Loop ke-245
(b) Loop ke-689
Gambar 4: Simulasi Dijalankan untuk Jalan 1
1) contoh Blok jalan
Gambar 5: Hasil Akhir Partikel pada Jalan 1
(a) 1 Blok dengan 2 Properti
(b) 3 Blok dengan 3 Property
Gambar 3: Jalan Lalu Lintas Satu Blok
Tabel III adalah hasil yang didapatkan dari hasil simulasi yang memuat informasi tentang waktu yang dibutuhkan untuk menempuh perjalanan. C. Analisa Data
Gambar 3 adalah gambar dari blok Jalan untuk simulasi. Blok tersebut terdiri dari bagian yang masing masing bagian memiliki nilai informasi tersendiri. Gambar 3a dan gambar 3b menunjukkan pembagian bagian dengan nilai yang berbeda
Dari hasil pengujian didapatkan hasil yang tidak berbeda jauh pada spesifikasi komputer yang berbeda. Hal ini di sebabkan karena pada pensimulasian kecepatan partikel di
4) Hasil Simulasi: •
•
•
•
Hasil Simulasi Jalan 1 Proses simulasi dapat dilihat pada gambar 4, gambar 4a, dan gambar 4b Pada hasil akhir simulasi didapatkan hasil akhir berupa gambar 5 Hasil Simulasi Jalan 2 – loop 1-Akhir Gambar 6 dan gambar adalah gambar dari hasil simulasi untuk jalan tiga blok. Simulasi membutuhkan waktu 1 menit 57 detik untuk mencapai titik tujuan dan membutuhkan loop sebanyak 3000 kali. Tabel Jumlah Partikel Berhasil dan Gagal Mencapai Target Tabel II adalah hasil pengujian untuk jalan sederhana satu blok dan tiga blok partikel yang berhasil mencapai titik tujuan dan tidak. Tabel Perhitungan Iterasi dan Waktu Simulasi
(a) loop ke-750
(b) Loop ke-4321 (akhir)
Gambar 6: Simulasi Dijalankan untuk Jalan 2 (loop 1Akhir)
Tabel II: Tabel Partikel Berhasil dan Gagal Mencapai Target No
Media Pengujian
Jenis Jalan
Partikel
Berhasil
Gagal
1 2 3 4 5 6 7 8
Komputer Desktop 1
1 2 1 2 1 2 1 2
4 25 4 25 4 25 4 25
4 21 4 20 4 21 4 18
0 4 0 5 0 4 0 7
Komputer Desktop 2 Komputer Desktop 3 Komputer Laptop
Tabel III: Tabel Pengujian Waktu Tempuh No
Media Pengujian
Jenis Jalan
Iterasi
Waktu
1 2 3 4 5 6 7 8
Komputer Desktop 1
1 2 1 2 1 2 1 2
1012 3057 1032 3102 1058 2717 1014 3102
0m:29s 1m:57s 0m:29s 2m:07s 0m:27s 1m:57s 0m:28s 1m:54s
Komputer Desktop 2 Komputer Desktop 3 Komputer Laptop
(a) Pengujian 1 No
Media Pengujian
Jenis Jalan
Iterasi
Waktu
1 2 3 4 5 6 7 8
Komputer Desktop 1
1 2 1 2 1 2 1 2
1035 3021 1021 3025 1014 2758 1000 3200
0m:28s 1m:59s 0m:30s 2m:04s 0m:28s 1m:57s 0m:30s 1m:56s
Komputer Desktop 2 Komputer Desktop 3 Komputer Laptop
(b) Pengujian 2
tentukan dengan kecepatan yang seragam. Optimisasi pada simulasi multi agent tidak terpengaruh oleh banyaknya iterasi yang dilakukan karena simulasi pada multi agent ini bersifat real time. Hasil ini Berbeda dengan hasil yang di dapat pada Matlab. Pada Matlab data dapat diukur dengan jumlah iterasi ketika partikel mencapai hasil yang konvergen. Hasil pengujian jumlah partikel sebanding dengan komplekstivitas dari jalur lalu lintas. Semakin besar Blok jalan semakin banyak pula jumlah partikel yang dibutuhkan untuk mendapatkan hasil optimisasi. Untuk permasalahan yang berukuran satu blok, jumlah partikel 4 buah sudah cukup untuk menemukan titik goal. Sedangkan untuk permasalahan 3 blok dibutuhkan lebih banyak partikel agar partikel dapat menemukan titik goal, pada percobaan dibutuhkan partikel sejumlah 25. Pada hasil pengujian didapatkan beberapa partikel yang tidak dapat menemukan jalan menuju goal. Hal ini disebabkan karena pada beberapa kasus ada partikel yang ketinggalan untuk mengikuti partikel sebelahnya. Untuk partikel yang tertinggal, gerak yang di lakukan adalah gerak secara acak. VI. P ENUTUP A. Kesimpulan Particle Swarm Optimization untuk mengoptimasi lalu lintas telah berhasil dilakukan. dan dari pengujian sistem dapat ditarik kesimpulan bahwa:
1) Penggunaan Particle Swarm Optimization sebagai obyek multi agent pada proses pencarian jalur menuju titik goal dapat dilakukan pada Blender dengan waktu tempuh sesuai dengan kecepatan yang ditentukan 2) Dari hasil pengujian didapatkan rata rata waktu yang digunakan untuk menempuh jalan 1 adalah 28.625 detik dan untuk menempuh jalan 2 adalah 1 menit 58 detik 3) Jumlah penggunaan partikel sebanding dengan besar dan kerumitan jalan raya. 4) Pada Percobaan partikel yang dibutuhkan untuk menyelesaikan permasalahan jalan satu blok adalah 4 buah dan untuk menyelesaikan permasalahan jalan 3 blok dibutuhkan 25 buah B. Saran Untuk pengembangan lebih lanjut, dapat dilakukan inovasi sebagai berikut: 1) Particle Swarm Optimization dapat dilakukan untuk berbagai jenis permasalahan sehingga inovasi untuk aplikasi PSO di bidang lain sangat dibutuhkan. contohnya dalam bidang robotika 2) Particle Swarm Optimization dapat menyelesaikan masalah secara realtime sehingga cocok untuk digunakan pengembangan game pintar yang membutuhkan pengambilan keputusan secara tepat dan cepat sesuai dengan kondisi yang berlaku pada kondisi tertentu. 3) Pemodifikasian program untuk membaca dan mengolah informasi perlu dilakukan. R EFERENCES [1] Craig W. Reynolds, Flocks, Herds, and Schools: A Distributed Behavioral Model. Proceeding of SIGGRAPH .87, ACM, 1987. [2] Eberhart,R.C., and Kennedy, J. A new optimizer using particle swarm theory. Proceedings of the sixth International Symposium on Micro Machine 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. Stichting Blender 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
