PERANGKAT LUNAK PENENTUAN RUTE TRANSPORTASI UMUM DENGAN ALGORITMA PENCARIAN HYBRID GREEDY DAN GENETIK

41

PERANGKAT LUNAK PENENTUAN RUTE TRANSPORTASI UMUM DENGAN ALGORITMA PENCARIAN HYBRID GREEDY DAN GENETIK Fivien Nur Savitri1, Mahmud Imrona2, Dade Nurjanah3 Jurusan Teknik Informatika – Sekolah Tinggi Teknologi Telkom, Bandung 1 [email protected], [email protected], [email protected] Abstrak Masyarakat kota Bandung dalam menggunakan transportasi umum biasanya memperhitungkan banyaknya transportasi umum yang akan digunakan mencapai tempat tujuan. Semakin sedikit berganti transportasi umum, maka dirasakan akan memperkecil usaha yang dikeluarkan. Namun jika dikaitkan dengan parameter lain, seperti jalur terpendek, biaya terendah, tingkat kemacetan terkecil dan tingkat keamanan yang dibutuhkan pengguna, usaha yang dikeluarkan justru lebih besar. Dibutuhkan suatu perangkat bantu yang tepat agar permasalahan tersebut dapat diselesaikan, salah satunya dengan menggunakan sistem kecerdasan buatan. Dengan menggunakan gabungan dua algoritma pencarian yaitu Algoritma Genetik (AG) dan Greedy Search, kecepatan proses perhitungan akan terkendali dan menghasilkan keluaran yang maksimal. Perangkat lunak ini diimplementasikan menggunakan bahasa pemrograman Sybase Power Builder 8.0, sedangkan basisdata menggunakan MS Access. Dalam penelitian ini hasil terbaik didapat pada: jumlah maksimal populasi 30, jumlah generasi 6, probabilitas kawin silang 0.1, probabilitas mutasi 0.06, dan maksimal node yang dapat ditangani 332. Kata Kunci : Greedy Search, Algoritma Genetik, Transportasi. Abstract A lot of people in Bandung use public transportation. To go to some place, sometimes they can not just use single public transportion of single route, they must switch-over routes. So before they take the trip, they determine which public transportation routes shoud they take to get the simplest – the least switch-over routes and less cost they spend. To get the most feasible route there are many parameters involved, e.g. distance, money to spend, traffic-jam, and security along the trip. So these are the problem: the shortest route is not always the most feasibel route. To solve the problem we propose an alternative tools to use an artificial intelligent application which can calcalute the combination of parameters mentioned above to fit the user’s requirements. This paper combine two algorithms: Genetic Algorithm and Greedy Search Algorithm. The objective of the combination is to develop an application which can control the process and produce a maximum and feasible output. To develop the Applicaton Software, we use Sybase Power Builder 8.0 as programming language software and MicroSoft Access as the database management system software. The best result is reached in maximum population 30, generation 6, probality of cross-capulate 0.1, probability of mutation 0.06, and maximum excuted node 332. Keywords: Greedy Search, Genetic Algorithm, Transportation. 1.

Pendahuluan

Terdapat banyak algoritma untuk menghasilkan solusi masalah pemilihan jalur, seperti algoritma DFS (Depth First Search) dan BFS (Breadth First Search), namun pemrosesannya tak dapat diketahui secara pasti sejak awal. Pada penelitian ini algoritma Genetik dan Greedy Search digabungkan agar waktu proses pencarian untuk memperoleh informasi rute perjalanan terpendek, biaya termurah, tingkat kemacetan terendah dan tingkat keamanan yang tinggi dapat dioptimalkan. Jaringan lalu lintas akan membentuk suatu graph berarah, dengan titik berupa persimpangan dan busur adalah jalan yang menghubungan dua persimpangan. Informasi yang berkaitan dengan parameter penentu angkutan umum, dapat disimpan pada titik atau busur dari graph. Penerapan algoritma genetik pada proses pencarian rute perjalanan dilakukan dengan mengevaluasi sekumpulan solusi

melalui fungsi fitness yang menyimpan nilai-nilai parameter penentu [1]. 2.

