Prosiding SNYuBe 2013
SIMULASI ROBOT PEMADAM API DENGAN METODE ALGORITMA GENETIK M. Basyir Program Studi Teknik Elektronika Jurusan Teknik Elektro, Politeknik Negeri Lhokseumawe Jln. Banda Aceh – Medan Km. 280.5 Buketrata Lhokseumawe Email:
[email protected] Abstrak Perkembangan ilmu robot semakin berkembang mulai dari robot manual, robot otomatis sampai robot cerdas. Salah satu metode yang digunakan pada robot cerdas ialah Algoritma Genetik (AG). AG ialah teknik untuk menentukan penyelesaian optimasi. Makalah ini menjelaskan pencarian jalur terpendek untuk mencari keberadaan api yang ada dalam satu dari empat ruangan. Penerapan AG berhasil mencari jalur terpendek dari kemungkinan jalur-jalur yang ada sehingga robot dengan cepat memadamkan api. Kata kunci: Robot, AG, jalur terpendek, api
Pendahuluan Perkembangan dunia robotika memiliki unsur yang sedikit berbeda dengan ilmu-ilmu dasar atau terapan lainnya. Ilmu dasar biasanya berkembang dari suatu asas atau hipotesa yang kemudian diteliti secara metodis, sedengkan ilmu robotika lebih sering dikembangkan melalui pendekatan praktis. Kemudian melalui pendekatan atau asumsi dari hasil pengamatan perilaku makhluk hidup atau peralatan yang bergerak lainnya dikembangkanlah penelitian secara teoritis [1]. Makin pesatnya perkembangan teknologi menyebabkan adanya perkembangan dan perluasan lingkup yang membutuhkan kehadiran kecerdasan buatan. Karakteristik “cerdas” sudah mulai dibutuhkan diberbagai disiplin ilmu dan teknologi. Kecerdasan buatan tidak hanya dominan di bidang ilmu komputer dan informatika saja tapi bias membuat irisan dengan ilmu lain. Misal irisan Kecerdasan Buatan dengan Teknik Elektro melahirkan berbagai ilmu seperti: pengolahan citra, teori kendali, pengenalan pola dan robotika. Banyak Usaha yang diarahkan untuk mendesain robot intelegen dalam industri. Perkembangan robotik ini mendorong studi atau penelitian di bidang pengolahan visual, teknik pemecaha soal atau pengontrolan bagian-bagian robot. Bidang pengolahan visual penting untuk menambah kemampuan robot. Teknik pemecahan soal berhubungan dengan pembuktian teori. Ini semua berkaitan dengan rancangan suatu bahasa pemrograman yang lebih tinggi levelnya dan lebih fleksibel. Bahasa pemograman dapat membatu mencari solusi sebelum diimplementasi ke alat/robot dengan cara mensimulasi variabel-variabel yang berkaiatan dan didukung dengan metode yang ada, misalnya metode kecerdasan buatan. Kecerdasan Buatan Artificial Intelligence (AI) dalam robotik adalah suatu algorithma yang dipandang cerdas yang diprogramkan. Pengertian cerdas di sini sangat relatif, 184
Prosiding SNYuBe 2013
karena tergantung dari sisi mana sesorang memandang. Metoda AI lain yang juga berkembang adalah Algorithma Genetik (AG). AG adalah teknik pencarian global dan optimasi dari sistem natural, genetik dan evolusi. Simulasi AG menggunakan koding dan operator khusus. AG mempertahankan populasi dari kandidat solusi, dimana setiap kandidat solusi dikodekan dalam biner disebut sebagai kromosom. Satu set kromosom sebuah populasi, dievaluasi dan dirangking oleh fungsi evaluasi fitness, dimana fungsi evaluasi fitness memainkan peranan penting dalam AG karena fungsi ini merupakan informasi sebaik apa masingmasing kandidat. Populasi awal biasanya dibangkitkan secara acak. Evaluasi dari satu generasi ke generasi berikutnya melalui 3 langkah utama: evaluasi fitness, seleksi dan reproduksi [2]. Makalah ini menjelaskan mengimplementasikan sebuah program dengan menggunakan metode GA untuk mencari jalur terpedek untuk mendapatkan api yang diletakkan disembarang/acak dalam ruangan, ruangan berjumlah 4 ruangan, dengan harapan robot dapat dengan cepat mencari dan memadamkan api, api sudah dipadamkan kemudian robot kembali ke posisi awal dan menunggu perintah selanjutnya. Metode Penelitian Arena/tral Simulasi dari Robot Bergerak memadamkan api yang diletakkan secara acak pada 4 buah kamar seperti ditunjukkan pada gambar 1 arena/trak robot pemadan api divisi beroda. Lintasan (Path Planning) robot bergerak menggunakan prinsip algoritma genetika (AG) dengan menggunakan bahasa pemogrman Delphi. Pembentukan Populasi Awal. Pembentukan Populasi awal dimulai dengan membuat tabel jarak antara titik. Jika antara titik ada tembok (garis hitam) maka nilai jarak diberi 1000 cm. Metode pendeksian tembok (garis) dilakukan dengan membaca warna setiap dari pixel. Jika bernilai 0 berarti hitam jarak diberi nilai 1000. Penarikan garis antara titik dilakukan secara bertahap dengan perhitungan berikut: dY= Y1-Y0, dX= X1-X0, Sudut = (180/3,14)* Arctan (dY/dX), Jika X0=X1 maka
Sudut=90. √
(1)
untuk mencapai koordinat titik berikutnya dilakukan dengan langkah: langkah dari 1 sampai dr, X= langkah * Cos (pi/180)* Sudut, Y= langkah * Sin(pi/180) *Sudut. Jika (X1>X0 dan Y1<=Y0) atau Jika (X1>=X0 dan Y1>Y0), maka: KoordinatX =X0+ X ; KoordinatY =Y0+Y. Tetapi Jika (X1<X0 dan Y1>=Y0) atau Jika (X1<X0 dan Y1
185
Prosiding SNYuBe 2013
74Cm 46Cm
26Cm
57Cm 46Cm 105Cm 46Cm 28Cm 59Cm
55Cm
46Cm 74Cm 46Cm
122Cm
46Cm 91Cm
46Cm 248Cm
137Cm
46Cm 91Cm 120Cm
46Cm 45Cm
248Cm
Gambar 1. Arena/Trak Robot Pemadan Api Divisi Beroda [3] Tabel 1. Koordinat untuk 5 titik No
Koord. X
Koord. Y
1
8
7
2
26
9
3
17
19
4
7
30
5
25
32
Agar jalur tidak bergerak ke titik berikutnya maka jarak titik yang sama diberi maksimum (1000), ditunjukkan pada tabel 2 jarak antara titik.
186
Prosiding SNYuBe 2013
Tabel 2. Jarak antara titik Titik
1
2
3
4
4
1
1000
18
15
23
30
2
18
1000
13
28
23
3
15
13
1000
15
15
4
23
28
15
1000
18
Pembentukan individu Awal. Agar mulai tetap dari home maka titik home diberi titik1, dan setiap individu gen pertamanya adalah titik 1. Penentuan gen 2 sampai gen 5 dilakukan dengan merandom dari 2 sampai 5+1. Nilai random yang didapat adalah 4, 2, 3, 5 maka individu awal adalah 1, 4, 2, 3, 5 yang berarti jalur individu awal adalah dari titik 1 ke titik 4, ke titik 2, ke titik 3 dan terakhir ke titk 5. Untuk mendapatkan individu ke 2 hingga ke terakhir dilakukan dengan cara yang sama. Pada metode ini banyaknya individu diset sebanyak-banyak titik dikali 2, tetapi diambil banyak individu sama dengan banyak titik. Contoh 5 individu dari populasi yang dihasilkan:
Individu 1: 1 2 3 5 4 Jarak=18+13+15+18=64; Individu 2: 1 3 4 5 2 Jarak=15+15+18+23=7; Individu 3: 1 4 2 3 5 Jarak=23+28+13+15=79; Individu 4: 1 2 3 4 5 Jarak=18+13+15+18=64 dan Individu 5: 1 5 3 2 4 Jarak=30+15+13+28=86. Mencari Fitnees. Nilai fitnes setiap individu adalah 1/jarak jalur dari individu, sehingga jarak terpendek akan menghasilkan nilai fitnees yang besar sedangkan jalur yang jauh atau melintasi garis mempunyai nilai fitnees yang kecil. Persen fitnees dibulatkan. Nilai fitnes dari: Individu 1: 1 2 3 5 4 Fitnees = 0,015625 Persen Fitnees=22; Individu 2: 1 3 4 5 2 Fitnees = 0,014085 Persen Fitnees=20; Individu 3: 1 4 2 3 5 Fitnees = 0,012658 Persen Fitnees=18; Individu 4: 1 2 3 4 5 Fitnees = 0,015625 Persen Fitnees=22 dan Individu 5: 1 5 3 2 4 Fitnees = 0,011628 Persen Fitnees=17. Dari Individu yang terbentuk kemudian diambil nilai Fitnees terbesar dan indvidu tersebut dibuat menjadi individu pertama. Membuat Roulet. Pembentukan roulet dilakukan dengan cara menyimpankan nomor individu ke tabel memori sebanyak persen fitnessnya. Individu 1 sebanyak 22 persen, berarti angka 1 disimpan ke memori sebanyak 22, berarti memori 1 sampai 22 berisi 1, sedangkan memori ke 23 sampai 42 berisi 2, memori 43 sampai 60 berisi 3, memori 61 sampai 82 berisi 4, memori 83 sampai 99 berisi 5. Karena nilai persen dibulatkan totalnya bisa kurang atau lebih dari100%, maka diperlu dibatasi sampai 100 memori. Putar Roulet. Pemutaran roulet dilaksanakan dengan mencari nilai random dari 1 sampai 100. Karena 0 tidak diikutkan untuk itu dilakukan random (100) +1. Nilai random yang didapat merupakan individu yang akan diproses selanjutnya. Pencarian individu ini dilakukan sebanyak-banyaknya individu yang diset sebelumnya. Agar individu terbesar tetap diikutkan maka individu yang didapat diletakkan pada posisi ke dua, dengan demikian pemutaran roulet dilakukan hanya sebanyak-banyak populasi1. Nilai random pertama yang didapat adalah 4, nilai random ke-2 adalah 2, nilai random ke-3 adalah 5, nilai random ke-4 adalah 3 maka susunan individu itu adalah sebagai berikut: Individu 1: 1 2 3 5 4 Jarak=18+13+15+18=64; Individu 2: 1 187
Prosiding SNYuBe 2013
2 3 4 5 Jarak=18+13+15+18=64 (Individu 4 lama); Individu 3: 1 3 4 2 Jarak=15+15+18+23=71 (Individu 2 lama); Individu 4: 1 5 3 2 Jarak=30+15+13+28=86 (Individu 5 lama) dan Individu 5: 1 4 2 3 Jarak=23+28+13+15=79 (Individu 3 lama).
5 4 5
Cross Over. Cross over dilakukan dengan saling menukarkan dari dua gen terpilih dari individu terpilih. Awal individu yang dipilih dilakukan secara random, dan individu yang dicroos over adalah individu terpilih sampai individu terakhir. Gen yang dicross over diambil secara random. Sebagai contoh: Individu yang terpilih adalah individu 5 dan nilai random pertama = 3 dan nilai random yang ke dua = 5. Dengan demikian populasi menjadi sebagai berikut: Individu 1: 1 2 3 5 4 Jarak=18+13+15+18=64 fitnees=22%; Individu 2: 1 2 3 4 5 Jarak=18+13+15+18=64 fitnees=22%; Individu 3: 1 3 4 5 2 Jarak=15+15+18+23=71 fitnees=20%; Individu 4: 1 5 3 2 4 Jarak=30+15+13+28=86 fitnees=16% dan Individu 5: 1 4 5 3 2 Jarak=23+18+15+13=9 fitnees=20%. Mutasi. Individu yang dimutasi adalah individu yang mempunyai nilai fitnees paling kecil. Mutasi dilakukan dengan menukar posisi gen (titik) yang mempunyai jarak dengan gen yang disampingnya sebesar 1000 atau lebih, tetapi Gen 1 dipertahankan tetap 1(Home). Dengan cara ini akan didapat individu baru yang mempunyai fitnees yang besar. Hasil dan Pembahasan Hasil penelitian, dilakukan tahapan demi tahapan. Tahapan pertama yaitu menentukan titik-titik yang akan dilalui robot, kemudian dari titik-titik tersebut akan dicari kemungkinan track-track yang ada. Hasil simulasi menunjukkan banyak sekali kemungkinan track yang ada, sehingga tidak mungkin robot akan melalui semua track karena membutuhkan waktu yang terlalu lama, seperti ditunjukkan pada gambar 2 hasil kemungkinan track yang ada antara titik-titik.
Gambar 2. Hasil Kemungkinan Track yang ada antaar titik-titik Untuk menghindari robot melalui semua track, maka perlu dilakukan proses pencarian track baru. Hasil track baru seperti tampak pada gambar 3 memperlihatkan track alternatif dari semua kemunginan track yang ada, sehingga track menjadi sedikit dan track baru merupakan track terpendek dari kemungkinan track yang ada seperti yang 188
Prosiding SNYuBe 2013
tampak ada gambar 2. Maka dengan track baru rute yang dilalui robot akan efektif dengan waktu tempuh paling dekat, hasil ini menunjukkan bahwa penggunaan AG pada proses pencarian jalur terdekat berhasil dengan baik.
Gambar 3. Hasil Track Baru
Gambar 4. Hasil Hitungan Track Api Gambar 4 hasil hitungan track api memperlihatkan kemungkinan track-track jalur antar titi-titik yang akan dilalui robot dalam proses mencari api. Track tersebut cukup banyak kemungkinan, hal ini membuat tidak mungkin robot melalui semua track untuk mencari api, maka perlu dilakukan proses selanjutnya yaitu membuat track baru agar proses pencarian api lebih cepat. Gambar 5 memperlihatkan hasil track baru api yang menunjukkan track terpendek berhasil diperoleh sehingga track yang dilalui robot dalam mencari api menjadi lebih pendek.
189
Prosiding SNYuBe 2013
Gambar 5. Hasil Track Baru Api Kesimpulan Penerapan Algoritma Genetik berhasil mencari jalur terdekat dari banyaknya kemungkinan jalur-jalur yang ada, sehingga jalur yang dilalui robot dalam mencari dan memadamkan api lebih efektif. Referensi [1] Rully M Iqbal, R Dikairono & Tri Arief S., „” Implementasi Sistem Vavigasi Behavior-Based Robotic dan Kontroler Fuzzy pada Manuver Robot Cerdas Pemadan Api” Jurnal Teknik POMITS Vol 1 No. 1, 2012, 1-8. [2] Bima S. B. D., „Perencanaan Jalur Robot pada Lingkungan Dinamis Berbasis Compact Genetik Algoritma“, Seminar Nasional Informatika UPN Veteran Yogyakarta, 2009. [3] Kontes Robot Cerdas Idnonesia (KRCI) pada http://www.dikti.go.id/?page_id=417.
190
