Yuliagandi, Devi (2010) Implementasi algoritma genetika hibrid (First improvement search) pada travelling salesman problem / Devi Yuliagandi. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Kata kunci graph Travelling Salesman Problem (TSP) Algoritma Genetika Hibrid. Travelling Salesman Problem (TSP) merupakan suatu permasalahan dalam memilih rute dari salesman yang akan mendistribusikan barang ke berbagai kota dan kembali ke kota awal dimana setiap kota harus dilewati hanya satu kali dengan total bobot seminimum mungkin. Dalam hal ini bobot bisa dalam ukuran jarak waktu ataupun biaya. Algoritma yang dapat menyelesaikan Travelling Salesman Problem diantaranya farthest insertion heuristic dan nearest neighbor. Terdapat algoritma lain yang dapat menyelesaikan Travelling Salesman Problem dan menghasilkan solusi tidak tunggal yaitu algoritma genetika. Algoritma genetika merupakan teknik optimasi yang didasarkan pada proses evolusi makhluk hidup dimana dalam evolusi tersebut makhluk hidup mengalami mekanisme seleksi alam (diantaranya pindah silang dan mutasi) untuk bertahan hidup. Algoritma genetika merupakan suatu algoritma yang dapat diaplikasikan dalam berbagai jenis permasalahan optimasi. Algoritma first improvement search adalah salah satu keluarga local search yang memperhitungkan perubahan di lingkungan persekitarannya dari keadaan yang diberikan untuk menghasilkan nilai optimal. Selain itu terdapat algoritma lain yang dapat menghasilkan solusi tidak tunggal yang merupakan pengembangan dari algoritma genetika. Algoritma tersebut adalah algoritma genetika hybrid. Algoritma genetika hybrid merupakan gabungan dari algoritma genetika dan local search (first improvement search). Dari uji coba yang dilakukan solusi yang dihasilkan algoritma genetika hybrid sama atau lebih baik daripada algoritma genetika dan metode-metode heuristic. Hal ini dipengaruhi oleh adanya local search. Solusi dari local search akan lebih baik jika pada langkah awal telah ditemukan nilai fitness yang lebih baik sebelum atau sampai batas p (p 61646 N 1 8804 p 8804 15). Namun terdapat beberapa parameter yang harus diperhatikan diantaranya banyaknya populasi yang digunakan dan maksimum generasi. Parameter tersebut akan mempengaruhi unjuk kerja dari algoritma genetika hybrid. Oleh karena itu dalam melakukan proses algoritma genetika hybrid perlu adanya kesesuaian antara jumlah populasi dan maksimum generasi terhadap jumlah kota. Maksimum generasi yang baik adalah 30% dari ukuran populasi dan ukuran populasi yang digunakan sebaiknya tidak kurang dari 30. Untuk mempermudah dalam perhitungan maka dibuat software algoritma genetika hybrid dalam suatu bahasa pemrograman delphi.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 23 Sep 2010 04:29 |
| Last Modified: | 09 Sep 2010 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/16994 |
Actions (login required)
 |
View Item |