Algoritma Hybrid Greedy dan Genetik

2.1 Algoritma Genetik Algoritma genetik merupakan prosedur iteratif, bekerja dengan suatu set untaian yang disebut populasi sebagai kandidat solusi dengan jumlah yang konstan dan berkembang dari generasi ke generasi melalui aplikasi operator genetik. Struktur dalam populasi generasi saat itu akan dievaluasi, dan selanjutnya diseleksi untuk menentukan populasi pada generasi selanjutnya. 2.1.1 Representasi atau Encoding Pengkodean parameter harus dilakukan terlebih dahulu untuk membentuk parameter-parameter

Perangkat Lunak Penentuan Rute Transportasi Umum dengan Algoritma Pencarian Hybrid Greedy dan Genetik (Fivien Nur Savitri)

42

menjadi suatu susunan kromosom, sehingga dapat dilakukan operasi genetik terhadapnya. Terdapat tiga fokus utama encoding, yaitu Feasibility, Legality dan Uniqueness Mapping [2]. 2.1.2 Inisialisasi Populasi Ukuran populasi akan berpengaruh pada proses pengolahan parameter melalui operator genetik. Semakin besar ukuran populasi, semakin tidak efisien pencapaian target optimasi yang telah ditentukan. Nilai efisien ukuran populasi dapat diperkirakan dari beberapa kali percobaan. 2.1.3 Evaluasi Populasi Seleksi berguna untuk mencapai nilai target yang ditentukan dari optimasi parameter yang ingin dicapai. Setiap kromosom dari populasi akan dievaluasi berdasarkan fungsi objektif yang bekerja dengan mengolah parameter-parameter yang telah dikodekan dari setiap kromosom. 2.1.4 Kawin Silang Pada tahap reproduksi, probabilitas kawin silang dan metoda kawin silang yang digunakan akan memengaruhi kecepatan proses pencarian solusi. Untuk mendapatkan probabilitas kawin silang yang sesuai, perlu dilakukan serangkaian uji coba. Ada beberapa metode kawin silang berdasarkan pola pertukaran gen, yaitu: one-point crossover, multipoint crossover dan uniform crossover [6].

offspring yang baru terbentuk untuk bergerak menuju lokal optimum populasi. Algoritma Genetik digunakan untuk melakukan penjelajahan menyeluruh dalam sebuah populasi, selama metode heuristik digunakan untuk membentuk lokal eksploitasi di sekitar kromosom [2]. Beberapa algoritma yang menggunakan hibrid genetik dengan heuristik adalah Lamarckian Evolution dan Algoritma Memetic. 3. Analisis dan Perancangan Perangkat lunak yang dibangun merupakan prototipe untuk implementasi penggunaan gabungan algoritma genetik dengan greedy search sehingga dapat ditemukan satu alternatif jalur terbaik dari sekumpulan alternatif jalur yang direpresentasikan oleh kromosom. Perangkat lunak penentuan rute perjalanan ini memiliki empat proses utama yaitu masukan, isolasi area pencarian, pencarian rute perjalanan dan administrasi. Penggunaan algoritma greedy search terletak pada isolasi area pencarian dan nilai kumulatif tertinggi setiap parameter sebagai batas maksimum nilai fitness . 3.1 Diagram Konteks Diagram konteks merupakan gambaran secara menyeluruh yang menunjukkan keterkaitan antara sistem dengan entitas eksternal, seperti ditunjukkan pada Gambar 1.

2.1.5 Mutasi Proses mutasi yang terlalu sering akan menghasilkan individu yang buruk akibat rusaknya untaian kromosom individu superior, sehingga munculnya individu superior mungkin akan berjalan lambat atau sama sekali tidak dihasilkan. Untuk itu probabilitas mutasi yang digunakan harus dipertimbangkan, salah satunya melalui uji coba agar mempercepat proses pencarian solusi.

Gambar 1. Diagram Konteks

