BAB II TINJAUAN PUSTAKA

BAB II

TINJAUAN PUSTAKA

2.1. Pendahuluan Pada bab ini akan dibahas tentang travelling salesman problem (TSP), metodemetode yang digunakan dalam penyelesaian TSP. Khusus penggunaan metode algoritma genetika akan dipaparkan secara teoritis mengenai tahap-tahap yang dilakukan dalam penggunaan metode algoritma mulai dari representasi kromosom, fungsi fitness, seleksi, crossover, mutasi.

2.2. Travelling Salesman Problem (TSP)

Travelling Salesman Problem (TSP) merupakan sebuah permasalahan optimasi yang dapat diterapkan pada berbagai kegiatan seperti routing. Masalah optimasi TSP terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Pokok permasalahan dari TSP adalah seorang salesman harus mengunjungi sejumlah kota yang diketahui jaraknya satu dengan yang lainnya. Menurut Arora (2000), pada traveling Salesman Problem (TSP) kita diberikan n buah simpul dan untuk setiap pair { i, j}, sebuah jarak d ij . Kita menginginkan sebuah path tertutup yang mengunjungi setiap simpul tepat sekali dan mencari biaya minimum, yang merupakan penjumlahan dari jarak-jarak yang ada pada path tersebut.

2.2.1. Sejarah Permasalahan TSP Permasalahan matematika tentang Traveling Salesman Problem dikemukakan pada tahun 1800 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Penyngton.

Universitas Sumatera Utara

Bentuk umum dari TSP pertama dipelajari oleh para matematikawan mulai tahun 1930. Diawali oleh Karl Menger di Vienna dan Harvard. Setelah itu permasalahan TSP dipublikasikan oleh Hassler Whitney dan Merrill Flood di Princeton. Penelitian secara detail dari hubungan antara Menger dan Whitney, dan perkembangan TSP sebagai sebuah topik studi dapat ditemukan di makalah Alexander Schrijver’s “On the history of combinatorial optimization (till 1960)”

2.2.2. Perkembangan Pemecahan TSP Untuk menilai apakah kita melakukan perkembangan dalam menyelesaikan permasalahan TSP, kita pasti menilai dari jumlah waktu yang makin berkurang. Misal kita memiliki metode baru A yang lebih cepat menyelesaikan permasalahan TSP dibanding metode B, kita akan menilai bahwa kita telah menemukan solusi lebih baik. Tetapi masalah perangkingan untuk metode ini akan sangat sulit dilakukan, karena metode-metode yang sangat berkaitan erat satu sama lain tidak dapat dinilai hanya melalui perbandingan yang sederhana (permasalahanpermasalahan TSP yang ringan). Oleh karena itu, untuk memutuskan apakah metode A lebih baik dibandingkan metode B, Kita harus mengesampingkan hasil dari contoh-contoh kasus yang sederhana dan dapat diselesaikan oleh hampir semua metode pemecahan permasalahan TSP. Saat ini kita seharusnya berkonsentrasi pada permasalahan-permasalahan yang benar-benar sulit yang sangat sulit terpecahkan sampai saat ini. Dari permasalahan-permasalahan yang sangat sulit ini, kita gunakan metode A dan metode B untuk menyelesaikannya. Setelah itu kita dapat memutuskan metode A lebih baik dari metode B jika untuk setiap permasalahan n-kota dengan n bilangan yang besar, metode A lebih cepat dalam menyelesaikan permasalahan dibanding metode B. Agar perbandingan metode-metode TSP ini dapat diaplikasikan, kita dapat menganalisis solusi-solusi dari sebuah metode dan menjamin bahwa setiap n akan memakan sejumlah waktu f(n). Jadi f(n) fungsi waktu dari sebuah metode terhadap jumlah kota (n). Untuk membandingkan dua buah metode, kita cukup


