Amijaya, FidiaDenyTisna (2013) Hybrid Algoritma Greedy - Particle Swarm Optimization - Algoritma Genetika (Hybrid GPSOGA). Magister thesis, Universitas Brawijaya.
Abstract
Algoritma Greedy adalah algoritma yang berdasarkan penyelesaian masalah secara heuristik yang membuat pilihan optimal lokal di setiap langkahnya dengan harapan menemukan solusi optimal global. Pada beberapa masalah, strategi Greedy tidak dapat menghasilkan solusi umum yang optimal, namun algoritma Greedy dapat menemukan solusi optimal lokal yang mendekati solusi optimal global dalam waktu yang wajar. Particle Swarm Optimization (PSO) adalah metode komputasi yang mengoptimalkan masalah secara iteratif dan berusaha untuk meningkatkan calon solusi dengan ukuran yang telah ditentukan. PSO mengoptimalkan suatu masalah dengan membangkitkan satu populasi yang berisi calon solusi (disebut juga partikel) dan menggerakkan partikel ini mengelilingi ruang pencarian sesuai dengan formula matematika sederhana yang disebut posisi partikel dan kecepatan. Tiap pergerakan partikel akan dipengaruhi oleh posisi lokal terbaik ( pbest ) dan juga dibimbing menuju ke posisi terbaik ( gbest ) di ruang pencarian. Pergerakan tersebut diperbarui sesuai dengan posisi yang lebih baik yang ditemukan oleh partikel lain dengan harapan mampu menggerakkan partikel pada solusi terbaik. Jika posisi partikel awal berkumpul disuatu tempat, maka kesempatan partikel untuk menemukan solusi terbaik akan semakin kecil karena partikel – partikel tersebut hanya berbagi informasi ditempat tersebut. Algoritma Genetika adalah sebuah pencarian heuristik yang meniru proses evolusi alam seperti keturunan, mutasi, seleksi, dan pindah silang. Dalam prosesnya, algoritma Genetika memiliki kesempatan yang besar untuk menemukan solusi global karena terdapat operator pindah silang dan mutasi dalam algoritmanya. Tetapi algoritma Genetika membutuhkan waktu yang lebih lama untuk melakukan pindah silang dan mutasi. Pada tesis ini, akan dibahas proses penggabungan algoritma berdasarkan tiga algoritma tersebut dengan harapan kelebihan tiap-tiap algoritma bisa saling menutupi kelemahannya dan masalah multidimensional Knapsack 0-1 akan digunakan sebagai masalah ujinya. Hasilnya, algoritma baru mempunyai hasil yang lebih baik ketiga algoritma penyusunnya.
English Abstract
Greedy algorithm is an algorithm that based on problem solving heuristic which making the locally optimal choice at each stage with the hope of finding a global optimal solution. In many problem, Greedy strategy can`t produce an general optimal solution, nonetheless a Greedy algorithm can find locally optimal solution that approximate a global optimal solution in a reasonable time. Particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively and trying to improve a candidate solution in given measure way. PSO optimizes a problem by having a population that contain candidate solutions (dubbed as particles) and moving these particles around in the search space according to simple mathematical formulae that called the particle`s position and velocity. Each particle`s movement is influenced by its local best known position (pbest) and is also guided toward the best known position (gbest) in the search space, which are updated as better positions are found by other particles with the hope it can move the particles toward the best solution. If the particles gather in one place, so the chance to find the best solution is small because the particles only share their information at that place. Genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution, such as inheritance, mutation, selection, and crossover. In its process, genetic algorithm have a large chance to find a global solution because it have crossover and mutation operators. But this algorithm may spend at most of its computational time to perform crossover and mutation. In this thesis, will explain the process of making hybrid algorithm based on that three algorithm with the hope the advantages of each algorithm can cover the disadvantages each algorithm and multidimensional knapsack problem 0-1 will be used as test problem. The result is the new algorithm have better solution than the three algorithms.
| Item Type: | Thesis (Magister) |
|---|---|
| Identification Number: | TES/519.62/AMI/h/041307709 |
| Subjects: | 500 Natural sciences and mathematics > 519 Probabilities and applied mathematics > 519.6 Mathematical optimization |
| Divisions: | S2/S3 > Magister Matematika, Fakultas MIPA |
| Depositing User: | Endro Setyobudi |
| Date Deposited: | 08 Nov 2013 09:51 |
| Last Modified: | 08 Nov 2013 09:51 |
| URI: | http://repository.ub.ac.id/id/eprint/157489 |
Actions (login required)
 |
View Item |