2.2 Greedy Search Greedy Search merupakan Best First Search dengan hanya mempertimbangkan harga perkiraan (estimated cost) [6]. Dapat dikatakan greedy search merupakan panduan (heuristik) dalam pemilihan solusi. Fungsi heuristik yang dirancang dengan baik dapat memainkan peranan penting dalam memandu proses pencarian yang efisien untuk mendapatkan solusi melalui arah yang menguntungkan [7]. 2.3 Algoritma Hibrid Genetik Salah satu bentuk algoritma hibrid genetik yang sering dilakukan adalah menggabungkan lokal optimasi sebagai tambahan pada iterasi algoritma genetik. Lokal optimasi disertakan ke setiap generasi

Gambar 2. Diagram Aliran Data Level-1

Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Juni 2005, Vol. 10, No. 1

43

3.2 Diagram Aliran Data Level-1 Pada level-1, terdapat proses-proses masukan, isolasi area pencarian, pencarian rute perjalanan dan administrasi yang saling berhubungan dalam mengelola masukan untuk diagram konteks Diagram aliran data level-1 ditunjukkan pada Gambar 2. 3.2.1 Proses masukan Proses masukan berfungsi mengolah informasi yang diperoleh dari user sehingga didapatkan titik lokasi asal dan tujuan berdasarkan kumpulan data titik simpang. Masukan pertama user adalah titik awal dan titik tujuan, yang selanjutnya diproses melalui suatu query untuk menghasilkan titik koordinat asal (X1,Y1) dan tujuan (X2,Y2). Masukan kedua adalah ketentuan nilai prioritas kebutuhan terhadap jarak, biaya, waktu dan keamanan. Hasil query berupa titik koordinat asal dan tujuan yang digunakan sebagai bahan masukan bagi proses kedua yaitu isolasi daerah pencarian. 3.2.2 Proses isolasi daerah pencarian Proses ini untuk membatasi area pencarian menemukan sekumpulan alternatif jalur sehingga sekumpulan alternatif jalur perjalanan tidak meluas karena dapat memakan waktu proses lebih lama ketika membentuk sebuah kromosom. Guna menangani kejadian dimana nilai solusi yang dituangkan dalam nilai fitness terbaik suatu kromosom di suatu area ke-n lebih besar terhadap nilai fitness pada area ke n+1, maka proses penghitungan dilakukan minimal dua kali. Jika nilai fitness kromosom terbaik lebih bagus pada area ke-n dibandingkan area ke- n+1 maka proses isolasi daerah pencarian berhenti, dan kromosom terbaik pada area ke-n akan tampil sebagai solusi rute perjalanan terbaik. Namun jika tidak, maka isolasi daerah pencarian akan diperluas dengan hitungan sebagai berikut: X1 = X1 – d Y1 = Y1 – d

X 2 = X2 + d Y2 = Y2 + d

(1)

dengan: X1 Y1 X2 Y2 d

= = = = =

titik koordinat X asal perjalanan titik koordinat Y asal perjalanan titik koordinat X tujuan perjalanan titik koordinat Y tujuan perjalanan nilai jarak pertambahan area lokasi pencarian dalam kilometer.

3.2.3 Proses pencarian rute perjalanan Proses pencarian rute perjalanan ditujukan untuk menghasilkan solusi rute perjalanan terbaik, yang dilakukan dengan enam tahapan berikut: i. Melakukan inisialisasi untaian yang disebut

populasi berbentuk kromosom. Jumlah

kromosom yang digunakan adalah 2n, dengan n merepresentasikan jumlah titik persimpangan tujuan. Adanya faktor bilangan pengali 2 karena setiap perjalanan menuju suatu titik simpang akan ditempuh dengan menggunakan angkutan umum. Proses pembentukan sebuah kromosom akan berhenti bila titik simpang yang didapat sama dengan titik simpang tujuan perjalanan. ii. Mengevaluasi setiap kromosom yang ada dalam populasi tersebut. Fungsi fitness digunakan untuk menghitung nilai kumulatif keempat parameter dalam menentukan kromosom terbaik. Formula fitness yang digunakan yaitu : 4

n

Eval (Y )

ci ( xij

hi )

(2)

i 1 j 1

