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:
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.
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.
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:
Kode Biner
Diameter Pipa (")
Harga Unit
0000
1
2
0001
2
5
0010
3
8
0011
4
11
0100
5
16
0101
8
23
0110
10
32
0111
12
60
1000
14
60
1001
16
90
1010
18
130
1011
20
170
1100
22
300
1101
24
500
Maka kita akan mendapat urutan string biner sebagai berikut :
String biner :
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
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
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:
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.
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.
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:
Kode Biner
Diameter Pipa (")
Harga Unit
0000
1
2
0001
2
5
0010
3
8
0011
4
11
0100
5
16
0101
8
23
0110
10
32
0111
12
60
1000
14
60
1001
16
90
1010
18
130
1011
20
170
1100
22
300
1101
24
500
Maka kita akan mendapat urutan string biner sebagai berikut :
String biner :
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
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
0 komentar:
Posting Komentar