Implementasi & Analisis Algoritma Grammatical Evolution UntukMemecahkan Kasus Santa fe trail

ERGANDARA PURBA SETRA

Informasi Umum

Kode

15.04.550

Klasifikasi

C -

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Artificial Intelligence

Dilihat

39 kali

Informasi Lainnya

Abstraksi

<p>Santa fe Trail merupakan suatu kasus dimana terdapat Ant yang mencari food yang tersebar membentuk jalur. Tujuan dari kasus ini adalah mencari suatu perintah untuk menggerakan Ant agar Ant bergerak mengambil seluruh food yang tersebar. Pada umumnya terdapat 89 food yang disebar. Tantangan dari kasus ini adalah food disebar membentuk jalur, namun jalur ini tidak sepenuhnya tersambung. Terdapat beberapa rintangan diantaranya, jalur terpotong 1/2/3 langkah; jalur membentuk huruf L dengan panjang yang bervariasi. Grammar Evolution (GE) dipilih untuk menyelesaikan kasus ini. GE merupakan salah satu algoritma evolusi. GE menggunakan grammar dalam membentuk solusinya. Dengan adanya grammar ini GE mudah untuk digunakan pada berbagai macam kasus. Dalam GE juga terdapat proses duplikasi yang akan menambah panjang kromosom bila panjang asal tidak cukup untuk ditranslasikan, sehingga menambah kemungkinan solusi dapat tercapai. Digunakan tiga peta yang berbeda pada pengujian. Peta1 merupakan peta yang umum digunakan pada kasus ini. Peta1 digunakan untuk menguji seberapa baik solusi optimal yang dapat dicapai dan menganalisa pengaruh metode seleksi roulette wheel & tournamen selection dalam mencapai solusi. Pada peta2 food terpotong satu langkah; peta3 food terpotong dua langkah; sedangkan pada peta4 hampir mirip dengan peta1 namun ditambahkan pemotongan jalur pada titik tertentu. Hasil pengujian dengan menggunakan peta umum santa fe trail, didapatkan langkah terbaik 405 langkah dengan menggunakan grammar2. Dengan menggunakan grammar1 langkah terbaiknya adalah 462 langkah. Peta2, peta3 dan peta4 tidak dapat mencapai solusi. Pada peta2 food maksimum yang dapat terambil sebanyak 43 sedangkan peta3 terambil 28 dari total 48. Peta4 dapat mengambil 50 food dari 75.</p>