dengan: c merupakan prioritas keputusan yaitu: jarak, biaya, tingkat kemacetan, dan tingkat kriminal; variabel xij adalah nilai prioritas ke-i untuk kromosom ke-j; variabel hi adalah nilai perkiraan heuristik untuk parameter ke-i yang diperoleh dari nilai minimum prioritas ke-i dari seluruh kromosom pada populasi tersebut. Jika nilai perbandingan keempat prioritas adalah satu dan nilai heuristik diabaikan, maka batas nilai fungsi fitness-nya adalah 0 ≤ Eval(Y) ≤ 4, dengan nilai 0 menunjukkan kromosom terbaik, dan 4 menunjukkan nilai kromosom terburuk. iii. Membuat kromosom baru dengan melakukan kawin silang antar-dua kromosom atau mutasi pada sebuah kromosom jika diperlukan. iv. Melakukan replacement sebagian kromosom yang terdapat pada populasi asal dengan kromosom anak (offspring) yang nilai fitness-nya lebih baik. Metode yang digunakan yaitu steadystate reproduction. v. Mengevaluasi sekumpulan kromosom baru dan memasukkannya ke populasi selanjutnya. vi. Jika waktu pemrosesan telah habis menurut parameter yang digunakan, maka hentikan proses pencarian dan tampilkan kromosom terbaik. Selanjutnya kromosom tersebut akan dikodekan kembali (encoding) ke dalam bentuk rute perjalanan sebagai solusi akhir. 3.2.4 Proses Administrator Proses ini digunakan untuk menyimpan data yang dibutuhkan oleh proses pencarian rute perjalanan. Perubahan data parameter seperti kecepatan rata-rata kendaraan yang dibutuhkan oleh proses pencarian rute perjalanan didasarkan informasi saat itu di lapangan. 3.3 Perancangan Basis Data Basis data terkait dengan jaringan data yang mendukung bekerjanya suatu sistem yang diberikan.

Perangkat Lunak Penentuan Rute Transportasi Umum dengan Algoritma Pencarian Hybrid Greedy dan Genetik (Fivien Nur Savitri)

44

Penggambaran jaringan data menggunakan notasi grafis yang disebut dengan Diagram E-R, seperti diperlihatkan pada Gambar 3. RUTE ANGKOT Kode Angkot char(2) Nama Jurusan Varchar(50) Biaya Decimal(5.0)

Kode Angkot Titik Simpang Titik Simpang Tujuan

melewati

char(2) char(3) char(3)

a. b. c. d.

Jumlah Populasi = {10, 20, 30, 40, 50} Probabilitas Kawin Silang = 0,1 Probabilitas Mutasi = 0,01 Waktu Pemrosesan ≤ 10 detik

Hasil pengujian memberikan jumlah populasi maksimum sebesar 30. Hasil pengujiannya secara lengkap ditunjukkan pada Gambar 4.

berdasarkan

SIMPANG

berada pada

Titik Simpang Titik Simpang Tujuan Kode Jalan

Char(3) Char(3) Char(3)

Titik Simpang KoordX menghubungkan KoordY Persimpangan

Pengujian Nilai Fitness terhadap Jumlah Populasi

Char(3) Decimal(4.5) Decimal(4.5) Varchar(100)

3.00

memiliki nilai

PARAMETER Titik Simpang Titik Simpang Tujuan Waktu Rawan Kriminal Rawan Kemacetan

2.6166

2.50

Nilai Fitness

ARAH

JALAN Kode Jalan Char(3) Jalan Varchar(100)

Char(3) Char(3) Integer(2) Integer(2) Integer(2)

2.3611

2.2095

2.00

2.1242

2.0814

1.50 1.00 0.50 0.00 10

20

30

40

50

Jumlah Populasi

Gambar 3. Diagram E-R Gambar 4. Pengujian Nilai Fitness terhadap Jumlah Populasi

3.4 Perancangan Dialog Perangkat lunak diimplementasikan dengan menyediakan kotak-kotak dialog yang memudahkan user dalam melakukan penentuan rute transportasi umum yang akan diambilnya, yaitu meliputi: a. Dialog Nilai Parameter b. Dialog Masukan dan Keluaran c. Dialog Updating Kecepatan Kendaraan dan Tingkat Kriminal d. Dialog Updating Tarif e. Laporan Data Kromosom f. Laporan Nilai Fitness per Populasi 4. Pengujian

