BAB 2 TINJAUAN PUSTAKA

5

BAB 2 TINJAUAN PUSTAKA

2.1.

Algoritma Genetika

Pada tahun 1975, John Holland, di dalam bukunya yang berjudul “Adaption in Natural and Artificial Systems”, mengemukakan komputasi berbasis evolusi. Tujuannya adalah untuk membuat komputer dapat melakukan apa yang terdapat di alam. Sebagai seorang pakar komputer, Holland memfokuskan diri pada manipulasi dari string dalam bentuk binary bit. Holland mengemukakan algoritma tersebut sebagai suatu konsep abstrak dari evolusi alam. Tahapan algoritma genetika yang dikemukakan oleh Holland dapat direpresentasikan sebagai suatu tahapan berurutan sebagai suatu bentuk populasi dari kromosom buatan menjadi sebuah populasi baru (Negnevitsky, 2005). Algoritma genetika adalah suatu algoritma stokastik yang memodelkan proses evolusi dari spesies biologi melalui seleksi alam (Konar, 2005). Secara umum, populasi ini dibangkitkan secara random dan solusi yang adalah dibangkitkan sesudah tahapan konsekutif dari proses crossover dan mutasi. Setiap individu dari populasi memiliki nilai yang diasosiasikan ke dalam suatu nilai fitness, di dalam kaitannya untuk menyelesaikan suatu permasalahan (Rabunal, 2006). Algoritma genetika yang dikemukakan oleh John Holland menggunakan konsep kromosom yang digunakan untuk menyatakan alternatif solusi dari suatu permasalahan. Tiap kromosom terdiri dari deretan bit string yang berupa bit 0 atau 1 yang disebut sebagai gen. Setiap kromosom dapat mengalami pertukaran materi genetis antara kromosom. Sedangkan proses mutasi akan mengganti secara acak nilai gen di beberapa lokasi pada kromosom. Selain itu dikenal pula istilah invertion yang akan membalikkan urutan beberapa gen yang berurutan di dalam kromosom. (Mitchel, 1999).

Universitas Sumatera Utara

6

Hal-hal yang harus dilakukan dalam menggunakan algoritma genetika adalah: 1. Mendefinisikan individu, di mana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat. 2. Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu atau baik-tidaknya solusi yang didapatkan. 3. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak. 4. Menentukan proses seleksi yang akan digunakan. 5. Menentukan proses perkawinan silang (crossover). 6. Mutasi gen yang akan digunakan. Adapun proses dari algroritma genetika secara umum dapat dilihat pada Gambar 2.1.

Gambar 2.1. Siklus Algoritma Genetika (Konar, 2005) Fase awal dari algoritma genetika adalah inisialisasi populasi yang menyatakan alternatif solusi. Elemen dari populasi adalah dideskripsikan dalam bentuk deretan bit string yang berisi bit 0 atau 1 yang disebut sebagai kromosom. Kemudian langkah selanjutnya adalah menghitung nilai fitness berdasarkan gen yang ada pada kromosom dalam tiap populasi. Berdasarkan nilai fitness dari tiap koromosom, maka tahapan selanjutnya adalah tahapan seleksi yang berfungsi untuk memilih kromosom yang terpilih sebagai parent yang akan menjalani crossover.


7

Proses crossover yang berjalan dengan beberapa variasi operator crossover berperan penting dalam membentuk kromosom anak (offspring) yang juga berperan penting untuk menambah keanekaragaman string di dalam suatu populasi. Kromosom selanjutnya akan masuk ke dalam tahap mutasi yang berfungsi untuk memastikan bahwa keanekaragaman (diversity) dari kromosom dalam suatu populasi tetap terjaga, untuk menghindari terjadinya konvergensi prematur yang berujung pada terjadinya solusi yang local optima. 2.2.

Struktur Umum Algoritma Genetika

Algoritma genetik memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetik, membentuk kromosom baru serta seleksi alam seperti yang terjadi pada makhluk hidup. Algoritma genetik secara umum dapat diilustrasikan dalam diagram pada Gambar 2.2.

Gambar 2.2 Gambar Diagram Alir Algoritma (Goldberg, 1989)


8

