-ABSTRAK-
Makalah ini memaparkan tentang implementasi metode simulated annealing
pada sebuah robot mobil mandiri untuk mencari rute terpendek. Karena robot
mobil dikontrol dengan menggunakan mikrokontroler, maka metode simulated
annealing juga diimplementasi pada mikrokontroler yang sama. Mikrokontroler
yang digunakan dalam aplikasi ini adalah mikrokontroler AT89S51 yang merupakan
salah satu mikrokontroler keluarga MCS51. Pada aplikasi ini, awalnya, robot
diberitahu informasi peta, posisi start dan posisi tujuan. Dengan menggunakan
metode simulated annealing, robot akan mencari rute terpendek dari posisi start
sampai posisi tujuan, kemudian robot akan bergerak sesuai dengan rute yang
telah didapat. Pengujian telah dilakukan dengan variasi posisi start dan posisi
tujuan. Hasil pengujian menunjukkan bahwa metode simulated annealing berhasil
diimplementasi pada level mikrokontroler. Robot dapat mencari rute terpendek
dengan metode simulated annealing dan robot dapat bergerak mengikuti rute yang
telah didapatkan. Kata
kunci—simulated annealing, robot
mobil, mikrokontroler, AT89S51.
I.
PENDAHULUAN
Pada penelitian
sebelumnya[1], telah berhasil diimplementasi metode hill climbing pada level mikrokontroler
dengan aplikasi. Metode hill climbing diimplementasi pada sebuah robot mobil
untuk mencari rute terpendek. Namun dari hasil penelitian tersebut, terdapat kelemahan
yaitu tidak kepastian metode hill climbing dapat menemukan solusi yang
diinginkan. Kadang metode hill climbing menghasilkan rute yang tidak dapat
mencapai posisi tujuan. Karena itu, penelitian ini merupakan penelitian lanjutan
untuk mendapatkan hasil yang lebih baik. Metode yang dipilih utnuk menggantikan
metode hill climbing adalah metode simulated annealing yang pada dasarnya merupakan
pengembangan dari metode hill climbing. Tujuan utama dari penelitian ini adalah
mengimplementasikan metode-metode sistem cerdas pada platform mikrokontroler.
Beberapa metode sistem cerdas yang telah berhasil diimplementasikan pada
platform mikrokontroler antara lain fuzzy logic[2], algoritma genetika[3],
termasuk hill climbing[1]. Dan kali ini metode yang akan diimplementasikan
adalah simulated annealing. Selain itu, tentunya diharapkan metode simulated
annealing dapat memberikan hasil yang lebih baik dari penelitian sebelumnya[1]
yang menggunakan metode hill climbing. Dalam penelitian ini, mikrokontroler
yang dipilih untuk implementasi metode simulated annealing adalah mikrokontroler
keluarga MCS51 yaitu mikrokontroler AT89S52. Alasan pemilihan mikrokontroler
ini adalah karena mikrokontroler ini sangat populer dan tersedia banyak di Indonesia,
serta harganya yang tidak terlalu mahal. Dengan demikian diharapkan penelitian
ini dapat memberikan kontribusi yang positif untuk penelitianpenelitian selanjutnya
dalam mengimplementasikan metodemetode kecerdasan buatan pada level
mikrokontroler khususnya mikrokontroler keluarga MCS51.
II. METODE SIMULATED ANNELALING
Simulated annealing
adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan
probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk
mencari pendekatan terhadap solusi optimum global dari suatu permasalahan.
Masalah yang membutuhkan pendekatan simulated annealing adalah masalah-masalah
optimisasi kombinatorial,di mana ruang pencarian solusi yang ada terlalu besar,
sehingga hamper tidak mungkin ditemukan solusi eksak terhadap permasalahan itu.
Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan
dalam mempelajari prose pembentukan kristal dalam suatu materi. Agar dapat terbentuk
susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat
tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali
dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan
kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas,
mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan
yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada
akhirnya menemukan tempat yang optimum, dimana energi internal yang dibutuhkan
atom itu untuk mempertahankan posisinya adalah minimum. Simulated annealing
berjalan berdasarkan analogi dengan proses annealing tersebut. Simulated annealing
memanfaatkan analogi antara cara pendinginan dan pembekuan metal menjadi sebuah
struktur crystal dengan energi yang minimal (proses penguatan) dan proses pencarian
untuk tujuan minimal.
Berikut adalah
algoritma metode simulated annealing: 1. Evaluasi keadaan awal. Jika tujuan
maka KELUAR (pencarian solusi selesai). Jika tidak lanjutkan dengan keadaan
awal sebagai keadaan sekarang. 2. Inisialisasi BEST_SO_FAR untuk keadaan
sekarang. 3. Inisialisasi suhu (T) sesuai dengan annealing schedule.
4. Kerjakan hingga solusi ditemukan
atau sudah tidak ada operator baru lagi akan diaplikasikan kekondisi sekarang.
\
a. Gunakan operator
yang belum pernah digunakan
untuk menghasilkan
keadaan baru.
b. Evaluasi kondisi
baru dengan menghitung: E = nilai sekarang – nilai keadaan baru (1)
i. Jika kondisi baru
tujuan maka KELUAR (pencarian solusi selesai).
ii.Jika bukan tujuan,
namun nilainya lebih baik dari sekarang, maka jadikan keadaan tersebut sebagai keadaaan
sekarang.
iii. Jika nilai
kondisi baru tidak lebih baik daripadakeadaan sekarang, maka tetapkan kondisi
baru sebagai keadaan sekarang dengan probabilitas: p’ = e -.E /T (2) dalam
kondisi ini juga generate random number dengan range [ 0 , 1 ]. Jika random
number lebih kecil dari p’ maka solusi diterima. Jika random
number lebih besar
dari p’ abaikan (solusi tidak diterima)
c. Perbaiki T sesuai
dengan annealing schedule
5. BEST_SO_FAR adalah solusi yang
dicari. Perbedaan antara metode simulated annealing dan metode simple hill climbing
adalah:
• Simulated annealing
memilki annealing schedule
• Pada metode
simulated annealing solusi yang jelek
masih ada kemungkinan
untuk diterima
• Nilai keadaan
sekarang adalah nilai yang terbaik sepanjang proses berlangsung. Kemudian jika keadaan
yang baru yang lebih jelek daripada keadaansekarang (karena kurang beruntung
dalam penerimaan solusi), keadaan yang baru tersebut masih bisa digunakan.
III.
DESKRIPSI SISTEM
A. Perangkat Keras dan Mekanik Robot Mobil
Bentuk dasar robot
terbuat dari kayu tebal 3mm dan berbentuk oval 14,5cm x 11cm. Robot dilengkapi
dengan 2 buah roda dan sebagai penggerak digunakan 2 buah motor DC dengan
masing-masing motor memiliki sebuah gear box. Gambar 1 menunjukkan gambar
mekanik penggerak robot. Robot mobil dirancang untuk bergerak mengikuti garis. Karena
itu robot mobil dilengkapi dengan sensor cahaya. Secara umum, diagram blok
perangkat keras robot dapat dilihat pada gambar 2.