4.1.2 Pengujian Jumlah Generasi Sama halnya dengan pengujian jumlah populasi, pada pengujian jumlah generasi digunakan setting parameter yang sama namun menggunakan jumlah populasi maksimum sebelumnya, yaitu: a. Jumlah Populasi = 30 b. Generasi = {5, 6, 7, 8, 9, 10} c. Probabilitas Kawin Silang = 0,1 d. Probabilitas Mutasi = 0,01 e. Waktu Pemrosesan ≤ 10 detik Hasil pengujian pada Gambar 5 memberikan jumlah generasi optimum adalah 6.

Pengujian terhadap algoritma genetik dilakukan berdasarkan pada parameter-parameter pembentuknya. Dari pengujian ini dapat diketahui suatu konfigurasi maksimal. Pada penelitian ini, batasan waktu pemrosesan ditetapkan tidak lebih dari 10 detik dari batasan area yang sama tanpa dilakukan penambahan terhadapnya. Selanjutnya akan dilakukan pengujian melalui tiga jenis metode.

Pengujian Nilai Fitness terhadap Jumlah Generasi 3.50 3.2071

Nilai Fitness

3.00

2.9474

2.7362

2.50

2.4122

2.5590

2.3700

2.00 1.50 1.00 0.50 0.00 5

4.1 Metode Pengujian Pertama Pengujian pertama dilakukan dengan menggunakan peta jaringan lalu lintas Kota Bandung yang telah direpresentasikan ke dalam basisdata bernama bandung.mdb. Pada kumpulan data tersebut terdapat 84 titik simpang, 204 busur jalan, dan 23 trayek angkutan kota. Perangkat lunak akan diimplementasikan pada operator 108 dengan rata-rata panjang pembicaraan selama 10 – 20 detik. 4.1.1 Pengujian Jumlah Populasi Untuk mengetahui pengaruh jumlah populasi terhadap rata-rata fitness yang diperoleh, digunakan setting parameter sebagai berikut:

6

7

8

9

10

Jumlah Generasi

Gambar 5. Pengujian Nilai Fitness terhadap Jumlah Generasi 4.1.3 Pengujian Probabilitas Kawin Silang a. b. c. d. e.

Setting parameter yang digunakan adalah : Jumlah Populasi = 30 Generasi = 6 Probabilitas Kawin Silang = {0,1; 0,2; ...; 0,9} Probabilitas Mutasi = 0,01 Waktu Pemrosesan ≤ 10 detik

Hasil pengujian pada Gambar 6 menunjukkan bahwa probabilitas kawin silang optimum adalah 0,1.

Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Juni 2005, Vol. 10, No. 1

45

4.00 3.50 3.00 2.50 2.00 1.50 1.00 0.50 0.00

3.6250

3.5448

3.6475

3.5493

3.6185

3.5665

3.2067

3.4339

a. terdapat (84 2) – 1 = 167 titik simpang, dikurangi satu karena terdapat satu titik simpang terkanan yang digunakan sebagai garis pencerminan vertikal. b. terdapat 203 2 = 406 busur jalan.

2.3700

Pengujian Nilai Fitness terhadap Jumlah Populasi (2-fold) 3.20

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Probabilitas Kawin Silang

Nilai Fitness

Nilai Fitness

Pengujian Nilai Fitness terhadap Probabilitas Kawin Silang

2.80

2.80 2.7306

2.40

2.5334

2.3700

2.5060

2.3432

2.30 2.20 2.10 0.02

0.03

0.04

50

2.5800

2.4571

0.01

40

Dari hasil pengujian jumlah populasi pada Gambar 8, diperoleh jumlah populasi maksimum 30 kromosom, sama dengan hasil pengujian pada data sebelumnya. Dapat disimpulkan bahwa nilai parameter yang digunakan masih memenuhi untuk area peta lalu lintas yang diperluas, sehingga dapat digunakan setting parameter yang sama: a. Jumlah Populasi = 30 b. Generasi = 6 c. Probabilitas Kawin Silang = 0,1 d. Probabilitas Mutasi = 0,06 e. Waktu Pemrosesan ≤ 10 detik