Goldberg (1989) mengemukakan bahwa algoritma genetik mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat dibedakan dari prosedur pencarian atau optimasi yang lain, yaitu: 1. Algoritma genetika dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri. 2. Algoritma genetika mencari solusi dari sejumlah individu-individu yang merupakan solusi permasalahan, bukan hanya dari satu individu. 3. Algoritma genetika berpatokan pada objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi. 4. Algoritma genetik menggunakan aturan-aturan transisi peluang, bukan aturanaturan deterministik. Variabel dan parameter yang digunakan pada algoritma genetik adalah: (Kuhn et al., 2013) 1. Inisialisasi populasi yang digunakan. Pada bagian ini ditentukan jumlah individu (kromosom) dan gen yang dilibatkan pada setiap generasi. 2. Evaluasi nilai fitness dari setiap individu. 3. Seleksi kromosom yang akan dijadikan kromosom parent untuk dilibatkan di dalam proses crossover berdasarkan nilai fitness. 4. Penentuan nilai PC (Probability Crossover) yang menentukan peluang terjadinya crossover pada setiap individu. 5. Mutation rate yang menentukan sejumlah gen yang dillibatkan dalam proses mutasi. Secara umum struktur dari suatu algoritma genetika dapat didefenisikan dengan langkah-langkah sebagai berikut: (Negnevitsky, 2005) 1. Membangkitkan populasi awal Populasi awal dibangkitkan secara acak sehingga didapatkan solusi awal. Populasi itu sendiri terdiri atas sejumlah kromosom yang merepresentasikan solusi yang diinginkan.


9

2. Menghitung Fitness dari Tiap Generasi. Pada tiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang dinamakan fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Fungsi fitness tersebut dapat dilihat pada Persamaan 2.1.

𝐹𝑖𝑡𝑛𝑒𝑠𝑠 =