Gambar 1. Mekanik penggerak robot
mobil.

Gambar 2. Diagram blok perangkat keras
robot.
Sensor cahaya yang
digunakan adalah sepasang LED dan LDR. Karena output dari sensor LDR berupa
sinyal analog, maka untuk merubah menjadi digital digunakan rangkaian komparator.
Output rangkaian ini hanya mempunyai 2 state yaitu low dan high yang
menunjukkan warna hitam dan putih. berikut gambar 3 dan 4 menunjukkan gambar rangkaian
sensor dan komparator.

Gambar 3. Rangkaian sensor

Gambar 4. Rangkaian komparator
Output sensor akan
dibaca oleh mikrokontroler sebagi informasi untuk mengendalikan robot mobil
bergerak mengikuti garis putih. Sebagai penggerak robot mobil, digunakan 2 buah
motor DC, masing-masing roda digerakkan oleh satui motor DC. Rangkaian driver
motor DC yang digunakan adalah rangkaian H-Bridge. Rangkaian HBridge ini
menggunakan transistor TIP 41 dan TIP 42. berikut gambar 5 menunjukkan gambar
rangkaian driver motor DC.

Gambar 5. Rangkaian driver motor DC
Mikrokontroler yang
digunakan sebagai pengendali dari robot mobil adalah mikrokontroler AT89S51. mikrokontroler
ini termasuk mikrokontroler keluarga MCS51. rangkaian mikrokontroler ini
dirancang sederhana yaitu berupa rangkaian single chip, tanpa ada memori eksternal.
Berikut gambar 6 menunjukkan gambar rangkaian mikrokontroler yang digunakan dan
tabel 1 menunjukkan tabel koneksi mikrokontroler dengan rangkaian sensor dan rangkaian
driver.

Gambar 6. Rangkaian single chip
mikrokontroler
Tabel 1. Tabel koneksi mikrokontroler
dengan sensor dan driver motor

B. Perangkat Lunak
Secara umum cara
kerja sistem robot mobil untuk mencari rute terpendek adalah seperti yang
ditunjukkan pada gambar 7.

Gambar 7. Diagram blok sistem kerja
robot mobil

Gambar 8. Peta area lintasan robot
mobil