membandingkan fungsi f(n) dari masing-masing metode. Hal ini tentu saja dapat menghasilkan perhitungan yang salah ketika ada metode yang baik tapi dianalisis dengan buruk sehingga menghasilkan f(n) yang buruk. Dalam banyak permasalahan komputasional, studi tentang algoritma+fungsi telah menghasilkan solusi matematika yang sangat bagus, yang penting dalam pengembangan untuk penyelesaian permasalahan praktis. Hal ini telah menjadi subjek studi yang utama dalam sains komputer. Untuk setiap permasalahan TSP akan sangat mudah kita katakan bahwa fungsi f(n)-nya adalah (n-1)!=n-1 x n-2 x n-3 x ...x 3 x 2 x 1 dan jumlah jalur yang mungkin terjadi adalah (n-1)!/2. Hasil yang lebih baik ditemukan pada tahun 1962 oleh Michael Held dan Richard Karp, yang menemukan algoritma dan fungsi yang mempunyai proporsi n22n, yaitu n x n x2 x 2 x … x 2, dimana ada sebanyak n perkalian dua. Untuk setiap n bernilai besar, fungsi f(n) Held-Karp akan selalu lebih kecil dibandingkan (n-1)!. Untuk setiap orang yang tertarik untuk menyelesaikan permasalahan TSP dalam jumlah besar, ada sebuah berita buruk bahwa selama 43 tahun sejak Held dan Karp menemukan fungsi f(n)= n22n ternyata tidak ditemukan fungsi f(n) yang lebih baik lagi. Hal ini tentu saja sangat mengecewakan karena dengan n=30 fungsi f(n) Held-Karp menghasilkan nilai yang sangat besar, dan untuk n=100 merupakan sesuatu yang mustahil untuk diselesaikan oleh kemampuan komputer saat ini. Perkembangan fungsi f(n) dalam TSP yang sangat lambat ini mungkin memang tidak dapat kita hindari; dengan komputer saat ini bisa jadi memang tidak ada metode yang menghasilkan f(n) yang mempunyai performansi yang baik, misal nc dimana c adalah sebuah angka konstanta, oleh karena itu, n x n x n x … x n dimana n muncul sebanyak c kali. TSP secara sederhana dapat didefinisikan sebagai proses pencarian lintasan terefisien dan terpendek dari beberapa kota yang dipresentasikan, melewati setiap kota tersebut dan kembali ke kota awal. Setiap kota hanya bisa sekali disinggahi. Persoalan yang dihadapi TSP ialah bagaimana merencanakan total jarak yang


minimum. Untuk menyelesaikan persoalan tersebut, tidak mudah dilakukan karena terdapat ruang pencarian dari sekumpulan permutasi sejumlah kota. Maka TSP kemudian dikenal dengan persoalan Non Polinomial. Gambaran sederhana dari pengertian TSP adalah sebagai berikut:

Gambar 2.1. Posisi kota-kota yang akan dilewati

Kota-kota pada gambar 1., masing-masing mempunyai koordinat (x,y), sehingga jarak antar kedua kota dapat dihitung dengan rumus:

(x1 − x2 )2 + ( y1 − y 2 )2

d12 =

...................................................

(2.1)

Setelah jarak-jarak yang menghubungkan tiap kota diketahui, maka dicari rute terpendek dari jalur yang akan dilewati untuk kembali ke kota awal.

Gambar 2.2. Rute optimal yang telah dicari

Pencarian Lintasan Terpendek dapat dinyatakan dengan persamaan: n

n

Min∑∑ d k ,m k −1 m −1

.................................................................................... (2.2)


2.3. Metode-metode Penyelesaian TSP Banyak metode yang dapat dipakai untuk menyelesaikan TSP antara lain : Greedy Heuristic, Ant Colony System, Simulated Annealing, Tabu Search. Metode lain yang dapat dipakai untuk menyelesaikan TSP adalah algoritma genetik. Algoritma genetik merupakan sebuah algoritma yang meniru cara kerja proses genetika pada makhluk hidup, dimana terdapat proses seleksi, rekombinasi dan mutasi untuk mendapatkan kromosom terbaik pada suatu generasi

