Pencarian Rute Terpendek dengan Dua Tujuan menggunakan Algoritma Genetika Paralel

Luthfiansyah Ilhamnanda Yusuf, Aina Musdholifah, S.Kom., M.Kom., Ph.D

2023 | Tesis | MAGISTER KECERDASAN ARTIFISIAL

Dalam perkembangan robot autonomous, pencarian jalur merupakan salah satu permasalahan utama yang dihadapi. Algoritma pencarian jalur atau Path Planning memungkinkan robot untuk bergerak sendiri tanpa ada campur tangan manusia. Algoritma Genetika adalah sebuah algoritma optimasi metaheuristik yang terinspirasi dari makhluk hidup dan dapat digunakan untuk menyelesaikan permasalahan Path Planning. 

Meskipun telah terbukti dapat memecahkan masalah Path Planning, Algoritma Genetika mempunyai kekurangan yaitu komputasi yang tinggi seiring dengan peningkatan kompleksitas permasalahan sehingga meningkatkan waktu komputasi. Penambahan destinasi dan objektif dari permasalahan path planning dapat meningkatkan kompleksitas Algoritma Genetika. Untuk memecahkan permasalahan ini, kemampuan multithreading pada prosesor modern dapat digunakan untuk melakukan paralelisasi Algoritma Genetika. 

Telah dilakukan pengujian untuk menguji performa metode Hybrid Parallel Genetic Algorithm (HPGA) dalam menyelesaikan permasalahan pencarian jalur dengan dua destinasi. Pengujian dilakukan pada 3 area berbeda dengan ukuran 15x12 dan performa dibandingkan dengan metode Algoritma Genetika Paralel lain, yaitu Global Parallel Genetic Algorithm (GPGA) dan Island Parallel Genetic Algorithm (IPGA). Jika dibandingkan dengan Algoritma Genetika sekuensial, GPGA dapat memberikan speed up hingga 2,4 kali, IPGA hingga 2,2 kali, dan HPGA memberikan speed up hingga 3,5 kali. HPGA dapat mencegah premature convergence jika dikombinasikan dengan teknik early stopping.

In the development of autonomous robots, path finding is one of the main problems faced. Algorithms to find a path or in short Path Planning Algorithm allows robots to move independently without any human intervention. Genetic Algorithm (GA) is a metaheuristic optimization algorithm inspired by living things and can be used to solve Path Planning problems.

Even though GA has been proven to be able to solve Path Planning problems, Genetic Algorithm has disadvantages. One of which is its high computation with increasing problem complexity, thereby increasing computing time. Adding destinations and objectives to path planning problems can increase the complexity of the Genetic Algorithm. To solve this problem, the multithreading capabilities of modern processors can be used to parallelize Genetic Algorithms.

Tests have been carried out to test the performance Hybrid Parallel Genetic Algorithm (HPGA) method in solving path planning problems with two destinations. Testing was carried out in 3 different areas with a size of 15x12 and comparisons were also made with other Parallel Genetic Algorithm methods, namely Global Parallel Genetic Algorithm (GPGA) and Island Parallel Genetic Algorithm (IPGA). When compared to sequential Genetic Algorithm, GPGA could achieve up to 2,4 times speed up, IPGA up to 2,2 times, and HPGA up to 3,5 times speed up. HPCA could prevent premature convergence when combined with early stopping technique.

Kata Kunci : Algoritma Genetika, Algoritma Genetika Paralel, Dua Destinasi, Dua Objektif, Path Planning