0

Contoh Penelitian Teknik Informatika (5)

Perbandingan Algoritma A* dan Algoritma Simplified Memory-Bounded A* (SMA*) dalam Penentuan Rute Pendistribusian Ice Cream Walls di Kota Bengkulu.

Disusun Oleh:

Zefy Arlinda

1. Pendahuluan

Pendistribusian hasil produksi merupakan hal yang sangat penting bagi perusahaan. Jalur pendistribusian yang dipilih hendaknya merupakan jalur terpendek yang dapat ditempuh. Jalur pendistribusian terpendek dapat menghemat anggaran dana perjalanan dan mempercepat waktu pendistribusian. Itulah mengapa ketepatan memilih jalur pendistribusian merupakan sesuatu yang harus diperhitungkan dengan baik. Begitu juga halnya dengan pendistribusian ice cream pada perusahaan Ice Cream Walls cabang Kota Bengkulu.

Pemilihan jalur pendistribusian terpendek dapat dibantu dengan menggunakan metode pencarian. Terdapat banyak metode pencarian yang telah diusulkan. Semua metode yang ada dibedakan menjadi dua jenis: pencarian buta atau tanpa informasi (blind atau un-informed search) dan pencaria heuristik atau dengan informasi (heuristic atau informed search). Metode-metode yang termasuk ke dalam teknik pencarian yang berdasarkan pada fungsi heuristik adalah: Generate and Test, Hill Climbing (Simple Hill Climbing  dan  Step-Ascent Hill Climbing), A*, Simplified Memory-Bounded A* (SMA*), dan Iterative Deepending A* (IDA*).

Algoritma A* (A Star) dapat menentukan rute terpendek dengan proses optimalisasi sehingga rute yang didapatkan merupakan rute yang optimum. Dalam notasi matematika dituliskan:

f(n) = g(n) + h(n).

Pada Algoritma SMA* terdapat sebuah senarai queue yang digunakan untuk memanipulasi antrian simpul yang terurut berdasarkan f-cost,  disini yang dimaksud f-cost adalah gabungan biaya sebenarnya dan biaya perkiraan, yang secara matematika dinyatakan seperti notasi pada A* tetapi mengalami sedikit modifikasi yaitu f-cost=g(n) + h(n).

Adanya perbedaan algoritma A* dan algoritma Simplified Memory-Bounded A*  dalam menyelesaikan masalah membuat penulis tertarik untuk membandingkan keduanya. Membandingkan algoritma A* dan algoritma Simplified Memory-Bounded A* dalam kasus pencarian jalur terpendek pendistribusian Ice Cream Walls di Kota Bengkulu.

2. Perumusan Masalah

Rumusan masalah dalam penelitian ini adalah:

  1. Algoritma manakah yang lebih optimal antara algoritma A* dan Algoritma Simplified Memory-Bounded A* (SMA*) dalam mencari jalur terpendek pendistribusian Ice Cream Walls di Kota Bengkulu ditinjau dari jarak, jumlah iterasi dan rute pendistribusian?
  2. Bagaimana mengimplementasikan algoritma A* dan algoritma Simplified Memory-Bounded A* (SMA*) dalam mencari jalur terpendek pendistribusian Ice Cream Walls di Kota 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 A* dan Simplified Memory-Bounded A*  (SMA*) berdasarkan variabel jarak, jumlah iterasi dan rute pendistribusian.
  2. Aplikasi ini akan dibangun menggunakan bahasa pemrograman MATLAB.
  3. Model perancangan yang digunakan untuk menganalisis dan mendesain aplikasi ini adalah model perancangan Data Flow Diagram (DFD).

4. Tujuan Penelitian

Tujuan penelitian yang dicapai:

  1. Membandingkan efesiensi antara algoritma A* dan algoritma Simplified Memory-Bounded A* (SMA*)  dalam pencarian jalur terpendek.
  2. Membangun sebuah perangkat lunak algoritma A* dan algoritma Simplified      Memory-Bounded A* (SMA*) untuk mencari jalur terpendek untuk pendistribusian    Ice Cream Walls di Kota Bengkulu

5. Manfaat Penelitian