2.3.1. Metode Aproksimasi (Greedy Heuristic) Pada algoritma ini, pemilihan lintasan akan dimulai pada lintasan yang memiliki nilai paling minimum, setiap mencapai suatu kota, algoritma ini akan memilih kota selanjutnya yang belum dikunjungi dan memiliki jarak yang paling minimum. Algoritma ini disebut juga Nearest Neighbour. Kompleksitas algoritma ini memang sangat mengagumkan yaitu O(n), tetapi hasil yang kita dapat bisa sangat jauh dari hasil yang optimal, semakin banyak kota semakin besar pula perbedaan hasil yang dicapai. Misalnya untuk contoh kasus yang sama dengan algoritma Branch and Bound sebelumnya yang menghasilkan nilai 15, maka algoritma ini menghasilkan nilai 18 berbeda sebesar 20% dari hasil sebelumnya padahal jumlah kota hanya 5 buah.

2.3.2. Metode Heuristic Teknik ini digunakan untuk mencari jawaban dari masalah kombinatorial dengan secepat mungkin. Algoritma tradisional akan gagal ketika menghadapi permasalahan yang sangat rumit, seperti permasalahan TSP dengan jumlah kota (n) yang sangat besar. Metode

Heuristic

memberikan

pendekatan

untuk

menyelesaikan

permasalahan optimasi kombinatorial. Optimasi kombinatorial akan memberi kita hasil yang mungkin dan mencari yang hasil yang mendekati optimal dari hasilhasil tersebut. Tetapi mungkin memang tidak ada metode Heuristik yang menghasilkan solusi yang merupakan solusi optimal. Metode Heuristik seperti


simulated annealing, algoritma genetika, tabu search, ant colony system mengusahakan suatu cara untuk mencari hasil yang baik tapi bukan yang terbaik.

2.4. Algoritma Genetik Algoritma genetik pertama kali diperkenalkan oleh John Holland dalam bukunya yang berjudul “Adaption in natural and artificial systems”, dan oleh De Jong dalam bukunya “Adaption of the behavior of a class of genetic adaptive systems”, yang keduanya diterbitkan pada tahun 1975, yang merupakan dasar dari algoritma genetik (Davis, 1991). Teori Holland menerangkan suatu metode untuk mengklasifikasikan obyek-obyek, kemudian secara selektif mengawinkan obyek-obyek tersebut satu sama lain untuk menghasilkan obyek baru untuk kemudian diklasifikasikan lagi. Hal ini didasarkan atas kreasi untuk tujuan memodelkan teori seleksi natural Darwin dari suatu bentuk makhluk hidup. Algoritma genetik merupakan teknik pencarian yang didasarkan atas mekanisme seleksi dan genetik natural. Algoritma genetik berbeda dengan tehnik pencarian konvensional, dimana pada algoritma genetik kondisi diawali dengan setting awal solusi acak yang disebut populasi. Tiap individu dalam populasi disebut kromosom, yang merepresentasikan suatu solusi atas permasalahan. Kromosom adalah suatu string simbol, yang umumnya merupakan string bit biner. Kromosom berevolusi melalui iterasi berkelanjutan, yang disebut generasi. Pada setiap generasi, kromosom dievaluasi berdasarkan suatu fungsi evaluasi (Gen M. et.all, 1997). Untuk menghasilkan generasi berikutnya, kromosom baru yang disebut offspring, dibentuk baik melalui penyatuan dua kromosom dari generasi awal menggunakan operator perkawinan silang (crossover) atau memodifikasi kromosom menggunakan operator mutasi (mutation). Suatu generasi baru dibentuk melalui proses seleksi beberapa induk (parents) dan anak (offspring), sesuai dengan nilai fitness, dan melalui eliminasi kromosom lainnya agar ukuran populasi tetap konstan. Kromosom yang sesuai memiliki kemungkinan tertinggi untuk dipilih. Setelah beberapa generasi, algoritma menghasilkan kromosomkromosom terbaik yang diharapkan mewakili solusi optimal atau suboptimal atas


