Penerapan Algoritma Genetika untuk Optimisasi Jalur pada Jaringan Telekomunikasi

Tulisan ini saya ambil dari tugas paper kuliah Sistem Berbasis Pengetahuan,  


Abstrak – Teknologi telekomunikasi yang semakin berkembang menuntut efisiensi dalam pengelolaan jaringan. Efisiensi yang dibahas disini adalah mengenai jalur pada jaringan telekomunikasi. Optimisasi jalur pada jaringan telekomunikasi berkaitan dengan proses pengirman informasi dari sumber ke pelanggan. Hal ini dimaksudkan agar proses routing yang terjadi bisa mengoptimalkan jalur yang digunakan sehingga bisa menciptakan efisiensi waktu. Penerapan optimisasi ini menggunakan algoritma genetika yaitu salah satu teknik optimisasi yang menggunakan metode genetika seperti reproduksi, mutasi, kawin silang, dan proses seleksi. Hasil yang diharapkan adalah diperoleh suatu metode algoritma genetika yang bisa digunakan untuk mencari jalur yang optimal dalam suatu jaringan telekomunikasi.

Kata kunci : Algoritma Genetika, Jalur Terpendek, Jaringan Telekomunikasi, Teknik Optimisasi

I.     Pendahuluan

Algoritma genetika atau dalam bahasa inggris disebut genetic algorithm yang biasa disingkat GA adalah teknik optimisasi yang mencari solusi terbaik dengan menerapkan teori evolusi Darwin [1]. Algoritma genetika ditemukan oleh John Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan dalam terminologi genetika [8].

          Jaringan telekomunikasi dikembangkan untuk menciptakan informasi dan mendistribusikannya melalui suatu proses routing, proses routing dari suatu router ke router yang lain mempertimbangkan efisiensi waktu dan delay sehingga diperlukan ketepatan dalam menentukan shortest path routing dari sumber ke tujuan dalam jaringan telekomunikasi [2]. Oleh sebab itu, dengan menggunakan algoritma genetika diharapkan dapat ditentukan jalur yang optimal antara sumber dan tujuan pada suatu jaringan telekomunikasi sehingga bisa efisien dari segi waktu dan peningkatan performance dari jaringan itu sendiri.

 

Gambar 1 Ilustrasi tahapan proses algoritma genetika [7]

II.  Permasalahan Optimasi Rute Jaringan

Dalam suatu jaringan telekomunikasi hubungan antara base station (BTS) sebagai sumber yang meng-cover layanan pelanggan dan mobile switching centre (MSC) yang melakukan proses switching sebagai sentral telepon seluler harus terjalin dengan baik. Pada intinya proses komunikasi seluler yang terjadi adalah ketika mobile station (MS) melakukan panggilan, maka base station yang melayani akan memberikan informasi ke mobile switching centre untuk mengecek keberadaan nomor yang dituju dan selanjutnya percakapan pun bisa dilangsungkan. Perhatikan gambar 2 diatas yang merupakan ilustrasi sederhana proses komunikasi antara MS1 dengan MS2. 
 

Gambar 2 Ilustrasi sederhana proses komunikasi seluler

Hal yang penting kemudian adalah jalur – jalur mana saja yang akan dilalui jaringan sehingga komunikasi bisa tercapai. Pada dasarnya setiap BTS terhubung satu sama lain sehingga jalur mana saja yang dilalui bisa menghubungkan komunikasi antara dua pelanggan. Dalam hal ini optimasai jaringan telekomunikasi diperlukan dalam hal pemilihan jalur yang akan dilewati oleh jaringan. Tentu saja jalur terpendek akan memberikan efisiensi dalam hal waktu dibandingkan dengan jalur lain yang lebih panjang. 

Optimisasi yang ada dalam suatu jaringan telekomunikasi mencangkup beberapa hal yaitu [9] :

1.      Minimalisasi biaya produksi

2.      Minimalisasi blocking

3.      Maksimalisasi penggunaan

4.      Minimalisasi panjang rute yang dilalui

Dalam paper  ini akan dibahas mengenai optimasi jaringan telekomunikasi dalam hal menentukan rute optimum yang akan dilalui oleh jaringan. Perhatikan gambar 3 dibawah ini, MS1 akan melakukan panggilan ke MS15, dari sekian banyak BTS – BTS yang ada, rute mana yang memiliki jarak terpendek dibandingkan lainnya. Tentunya hal ini akan menjadi pembahasan berikutnya tentang bagaimana implementasi algoritma genetika dalam optimasi jalur atau rute dalam suatu jaringan telekomunikasi.

Gambar 3 Topologi jaringan telekomunikasi untuk simulasi

