Perbandingan Algoritma Tabu Search dan Algoritma Genetika Pada Optimasi Produksi Perusahaan Makanan Khas Bengkulu1. Pendahuluan Industri pariwisata merupakan salah satu sektor penting dalam meningkatkan perekonomian negara dan masyarakat. Pariwisata telah menjadi salah satu industri yang tumbuh dan berkembang pesat, memiliki peran dan makna yang besar dalam proses pembangunan dan perkembangan kehidupan manusia. Kawasan pesisir pantai Kota Bengkulu adalah salah satu kawasan yang menjadi andalan karena memiliki panorama alam berupa pasir putih yang indah dan membentang panjang, serta banyaknya peninggalan sejarah (heritage) di kawasan pesisir pantai Kota Bengkulu. Heritage tersebut antara lain berupa Benteng Marlborough, Rumah Kediaman Bung Karno, Tugu Hamilton, Monumen Thomas Parr, dan beberapa heritage lainnya yang menarik. Satu hal yang perlu diketahui, industri pariwisata belum lengkap tanpa adanya kuliner khas daerah yang disajikan di tempat wisata tujuan. Para wisatawan yang berkunjung tentu saja akan mencari makanan khas daerah wisata tujuan. Hal ini memicu tumbuhnya industri-industri makanan khas daerah yang menyediakan makanan khas daerah. Beberpa industri makanan khas Bengkulu adalah Sari Rasa, Naga Rasa, Ratu Samban, Cita Rasa, dan ENDE. Makanan yang diproduksi diantaranya perut punai, kue tat, manisan terong, lempuk, siput wijen, keripik rafflesia, dan kerupuk bawang. Permintaan konsumen yang bervariasi dan adanya kompetitor membuat perusahaan harus mengoptimalkan produksi.

1

Perusahaan harus kreatif dan mengerti keinginan pasar. Perusahaan harus bisa menentukan jumlah dan jenis makanan yang diproduksi sehingga dapat memaksimalkan keuntungan. Permasalahan optimasi keuntungan dapat menjadi sebuah permasalahan baru karena banyaknya kemungkinan dan kombinasi solusi yang berkembang seiring meningkatnya tugas dan sumber daya serta munculnya fungsi tujuan yang baru. Pencarian solusi atas permasalahan optimasi dapat diselesaikan dengan pendekatan heuristik. Pendekatan ini merupakan pendekatan pencarian solusi atas permasalahan yang ada dengan menggunakan pengetahuan yang didapat pada pencarian sebelumnya. Pada pencarian heuristik ada beberapa metode yang sudah mulai dikembangkan, antara lain: generate and test, hill climbing, Tabu Search, simulated annealing, algoritma genetika dan algoritma semut (Kusumadewi dan Purnomo, 2005:2). Algoritma tabu search dan algortima genetika merupakan algoritma yang dapat digunakan untuk membantu optimasi. Konsep dasar dari tabu search adalah pengefektifan proses pencarian solusi dengan cara mencari solusi terbaik (best solution) pada setiap tahap pelacakan. Langkah-langkah ini kemudian dimasukkan ke dalam daftar yang disebut dengan tabu list. Proses pencariannya itu sendiri dilakukan dengan cara menentukan solusi awal kemudian dilakukan gerakan ke solusi-solusi berikutnya dan baru berhenti sampai kriteria penghentian tercapai. Sedangkan algoritma genetik adalah algoritma pencarian yang berdasarkan pada mekanismesistem natural yakni genetik dan seleksi alam. Adanya perbedaan algoritma tabu search dan algoritma genetika dalam menyelesaikan masalah membuat penulis tertarik untuk membandingkan

2

keduanya. Membandingkan algoritma tabu search dan algoritma genetika dalam kasus optimasi produksi makanan khas Bengkulu.

