Sekilas Tentang Algoritma Genetika dan Aplikasinya

pada Optimasi Jaringan Pipa Air Bersih

Oleh: Budi Sukmawan

1. Apakah Algoritma Genetika (Genetic Algorithm, GA)?

Algoritma Genetika pada dasarnya adalah program komputer yang mensimulasikan proses evolusi. Dalam hal ini populasi dari kromosom dihasilkan secara random dan memungkinkan untuk berkembang biak sesuai dengan hukum-hukum evolusi dengan harapan akan menghasilkan individu kromosom yang prima. Kromosom ini pada kenyataannya adalah kandidat penyelesaian dari masalah, sehingga bila kromosom yang baik berkembang, solusi yang baik terhadap masalah diharapkan akan dihasilkan.

Algoritma Genetika ini banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan. Algoritma ini dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimal dari satu variabel atau multi variabel. Sebelum algoritma ini dijalankan, masalah apa yang ingin dioptimalkan itu harus dinyatakan dalam fungsi tujuan, yang dikenal dengan fungsi fitness. Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. Walaupun pada awalnya semua nilai fitness kemungkinan sangat kecil (karena algoritma ini menghasilkannya secara random), sebagian akan lebih tinggi dari yang lain. Kromosom dengan nilai fitness yang tinggi ini akan memberikan probabilitas yang tinggi untuk bereproduksi pada generasi selanjutnya. Sehingga untuk setiap generasi pada proses evolusi, fungsi fitness yang mensimulasikan seleksi alam, akan menekan populasi kearah fitness yang meningkat.

Algoritma genetika sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode yang konvensional. Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu:  operator reproduksi, operator crossover (persilangan) dan operator mutasi. Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:

1. Membangkitkan populasi awal, Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan.
2. Membentuk generasi baru, Dalam membentuk digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru.
3. Evaluasi solusi, Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain:

• Berhenti pada generasi tertentu.
• Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah.
• Berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.

Pada uraian berikut penulis mencoba membahas aplikasi algoritma genetika pada bidang sistem distribusi air bersih, karena selama ini penulis bekerja pada konsultan dalam bidang sistem air bersih, dan penulis menguasai sedikit tentang masalah ini.

2. Aplikasi Optimasi GA pada Sistem Jaringan Pipa Air Bersih

Dalam sistem air bersih aplikasi GA umumnya dapat digunakan dalam kalibrasi model hidrolis jaringan pipa dan optimasi perencanaan jaringan baru atau pengembangan jaringan untuk mendapatkan harga pipa yang paling murah dengan memilih diameter pipa dengan harga yang paling ekonomis tetapi tetap mememenuhi kriteria hidrolis yang ditentukan (misalnya: sisa tekan pada titik sadap minimal 30m). Sebagai contoh dalam optimasi jaringan dengan GA, kita dapat mengasumsikan diameter pipa yang akan dipilih sebagai kromosom dan dikodekan kedalam kode string biner. Contohnya adalah sebagai berikut:

Maka kita akan mendapat urutan string biner sebagai berikut :

Selanjutnya kita melakukan proses iterasi evolusi GA pada string biner kromosom ini, mengubah diameter pipa pada jaringan, lalu mengetes hasilnya pada program simulator hidrolis (mis: Epanet) dan diulang sampai kriteria berhenti pada evaluasi solusi tercapai.

Optimasi GA adalah alat yang ampuh yang dapat digunakan oleh pengelola air bersih dan konsultan untuk membantu mencari solusi yang mendekati optimal pada masalah perencanaan, perancangan dan operasi sistem air bersih. Optimasi GA tidak seharusnya dilihat sebagai pendekatan yang bersaing dengan analisa simulasi tradisional. Tetapi GA adalah langkah lanjutan dari analisa simulasi dimana dengan penggunaan GA akan didapat penghematan biaya 20% - 30%.

Dibawah ini akan kita lihat bagaimana GA dapat ditempatkan dalam proses studi dengan melihat langkah-langkah studi simulasi tradisional dan langkah-langkah dalam analisis optimasi GA:

2.1. Langkah-langkah pada Pendekatan Simulasi Tradisional

Pada umumnya langkah-langkah pada master plan distribusi air bersih adalah sebagai berikut:

Langkah 1 - Pembuatan model sistem eksisting menggunakan EPANET, ALEID, H2ONet, MIKENet, KYPIPE, WaterCAD, dll.

Langkah 2 - Kalibrasi model berdasarkan pengukuran lapangan.

