SKRIPSI Jurusan Pendidikan Jasmani dan Kesehatan - Fakultas Ilmu Keolahragaan UM, 2010

Ukuran Huruf:  Kecil  Sedang  Besar

Aplikasi Algoritma Seleksi Klon (Clonal Selection) pada Travelling Salesman Problem (TSP)

novi tri suhartini

Abstrak


ABSTRAK

 

Suhartini, Novi Tri.  2010. Aplikasi Algoritma Seleksi Klon (Clonal Selection) Pada Travelling Salesman Problem (TSP). Skripsi, Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I). Prof. Drs. Purwanto, Ph.D, (II). Darmawan Satyananda,S.T,M.T.

Kata kunci: graph, Travelling Salesman Problem (TSP), optimasi, sistem imun,algoritma seleksi klon (Clonal Selection). seleksi positif/seleksi negatif.

Traveling Salesman problem yang biasa disebut TSP merupakan salah satu aplikasi dari sikel Hamilton. Definisi dari travelling salesman problem adalah suatu permasalahan yang digunakan untuk menemukan sikel Hamilton pada graph komplit berbobot yang memiliki total bobot sisi minimum. TSP merupakan suatu permasalahan yang awalnya dialami oleh seorang sales yang harus mengunjungi beberapa kota dan harus melalui setiap kota tersebut tepat satu kali dan harus kembali lagi ke kota awal dengan jarak tempuh dan biaya seminimum mungkin.

Seleksi klon (Clonal Selection) adalah mekanisme yang digunakan oleh sistem kekebalan tubuh (Immune system) untuk menyeleksi sel yang akan diperbanyak atau di klon berdasarkan kemampuan untuk mengenali antigen pada pantogen (benda asing yang berasal dari luar tubuh). Pada seleksi klon terjadi proses seleksi positif dan seleksi negatif, yaitu upaya untuk meningkatkan kemampuan untuk mengenali dan mengikat antigen. Algoritma seleksi klon (Clonal Selection) merupakan suatu algoritma yang terinspiasi oleh seleksi klon yang terjadi pada sistem kekebalan tubuh manusia untuk menemukan solusi optimum.

            Penulisan skripsi ini bertujuan untuk menyelesaikan permasalahan TSP dengan menggunakan algoritma seleksi klon dimana solusi yang diberikan tidak tunggal dengan jarak tempuh yang sama. Untuk menunjukkan keoptimalan dari

algoritma seleksi klon ini, maka algoritma koloni semut dan algoritma branch and bound digunakan sebagai algoritma pembanding. Pada beberapa kasus penyelesaian TSP dengan menggunakan algoritma seleksi klon dan algoritma koloni semut  diperoleh hasil yang sama.

Kelebihan dari algoritma seleksi klon adalah banyaknya variasi solusi yang dihasilkan, yang berupa banyak rute dengan afinitas yang sama. Sedangkan kelemahan algoritma ini terletak pada waktu yang relatif lama dalam menyelesaikan masalah dengan iterasi manual. Dalam setiap iterasinya algoritma seleksi klon menggunakan suatu fungsi yang random/tidak tetap. Oleh karena itu, algoritma seleksi klon merupakan algoritma yang berbasis komputasi. Untuk mempermudah dalam proses perhitungannya, maka dalam skripsi ini Algoritma seleksi klon dibuat dalam suatu bahasa program dengan bahasa pemrograman Delphi.