Review: Educational Intelligent System Using Genetic Algorithm

Paper Review oleh Bima Krisna Noveta, Dion Andres, Francisco Calvin Arnel Ferano, Jonathan Christian Setyono, dan Patrick Valentino.

Editor: Amalia Zahra, S.Kom., Ph.D.

Referensi: Protopopova, J., & Kulik, S. (2020). Educational intelligent system using genetic algorithm. Procedia Computer Science, 169, 168-172.

Tujuan paper referensi tersebut disusun adalah untuk membuat intelligent information system untuk edukasi, yakni mengembangkan sistem bernama GALA (Genetic Algorithm Learning Application). Sistem ini dirancang untuk memberikan pembelajaran kepada murid untuk menggunakan algoritma genetika dalam aplikasi. Sistem ini dapat mengkodekan solusi dari masalah dan mengambil konfigurasi yang paling cocok dari algoritma genetika.

Genetic algorithm merupakan sebuah algoritma yang diciptakan dengan satu tujuan saja, yaitu untuk melakukan optimisasi, tidak untuk klasifikasi, regresi, dan lain sebagainya.  Genetic algorithm adalah sebuah algoritma stokastik, yang berarti algoritma ini akan bekerja dan menghasilkan output melalui perhitungan peluang. Sesuai dengan namanya, Genetic algorithm memiliki prosedur kerja yang sama dengan prosedur kerja persilangan genetik (evolusi) pada dunia nyata atau pada makhluk hidup.

Dalam teori makhluk hidup, sebuah individu akan memiliki serangkaian genetik yang membentuk sebuah kromosom. Ketika melakukan persilangan reproduksi dengan individu lainnya, maka akan terjadi genetic crossover yang meciptakan individu baru dengan kromosom yang baru (kombinasi genetika yang baru). Setiap individu baru ini merupakan potential solution untuk permasalahan.

Setiap individu akan diberikan analisis mengenai kecocokan dengan kriteria permasalahan, sehingga setiap individu akan memiliki nilai atau skor untuk menentukan individu mana yang paling baik berdasarkan algoritma yang dibuat. Proses ini disebut dengan fitness function.

Genetic Algorithm digunakan dalam pembuatan aplikasi GALA (Generic Algorithm Learning Application). GALA dikembangkan untuk mengajarkan bagaimana caranya menggunakan GA untuk menyelesaikan masalah. Tujuan utama dari pengembangan sistem ini adalah untuk menyediakan sebuah tool sederhana dan intuitif dalam mempelajari penggunaan genetic algorithm untuk menyelesaikan masalah.

Sistem ini memiliki arsitektur modular yang dibagi menjadi 3 bagian utama berdasarkan fungsi dari area operasinya :

1. “Objects”: subsystem yang bekerja dengan user-defined objects seperti chromosomes, genotypes dan fungsi, dan memperbolehkan user untuk membuat, mengubah dan mencari hal tersebut.
2. “Problems”: subsystem yang dirancang untuk mengatur masalah pengguna dan solusinya. Subsystem ini memperbolehkan pengguna untuk mengubah dan mengeliminasi masalah yang sudah ada, menciptakan masalah baru, melihat masalah, serta melihat dan mengatur semua solusi yang sudah dibuat untuk sebuah task tertentu;
3. “Import/Export” subsystem digunakan untuk mensinkronisasikan data antara client app dan database servers.

Sistem GALA mengimplementasikan sebuah arsitektur, yakni three-tier client-server dan berisi komponen-komponen, di anataranya sebuah database server yang menjalankan database management system MongoDB, sebuah web server yang mengimplementasikan platform NodeJS dengan menggunakan Express framework, dan sebuah client web-app yang memproses komputasi matematik (dengan menggunakan library MathJS) dan merender GUI (berdasarkan framework VueJS).

Dalam sistem GALA, sebuah gen adalah sebuah pre-defined combination encoded dan decoded yang merupakan reseprentasi dari sebuah decision gen. Tipe gen:

1. Int adalah integer dalam genotype (encoded) dan phenotype (decoded). Mutasi dibuat dengan mengganti value integer dengan menambakan sebuah integer random dari sebuah range;
2. Float direpresentatifkan oleh bilangan tidak bulat dalam tipe encoded and decoded. Mutasi terjadi mirip dengan gen tipe Int.
3. BinaryFloat dalam bentuk encoded direpresentasikan oleh angka binary, dan dalam bentuk decoded berbentuk floating-point dengan akurasi tertentu. Mutasinya adalah inversi random dari sebuah locus gen.
4. BinaryInt dalam bentuk encoded-nya direpresentasikan oleh sebuah sequence dari bits yang memiliki values “0” atau “1” (boolean vector). Dalam bentuk decoded-nya berbentuk integer. Mutasi terjadi dengan mengganti value dari sebuah bit yang dipilih secara acak dari bentuk encoded-nya.
5. GrayInt adalah bentuk encoded yang direpresentasikan menggunakan binary code Gray dan merupakan seluruh angka bila dalam bentuk decoded. Keunggulan dari gray code adalah representasi encoded phenotype dari angka yang bersebelahan hanya berbeda satu bit sehingga dalam mutasi kerugian tajam dari keputusan baik dapat dieliminasi. Mutasinya terjadi dengan menggunakan inversi random dari sebuah locus gen.

Dalam pembuatan konfigurasi solusi dari masalah yang menggunakan Genetic Algorithm, ada beberapa parameter yang digunakan, yaitu Genotype dari individual yang diproses menggunakan algoritma, fungsi tujuan/goal untuk maximize/minimize, nilai spesifik setiap individu awal, jumlah populasi independen yang diproses, strategi dalam memilih individual menjadi populasi intermediate dan sebagian kecil dari yang terpilih, strategi pair form, jumlah poin serta kemungkinan crossover dan mutation, strategi penggabungan populasi intermediate dan main, serta kriteria terminasi. Kriteria terminasi sendiri meliputi maksimum iterasi, pencapaian nilai fungsi tujuan yang diinginkan, tidak ada perubahan signifikan dari rata-rata fungsi tujuan dalam populasi (stagnasi).

Secara kesimpulan, GALA dirancang sebagai sistem edukasi yang memberikan kemampuan bagi murid untuk memecahkan masalah menggunakan GA (Genetic Algorithm) seperti masalah engineering dan production yang memiliki banyak kombinasi solusi. Sistem GALA ini akan mencari konfigurasi GA paling sesuai berdasarkan permasalahan yang diberikan oleh murid sehingga solusi yang dihasilkan merupakan solusi yang mendekati optimal atau 98% optimal berdasarkan contoh kasus penyediaan air bersih pada pemukiman.