ALGORITMA PARTICLE SWARM OPTIMIZATION DAN TERAPANNYA DALAM MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS MAKALAH

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ALGORITMA PARTICLE SWARM OPTIMIZATION DAN TERAPANNYA DALAM MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS

MAKALAH

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun oleh: Helvetika Amperiana NIM: 123114009

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2017


ALGORITMA PARTICLE SWARM OPTIMIZATION DAN TERAPANNYA DALAM MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS

MAKALAH

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun oleh: Helvetika Amperiana NIM: 123114009

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2017 i


PARTICLE SWARM OPTIMIZATION ALGORITHM AND ITS APPLICATION IN SOLVING CUTTING PAPER ROLL PROBLEM

A PAPER

Presented as a Partial Fulfillment of the Requirements to Obtain the Degree of Sarjana Sains Mathematics Study Program

Written by: Helvetika Amperiana Student ID: 123114009

MATHEMATICS STUDY PROGRAM DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2017 ii


MAKALAH

ALGORITMA PARTICLE S WARM O PTIMIZATTON DAN TERAPANNYA DALAM MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS

Sisusun oleh: Narna. F{elv*tika Ampcriana

NIM: 123114**9

Telah dis*f*jui *l*h:

Ilasen pembimbing makal ah

Tanggzil: 31 Ja:ruari 2017

iii



HALAMAN PERSEMBAHAN

Maka.. Ingat selalu bahwa berkat dan karunia berbanding lurus dengan tanggung jawab dan itu semua hanya dapat disempurnakan oleh Kasih.

Tugas akhir ini saya persembahkan untuk orang tua saya tercinta, Ir. Yugianto dan Ho’ing Buddy Serta adik saya terkasih, Febriano Ampera Putra

v



ABSTRAK Algoritma Particle Swarm Optimization (PSO) merupakan salah satu algoritma optimasi dengan teknik pendekatan heuristik. Pendekatan haeuristik yaitu pendekatan komputasi untuk mencari suatu penyelesaian optimal atau mendekati optimal dari suatu masalah optimasi dengan cara mencoba secara iteratif untuk memperbaiki kandidat solusi dengan memperhatikan batasan kualitas solusi yang diinginkan. Algoritma PSO terinspirasi dari perilaku sekawanan burung atau sekumpulan ikan yang dapat menjelajah ruang solusi secara efektif sehingga mempunyai keefektifan yang baik dalam menyelesaikan masalah. Makalah ini mengimplementasikan algoritma PSO untuk menyelesaikan masalah pemotongan persediaan kertas, yaitu pada rol kertas jumbo yang akan dipotong untuk mendapatkan rol kertas kecil. Lebar rol kertas kecil ditentukan oleh permintaan pelanggan dan jumlah rol yang dipesan juga berbeda-beda. Tujuannya adalah mencari dan menyusun pola pemotongan dari sebuah rol jumbo menjadi rol kecil sedemikian hingga diperoleh hasil yang optimum. Berdasarkan hasil penelitian ini, diperoleh solusi optimal yaitu jumlah rol jumbo dan sisa yang minimum untuk beberapa kasus pesanan yang masuk. Selanjutnya dibuat suatu program tampilan dengan MATLAB berdasarkan algoritma PSO. Dibandingkan dengan perhitungan software Quantitative Method (QM), yaitu software yang populer digunakan untuk memproses data kuantitatif, hasilnya cukup mendekati. Kata kunci: Algoritma Particle Swarm Optimization (PSO), masalah pemotongan persediaan, program linear

vii


ABSTRACT Particle Swarm Optimization (PSO) algorithm is an optimization algorithm classified as a heuristic approach technique. It seeks an optimal solution or almost optimal in iterative manner. The candidate for solutions are improved iteratively with regards to the quality of the desired solution. PSO algorithm is inspired by the behavior of a flock of birds or school of fish that can explore the solution space effectively so have a good effectiveness in solving the problems. This paper implements the PSO algorithm to solve the problem of cutting paper supplies. Jumbo paper rolls are cut in to smaller paper rolls which widths are determined by customer demand. The number of rolls are also varied. The goal is to find and develop cutting pattern of jumbo rolls into small rolls so that optimum results are obtained. Based on PSO algorithms written in MATLAB, the optimal solution is obtained which minimizes the use of the number of jumbo rolls for some cases of incoming orders. Compared to the results produced by optimization software QM (Quantitative Methods), the result is quite accurate. Paper industry produces jumbo paper rolls by using a paper machine. The Keywords: Particle Swarm Optimization (PSO) algorithm, cutting stock problem, paper roll, linear programming.

viii




DAFTAR ISI

HALAMAN PERSEMBAHAN ....................................................................................... v

PERNYATAAN KEASLIAN KARYA .....................................................................vi ABSTRAK.....................................................................................................................vii ABSTRACT .................................................................................................................viii LEMBAR PERNYATAAN PERSETUJUAN .........................................................vii KATA PENGANTAR .................................................................................................. x DAFTAR ISI ..................................................................................................................xi BAB I PENDAHULUAN ............................................................................................ 1 A. Latar Belakang Masalah ............................................................................... 1 B. Rumusan Masalah ........................................................................................ 6 C. Pembatasan Masalah .................................................................................... 6 D. Tujuan Penulisan .......................................................................................... 7 E. Manfaat Penulisan ........................................................................................ 7 F.

Metode Penulisan ......................................................................................... 7

G.

Sistematika Penulisan .......................................................................................... 7

BAB II LANDASAN TEORI .................................................................................... 10 A. Program Linear........................................................................................... 10 B. Program Linear Bilangan Bulat ................................................................. 11 C. Masalah Knapsack ..................................................................................... 16 D. Algoritma Particle Swarm Optimization (PSO) ........................................ 29 BAB III MASALAH PEMOTONGAN PERSEDIAAN ....................................... 54 A. Masalah Pemotongan Persediaan (Cutting Stock Problem) ....................... 54 B. Algoritma PSO Sebagai Pendekatan untuk Pencarian Solusi Optimal CSP 60 BAB IV PENERAPAN ALGORITMA PARTICLE SWARM OPTIMIZATION UNTUK MASALAH PEMOTONGAN ROL KERTAS ............................ 69 BAB V PENUTUP ...................................................................................................... 76 A. Kesimpulan ................................................................................................ 76 B. Saran ........................................................................................................... 77 DAFTAR PUSTAKA ................................................................................................. 78

xi


LAMPIRAN ................................................................................................................. 80

xii


BAB I PENDAHULUAN

A.

Latar Belakang Masalah Metode heuristik adalah suatu teknik aproksimasi atau pendekatan yang

didesain untuk memecahkan masalah optimasi dengan cara mencoba secara iteratif sebagai upaya memperbaiki kandidat solusi dengan memperhatikan batasan kualitas solusi yang diinginkan dengan mengutamakan waktu komputasi dan biasanya menghasilkan solusi yang cukup baik, dalam arti optimal atau mendekati optimal. Metode ini dapat mencari solusi dalam ruang pencarian (search space) yang besar dengan cara memadukan interaksi antara prosedur pencarian lokal dan melakukan pencarian di ruang solusi untuk menemukan solusi global. Selain itu, ada prosedur yang memanfaatkan satu atau lebih titik-titik tetangga (neighborhood structures) sebagai acuan menuju solusi lain. Karena metode ini dapat menghasilkan solusi yang cukup baik dalam memecahkan permasalahan kombinatorial dengan skala yang cukup besar dan waktu komputasi yang relatif cepat, maka metode ini muncul sebagai alternatif yang dapat beradaptasi dengan baik untuk kasus-kasus sulit dalam konteks industri dan telah mencatatkan sejarah sukses. Langkah-langkah dari metode ini menggunakan algoritma optimasi yang diadaptasi dari Swarm Intelligence. Algoritma optimasi yang termasuk ke dalam kelas Swarm Intelligence (SI) diantaranya adalah: Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Artificial Bee Colony Algorithm (ABC),

1

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 2

Cat Swarm Optimization (CSO), dan lain-lain. Akan tetapi, yang akan dibahas disini adalah Algoritma Particle Swarm Optimization (PSO) sebagaimana diterapkan dalam penelitian ini dengan tujuan untuk mencapai solusi yang optimal bagi masalah pemotongan kertas. Particle Swarm Optimization (PSO) diperkenalkan pertama kali oleh James Kennedy (seorang psikolog sosial) dan Russell Eberhart (seorang insinyur elektro) pada tahun 1995, PSO berasal dari simulasi perilaku kawanan burung. Meskipun sejumlah ilmuwan telah menciptakan simulasi komputer tentang berbagai penafsiran dari gerakan organisme pada kawanan burung atau gerombolan ikan, Kennedy dan Eberhart hanya tertarik pada model yang dikembangkan oleh Heppner (ahli zoologi). Dalam model Heppner ini, burung akan mulai dengan beterbangan di sekitar tanpa tujuan tertentu dan membentuk kawanan secara spontan sampai salah satu burung terbang di atas wilayah yang akan dijadikan tempat bersarang. Bagi Eberhart dan Kennedy, menemukan sebuah tempat bersarang analog dengan menemukan solusi yang baik pada bidang penyelesaian yang memungkinkan. Mereka juga merevisi metodologi Heppner sehingga partikel (individu) akan terbang di atas ruang solusi dan mencoba untuk menemukan solusi terbaik menurut penemuan mereka sendiri dan pengalaman masa lalu dari tetangga mereka. Kita bisa mengutip beberapa karya yang berhasil menggunakan metode ini seperti masalah pemotongan berdasarkan pola oleh Ghassen Ben Lagha dan Xianjun Shen dkk. Dalam makalah ini, saya memberikan rumusan matematika untuk masalah pemotongan persediaan yang berperan dalam mengambil pertimbangan pada saat


hendak melakukan proses pemotongan kertas dalam rangka untuk memenuhi semua pesanan dari konsumen. Berikut diagram alir dari pencarian solusi masalah pemotongan rol kertas dengan algoritma PSO. 1. Mengurutkan lebar roll kecil dari terbesar sampai terkecil. (data)

2. Menentukan pola kertas. (kendala)

pemotongan

3. Mengoperasikan algoritma PSO sesuai dengan data dan kendala agar nilai optimal dari fungsi objektif tercapai. Gambar 1.1: Diagram alir pencarian solusi masalah pemotongan rol kertas dengan algoritma PSO

Pada makalah ini masalah pemotongan rol kertas dibatasi hanya pada pemotongan dari rol ke rol yang berarti hanya untuk pemotongan dari rol jumbo menjadi rol-rol kecil dan dengan pola pemotongan satu dimensi. Selebihnya makalah ini mengandung bagian-bagian sebagai berikut: Bagian pertama menyatakan formulasi matematis dan menjelaskan bagaimana mengatasi masalahnya. Bagian kedua yaitu pendekatan dengan algoritma PSO dan fiturfiturnya. Bagian ketiga akan melaporkan penyelidikan eksperimental. Bagian keempat menyajikan penerapan algoritma PSO yang dapat digunakan secara


langsung untuk menyelesaikan masalah pemotongan kertas satu dimensi (dari rol ke rol) menggunakan GUI yang dibuat dengan menggunakan MATLAB. Dan bagian terakhir berisi kesimpulan dan saran. Seperti yang sudah disinggung sebelumnya, akan dibahas algoritma PSO sebagai salah satu metode heuristik yang dapat memecahkan permasalahan kombinatorial dengan skala yang cukup besar. Salah satu masalah kombinatorial yang dihadapi sejak masa revolusi industri yang berjaya pada abad terakhir, adalah masalah pemotongan persediaan atau Cutting Stock Problem (CSP) maupun masalah pengurangan sisa atau Trim Loss Problem (TLP). Masalah pemotongan persediaan atau Cutting Stock Problem (CSP) biasanya berkaitan dengan meminimumkan biaya produksi untuk mencapai pemakaian bahan baku yang optimal. Salah satu cara yang ditempuh untuk dapat meminimumkan biaya produksi adalah dengan memproduksi jumlah rol yang sesuai dengan pesanan. Sedangkan untuk masalah pengurangan sisa atau Trim Loss Problem (TLP) biasanya terjadi karena pola pemotongan yang digunakan kurang tepat sehingga mengakibatkan ketidakefisienan pemakaian bahan baku. Oleh karena itu, memproduksi jumlah rol yang optimal dan pola pemotongan yang tepat akan memberi pengaruh yang signifikan dalam hal meminimumkan biaya produksi meskipun sisa pemotongan kertas dapat didaur ulang, diproduksi menjadi produk lain, dan dimasukkan ke dalam penyimpanan. Efisiensi akan meningkat jika produksi jumlah rol semakin sedikit dan sesuai dengan kebutuhan serta pola pemotongan yang dihasilkan semakin baik dan akurat.


Sebelum rol jumbo dipotong menjadi potongan kertas atau rol kecil, maka harus diperhitungan berbagai macam kemungkinan pola pemotongan dari rol jumbo tersebut yang kemudian akan dipilih yang paling optimal. Pola tersebut berupa gabungan dari beberapa ukuran kertas atau rol yang diinginkan konsumen. Pembentukan pola tersebut juga harus memperhatikan beberapa kendala agar didapat hasil yang optimal. Dalam 1 rol jumbo yang akan dipotong menjadi rol-rol kecil haruslah memuat pesanan dengan diameter rol, panjang rol, jenis kertas, warna kertas, dan berat yang sama. Terdapat banyak metode untuk menyelesaikan masalah tersebut salah satunya dengan program linear. Secara umum, masalah program linear dapat dirumuskan sebagai berikut: Maksimumkan atau minimumkan 𝒛 = 𝒄𝒙 Dengan kendala ≤ 𝑨𝒙 {=} 𝒃 ≥ 𝒙≥𝟎 dengan 𝒙 = (𝑥1 , 𝑥2 , … , 𝑥𝑛+𝑚 𝑏1 dan 𝒃 = [ ⋮ ]. 𝑏𝑚

)𝑇

𝑎11 , 𝒄 = (𝑐1 , 𝑐2 , … , 𝑐𝑛+𝑚 ), 𝑨 = [ ⋮ 𝑎𝑚1

⋯ 𝑎1,𝑛+𝑚 ⋱ ⋮ ], ⋯ 𝑎𝑚,𝑛+𝑚


Dalam mencari penyelesaian program linear, metode yang sering digunakan adalah metode simpleks. Ketika masalah tersebut diaplikasikan dalam dunia industri, dapat dipastikan bahwa akan dilibatkan data dalam jumlah besar sebagai masukan. Semakin besar masalah ukuran ini, semakin banyak penyelesaian dan proses mengoptimumkan menjadi lebih sulit. Oleh karena itu, selain metode simpleks, terdapat metode yang juga dapat digunakan untuk menyelesaikan masalah di atas yaitu metode heuristik.

B.

Rumusan Masalah Berdasarkan latar belakang tersebut, secara garis besar uraian rumusan

masalah yang dibahas dalam makalah ini adalah: a. Bagaimana memodelkan masalah pemotongan kertas agar didapat solusi yang optimal? b. Bagaimana

menyelesaikan

masalah

pemotongan

kertas

dengan

masalah

pemotongan

kertas

dengan

menggunakan algoritma PSO? c. Bagaimana

menyelesaikan

menggunakan MATLAB?

C.

Pembatasan Masalah Agar penulisan dan pembahasan isi menjadi lebih terarah dan tidak

menyimpang dari masalah yang dibahas maka dalam penulisan makalah ini dibatasi, yaitu pemotongan kertas dari rol jumbo menjadi pesanan rol kecil dengan pola pemotongan satu dimensi.


D.

Tujuan Penulisan Tujuan yang ingin dicapai penulis dalam penulisan makalah ini selain untuk

memenuhi syarat makalah dalam program studi Matematika Universitas Sanata Dharma, yaitu sebagai berikut. a. Memodelkan masalah pemotongan kertas. b. Menyelesaikan masalah pemotongan kertas dengan algoritma PSO. c. Menyelesaikan masalah pemotongan kertas dengan aplikasi MATLAB.

E.

Manfaat Penulisan Manfaat penulisan dari makalah ini adalah: a. Dapat memodelkan dan mengaplikasikan program linear dalam masalah pemotongan kertas. b. Dapat membantu berbagai pihak untuk menentukan pola pemotongan kertas yang optimal.

F.

Metode Penulisan Metode yang digunakan penulis dalam penyusunan makalah yaitu studi

pustaka, yaitu dengan mempelajari buku atau jurnal yang berkaitan dengan masalah pemotongan persediaan (cutting stock problem).

G.

Sistematika Penulisan

BAB I. PENDAHULUAN A. Latar Belakang Masalah


B. Perumusan Masalah C. Pembatasan Masalah D. Tujuan Penulisan E. Manfaat Penulisan F. Metode Penulisan G. Sistematika Penulisan

BAB II. PROGRAM LINEAR DAN METODE HEURISTIK A. Program Linear B. Program Linear Bilangan Bulat C. Masalah Knapsack D. Algoritma Particle Swarm Optimization (PSO)

BAB III. MASALAH PEMOTONGAN PERSEDIAAN A. Masalah Pemotongan Persediaan (Cutting Stock Problem) B. Pencarian Solusi Optimal dengan Algoritma PSO

BAB IV. PENERAPAN ALGORITMA PSO UNTUK MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS

BAB V. PENUTUP A. Kesimpulan B. Saran


DAFTAR PUSTAKA LAMPIRAN


BAB II LANDASAN TEORI

A.

Program Linear Program linear adalah sebuah metode matematis yang berkarakteristik

linear untuk menemukan suatu penyelesaian optimal dengan cara memaksimumkan atau meminimumkan fungsi obyektif atau tujuan terhadap suatu susunan kendala. Istilah program linear secara eksplisit telah menunjukkan karakteristiknya. Model matematika harus berupa fungsi linear dan penyelesaian optimal diturunkan melalui teknik optimasi linear. Bentuk baku model matematis program linear dapat dilihat: Fungsi obyektif/tujuan: Maksimumkan/minimumkan 𝑧 = ∑𝑛𝑗=1 𝑐𝑗 𝑥𝑗 Terhadap fungsi kendala-kendala 𝑛

≤ ∑ 𝑎𝑖𝑗 𝑥𝑗 {=} 𝑏𝑖 ≥ 𝑗=1

(2.1)

𝑥𝑗 ≥ 0 dengan

𝑥𝑗 : Variabel keputusan ke-j 𝑐𝑗 : Parameter fungsi tujuan ke-j 𝑏𝑖 : Kapasitas kendala ke-i 𝑎𝑖𝑗 : Parameter fungsi tujuan ke-i untuk variabel keputusan ke-j 𝑖 ∶ 1, 2, … , 𝑚 𝑗 ∶ 1, 2, … , 𝑛

10


dengan setiap pertidaksamaan yang memiliki simbol, ≤, ≥, =, hanya dipilih salah satu. Fungsi obyektif atau fungsi tujuan disebut juga fungsi linear. Dengan 𝑎𝑖𝑗 disebut koefisien teknis, 𝑐𝑗 disebut koefisien ongkos, dan 𝑏𝑖 disebut suku tetap di ruas kanan disingkat “suku tetap” atau “ruas kanan”. Jika 𝑥𝑗 , 𝑗 = 1, … , 𝑛 memenuhi semua kendala, maka disebut penyelesaian layak. Penyelesaian layak yang juga mengoptimumkan 𝑧 disebut penyelesaian optimum. Setiap masalah minimum dapat dilihat seperti masalah maksimum dan sebaliknya. Ini dapat terlihat dari pengamatan berikut 𝑛

𝑛

(2.2)

𝑚𝑖𝑛 ∑ 𝑐𝑗 𝑥𝑗 = −𝑚𝑎𝑥⁡(− ∑ 𝑐𝑗 𝑥𝑗 ) 𝑗=1

𝑗=1

Itu berarti untuk meminimumkan fungsi tujuan kita dapat memaksimumkan negatif dari fungsi tujuannya kemudian menegatifkan lagi hasil maksimumnya. Solusi yang digunakan untuk menyelesaikan masalah program linear yaitu dengan metode grafik dan metode simpleks. Metode grafik digunakan untuk memecahkan persoalan model program linear dua variabel. Lalu pada tahun 1947 G. Dantzig mengembangkan metode yang dapat memecahkan persoalan model program linear dengan lebih dari dua variabel yang disebut metode simpleks. Namun kedua metode tersebut tidak akan dibahas di sini.

B.

Program Linear Bilangan Bulat Penyelesaian kasus masalah program linear dapat menghasilkan nilai optimal

berupa bilangan pecahan. Padahal dalam kasus di dunia nyata penyelesaian masalah harus berupa bilangan bulat terutama apabila variabel-variabel keputusannya


mewakili item yang utuh dan tidak dapat dipecah seperti pada: masalah Knapsack dan masalah pemotongan persediaan. Program linear bilangan bulat adalah sebuah model penyelesaian matematis yang memungkinkan solusi masalah program linear yang berupa bilangan pecahan diubah menjadi bilangan bulat tanpa meninggalkan optimalitas penyelesaian. Program linear bilangan bulat secara umum terbagi menjadi 3 jenis yaitu program linear bilangan bulat murni (pure), program linear bilangan bulat campuran (mixed), dan program linear bilangan bulat 0-1 (binary). Program linear bilangan bulat murni terjadi apabila semua variabel dalam solusi optimal merupakan bilangan bulat. Sedangkan program linear bilangan bulat campuran terjadi apabila variabelnya ada yang bukan bilangan bulat. Selanjutnya untuk program linear bilangan bulat 0-1 (biner) secara khusus mensyaratkan agar semua variabel dalam solusi optimal harus merupakan bilangan bulat bernilai 0 atau 1. Untuk masalah program linear bilangan bulat yang kasusnya besar, metode yang biasa digunakan yaitu metode pemotongan bidang (Cutting Plane), dan metode cabang dan batas (Branch and Bound). Namun disini hanya akan dibahas metode cabang dan batas untuk penyelesaian masalah program linear bilangan bulat.

Metode Pencabangan dan Pembatasan (Branch and Bound Method) Metode cabang dan batas adalah suatu metode yang sangat sederhana namun sering digunakan untuk menyelesaikan masalah program linear bilangan bulat


(integer). Metode ini diusulkan pertama kali oleh A. H. Land dan A. G. Doig pada tahun 1960. Metode ini secara umum dimulai dengan mencari solusi masalah program linear tanpa menambahkan syarat bahwa penyelesaian optimalnya harus berupa bilangan bulat. 1. Jika secara kebetulan penyelesaian optimal yang didapat berupa bilangan bulat, maka penyelesaian ini juga merupakan penyelesaian masalah program linear bulatnya. 2. Jika penyelesaian yang didapat bukan bilangan bulat, maka selanjutnya kendala baru yang membatasi nilai salah satu variabel yang tidak bulat ditambahkan. 3. Penambahan ini mengakibatkan terbaginya daerah layak menjadi 2 bagian sehingga terbentuklah 2 sub-masalah baru yang kemudian harus diselesaikan. Dengan kata lain, terjadi pencabangan dari masalah aslinya menjadi 2 sub-masalah baru. 4. Batas untuk nilai fungsi obyektif atau fungsi tujuan kemudian dapat ditentukan. Batas ini dapat digunakan untuk mengeliminasi sub-masalah yang tidak diperlukan dan menentukan apakah penyelesaian optimalnya sudah tercapai. 5. Jika penyelesaian yang didapat belum optimal, maka sub-masalah baru dipilih dan proses pencabangan berlanjut. Untuk lebih jelasnya, metode ini bekerja sebagai berikut. Metode ini diawali dengan mencari penyelesaian optimal bagi masalah program linear biasa. Jadi


syarat bahwa nilai dari variabel-variabelnya harus berupa bilangan bulat diabaikan untuk sementara. Apabila dalam penyelesaian ini diperoleh variabel-variabel yang tidak bulat, katakanlah 𝑥𝑖 maka pasti dapat ditemukan dua bilangan bulat tak negatif 𝑛 dan 𝑛 + 1 sehingga 𝑛⁡ < ⁡ 𝑥𝑖 < ⁡𝑛 + 1. Selanjutnya, masalah program linear bulat di atas dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala 𝑥𝑖  ⁡𝑛 dan 𝑥𝑖 ⁡  ⁡𝑛 + 1. Proses pencabangan ini bertujuan untuk mempersempit daerah layak sehingga dapat dilakukan eliminasi terhadap penyelesaian yang tak bulat bagi 𝑥𝑖 dari tinjauan selanjutnya, tetapi masih tetap mempertahankan semua penyelesaian bilangan bulat yang mungkin terhadap masalah semula. Kemudian, proses pencabangan ini terus dilakukan hingga diperoleh suatu penyelesaian bilangan bulat yang pertama.

Contoh 2.1 Minimumkan 𝑧 = 𝑥1 + 𝑥2 Dengan kendala 4𝑥1 + 4𝑥2 ≥ 10 24𝑥1 + 10𝑥2 ≥ 60 { 𝑥1 , 𝑥2 ≥ 0⁡dan⁡bilangan⁡bulat Penyelesaian: Menyelesaikan masalah program linear tersebut sehingga mendapatkan solusi optimal 𝑥1 = 2,5, 𝑥2 = 0, dan 𝑧 = 2,5. Penyelesaian tidak berbentuk bilangan bulat maka lanjut ke langkah 2.


Selanjutnya, masalah program linear bulat di atas dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala 𝑥1  ⁡2 dan 𝑥1  3. Sehingga didapatkan dua sub-masalah baru yang harus diselesaikan sebagai berikut. Sub-masalah 1: Minimumkan 𝑧 = 𝑥1 + 𝑥2 Dengan kendala 4𝑥1 + 4𝑥2 ≥ 10 24𝑥1 + 10𝑥2 ≥ 60

𝑥1  ⁡2 {𝑥1 , 𝑥2 ≥ 0⁡dan⁡bilangan⁡bulat dan Sub-masalah 2: Minimumkan 𝑧 = 𝑥1 + 𝑥2 Dengan kendala 4𝑥1 + 4𝑥2 ≥ 10 24𝑥1 + 10𝑥2 ≥ 60

𝑥1  3 {𝑥1 , 𝑥2 ≥ 0⁡dan⁡bilangan⁡bulat Batas untuk nilai tujuan belum dapat ditentukan karena belum mendapatkan penyelesaian bilangan bulat. Dari submasalah 1 diperoleh penyelesaian 𝑥1 = 2, 𝑥2 = 1,2, dan 𝑧 = 3,2. Penyelesaian tidak berbentuk bilangan bulat maka lanjut ke langkah 2. Langkah 2: Sub-masalah program linear dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala 𝑥2  1 dan 𝑥2  2. Karena 𝑥2  1 tidak berada dalam daerah layak maka kita memilih 𝑥2  2. Jadi, diperoleh solusi optimal yaitu 𝑧 = 3.


Dari sub-masalah 2 diperoleh penyelesaian 𝑥1 = 3, 𝑥2 = −0,5, dan 𝑧 = 2,5. Penyelesaian tidak berbentuk bilangan bulat maka lanjut ke langkah 2. Langkah 2: Sub-masalah program linear dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala 𝑥2  0 dan 𝑥2  1. Karena 𝑥2  0 tidak berada dalam daerah layak maka kita memilih 𝑥2  1 sehingga 𝑧 = 4. Jadi, diperoleh solusi optimal yaitu 𝑥1 = 2, 𝑥2 = 1, dan 𝑧 = 3.

C. Masalah Knapsack Masalah Knapsack adalah masalah program linear bilangan bulat yang hanya memiliki satu kendala dan penyelesaian berupa bilangan bulat. Masalah Knapsack biasanya digunakan untuk menyusun barang ke dalam karung yang besar yang tidak dapat memuat semua barang. Permasalahan Knapsack ini mencari solusi terbaik dari semua kemungkinan susunan barang yang akan dimasukkan ke dalam karung. Masalah Knapsack dapat dituliskan sebagai berikut. Maksimumkan 𝑧 = ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 dengan kendala 𝑚

(2.3)

∑ 𝑤𝑖 𝑎𝑖 ≤ 𝑟 𝑖=1

dengan 𝑎𝑖 adalah bilangan bulat tak negatif (𝑖 = 1,2, . . . , 𝑚) dan merupakan banyaknya barang ke-i yang dimasukan ke dalam karung, 𝑤𝑖 adalah ukuran barang ke-i yang bernilai positif dan 𝑟 adalah ukuran atau karung yang juga bernilai positif. Diasumsikan 𝑦𝑖 adalah nilai barang ke-i yang bernilai positif (variabel 𝑎𝑖 dengan


𝑦𝑖 ≤ 0 dapat segera dihapus). Perbandingan 𝑦𝑖 ⁄𝑤𝑖 merupakan nilai per satuan ukuran dari barang ke-i atau sebagai efisiensi variabel 𝑎𝑖 . Kita asumsikan lagi efisiensi variabel 𝑎𝑖 diurutkan secara menurun menurut nilai yang dikandungnya: 𝑦1 ⁄𝑤1 ≥ 𝑦2 ⁄𝑤2 ≥ ⋯ ≥ 𝑦𝑚 ⁄𝑤𝑚

(2.4)

Untuk setiap solusi optimal dari masalah Knapsack memenuhi: 𝑚

(2.5)

𝑟 − ∑ 𝑤𝑖 𝑎𝑖 < 𝑤𝑚 𝑖=1

Pertidaksamaan (2.5) artinya sisa ukuran dari karung haruslah kurang dari barang ke-m. Masalah Knapsack memiliki dua jenis berdasarkan penyelesaiannya yaitu Knapsack (0-1) dan Knapsack bilangan bulat. Pada makalah ini akan menggunakan Knapsack bilangan bulat yang akan diselesaikan menggunakan metode cabang dan batas. Berikut adalah tahapan untuk menyelesaikan masalah Knapsack dengan metode cabang dan batas. 1.

Menentukan nilai awal yaitu 𝑀 = 0 dan 𝑘 = 0.

2.

Menemukan perpanjangan cabang. Untuk 𝑗 = 𝑘 + 1, 𝑘 + 2, . . . , 𝑚 maka 𝑎𝑗 = 𝑗−1

⌊(𝑟 − ∑𝑖=1 𝑤𝑖 𝑎𝑖 )⁄𝑤𝑗 ⌋. Biasanya untuk 𝑎1 = ⌊𝑟⁄𝑤1 ⌋. Maka didapat solusi ∗ terbaik 𝑎1∗ , 𝑎2∗ , … , 𝑎𝑚 .

3.

𝑚 Memperbaiki solusi. Jika ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 > 𝑀, maka mengganti M dengan ∑𝑖=1 𝑦𝑖 𝑎𝑖 ∗ dan mengganti 𝑎1∗ , 𝑎2∗ , … , 𝑎𝑚 dengan 𝑎1 , 𝑎2 , … , 𝑎𝑚 .


4.

Menemukan cabang selanjutnya. Menemukan k terbesar sedemikian hingga 𝑘 ≤ 𝑚 − 1 dimana 𝑎𝑘 > 0. Kita dapat tuliskan 𝑎̅𝑖 = 𝑎𝑖 untuk 𝑖 = 1, 2, . . . , 𝑘 − 1. a. Jika k=1 maka berhenti; selain itu ganti k dengan k-1. b. Jika 𝑎𝑘 = 0, maka kembali ke 4a, selain itu ganti 𝑎𝑘 dengan 𝑎𝑘 = 𝑎𝑘 − 1. c. Pencarian cabang yang lebih baik. 𝑦

Jika ∑𝑘𝑖=1 𝑦𝑖 𝑎̅𝑖 + 𝑤𝑘+1 (𝑟 − ∑𝑘𝑖=1 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 (untuk koefisien 𝑦𝑖 bukan bilang𝑘+1

𝑦

an bulat positif) atau ∑𝑘𝑖=1 𝑦𝑖 𝑎̅𝑖 + 𝑤𝑘+1 (𝑟 − ∑𝑘𝑖=1 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 + 1 (untuk koe𝑘+1

fisien 𝑦𝑖 bilangan bulat positif) maka 𝑎̅1 , 𝑎̅2 , … , 𝑎̅𝑘 tidak layak diperiksa. Oleh karena itu, harus kembali ke langkah 4. Selain itu, kembali ke langkah 2.


Start Menentukan nilai awal yaitu 𝑀 = 0 dan 𝑘 = 0.

Menentukan perpanjangan cabang. Untuk 𝑗 = 𝑘 + 1, 𝑘 + 2, . . . , 𝑚 maka 𝑗−1 𝑎𝑗 = ⌊(𝑟 − ∑𝑖=1 𝑦𝑖 𝑎𝑖 )⁄𝑤𝑗 ⌋ dan didapat solusi terbaik 𝑎1∗ , 𝑎2∗ , … , 𝑎𝑚∗ .

M Tidak berubah

Tidak

Apakah ∑𝑚𝑖=1 𝑦𝑖 𝑎𝑖∗ > 𝑀

Ya

Mengganti M dengan ∑𝑚𝑖=1 𝑦𝑖 𝑎𝑖∗

Mengganti solusi sebelumnya (𝑎1∗ , 𝑎2∗ , … , 𝑎𝑚∗ ) dengan 𝑎1 , 𝑎2 , … , 𝑎𝑚 .

Tidak

Ya

Apakah ∑𝑘𝑖=1 𝑦𝑖 𝑎̅𝑖 + 𝑦 𝑘+1 (𝑟 − ∑𝑘𝑖=1 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 ? 𝑤 𝑘+1

Tidak

Apakah terdapat 𝑎𝑘 = 0 dan 𝑘 = 1?

Mereduksi k sampai diperoleh 𝑎𝑘 > 0 lalu mengganti 𝑎𝑘 Tidak dengan 𝑎̅ = 𝑎 − 1, dimana 𝑘 𝑘 𝑎̅𝑖 = 𝑎𝑖 untuk 𝑖 = 1, 2, . . . , 𝑘 − 1.

Apakah koefisien 𝑦𝑖 bilangan bulat positif?

Ya

Apakah ∑𝑘𝑖=1 𝑦𝑖 𝑎̅𝑖 + Tidak 𝑦 𝑘+1 (𝑟 − ∑𝑘𝑖=1 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑤 𝑘+1

𝑀+1?

Ya

Vektor a

END

Gambar 2.1: Diagram alir masalah Knapsack


Contoh 2.2 Maksimumkan 7 1 5 1 𝑎1 + 𝑎2 + 𝑎3 + 𝑎4 24 4 24 6 dengan kendala 25,5𝑎1 + 22,5𝑎2 + 20𝑎3 + 15𝑎4 ≤ 91 Jawab: 1.

Menentukan nilai awal yaitu 𝑀 = 0 dan 𝑘 = 0.

2.

Menemukan cabang. Untuk 𝑗 = 𝑘 + 1, 𝑘 + 2, . . . , 𝑚 maka 𝑎1 = ⌊91⁄25,5⌋ = 3 2−1

𝑎2 = ⌊(91 − ∑ 𝑤𝑖 𝑎𝑖 )⁄𝑤2 ⌋ = ⌊(91 − (25,5.3))⁄22,5⌋ = 0 𝑖=1 3−1

𝑎3 = ⌊(91 − ∑ 𝑤𝑖 𝑎𝑖 )⁄𝑤3 ⌋ = ⌊(91 − (25,5.3 + 22,5.0))⁄20⌋ = 0 𝑖=1 4−1

𝑎4 = ⌊(91 − ∑ 𝑤𝑖 𝑎𝑖 )⁄𝑤4 ⌋ = ⌊(91 − (25,5.3 + 22,5.0 + 20.0))⁄15⌋ = 0 𝑖=1

Maka didapat solusi terbaik 𝑎1∗ = 3, 𝑎2∗ = 𝑎3∗ = 𝑎4∗ = 0. 3.

Menentukan apakah solusi yang diperoleh meningkat? Karena ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 = 0,875 > 𝑀 = 0, maka

𝑀 = 0,875 dan 𝑎1∗ = 3, 𝑎2∗ =

𝑎3∗ = 𝑎4∗ = 0 diganti menjadi 𝑎1 = 3, 𝑎2 = 𝑎3 = 𝑎4 = 0. 4.

Didapatkan k=3 (𝑎3 = 0) lalu dikurangkan sampai diperoleh k=1 dimana 𝑎𝑘 > 0. Maka kita ganti 𝑎1 = 3 menjadi 𝑎̅1 = 2.

5.

Apakah cabang layak untuk dieksplor?


Karena koefisien 𝑦𝑖 bukan bilangan bulat positif, maka kita uji pertidaksamaan berikut dengan k=1 dan 𝑎̅1 = 2. 𝑘

𝑘

𝑖=1

𝑖=1

𝑦𝑘+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 𝑤𝑘+1 1

1

𝑖=1

𝑖=1

𝑦1+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 0,875 𝑤1+1 7 1/4 (91 − 25,5.2) ≤ 0,875 .2 + 24 22,5 7 1 + (40) = 1,0278 > 0,875 12 90 Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dieksplor. Kembali ke langkah 2. 2.

Diketahui k=1 dan 𝑎1 = 𝑎̅1 = 2, maka diperoleh 2−1

𝑎2 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤2 ⌋ = ⌊(91 − (25,5.2))⁄22,5⌋ = 1 𝑖=1 3−1

𝑎3 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤3 ⌋ = ⌊(91 − (25,5.2 + 22,5.1))⁄20⌋ = 0 𝑖=1 4−1

𝑎4 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤4 ⌋ = ⌊(91 − (25,5.2 + 22,5.1 + 20.0))⁄15⌋ 𝑖=1

= 1⁡ 3.

∗ ∗ ∗ Karena ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 = 1 > 𝑀 = 0,875, maka 𝑀 = 1 dan 𝑎1 = 3, 𝑎2 = 𝑎3 =

𝑎4∗ = 0 diganti menjadi 𝑎1 = 2, 𝑎2 = 1, 𝑎3 = 0, 𝑎4 = 1. 4.

Didapatkan k=3 (𝑎3 = 0) lalu dikurangkan sampai diperoleh k=2 dimana 𝑎𝑘 > 0. Maka kita ganti 𝑎2 = 1 dengan 𝑎̅2 = 0..


5.

Apakah cabang layak untuk dieksplor? Karena koefisien 𝑦𝑖 bukan bilangan bulat positif, maka kita uji pertidaksamaan berikut dengan k=2 dan 𝑎̅1 = 2, 𝑎̅2 = 0. 𝑘

𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1

𝑦𝑘+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 𝑤𝑘+1 𝑦2+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 1 𝑤2+1 (

7 1 5/24 . 2 + . 0) + (91 − (25,5.2 + 22,5.0)) ≤ 1 24 4 20 7 5 (40) = 1 ≤ 1 + 12 480

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dieksplor. Kembali ke langkah 4. 4.

Didapatkan k=2 (𝑎2 = 0) lalu dikurangkan sampai diperoleh k=1 dimana 𝑎𝑘 > 0 dan kita ganti 𝑎1 = 2 dengan 𝑎̅1 = 1.

5.

Apakah cabang layak untuk dieksplor? Karena koefisien 𝑦𝑖 bukan bilangan bulat positif, maka kita uji pertidaksamaan berikut dengan k=1 dan 𝑎̅1 = 1. 𝑘

𝑘

𝑖=1

𝑖=1

1

1

𝑖=1

𝑖=1


7 1/4 . 1) + (91 − (25,5.1)) ≤ 1 24 22,5


7 1 (65,5) = 1,0194 > 1 + 24 90 Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dieksplor. Kembali ke langkah 2. 2.


𝑎2 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤2 ⌋ = ⌊(91 − (25,5.1))⁄22,5⌋ = 2 𝑖=1 3−1

𝑎3 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤3 ⌋ = ⌊(91 − (25,5.1 + 22,5.2))⁄20⌋ = 1 𝑖=1 4−1

𝑎4 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤4 ⌋ = ⌊(91 − (25,5.1 + 22,5.2 + 20.1))⁄15⌋ 𝑖=1

= 0⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ 3.

∗ ∗ Karena ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 = 1 = 𝑀 = 1, maka 𝑀 = 1 dan 𝑎1 = 2, 𝑎2 = 0 diganti

menjadi 𝑎1 = 1, 𝑎2 = 2, 𝑎3 = 1, 𝑎4 = 0. 4.

Didapatkan k=3 dimana 𝑎𝑘 < 0, maka kita ganti 𝑎3 = 1 dengan 𝑎̅3 = 0.

5.

Apakah cabang layak untuk dieksplor? Karena koefisien 𝑦𝑖 bukan bilangan bulat positif, maka kita uji pertidaksamaan berikut dengan k=1 dan 𝑎̅1 = 1, 𝑎̅2 = 2, 𝑎̅3 = 0. 𝑘

𝑘

𝑖=1

𝑖=1

1

3

𝑖=1

𝑖=1

𝑦𝑘+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 𝑤𝑘+1 𝑦3+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 1 𝑤3+1 7 1 1/6 ( . 1 + . 2 + 0) + (91 − (25,5.1 + 22,5.2 + 0)) ≤ 1 24 4 15


19 1 (20,5) = 1,0194 > 1 + 24 90 Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dieksplor. Kembali ke langkah 2. 2.

Diketahui k=3, 𝑎1 = 𝑎̅1 = 1, 𝑎2 = 𝑎̅2 = 2, dan 𝑎3 = 𝑎̅3 = 0, maka diperoleh 4−1

𝑎4 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤4 ⌋ = ⌊(91 − (25,5.1 + 22,5.2 + 20.0))⁄15⌋ 𝑖=1

= 1⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ 3.

Karena ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 = 0,9583 ≤ 𝑀 = 1, maka

𝑀 = 1 dan 𝑎1∗ = 2, 𝑎2∗ = 0

diganti menjadi 𝑎1 = 1, 𝑎2 = 2, 𝑎3 = 0, 𝑎4 = 1. 4.

Didapatkan k=3 (𝑎3 = 0) lalu dikurangkan sampai diperoleh k=2 dimana 𝑎𝑘 < 0, maka kita ganti 𝑎2 = 2 dengan 𝑎̅2 = 1.

5.


𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1


7 1 5/24 . 1 + . 1) + (91 − (25,5.1 + 22,5.1)) ≤ 1 24 4 20 13 5 (43) = 0,9896 ≤ 1 + 24 480

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dieksplor. Kembali ke langkah 4.


4.

Kita peroleh k=2 dimana 𝑎𝑘 < 0, maka kita ganti 𝑎2 = 1 dengan 𝑎̅2 = 0.

5.


𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1


7 1 5/24 . 1 + . 0) + (91 − (25,5.1 + 22,5.0)) ≤ 1 24 4 20 7 5 (65.5) = 0,974 ≤ 1 + 24 480



5.

Apakah cabang layak untuk dieksplor? Karena koefisien 𝑦𝑖 bukan bilangan bulat positif, maka kita uji pertidaksamaan berikut dengan k=1 dan 𝑎̅1 = 0. 𝑘

𝑘

𝑖=1

𝑖=1

1

1

𝑖=1

𝑖=1


7 1/4 . 0) + (91 − (25,5.0)) ≤ 1 24 22,5


1 (91) = 1,011 > 1 90 Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dieksplor. Kembali ke langkah 2. 2.


𝑎2 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤2 ⌋ = ⌊(91 − (25,5.0))⁄22,5⌋ = 4 𝑖=1 3−1

𝑎3 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤3 ⌋ = ⌊(91 − (25,5.0 + 22,5.4))⁄20⌋ = 0 𝑖=1 4−1

𝑎4 = ⌊(91 − ∑ 𝑤𝑖 𝑎̅𝑖 )⁄𝑤4 ⌋ = ⌊(91 − (25,5.0 + 22,5.4 + 20.0))⁄15⌋ 𝑖=1

= 0⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ 3.

∗ ∗ Karena ∑𝑚 𝑖=1 𝑦𝑖 𝑎𝑖 = 1 ≤ 𝑀 = 1, maka 𝑀 = 1 dan 𝑎1 = 1, 𝑎2 = 0 diganti

menjadi 𝑎1 = 0, 𝑎2 = 4, 𝑎3 = 0, 𝑎4 = 0. 4.


5.


𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1

𝑦𝑘+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 𝑀 𝑤𝑘+1 𝑦2+1 ∑ 𝑦𝑖 𝑎̅𝑖 + (𝑟 − ∑ 𝑤𝑖 𝑎̅𝑖 ) ≤ 1 𝑤2+1


(

7 1 5/24 . 0 + . 3) + (91 − (25,5.0 + 22,5.3)) ≤ 1 24 4 20 3 5 (23,5) = 0,9948 ≤ 1 + 4 480



5.


𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1


7 1 5/24 . 0 + . 2) + (91 − (25,5.0 + 22,5.2)) ≤ 1 24 4 20 1 5 (46) = 0,9792 ≤ 1 + 2 480



5.

Apakah cabang layak untuk dieksplor? Karena koefisien 𝑦𝑖 bukan bilangan bulat positif, maka kita uji pertidaksamaan berikut dengan k=2 dan 𝑎̅1 = 0, 𝑎̅2 = 1.


𝑘

𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1


7 1 5/24 . 0 + . 1) + (91 − (25,5.0 + 22,5.1)) ≤ 1 24 4 20 1 5 (68,5) = 0,9635 ≤ 1 + 4 480



5.


𝑘

𝑖=1

𝑖=1

2

2

𝑖=1

𝑖=1


7 1 5/24 . 0 + . 0) + (91 − (25,5.0 + 22,5.0)) ≤ 1 24 4 20 5 (91) = 0,9479 ≤ 1 480


Kita peroleh k=1 dimana 𝑎𝑘 = 0, maka iterasi berhenti.


Jadi didapatkan solusi yaitu 𝑎1∗ = 2, 𝑎2∗ = 1, 𝑎3∗ = 0, 𝑎4∗ = 1 dengan 𝑍 = 1, 𝑎1∗ = 1, 𝑎2∗ = 2, 𝑎3∗ = 1, 𝑎4∗ = 0 dengan 𝑍 = 1, dan 𝑎1∗ = 0, 𝑎2∗ = 4, 𝑎3∗ = 0, 𝑎4∗ = 0 dengan 𝑍 = 1. Berikut pohon enumerasi dari solusi-solusi yang sudah didapat diatas. 𝑎1 = 3

𝑎2 = 0

𝑎3 = 0

𝑎2 = 1

𝑎3 = 0

𝑎4 = 0

𝑎4 = 1

𝑎1 = 2 𝑎2 = 0

dipotong

𝑎3 = 1

𝑎4 = 0

𝑎3 = 0

𝑎4 = 1

𝑎2 = 2

𝑎1 = 1

𝑎2 = 1

dipotong

𝑎2 = 0

dipotong

𝑎2 = 4

𝑎1 = 0

𝑎1 = 0

𝑎3 = 0

𝑎2 = 3

dipotong

𝑎2 = 2

dipotong

𝑎2 = 1

dipotong

𝑎2 = 0

dipotong

𝑎4 = 0

dipotong

Gambar 2.3: Pohon enumerasi yang dihasilkan dari contoh 2.2

D. Algoritma Particle Swarm Optimization (PSO) Algoritma Particle Swarm Optimization (PSO) meniru perilaku sosial organisme (burung atau ikan), dimana perilaku sosial terdiri dari tindakan individu dan pengaruh dari individu-individu lain dalam suatu kelompok. Tiap-tiap makhluk


hidup (selanjutnya disebut partikel) akan disebar di ruang pencarian solusi (search space) yang seragam secara acak. Kemudian setiap partikel akan berusaha berpindah posisi untuk mencari posisi lain yang dapat menghasilkan fungsi obyektif atau tujuan yang lebih baik. Setiap pergerakan partikel akan dipandu oleh dua hal, posisi terbaik yang pernah ditempati partikel tersebut dan posisi terbaik yang pernah ditemui oleh seluruh partikel. Sehingga, partikel-partikel tersebut akan bekerja sama dalam mencari solusi optimal. Kata partikel menunjukkan, misalnya, seekor burung dalam kawanan burung. Setiap individu atau partikel berperilaku secara terdistribusi dengan cara menggunakan kecerdasannya (intelligence) sendiri dan juga dipengaruhi perilaku kelompok kolektifnya. Dengan demikian, jika satu partikel atau seekor burung menemukan jalan yang tepat atau pendek menuju ke sumber makanan, sisa kelompok yang lain juga akan dapat segera mengikuti jalan tersebut meskipun lokasi mereka jauh di kelompok tersebut. Dalam algoritma PSO, kawanan diasumsikan mempunyai ukuran tertentu dengan setiap partikel posisi awalnya terletak di suatu lokasi yang acak dalam ruang multidimensi. Setiap partikel diasumsikan memiliki dua karakteristik: posisi dan kecepatan. Setiap partikel bergerak dalam ruang berdasarkan informasi yang diterima mengenai posisi yang baik tersebut. Sebagai contoh, misalnya perilaku burung-burung dalam kawanan burung. Meskipun setiap burung mempunyai keterbatasan dalam hal kecerdasan, biasanya ia akan mengikuti kebiasaan (rule) seperti berikut: 1. Seekor burung tidak berada terlalu dekat dengan burung yang lain.


2. Burung tersebut akan mengarahkan terbangnya ke arah rata-rata keseluruhan burung. 3. Burung akan memposisikan diri dengan rata-rata posisi burung yang lain dengan menjaga jarak sehingga jarak antar burung dalam kawanan itu tidak terlalu jauh. Dengan demikian, perilaku kawanan burung akan didasarkan pada kombinasi dari 3 faktor simpel berikut: 1. Kohesi – terbang bersama 2. Separasi – jangan terlalu dekat 3. Penyesuaian (alignment) – mengikuti arah bersama Jadi PSO dikembangkan dengan berdasarkan pada model berikut : 1. Ketika seekor burung mendekati target atau makanan (atau bisa minimum atau maksimum dari nilai suatu fungsi tujuan) secara cepat mengirim informasi kepada burung-burung yang lain dalam kawanan tersebut. 2. Burung yang lain akan mengikuti arah menuju ke makanan tetapi tidak secara langsung. 3. Ada komponen yang tergantung pada pikiran setiap burung, yaitu memorinya tentang apa yang sudah dilewati pada waktu sebelumnya. Pada algoritma PSO, pencarian solusi dilakukan oleh suatu populasi yang terdiri dari beberapa partikel. Populasi dibangkitkan secara acak (random) dengan batasan nilai terkecil dan terbesar. Setiap partikel merepresentasikan posisi atau


solusi dari permasalahan yang dihadapi. Setiap partikel melakukan pencarian solusi yang optimal dengan melintasi ruang pencarian (search space). Hal ini dilakukan dengan cara setiap partikel melakukan penyesuaian terhadap posisi partikel terbaik dari partikel tersebut (local best) dan penyesuaian terhadap posisi partikel terbaik dari seluruh kawanan (global best) selama melintasi ruang pencarian. Jadi, penyebaran pengalaman atau informasi terjadi di dalam partikel itu sendiri dan antara suatu partikel dengan partikel terbaik dari seluruh kawanan selama proses pencarian solusi. Setelah itu, dilakukan proses pencarian untuk mencari posisi terbaik setiap partikel dalam sejumlah iterasi tertentu sampai didapatkan posisi yang relatif tetap (steady) dengan kata lain nilai fungsi mulai konvergen atau iterasi telah mencapai batas yang telah ditetapkan. Pada setiap iterasi, setiap solusi yang direpresentasikan oleh posisi partikel dievaluasi performanya dengan cara memasukkan solusi tersebut ke dalam fungsi kesesuaian (fitness function). Setiap partikel diperlakukan seperti sebuah titik pada suatu dimensi ruang tertentu. Kemudian terdapat dua faktor yang memberikan karakter terhadap status partikel pada ruang pencarian, yaitu posisi partikel dan kecepatan partikel. Berikut ini merupakan formulasi matematis yang menggambarkan posisi dan kecepatan partikel pada suatu dimensi ruang tertentu: 𝑋 𝑖 (𝑡) = 𝑥1𝑖 (𝑡), 𝑥2𝑖 (𝑡), ..., 𝑥𝑁𝑖 (𝑡)

(2.6)

𝑉 𝑖 (𝑡) = 𝑣1𝑖 (𝑡), 𝑣2𝑖 (𝑡), ..., 𝑣𝑁𝑖 (𝑡)

(2.7)

dengan X = posisi partikel, V = kecepatan partikel, i = indeks partikel, t = iterasi ke-t, dan N = ukuran dimensi ruang. Adapun model matematika yang


menggambarkan mekanisme pembaruan status partikel kecepatan maupun posisi (updating velocity and position), adalah sebagai berikut: 𝑉 𝑖 (𝑡) = 𝑉 𝑖 (𝑡 − 1) + 𝑐1. 𝑟1. (𝑋𝐿𝑖 − 𝑋 𝑖 (𝑡 − 1)) + 𝑐2. 𝑟2. (𝑋𝐺 − 𝑋 𝑖 (𝑡 − 1)) (2.8) 𝑋 𝑖 (𝑡) = 𝑉 𝑖 (𝑡) + 𝑋 𝑖 (𝑡 − 1)

(2.9)

𝑖 𝑖 𝑖 dengan 𝑋𝐿𝑖 = 𝑥𝐿1 , 𝑥𝐿2 , ..., 𝑥𝐿𝑁 merepresentasikan local best dari partikel ke-

i (yang selanjutnya akan disebut sebagai particle best). Sedangkan 𝑋𝐺 = 𝑥𝐺1 , 𝑥𝐺2 , ..., 𝑥𝐺𝑁 merepresentasikan global best dari seluruh kawanan. Sedangkan 𝑐1 dan 𝑐2 adalah suatu konstanta yang bernilai positif yang biasanya disebut faktor pembelajaran (learning factor) atau faktor percepatan (acceleration factor). Kemudian 𝑟1 dan 𝑟2 adalah suatu bilangan acak (random) yang bernilai antara 0 sampai 1. Persamaan (2.8) digunakan untuk menghitung kecepatan partikel yang baru berdasarkan kecepatan sebelumnya, jarak antara posisi saat ini dengan posisi terbaik partikel (particle best), dan jarak antara posisi saat ini dengan posisi terbaik kawanan (global best). Kemudian partikel terbang menuju posisi yang baru berdasarkan persamaan (2.9). Setelah algoritma PSO ini dijalankan dengan sejumlah iterasi tertentu hingga mencapai kriteria pemberhentian, maka akan didapatkan solusi yang terletak pada posisi terbaik kawanan (global best). Model ini akan disimulasikan dalam ruang dengan dimensi tertentu dengan sejumlah iterasi sehingga di setiap iterasi, posisi partikel akan semakin mengarah ke target yang dituju (minimasi atau maksimasi fungsi). Ini dilakukan hingga maksimum iterasi dicapai atau bisa juga digunakan kriteria penghentian yang lain yaitu nilai fungsi obyektif atau tujuan sudah konvergen ke nilai optimum.


Proses untuk mencari nilai minimum menggunakan algoritma PSO yaitu sebagai berikut : 1. Inisialisasi sekumpulan partikel secara acak atau random (setiap partikel merepresentasikan solusi yang mungkin untuk masalah optimasi). 2. Inisialisasi posisi dari setiap partikel (𝑋 𝑖 ) dan kecepatan dari setiap partikel (𝑉 𝑖 ). 3. Hitung nilai kesesuaian dari setiap partikel 𝐹 𝑖 berdasarkan formula dan model yang telah ditentukan sesuai dengan masalah optimasinya. 4. Untuk setiap partikel, bandingkan nilai kesesuaian 𝐹 𝑖 dengan nilai terbaiknya yang telah dicapai 𝑋𝐿𝑖 (particle best), jika 𝐹 𝑖 < 𝑋𝐿𝑖 , maka 𝑋𝐿𝑖 diganti dengan 𝐹 𝑖 . 5. Untuk setiap partikel, bandingkan nilai kesesuaian 𝐹 𝑖 dengan nilai terbaik yang dicapai dalam populasi 𝑋𝐺 (global best), jika 𝐹 𝑖 < 𝑋𝐺 , maka 𝑋𝐺 diganti dengan 𝐹 𝑖 . 6. Berdasarkan bagian 4 dan 5, kecepatan (𝑉 𝑖 ) dan posisi dari partikel (𝑋 𝑖 ) diubah. Rumus pembaruan kecepatan (𝑉 𝑖 ) : 𝑉 𝑖 (𝑡) = 𝑉 𝑖 (𝑡 − 1) + 𝑐1. 𝑟1. (𝑋𝐿𝑖 − 𝑋 𝑖 (𝑡 − 1)) + 𝑐2. 𝑟2. (𝑋𝐺 − 𝑋 𝑖 (𝑡 − 1)) Adapun rumus pembaruan posisi (𝑋 𝑖 ) adalah 𝑋 𝑖 (𝑡) = 𝑋 𝑖 (𝑡 − 1) + 𝑉 𝑖 (𝑡). 7. Jika telah mencapai kondisi akhir (mencapai nilai iterasi optimum atau perulangan telah mencapai nilai yang konvergen ke nilai fungsi


minimum) maka perulangan berhenti dan nilai optimumnya didapatkan namun jika belum maka diulangi pada nomor 3.

Berikut Pseudo code dari algoritma PSO : For setiap partikel Inisialisasi partikel End Repeat For setiap partikel Hitung nilai kesesuaian If nilai kesesuaian baru lebih baik daripada nilai kesesuian lama Perbarui nilai kesesuian dari partikel tersebut End End Pilih partikel dengan nilai kesesuaian terbaik diantara semua partikel tetangganya dan simpan nilai kesesuaian terbaik tersebut For setiap partikel Hitung kecepatan partikel menggunakan rumus pertama di atas Perbarui posisi pertikel menggunakan rumus kedua di atas End Until (kriteria berhenti = True)


Berikut ini adalah diagram alir dari algoritma PSO: Mulai

Bangkitkan parameter dari PSO

Inisialisasi posisi, kecepatan, dan ruang setiap partikel

Evaluasi nilai kesesuian terbaik dari tiap partikel, dan pilih Pbest dan Gbest

Bangkitkan iterasi dari t = 1

Perbarui posisi dan kecepatan setiap partikel

Hitung kembali nilai kesesuaian tiap partikel dan perbarui Pbest dan Gbest

Tidak Apakah kriteria terpenuhi?

Ya Cetak nilai optimal dari variabel


Cara Kerja Algoritma Particle Swarm Optimization Misalkan kita mempunyai fungsi berikut: min f(x) dimana 𝑥 (𝐵) ≤ 𝑥 ≤ 𝑥 (𝐴) Prosedur PSO dapat dijabarkan dengan langkah-langkah sebagai berikut: 1. Asumsikan bahwa ukuran kelompok atau kawanan (jumlah partikel) adalah N. Untuk mengurangi jumlah evaluasi fungsi yang diperlukan untuk menemukan solusi, sebaiknya ukuran N tidak terlalu besar, tetapi juga tidak terlalu kecil, agar ada banyak kemungkinan posisi menuju solusi terbaik atau optimal. Jika terlalu kecil, sedikit kemungkinan menemukan posisi partikel yang baik. Terlalu besar juga akan membuat perhitungan jadi panjang. Biasanya digunakan ukuran kawanan adalah 20 sampai 30 partikel. 2. Bangkitkan populasi awal 𝑥 dengan rentang 𝑥 (𝐵) dan 𝑥 (𝐴) secara random sehingga didapat 𝑥1 , 𝑥2 , . . . , 𝑥𝑁 . Setelah itu, untuk mudahnya, posisi partikel j dan kecepatannya pada iterasi i dinotasikan sebagai 𝑥𝑗𝑖 dan 𝑣𝑗𝑖 . Sehingga partikel-partikel awal ini dinotasikan 𝑥10 , 𝑥20 , ..., 𝑥𝑁0 dan kecepatan-kecepatan awal ini dinotasikan 𝑣10 , 𝑣20 , ..., 𝑣𝑁0 . Vektor 𝑥𝑗0 , (𝑗 = 1,2, … , 𝑁) disebut vektor koordinat dari partikel dan vektor 𝑣𝑗0 , (𝑗 = 1,2, … , 𝑁) disebut vektor koordinat dari kecepatan. Evaluasi nilai fungsi tujuan untuk setiap partikel dan nyatakan dengan f[𝑥10 ], f[𝑥20 ], ..., f[𝑥𝑁0 ].


3. Hitung kecepatan dari semua partikel. Semua partikel bergerak menuju titik optimal dengan suatu kecepatan. Awalnya semua kecepatan dari partikel diasumsikan sama dengan nol. Set iterasi 𝑖 = 1. 4. Pada iterasi ke-i, temukan 2 parameter penting untuk setiap partikel j, yaitu: a. Nilai terbaik sejauh ini dari 𝑥𝑗𝑖 (koordinat partikel j pada iterasi i) dan untuk memudahkan penulisan, nyatakan saja sebagai Pbest,j, dengan nilai fungsi obyektif paling rendah (kasus minimasi), f[𝑥𝑗𝑖 ], yang ditemui sebuah partikel j pada semua iterasi sebelumnya. Nilai terbaik untuk semua partikel 𝑥𝑗𝑖 yang ditemukan sampai iterasi ke-i, kita tuliskan saja sebagai Gbest, dengan nilai fungsi tujuan paling kecil atau minimum diantara semua partikel untuk semua iterasi sebelumnya, f[𝑥𝑗𝑖 ]. b. Hitung kecepatan partikel j pada iterasi ke-i dengan rumus sebagai berikut: 𝑣𝑗𝑖 = 𝑣𝑗𝑖−1 + 𝑐1 . 𝑟1 . (Pbest,j⁡–⁡𝑥𝑗𝑖−1 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥𝑗𝑖−1 ),⁡dengan 𝑗 = 1,2, … , 𝑁 dimana 𝑐1 dan 𝑐2 masing-masing adalah learning rates untuk kemampuan individu (cognitive) dan pengaruh sosial (group), dan 𝑟1 dan 𝑟2 bilangan acak (random) yang berdistribusi seragam (uniform) dalam interval 0 dan 1. Jadi parameter 𝑐1 dan 𝑐2 menunjukkan bobot dari memori (position) sebuah partikel terhadap memori (position) dari kelompok (swarm). Nilai dari 𝑐1 dan 𝑐2


adalah 2 sehingga partikel-partikel akan mendekati target sekitar setengah selisihnya. c. Hitung posisi atau koordinat partikel j pada iterasi ke-i dengan cara 𝑥𝑗𝑖 = 𝑥𝑗𝑖−1 + 𝑣𝑗𝑖 ;

j = 1, 2, ..., N

Evaluasi nilai fungsi tujuan untuk setiap partikel dan nyatakan sebagai f[𝑥1𝑖 ], f[𝑥2𝑖 ], ..., f[𝑥𝑁𝑖 ]. 5. Cek apakah solusi yang sekarang sudah konvergen. Jika posisi semua partikel menuju ke satu nilai yang sama, maka ini disebut konvergen. Jika belum konvergen maka langkah 4 diulang dengan memperbarui iterasi 𝑖⁡ = ⁡𝑖⁡ + ⁡1, dengan cara menghitung nilai baru dari Pbest,j dan Gbest. Proses iterasi ini dilanjutkan sampai semua partikel menuju ke satu titik solusi yang sama. Biasanya akan ditentukan dengan kriteria penghentian (stopping criteria), misalnya jumlah selisih solusi sekarang dengan solusi sebelumnya sudah sangat kecil.

Contoh 2.3 Kerjakan soal berikut: min 𝑓(𝑥) = (100⁡– ⁡𝑥)2 dengan 60 ≤ x ≤ 120 Sebelum masuk ke dalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu: Tentukan dimensi permasalahan. Diasumsikan dalam kasus ini, dimensi bernilai 1 karena ada 1


variabel yang akan dicari nilainya. Kemudian tentukan jumlah partikel yang digunakan dalam perhitungan. Diasumsikan dalam kasus ini, jumlah partikel yang digunakan adalah 4 partikel. Tentukan jumlah iterasi yang digunakan oleh setiap partikel untuk melakukan proses. Diasumsikan dalam kasus ini, jumlah iterasi yang digunakan adalah 3 kali. Tentukan total posisi yang harus dicapai. Semua solusi yang ditemukan oleh masing-masing individu harus berjumlah sebanyak variabel ini. Diasumsikan dalam kasus ini, total nilai yang harus dicapai adalah sesuai fungsi obyektif atau fungsi tujuan dan memenuhi batasan nilai yang diberikan yaitu bernilai antara 60 dan 120. Tentukan kecepatan awal untuk perpindahan posisi partikel dalam setiap proses. Diasumsikan dalam kasus ini nilai kecepatan awal adalah 0. Kemudian bobot sosial dalam contoh soal ini diasumsikan 𝑐1 = 𝑐2 = 1. Langkah-langkah penggunaan algoritma ini adalah 1. Inisialisasi data, dengan jumlah partikel 𝑁 = 4 seperti yang sudah ditentukan sebelumnya, didapat populasi awal secara acak (random) misalkan: 𝑥10 = 80, 𝑥20 = 90, 𝑥30 = 110, 𝑥40 = 75. 2. Hitung nilai fungsi untuk setiap partikel ⁡𝑥𝑗0 untuk 𝑗 = 1, 2, 3, 4 dan nyatakan dengan: 𝑓(𝑥10 ) = 𝑓(80) = 400,


𝑓(𝑥20 ) = 𝑓(90) = 100, 𝑓(𝑥30 ) = 𝑓(110) = 100, 𝑓(𝑥40 ) = 𝑓(75) = 625. 3. Seperti yang sudah dipaparkan di atas, ditentukan kecepatan awal 𝑣10 = ⁡𝑣20 = 𝑣30 = 𝑣40 = 0 dan tetapkan iterasi pertama yaitu 𝑖 = 1. 4. Selanjutnya ditemukan nilai terbaik lokal sejauh ini yang merupakan posisi partikel terbaik dari partikel tersebut alias 𝑃𝑏𝑒𝑠𝑡,𝑗 serta nilai terbaik global yang merupakan posisi partikel terbaik dari seluruh kawanan (𝐺𝑏𝑒𝑠𝑡 ). 𝑃𝑏𝑒𝑠𝑡,1 = 80, 𝑃𝑏𝑒𝑠𝑡,2 = 90, 𝑃𝑏𝑒𝑠𝑡,3 = 110, 𝑃𝑏𝑒𝑠𝑡,4 = 75, 𝐺𝑏𝑒𝑠𝑡 = 90. 5. Hitung 𝑣𝑗𝑖 dengan 𝑐1 = 𝑐2 = 1 dan misalkan nilai bilangan acak (random) yang didapat 𝑟1 = 0.4 dan 𝑟2 = 0.5 dengan rumus: 𝑣𝑗𝑖 = 𝑣𝑗𝑖−1 + 𝑐1 . 𝑟1 . (Pbest,j⁡–⁡𝑥𝑗𝑖−1 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥𝑗𝑖−1 ) diperoleh: 𝑣11 = 𝑣10 + 𝑐1 . 𝑟1 . (Pbest,1⁡–⁡𝑥10 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥10 ) = 0 + 0.4(80 − 80) + 0.5(90 − 80) = 5 𝑣21 = 𝑣20 + 𝑐1 . 𝑟1 . (Pbest,2⁡–⁡𝑥20 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥20 ) = 0 + 0.4(90 − 90) + 0.5(90 − 90) = 0


𝑣31

=

𝑣30 + 𝑐1 . 𝑟1 . (Pbest,3⁡–⁡𝑥30 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥30 ) = 0 + 0.4(110 −

110) + 0.5(90 − 110) = −10 𝑣41 = 𝑣40 + 𝑐1 . 𝑟1 . (Pbest,4⁡–⁡𝑥40 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥40 ) = 0 + 0.4(75 − 75) + 0.5(90 − 75) = 7.5 Sehingga nilai 𝑥𝑗𝑖 sebagai posisi partikel yang baru adalah: 𝑥11 = 80 + 5 = 85, 𝑥21 = 90 + 0 = 90, 𝑥31 = 110 − 10 = 100, 𝑥41 = 75 + 7.5 = 82.5 6. Hitung nilai fungsi sekarang pada partikel ⁡𝑥𝑗1 untuk 𝑗 = 1, 2, 3, 4 𝑓(𝑥11 ) = 𝑓(85) = 225, 𝑓(𝑥21 ) = 𝑓(90) = 100, 𝑓(𝑥31 ) = 𝑓(100) = 0, 𝑓(𝑥41 ) = 𝑓(82.5) = 306.25 Sedangkan pada iterasi sebelumnya kita dapatkan 𝑓(𝑥10 ) = 𝑓(80) = 400, 𝑓(𝑥20 ) = 𝑓(90) = 100, 𝑓(𝑥30 ) = 𝑓(1110) = 100, 𝑓(𝑥40 ) = 𝑓(75) = 625 7. Nilai 𝑓(𝑥𝑗𝑖 ) dari iterasi sebelumnya tidak ada yang lebih baik sehingga 𝑃𝑏𝑒𝑠𝑡,𝑗 baru untuk masing-masing partikel sama dengan nilai 𝑥𝑗1 nya. 𝑃𝑏𝑒𝑠𝑡,1 = 85,


𝑃𝑏𝑒𝑠𝑡,2 = 90, 𝑃𝑏𝑒𝑠𝑡,3 = 100, 𝑃𝑏𝑒𝑠𝑡,4 = 82.5, 𝐺𝑏𝑒𝑠𝑡 = 100. Apakah solusi 𝑥𝑗1 sudah konvergen, dimana nilai dari masing-masing 𝑥𝑗1 nya sudah dekat? Belum. Maka, lanjutkan ke iterasi berikutnya yaitu 𝑖 = 2. 8. Hitung kecepatan baru dan misalkan nilai bilangan acak (random) selanjutnya yang didapat adalah 𝑟1 = 0.3 dan 𝑟2 = 0.6 maka diperoleh: 𝑣12 = 𝑣11 + 𝑐1 . 𝑟1 . (Pbest,1⁡–⁡𝑥11 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥11 ) = 5 + 0.3(85 − 85) + 0.6(100 − 85) = 14 𝑣22 = 𝑣21 + 𝑐1 . 𝑟1 . (Pbest,2⁡–⁡𝑥21 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥21 ) = 0 + 0.3(90 − 90) + 0.6(100 − 90) = 6 𝑣32 = 𝑣31 + 𝑐1 . 𝑟1 . (Pbest,3⁡–⁡𝑥31 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥31 ) = −10 + 0.3(100 − 100) + 0.6(100 − 100) = −10 𝑣42 = 𝑣41 + 𝑐1 . 𝑟1 . (Pbest,4⁡–⁡𝑥41 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥41 ) = 7.5 + 0.3(82.5 − 82.5) + 0.6(100 − 82.5) = 18 Sehingga nilai 𝑥𝑗𝑖 sebagai posisi partikel yang baru adalah: 𝑥12 = 85 + 14 = 99, 𝑥22 = 90 + 6 = 96, 𝑥32 = 100 − 10 = 90, 𝑥42 = 82.5 + 18 = 100.5 9. Hitung nilai fungsi sekarang pada partikel ⁡𝑥𝑗2 untuk 𝑗 = 1, 2, 3, 4


𝑓(𝑥12 ) = 𝑓(99) = 1, 𝑓(𝑥22 ) = 𝑓(96) = 16, 𝑓(𝑥32 ) = 𝑓(90) = 100, 𝑓(𝑥42 ) = 𝑓(100.5) = 0.25 10. Jika dibandingkan dengan nilai 𝑓(𝑥𝑗𝑖 ) dari iterasi sebelumnya, ada nilai yang lebih baik dari nilai 𝑓(𝑥𝑗𝑖 ) sekarang yaitu 𝑓(𝑥31 ) = 0, sehingga 𝑃𝑏𝑒𝑠𝑡,3 = 100, dan 𝐺𝑏𝑒𝑠𝑡 akan dicari dari 𝑚𝑖𝑛⁡{1,16,0,0.25} = 0 yang dicapai pada 𝑥31 = 100. Sehingga untuk iterasi berikutnya, 𝑃𝑏𝑒𝑠𝑡 = {99,96,100,100.5} dan 𝐺𝑏𝑒𝑠𝑡 = 100. Cek kembali, apakah solusi sudah konvergen? Jika belum konvergen, set 𝑖 = 3, masuk ke iterasi berikutnya.lanjutkan ke langkah berikutnya dengan menghitung kecepatan 𝑣𝑗𝑖 baru dimana 𝑖 = 3⁡; ⁡𝑗 = 1,2,3,4 dan ulangi langkah-langkah selanjutnya sampai mencapai suatu nilai yang konvergen. Hasil dari langkah-langkah di atas dapat disajikan dalam bentuk tabel: 𝑖

𝑥𝑗𝑖

𝑣𝑗𝑖

𝑓(𝑥𝑗𝑖 )

𝑃𝑏𝑒𝑠𝑡,𝑗

0 𝑥10 = 80

𝑣10 = 0

𝑓(𝑥10 ) = 𝑓(80) = 400

𝑃𝑏𝑒𝑠𝑡,1 = 80

𝑥20 = 90

𝑣20 = 0

𝑓(𝑥20 ) = 𝑓(90) = 100


𝑥30 = 110

𝑣30 = 0

𝑓(𝑥30 ) = 𝑓(110) = 100

𝑃𝑏𝑒𝑠𝑡,3 = 110⁡

𝑥40 = 75

𝑣40 = 0

𝑓(𝑥40 ) = 𝑓(75) = 625


1 𝑥11 = 85

𝑣11 = 5

𝑓(𝑥11 ) = 𝑓(85) = 225


𝑥21 = 90

𝑣21 = 0

𝑓(𝑥21 ) = 𝑓(90) = 100


𝐺𝑏𝑒𝑠𝑡

90


𝑥31 = 100

𝑣31 = −10 𝑓(𝑥31 ) = 𝑓(100) = 0

𝑥41 = 82.5

𝑣41 = 7.5

𝑓(𝑥41 ) = 𝑓(82.5) = 306.25 𝑃𝑏𝑒𝑠𝑡,4 = 82.5

𝑣12 = 14

𝑓(𝑥12 ) = 𝑓(99) = 1


𝑥22 = 96

𝑣22 = 6

𝑓(𝑥22 ) = 𝑓(96) = 16


𝑥32 = 90

𝑣32 = −10 𝑓(𝑥32 ) = 𝑓(90) = 100

2 𝑥12 = 99

𝑥42 = 100.5 𝑣42 = 18

𝑃𝑏𝑒𝑠𝑡,3 = 100⁡

100

100

𝑃𝑏𝑒𝑠𝑡,3 = 100⁡

𝑓(𝑥42 ) = 𝑓(100.5) = 0.25 𝑃𝑏𝑒𝑠𝑡,4 = 100.5

Tabel 2.1: Tabel hasil perhitungan PSO secara manual untuk contoh 2.3 Dan berikut adalah hasil perhitungan yang diproses dengan menggunakan MATLAB: run = 1 Iteration

Best particle Objective fun

1

4

12.4323

2

4

12.4323

3

4

12.4323

4

1

6.3561

----------------------------------------------------run = 2


Iteration

Best particle Objective fun

1

4

0.0000

2

4

0.0000

3

4

0.0000

4

4

0.0000

----------------------------------------------------********************************************************* Final Results-------------------------------------------bestfun = 0 bestrun = 2 best_variables = 100 ********************************************************* Elapsed time is 0.155848 seconds.


Berikut adalah grafik konvergensi yang ditampilkan dari best run:

Gambar 2.3: Gambar grafik konvergensi PSO pada run ke 2 Dalam implementasinya, ditemukan bahwa kecepatan partikel dalam PSO standar diperbarui (update) terlalu cepat dan nilai minimum fungsi tujuan yang dicari sering terlewati. Oleh karena itu, kemudian dilakukan modifikasi atau perbaikan terhadap algoritma PSO standar. Perbaikan itu berupa penambahan suatu bobot inersia 𝑤 untuk mengurangi kecepatan pada formula pembaruan (update) kecepatan seperti yang telah disinggung sebelumnya. Bobot inersia ini diusulkan oleh Yuhui Shi dan Erberhart pada tahun 1998 untuk meredam kecepatan selama iterasi, yang memungkinkan kawanan burung konvergen dalam artian menuju titik target secara lebih akuratdan efisien dibanding


algoritma aslinya yaitu algoritma PSO standar. Biasanya nilai bobot inersia 𝑤 dibuat sedemikian hingga semakin besar iterasi yang dilalui, semakin mengecil kecepatan partikelnya. Nilai ini bervariasi secara linear dalam rentang 0.4 hingga 0.9. Secara matematis perbaikan PSO ini dapat dituliskan sebagai berikut: 𝑣𝑗𝑖 = 𝒘. 𝑣𝑗𝑖−1 + 𝑐1 . 𝑟1 . (Pbest,j⁡–⁡𝑥𝑗𝑖−1 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥𝑗𝑖−1 ),⁡dengan 𝑗 = 1,2, … , 𝑁 Formula tersebut adalah modifikasi terhadap formula sebelumnya, yaitu: 𝑣𝑗𝑖 = 𝑣𝑗𝑖−1 + 𝑐1 . 𝑟1 . (Pbest,j⁡–⁡𝑥𝑗𝑖−1 ) + 𝑐2 . 𝑟2 . (Gbest⁡–⁡𝑥𝑗𝑖−1 ),⁡dengan 𝑗 = 1,2, … , 𝑁 Perlu diketahui bahwa nilai bobot inersia (𝑤) yang tinggi menambah posisi pencarian global (global exploration), sedangkan nilai bobot inersia (𝑤) yang rendah menambah posisi pencarian lokal (local search). Oleh karena itu, supaya tidak terlalu menitikberatkan pada salah satu bagian dan tetap mencari area pencarian yang baru dalam ruang berdimensi tertentu, maka perlu dicari nilai bobot inersia (𝑤) yang secara imbang menjaga pencarian global dan lokal. Untuk mencapai itu dan mempercepat konvergensi, suatu bobot inersia yang mengecil nilainya dengan bertambahnya iterasi dapat dirumuskan: 𝑤𝑚𝑎𝑥 − 𝑤𝑚𝑖𝑛 𝑤 𝑖 = 𝑤𝑚𝑎𝑥 − ( )𝑖 𝑖𝑚𝑎𝑥

(2.10)

dimana 𝑤𝑚𝑎𝑥 dan 𝑤𝑚𝑖𝑛 masing-masing adalah nilai awal dan nilai akhir bobot inersia, 𝑖𝑚𝑎𝑥 adalah jumlah iterasi maksimum yang digunakan dan 𝑖 adalah iterasi saat ini (sekarang). Biasanya digunakan nilai 𝑤𝑚𝑎𝑥 = 0.9 dan 𝑤𝑚𝑖𝑛 = 0.4. Gambar pergerakan nilai fungsi tujuan 𝑓(𝑥) = (100⁡– ⁡𝑥)2 , untuk 50 iterasi ditunjukkan dalam gambar 2.2 sedangkan gambar pergerakan nilai fungsi tujuan 𝑓(𝑥) =


(100⁡– ⁡𝑥)2 setelah dilakukan modifikasi terhadap PSO (dengan menyertakan bobot inersia) untuk 50 iterasi ditunjukkan dalam gambar 2.3. Terlihat bahwa dengan adanya modifikasi, pergerakan akan lebih cepat konvergen. Berikut ini diberikan hasil implementasi grafik konvergensi dua jenis PSO:

Gambar 2.4: Pergerakan nilai fungsi tujuan untuk PSO tanpa modifikasi


Gambar 2.5: Pergerakan nilai fungsi tujuan untuk PSO dengan modifikasi Dari kedua gambar di atas, dapat dibandingkan bagaimana pergerakan vektor solusi menuju solusi optimal atau melihat pergerakan nilai fungsi tujuannya dari PSO asli (PSO standar) maupun PSO yang sudah dimodifikasi (disertai bobot inersia). Contoh 2.4 Contoh berikutnya yaitu bagaimana meminimalkan fungsi tujuan berdimensi lebih dari satu dan memiliki kendala (constraint). Fungsi obyektif :

min 𝑓(𝑥) = (𝑥1 − 2)2 + (𝑥2 − 3)2

dengan kendala 2𝑥1 + 𝑥2 = 4


Langsung saja kita proses dengan bantuan MATLAB dan didapatkan hasilnya sebagai berikut: ********************************************************* Final Results-------------------------------------------bestfun = 1.8000

bestrun = 2

best_variables = 0.7993 2.4014 ********************************************************* Elapsed time is 1.182401 seconds.

Gambar 2.6: Gambar grafik konvergensi PSO pada run ke 2


Untuk mendapatkan hasil tersebut, diperlukan dua script program MATLAB yang telah dimodifikasi dari script program asli yang telah dituliskan oleh Nabab Alam. File pertama mendefinisikan fungsi obyektif atau fungsi tujuan, dan file kedua dibangun program utama yang akan memecahkan masalah dengan menggunakan algoritma PSO. Script kode program terlampir. Untuk file pertama diberi nama ofun2.m. Kemudian file ke2 merupakan file program utama. Setelah script program tersebut dijalankan, diketahui nilai fungsi obyektif (fungsi tujuan) terbaik yang dihasilkan setelah 10 kali independent run adalah 1.8000 dan menghasilkan nilai variabel-variabel terbaik antara lain: x(1) = 0.7993 dan x(2) = 2.4014. Dari 10 run yang dilakukan, diketahui run yang memberikan hasil terbaik adalah run ke-2. Simulasi ini memerlukan waktu 1.182401 detik. Kita juga dapat melakukan perhitungan tanpa kendala dengan mengganti fungsi objektif pada file pertama. Sebagai contoh, kita akan kerjakan lagi contoh yang tadi tetapi tanpa kendala dan mengubah nama script ofun2.m menjadi ofun.m Kita juga harus mengubah kata ofun2 menjadi ofun pada baris 32 dan baris 73 pada file kedua (program PSO utama). Script utuh dapat diperiksa pada lampiran. Hasilnya adalah sebagai berikut: ********************************************************* Final Results-------------------------------------------bestfun = 0 bestrun = 2


best_variables = 2

3

********************************************************* Elapsed time is 0.501870 seconds.

Tampilan grafik konvergensi pada best run adalah:

Gambar 2.7: Gambar grafik konvergensi PSO pada run ke 2

Jadi, PSO dapat digunakan untuk menyelesaikan masalah program linear maupun non linear, dengan atau tanpa kendala.


BAB III MASALAH PEMOTONGAN PERSEDIAAN

A.

Masalah Pemotongan Persediaan (Cutting Stock Problem) Masalah pemotongan persediaan pertama kali dijelaskan di awal era

pemrograman linear. Gilmore dan Gomory (1961) adalah yang pertama merumuskan masalah pemotongan persediaan. Masalah dalam bentuk yang paling sederhana dapat digambarkan sebagai berikut: materi yang diberikan yang tersedia dalam berbagai bentuk dan ukuran tertentu, dipotong agar bisa menghasilkan bentuk dan ukuran tertentu yang diinginkan, sehingga dapat meminimalkan beberapa tujuan seperti biaya. Tergantung pada jenis bahan dan pola pemotongan berdasarkan pertimbangan, kita membedakan masalah pemotongan diantaranya satu, dua, dan tiga dimensi. Sebagai contoh, pemotongan kertas koran untuk panjang yang berbeda adalah masalah pemotongan satu dimensi. Karena lebar koran tetap sama, sementara hanya panjangnya yang bervariasi atau beragam. Pada makalah ini, hanya akan dibahas masalah pemotongan persediaan satu dimensi. Dalam suatu industri kertas, mesin kertas (paper machine) memproduksi rol kertas jumbo, dengan lebar maksimum yang sudah ditetapkan yang disebut dengan deckle. Kemudian rol jumbo melewati beberapa proses proses produksi dalam memenuhi pesanan. Salah satu proses produksi yang paling penting adalah pemotongan rol kertas jumbo menjadi rol yang lebih kecil atau potongan kertas persegi panjang. Proses pemotongan tersebut harus dapat meminimumkan jumlah rol jumbo yang akan dipotong dan juga dapat meminimumkan sisa pemotongan.

54


Masalah pemotongan persediaan satu dimensi yang akan dibahas adalah tentang pemotongan rol jumbo menjadi potongan rol kecil dengan ukuran yang bervariasi. Berikut gambar pemotongan satu dimensi dari rol jumbo menjadi rol kecil.

Gambar 3.1: Pemotongan rol jumbo menjadi beberapa bagian (rol kecil). Misalkan terdapat n kemungkinan pola pemotongan untuk rol jumbo dengan lebar 𝑟, rol kecil memiliki lebar 𝑤𝑖 untuk 𝑖 = 1, … , 𝑚, dan 𝑝𝑖 adalah banyaknya rol kecil dengan lebar 𝑤𝑖 (𝑝𝑖 bilangan bulat non negatif) sehingga ∑𝑚 𝑖=1 𝑝𝑖 𝑤𝑖 ≤ 𝑟. Maka masalah pemotongan ini dapat diselesaikan dalam program linier sebagai berikut. Minimumkan 𝑛

(3.1)

𝑧 = ∑ 𝑥𝑗 𝑗=1

Dengan kendala 𝑛

(3.2)

∑ 𝑝𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 𝑗=1

𝑥𝑗 ≥ 0


dan 𝑝𝑖𝑗 adalah banyaknya rol kecil dengan lebar 𝑤𝑖 dalam pola pemotongan ke-j, 𝑏𝑖 adalah banyaknya permintaan rol kecil dengan lebar 𝑤𝑖 , variabel 𝑥𝑗 menunjukkan banyaknya rol jumbo yang dipotong pada jenis pemotongan ke-𝑗, variabel 𝑚 mewakili banyaknya variasi lebar kertas potongan (rol kecil), variabel 𝑛 menunjukkan banyaknya kemungkinan pemotongan yang dapat dilakukan sesuai dengan variasi lebar kertas sesuai pesanan (pola pemotongan). Contoh 3.1 Sebuah industri kertas menghasilkan rol jumbo dengan lebar 3 meter. Pelanggan menginginkan rol dengan lebar yang lebih kecil. Dari rol jumbo dapat dipotong ke dalam 2 rol dengan lebar 93 cm, 1 rol dengan lebar 108 cm, dan menyisakan rol dengan lebar 6 cm. Misalkan pesanan yang diterima adalah sebagai berikut. Banyak rol

Lebar rol (cm)

97

135

610

108

395

93

211

42

Tabel 3.1: Tabel pesanan yang diterima Permasalahannya menjadi bagaimana menentukan pola pemotongan rol jumbo agar pesanan dapat dipenuhi dengan banyaknya rol jumbo yang harus dipotong sesedikit mungkin.


Ada 12 kemungkinan cara memotong rol jumbo ke dalam rol kecil sesuai pesanan (dengan sisa pemotongan kurang dari 42 cm) yaitu: Lebar rol

Kemungkinan 𝑗

135

108

93

42

1

2

0

0

0

2

1

1

0

1

3

1

0

1

1

4

1

0

0

3

5

0

2

0

2

6

0

1

2

0

7

0

1

1

2

8

0

1

0

4

9

0

0

3

0

10

0

0

2

2

11

0

0

1

4

12

0

0

0

7

Tabel 3.2: Tabel pola pemotongan yang dibuat sesuai pesanan


Pola 1 dari tabel di atas berarti 1 rol jumbo dengan lebar 3 meter akan dipotong menjadi 2 rol kecil dengan lebar 135 cm. Pola 2 berarti 1 rol jumbo akan dipotong menjadi 1 rol kecil dengan lebar 135, 1 rol kecil dengan lebar 108 dan 1 rol kecil dengan lebar 42 cm. Demikian seterusnya berlaku cara membaca data yang sama untuk pola-pola pemotongan yang lain. Untuk setiap kemungkinan pola 𝑃𝑗 di atas, kita memperkenalkan variabel 𝑥𝑗 ≥ 0 yang menunjukkan banyaknya rol jumbo yang harus dipotong menurut pola 𝑃𝑗 . Dengan demikian, fungsi tujuan adalah meminimumkan jumlah rol jumbo yang dipotong yaitu ∑12 𝑗=1 𝑥𝑗 . Agar pesanan terpenuhi maka untuk setiap ukuran lebar yang dipesan ditambahkan 1 kendala. Sebagai contoh, untuk pesanan 395 rol dengan lebar 93 cm, maka fungsi kendala dapat dituliskan 𝑥3 + 2𝑥6 + 𝑥7 + 3𝑥9 + 2𝑥10 + 𝑥11 ≥ 395 yang berarti jumlah rol kecil dengan lebar 93 cm yang dihasilkan dengan memotong rol jumbo menurut berbagai pola pemotongan tidak boleh kurang dari 395 rol (jumlah rol pesanan). Demikian seterusnya sehingga diperoleh masalah program linier berikut. Minimumkan 12

∑ 𝑥𝑗 𝑗=1

Dengan kendala 𝑥3 + 2𝑥6 + 𝑥7 + 3𝑥9 + 2𝑥10 + 𝑥11 ≥ 395


2𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 ≥ 97 𝑥2 + 2𝑥5 + 𝑥6 + 𝑥7 + 𝑥8 ≥ 610 𝑥2 + 𝑥3 + 3𝑥4 + 2𝑥5 + 2𝑥7 + 4𝑥8 + 2𝑥10 + 4𝑥11 + 7𝑥12 ≥ 211 𝑥𝑗 ≥ 0 Masalah tersebut dapat diselesaikan dengan program QM for Windows yang merupakan perangkat lunak digunakan untuk membantu proses perhitungan secara teknis pengambilan keputusan secara kuantitatif. Program ini menyediakan modulmodul dalam area pengambilan keputusan bisnis seperti assignment, forecasting, integer programming, linear programming, quality control, inventory, dan lainlain. Berikut adalah hasil yang didapat menggunakan QM.

Tabel 3.3: Hasil QM pada contoh 3.1


Dari gambar di atas, didapatkan solusi optimal yaitu 𝑥1 = 48,5, 𝑥5 = 206,25, 𝑥6 = 197,5, dan selainnya bernilai 0. Itu berarti untuk memenuhi pesanan diperlukan rol sebanyak 48,5 untuk pola pemotongan pertama, 206,25 rol untuk pola pemotongan kelima, dan 197,5 rol untuk pola pemotongan keenam. Dengan demikian, banyaknya rol jumbo yang digunakan sebanyak 452,25 rol. Ketika kita melibatkan masalah pemotongan persediaan dalam dunia industri kertas, tentu saja penyelesaian kasus pada masalah ini adalah dengan menyertakan data sebagai input. Secara umum, masalah-masalah ini sangat luas dan kompleks untuk diselesaikan sampai mendapat solusi eksak. Oleh karena itu, metode heuristik menjadi salah satu algoritma yang diharapakan dapat berjalan dengan baik untuk menemukan solusi yang optimal.

B.

Algoritma PSO Sebagai Pendekatan untuk Pencarian Solusi Optimal CSP Seperti yang sudah dibahas sebelumnya, algoritma Particle Swarm

Optimization (PSO) adalah algoritma evolusioner berbasis populasi yang terinspirasi dari teori kawanan di mana semua partikel di lingkungan itu bergantung pada penjelajahan mereka dan pengalaman masa lalu dari tetangga mereka. Bergantung pada pengalaman mereka sendiri dan anggota lain dari kawanan, setiap individu mendapatkan manfaat dari informasi tersebut untuk mencari makanan atau daerah untuk bersarang yang akan merepresentasikan solusi ideal. PSO menggunakan konsep populasi dan kinerja serta penyesuaian individu sebagai berikut:


A. Pengkodean Partikel Pengkodean untuk partikel ini didesain sebagai vektor berukuran m (setara dengan jumlah potongan yang diminta). Posisi j pada partikel menandai persediaan kertas di mana bagian j tersebut dipotong pada saat iterasi ke-i. Contoh: Misal: 𝑋𝑗𝑖 = (1,2,2,3) kita dapat mencatat bahwa solusi ini sesuai dengan ekstraksi 4 potongan dari 3 jenis panjang kertas. Sesuai dengan contoh ini, solusi atau partikel diilustrasikan sebagai berikut:

Potongan partikel

Gambar 3.2 : Ilustrasi partikel B. Fungsi Fitness Fungsi Fitness pada masalah pemotongan persediaan ini merupakan fungsi obyektif yang bertujuan untuk mengevaluasi setiap partikel dan menemukan banyaknya kertas yang digunakan. Nilai fitness dihitung sebagai penjumlahan semua nilai fungsi obyektif dari masing-masing variabel (partikel). C. Populasi Awal Posisi sebuah partikel yang ditunjukkan oleh vektor menyajikan solusi potensial dari masalah. PSO diinisialisasi dengan populasi partikel yang secara acak diberikan atau dihasilkan oleh metode heuristik dan mencari posisi terbaik (solusi) dengan nilai fitness terbaik.


D. Pergerakan Partikel Setelah pembangkitan populasi awal, sebuah seleksi dilakukan untuk memilih partikel pemimpin atau solusi terbaik global. Operasi perhitungan dilakukan pada setiap iterasi untuk memilih antara Terbaik Global (Gbest) dan partikel acak untuk membawanya lebih dekat ke solusi yang optimal. Pada saat itu, kawanan tumbuh dan merangkak dengan optimal sampai tercapai kriteria penghentiannya. Pada setiap iterasi dalam algoritma, setiap partikel xj memodifikasi kecepatan 𝑣𝑗𝑖 -nya dan posisi 𝑥𝑗𝑖 tergantung pada dua elemen penting: Sebuah lokal utama yaitu 𝑃𝑏𝑒𝑠𝑡𝑗𝑖 dan yang kedua yang mewakili perilaku sosial dari kawanan yaitu 𝐺𝑏𝑒𝑠𝑡𝑗𝑖 . Kecepatan yang mengontrol pergerakan partikel ini dirancang sebagai berikut: 𝑣𝑗𝑖 = 𝑣𝑗𝑖−1 + (𝑐1 𝑟1 × (𝑃𝑏𝑒𝑠𝑡𝑗𝑖 − 𝑥𝑗𝑖−1 )) + (𝑐2 𝑟2 × (𝐺𝑏𝑒𝑠𝑡𝑗𝑖 − 𝑥𝑗𝑖−1 )) 𝑥𝑗𝑖 = 𝑥𝑗𝑖−1 + 𝑣𝑗𝑖 Selanjutnya, kita mendefinisikan operator yang dipakai persamaan di atas: 1. Operator Pengurangan: Operator (−) merupakan pengurangan untuk mendapatkan selisih nilai antara posisi saat ini dengan partikel ke-j pada iterasi sebelumnya, 𝑥𝑗𝑖−1 dan posisi yang diinginkan sebagai 𝑃𝑏𝑒𝑠𝑡𝑗𝑖−1 maupun 𝐺𝑏𝑒𝑠𝑡𝑗𝑖 dapat disajikan oleh vektor dari n elemen di mana, setiap elemen menunjukkan bahwa apakah isi dari elemen yang berkoresponden dalam 𝑥𝑗𝑖−1 memenuhi kondisi yang diinginkan atau tidak. Jika ya, elemen akan mendapat nilai dari 𝑃𝑏𝑒𝑠𝑡𝑗𝑖−1 atau 𝐺𝑏𝑒𝑠𝑡𝑗𝑖 . 2. Operator perkalian: Operator (×) ini menyangkut eksplorasi ruang pencarian karena hanya berhubungan dengan struktur biner acak. Jadi dalam


operator ini, partikel memiliki peluang untuk melakukan penyimpangan posisi. 3. Operator Penambahan: Hasil operator (+) ini sebenarnya memiliki misi pertukaran informasi struktural yang dikembangkan selama pencarian.

Berikut adalah hasil penyelesaian masalah pemotongan persediaan kertas sesuai contoh yang dapat ditampilkan setelah dieksekusi dengan algoritma PSO dengan bantuan MATLAB: ********************************************************* Final Results-------------------------------------------bestfun = 452.2747

bestrun = 5

best_variables = Columns 1 through 9 48.5080

0

0

0 206.2667 197.5001

0

0

0

Columns 10 through 12 0

0

0

>> Elapsed time is 15.217224 seconds. *********************************************************


Gambar 3.3: Gambar grafik konvergensi PSO pada run ke 5 Hasil perhitungan dengan algoritma PSO yang dijalankan pada program MATLAB tidak berbeda jauh dengan hasil perhitungan yang dilakukan oleh software QM, didapatkan solusi optimal yaitu 𝑥1 = 48.5080, 𝑥5 = 206.2667, 𝑥6 = 197.5001, dan selainnya bernilai 0. Itu berarti untuk memenuhi pesanan diperlukan rol sebanyak 48.5080 untuk pola pemotongan pertama, 206.2667 rol untuk pola pemotongan kelima, dan 197.5001 rol untuk pola pemotongan keenam. Dengan demikian, banyaknya rol jumbo yang digunakan sebanyak 452.2747 rol. Dari data yang sudah didapat menghasilkan jumlah rol bukan berupa bilangan bulat. Oleh karena itu, diperlukan suatu metode untuk memberikan solusi berupa bilangan bulat. Metode yang digunakan adalah first-fit decreasing.


Metode First-Fit Decreasing Pada iterasi ke-j dari metode ini yaitu menemukan pola pemotongan rol jumbo ke-j. Iterasi dimulai dengan sisa permintaan setelah jumlah rol dibulatkan ke ′ bawah yaitu 𝑏1′ , 𝑏2′ , … , 𝑏𝑚 . Pola pemotongan yang dihasilkan untuk setiap iterasi

yaitu 𝑏𝑖′ 𝑎𝑖 = 𝑚𝑖𝑛

(3.3)

𝑖−1

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤𝑖 ⌋ 𝑘=1

{

Untuk 𝑖 = 1,2, … , 𝑚, kemudian ganti setiap nilai 𝑏𝑖′ dengan 𝑏𝑖′ − 𝑎𝑖 dan lanjutkan proses iterasi ke-j+1.

Contoh 3.2 Mencari solusi bilangan bulat untuk contoh 3.1 didapatkan hasil Pola

Lebar rol

pemotongan

Banyak rol 135

108

93

42

1

2

0

0

0

48,5

2

0

2

0

2

206,27

3

0

1

2

0

197,5

ke-

Tabel 3.4: Tabel hasil yang diperoleh dengan menggunakan algoritma PSO


Karena solusi belum bernilai bilangan bulat, maka dengan menggunakan metode first-fit decreasing solusi diubah menjadi bilangan bulat. Pertama, semua solusi yang diperoleh dibulatkan ke bawah. Sehingga untuk pola 1 memerlukan 48 rol, pola 2 memerlukan 206 rol, dan pola 3 memerlukan 197 rol. Karena semua solusi dibulatkan ke bawah, maka jumlah produksi rol pesanan kurang atau sama dengan permintaan rol. Lebar Rol (𝑤𝑖 )

Permintaan (𝑏𝑖 )

Sisa (𝑏𝑖′ )

Produksi (⌊𝑥𝐵∗ ⌋)

135 cm

97 rol

96 rol

1 rol

108 cm

610 rol

609 rol

1 rol

93 cm

395 rol

394 rol

1 rol

42 cm

211 rol

412 rol

0 rol

Tabel 3.5: Tabel nilai solusi yang sudah dibulatkan ke bawah dan sisa produksinya

Iterasi 1 Diketahui 𝑏1′ = 1, 𝑏2′ = 1, 𝑏3′ = 1, 𝑏4′ = 0. 𝑎1 = 𝑚𝑖𝑛 {

𝑏1′ 1 1 = 𝑚𝑖𝑛 { = 𝑚𝑖𝑛 { = 1 ⌊300⁄135⌋ ⌊𝑟⁄𝑤1 ⌋ 2 𝑏2′

𝑎2 = 𝑚𝑖𝑛 {

1

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤2 ⌋ 𝑘=1

= 𝑚𝑖𝑛 {

1 1 = 𝑚𝑖𝑛 { = 1 ⌊(300 − 135.1)⁄108⌋ 1


𝑏3′ 𝑎3 = 𝑚𝑖𝑛 {

2

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤3 ⌋

= 𝑚𝑖𝑛 {⌊(300

1 − (135.1 + 108.1)⁄93⌋

𝑘=1

1 = 𝑚𝑖𝑛 { = 0 0 𝑏4′ 𝑎4 = 𝑚𝑖𝑛 {

3

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤4 ⌋ 𝑘=1

= 𝑚𝑖𝑛 {⌊(300

0 0 = 𝑚𝑖𝑛 { = 0 − (135.1 + 108.1 + 93.0)⁄42⌋ 1

Sehingga didapatkan 𝑏1′ = 0, 𝑏2′ = 0, 𝑏3′ = 1, 𝑏4′ = 0. Iterasi 2 𝑎1 = 𝑚𝑖𝑛 {

𝑏1′ 0 0 = 𝑚𝑖𝑛 { = 𝑚𝑖𝑛 { = 0 ⌊300⁄135⌋ ⌊𝑟⁄𝑤1 ⌋ 2 𝑏2′

𝑎2 = 𝑚𝑖𝑛 {

1

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤2 ⌋

= 𝑚𝑖𝑛 {

0 0 = 𝑚𝑖𝑛 { = 0 ⌊(300 − 135.0)⁄108⌋ 2

𝑘=1

𝑏3′ 𝑎3 = 𝑚𝑖𝑛 {

2

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤3 ⌋

= 𝑚𝑖𝑛 {⌊(300

1 − (135.0 + 108.0)⁄93⌋

𝑘=1

1 = 𝑚𝑖𝑛 { = 1 3 𝑏4′ 𝑎4 = 𝑚𝑖𝑛 {

3

⌊(𝑟 − ∑ 𝑤𝑘 𝑎𝑘 )⁄𝑤4 ⌋ 𝑘=1

= 𝑚𝑖𝑛 {⌊(300

0 0 = 𝑚𝑖𝑛 { = 0 − (135.0 + 108.0 + 93.1)⁄42⌋ 4


Sehingga didapatkan 𝑏1′ = 0, 𝑏2′ = 0, 𝑏3′ = 0, 𝑏4′ = 0. Proses iterasi diberhentikan karena semua pesanan sudah terpenuhi. Jadi, didapatkan 2 rol tambahan dengan 2 pola yang berbeda. Lebar rol pesanan Pola

Jumlah rol 135

108

93

42

1

2

0

0

0

48

2

0

2

0

2

206

3

0

1

2

0

197

4

1

1

0

0

1

5

0

0

1

0

1

TOTAL

453

Tabel 3.6: Tabel jumlah rol sesuai pola dari algoritma PSO dan algoritma FFD


BAB IV PENERAPAN ALGORITMA PARTICLE SWARM OPTIMIZATION UNTUK MASALAH PEMOTONGAN ROL KERTAS

Pada bab ini akan dijelaskan mengenai cara menggunakan aplikasi yang sudah dibuat berdasarkan algoritma Particle Swarm Optimization. Aplikasi ini dibuat dengan Graphical User Interface (GUI) MATLAB. Dengan adanya aplikasi ini dapat memudahkan perhitungan. Berikut penjelasan dan cara tentang aplikasi ini. Buka aplikasi GUI MATLAB yang sudah dibuat maka akan terlihat tampilan seperti berikut ini.

Gambar 4.1: Tampilan Menu Utama Program

69


Kemudian kita dapat menentukan banyak jenis rol yang dipesan berdasarkan lebarnya dengan cara mengetikkannya pada kolom yang tersedia.

Gambar 4.2: Tampilan program ketika dimasukkan data banyak rol dan lebar rol


Jika dipilih tombol tambah data, maka akan muncul tampilan seperti di bawah.

Gambar 4.3: Tampilan program ketika data tabel ditambah

Setelah itu, isi semua data tabel dengan banyak rol dan lebar rol yang diinginkan sesuai pesanan, kemudian tentukan panjang rol jumbo dengan cara


mengetikkannya pada kolom yang tersedia. Input data ini juga akan digunakan dalam proses perhitungan.

Gambar 4.4: Tampilan program ketika data tabel dan lebar rol sudah terisi


Setelah itu, tekan tombol ‘Lakukan Proses Perhitungan’ maka akan muncul wait baryang menunjukkan proses running dan iterasi.

Gambar 4.5: Tampilan untuk proses running dan iterasi


Tunggu beberapa saat, maka penyelesaian optimal akan muncul pada field yang telah tersedia.

Gambar 4.6: Hasil yang didapat berupa pola pemotongan, best function, best run, best variable, kesimpulan, grafik konvergensi, serta waktu perhitungan.


Proses diberhentikan setelah maximum run terpenuhi. Dari tampilan GUI dapat diketahui bahwa semua pesananan sudah terpenuhi serta hasil dari best fun adalah 452.2502 dan nilainya masih belum bulat karena nilai tersebut hanya merupakan suatu output dari pendekatan algoritma PSO yang akan berguna untuk mencari best variable yang akan digunakan sebagai input untuk diproses menggunakan algoritma First-fit decreasing (FFD) agar bernilai bulat. Setelah itu, kita akan mendapatkan pola secara utuh dimana pola-pola awal yang didapatkan dari best variable hasil perhitungan algoritma PSO sudah disesuaikan dan ditambahkan dengan pola-pola baru yang didapatkan dari algoritma FFD. Jadi, didapatkan 2 rol tambahan dengan 2 pola yang berbeda. Lebar rol pesanan Pola

Jumlah rol 135

108

93

42

1

1

1

0

1

97

2

0

2

0

2

157

3

0

1

2

0

197

4

0

2

0

0

1

5

0

0

1

0

1

TOTAL

453

Tabel 4.1: Tabel jumlah rol sesuai pola dari algoritma PSO dan algoritma FFD


BAB V PENUTUP

A.

Kesimpulan Masalah pemotongan kertas merupakan masalah penting pada proses

produksi selain untuk mendapatkan hasil pemotongan yang baik juga untuk meminimumkan produksi jumlah rol. Sehingga biaya produksi bahan baku juga menjadi minimum. Masalah ini juga memiliki berbagai kendala yang harus dipertimbangkan sehingga tidak mudah diselesaikan secara manual. Namun, pada makalah ini masalah ini diselesaikan dengan 2 metode yang berbeda. Pertama, memodelkan dan menyelesaikan masalah pemotongan kertas satu dimensi dengan metode program linear. Cara memodelkan masalah ini yaitu membuat suatu pola pemotongan dengan syarat sisa pemotongan kurang dari panjang pesanan minimum kemudian menyelesaikan model ini dengan program linear sehingga diperoleh kombinasi pola yang paling optimal. Dari penyelesaian yang didapat, solusi masih berupa pecahan, untuk membuat kemungkinan pola pemotongan sangat banyak, dan menghasilkan rol yang melebihi pesanan sehingga diperlukan suatu metode yang lebih efektif dalam menyelesaikan permasalahan ini. Dalam makalah ini, masalah diselesaikan dengan menggunakan perangkat lunak QM terlebih dahulu. Kedua, menggunakan metode heuristik dengan menggunakan algoritma Particle Swarm Optimization (PSO) untuk menyelesaikan masalah pemotongan. Dari penyelesaian yang didapat, terlihat bahwa solusi masih berupa pecahan sehingga diperlukan metode First Fit Decreasing untuk mengubah solusi ke dalam

76


bentuk bilangan bulat. Hasil perhitungan dengan PSO cukup akurat sehingga dapat dipergunakan untuk menyelesaikan masalah pemotongan persediaan kertas. Pada makalah ini juga terdapat aplikasi yang dibuat dengan GUI MATLAB untuk menyelesaikan masalah pemotongan kertas berdasarkan metode tersebut dimana hasil berupa jumlah rol. Aplikasi ini dibuat agar saat memasukkan data atau menampilkan data menjadi lebih mudah. Aplikasi ini dapat memproses data yang sudah dimasukkan sehingga perhitungan menjadi lebih cepat dan relatif mudah. B.

Saran Penulis menyadari penulisan ini masih banyak kekurangan. Oleh sebab itu,

penulis mengharapkan kelak akan ada yang melanjutkan penelitian ini. Pada makalah ini hanya dibahas algoritma PSO sebagai suatu metode pendekatan untuk mencari penyelesaian permasalahan pemotongan kertas berdimensi satu. Penulis berharap di penelitian selanjutnya metode ini dapat diperluas untuk menyelesaikan masalah pemotongan dua dan tiga dimensi. Pada makalah ini juga hanya terbatas pada pemotongan dari rol ke rol dan meminimumkan jumlah penggunaan rol, sehingga untuk penulisan selanjutnya dapat diperluas dengan pemotongan dari rol menjadi potongan kertas atau gabungan dari rol dan potongan kertas dengan ukuran tertentu serta dapat meminimumkan sisa dan pola yang dihasilkan.


DAFTAR PUSTAKA

Anton, Howard dan Chris Rorres. (2010). Elementary Linear Algebra: Applications version. Hoboken: John Wiley & Sons. Alam, Mahamad Nabab. (2016). ResearchGate. Codes in MATLAB for Particle Swarm Optimization. 1-4. Alam, Mahamad Nabab. (2016). ResearchGate. Particle Swarm Optimization: Algorithm and It’s Codes in MATLAB. 1-11. Bisschop, Johannes. (2016). AIMMS Optimization Modeling. AIIMS B.V. Chvatal, Vasek. (1983). Linear programming. New York: W. H. Freeman and Company. Eiselt, H.A. dan C.L. Sandblom. (2007). Linear Programming and its Applications. Verlag: Springer. Gilat, Amos. (2011). MATLAB An Introduction. Fourth Edition. Ohio: John Wiley and Sons, Inc. Ignizio, J. P. dan Cavalier T. M. (1994). Linear Programming. Mac Graw Hill Book Company, Inc. Lagha, Ghassen B. dkk. (2014). Particle Swarm Optimization Approach for Resolving Cutting Stock Problem: International Conference on Advanced Logistic and Transport. Mahadika, Rosa Ajeng. (2016). Penyelesaian Masalah Pemotongan Rol Kertas dengan Metode Penghasil Kolom. Yogyakarta: Jurusan Matematika USD.

78


Matousek, Jiri dan Bernd Gartner. (2007). Understanding and Using Linear Programming. Verlag: Springer. Parmar, Kashyap B. dkk. (2014). Cutting Stock Problem: A Survey of Evolutionary Computing Based Solution in 2014 International Conference on Green Computing Communication and Electrical Engineering. Putra, Antonius Rianditya. (2015). Penjadwalan Mata Kuliah Menggunakan Algoritma Particle Swarm Optimization. Yogyakarta: Jurusan Teknik Informatika USD. Sahyar. (2016). Algoritma & Pemrograman Menggunakan MATLAB (Matrix Laboratory). Jakarta: Kencana. Santosa, Budi dan Paul Willy. (2011). Metoda Metaheuristik Konsep dan Implementasi. Surabaya: Guna Widya. Shen, Xianjun dkk. (2007). A Heuristic Particle Swarm Optimization for Cutting Stock Problem Based on Cutting Pattern: ICCS. Siswanto. (2007). Operations Research Jilid 1. Jakarta: Erlangga. Susanta. (1996). Program Linear. Jakarta: Depdikbud. Suyanto.

(2010).

Algoritma

Optimasi

Deterministik

atau

Probabilistik.

Yogyakarta: Graha Ilmu. Taha, Hamdy A. (2011). Operations Reasearch An Introduction. Ninth Edition. New Jersey: Prentice Hall. Winston, Wayne L. (2004). Operations Research Applications and Algorithms. Fourth Edition. Toronto: Thomson Learning.


LAMPIRAN

1. Script ofun2.m 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.

function f=ofun2(x) co=[]; %fungsi obyektif atau fungsi tujuan (minimisasi) of=(x(1)-2)^2+(x(2)-3)^2; %kendala (semua kendala harus dikonversi ke dalam bentuk <=0) %jika tidak terdapat kendala maka baris kendala dihilangkan co(1)=(2*(x(1)))+(x(2))-4; %kendala dalam bentuk <=0 %mendefinisikan fungsi pinalti untuk setiap kendala for i=1:length(co) if co(i)>0 c(i)=1; else c(i)=0; end end penalty=10000; %nilai pinalti untuk tiap pelanggaran kendala f=of+penalty*sum(c); %fungsi fitness

2. Script Untitled2.m sebagai file program PSO utama 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

clc clear all close all %rng default LB=[0 0]; UB=[10 10];

%batas bawah dari variabel %batas atas dari variabel

%nilai parameter-parameter pso m=2; %dimensi yang merepresentasikan jumlah variabel n=30; %ukuran populasi wmax=0.9; %bobot inersia maksimum wmin=0.4; %bobot inersia minimum c1=2; %kemampuan individu (cognitive) c2=2; %pengaruh sosial (memory) %pso main program (program utama pso)dimulai maxite=100; %jumlah iterasi maksimum maxrun=10; %jumlah proses (run) maksimum yang dijalankan for run=1:maxrun

80


22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

run %awal inisialisasi pso for i=1:n for j=1:m x0(i,j)=round(LB(j)+rand()*(UB(j)-LB(j))); end end x=x0; %populasi awal v=0.1*x0; %kecepatan awal for i=1:n f0(i,1)=ofun2(x0(i,:)); end [fmin0,index0]=min(f0); pbest=x0; %nilai pbest awal gbest=x0(index0,:); %nilai gbest awal %akhir inisialisasi pso %algoritma pso dimulai ite=1; tolerance=1; while ite<=maxite && tolerance>10^-12 w=wmax-(wmax-wmin)*ite/maxite; %rumus bobot inersia %rumus pembaruan kecepatan pso for i=1:n for j=1:m v(i,j)=w*v(i,j)+c1*rand()*(pbest(i,j)-x(i,j))... +c2*rand()*(gbest(1,j)-x(1,j)); end end %rumus pembaruan posisi pso for i=1:n for j=1:m x(i,j)=x(i,j)+v(i,j); end end %menanganani pelannggaran batas for i=1:n for j=1:m if x(i,j)UB(j) x(i,j)=UB(j); end end end %menghitung fungsi fitness for i=1:n f(i,1)=ofun2(x(i,:)); end %memperbarui pbest dan fitness for i=1:n


78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126

if f(i,1)
%memperbarui gbest dan best fitness if fmin100; tolerance=abs(ffmin(ite-100,run)-fmin0); end %menampilkan hasil iterasi if ite==1 disp(sprintf('Iteration Best particle Objective fun')); end disp(sprintf('%8g %8g %8.4f',ite,index,fmin0)); ite=ite+1; end %algoritma pso berakhir gbest; fvalue=(gbest(1)-2)^2+(gbest(2)-3)^2; fff(run)=fvalue; rgbest(run,:)=gbest; disp(sprintf('-------------------------------------------')); end %pso main program (program utama pso) berakhir disp(sprintf('\n')); disp(sprintf('*******************************************')); disp(sprintf('Final Results------------------------------')); [bestfun,bestrun]=min(fff) best_variables=rgbest(bestrun,:) disp(sprintf('*******************************************')); %menampilkan grafik karakteristik konvergensi PSO plot(ffmin(1:ffite(bestrun),bestrun),'-k'); xlabel('Iteration'); ylabel('Fitness function value'); title('PSO convergence characteristic') %#############################################

3. Script ofun.m 1. 2.

%mencari partikel terbaik %menyimpan best fitness %menyimpan penghitungan iterasi

function f=ofun8(x)


3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

%co=[]; %fungsi obyektif atau fungsi tujuan (minimisasi) of=(x(1)-2)^2+(x(2)-3)^2; %kendala (semua kendala harus dikonversi ke dalam bentuk <=0) %jika tidak terdapat kendala maka baris kendala dihilangkan %c0(1)=2*x(1)+x(2)-4; %kendala dalam bentuk <=0 %mendefinisikan fungsi pinalti untuk setiap kendala penalty=0; f=of+penalty;

%karena tidak ada kendala %fungsi fitness

4. Script ofun3.m 1 function f=ofun3(x) 2 3 c0=[]; 4 5 %objective function (minimization) 6 of=(x(1))+(x(2))+(x(3))+(x(4))+(x(5))+(x(6))+(x(7))+(x(8))+(x(9)) +(x(10))+(x(11))+(x(12)); 7 8 %constraints (all constraints must be converted into <=0 type) 9 %if there is no constraints then comments all c0 lines below 10 c0(1)=395-(x(3))-(2*(x(6)))-(x(7))-(3*(x(9)))-(2*(x(10)))(x(11)); %<=0 type constraints 11 c0(2)=97-(2*(x(1)))-(x(2))-(x(3))-(x(4)); 12 c0(3)=610-(x(2))-(2*(x(5)))-(x(6))-(x(7))-(x(8)); 13 c0(4)=211-(x(2))-(x(3))-(3*(x(4)))-(2*(x(5)))-(2*(x(7)))(4*(x(8)))-(2*(x(10)))-(4*(x(11)))-(7*(x(12))); 14 15 %defining penalty for each constraint 16 for i=1:length(c0) 17 if c0(i)>0 18 c(i)=1; 19 else 20 c(i)=0; 21 end 22 end 23 24 penalty=10000; %penalty on each constraints violation 25 f=of+penalty*sum(c); %fitness function

5. Script Untitled3.m sebagai file program PSO utama 1 2 3 4 5

clc clear all close all %rng default


6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

A=[0,600] LB=zeros(1,m); LB(1,:)=A(1); UB=zeros(1,m); UB(1,:)=A(2); display(LB) display(UB)

%lower bounds of variables %upper bounds of variables

%pso parameters values m=12; %number of variables n=100; %population size wmax=0.9; %inertia weight wmin=0.4; %inertia weight c1=2; %acceleration factor c2=2; %accelaration factor %pso main program maxite=1000; %set maximum number of iteration maxrun=10; %set maximum number of runs need to be for run=1:maxrun run %pso initialization for i=1:n for j=1:m x0(i,j)=round(LB(j)+rand()*(UB(j)-LB(j))); end end x=x0; %initial population v=0.1*x0; %initial velocity for i=1:n f0(i,1)=ofun3(x0(i,:)); end [fmin0,index0]=min(f0); pbest=x0; %initial pbest gbest=x0(index0,:); %initial gbest %pso initialization %pso algorithm ite=1; tolerance=1; while ite<=maxite && tolerance>10^-12 w=wmax-(wmax-wmin)*ite/maxite; %update inertial weight %pso velocity updates for i=1:n for j=1:m v(i,j)=w*v(i,j)+c1*rand()*(pbest(i,j)-x(i,j))... +c2*rand()*(gbest(1,j)-x(1,j)); end end %pso position update for i=1:n for j=1:m x(i,j)=x(i,j)+v(i,j);


62 end 63 end 64 65 %handling boundary violations 66 for i=1:n 67 for j=1:m 68 if x(i,j)UB(j) 71 x(i,j)=UB(j); 72 end 73 end 74 end 75 76 %evaluating fitness 77 for i=1:n 78 f(i,1)=ofun3(x(i,:)); 79 end 80 81 %updating pbest and fitness 82 for i=1:n 83 if f(i,1)100; 101 tolerance=abs(ffmin(ite-100,run)-fmin0); 102 end 103 104 %displaying iterative results 105 if ite==1 106 disp(sprintf('Iteration Best particle Objective fun')); 107 end 108 disp(sprintf('%8g %8g %8.4f',ite,index,fmin0)); 109 ite=ite+1; 110 end 111 112 %pso algorithm 113 gbest; 114 fvalue=(gbest(1))+(gbest(2))+ (gbest(3))+(gbest(4))+ (gbest(5))+(gbest(6))+ (gbest(7))+(gbest(8))+ (gbest(9))+(gbest(10))+ (gbest(11))+(gbest(12)); 115 fff(run)=fvalue;


116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134

rgbest(run,:)=gbest; disp(sprintf('--------------------------------------------')); end %pso main program disp(sprintf('\n')); disp(sprintf('********************************************')); disp(sprintf('Final Results-------------------------------')); [bestfun,bestrun]=min(fff) best_variables=rgbest(bestrun,:) disp(sprintf('********************************************')); toc %PSO convergence characteristic plot(ffmin(1:ffite(bestrun),bestrun),'-k'); xlabel('Iteration'); ylabel('Fitness function value'); title('PSO convergence characteristic') %#############################################

6. Kode fungsi obyektif (fungsi tujuan) pada GUI function f=fungsiObyektif(x, pola, banyakRol) %objective function (minimization) of = repmat(x',1,size(pola,2)) .* pola; %Hitung nilai f dengan menjumlahkan semua nilai fungsi obyektif dari masing-masing dimensi f = sum(sum(of)); %konstrain global %Jika jumlah nilai fungsi obyektif kurang dari atau terlalu jauh melebihi parameter banyak rol yang diperlukan %Maka tambahkan nilai penalti pada nilai f, yaitu sejumlah banyak rol pada semua dimensi %Cara penambahan nilai penalti dapat diganti sesuai kebutuhan if (f < (sum(banyakRol)) || (f > (sum(banyakRol) + round((max(banyakRol)+min(banyakRol))/2)))) f = f + sum(banyakRol); end %konstrain lokal %Lakukan perhitungan pada masing-masing nilai fungsi obyektif for i=1:size(of,2) %Jika jumlah nilai fungsi obyektif pada dimensi ini kurang dari atau terlalu jauh melebihi parameter banyak rol dari masingmasing dimensi %Maka tambahkan nilai penalti pada nilai f, yaitu sejumlah banyak rol pada dimensi tersebut %Cara penambahan nilai penalti dapat diganti sesuai kebutuhan


if (sum(of(:,i)) < (banyakRol(i))) || (sum(of(:,i)) > round(banyakRol(i) + ((max(banyakRol)+min(banyakRol))/2))) f = f + banyakRol(i); end end

7. Kode PSO pada GUI function [bestfun, bestrun, best_variables, jumlahIterasiConvergence, nilaiConvergence] = PSO(input, pola) %Dimensi adalah sesuai dengan banyak pola pemotongan yang telah dihitung dimensi=size(pola,1); %Batas bawah adalah selalu 0 karena tidak mungkin pemesanan dilakukan dengan angka negatif batasBawah = zeros(1,dimensi); %Batas atas adalah sesuai dengan angka tertinggi yang terdapat pada parameter banyak rol batasAtas = zeros(0,dimensi); for i=1:dimensi batasAtas(1,i) = max(input(:,1)); end %% Perhitungan utama pada algoritma PSO %pso parameters values %----------------------------------------------------------------n=100; %population size wmax=0.9; %inertia weight wmin=0.4; %inertia weight c1=2; %acceleration factor c2=2; %accelaration factor %----------------------------------------------------------------%pso main program %----------------------------------------------------------------%Memulai proses perhitungan wb = waitbar(0,'Sedang memproses data ...'); set(wb, 'Position', [300 100 270 56]); maxite=1000; %set maximum number of iteration maxrun=10; %set maximum number of runs need to be for run=1:maxrun %pso initialization %------------------------------------------------------------for i=1:n x0(i,:) = inisialisasi(input, pola, dimensi, batasAtas, batasBawah); end for i=1:n f0(i,1) = fungsiObyektif(x0(i,:), pola, input(:,1));


end x=x0; %initial population v=0.1*x0; %initial velocity [fmin0,index0]=min(f0); pbest=x0; %initial pbest gbest=x0(index0,:); %initial gbest %------------------------------------------------------------%pso algorithm %------------------------------------------------------------ite=1; tolerance=1; while ite<=maxite && tolerance>10^-4 %Tampilkan waitbar untuk iterasi (hanya sebagai penanda visual) waitbar(ite/maxite, wb, ['Sedang memproses PSO ... ' num2str(ite) ' dari ' num2str(maxite)]) %update inertial weight w=wmax-(wmax-wmin)*ite/maxite; %pso velocity updates for i=1:n for j=1:dimensi v(i,j)=w*v(i,j)+c1*rand()*(pbest(i,j)-x(i,j))... +c2*rand()*(gbest(1,j)-x(1,j)); end end %pso position update for i=1:n for j=1:dimensi x(i,j)=x(i,j)+v(i,j); end end %handling boundary violations for i=1:n for j=1:dimensi if x(i,j)batasAtas(j) x(i,j)=batasAtas(j); end end %objective function (minimization) of = repmat(x(i,:)',1,size(pola,2)) .* pola; %Lakukan perhitungan pada masing-masing nilai fungsi obyektif for j=1:size(of,2) %Jika jumlah nilai fungsi obyektif pada dimensi ini kurang dari parameter banyak rol dari masing-masing dimensi maka posisi yang baru dianggap tidak valid,dan posisi partikel ini diganti dengan posisi partikel terbaik.


if (sum(of(:,j)) < (input(j,1))) %x(i,:) = inisialisasi(input,pola,dimensi,batasAtas,batasBawah); x(i,:) = gbest; break end end end %evaluating fitness for i=1:n f(i,1)=fungsiObyektif(x(i,:), pola, input(:,1)); end %updating pbest and fitness for i=1:n if f(i,1)
%finding out the best particle %storing best fitness %storing iteration count

%updating gbest and best fitness if fmin100; tolerance=abs(ffmin(ite-100,run)-fmin0); end %displaying iterative results % if ite==1 % disp(sprintf('Iteration Best particle Objective fun')); % end % disp(sprintf('%8g %8g %8.4f',ite,index,fmin0)); ite=ite+1; end %------------------------------------------------------------fvalue=0; for a=1:dimensi fvalue=fvalue+gbest(a); end fff(run)=fvalue; rgbest(run,:)=gbest; disp(sprintf('------------------------------------------'));

% end delete(wb); %-----------------------------------------------------------------


% disp(sprintf('\n')); %disp(sprintf('***********************************************')); % disp(sprintf('Final Results---------------------------------')); [bestfun,bestrun]=min(fff); best_variables=rgbest(bestrun,:); jumlahIterasiConvergence = ffite(bestrun); nilaiConvergence = ffmin(1:jumlahIterasiConvergence,bestrun); %disp(sprintf('***********************************************')); % toc %############################################# end %% fungsi untuk melakukan inisialisasi data function x0 = inisialisasi(input, pola, dimensi, batasAtas, batasBawah) isSelesai = false; while ~isSelesai for j=1:dimensi %Tentukan nilai acak antara 0 sampai dengan 1 %Jika nilai acak bernilai kurang dari 0.5, maka nilai variable untuk dimensi tersebut adalah 0 %Jika tidak, maka tentukan nilai acak diantara batas atas dan batas bawah dimensi tersebut if rand() < 0.5 x0(j) = 0; else x0(j)=round(batasBawah(j)+rand()*(batasAtas(j)-batasBawah(j))); end end %objective function (minimization) of = repmat(x0',1,size(pola,2)) .* pola; %Lakukan perhitungan pada masing-masing nilai fungsi obyektif isDiulang = false; for j=1:size(of,2) %Jika jumlah nilai fungsi obyektif pada dimensi ini kurang dari parameter banyak rol dari masing-masing dimensi maka posisi yang baru ini dianggap tidak valid,sehingga ulangi perhitungan untuk mendapatkan posisi yang lain if (sum(of(:,j)) < (input(j,1))) isDiulang = true; break end end if isDiulang continue end %Jika posisi acak sudah valid, maka proses inisialisasi telah selesai isSelesai = true; end


end

8. Kode FFD pada GUI function [output_best_variables, output_pola] = FFD(best_variables, pola, banyakRol, lebarRol, lebarRolJumbo) %Simpan nilai hasil pembulatan kebawah untuk setiap jawaban nilai variabel yang tersedia pembulatan_best_variables = fix(best_variables); %Hitung jumlah produksi rol dari masing-masing data menggunakan nilai variabel hasil pembulatan of = repmat(pembulatan_best_variables',1,size(pola,2)) .* pola; produksiRol = []; for i=1:size(of,2) produksiRol(i) = sum(of(:,i)); end %Hitung sisa rol dari hasil pengurangan antara banyak rol permintaan dan produksi rol hasil pembulatan %Jika jumlah produksi sudah melebihi banyak rol permintaan, maka sisa rol adalah 0 sisaRol = []; for i=1:size(of,2) if banyakRol(i) < produksiRol(i) sisaRol(i) = 0; else sisaRol(i) = round(banyakRol(i)-produksiRol(i)); end end %Lakukan perhitungan penyesuaian sampai tidak ada sisa rol. polaBaru = []; idxPolaBaru = 1; isSelesai = false; while ~isSelesai a = []; %Lakukan perhitungan pada masing-masing data sisa rol for i=1:size(sisaRol,2); %Hitung Swa=sum(wk*ak) Swa = 0; if i > 1 for j=1:size(a,2) Swa = Swa + lebarRol(j)*a(j); end end %nilai pertama adalah sesuai dengan sisa rol


nilaiPertama = sisaRol(i); %nilai kedua adalah (lebarRolJumbo - Swa) / lebarRol nilaiKedua = fix((lebarRolJumbo - Swa) / lebarRol(i)); %a = nilai minimal dari kedua nilai diatas a(i) = min(nilaiPertama, nilaiKedua); end %Masukkan a sebagai pola tambahan yang baru polaBaru(idxPolaBaru,:) = a; idxPolaBaru = idxPolaBaru+1; %Hitung sisa rol yang baru setelah dikurangi a sisaRol = sisaRol-a; %Jika tidak ada lagi sisa rol,maka tambahkan angka 1 sebanyak jumlah pola tambahan setelah best variabel masukkan pola tambahan ke dalam variabel pola dan perhitungan FFD telah selesai if sum(sisaRol) <= 0 output_best_variables = [pembulatan_best_variables ones(1,size(polaBaru,1))]; output_pola = [pola; polaBaru]; isSelesai = true; end end

9. Kode Main GUI function varargout = mainGUI(varargin) % MAINGUI MATLAB code for mainGUI.fig % MAINGUI, by itself, creates a new MAINGUI or raises the existing % singleton*. % % H = MAINGUI returns the handle to a new MAINGUI or the handle to % the existing singleton*. % % MAINGUI('CALLBACK',hObject,eventData,handles,...) calls the local % function named CALLBACK in MAINGUI.M with the given input arguments. % % MAINGUI('Property','Value',...) creates a new MAINGUI or raises the % existing singleton*. Starting from the left, property value pairs are % applied to the GUI before mainGUI_OpeningFcn gets called. An % unrecognized property name or invalid value makes property application % stop. All inputs are passed to mainGUI_OpeningFcn via varargin. %


% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one % instance to run (singleton)". % % See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help mainGUI % Last Modified by GUIDE v2.5 02-Jan-2017 23:58:19 % Begin initialization code - DO NOT EDIT gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @mainGUI_OpeningFcn, ... 'gui_OutputFcn', @mainGUI_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1}); end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else gui_mainfcn(gui_State, varargin{:}); end % End initialization code - DO NOT EDIT

% --- Executes just before mainGUI is made visible. function mainGUI_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn. % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % varargin command line arguments to mainGUI (see VARARGIN) % Choose default command line output for mainGUI handles.output = hObject; % a = axes('Position', [ 0 0 1 1], 'Units', 'Normalized'); % imshow('bg.png','Parent',a); % Update handles structure guidata(hObject, handles); btnHapusTabel_Callback(handles.btnHapusTabel, eventdata, handles) axes(handles.imgPlot); cla(gca, 'reset'); set(gca,'XTick',[],'YTick',[]); set(handles.txtHasilPerhitungan,'String','');


movegui(gcf, 'center'); % UIWAIT makes mainGUI wait for user response (see UIRESUME) % uiwait(handles.figure1); % --- Outputs from this function are returned to the command line. function varargout = mainGUI_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT); % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % Get default command line output from handles structure varargout{1} = handles.output; %Fungsi untuk memastikan sebuah input merupakan angka atau bukan function b = isAngka(n) if (isnumeric(n)) b=1; else tmp = str2num(n); b=~isempty(tmp); end % --- Executes on button press in btnTambahData. function btnTambahData_Callback(hObject, eventdata, handles) % hObject handle to btnTambahData (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) banyakRol = get(handles.txtBanyakRol,'String'); if (~isAngka(banyakRol)) message = sprintf('Banyak Rol harus dalam bentuk angka!'); uiwait(msgbox(message)); return end if str2num(banyakRol) <= 0 message = sprintf('Banyak Rol harus bernilai positif!'); uiwait(msgbox(message)); return end if str2num(banyakRol)~=fix(str2num(banyakRol)) message = sprintf('Banyak Rol harus dalam bentuk bilangan bulat!'); uiwait(msgbox(message)); return end lebarRol = get(handles.txtLebarRol,'String');


if (~isAngka(lebarRol)) message = sprintf('Lebar Rol harus dalam bentuk angka!'); uiwait(msgbox(message)); return end if str2num(lebarRol) <= 0 message = sprintf('Lebar Rol harus bernilai positif!'); uiwait(msgbox(message)); return end if str2num(lebarRol)~=fix(str2num(lebarRol)) message = sprintf('Lebar Rol harus dalam bentuk bilangan bulat!'); uiwait(msgbox(message)); return end data = get(handles.tblData,'Data'); jumlahData = size(data,1)+1; if jumlahData == 1 dataBaru = num2cell(data); else dataBaru = data; end dataBaru{jumlahData,1} = banyakRol; dataBaru{jumlahData,2} = lebarRol; set(handles.tblData,'Data',dataBaru); set(handles.txtBanyakRol,'String',''); set(handles.txtLebarRol,'String','');

% --- Executes on button press in btnHapusTabel. function btnHapusTabel_Callback(hObject, eventdata, handles) % hObject handle to btnHapusTabel (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) set(handles.txtBanyakRol,'String',''); set(handles.txtLebarRol,'String',''); set(handles.txtLebarRolJumbo,'String',''); set(handles.tblData,'Data','');

function txtLebarRolJumbo_Callback(hObject, eventdata, handles) % hObject handle to txtLebarRolJumbo (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA)


% Hints: get(hObject,'String') returns contents of txtLebarRolJumbo as text % str2double(get(hObject,'String')) returns contents of txtLebarRolJumbo as a double % --- Executes during object creation, after setting all properties. function txtLebarRolJumbo_CreateFcn(hObject, eventdata, handles) % hObject handle to txtLebarRolJumbo (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows. % See ISPC and COMPUTER. if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end % --- Executes on button press in btnProses. function btnProses_Callback(hObject, eventdata, handles) % hObject handle to btnProses (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) data = get(handles.tblData,'Data'); jumlahData = size(data,1); if jumlahData <= 0 message = sprintf('Masukkan data terlebih dahulu!'); uiwait(msgbox(message)); return end lebarRolJumbo = get(handles.txtLebarRolJumbo,'String'); if (~isAngka(lebarRolJumbo)) message = sprintf('Lebar Rol Jumbo harus dalam bentuk angka!'); uiwait(msgbox(message)); return end if str2num(lebarRolJumbo) <= 0 message = sprintf('Lebar Rol Jumbo harus bernilai positif!'); uiwait(msgbox(message)); return end if str2num(lebarRolJumbo)~=fix(str2num(lebarRolJumbo)) message = sprintf('Lebar Rol Jumbo harus dalam bentuk bilangan bulat!'); uiwait(msgbox(message));


return end lebarRolJumbo = str2num(lebarRolJumbo); for i=1:jumlahData if str2num(data{i,2}) > lebarRolJumbo message = sprintf('Masukkan data terlebih dahulu!'); uiwait(msgbox(message)); return end end %% Proses pencarian pola pemotongan sesuai input data %Memulai perhitungan waktu tic %Input adalah sesuai dengan data yang telah diinputkan input = str2double(data); %Jumlah konstrain adalah sesuai dengan banyak data yang telah diinputkan jumlahKonstrain = jumlahData; %Lakukan pengurutan input dari lebar rol tertinggi ke lebar rol terendah (untuk memudahkan cara perhitungan) [~, idxTerurut] = sort(input(:,2), 'descend'); input = input(idxTerurut,:); %Batas bawah adalah selalu 0 karena tidak mungkin pemotongan kertas dilakukan dengan angka negatif batasBawah = zeros(1,jumlahKonstrain); %Batas atas adalah sesuai dengan angka bulat dari lebar rol jumbo / lebar rol dari masing-masing data batasAtas = zeros(0,jumlahKonstrain); for i=1:jumlahKonstrain batasAtas(1,i) = fix(lebarRolJumbo / input(i,2)); end %Untuk menampung daftar pola pemotongan yang diperoleh pola = zeros(0,jumlahKonstrain); idxPola = 1; %Untuk mencari semua nilai kemungkinan dari masing-masing variabel nilaiVariabel = batasAtas; idxData = jumlahKonstrain; %Lakukan perhitungan sampai perhitungan dihentikan isSelesai = false; while ~isSelesai %Hitung jumlah lebar rol dengan perkalian nilai variabel dengan lebar rol masing-masing data


jumlahLebarRol = sum(nilaiVariabel .* input(:,2)'); %Jika jumlah lebar rol masih berada dalam batas lebar rol jumbo, dan sisa rol tidak lebih dari lebar rol terendah %maka masukkan nilai variabel ini sebagai pola if jumlahLebarRol <= lebarRolJumbo && ((lebarRolJumbojumlahLebarRol) < min(input(:,2))) pola(idxPola,:) = nilaiVariabel; idxPola = idxPola+1; end %Kurangi nilai variabel pada indeks data terpilih dengan angka 1 nilaiVariabel(idxData) = nilaiVariabel(idxData)-1; %Jika nilai variabel pada indeks data terpilih kurang dari 0 if nilaiVariabel(idxData) < 0 %Cari indeks data terakhir yang memiliki nilai variabel lebih dari 0 idxData = find(nilaiVariabel > 0, 1, 'last'); %Jika semua nilai variabel sudah bernilai 0, maka perulangan pencarian pola pemotongan sudah selesai tmp = find(nilaiVariabel<=0); if size(tmp,2) >= jumlahKonstrain isSelesai = true; break; end %Kurangi nilai variabel pada indeks data terpilih dengan angka 1 nilaiVariabel(idxData) = nilaiVariabel(idxData)-1; %Lakukan perhitungan untuk masing-masing indeks data setelah indeks data terpilih %Kembalikan nilai variabelnya agar kembali menjadi batas atas indeks data tersebut, %Kemudian kembalikan indeks data menjadi indeks data terakhir %Sehingga perhitungan kembali diulang dari nilai yang paling tinggi dari indeks data yang paling akhir. for i=idxData+1:jumlahKonstrain nilaiVariabel(i) = batasAtas(i); end idxData = jumlahKonstrain; end end %% Proses perhitungan menggunakan algoritma PSO [bestfun, bestrun, best_variables, jumlahIterasiConvergence, nilaiConvergence] = PSO(input, pola); %% Proses penyesuaian nilai variabel apabila terdapat jawaban yang bukan merupakan angka bulat


%Cek apakah terdapat angka desimal pada jawaban nilai best variable isDesimal = false; for i=1:size(best_variables,2) if fix(best_variables(1,i)) ~= best_variables(1,i) isDesimal = true; break; end end % Lakukan penyesuaian jawaban nilai variabel menggunakan metode First-Fit Decreasing apabila diperlukan if isDesimal [best_variables, pola] = FFD(best_variables, pola, input(:,1), input(:,2), lebarRolJumbo); end %% Tampilkan kesimpulan dan grafik pada layar %Catat hasil akhir waktu perhitungan setelah melalui proses PSO (dan First-Fit Decreasing) waktuPerhitungan = toc; teks = cell(1); idxTeks = 1; teks(idxTeks) = {'Pola pemotongan yang digunakan adalah'}; idxTeks = idxTeks + 1; %Header konstrain (co1, co2, dst) tmpTeks = ' '; for i=1:size(pola,2) co = ['co' num2str(i)]; tmpTeks = [tmpTeks blanks(5 - length(num2str(co))) co ', ']; end teks(idxTeks) = mat2cell(tmpTeks, 1); idxTeks = idxTeks + 1; %Pola pemotongan yang ditemukan for i=1:size(pola,1) x = ['x' num2str(i)]; tmpTeks = [x blanks(5 - length(num2str(x)))]; for j=1:size(pola,2) nilai = [num2str(pola(i,j))]; tmpTeks = [tmpTeks blanks(5 - length(num2str(nilai))) nilai ', ']; end teks(idxTeks) = mat2cell(tmpTeks, 1); idxTeks = idxTeks + 1; end tmpTeks = '';


for i=1:size(best_variables,2) tmpTeks = [tmpTeks num2str(best_variables(1,i), '%i') ', ']; end %bestfun, bestrun, dan best variables teks(idxTeks) = {['']}; idxTeks = idxTeks + 1; teks(idxTeks) = {['bestfun = ' num2str(bestfun, '%1.4f')]}; idxTeks = idxTeks + 1; teks(idxTeks) = {['bestrun = ' num2str(bestrun)]}; idxTeks = idxTeks + 1; teks(idxTeks) = {['best variable = ' tmpTeks]}; idxTeks = idxTeks + 1; %Kesimpulan nilai variabel dari masing-masing pola pemotongan teks(idxTeks) = {['']}; idxTeks = idxTeks + 1; teks(idxTeks) = {'Kesimpulan dari best variable: '}; idxTeks = idxTeks + 1; for i=1:size(best_variables,2) if round(best_variables(1,i)) > 0 teks(idxTeks) = {['Pola ' num2str(i) blanks(5 length(num2str(i))) ' bernilai ' num2str(best_variables(1,i), '%i')]}; idxTeks = idxTeks + 1; end end teks(idxTeks) = {['']}; idxTeks = idxTeks + 1; teks(idxTeks) = {['Banyak rol jumbo yang digunakan = ' num2str((sum(best_variables)), '%i') ' rol']}; idxTeks = idxTeks + 1; %Total lebar rol dan jumlah rol jumbo yang diperlukan %objective function (minimization) of = repmat(best_variables',1,size(pola,2)) .* pola; totalLebarRol = 0; for i=1:size(of,2) totalLebarRol = totalLebarRol + sum(of(:,i)) * input(i,2); teks(idxTeks) = {['Lebar rol ' num2str(input(i,2)) blanks(5 length(num2str(input(i,2)))) ' berjumlah ' num2str(sum(of(:,i)), '%i') ' rol']}; idxTeks = idxTeks + 1; end %teks(idxTeks) = {['Total lebar rol = ' num2str(totalLebarRol, '%i') ' cm']}; idxTeks = idxTeks + 1;


JumlahRolHasil = totalLebarRol/lebarRolJumbo; if JumlahRolHasil > fix(JumlahRolHasil) JumlahRolHasil = fix(JumlahRolHasil)+1; end %teks(idxTeks) = {['Banyak rol jumbo yang dihasilkan = ' num2str(JumlahRolHasil, '%i') ' rol']}; idxTeks = idxTeks + 1; %Waktu perhitungan teks(idxTeks) = {['']}; idxTeks = idxTeks + 1; teks(idxTeks) = {['Waktu perhitungan = ' num2str(waktuPerhitungan, '%1.4f') ' detik']}; idxTeks = idxTeks + 1; set(handles.txtHasilPerhitungan,'String', teks); %Tampilan grafik axes(handles.imgPlot) cla(gca, 'reset'); plot(nilaiConvergence,'-k'); %set axis limits [xmin,xmax,ymin,ymax] axis([0,jumlahIterasiConvergence,min(nilaiConvergence),max(nilaiCo nvergence)]) xlabel('Iterasi'); ylabel('Nilai Fungsi'); title('PSO convergence')

ALGORITMA PARTICLE SWARM OPTIMIZATION DAN TERAPANNYA DALAM MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS MAKALAH

Recommend Documents