Manfaat penelitian yang dapat diambil adalah:

  1. Manfaat ilmiah
    • Mengetahui algoritma mana yang lebih optimal antara algoritma A* dan algoritma Simplified Memory-Bounded A* (SMA*).
    • Meningkatkan pemahaman tentang algoritma A* dan algoritma Simplified Memory-Bounded A* (SMA*) dalam pencarian jalur terpendek.

2.  Manfaat Praktis

Membantu perusahaan Ice Cream Walls atas persoalan pencarian jalur terpendek pendistribusian produk di Kota Bengkulu.

Advertisements
0

Contoh Penelitian Teknik Informatika (1)

PERBANDINGAN ALGORITMA GENETIKA STEADY-STATE DAN GENERATIONAL REPLACEMENT PADA OPTIMASI PRODUKSI MAKANAN KHAS BENGKULU

(Studi Kasus: Optimasi Produksi Makanan Khas Bengkulu di Perusahaan ENDE)

Oleh: Zefy Arlinda

BAB I

PENDAHULUAN

 

1.1.            Latar Belakang

Sejak dahulu masyarakat Indonesia telah memiliki makanan khas yang paling cocok dengan kondisi daerah serta menjadi kebiasaan makan daerah tertentu. Perbedaan selera akan makanan membuat setiap daerah memiliki makanan khas masing-masing. Dalam perkembangannya, makanan tradisional atau khas suatu daerah tidak hanya menjadi makanan sehari-hari tetapi juga menjadi aset industri makanan dan wisata yang tidak dapat diabaikan, industri pariwisata belum lengkap tanpa adanya kuliner khas daerah yang disajikan di tempat wisata tujuan. Para wisatawan yang  berkunjung ke suatu daerah tentu saja akan mencari makanan khas daerah wisata tersebut. Hal ini memicu tumbuhnya industri-industri makanan khas daerah, termasuk di Bengkulu. Beberapa 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.

Ternyata makanan khas Bengkulu tidak hanya diminati oleh warga Bengkulu dan wisatawan yang datang ke Bengkulu  tetapi juga masyarakat luar negeri. Makanan khas Bengkulu produksi ENDE telah mendapat pesananan dari negeri China (http://www.langitperempuan.com/2008/10/agar-tidak-punah-kue-kue-khas-bengkulu-dibuat-renyah-dikunyah/). Pesanan yang datang dari negeri jauh ini merupakan sinyal, bahwa industri makanan khas Bengkulu memiliki masa depan yang menjanjikan untuk digarap dengan serius. Permintaan konsumen yang bervariasi dan adanya kompetitor membuat perusahaan harus mengoptimalkan produksi. Perusahaan harus kreatif dan mengerti keinginan pasar. Perusahaan harus bisa menentukan jumlah dan jenis makanan yang diproduksi sehingga dapat memaksimalkan keuntungan.

Permasalahan optimasi keuntungan 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 genetika merupakan algoritma yang dapat digunakan untuk membantu optimasi. Algoritma genetika adalah algoritma pencarian yang berdasarkan pada mekanisme sistem natural yakni genetik dan seleksi alam. Terdapat dua variasi algoritma genetika, yaitu: Steady State dan Generational Replacement. Pada algoritma genetika yang berjenis Stedy State, proses replacement dilakukan setiap kali dihasilkan dua offspring hasil crossover. Offspring menggantikan kromosom yang nilai fitness-nya paling kecil. Dengan demikian, populasi baru yang dihasilkan selalu memiliki individu-individu yang lebih baik dibandingkan populasi lama (Suyanto, 2011:207).

Adanya perbedaan algoritma genetika Steady State dan Generational Replacement dalam menyelesaikan masalah membuat penulis tertarik untuk membandingkan keduanya.  Membandingkan algoritma genetika Steady State dan Generational Replacement dalam kasus optimasi produksi makanan khas Bengkulu.

Penelitian terkait mengenai algoritma genetika ini adalah penelitian yang dikembangkan oleh Flora Apriani Jurusan Teknik Informatika, Universitas Bengkulu Tahun 2009 yang berjudul IMPLEMENTASI ALGORITMA GENETIKA PADA OPTIMASI PRODUKSI PERUSAHAAN ROTI. Sistem ini dibuat untuk mencari solusi optimal atas proses produksi perusahaan Surya Bakery. Aplikasi ini dibuat menggunakan MATLAB 7.0.1 dan metode pengembangan yang digunakan adalah UML (Unified Modeling Language). Algoritma genetika yang digunakan pada aplikasi ini masih secara umum, belum dijelaskan spesifikasi algoritma yang digunakan.

1.2.            Rumusan Masalah

Berdasarkan uraian pada latar belakang di atas, maka rumusan masalah dalam penelitian ini adalah:

  1. Bagaimana perbandingan antara Algoritma Genetika Steady State dan Generational Replacement dalam mencari solusi optimal pada masalah optimasi produksi makanan khas Bengkulu?
  2. Bagaimana mengimplementasikan Algoritma Genetika Steady State dan Generational Replacement dalam mencari solusi optimal pada problem optimasi perusahaan makanan khas Bengkulu dengan menggunakan MATLAB 7.12.0?

1.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 Algoritma Genetika Steady State dan Generational Replacement berdasarkan variabel ketersediaan bahan baku, jumlah pemakaian bahan, keuntungan satuan kotak makanan, dan jenis makanan yang diproduksi oleh perusahaan ENDE.
  2. Model perancangan yang digunakan untuk menganalisis dan mendesain aplikasi ini adalah model perancangan Data Flow Diagram (DFD).

1.4.            Tujuan

Berdasarkan latar belakang di atas tujuan penelitian ini adalah:

  1. Mengetahui perbandingan antara Algoritma Genetika Steady State dan Generational Replacement dalam pencarian solusi optimal pada masalah optimasi produksi makanan khas Bengkulu.
  2. Mengimplementasikan Algoritma Genetika Steady State dan Generational Replacement dalam mencari solusi optimal pada problem optimasi perusahaan makanan khas Bengkulu dengan menggunakan MATLAB 7.12.0.

1.5.            Manfaat

Manfaat penelitian yang dapat diambil adalah:

  1. Manfaat ilmiah

1)      Mengetahui algoritma mana yang lebih optimal antara Algoritma Genetika Steady State dan Generational Replacement.

