unsplash.com

Dear Steemian...

Pembahasan ini merupakan lanjutan dari pembahasan sebelumnya yang menjelaskan mengenai pengimplementasian pada algortima genetika dalam menggunakan teknik mutasi dinamis Knapsack Problem. Tujuannya ialah demi menghasilkan hasil yang dapat di analisis sebagai bahan pembelajaran dalam mempelajari ilmu-ilmu baik dibidang algoritma genetika maupun algoritma lainnya. Maka langsung saja simak beberapa pembahasan berikut ini.

HASIL PENELITIAN

Pada bagian ini akan dijelaskan pembahasan dari metode yang telah dibahas pada bab sebelumnya. Di sini akan diuji beberapa sample dari koordinat TSP. Tabel berikut ini merupakan data uji awal untuk menerapkan metode Knapsack pada TSP.

Tabel 4. Data koordinat yang akan di uji

Pada Tabel 4 ada 30 buah koordinat yang membentang pada TSP. Koordinat tersebut dimulai dari Koordinat 0 hingga Koordinat 29. Penciptaan koordinat dilakukan dengan cara random. Pengujian disini tidak menyimpan koordinat dalam suatu database yang bersifat statis. Ini bertujuan agar metode ini dapat diterapkan kepada berbagai macam permasalahan.

Gambar 3. Hasil pembentukan koordinat berdasarkan Tabel 4

Pada Gambar 3 adalah gambar node-node yang telah terbentuk berdasarkan data koordinat yang telah dibangkitkan secara acak. Nilai sumbu X dan sumbu Y dapat dilihat pada Tabel 4. Gambar ini membentuk node-node yang berada dalam rentang X <= 75 dan Y <= 45. Nilai ini dapat disesuaikan sesuai dengan kebutuhan user. Agar perhitungan tidak mempunyai nilai yang terlalu besar, maka nilai yang menjadi acuan tidak melebihi dari 100. Pada pembuatan koordinat TSP, tidak boleh memiliki nilai sumbu X dan sumbu Y yang bersamaan, dengan kata lain tidak boleh ada koordinat yang sama persis nilainya. Permasalahan yang dihadapi jika ada dua buah node yang memiliki koordinat yang sama adalah tidak terjadi pergerakan pada node-node tersebut. Tetapi hal ini mempunyai kemungkinan yang sangat kecil karena nilai yang dibangkitkan merupakan nilai yang acak. Sementara jika ada beberapa node yang memiliki nilai yang sama pada salah satu sumbu X atau sumbu Y, ini tidak akan mempengaruhi jalannya proses perhitungan Knapsack TSP.

Penentuan Target

Target merupakan suatu tujuan yang akan dicapai pada kasus TSP. Perbedaan yang mendasar antara TSP konvensional dengan Knapsack TSP adalah terletak di penentuan target. Pada Knapsack TSP, jumlah node yang akan dilewati ditentukan berdasarkan keinginan dari user. Bobot atau jarak yang dicapai juga harus ditentukan sebelumnya. Sementara pada TSP konvensional, semua node yang diciptakan harus dilalui dengan jarak yang paling minimal pada algoritma genetika. Pada perhitungan kali ini target untuk jumlah node yang dilewati adalah 10 buah node sementara target jarak yang diinginkan sebesar 400. Diharapkan perhitungan Knapsack TSP dapat menentukan node-node mana saja yang memiliki peluang yang sama dengan target atau mendekati target dengan sedekat-dekatnya.

Pengambilan Populasi

Pengambilan populasi diambil secara acak dari susunan koordinat TSP awal. Pada koordinat sebelumnya dinyatakan ada 30 buah koordinat yang masing-masing memiliki nilai sumbu x dan sumbu y. Populasi yang diambil tidak boleh melebihi dari jumlah koordinat yang ada. Sebagai contoh, akan diambil sebuah populasi yang terdiri dari 10 buah node.

{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 }

{0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 3 4 5 6 7 9 10 11 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 3 5 6 7 9 10 11 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 3 5 6 7 9 10 11 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 5 6 7 9 10 11 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 5 6 7 9 10 11 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 5 6 7 9 10 15 16 17 18 19 20 21 23 24 25 26 27 28 29 }

{0 1 2 5 6 7 9 10 15 16 17 18 19 20 21 23 24 25 27 28 29 }

{0 1 2 5 6 7 9 15 16 17 18 19 20 21 23 24 25 27 28 29 }

Pada data di atas, pertama sekali akan dibentuk 30 koordinat (terlihat pada baris pertama). Pada baris kedua akan diambil koordinat ke 22 dari 30 koordinat sebelumnya. Ini dapat dilihat jumlah koordinat sudah berkurang satu, dimana pada baris kedua tidak ada lagi angka 22 pada daftar koordinat tersebut. Pos = 22 menyatakan koordinat yang diambil merupakan urutan ke 22 dari array koordinat. Proses ini kan berulang sampai sebanyak node yang ditentukan pada Knapsack TSP. Pada pengujian kali ini, jumlah node target ditentukan sebanyak 10 buah. Pada akhir pengambilan data acak dari ke 30 data koordinat terlihat ada 20 buah node yang tersisa seperti yang diilustrasikan di bawah ini.

{0 1 2 5 6 7 9 15 16 17 18 19 20 21 23 24 25 27 28 29}

Koordinat-koordinat diatas adalah koordinat yang tidak termasuk dalam proses pengambilan populasi. Setelah dilakukan proses pengambilan populasi dapat dilihat node yang terpilih adalah

22–8–12–4–13–3–14–11–26–10-22

Pengambilan koordinat tidak boleh berulang, dengan arti node yang sudah terpilih tidak boleh dimasukkan kembali dalam node berikutnya. Karena sesuai dengan prinsip kerja TSP, node hanya dapat dilalui sekali saja dalam proses perjalanannya. Pada data di atas dapat dilihat tidak ada node yang berulang. Perjalanan akan dimulai dari node 22 sampai node 10 dan akhirnya kembali ke node 22.

Tabel 5. Node yang terpilih pada proses pembuatan populasi

Pada Tabel 5 merupakan node-node yang terpilih dari pembentukan 10 buah node yang menjadi target dari Knapsack TSP. Proses pembentukan populasi akan berlangsung sampai ukuran populasi terpenuhi. Pada percobaan ini akan dilakukan sebanyak 10 buah populasi. Data yang ditampilkan diatas merupakan data pengambilan sebanyak satu populasi saja. Proses pembentukan 10 populasi dapat dilihat pada lampiran 2, dan hasil pembuatan 10 populasi acak ditampilkan pada Tabel 6 berikut ini.

Tabel 6. Hasil pembuatan 10 buah populasi acak

Tabel di atas diperoleh dari proses pembangkitan populasi. Setiap populasi dari populasi 0 sampai populasi 9 akan dihitung masing-masing nilai fitnessnya. Fitness yang mendekati target memiliki peluang yang lebih besar untuk dijadikan parent pada proses seleksi dan mutasi.

To be continued ...

Wondering How Steemit Works, Read Steemit FAQ?