! (!!!"#$%& !"#$%&'()

................................................... (2.1)

Dari persamaan 2.1, nilai fitness ditentukan oleh nilai fungsi objektif. Fungsi objektif tersebut menunjukkan hasil penjumlahan jarak pada tiap kromosom. Semakin tinggi nilai fitness akan semakin besar kemungkinan kromosom tersebut terpilih ke generasi berikutnya. Jadi nilai fungsi objektif berbanding terbalik dengan nilai fitness, semakin kecil nilai fungsi objektif semakin besar nilai fitness-nya. 3. Evaluasi Solusi Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dilanjutkan dengan proses perkawinan. Beberapa kriteria berhenti sering digunakan antara lain: berhenti pada generasi tertentu, berhenti setelah beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah, berhenti pada n generasi yang tidak didapatkan nilai fitness yang lebih tinggi. 4. Proses Crossover Menentukan nilai PC (Probability Crossover) dan kemudian menentukan pasangan kromosom yang akan terlibat di dalam proses crossover berdasarkan nilai PC yang dibangkitkan tersebut dengan menggunakan salah satu metode crossover. 5. Proses Mutasi Menentukan nilai mutation rate, dan kemudian berdasarkan nilai bilangan random yang dibangkitkan akan dapat ditentukan gen-gen yang terlibat di dalam proses mutasi tersebut.


10

6. Menjadikan Kromosom Anak hasil dari Proses Crossover dan Mutasi sebagai Populasi Baru. 2.3.

Teknik Encoding

Proses encoding adalah salah satu proses yang sulit di dalam algoritma genetika. Hal ini disebabkan karena proses encoding untuk setiap permasalahan berbeda karena tidak semua teknik encoding cocok untuk tiap permasalahan. Proses encoding menghasilkan string yang kemudian disebut kromosom. String terdiri dari sekumpulan bit yang dikenal sebagai gen. Jadi satu kromosom terdiri dari sejumlah gen (Lukas, 2005). Ada bermacam-macam teknik encoding yang dapat dilakukan dalam algoritma genetika. Beberapa teknik encoding itu antara lain adalah binary encoding, permutation encoding, value encoding, dan tree encoding. Teknik encoding yang digunakan pada Traveling Salesman Problem adalah Permutation Encoding. (Lukas, 2005). Pada Permutation Encoding, kromosom-kromosom adalah kumpulan angka yang mewakili posisi di dalam sebuah rangkaian. Dalam permutatiom encoding, setiap kromosom adalah sebuah string dari nomor-nomor seperti diilustrasikan pada Tabel 2,1, Tabel 2.1. Teknik Permutation Encoding Kromosom (Rute Kota)

A

B

C

D

E

F

G

H

I

Gen (Jarak)

1

5

3

2

6

4

7

9

8

Pada TSP, kromosom menggambarkan rute kota yang dikunjungi salesman, sedangkan jarak antar kota menggambarkan gen. Pada Tabel 2.1, kromosom (rute kota) A-B-C-D-E-F-G-H-I dengan jarak 1, 5, 3, 2, 6, 4, 7, 9, 8. 2.4.

Operator Genetik

Algoritma genetik merupakan proses pencarian yang heuristik dan acak sehingga penekanan pemilihan operator yang digunakan sangat menentukan keberhasilan algoritma genetik dalam menemukan solusi optimum suatu masalah yang diberikan. Hal yang harus diperhatikan adalah menghindari terjadinya konvergensi prematur,


11

yaitu mencapai solusi optimum yang belum waktunya, dalam arti bahwa solusi yang diperoleh adalah hasil local optima. Operator pada algoritma genetika terdiri atas sejumlah parameter kontrol yang terdiri-dari: (Taiwo et al., 2013) 1. Ukuran populasi: mendefinisikan berapa banyak kromosom dan berapa banyak gen di dalam satu kromosom yang terlibat selama proses pencarian. 2. Probabilitas crossover: menspesifikasikan probabilitas crossover di antara dua kromosom. 3. Probabilitas mutasi: menspesifikasikan probabilitas dari dilakukannya mutasi bit-wise. 4. Kriteria terminasi: menspesifikasikan kondisi berakhirnya pencarian solusi pada algoritma genetika. 2.4.1. Proses Seleksi Proses seleksi berhubungan erat dengan nilai fitness yang diperoleh oleh setiap individu. (Reeves, 2003). Proses seleksi dilakukan dengan cara membuat individu yang mempunyai fungsi objektif kecil mempunyai kemungkinan terpilih yang lebih besar atau mempunyai nilai probabilitas yang tinggi (Hermawanto, 2007). Dalam proses seleksi parent, ada banyak metode yang dapat diterapkan. Dua metode umum yang sering digunakan yaitu (Chipperfield. et.al, 2005): 1.

Seleksi Roda Roulette (Roulette Wheel Selection) Roulette wheel selection adalah metode seleksi yang paling sederhana. Pada metode ini semua kromosom (individu) di dalam suatu populasi adalah ditempatkan pada roulette wheel sesuai dengan nilai fitness mereka. Besarnya ukuran tiap segmen di dalam roulette adalah sebanding dengan nilai fitness dari tiap individu. Semakin besar nilai fitness maka semakin besar pula ukuran segmen di dalam roulette wheel, kemudian roulette wheel diputar. Individu yang sesuai dengan segmen pada roulette wheel ketika berhenti yang akan dipilih. (Kumar, 2012). Metode roulette wheel selection dapat dilihat pada Gambar 2.3.


12

Kromosom

Fitness

K1

1

K2

2

K3

0.5

K4

0.5

Jumlah

4

K4 K3

K1

K2

Gambar 2.3 Metode Roulette Wheel Selection (Hassoun, 1995) 2.

Stochastic Universal Sampling Karakteristik metode ini adalah memiliki nilai bias nol dan penyebaran yang minimum. Individu-individu dipetakan dalam suatu segmen garis secara berurutan sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitness-nya. Kemudian diberikan sejumlah pointer sebanyak individu yang ingin diseleksi pada garis tersebut (Pencheva et.al, 2009). Misal N adalah jumlah individu yang akan diseleksi, maka jarak antar pointer adalah 1/N dan posisi pointer pertama diberikan secara acak pada range [1 , 1/N]. Metode stochastic universal sampling dapat dilihat pada Gambar 2.4.

Gambar 2.4 Metode Stochastic Universal Sampling (Pencheva, 2009) 2.4.2. Pindah Silang (Crossover) Operator crossover memainkan peran penting di dalam menghasilkan generasi baru. Operator crossover adalah operator genetika yang mengombinasikan dua kromosom parents untuk menghasilkan kromosom offspring. Tujuan utama dari adanya crossover adalah menghasilkan kromosom baru yang lebih baik daripada kedua parent


13

karena mengambil karakteristik terbaik dari tiap parent. Proses crossover yang terjadi selama proses evolusi sesuai dengan nilai crossover probability yang didefinisikan oleh pengguna (Abuiziah, 2013). Kromosom yang terpilih untuk mengalami crossover ditentukan melalui nilai probability crossover (Pc). Suatu kromosom terpilih untuk mengalami crossover jika nilai random kromosom (Rc) < Pc. Besarnya nilai Pc adalah diantara 0.4 sampai dengan 0.9 (Coley, 1999). Crossover bertujuan menambah keanekaragaman string dalam satu populasi dengan penyilangan antara gen-gen dari induk (Robandi, 2006). Beberapa jenis crossover sebagai berikut: 1)

