Genetic Algorithm (GA) merupakan salah satu metode heuristik yang digunakan untuk mengoptimasi sebuah proses. Karena merupakan metode heuristik, maka solusi yang diperoleh dari GA bukan yang terbaik, melainkan yang mendekati optimal.

Konsep GA terinspirasi dari teori evolusi Darwin dengan quote “the strongest species that survive”. Teori evolusi Darwin menegaskan bahwa organisme dapat bertahan hidup dengan beberapa proses yakni reproduksi (crossover) dan mutasi. Konsep tersebut kemudian diadaptasi pada algoritma komputasi untuk menemukan solusi pada masalah fungsi objektif.

Gambar 1. Proses pada Genetic Algorithm

Proses pada GA umumnya dapat dilihat pada gambar 1 di atas. Chromosome adalah sebuah solusi yang dihasilkan oleh GA dan koleksi dari chromosome disebut juga populasi. Sebuah chromosome terdiri dari genetika dimana tiap gene dapat direpresentasikan dengan sebuah value berupa numeric, binary, symbol ataupun karakter tergantung masalah yang akan diselesaikan.

Fitness function merupakan sebuah fungsi yang digunakan untuk mengukur tingkat kecocokan sebuah solusi/chromosome yang dihasilkan oleh GA. Proses reproduksi/ menghasilkan solusi lain dilakukan dengan beberapa tahapan proses yakni selection, crossover dan mutasi.

Generasi merupakan representasi iterasi reproduksi yang telah terjadi. Selection merupakan proses pemilihan koleksi chromosome yang akan digunakan sebagai parent untuk menemukan genetika baru melalui proses crossover yang menghasilkan komposisi genetika baru dengan kombinasi genetik dari parent. Pada sebuah generasi, mutasi genetika pada beberapa chromosome dapat terjadi. Jumlah chromosome yang akan melalui proses crossover dan mutasi pada algoritma komputasi direpresentasikan dengan crossover rate dan mutasi rate. Proses ini akan diiterasi pada beberapa generasi, proses selection secara umum menerapkan teori evolusi Darwin dimana solusi dengan fitness value yang lebih besar memiliki peluang lebih besar dipilih untuk reproduksi. Sehingga hasil chromosome konvergen pada sebuah nilai yang merepresentasikan solusi terbaik pada sebuah masalah.

Di bawah ini merupakan tutorial tentang cara mengoptimalkan rute pada peta menggunakan GA dalam bahasa Python.

Persiapan dan Instalasi

  1. Unduh Anaconda Python. Anaconda Python merupakan open source distribution dari bahasa pemrograman Python dan R untuk data science dan machine Link untuk mengunduh Anaconda Python: https://www.anaconda.com/products/individualSetelah Anaconda Python berhasil diunduh, maka tahap selanjutnya yang harus dilakukan adalah selesaikan instalasi.
  2. Untuk mengecek apakah instalasi berhasil atau tidak, buka terminal dan ketik perintah dibawah ini:python –version
    Perintah diatas akan mencetak versi dari python yang terinstalasi dalam perangkat kita.
  1. Buka Jupyter Notebook dengan perintah dibawah ini:jupyter notebookPerintah diatas akan membuka Jupyter Notebook pada web browser dimana kita bisa mengetik dan menjalankan kode.

Library yang akan digunakan

Akan digunakan beberapa library, yaitu:

  • Pandas: berfungsi sebagai data analysis and manipulation tool
  • Numpy: berfungsi untuk tool dalam memproses multidimensional object (array)
  • Random: berfungsi untuk menghasilkan angka random
  • plyploy: berfungsi untuk memproyeksikan titik pada sebuah plot (grafik)
  • Seaborn: berfungsi untuk statistical data visualization

Untuk memakai library tersebut maka langkah awal adalah dengan mengimportnya dengan kode sebagai berikut:

Penjelasan Coding

Fungsi print_pop digunakan untuk mengetahui rute yang ada pada population

Langkah selanjutnya adalah membuat fungsi initialize_map dan initialize_complex_map yang akan membuat map secara random, parameter N merupakan size dari map yang akan dibuat (N x N) dengan value default yaitu 0, lalu parameter p_zero akan digunakan sebagai penentu apabila angka random lebih besar dari p_zero maka nilai default (0) akan digantikan dengan angka random tersebut. Value pada setiap map ini akan menandakan waktu yang dibutuhkan untuk pergi dari i ke j. Sementara apabila nilai dari value tersebut 0 menandakan tidak ada rute yang bisa dilewati dari i ke j.


Fungsi create_starting_population akan menghasilkan jumlah populasi sebesar N, dengan setiap populasinya merupakan rute yang bisa dilewati dari titik 0 yang ditentukan secara random melalui fungsi create_new_member.

Fungsi fitness digunakan untuk menghitung fitness value dari sebuah rute yang ada, fungsi ini akan menghasilkan cost yang ditempuh melalui rute yang diberikan pada parameter.

Fungsi crossover akan digunakan untuk melakukan tahap crossover pada Genetic Algorithm, langkah awal adalah menentukan cut point pada a dan b, lalu kedua rute tersebut akan ditukar berdasarkan cut point tersebut.

Fungsi mutate berguna untuk langkah mutasi pada Genetic Algorithm, dimana apabila hasil dari angka random lebih kecil dari parameter probability, maka bagian dari rute tersebut akan dirombak sehingga jalan yang diciptakan akan menjadi rute yang berbeda dari sebelumnya. (logic mirip dengan fungsi create_new_member)

Fungsi create_new_member merupakan fungsi yang digunakan untuk membuat sebuah rute baru dari map yang sudah dibuat, dengan jumlah step yang random, struktur dari rute tersebut merupakan vector integer dengan nilai yang ada menunjukan step selanjutnya pada rute tersebut. Setiap rute akan dimulai dari titik 0 maka value pertama dari vektor tersebut akan merepresentasikan ketitik mana kita akan bergerak, misalkan nilainya adalah 4 maka kita akan bergerak dari titik 0 ke 4, tentunya hasil random ini hanya akan mengikutsertakan titik yang bisa dituju dari titik sebelumnya. Hal ini akan berulang terus menerus hingga mendapatkan titik tujuan yaitu N-1.

Fungsi score_population berguna untuk mengetahui fitness value dari populasi yang ada saat ini, dengan menghitungnya menggunakan fungsi fitness pada sebuah populasi,

Fungsi pick_mate akan melihat nilai dari fitness pada sebuah populasi dan akan memilih  populasi mana yang akan lanjut sebagai populasi selanjutnya dan tidak (berkaitan dengan proses crossover).

Fungsi plot_best akan memvisualisasikan rute terbaik yang dihasilkan, titik putih dan garis putih menandakan rute hasil dari GA tersebut.

Sumber:

  1. Genetic Algorithm from Scratch in Python — Full Walkthrough https://www.youtube.com/watch?v=uCXm6avugCo
  2. Denny Hermawanto, Genetic Algorithm for Solving Simple Mathematical Equality Problem: https://arxiv.org/ftp/arxiv/papers/1308/1308.4675.pdf

Author : Alvin Riady, Christian Alvin Setiabudi, Felix Andrian Nugroho, Tommy Willianto – Binus Graduate Program – Master of Computer Science
Supervised by : Dr. Derwin Suhartono, S.Kom., MTI