2. Perumusan Masalah Berdasarkan uraian pada latar belakang di atas, maka rumusan masalah dalam penelitian ini adalah: 1. Algoritma manakah yang lebih optimal antara Tabu Search dan Algoritma Genetika dalam mencari solusi optimal pada masalah optimasi perusahaan makanan khas Bengkulu? 2. Bagaimana mengimplementasikan metode Tabu Search dan Algoritma Genetika dalam mencari solusi optimal pada problem optimasi perusahaan makanan khas Bengkulu?

3. Batasan Masalah Agar pembahasan dalam penelitian ini dapat dilakukan secara terarah dan sesuai dengan yang diharapkan, maka perlu diterapkan batasan-batasan permasalahan yang akan dibahas, antara lain: 1. Penelitian ini hanya membandingkan optimasi hasil akhir dari metode Tabu Search dan Algoritma Genetika berdasarkan variabel ketersediaan bahan baku, jumlah pemakaian bahan, keuntungan satuan kotak makanan, dan jenis makanan yang diproduksi oleh perusahaan ENDE. 2. Aplikasi ini akan dibangun menggunakan bahasa pemrograman MATLAB.

3

3.

Model perancangan yang digunakan untuk menganalisis dan mendesain aplikasi ini adalah model perancangan Data Flow Diagram (DFD).

4. Tinjauan Pustaka 4.1.Tabu Search Sri Kusumadewi dan Hari Purnomo (2005) menyatakan bahwa tabu search merupakan suatu metode optimasi yang menggunakan short-term memory untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokal. Metode ini menggunakan tabu-list untuk menyimpan beberapa soulusi yang baru saja dievaluasi. Selama proses optimasi, pada setiap iterasi, solusi yang akan dievaluasi akan dicocokkan terlebih dahulu dengan isi tabu-list untuk melihat apakah solusi tersebut sudah ada pada tabu-list. Apabila solusi itu sudah ada pada tabu-list, maka solusi itu tidak akan dievaluasi lagi pada iterasi berikutnya. Apabila sudah tidak ada lagi solusi yang tidak menjadi anggota tabu-list, maka nilai terbaik yang diperoleh merupakan solusi yang sebenarnya. Pemilihan kandidat terbaik didasarkan nilai fungsi tujuan. Pemeriksaan nilai fungsi tujuan terlebih dahulu dilakukan sebelum pemeriksaan status tabu. Apabila nilai fungsi tujuan sebuah kandidat lebih baik dari yang lain, maka kandidat tersebut berpotensi untuk diterima sehingga perlu diperiksa status tabu-nya. Pemilihan kandidat solusi terbaik yang dilakukan oleh tabu search menggunakan prinsip global test strategy bukan first best strategy. Global test strategy adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini dengan solusi terbaik yang ada pada

4

neighborhood. Sedangkan first best strategy adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini secara langsung jika solusi yang lebih baik ditemukan. Menurut Kusumadewi dan Purnomo (2005:132) algoritma Tabu Search secara garis besar dapat ditulis sebagai berikut: Langkah 0. Tetapkan: X = Matriks input berukuran m x n. MaxIter = maksimum iterasi. Langkah 1. S = bangkitkan solusi secara random Langkah 2. GlobalMin = FCost(S) Langkah 3. Best = S Langkah 4. TabuList = [ ] Langkah 5. Kerjakan dari k = l sampai MaxIter: Langkah 6. BestSoFar = FCost(S) Langkah 7. BestMove = S Langkah 8. Kerjakan dari i = l sampai(n - l): Langkah 9. Kerjakan dari j = i sampai n: Langkah 10. L = Tukar(S[i],S[j]). Langkah 11. Cost = FCost(L) Langkah 12. Jika(LTabuList)atau(Cost < GlobalMin), kerjakan: Langkah 13. Jika(Cost < BestSoFar), kerjakan Langkah 14. BestSoFar = Cost. Langkah 15. BestMove = L. Langkah 16. S = BestMove. Langkah 17. Tambahkan S ke TabuList Langkah 18. Jika BestSoFar < GlobalMin, kerjakan: Langkah 19. GlobalMin = BestSoFar. Langkah 20. Best = BestMove. Solusi akhir adalah Best, dengan cost sebesar GlobalMin.