III.   Algoritma Genetika

Algoritma genetika adalah adalah algoritma pencarian yang didasarkan atas mekanisme seleksi alami dan evolusi biologis. Algoritma genetika mengkombinasikan antara deretan struktur dengan  pertukaran informasi acak ke bentuk algoritma pencarian dengan beberapa perubahan bakat pada manusia. Pada setiap generasi, himpunan baru dari deretan individu dibuat berdasarkan kecocokan pada generasi sebelumnya [8].

Evolusi dari satu generasi ke generasi selanjutnya pada dasarnya terdiri atas 3 tahapan yaitu evaluasi kemampuan, proses seleksi dan proses reproduksi [4].

Seperti pada gambar 1 bisa dilihat terjadinya rotasi dalam algoritma genetika yang terjadi berulang – ulang sampa diperoleh keturunan terbaik dalam generasinya. Pada tahapa awal terjadi prose pengkodean sehinggan menjadi bit – bit string kromosom kemudian terjadi proses evaluasi kemampuan dari kromosom – kromosom tersebut, sehingga kromosom terbaik yang bisa bertahan. Pada bagian ini terdapat proses kawin silang atau cross over yaitu proses menyilangkan dua kromosom sehingga bisa diperoleh keturunan yang lebih baik daripada orang tuanya. Proses yang kedua disebut proses mutasi yaitu menambahkan nilai acak kepada keturunan. Pada proses seleksi secara acak melahirkan keturunan baru yang akan menjadi bagian dari populasi baru yang merupakan generasi terbaik dari populasi tersebut.

IV.   Implementasi ALgoritma Genetika

Pada bagian ini menjelaskan implementasi dari algoritma genetika untuk menentukan rute terpendek dari suatu jaringan telekomunikasi. Teknik GA telah banyak memberikan solusi – solusi untuk permasalah numerik untuk masalah optimisasi, termasuk kedalamnya proses optimisasi untuk menentukan rute terpendek pada suatu jaringan telepon [9].

 PICTURE BLANK (on paper)

Gambar 4 Ilustrasi proses routing jaringan [6]

Implementasi dari algoritma genetika dapat dibagi kedalam beberapa tahapan berikut ini [5] [9] :

1.      Menentukan populasi awal

Tahap yang paling penting ini adalah menentukan populasi awal. Populasi awal ini diberikan secara acak, missal diberikan populasi awal P, maka setiap kromosom yang terdapat pada populasi P tersebut yang akan diproses. Hal ini berarti kita menentukan sumber dari jaringan itu sendiri atau merupakan titik awal dari jaringan yang akan dihubungkan.

 PICTURE BLANK (on paper)

Gambar 5 Ilustrasi sturuktur kromosom [4]

2.      Evaluasi kemampuan dalam populasi

Tahap kedua ini adalah mengevaluasi kemampuan setiap individua atau kromosom ataupun titik pada jaringan telekomunikasi dalam hal ini. Dalam jaringan telekomunikasi, setiap titik yang berada di dekat titik awal yang sudah ditentukan pada tahap pertama dievaluasi dari segi jarak nya ke titik awal tersebut, titik terdekat dari titik awal yang akan dipilih untuk kemudian dihubungkan.

3.      Memilih kromosom terbaik

Pada tahapain ini adalah memilih kromosom terbaik setelah dilakukan evaluasi pada bagian kedua untuk kemudian di reproduksi. Dengan menentukan jalur – jalur mana yang bisa dikerjakan dengan mudah dan susah. Jalur yang mudah dikerjakan kemudian dipilih dan disebut sebagai kromosom terbaik secara algoritma genetika

4.      Proses kawin silang dan mutasi

Pada tahap ini dilakukan proses crossover dan mutation yaitu proses kawin silang dan proses mutasi. Pada jaringan telekomunikasi ini dimaksudkan untuk menukar bagian tengan pada jalur pertama dengan bagian tengan pada jalur kedua sehingga panjang dari rute bisa diperpendek. Begitu juga proses mutasi dilakukan secara acak menempatkan bit pada jalur yang dikehendaki. Hal ini agar diperoleh jalur yang lebih pendek untuk setiap proses kawin silang atau mutasi yang dilakukan.

 PICTURE BLANK (on paper)

Gambar 6 Ilustrasi proses kawin silang [6]

 PICTURE BLANK (on paper)

Gambar 7 Ilustrasi proses mutasi [6]

5.      Evaluasi

Pada bagian ini mengevaluasi setiap jalur yang sudah diambil apakah merupakan jalur terbaik yang bisa diambil sehinggan didapatkan jalur optimum pada jaringan tersebut.

6.      Pengulangan

