Penerapan Algoritma Genetika Pada Perencanaan Lintasan Kendaraan

Postingan ini merupakan tugas mata kuliah softskill saya yang berupa ringkasan dari jurnal yang berhubungan dengan komputasi modern.

Jika anda ingin mengunjungi situs aslinya ada di http://eprints.undip.ac.id/25226/

Dan jika anda ingin mengetahui isi lengkap dari jurnal ini, silahkan download di http://eprints.undip.ac.id/25226/1/ML2F003505.pdf

ABSTRAK

Algoritma genetika adalah algoritma pencarian heuristik yang didasarkan atas mekanisme evolusi biologis. Individu yang lebih kuat (fit) akan memiliki tingkat survival dan tingkat reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang fit. Konsep penting dalam teori evolusi adalah fitness dan selection untuk proses reproduksi. Algoritma genetika telah banyak diaplikasikan untuk penyelesaian masalah dan pemodelan dalam bidang teknolog seperti: optimasi, pemrograman otomatis dan machine learning. Aplikasi perencanaan lintasan pada tugas akhir ini bertujuan untuk mencari atau menemukan jalur terpendek yang tidak melalui penghalang pada sebuah peta dari satu titik awal sampai pada titik tujuan. Peta merupakan gambar 2 dimensi dengan penghalang berupa lingkaran. Dalam tugas akhir ini algoritma genetika akan melakukan proses evolusi pada populasi awal yang diberikan. Dalam proses evolusi terdapat beberapa bagian penting pada algoritma genetika yaitu : pindah silang (crossover), mutasi, elitisme . Pada implementasi program algoritma genetika dapat mencari jalan terpendek yang bebas hambatan. Pada pengujian dilakukan dengan titik acuan dan populasi yang berbeda, yang menghasilkan jarak terpendek yang ditemukan ialah 28,7062 satuan.

Kata kunci: algoritma genetika, perencanaan lintasan, fitness, dan selection.

Algoritma genetika atau disingkat GA (Genetik Algorithm) merupakan suatu konsep komputasi yang pertama kali diutarakan oleh John Holland dari Universitas Michigan pada tahun 1975. Peneliti lain yang banyak memberikan kontribusi antara lain adalah Goldberg, De Jong, Grafenstette, Davis dan Muhlenbeing. Aplikasi GA meliputi berbagai hal yang luas seperti, perencanaan lintasan, desain VLSI, penalaan PID, pengolahan sinyal, fungsi optimisasi pada perencanaan sistem tenaga listrik.

Algoritma genetika memiliki beberapa keunggulan dibandingkan dengan metode komputasi konvensional antara lain :

1. Sifat dasarnya yang menunjang komputasi parallel dimana kekuatan cariannya adalah sebesar jumlah populasinya.
2. Sifatnya yang tidak membutuhkan pengetahuan dasar tentang objek yang sedang dikalkulasi.
3. Sifatnya yang lentur, sehingga perubahan input atau masuknya gangguan pada sistem secara on-line  pada saat perhitungan dapat segera diantisipasi.

Penerapan Algoritma Genetika pada Perencanaan Lintasan Kendaraan

Algoritma genetika adalah suatu bentuk teknik pencarian secara  stochastic, berdasarkan mekanisme yang ada pada seleksi alam dan genetik secara natural. Setiap makhluk hidup memiliki gen-gen, yaitu bagian dari kromosom yang menentukan atau mempengaruhi karakteristik setiap individu. Mekanisme genetik mencerminkan kemampuan individu untuk melakukan perkawinan dan menghasilkan keturunan yang memiliki karakteristik yang hampir sama dengan orang tuanya. Sedangkan prinsip seleksi alam menyatakan bahwa setiap makhluk hidup dapat mempertahankan dirinya jika mampu beradaptasi dengan lingkungannya. Dengan demikian, diharapkan keturunan yang dihasilkan memiliki kombinasi karakteristik yang terbaik dari orang tuanya, dan dapat menopang generasi-generasi selanjutnya.

Lintasan terbaik pada generasi ke-10 dengan 1 titik acuan

Perancangan Program

Aplikasi perangkat lunak penerapan algoritma genetika pada perencanaan lintasan ini terdiri dari 4 komponen utama, yaitu proses inisialisasi awal, fungsi evaluasi, seleksi, dan operator genetika. Keluaran dari aplikasi ini adalah gambar 2 dimensi yang menunjukkkan lintasan terpendek.

Gambar diagram alir sistem perencanaan lintasan dengan algoritma genetika

Analisa & Pembahasan

Piranti lunak penerapan algoritma genetika pada perencanaan lintasan kendaraan dibuat menggunakan Matlab7.1 dengan sistem operasi Microsoft Windows XP.

Gambar 1 Lintasan terbaik pada generasi ke-10 dengan 1 titik acuan

Gambar 2 lintasan terbaik pada generasi ke-100 dengan 1 titik acuan

 Hasil dari kedua gambar di atas ada perbedaan pada jumlah generasi dan hasil yang ditemukan. Pada gambar 1. dilakukan iterasi sampai pada generasi ke-10 dan pada gambar 2. dilakukan iterasi sampai pada generasi ke-100. Dimana jarak yang ditempuh pada gambar 2. lebih kecil dibandingkan dengan gambar 1. Hal ini menunjukkan bahwa hasil yang ditemukan pada iterasi ke-100 lebih baik daripada hasil pada iterasi ke-10.

Kesimpulan

Dari hasil analisa dan pembahsan terhadap perangkat lunak, dapat diambil beberapa kesimpulan sebagai berikut :

• Pertama, algoritma genetika memiliki kemampuan untuk melakukan pendekatan pada masalah perencanaan lintasan kendaraan.
• Kedua, Algoritma genetika menghasilkan jarak terpendek pada iterasi yang lebih besar dengan titik acuan yang sama. Semakin banyak iterasi yang dilakukan semakin baik hasil yang ditemukan.
• Ketiga, Lintasan terpendek didapat pada generasi ke-100 dengan 2 titik acuan. Hal ini menunjukkan bahwa pada permasalahan tugas akhir ini dengan 2 titik acuan algoritma genetika telah dapat menenmukan hasil paling optimum.

Beberapa hal yang perlu diperhatikan untuk penelitian ke depan adalah sebagai berikut :

• Pertama, Perlu dilakukan perbandingan dengan metode atau pendekan yang lain, seperti algoritma coloni semut (ACO).
• Kedua, Untuk pengujian lebih lanjut perlu dilakukan penerapan hasil pada perangkat keras dalam hal ini kendaraan.
• Ketiga, Perlu dilakukan perencanaan lintasan pada ruang lingkup yang lebih kompleks, seperti peta 3 dimensi (3D).

Sumber: http://eprints.undip.ac.id/25226