4.2. Algoritma Genetika Algoritma genetika adalah algoritma pencarian yang didasarkan pada mekanisme seleksi ilmiah dan geentika alamiah. Pada awalnya algoritma genetika digunakan sebagai algoritma pencarian parameter-parameter optimal. Tetapi dalam pengembangannya, algoritma genetika bisa

5

diaplikasikan untuk berbagai masalah lain, seperti learning, peramalan, pemrograman otomatis, dan sebagainya. Pada bidang soft computing algoritma genetika banyak digunakan untuk mendapat nilai-nilai parameter pada jaringan syaraf tiruan maupun sistem fuzzy (Suyanto, 2011:205). Algoritma genetika banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan. Algoritma genetika dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimal dari satu variabel atau multi variabel. Sebelum algoritma ini dijalankan, masalah apa yang ingin dioptimalkan itu harus dinyatakan dalam fungsi tujuan, yang dikenal dengan fungsi fitness. Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. Walaupun kecil pada (karena awalnya algoritma semua ini

nilai fitness kemungkinan

sangat

menghasilkannya secara random), sebagian akan lebih tinggi dari yang lain. Kromosom dengan nilai fitness yang tinggi ini akan memberikan

probabilitas yang tinggi untuk bereproduksi pada generasi selanjutnya. Sehingga untuk setiap generasi pada proses evolusi, fungsi fitness yang mensimulasikan seleksi alam, akan menekan populasi kearah fitness yang meningkat Algoritma genetika memiliki beberapa komponen yaitu: 1. Representasi Kromosom 2. Prosedur Inisialisasi 3. Fungsi Evaluasi 4. Seleksi 5. Operator Genetika

6

6. Penentuan Parameter

4.3.Optimasi Menurut Kamus besar Bahasa Indonesia (2008:626) optimasi berarti menjadikan paling baik, menjadikan paling tinggi. Optimasi sangat berguna dalam rangka melakukan usaha secara efektif dan efisien untuk mencapai target atau hasil yang ingin dicapai. Tentunya hal ini akan sangat sesuai dengan prinsip ekonomi yang berorientasi menekan pengeluaran untuk menghasilkan output yang maksimal. Contoh bidang yang terbantu dengan adanya optimasi adalah arsitektur, data mining, jaringan komputer, pengolahan perdagangan, sebagainya. Langkah-langkah yang dilakukan dalam mencari optimasi yaitu: 1. Mengembangkan model dari masalah 2. Menentukan fungsi tujuan 3. Merumuskan kendala atau batasan sumber daya 4. Melakukan optimasi Dalam algoritma genetika, model dari permasalahan optimasi dapat direpresentasikan dalam bentuk biner, string, bit, pohon, array, bilangan real, aturan, elemen permutasi, elemen program, atau representasi yang lainnya (Kusumadewi, 2003: 280). Kemudian menggunakan parameter algoritma genetika untuk memperoleh solusi dari permasalahan yang ada. citra digital, telekomunikasi, perikanan, ekonomi, transportasi, dan

pertanian,

perkebunan,

kehutanan,

7

5. Tujuan Penelitian Tujuan penelitian yang dicapai: 1. Membandingkan efesiensi antara algoritma tabu search dan algoritma genetika dalam pencarian optimasi produksi makanan khas Bengkulu. 2. Membangun sebuah perangkat lunak algoritma tabu search algoritma genetika untuk mencari solusi optimal pada problem optimasi perusahaan makanan khas Bengkulu.