Proses –proses diatas dilakukan berulang sampai jalur yang diinginkan terbentuk.

V.  Simulasi MATLAB

Pada paper ini disimulasikan sebuah teknik graf yang merupakan kumpulan dari beberapa simpul yang dihubungkan satu sama lain dengan busur panah atau arah [8].  Simulasi ini ingin mengetahui rute yang terpendek dari suatu jaringan telekomunikasi dengan menggunakan MATLAB. Topologi jaringan yang digunakan adalah seperti pada gambar 3, yaitu terdapat banyak BTS yang bisa menghubungkan komunikasi antara dua telepon. Dengan simulasi ini akan ditemukan jalur terpendek yang bisa dilalui, sehinggan tujuan bisa tercapai. Pada gambar 3 diatas kita bisa menentuka link – link  yang saling terhubung antar BTS satu sama lain seperti pada table dibawah.

Tabel 1 Kode biner pada jaringan gambar 3

No	Kromosom	Jalur
1	0 0 0 1	2 ; 3
2	0 0 1 0	3 ; 4
3	0 0 1 1	6 ; 7
4	0 1 0 0	5 ; 8
5	0 1 0 1	6 ; 9
6	0 1 1 0	11
7	0 1 1 1	10
8	1 0 0 0	9 ; 12
9	1 0 0 1	11
10	1 0 1 0	11
11	1 0 1 1	13 ; 14
12	1 1 0 0	13
13	1 1 0 1	14
14	1 1 1 0	15
15	1 1 1 1	Tujuan

Setelah menentukan titik – titik yang berhubungan kita bisa membuatnya menggunakan perintah MATLAB [3] [4] :

Angka yang terletak pada baris pertama merupakan sumber dari jaringan, angka yang terletak pada baris kedua merupakan tujuan jaringan, dan angka yang terletak pada baris ketiga merupakan jarak antar titik – titik BTS. Hasil dari eksekusi perintah diatas adalah sebagai berikut :

Selanjutnya diberikan perintah untuk menetukan rute terpendek dari jaringan dengan perintah graphshortestpath berikut ini :

Sehingga menghasilkan angka seperti gambar diatas yaitu cost yang merupakan jarak yang ditempuh dan path  yaitu rute terpendek yang dilalui oleh jaringan. Dan untuk menampilkan gambar dari rute tersebut, beikut perintahnya :

Hasilnya seperti pada gambar dibawah ini :

 

Gambar 8 Hasil simulasi MATLAB

 

Garis merah diatas seteleh dilakukan edit, merupakan rute yang akan ditempuh dalam suatu jaringan telekomunikasi dan merupakan rute terpendek yang bisa dilalui. Contoh simulasi ini menerapakan metode algoritma genetika seperti yang dijabarkan pada chapter sebelumnya, proses perulangan yang dilakukan sehingga menghasilkan suatu generasi terbaik yang ada dalam hal ini menemukan jalur terpendek dalam jaringan tersebut.

VI.   Kesimpulan

Algoritma genetika bisa menjadi solusi dalam mencari rute terpendek untuk suatu jaringan telekomunikasi. Pada pembahasan ini, proses perhitungan jarak jalur dilakukan dari sumber menuju ke tujuan jaringan dalam hal ini dari mobile phone pemanggil ke mobile phone penerima. Tingkat persentasi optimasi algoritma genetika ditentukan oleh maksimum generasi, semakin banyak generasi yang diproses maka semakin tinggi tingkat optimasi nya. Oleh karena itu, untuk jaringan telekomunikasi yang mempunyai banyak hubungan antara BTS, dengan menggunakan algoritma genetika ini bisa diketahui dengan rinci jalur terpendek yang bisa dilalui untuk menghubungkan percakapan.

Panjang kromosom pada pembahasan ini tergantung dari banyaknya hubungan BTS yang terjalin dalam jaringan telekomunikasi. Pada simulasi ini terdapat 15 hubungan sehingga menggunakan kromosom 4 bit biner. Algoritma genetika lebih bisa memberikan hasil yang optimum karena algoritma genetika melakukan proses berulang – ulang sehingga diperolah generasi terbaik dalam hal ini berarti mempunyai jarak terpendek dalam satu jaringan telekomunikasi.

Paper ini hanya contoh penerapan algoritma genetika dalam hal optimasi jalur pada jaringan telekomunikasi yaitu mencari jalur terpendek dari jaringan yang ada sehingga diharapkan bisa menghasilkan efisiensi waktu dan meningkatkan kemampuan jaringan dalam melayani pelanggan.

referensi atau daftar pustaka serta versi lengkapnya terlampir di makalah asli. semoga bermanfaat.