0.05

0.06

0.07

0.08

0.09

Probabilitas Mutasi

Gambar 7. Pengujian Nilai Fitness terhadap Probabilitas Mutasi 4.2 Metode Pengujian Kedua Pengujian Kedua dilakukan untuk aplikasi dengan area peta yang memiliki titik simpang sebanyak mungkin. Dalam hal ini digunakan data jaringan lalu lintas dummy yang diperoleh dari pencerminan ke kanan atau ke kiri, ke bawah atau ke atas, dan seterusnya terhadap peta sebelumnya. Hasil pencerminan pertama ke arah kanan disebut sebagai peta jaringan 2-fold yang disimpan dalam basisdata bernama 2fold.mdb. Kemudian dicerminkan kembali ke arah bawah dengan nama 4fold.mdb, dan 8fold.mdb sebagai hasil pencerminan ketiga kali ke arah kanan, dan seterusnya.

4.2.2 Pengujian 4-Fold Data peta 4-Fold diambil dari pencerminan ke kanan kemudian ke bawah dari terhadap peta asal dengan mengambil garis vertikal terhadap sumbu X titik simpang terkanan dan selanjutnya garis horisontal terhadap sumbu Y titik simpang terbawah, sehingga diperoleh hasil: a. (167 2) – 2 = 332 titik simpang, dan b. 812 busur jalan Pengujian dilakukan sebanyak 10 kali proses untuk setiap populasi ke-10 sampai dengan ke-50. Populasi 60 dan seterusnya diabaikan karena pada pengujian pertama yang masih menggunakan data asal, waktu pemrosesannya membutuhkan lebih dari 10 detik. Hasil pengujiannya disajikan di Gambar 9. Pengujian Nilai Fitness terhadap Jumlah Populasi (4-fold) 3.50 3.00

Nilai Fitness

Nilai Fitness

2.5517

30

Gambar 8. Pengujian Nilai Fitness terhadap Jumlah Populasi 2-Fold

Pengujian Nilai Fitness terhadap Probabilitas Mutasi

2.50

20

Jumlah Populasi

Hasil pengujian pada Gambar 7 menunjukkan bahwa probabilitas mutasi optimum adalah 0,06.

2.6038

2.6641

10

Setting parameter yang digunakan adalah : Jumlah Populasi = 30 Generasi = 6 Probabilitas Kawin Silang = 0,1 Probabilitas Mutasi = {0,01; 0,02; ... ;0,09} Waktu Pemrosesan ≤ 10 detik

2.60

2.7957

2.60

4.1.4 Pengujian Probabilitas Mutasi

2.70

2.9315

2.40

Gambar 6. Pengujian Nilai Fitness terhadap Probabilitas Kawin Silang

a. b. c. d. e.

3.1416 3.0455

3.00

2.9962

2.8886

2.7206

2.5607

2.50

2.4734

2.00 1.50 1.00 0.50 0.00 10

4.2.1 Pengujian 2-Fold Data hasil kelipatan dua dari peta jaringan sebelumnya yaitu 2fold.mdb memiliki karakteristik:

20

30

40

50

Ju ml ah Popu l asi

Gambar 15. Pengujian Nilai Fitness terhadap Jumlah Populasi 4-Fold

Perangkat Lunak Penentuan Rute Transportasi Umum dengan Algoritma Pencarian Hybrid Greedy dan Genetik (Fivien Nur Savitri)

= 1A3A 2B5B 4C6C 7 = 1B2B 5B4B 7B5C 3 = 1B2A 4C6C 7C4A 7 = 1B2B 5C3C 4C6C 7 …. ….. = 1A3A 2B5C 3C4B 7 = 1B2A 4B7C 63A1 A

46