6. Manfaat Penelitian Manfaat penelitian yang dapat diambil adalah: 1. Manfaat ilmiah 1) Mengetahui algoritma mana yang lebih optimal antara algoritma tabu search atau algoritma algoritma genetika. 2) Meningkatkan pemahaman tentang algoritma tabu search dan algoritma algoritma genetika dalam mencari solusi optimal atas persoalan optimasi keuntungan perusahaan makanan khas Bengkulu. 2. Manfaat praktis Membantu perusahaan makanan khas Bengkulu (perusahaan ENDE) atas persoalan optimasi keuntungan perusahaan sehingga diperoleh kombinasi terbaik untuk jumlah dan jenis makanan yang diproduksi.

7. Metode Penelitian 7.1. Jenis Penelitian Penelitian yang akan dilakukan ini menggunakan metode

8

penelitian terapan karena tujuan penelitian ini adalah menerapkan metode genetika dan metode tabu search dalam menghasilkan suatu perangkat lunak yang dapat membantu dalam optimasi produksi perusahaan makanan khas Bengkulu. Penelitian terapan dilakukan dengan tujuan menerapkan, menguji, dan mengevaluasi kemampuan suatu teori yang diterapkan dalam memecahkan masalah-masalah praktis (Sugiyono, 2002:2). 7.2. Teknik Pengumpulan Data Teknik pengumpulan data yang digunakan dalam penelitian ini bersifat studi literatur dan studi lapangan, berikut keterangan tentang teknik pengumpulan data yang digunakan: 1. Studi literatur Studi literatur dilakukan dengan mempelajari literatur yang berhubungan dengan algoritma tabu search, algoritma genetika, DFD, dan pemrograman Matlab. 2. Studi lapangan Studi lapangan dilakukan dengan cara meneliti berapa jumlah kue yang terjual perharinya, ketersediaan bahan baku, biaya produksi, dan jenis makanan yang diproduksi.

7.3. Alat Bantu Pengembangan Sistem Alat bantu yang digunakan dalam penelitian ini adalah: 1. DFD (Data Flow Diagram) 2. Perangkat keras yang akan digunakan dalam penelitian ini adalah

9

satu unit laptop dengan spesifikasi: 1) 2) 3) Processor Memori Harddisk : Intel TM 2Duo CPU T5870 @ 2.00 GHz : 0.99 GB of RAM : 250 GB

3. Perangkat lunak yang akan digunakan adalah: 1) Windows XP Profesional 2) MATLAB 3) Microsoft Office Visio 2003 untuk perancangan DFD dan form aplikasi.

8. Jadwal Pelaksanaan Pembuatan tugas akhir ini terhitung dari bulan Juni sampai November 2011. Berikut tabel rincian pengerjaan tugas akhir yang berjudul Perbandingan Algoritma Tabu Search dan Algoritma Genetika Pada Optimasi Produksi Perusahaan Makanan Khas Bengkulu. Tabel 1. Rincian Kegiatan Pengerjaan Tugas AkhirNo 1. 2. 3. Kegiatan Pembuatan proposal Seminar proposal Memahami dan menganalisa proses produksi Desain aplikasi secara umum Desain aplikasi secara terperinci Mendesain pengkodean aplikasi Penyelesaian program Juni Juli Agustus September Oktober November

4. 5. 6. 7.

10

8.

Penyelesaian laporan

11

DAFTAR PUSTAKA

Kusumadewi, Sri., Purnomo, Hari. 2005. Penyelesaian Masalah dengan Teknikteknik Heuristik. Yogyakarta: Graha Ilmu. Kusumadewi, Sri. 2003. Artificial Yogyakarta: Graha Ilmu. Intelligence (Teknik & Aplikasinya).

Mardalis. 2009. Metode Penelitian Suatu Pendekatan Proposal. Jakarta: Bumi Aksara. Pusat Bahasa. 2008. Kamus Besar Bahasa Indonesia. Jakarta: Gramedia Pustaka Utama. Sahid. 2005. Pengantar Komputasi Numerik dengan Matlab. Yogyakarta: Andi. Sugiyono. 2009. Motode Penelitian Kuantitatif dan Kualitatif dan R&D. Bandung: Alfabeta. Suyanto. 2011. Artificial Intelligence. Bandung: Informatika.

12