Crossover Pengkodean Biner Ada beberapa metode crossover dengan pengkodean biner, yaitu sebagai

berikut: a. One Point Crossover Pada one point crossover, sebuah bilangan acak mendefinisikan segmen yang membagi kromosom ke dalam dua bagian. Kromosom offspring dihasilkan melalui kombinasi kromosom yang dihasilkan pada segmen point berdasarkan bilangan acak tersebut. Bagian pertama adalah sebelum segmen point mengambil kromosom parent yang pertama dan bagian kedua setelah bilangan random adalah mengambil kromosom parent yang kedua. (Andrade, 2008). Illustasi dari proses one point crossover dapat dilihat pada Tabel 2.2. Tabel 2.2. One Point Crossover Kromosom Parent 1

11001011

Kromosom Parent 2

11011111

Offspring

11001111

b. Two Point Crossover Two point crossover hampir sama dengan one point crossover. Perbedaannya adalah bahwa pada two point crossover, cut point yang digunakan adalah sebanyak 2, dan dibangkitkan secara acak (Mendes, 2013). Illustrasi dari proes two point crossover dapat dilihat pada Tabel 2.3.


14

Tabel 2.3. Two Point Crossover

2)

Kromosom Parent 1

11001011

Kromosom Parent 2

11011111

Offspring

11011111

Uniform Crossover Pada uniform crossover, sebuah vektor bit acak yang berukuran sama dengan kromosom yang digunakan. Di dalam proses untuk menghasilkan kromosom offspring, akan dipilih bit-bit dalam mask vektor bit acak. Jika yang terpilih adalah bit 0, berarti kromosom offspring diperoleh dari parent 1 dan jika yang terpilih adalah bit 1 berarti kromosom offspring diperoleh dari parent 2 (Andrade, 2008). Illustrasi dari proses uniform crossover dapat dilihat pada Tabel 2.4. Tabel 2.4. Uniform Crossover

3)

Kromosom Parent 1

11001011

Kromosom Parent 2

11011111

Mask

01010101

Offspring

11011111

Arithmetic Crossover

Kromosom offspring diperoleh dengan melakukan operasi aritmatika terhadap parent (induk). Terdapat 3 jenis arithmetic crossover, yaitu sebagai berikut. (Picek et al., 2013). 1.

Single Arithmetic Crossover Pada single arithmetic crossover, pindah silang terjadi pada salah satu gen yang posisinya ditentukan dengan cara membangkitkan suatu bilangan acak. Pada posisi gen yang ditentukan, nilai gen akan ditentukan melalui operasi aritmatika terhadap nilai gen dari parent menurut persamaan 2.2 (Eiben, 2014). Adapun operasi aritmatika pada single arithmetic crossover dapat dilihat pada Persamaan 2.2 dan Tabel 2.5.


15

Child = x ,...., x , α . y + (1 − α ).x ,..., x ........................................(2.2) 1 k k k n Ket: α = Variabel pengali yang nilainya berkisar dari 0-1 Tabel 2.5. Single Arithmetic Crossover Kromosom Parent 1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Kromosom Parent 2

0.3 0.2 0.3 0.2 0.3 0.2 0.3 0.2 0.3

Bilangan Acak

8

α

2.

0.5

Kromosom Offspring 1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.5 0.9


0.3 0.2 0.3 0.2 0.3 0.2 0.3 0.5 0.3