Gambar
9. flowchart perangkat lunak robot mobil.
Pemetaan merupakan hal yang penting yang
pertama kali dilakukan dalam alur program. Berhasil atau tidaknya pencarian
benda ataupun penentuan jalur terpendek tidak lepas dari pemetaan ini. Dengan
pemetaan ini maka seluruh area yang ada akan digambarkan. Hasil yang didapat
dari pemetaan tersebut akan dijadikan acuan untuk menghitung kuadrat jarak
lurus setiap titik yang ada pada area terhadap titik tujuan. Nilai hasil
perhitungan jarak yang didapat tersebut akan disimpan di dalam alamat RAM mikrokontroler.
Nilai tersebut kemudian akan dianalisa dengan menggunakan metode simulated
annealing. Dengan metode ini maka akan didapatkan rute yang terpendek menuju
titik tujuan. Namun, rute ini masih berupa alamat RAM bukan nilai ouput port
yang sesungguhnya. Oleh karena itu perlu diubah menjadi output port. Barulah
robot tersebut dapat menelusuri jalur yang telah didapat. Jalur tersebut
merupakan jalur terpendek menuju tujuan yang diinginkan.
IV.
HASIL PENGUJIAN
Pengujian sistem
telah dilakukan dengan variasi posisi start dan posisi tujuan untuk melihat
performans system apakah dapat mencari rute terpendek. Beberapa pengujian yang
dilakukan antara lain posisi start (0,5) dan posisi tujuan (0,2), posisi start
(0,0) dan posisi tujuan (0,5), posisi start (2,0) dan posisi tujuan (4,5),
posisi start (0,4) dan posisi tujuan (1,0), posisi start (1,0) dan posisi
tujuan (4,0). Berikut gambar 10 sampai gambar 14 menunjukkan rute dari hasil
pengujian yang didapatkan oleh robot mobil dengan menggunakan metode simulated
annealing.

Gambar 10. Rute hasil pengujian dengan
psosi start (0,5)

Gambar 11. Rute hasil pengujian dengan
psosi start (0,0) dan
posisi tujuan (0,5)

Gambar 12. Rute hasil pengujian dengan
psosi start (0,2) dan
posisi tujuan (4,5)

Gambar 13. Rute hasil pengujian dengan
psosi start (0,4) dan
posisi tujuan (1,0)

Gambar 14. Rute hasil pengujian dengan
psosi start (1,0) dan
posisi tujuan (0,4)
Bila melihat hasil
pengujian yang telah dilakukan seperti yang ditunkukkan oleh gambar 10 sampai
gambar 13, terlihat bahwa dengan menggunakan metode simulated annealing, robot
mobil berhasil mencari rute terpendek. Dan robot mobil juga dapat bergerak
mengikuti rute yang telah didapatkan. Tetapi pada hasil pengujian yang
ditunjukkan oleh gambar 14, metode simulated annealing terjebak pada rute yang
sama sehingga robot hanya bergerak berputarputar saja pada area tertentu.
V.
KESIMPULAN
Dari hasil pengujian
yang telah dilakukan dapat diambil kesimpulan bahwa metode simulated annealing
berhasil di terapkan untuk pencarian rute terdekat pada robot mobil. Tetapi
masih terdapat kemungkinan bahwa simulated annealing tidak dapat memberikan
hasil yang terbaik seperti hasil pengujian yang ditunjukkan oleh gambar 14.
Pada penelitian ini simulated annealing telah berhasil diimplementasikan pada
level mikrokontroler.
REFERENSI
[1] Thiang, Handry Khoswanto, Felix
Pasila, Hendra Thelly, “Aplikasi Metode Hill Climbing pada Standalone Robot
Mobil untuk Mencari Rute Terpendek”, Prosiding Seminar KOMMIT 2008, Depok,
2008.
[2] Thiang, Anies Hannawati, Resmana
Lim, Hany Ferdinando, “PetraFuz: a Low Cost Embedded Controller Based Fuzzy
Logic Development System”, Proceeding of The Fourth Asian Fuzzy Systems
Symposium (AFSS 2000), Tsukuba
Science City,
Jepang,
Juni 2000.
[3] Thiang, Ronald Kurniawan, Hany
Ferdinando, “Implementation of Genetic Algorithm on MCS51 Microcontroller for
Finding the Shortest Path”. Proceeding of Seminar of Intelligent Technology and
Its Applications (SITIA 2001), ITS-Surabaya, May 2001.
[4] Rich, Elaine. Artificial
Intelligence. New York:
McGraw-Hill, 1991.
[5] AT89S51 Datasheet. San Jose, CA:
Atmel Corporation, 1995. Implementasi Metode.