4.2.3 Pengujian 8-Fold Data yang diuji adalah gabungan antara data 4fold dengan hasil pencerminannya ke arah kanan, sehingga menghasilkan: a. (332 2) – 2 = 662 titik simpang, dan b. 1.624 busur jalan. Dengan menggunakan metode pengujian yang sama, pada 10 kali proses pertama aplikasi tidak dapat menghasilkan jalur solusi, karena tidak ada satupun kromosom terbentuk pada saat inisialisasi populasi, sehingga tidak terjadi operasi genetik terhadapnya. Demikian pula halnya bila batasan waktu proses ditambah menjadi 20 detik, sehingga pada kasus ini aplikasi tidak dapat menangani untuk area yang diperluas sebanyak 8 kali. Dengan kata lain, aplikasi ini hanya dapat menghasilkan jalur solusi untuk jumlah titik simpang maksimal sebanyak 332. 4.3 Metode Pengujian Ketiga Pada metode ini, akan dilakukan pengujian dengan kasus tertentu yang memungkinkan terjadinya kegagalan proses. 4.3.1 Kasus Pertama Jika data titik simpang asal dan tujuan rute perjalanan yang dimasukkan adalah sama, maka dari hasil pengujian didapatkan bahwa aplikasi ini tidak menghasilkan satu pun kromosom pada saat proses inisialisasi populasi, sehingga tidak terjadi operasi genetik terhadapnya. Namun kasus ini bisa diatasi lebih dini, salah satunya dengan menampilkan pesan layar bahwa data yang dimasukkan adalah invalid.

Setelah melihat hasil pengujian untuk kasus kedua, maka dapat dikatakan aplikasi ini masih belum mampu menangani secara maksimal untuk kasus pencarian rute perjalanan di luar area, jika waktu proses yang digunakan kurang dari 20 detik. 5. Kesimpulan dan Saran Dapat disimpulkan bahwa perangkat lunak ini dapat berjalan dengan batasan maksimal jumlah populasi sebesar 30 kromosom, jumlah generasi 6, probabilitas kawin silang 0.1, probabilitas mutasi 0.06, dan maksimal titik yang dapat dibangun sejumlah 332. Perangkat lunak aplikasi ini memadai untuk diimplementasikan dengan menggunakan operator khusus seperti pada operator penerangan 108, karena tidak menyertakan gambar atau peta wilayah Kota Bandung dalam salah satu tampilan dialognya. Daftar Pustaka [1] Davis, 1991, Handbook of Genetic Algorithms, Van Nostrand Reinhold. [2] Gen and Cheng, 1996, Genetic Algorithms & Engineering Design, John Wiley & Son, Inc. [3] Goldberg, David E., 1989, Genetic Algorithms in search, optimization and machine learning, Addison Wesley. [4] Michalewicz, 1996, Genetic Algorithms + Data Structure = Evolution Program, SpringerVerlag. [5] Pressman, 1997, Software Engineering: A Practtioner’s Approach, McGraw-Hill. [6] Setiawan, Andi, 1993, Artificial Intelligent, Andi Offset, Yogyakarta.

4.3.2 Kasus Kedua Kasus kedua timbul akibat adanya pembatasan area berdasarkan koordinat titik asal dan tujuan, yang sejalan dengan proses didalamnya, area tersebut akan semakin meluas setiap beberapa kilometer sesuai yang dikehendaki. Jika titik simpang asal dan tujuan tidak memiliki hubungan atau tidak terdapat busur jalan yang dapat menghubungkannya di dalam area tersebut, maka hal ini dapat menyebabkan terjadinya kegagalan proses pada saat inisialisasi populasi. Dari hasil pengujian sebanyak 99 kali dan penambahan area sebesar 2 km dengan menggunakan titik simpang asal dan tujuan seperti kondisi diatas, maka diperoleh hasil pada Tabel 1.

[7] Sukmono, Gito, 1999, Aplikasi Algoritma Genetik untuk Pengendalian Ruting Dinamis, STT Telkom. [8] Suyanto, 2002, Intelijensia Buatan, Jurusan Teknik Informatika, STT Telkom, Bandung.

Tabel 1. Hasil Pengujian Kasus 2 No. 1. 2. 3. 4.

Waktu Proses (detik) 10 20 40 80

Persentase Keberhasilan (%) 13,1 20,2 51,5 86,8

Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Juni 2005, Vol. 10, No. 1