Simple Arithmetic Crossover Pada simple arithmetic crossover, tentukan bilangan random sebagai titik potong antara 0 sampai sepanjang kromosom pada masing-masing parent. Untuk gen pada kromosom offspring untuk batas sebelum titik potong disalin dari gen pada kromosom parent. Untuk gen setelah titik potong, gen yang ada dibentuk dari operasi aritmatika pada gen dari kromosom parent dengan persamaan seperti pada persamaan 2.3 (Picek, 2013). Illustrasi dari proses simple arithmetic crossover dapat dilihat pada Tabel 2.6. Child= x ,..., x , α . y + (1 − α ).x ,...,α . y + (1 − α ).x ....................(2.3) 1 k k +1 k +1 n n Ket: α = Variabel pengali yang nilainya berkisar dari 0-1 Tabel 2.6. Simple Arithmetic Crossover Kromosom Parent 1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Kromosom Parent 2

0.3 0.2 0.3 0.2 0.3 0.2 0.3 0.2 0.3

Bilangan Acak α

6 0.5


0.1 0.2 0.3 0.4 0.5 0.6 0.5 0.5 0.6


0.3 0.2 0.3 0.2 0.3 0.2 0.5 0.5 0.6


16

3.

Whole Arithmetic Crossover Pada whole arithmetic crossover, gen pada kromosom offspring diperoleh dari hasil operasi aritmatika gen pada kromosom parent, di mana proses aritmatika yang dilakukan sesuai dengan persamaan 2.4 (Eiben, 2014). Illustrasi dari proses whole arithmetic crossover dapat dilihat pada Tabel 2.7.

− − Child= α . x + (1 − α ). y ...........................................................................(2.4) Ket: α = Variabel pengali yang nilainya berkisar dari 0-1 Tabel 2.7. Whole Arithmetic Crossover Kromosom Parent 1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Kromosom Parent 2

0.3 0.2 0.3 0.2 0.3 0.2 0.3 0.2 0.3

α

0.5


0.2 0.2 0.3 0.3 0.4 0.4 0.5 0.5 0.6


0.2 0.2 0.3 0.3 0.4 0.4 0.5 0.5 0.6

2.4.3. Mutasi Mutasi adalah proses untuk mengubah gen di dalam sebuah kromosom. Mutasi dilakukan setelah proses crossover dilakukan. Mutasi mengubah offspring baru dengan mengubah 1 menjadi 0 atau 0 menjadi 1. Mutasi dapat terjadi pada setiap posisi di dalam string dengan beberapa probabilitas yang umumnya sangat kecil. Mutasi adalah dimaksudkan untuk mencegah hasil pencarian mengarah pada keadaan local optima di dalam sebuah area pencarian (Shaikh, 2012). Operator mutasi merupakan operasi yang menyangkut satu kromosom tertentu. Beberapa cara operasi mutasi diterapkan dalam algoritma genetik menurut jenis pengkodean terhadap phenotype, antara lain: 1.

Mutasi dalam Pengkodean Biner

Mutasi pada pengkodean biner merupakan operasi yang sangat sederhana. Proses yang dilakukan adalah menginversi nilai pada posisi tertentu yang terpilih secara acak (atau menggunakan skema tertentu) pada kromosom, yang disebut inverse.


17

Tabel 2.8. Contoh Mutasi pada Pengkodean Biner Kromosom sebelum mutasi

10010111

Kromosom setelah mutasi

10010011

2.

Mutasi dalam Pengkodean Permutasi

Proses mutasi yang dilakukan dalam pengkodean biner dengan mengubah langsung pada kromosom tidak dapat dilakukan pada pengkodean permutasi karena konsistensi urutan permutasi haru diperhatikan. Salah satu cara yang dapat dilakukan adalah dengan memilih dua posisi (locus) dari kromosom dan kemudian nilainya saling dipertukarkan. Tabel 2.9. Contoh Mutasi pada Pengkodean Permutasi Kromosom sebelum mutasi

10010111

Kromosom setelah mutasi

10010011

3.

Mutasi dalam Pengkodean Nilai

Mutasi pada pengkodean nilai hampir sama dengan yang dilakukan pada pengkodean biner, tetapi yang dilakukan bukan menginversi nilai . Penerapannya bergantung pada jenis nilai yang digunakan. Sebagai contoh untuk nilai riil, proses mutasi dapat dilakukan seperti yang dilakukan pada pengkodean permutasi, dengan saling mempertukarkan nilai dua gen pada kromosom. 4.

Mutasi dalam Pengkodean Pohon

