Skripsi

Penyelesaian masalah travelling salesman problem (TSP) dengan menggunakan algoritma genetika pada digraph tidak komplit / Dyah Arum Rachmawati

Abstrak
ABSTRAK Rachmawati Dyah Arum. 2008. Penyelesaian Masalah Travelling Salesman Problem (TSP) Dengan Menggunakan Algoritma Genetika Pada Digraph Tidak Komplit. Skripsi Jurusan matematika FMIPA Universitas Negeri Malang. Dosen pembimbing (1) Dra. Sapti Wahyuningsih M.Si (II) Mohamad Yasin S.Kom M.Kom Kata kunci Algoritma Genetika Travelling Salesman problem Teori graph merupakan salah satu bagian matematika yang bermanfaat untuk menyelesaikan permasalahan dalam kehidupan sehari-hari. Salah satu permasalahan yang dapat diselesaikan menggunakan teori graph adalah masalah travelling Salesman problem yaitu persoalan optimasi untuk mencari perjalanan terpendek bagi pedagang keliling yang ingin berkunjung ke beberapa kota dan kembali ke kota asal keberangkatan. Masalah yang dibahas dalam skripsi ini adalah masalah TSP yang akan diselesaikan dengan menggunakan Algoritma Genetika yang diaplikasikan pada digraph tidak komplit. Langkah pertama yang akan dilakukan pada penggunaan TSP dalam algoritma genetika adalah memilih pengkodean dengan representasi yang paling sesuai kemudian menentukan populasi awal yang akan digunakan dalam mekanisme algoritma. Langkah selanjutnya adalah menentukan fungsi-fungsi yang digunakan oleh algoritma selama mekanisme berlangsung yaitu fungsi evaluasi dan fungsi seleksi. Selanjutnya mekanisme penyesuaian dan dilanjutkan dengan proses seleksi serta menentukan prosedur operator genetik yang sesuai. Langkah terakhir yaitu seleksi terhadap kromosom terbaik. Dari ketiga contoh yang telah dibahas dapat diduga bahwa algoritma genetika menghasilkan lebih dari satu solusi sehingga dapat dipilih alternatif solusi yang diinginkan. Algoritma genetika juga dapat menyelesaikan persoalan pada digraph tidak komplit walaupun memerlukan pengerjaan yang lama dan proses yang rumit. Dengan menggunakan alat bantu berupa software Grin40 untuk TSP dapat diperoleh solusi yang tidak tunggal. Sedangkan dengan menggunakan software WinQSB dengan metode Branch and Bound diperoleh solusi yang tunggal.

Informasi Detail

DDC

Rs 511.5 RAC p

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2008.

Deskripsi Fisik

ix, 86 hlm. : il. : tab. ; 30 cm.

Bahasa

Indonesia

No Reg

01037/KI/09

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2008

Subjek

1. TEORI GRAPH
2. TRAVELLING SALESMAN PROBLEM
3. ALGORITMA GENETIKA

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. MOHAMAD YASIN

Lampiran Berkas