PENERAPAN ALGORITMA GENETIK PADA PENYELESAIAN MASALAH PEWARNAAN GRAF.

Perkembangan ilmu pengetahuan untuk menyelesaikan suatu masalah yang dapat ditangani oleh suatu algoritma yang efisien semakin luas. Jenis masalah dapat berkisar dari masalah yang mudah sampai ke masalah yang kompleks, seperti masalah pewarnaan graf. Sehubungan kekompleksan masalah tersebut, dari sekian banyak algoritma, perlu diketahui algoritma mana yang lebih efisien.

Masalah pewarnaan graf merupakan salah satu konsep dalam graf tak berarah, bagaimana mewarnakan setiap verteks pada suatu graf tak berarah sehingga setiap verteks yang terhubung oleh edge menerima warna yang berbeda. Pewarnaan secara tepat dengan jumlah warna yang minimum pada umumnya merupakan pekerjaan yang rumit, masalah tersebut merupakan salah satu masalah yang termasuk NP-Complete yang sulit ditemukan solusinya.

Salah satu cara untuk menyelesaikan masalah pewarnaan graf adalah dengan menggunakan metode heuristik. Ciri algoritma heuristik adalah selalu menemukan solusi yang baik tetapi tidak harus yang terbaik, serta cepat dan mudah untuk diimplementasikan. Algoritma genetik merupakan suatu metode penyelesaian masalah yang didasarkan pada metode heuristik, dimana mekanisme kerjanya menirukan proses evolusi biologi menurut teori Darwin. Dengan menggunakan penyandian yang tepat dan pendefinisian fungsi fitness yang jelas maka algoritma genetik dapat dengan mudah diimplementasikan serta dengan menerapkan mekanisme seleksi, perkawinan silang, mutasi, dan update generasi secara tepat maka algoritma genetik dapat memberikan solusi untuk masalah pewarnaan graf.

Hasil yang dicapai dengan algoritma genetik dapat mencapai solusi yang optimum, dengan penambahan jumlah generasi yang semakin besar maka fitness terbaik dapat dicapai dimana setiap verteks yang berdekatan menerima warna yang berbeda sehingga solusi untuk masalah graf 3-coloring terpenuhi.