Mutasi dalam pengkodean pohon dapat dilakukan antara lain dengan cara mengubah operator (+, -, *, /) atau nilai yang terkandung pada suatu verteks pohon yang dipilih. Atau, dapat juga dilakukan dengan memilih dua verteks dari pohon dan saling mempertukarkan operator atau nilainya. 2.5.

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


18

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 yang 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 genetika akan mempunyai sedikit variasi kemungkinan untuk melakukan crossover antara orang tua karena hanya sebagian kecil dari search space yang dipakai. Sebaliknya jika terlalu banyak maka algoritma genetika akan berjalan lambat. 4. Jumlah Populasi Menetukan jumlah populasi atau banyaknya generasi yang dihasilkan, digunakan sebagai batas akhir proses seleksi, persilangan, dan mutasi. 2.6.

Traveling Salesman Problem (TSP)

Permasalahan matematika tentang Traveling Salesman Problem dikemukakan pada tahun 1800 oleh

matematikawan Irlandia William Rowan Hamilton dan

matematikawan Inggris Thomas Penyngton. Permasalahan TSP ini merupakan permasalahan di mana seorang salesman harus mengunjungi semua kota di mana tiap kota hanya dikunjungi sekali, dan dia harus mulai dan kembali ke kota asal. Tujuan yang ingin dicapai pada permasalahan TSP adalah mencari rute terpendek bagi seorang salesman. (Biggs et.al, 1976).


19

2.7.

Penelitian-Penelitian Terkait

2.7.1. Penelitian Terdahulu Lin et al. (2009), menggunakan algoritma genetika untuk mencari jarak terpendek pada sistem ITS (Intelligent Transportation System) di Taiwan dengan menggunakan variasi jumlah gen dan kromosom. Hasil penelitian Lin et.al (2009) memberikan hasil bahwa semakin banyak gen dan kromosom maka solusi optima akan lebih cepat diperoleh. Ada beberapa penelitian lain yang telah dilakukan berkenaan dengan algoritma genetika. Samuel, et al. (2005) membahas bagaimana algoritma genetik menyelesaikan TSP dengan menggunakan metode order crossover sebagai teknik rekombinasi dan metode insertion mutation sebagai teknik mutasi yang digunakan pada algoritma genetik. (Annies,et al, 2002) menunjukkan bahwa algoritma genetika dapat digunakan untuk menyelesaikan masalah optimasi yang kompleks seperti mencari rute paling optimum, menggunakan beberapa metode seleksi yaitu roulette wheel, elitism, dan gabungan antara metode roulette wheel dan elitism. Ada dua jenis crossover yang digunakan yaitu one cut point crossover dan two cut point crossover. Nasution (2012) membahas analisis penyelesaian TSP menggunakan partially mapped crossover dengan menentukan nilai probabilitas crossover 20%, 40%, 60%, 80%, dan 99%. Deep & Mebrahtu (2012) membuat variasi pada partially mapped crossover dengan menentukan letak kromosom dalam posisi acak. Kemudian, Al kasasbeh, et al. (2012) menambahkan sebuah procedure baru pada algoritma genetika untuk menyelesaikan TSP yaitu dengan metode shared neighbour. Penelitian terbaru yang dilakukan oleh Picek et.al (2013) yang membandingkan beberapa metode crossover di dalam menyelesaikan 24 permasalahan dengan menggunakan 16 metode crossover, yang menarik dari hasil penelitian adalah bahwa metode whole arithmetic crossover memiliki performance yang lebih baik daripada metode simple arithmetic crossover dan simple arithmetic crossover memiliki performance yang lebih baik daripada single arithmetic crossover. Penelitian yang dilakukan oleh Picek et al. (2013) cukup menarik, karena secara luas membandingkan beberapa metode crossover yang ada sehingga memberikan sumbangsih yang cukup berarti di dalam perkembangan konsep algoritma genetika. Namun, yang belum dibahas di dalam penelitian ini adalah apakah terdapat keterkaitan langsung antara jumlah gen yang mengalami crossover di dalam sebuah kromosom dapat berpengaruh cukup signifikan terhadap performance


20