permasalahan. Bila P(t) dan C(t) masing-masing merupakan parents dan offspring pada suatu generasi t, struktur umum algoritma genetik dapat dijelaskan sebagai berikut: Procedure: Genetic Algorithm begin t ← 0; initialize P(t); evaluate P(t); while (not termination condition) do recombine P(t) to yield C(t); evaluate C(t); select P(t + ) from P(t) and C(t); t ← t + 1; end end Struktur algoritma tersebut merupakan versi modifikasi dari Grefenstette dan Baker (1989). Umumnya, inisialisasi diasumsikan acak (random). Rekombinasi umumnya melibatkan crossover dan mutation untuk menghasilkan offspring. Sesungguhnya hanya ada dua macam operasi dalam algoritma genetik, yaitu: 1. Operasi genetik: crossover dan mutasi. 2. Operasi evolusi: selection. Operasi genetik mencerminkan proses hereditas gen untuk menciptakan offspring baru pada tiap generasi. Operasi evolusi mencerminkan proses evolusi Darwin untuk menghasilkan populasi dari generasi ke generasi. Crossover merupakan operator genetik utama, yang dioperasikan pada dua kromosom pada suatu waktu dan menghasilkan offspring dengan mengkombinasikan pola-pola kedua kromosom. Cara termudah untuk melakukan crossover adalah dengan pemilihan

cut-point

secara

acak

dan

membentuk

offspring

dengan

mengkombinasikan segmen sebelah kiri dari cut-point salah satu parent dengan segmen sebelah kanan dari cut-point parent lainnya. Metode ini berjalan baik pada


representasi bit string. Kinerja algoritma genetik tergantung atas kinerja operator crossover yang digunakan.

crossover 110010 1010 101110 1110 chromosome s 1100101010 encoding

1011101110

110010 1110 101110 1010

solutions 0011011001 mutation 1100110001 00110 1 1001

00110 0 1001

evaluation selection

offspring 110010 1110 101110 1010 00110 01001

New population

decoding Roulette wheel solutions

Fitness computation

Gambar 2.3. Struktur Utama Algoritma Genetik Sumber: (Gen M. et.all, 1997). Probabilitas crossover (p c ) didefinisikan sebagai rasio jumlah offspring yang dihasillkan dalam tiap generasi atas ukuran populasi (pop_size). Rasio ini mengendalikan jumlah p c x pop_size yang diharapkan dari kromosom untuk menjalankan operasi crossover. Tingkat crossover yang tinggi memperbolehkan


eksplorasi solusi lebih luas dan mengurangi kemungkinan menghasilkan kesalahan optimasi, tetapi apabila tingkat rasio terlalu tinggi, maka akan menghasilkan pemborosan waktu komputasi atas eksplorasi kondisi-kondisi ketidakpastian terhadap solusi permasalahan.

2.4.1. Encoding Kromosom Langkah awal untuk mengimplementasikan suatu program komputer seringkali adalah pemilihan tipe data. Hal inilah yang merupakan variasi perbedaan awal antara teori asli Holland dan beberapa teori alternatif algoritma genetik lainnya yang kemudian muncul. Holland meng-encoding kromosom ke dalam suatu string digit biner. Sejumlah operasi encoding biner digunakan untuk menghasilkan algoritma genetik yang sederhana, efektif dan sesuai. Akan tetapi ada banyak cara untuk merepresentasikan gen suatu obyek, yang masing-masing memiliki keuntungan implisit tersendiri (Davis, 1991). Agar dapat merepresentasikan suatu problem ke dalam bentuk gen, substansi-substansi solusi harus direpresentasikan sebagai suatu kumpulan unit informasi (Davis, 1991).

2.4.2. Encoding dan Decoding Pada aturan algoritma genetik, kumpulan gen yang diencoding disebut dengan genotype, sedangkan data aktual yang diencoding disebut dengan phenotype (Gen M. et.all, 1997). Apakah phenotype diencoding untuk membentuk suatu genotype atau genotype didecoding untuk membentuk suatu phenotype, hanyalah menyangkut perbedaan penafsiran dalam literatur (Heitkoetter, 1993). Pada banyak kasus, nilai aktual tiap gen disebut dengan allele (Gen M. et.all, 1997). Menurut realitasnya, gen dari makhluk hidup disimpan berpasangan dan tiap induk hanya memunculkan satu gen untuk tiap pasangan (Sherwod, 1993). Hal ini berbeda dengan algoritma genetik, dimana gen tidak disimpan berpasangan, tetapi baik pada algoritma genetik dan bentuk nyata biologis, hanya sebagian gen induk yang diwariskan pada anak (offspring) (Davis, 1991).


2.4.3. Ukuran Populasi Langkah awal pada algoritma genetik adalah menginisialisasi keseluruhan populasi kromosom. Jumlah populasi ini harus ditentukan, tergantung pada teknik komputasi yang tersedia, perbedaan ukuran akan menghasilkan hasil optimal. Apabila ukuran populasi yang dipilih terlalu kecil, maka tingkat eksplorasi atas ruang pencarian global akan terbatas, walaupun arah menuju konvergensi lebih cepat. Apabila ukuran populasi terlalu besar, maka waktu akan banyak terbuang karena berkaitan dengan besarnya jumlah data yang dibutuhkan dan waktu ke arah konvergensi akan lebih lama (Goldberg, 1989).

2.4.4. Evaluasi Kromosom Populasi yang acak hampir selalu tidak sesuai (Davis, 1991). Untuk dapat menentukan yang mana yang lebih tepat, tiap obyek harus dievaluasi. Untuk mengevaluasi obyek, beberapa pengetahuan tentang lingkungan kerjanya harus diketahui supaya dapat tetap survive. Lingkungan ini diencoding secara parsial (atau secara parsial didecoding) untuk menyesuaikan dengan deskripsi permasalahan (Gen M. et.all, 1997).

2.4.5. Insialisasi Populasi Terdapat dua teknik umum untuk inisialisasi suatu populasi. Populasi obyek (keseluruhan informasi genetik tentang obyek dalam koloni) dapat diambil dari secondary storage. Data ini akan merupakan titik awal bagi evolusi yang terarah. Secara umum algoritma genetik dapat diawali dengan populasi acak. Hal ini merupakan ukuran penuh populasi obyek dimana operasi genetik ditentukan dengan proses acak (Davis, 1991).


2.4.6. Metode Seleksi Untuk Kepunahan atau Kelahiran Seleksi bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit. (Kusumadewi, 2005) Apabila populasi awal obyek telah dibentuk, dimana masing-masing diukur oleh fitness (atau biaya), maka dapat ditemukan nilai fitness keseluruhan. Apabila nilai fitness keseluruhan tidak setinggi yang diharapkan, sebagian obyek dalam populasi dapat diseleksi untuk dieliminasi (punah). Hal ini berkaitan berkaitan operator seleksi natural elitist (elitist natural selection) (Davis, 1991). Pada awal munculnya algoritma genetik, digunakan strategi penggantian untuk mempertahankan jumlah populasi tetap dengan menggantikan dua induk dengan dua offspring pada tiap generasi. Setelah itu strategi “crowding” dikembangkan dimana pada metode ini, satu offspring menggantikan induknya yang memiliki banyak kesamaan. Hal ini membutuhkan perbandingan gen per gen anak dengan tiap induknya, dan kondisi semacam ini membutuhkan perhitungan komputasi yang cukup rumit (Gen M. et.all, 1997). Tournament selection merupakan teknik lain untuk menentukan obyek mana yang akan dieliminasi. Pada metode ini, dua obyek dipilih dan diadu, pemenangnya akan melakukan reproduksi dan yang kalah akan punah (Rich, 1995). Hal ini meniru perilaku yang terjadi pada populasi rusa dalam jumlah besar dan kadang-kadang juga terjadi di antara manusia. Banyaknya obyek yang akan dieliminasi pada tiap generasi merupakan suatu hal yang harus benar-benar diperhatikan. Proporsi terminasi prematur dalam populasi menciptakan apa yang dinamakan dengan tekanan seleksi. Misalnya, pada kejadian nyata peristiwa seperti wabah, perang, banjir, jaman es merepresentasikan periode dimana tekanan seleksi cukup tinggi, yang tingkat tekanannya berbeda pada tiap kasus. Pada perkembangan teori algoritma genetik, metode seleksi obyek untuk melahirkan diatur dengan cara yang berbeda. Model dasar dari Holland mengunakan metode dimana yang paling sehat yang akan dipilih untuk melahirkan. Metode lain melakukan pilihan pada dua obyek secara acak untuk melahirkan. Kelahiran yang selektif dapat digunakan secara terpadu dengan atau


tanpa operator elitist natural selection untuk melakukan evolusi (Gen M. et.all, 1997). Pada populasi yang memiliki tingkat evolusi yang cukup tinggi, proses spesialisasi akan terjadi. Kondisi terjadinya intra-mating dari beberapa grup (spesies) menghasilkan offspring dengan nilai fitness tinggi dalam spesies, sedangkan perkawinan anggota spesies dengan anggota populasi yang bukan dalam spesies akan menghasilkan offspring dengan nilai fitness yang sangat rendah, yang disebut “lethals”. Lethal jarang bisa survive pada generasi selanjutnya (Heitkoetter, 1993). Tujuan kelahiran selektif adalah menghasilkan kromosom dengan nilai fitness tinggi (Gen M. et.all, 1997) dan untuk menghindari kelebihan produksi lethal (Heitkoetter, 1993). Beberapa metode seleksi dari induk, antara lain : 1. Rank Based Fitness Assignment 2. Roulette Wheel Selection 3. Stochastic Universal Sampling 4. Local Selection 5. Trunction Selection 6. Tournament Selection.

Roulettte Wheel Selection Metode seleksi dengan mesin roulette ini merupakan metode yang paling sederhana. Seleksi ini sering dikenal dengan nama stochastic sampling with replacement Seleksi ini bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang memiliki fitness tinggi untuk melakukan reproduksi. Algoritma dari seleksi roulette wheel : 1.

Dihitung nilai fitness masing-masing individu (f i , dimana i adalah individu ke 1 s/d ke-n

2.

Dihitung total fitness semua individu

3.

Dihitung fitness relatif masing-masing individu


4.

Dari fitness relatif tersebut, dihitung fitness kumulatifnya.

5.

Dibangkitkan nilai random

6.

Dari bilangan random yang dihasilkan, ditentukan individu mana yang terpilih dalam proses seleksi

2.4.7. Crossover Apabila induk telah dipilih, maka kelahiran dapat terjadi. Bagi tiap gen dalam kromosom obyek baru dihasilkan dari seleksi allele baik dari ibu atau bapak. Proses mengkombinasikan gen dapat dilakukan dengan beberapa cara. Metode paling sederhana disebut dengan single point crossover (Gen M. et.all, 1997; Davis, 1991). Metode ini dapat didemonstrasikan dengan jelas menggunakan gen yang diencoding dalam biner, walaupun begitu nantinya dapat ditranslasikan ke bentuk representasi gen manapun (Davis, 1991). Crossover (perkawinan silang) bertujuan menambah keanekaragaman string dalam populasi dengan penyilangan antar-string yang diperoleh dari sebelumnya. Beberapa jenis crossover tersebut adalah: 1. Crossover 1-titik Pada crossover dilakukan dengan memisahkan suatu string menjadi dua bagian dan selanjutnya salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain yang telah dipisahkan dengan cara yang sama. Proses yang demikian dinamakan operator crossover satu titik. Induk 1: 11001 | 010 Induk 2: 00100 | 111 Diperoleh : Anak 1: 11001 | 111 Anak 2: 00100 | 010

2. Crossover 2-titik Proses crossover ini dilakukan dengan memilih dua titik crossover. Kromosom keturunan kemudian dibentuk dengan barisan bit dari awal kromosom


sampai titik crossover pertama disalin dari orangtua pertama, bagian dari titik crossover pertama dan kedua disalin dari orangtua kedua, kemudian selebihnya disalin dari orangtua pertama lagi. Induk 1: 110 | 010 | 10 Induk 2: 001 | 001 | 11 Diperoleh : Anak 1 : 110 | 001 | 10 Anak 2 : 001 | 010 | 11 3. Crossover seragam (uniform) Crossover seragam manghasilkan kromosom keturunan dengan menyalin bit-bit secara acak dari kedua orangtuanya. Induk 1: 11001010 Induk 2: 00100111 Diperoleh : Anak 1: Anak 2:

4. Partial Mapped Crossover (PMX). PMX diciptakan oleh Goldberg dan Lingle. PMX merupakan rumusan modifikasi dari pindah silang dua-poin. Hal yang penting dari PMX adalah pindah silang dua poin ditambah dengan beberapa prosedur tambahan.

Pilih posisi untuk menentukan substring secara acak Induk 1

:1 2 3|4 5 6|7 8

Induk 2

:3 7 5|1 6 8|2 4

Diperoleh : Anak 1

:4 2 3|1 6 8|7 5

Anak 2

:3 7 8|4 5 6|2 1


Gambar 2.4. Pemetaan PMX Sumber (Larranaga P. et.all, 1999) Proses crossover dapat dilakukan dengan lebih dari satu crossover point (Gen M. et.all, 1997). Sesungguhnya, tiap titik dapat dipilih bagi crossover apabila kondisi tersebut lebih baik (Heitkoetter, 1993). Salah satu metode crossover yang seringkali digunakan dalam sistem multi-objective, adalah unity based crossover (Heitkoetter, 1993). Pada metode ini, tiap gen memiliki probabilitas yang sama muncul dari induk manapun, mungkin ada crossover point yang diletakkan di belakang pada tiap gen atau gen manapun (Heitkoettr, 1993).

2.4.8. Mutasi Setelah crossover dilakukan dan sebelum anak dilepaskan ke rimba belantara, ada kemungkinan terjadinya mutasi. Kemungkinan terjadinya mutasi ini diukur dengan tingkat mutasi. Nilainya biasanya cukup rendah (Davis, 1991). Tujuan adanya mutasi adalah menghasilkan noise, pada khususnya allele baru ke dalam populasi. Hal ini berguna untuk menghindari nilai minimum, juga membantu dalam eksplorasi wilayah baru pada ruang solusi multi dimensi (Gen M. et.all, 1997). Apabila tingkat mutasi yang terlalu tinggi, dapat menyebabkan gen yang dilahirkan dengan sempurna akan hilang dan oleh karena itu memperendah eksploitasi wilayah nilai fitness tinggi atas solusi. Beberapa sistem tidak menggunakan operator mutasi sama sekali (Heitkoetter, 1993). Sebaliknya, mereka mengandalkan populasi acak yang penuh perbedaan yang dihasilkan atas


inisialisasi untuk menyediakan gen yang cukup dimana rekombinasi itu sendiri akan menghasilkan pencarian yang efektif (Heitkoetter, 1993). Saat gen telah dipilih untuk bermutasi, mutasi tersebut dapat mengambil berbagai macam bentuk (Davis, 1991), hal ini tergantung atas implementasi algoritma genetik.

2.4.8.1. Mutasi Bilangan Real Pada mutasi bilangan real, ukuran langkah mutasi biasanya sangat sulit ditentukan. Ukuran yang kecil biasanya sering mengalami kesuksesan, namun adakalanya ukuran yang lebih besar akan berjalan lebih cepat. Operator mutasi untuk bilangan real dapat ditetapkan sebagai : 1. Variabel yang dimutasi = variabel ± range * delta; (+ atau – memiliki probabilitas yang sama. 2. range = 0.5 * domain variabel; (interval pencarian) 3. delta = Σ ( a i * 2-i); a i = 1 dengan probabilitas 1/m, selain itu a i = 0 dengan m = 20.

2.4.8.2. Mutasi Biner Mutasi biner memiliki prosedur yang mirip dengan mutasi bilangan real. Cara sederhana untuk mendapatkan mutasi biner adalah dengan mengganti satu atau beberapa nilai gen dari kromosom. Langkah-langkah mutasi ini adalah : 1.

Hitung jumlah gen pada populasi (panjang kromosom ini dikalikan dengan ukuran populasi.

2.

Pilih secara random gen yang akan dimutasi

3.

Tentukan kromosom dari gen yang terpilih untuk dimutasi

4.

Ganti nilai gen (n ke m, atau m ke n) dari kromosom yang akan dimutasi tersebut.

Posisi mutasi : ke-2 dan ke-6 Kromosom terpilih

:123456

Hasil Mutasi

:163452


2.4.9. Parameter Genetik Pengoperasian algoritma genetik dibutuhkan 4 parameter (Juniawati, 2003) yaitu: 1. Probabilitas Persilangan (Crossover Probability) Menunjukkan kemungkinan crossover terjadi antara 2 kromosom. Jika tidak terjadi crossover maka keturunannya akan sama persis dengan kromosom orangtua, tetapi tidak berarti generasi yang baru akan sama persis dengan generasi yang lama. Jika probabilitas crossover 100% maka semua keturunannya dihasilkan dari crossover. Crossover dilakukan dengan harapan bahwa kromosom yang baru akan lebih baik. 2. Probabilitas Mutasi (Mutation Probability) Menunjukkan kemungkinan mutasi terjadi pada gen-gen yag menyusun sebuah kromosom. Jika tidak terjadi mutasi maka keturunan yang dihasilkan setelah crossover tidak berubah. Jika terjadi mutasi bagian kromosom akan berubah. Jika probabilitas 100%, semua kromosom dimutasi. Jika probabilitasnya 0%, tidak ada yang mengalami mutasi. 3. Jumlah Individu Menunjukkan jumlah kromosom yang terdapat dalam populasi (dalam satu generasi). Jika hanya sedikit kromosom dalam populasi maka algoritma genetik akan mempunyai sedikit variasi kemungkinan untuk melakukan crossover antara orangtua karena hanya sebagian kecil dari search space yang dipakai. Sebaliknya jika terlalu banyak maka algoritma genetik akan berjalan lambat. 4. Jumlah Populasi Menentukan jumlah populasi atau banyaknya generasi yang dihasilkan, digunakan sebagai batas akhir proses seleksi, persilangan dan mutasi.

2.5. Riset-riset Terkait Beberapa

riset-riset terkait yang telah diteliti oleh peneliti sebelumnya yang

berkaitan dengan penelitian ini adalah sebagai berikut : Aulia Fitrah et.al (2006), dalam risetnya menjelaskan bahwa Persoalan pedagang keliling (TSP) dapat diselesaikan dengan menggunakan algoritma genetika. Walaupun solusi TSP yang dihasilkan oleh algoritma ini belum tentu


merupakan solusi paling optimal (misalnya apabila yang dilalui sangat banyak), namun algoritma genetika akan menghasilkan solusi yang lebih optimal pada setiap generasinya. Hal tersebut terlihat dari nilai fitness tiap generasi. Crossover yang digunakan adalah order crossover dengan probabilty crossover sebesar 50%. Buthainah Fahran Al-Dulaimi, et.al (2008), penyelesaian traveling salesman problem dengan membandingkan antara partially mapped crossover (PMX), Order Crossover (OX), Cycle Crossover (CX) dengan menggunakan mutasi 1%, 30%, 70% dan 100%. Samuel Lukas et.al (2005), penerapan algoritma genetika untuk travelling salesman problem dengan menggunakan metode order crossover dan insertion mutation.


BAB II TINJAUAN PUSTAKA

Recommend Documents