Langkah 3 - Tentukan kebutuhan air di masa yang akan datang yang harus dicapai dan disain dan kriteria kinerja yang harus dipenuhi.

Langkah 4 - Tambahkan pipa, reservoar, pompa dan valve pada sistem dan jalankan simulasi untuk melihat apakah simulasi dapat bekerja.

Langkah 5 - Lanjutkan penyesuaian peningkatan yang diusulkan dengan cara coba-coba sampai ditemukan solusi yang tepat (atau limit biaya telah terlampaui).

2.2. Langkah-langkah yang diperlukan dalam aplikasi Optimasi GA

Optimasi GA masuk ke dalam proses setelah langkah 1,2 dan 3 selesai. Dari pada menggunakan cara pendekatan coba-coba (trial-and-error) untuk evaluasi hasil solusi satu persatu pada langkah 4 dan 5, otomatisasi GA digunakan untuk mengidentifikasi biaya termurah, yang mendekati solusi optimal sebagai berikut:

Langkah 4 - Identifikasikan pilihan yang memungkinkan untuk pengadaan baru atau rehab dari pipa, reservoar, pompa dan valve dan pilihan operasi.

Langkah 5 - Formulasikan rutin GA untuk variabel-variabel dari keputusan tersebut.

Langkah 6 - Hubungkan model hidrolis pada rutin GA.

Langkah 7 - Lakukan dan jalankan GA dan dapatkan masukan dan arah dari ahli hidrolis.

Langkah 8 - Finalisasikan alternatif yang dihasilkan dan verifikasi.

Pada umumnya langkah 5, 6, dan 7 telah tercakup dalam software aplikasi optimasi GA, sehingga lebih memudahakan untuk pengguna. Dengan demikian optimasi GA dengan mudah diintegrasikan pada proses studi pada tahap evaluasi alternatif. Data dan informasi yang dibutuhkan oleh GA sama persis dengan data yang dibutuhkan oleh engineer dalam menggunakan analisis simulasi.

Analisa GA membutuhkan:

• Sistem simulasi model hidrolis
• Daftar elemen (pipa, reservoar, pompa, valve) dan pilihan operasional yang seharusnya dipertimbangkan sebagai opsi dalam perencanaan
• Harga dari tiap elemen yang dipakai
• Daftar dari kriteria disain dan kinerja sisteim yang harus dicapai

Untuk mendapat gambaran tentang penerapan aplikasi ini penulis telah membuat aplikasi demo untuk penerapan dalam optimasi jaringan pipa air bersih. Tampilannya dapat dilihat pada gambar berikut ini:

Setelah aplikasi dijalankan (tekan tombol Optimasi) akan telihat diameter pipa berubah misalnya pada pipa nomor 7 rancangan awal diameter pipa 14" berubah menjadi 10", pada pipa nomor 8 pipa diameter 8" tenyata cukup digunakan 1" saja. Biaya juga menurun dari 501.000 unit menjadi 419.000 unit saja dengan penghematan biaya 16,4%. Anda juga dapat lebih menurunkan biaya dengan menurunkan nilai Minimal sisa tekan (dalam meter), standar di Indonesia biasanya 10 - 15m saja.

Aplikasi demonya dapat anda download disini.

3. Aplikasi pada bidang lain

Telah lebih dari 10-15 tahun GA digunakan dalam lingkungan aplikasi yang luas, seperti :

• Disain jaringan listrik tegangan tinggi, penjadwalan konstruksi, management investasi.
• Dalam bidang lain seperti: disain sirkuit terintegrasi (IC) untuk mendapatkan ukuran yang lebih kecil, perancangan mesin turbin gas untuk mendapatkan penggunaan bahan bakar yang effisien pada pesawat udara, perencanaan jaringan kabel filber optik.
• dll.

Referensi:

• Hendry Setiawan, Thiang, Hany Ferdinando, "Aplikasi Algoritma Genetika Untuk Merancang Fungsi Keanggotaan Pada Kendali Logika Fuzzy", 2001

• Jeff S Smith and SoftTech Design, Inc., "What Are Genetic Algorithms (GAs)?",  http://www.softtechdesign.com/, 2002

• OPTIMATICS/FREY, http://www.frey-water.com/

• Thiang, Ronald Kurniawan, Hany Ferdinando, "Implementasi Algoritma Genetika pada Mikrokontroler MCS51 Untuk Mencari Rute Terpendek", 2001

Copyright (c) 2003 - Budi Sukmawan

v1.0: 06 Desember 2003