crossover. Hal ini mengingat terdapatnya peningkatan performance bila dikaitkan dengan jumlah gen yang mengalami crossover. Mengingat performance yang merupakan hasil penelitian adalah whole arithmetic crossover memiliki performance yang lebih baik dari simple arithmetic crossover dan Simple arithmetic crossover memiliki performance yang lebih baik daripada single arithmetic crossover. 2.7.2. Perbedaan Penelitian Perbedaan penelitian yang pernah dilakukan dengan penelitian yang dilakukan oleh peneliti dapat dilihat pada Tabel 2.10. Tabel 2.10. Perbedaan Penelitian No 1.

Nama Peneliti Lin Chu Hsing, Jui Ling Yu, Jung Chun Liu, Wei Shen Lai, dan Chia Han Ho (2009)

Persamaan Sama-sama menerapkan algoritma genetika untuk mencari rute terpendek pada ITS (Intelligent Transportation System) di Taiwan

2.

Lukas Samuel, Toni Anwar, dan Willi Yuliani (2005)

Sama-sama menerapkan algoritma genetika untuk menyelesaikan permasalahan Traveling Salesman Problem (TSP)

3.

Annies Hannawati, Thing, dan Eleazar (2002)

Menerapkan algoritma genetika untuk menyelesaikan masalah optimasi yang kompleks seperti mencari rute paling optimum

4.

K. Nasution (2012)

Sama-sama menerapkan algoritma genetika untuk menyelesaikan permasalahan Traveling Salesman Problem

Perbedaan Pembahasan dititikberatkan pada pengaruh jumlah gen dan kromosom di dalam mendapatkan solusi optimal. Penelitian ini tidak membahas mengenai pengaruh gen yang mengalami crossover di dalam mendapatkan solusi optimal. Pembahasan penelitian mengenai penggunaan metode order crossover digabungkan dengan teknik insertion mutation untuk menyelesaikan permasalahan TSP. Penelitian ini hanya membahas penyelesaian permasalahan TSP dan tidak membahas mengenai performance dari algoritma genetika. Penelitian ini menggunakan beberapa metode seleksi yaitu roulette wheel, elitism, dan gabungan antara metode roulette wheel dan elitism, selain itu juga menggunakan dua jenis crossover yaitu one cut point crossover dan two cut point crossover. Namun, penelitian tidak membahas mengenai performance Atas metode arithmetic crissover dalam kaitannya dengan jumlah gen yang mengalami crossover. Penelitian ini difokuskan pada pembahasan mengenai pengaruh dari nilai probabilitas crossover di dalam partially mapped crossover dan tidak membahas mengenai performance atas arithmetic crossover dalam kaitannya


21

No

Nama Peneliti

Persamaan

5.

Kusum Deep dan Hadush Mebrahtu (2012)

Penelitian ini sama seperti penelitian yang dilakukan oleh peneliti membahas mengenai penerapan algoritma genetika di dalam menyelesaikan permasalahan Traveling Salesman Problem

6.

Stjepan Picek, Domagoj Jakobovic dan Marin Gloub (2013)

Penelitian ini membahas mengenai perbandingan performance atas metode arithmetic crossover dan beberapa metode crossover yang lain

7.

Sri Melvani Hardi (2014)

Penelitian ini membahas mengenai pengaruh crossover di dalam performance algoritma genetika di dalam menyelesaikan permasalahan Traveling Salesman Problem (TSP)

Perbedaan dengan jumlah gen yang mengalami crossover. Penelitian ini membahas mengenai pembuatan variasi pada partially mapped crossover dengan menentukan letak kromosom dalam posisi acak dan tidak membahas mengenai kaitan antara jumlah gen yang mengalami crossover dengan performance atas metode arithmetic crossover Penelitian ini membandingkan beberapa metode crossover di dalam menyelesaikan 24 permasalahan dengan menggunakan 16 metode crossover, tetapi penelitian ini tidak membahas mengenai kaitan antara jumlah gen yang mengalami crossover terhadap performance dari crossover khususnya arithmetic crossover Penelitian ini pengaruh dari variasi terhadap performance dari algoritma genetika dan tidak membahas mengenai kaitan antara jumlah gen yang mengalami crossover dengan performance dari algoritma genetika

2.7.3. Kontribusi yang Diberikan Melalui penelitian ini diharapkan dapat diperoleh hasil analisis keterkaitan jumlah gen yang mengalami crossover dengan performance algoritma genetika dengan setiap metode arithmetic crossover yang ada.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents