PENERAPAN KOMPUTASI PARALEL PADA ALGORITME GENETIKA UNTUK PENCARIAN NILAI BOBOT JARINGAN SYARAF TIRUAN YANG OPTIMAL

EKO DWI NUGROHO, Dr. Ing. Reza Pulungan, S.Si., M.Sc.; Moh. Edi Wibowo, M.Kom., Ph.D.

2017 | Tesis | S2 Ilmu Komputer

Algoritma genetika merupakan pendekatan optimasi evolusi berbasis populasi dan ini telah digunakan untuk melatih jaringan syaraf tiruan. Ketika sejumlah besar individu membuat populasi, namun, waktu komputasi dari algoritma sering menjadi sangat panjang. Komputasi paralel merupakan teknik yang potensial dapat digunakan untuk mengatasi masalah ini. Penelitian ini menyelidiki penerapan algoritma genetika paralel untuk mencari bobot optimal jaringan syaraf tiruan (multilayer perceptrons). Paralelisasi dilakukan dengan menggunakan Message Passing Interface, di mana sub-populasi (dan nilai-nilai fitnessnya) dipertukarkan antara prosesor, sementara proses inisialisasi populasi, evaluasi, seleksi, crossover, dan mutasi dilakukan secara paralel antara prosesor. Percobaan penelitian ini menunjukkan bahwa paralelisasi memang mengurangi waktu komputasi dari algoritma genetika. Metode yang diusulkan menghasilkan waktu komputasi rata-rata 2,066, 2,656, dan 47,788 detik/generasi untuk masing-masing data permainan Tic-Tac-Toe, evaluasi mobil, dan permainan catur (King-Rook vs. King-Pawn). Sebagai perbandingan, waktu komputasi rata-rata versi seri algoritma ini 14,397, 12,961, dan 350,963 detik/generasi untuk masing-masing tiga data yang sama. Metode yang diusulkan meningkatkan kecepatan komputasi sampai tujuh kali dibandingkan dengan versi seri.

Genetic algorithm is a population-based evolutionary optimization approach, and this has been used to train artificial neural networks. When a large number of individuals make up the population, however, the running time of the algorithm often becomes very long. Parallel computation is a technique that can potentially be used to address this issue. This research investigates the adoption of parallel genetic algorithm for searching optimal weights of artificial neural networks (multilayer perceptrons). Paralellization is conducted using Message Passing Interface, where sub-populations (and their fitness values) are exchanged between processors, while initialization population, evaluation, selection, crossover, and mutation processes are performed parallel between processors. Experiments of this research show that parallelization has indeed reduced the running time of genetic algorithm. The proposed method results an average running time of 2.066, 2.656, and 47.788 seconds/generation for the game of Tic-Tac-Toe, car evaluation, and game of chess (King-Rook vs. King-Pawn) datasets, respectively. As a comparison, the average running time of the serial version of the algorithm is 14.397, 12.961, and 350.963 seconds/generation for the same three datasets, respectively. The proposed method increases computation speed up to seven times compared to the series version.

Kata Kunci : Algoritme Genetika, Backpropagation Algorithm, Jaringan Syaraf Tiruan, Komputasi Paralel, Message Passing Interface.