2)      Meningkatkan pemahaman tentang Algoritma Genetika Steady State dan Generational Replacement dalam mencari solusi optimal atas persoalan optimasi produksi perusahaan makanan khas Bengkulu.

2. Manfaat praktis

Membantu perusahaan makanan khas Bengkulu (perusahaan ENDE) atas persoalan optimasi produksi perusahaan sehingga diperoleh kombinasi terbaik untuk jumlah dan jenis makanan yang diproduksi.

…………………….btw, maaf ya tulisannya kurang rapi, gara-gara jarang ngeblog di sini banyak fitur yang hilang heheheeee………………..

2

Algoritma LCS dan Teman-teman

Si Longest Common Subsequence (LCS) dan teman-teman memang berhasil buat kepala muter-muter whehehe,, LCS dan teman-teman menambah asik mata kuliah Desain Analisis dan Algoritma ^________^,, sebenarnya jika dipelajari benar-benar kita bisa paham sih, dasar saya yang malas kali ya -_-. Padahal Dosen dah Ngasi buku Introduction to Algorithms (karangan om Thomas H. Cormen dkk) trus teman dah ngasi buku kunci jawaban buku om Thomas H. Cormen. Berikut contoh lcs di buku om cormen, silahkan download bukunya, semoga kalian bisa lebih memahami si LCS dan teman-teman. Berikut salah satu contoh yang ada di buku om cormen.

lcs

lcs

Algoritma menghitung panjang LCS

LCS-Length(X,Y)

1.   m ß length [X]

2.   n ß length [Y]

3.   For iß1 to m do c[i,0] ß 0

4.   For j ß 0 to n do

5.   c[0,j] ß 0

6.   For i ß 1 to m do

7.          for j ß 1 to n do

8.                if xi = yj then c[i,j] ß c[i-1,j-1]+1

9.                                       b[i,j]ß “  ã   “

10.                                                else if  c[i-1, j]   ≥ c[i, j-1]

11.                                                         then  b[i, j] ß “ á”

12.                                                         else c[i, j] ← c[ i, j-1]

13.                                                                 b[I,j] ß “ ← “

14.                     Return c  and b

 

Download:

Buku Introduction to Algoritma by Thomas H. Cormen

Buku penyelesaian soal-soal yang ada di buku Introduction to Algoritma by Thomas H. Cormen