Implementasi algoritma genetik paralel berbasiskan Parallel Virtual Machine (PVM) dalam lingkungan jaringan komputer

SARMAN, Prof. Adhi Susanto, M.Sc.,Ph.D

2005 | Tesis | S2 Teknik Elektro

Algoritma genetik (GA) adalah suatu teknik pencarian yang banyak digunakan untuk penyelesaian banyak kasus. GA sekuensial memberikan dua pilihan, mendapatkan solusi yang baik atau kebutuhkan waktu eksekusi singkat. GA mempunyai derajat keparalelan tinggi, sehingga untuk mengatasi kendala waktu eksekusi pada GA ditempuh dengan proses paralelisasi (Parallel Genetic Algorithm, PGA) dalam lingkungan PVM (Parallel Virtual Machine) untuk menyelesaikan banyak kasus. Ada sejumlah metode pemaralelan GA guna meningkatkan kecepatan komputasi. Model paralelisasi GA dapat diklasifikasikan dalam global PGA, migrasi PGA, dan difusi PGA. Pada penelitian ini digunakan model Global PGA atau yang sering disebut model master-slave. Master melakukan inisialisasi populasi dan menyimpannya, sedang slave melaksanakan operasi genetik (crossover dan mutasi) dan evaluasi fitness. Untuk membuktikan hipotesis penelitian digunakan kasus Traveling Salesman Problem (TSP). Global PGA terbukti mampu memberikan solusi yang lebih baik berupa waktu eksekusi yang lebih pendek dibanding dengan algoritma genetik sekuensial dengan jumlah generasi yang sama.

Genetic Algorithms (GA’s) are powerful search techniques to solve complex problems in many study fields. With a sequential GA, we have to choose between getting a good result with a high confidence or paying a reasonally low computation cost. GA’s are easy to parallelize, so utilized Parallel Genetic Algorithms (PGA’s) under the PVM (parallel virtual machine) to solve many problems at hand. There are a number of GA-based parallel methods to elevate the computational speed. The methods of parallelization can be classified as Global PGA, Migration PGA, and Diffusion PGA. This research used Global PGA or Master-slave parallelization, where the master stored the population and the slaves evaluated the fitness function, apply mutation and crossover. To compare the computation costs of PGA and the sequential GA, we took TSPs (Traveling Salesman Problems) as examples to test. The Global PGA gave better results than the sequential GA under the same generation set.

Kata Kunci : Algoritma Genetik Paralel,PVM,Jaringan Komputer