BAB II
LANDASAN TEORI
2.1. Kerangka Pikir
Algoritma merupakan tahapan-tahapan untuk mencapai hasil. Jadi Algoritma tidak selalu berhubungan dengan Ilmu Komputer. Misalkan cara membuat cake. Pertama kita harus mempersiapkan adonan cake. Kemudian apabila adonan tersebut telah jadi, panaskan oven. Kemudian taruh adonan cake tersebut kedalam Loyang yang telah dioleskan mentega dan ditaburi sedikit tepung. Apabila adonan tersebut telah dimasukkan kedalam Loyang,masukkan Loyang yang berisi adonan cake tersebut kedalam oven yang telah di tentukan suhunya tadi. Tunggulah kira-kira setengah jam. Maka adonan cake tersebut akan menjadi kue cake.
Di sini penulis bukan membahas tentang kue cake, tapi penulis hanya memberi gambaran logis tentang pengertian Algoritma yang sebenarnya. Yang dapat kita ambil dari contoh di atas adalah untuk menghasilkan sesuatu,maka diperlukan proses. Proses tersebut terdiri dari tahapan-tahapan yang logis. Jadi menurut pemikiran saya,secara umum Inti dari algoritma adalah tahapan-tahapan logis yang harus dipenuhi untuk mencapai suatu hasil.
Sekarang penulis akan membahas Algoritma menurut pengertian ilmu Komputer. Algoritma dalam ilmu Komputer adalah urut-urutan yang logis dan tepat untuk memecahkan permasalahan yang menggunakan Komputer dengan bahasa pemrograman yang telah ditentukan seperti bahasa pascal, Visual Basic, C, atau yang lainnya. Untuk membuat sebuah program, seseorang harus memiliki daya piker yang bagus. Dan untuk menghasilkan sebuah program yang berbeda dengan yang lainnya, maka orang tersebut harus memiliki kreativitas.
Sedangkan menurut penulis, algoritma adalah : Cara yang dapat ditempuh oleh komputer dalam mencapai suatu tujuan, terdiri atas langkah-langkah yang terdefinisi dengan baik, menerima input, melakukan proses, dan menghasilkan output. Meskipun tidak selalu, biasanya sebuah algoritma memiliki sifat bisa dihitung (computable) atau bisa diukur (measurable).
Sebuah algoritma dikatan benar (correct), jika algoritma tersebut baerhasil mengeluarkan output yang benar untuk semua kemungkinan input. Jika sebuah algoritma dikatakan 99% benar, algoritma tersebut tetap salah (incorrect). Agar algoritma tersebut dikatan benar, algoritma tersebut harus benar 100%.
Contoh algoritma sederhana dalam dunia nyata...
Jika seseorang ingin mengirim surat kepada temannya di tempat lain, langkah yang harus dilakukan adalah :
1. Menulis surat.
2. Surat dimasukkan ke dalam amplop tertutup.
3. Amplop ditempeli perangko secukupnya.
4. Pergi ke Kantor Pos terdekat untuk mengirimkannya.
Tapi, algoritma tidaklah semudah dan sesederhana itu. Dalam membuat algoritma yang baik, kita harus menulis semua kemungkinan yang akan terjadi, walaupun kejadian itu belum tentu terjadi. Misalnya contoh diatas, ketika orang tersebut sedang menulis surat, tinta pulpennya habis dan dia harus mencari atau membeli pulpen lain. Ketika dia sedang mengantarkan surat tersebut ke kantor pos, kantor pos itu sudah tutup, dan kemungkinan-kemungkinan lainnya.
2.2. Kerangka Teori
2.2.1. Pengertian Algoritma
Menurut Muhammad ibn Mūsā al-Khwārizmī algoritma adalah : "Suatu metode khusus untuk menyelesaikan suatu persoalan". Menurut Goodman Hedet Niemi algoritma adalah : "Urut-urutan terbatas dari operasi terdefinisi dengan baik, yang masing-masing membutuhkan memori dan waktu yang terbatas untuk menyelesaikan suatu masalah".
Kata Algoritma berasal dari bahasa arab yaitu Algorism yang berarti proses menghitung dengan angka arab. Sedangkan Algorist adalah orang yang menghitung dengan menggunakan angka arab. Sebenarnya, Algoritma itu sendiri berasal dari nama seorang ahli matematika dari Uzbekistan yaitu Abu Abdullah Muhammad Ibn Musa al-Khwarizmi yang dibaca oleh orang barat menjadi Algorism.
Pengertian Algoritma
Algoritma merupakan prosedur komputasi yang terdefinisi dengan baik ( dari initial state ke terminal state ) yang menerima himpunan ( input ) untuk menyelesaikan suatu masalah yang menghasilkan himpunan output. Suatu algoritma dikatakan benar apabila himpunan input menghasilkan output yang benar. Langkah logis berarti algoritma tidak harus mengikuti urutan tertentu, dan tidak melompati langkah yang lain
Contoh algoritma pengurutan angka (sorting) memiliki:
- Input : Himpunan n bilangan (a1, a2, a3, …, an) seperti: 5, 3, 4, 2, 1
- Output : Himpunan n bilangan terurut (a’1, a’2, a’3, …, a’n) seperti: 1, 2, 3, 4, 5
Contoh permasalahan yang diselesaikan algoritma:
Human Genome Project mengidentifikasi 100,000 gen DNA manusia yang menentukan 3 miliar pasang kimia pembentuk DNA.
Data tersebut disimpan dalam database dan memerlukan aplikasi analisis data. Algoritma melakukan penyimpanan dan analisis yang cepat.
Internet untuk pencarian informasi melalui mesin pencarian (search engines) : Algoritma membantu pencarian informasi yang cepat dan cerdas.
Peta perjalanan terdapat tempat tujuan yang ingin dicapai dari tempat asal : Algoritma memberikan solusi pencarian jalan terpendek dan tercepat untuk menampilkan rute dari tempat asal ke tempat tujuan tersebut.
Kriteria dari suatu algoritma :
Input: algoritma dapat memiliki nol atau lebih inputan dari luar.Instruksi : sintaks (cara pengkodean) sesuai bahasa pemrograman yang dipakai dan mengandung komponen input, output, proses, seleksi, dan perulangan yang menugaskan komputer untuk mengeksekusi suatu perintah tertentu.
· Output: algoritma harus memiliki minimal satu buah output/keluaran.
· Definiteness (pasti): algoritma memiliki instruksi-instruksi yang jelas dan tidak ambigu.
· Finiteness (ada batas): algoritma harus memiliki titik berhenti (stopping role).
· Effectiveness (tepat dan efisien): algoritma sebisa mungkin harus dapat dilaksanakan dan efektif
Contoh instruksi yang tidak efektif adalah: A=A+0 atau A=A*1
Program adalah Kumpulan instruksi-instruksi (source code) yang dibuat oleh programmer (pembuat program) untuk menyelesaikan suatu masalah pada komputer
· Algoritma menempati posisi di bagian implementasi
· Pemrogram melakukan proses coding (pembuatan program).
· Bahasa pemrograman : Alat untuk membuat program.
· Perbedaan: cara memberikan instruksi.
· Persamaan: output/pemecahan masalah yang dicapai.
· Contoh bahasa pemrograman:
· COBOL (Common Business Oriented Language)
· FORTRAN (FORmula TRANslation)
· BASIC (Beginner All-purpose Symbolic Instructional Code)
· Pascal (dinamakan untuk Blaise Pascal)
· Ada (dinamakan untuk Ada Lovelace)
· C (pengembang bahasa B)
· Visual Basic (mirip BASIC, buatan Microsoft)
· Delphi (mirip Pascal, buatan Borland)
· C++ (bahasa berorientasi object, berbasiskan C)
· C# (mirip Java, buatan Microsoft)
· Java
Pengekspresian algoritma :
· Alur pengekspresian algoritma dituangkan secara tertulis
· Alur pengekspresian: alur pemikiran, sehingga algoritma setiap orang berbeda
· Tertulis: algoritma berupa tulisan/kalimat, gambar, atau tabel
· Algoritma dapat menggunakan beberapa metode :
· Tulisan/kalimat: pseudocode
Pseudocode :
Berasal dari kata pseudo dan code, berarti kode yang tidak sebenarnya Umumnya dimulai dengan kata “BEGIN” dan diakhiri “END”
IF-THEN dan ELSE digunakan untuk operasi percabangan/seleksi
WHILE dan DO-WHILE digunakan untuk operasi perulangan
Deskripsi informal untuk algoritma pada pemrograman komputer
Tujuan: memudahkan manusia untuk membaca bahasa pemrograman konvensional
Tidak ada standar untuk pseudocode karena bukan program yang dapat dieksekusi
Umumnya dimulai dengan kata “BEGIN” dan diakhiri “END”
IF-THEN dan ELSE digunakan untuk operasi percabangan/seleksi
WHILE dan DO-WHILE digunakan untuk operasi perulangan
Contoh pseudocode untuk melakukan panggilan melalui telepon:
BEGIN
Hold Up The Phhone
WHILE not dial
Press dial button
If Connected THEN
WHILE Not Finished
Talking
Hold Down The Phone
END
Contoh pseudocode untuk mengecek apakah bilangan genap atau ganjil:
BEGIN
Number = Input Number
Result = Number % 2
IF Result = 0
THEN Print “The Number Is Even Number”
ELSE
THEN Print “The Number Is Odd Number”
Flowchart ( Diagram Alur ) adalah Representasi skematik dari suatu algoritma atau proses.
Skematik: penggunaan diagram untuk merepresentasikan elemen suatu sistem menggunakan simbol-simbol abstrak yang bukan sesungguhnya.
Contoh: bangunan pada peta disimbolkan dengan titik, gunung disimbolkan dengan segitiga
Algoritma berasal dari nama seorang ahli astronomi dan matematik Persia (Iran), Abu Ja’far Mohammed Ibn Musa al-Khowarizmi, dalam sebuah tulisan Arab berjudul “al jabr w’al-muqabala” pada tahun 825 M.
Tulisan tersebut diterjemahkan dalam bahasa latin pada abad ke-12 berjudul “Algoritmi de numero Indorum atau Algoritmus on The Numbers of The Indians
Kata “Algoritmi” merujuk pada nama penulisnya, tetapi masyarakat menyalahartikan sebagai “calculation method”.
Algoritma
Diagram Alur sering digunakan untuk menggambarkan sebuah algoritma.
Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.
Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
Sejarah istilah "algoritma"Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.
Jenis-jenis Algoritma
Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda.
Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.
Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap;
dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.
Algoritma adalah suatu prosedur yang tepat untuk memecahkan masalah dengan menggunakan bantuan komputer serta menggunakan suatu bahasa pemrogaman tertentu seperti bahasa Pascal, Visual Basic, Java, dan masih banyak lagi bahasa yang lain.Pranata (2002:8) dalam kehidupan sehari-hari, sebenarnya kita juga menggunakan algoritma untuk melaksanakan sesuatu. Sebagai contoh, ketika kita menulis surat, maka kita perlu melakukan beberapa langkah sebagai berikut:
1. Mempersiapkan kertas dan amplop.
2. Mempersiapkan alat tulis, seperti pena atau pensil.
3. Mulai menulis.
4. Memasukkan kertas ke dalam amplop.
5. Pergi ke kantor pos untuk mengeposkan surat tersebut.
Dengan algoritma, kita dapat mengatasi masalah dari yang sederhana sampai yang kompleks sekalipun. Namun, seorang user harus mampu membuat suatu program dengan menggunakan bahasa yang difahami oleh komputer. Sebelum disajikan dalam bentuk bahasa pemrogaman, sebaiknya kita membuat diagram alir (Flow Chart) dan Pseudocode. Hal ini dimaksudkan agar dapat mempermudah kerja atau mempermudah dalam membuat program. Selain itu, algoritma dapat mengatasi masalah logika dan masalah matematika dengan cara berurutan, tetapi kadang-kadang algoritma tidak selalu berurutan, hal ini dikenal dengan proses percabangan.
Pada dasarnya, komputer adalah mesin digital, artinya komputer hanya bisa mengenal kondisi ada arus listrik (biasanya dilambangkan dengan 1) dan tidak ada arus listrik (biasanya dilambangkan dengan 0). Dengan kata lain, kita harus menggunakan sandi 0 dan 1 untuk melakukan pemrogaman komputer. Bahasa pemrogaman yang menggunakan sandi 0 dan 1 ini disebut bahasa mesin. Karena bahasa mesin sangat susah, maka muncul ide untuk melambangkan untaian sandi 0 dan 1 dengan singkatan kata yang lebih mudah difahami manusia biasa disebut dengan mnemonic code. Bahasa pemrogaman yang menggunakan singkatan kata ini disebut bahasa assembly.
Program algoritma harus komplit, nyata, dan jelas. Meskipun tugas algoritma tidak menghasilkan solusi, tetapi proses harus berakhir hal ini disebut dengan semi algorithm (prosedur akan berjalan terus atau biasa disebut dengan perulangan). Intinya kita tidak boleh menambah masalah, akan tetapi kita harus mampu menyelesaikan masalah untuk mendapat hasil yang tepat. Adapun contoh algoritma seperti dalam menghitung luas lingkaran dari masukan berupa jari-jari lingkaran. Rumus lingkaran adalah L=?*R*R
Berikut ini adalah contoh algoritma untuk menghitung luas lingkaran:
1. Masukkan R
2. Pi ? 3,14
3. L ? Pi*R*R
4. Tulis L
Perhatikan tanda ? pada baris kedua dan ketiga. Tanda ini berarti nilai di sebelah kanan diberikan pada operan di sebelah kiri. Sebagai contoh, untuk baris kedua, nilai 3,14 diberikan pada variabel Pi. Berikutnya, nilai Pi*R*R diberikan pada variable L. Baris terakhir menuliskan luas lingkaran tersebut.
Seperti yang dikemukakan di atas, bahwa algoritma ada yang tidak berurutan dan biasa di sebut dengan pengulangan. Adapun contohnya yaitu dalam penghitungan rata-rata dari sekumpulan data yang dimasukkan pengguna.
Berikut ini adalah algoritma untuk menghitung rata-rata data yang dimasukkan pengguna:
1. Masukkan N
2. i?1
3. j?0
4. Selama (i<=N) kerjakan baris 4 sampai dengan 7
5. Masukkan dt
6. i?i+1
7. j?j+dt
8. Rata?j/N
9. Tulis rata
Baris pertama meminta pengguna memasukkan N, yaitu jumlah data.
Pada baris kedua, variabel I, yang berguna sebagai pencacah banyaknya data yang telah dimasukkan pegguna, bernilai 1.
Pada baris ketiga, variabel j, yang digunakan untuk menyimpan hasil penjumlahan data, diberi nilai 0.
Baris keempat memberikan perintah untuk mengulangi baris keempat sampai dengan baris ketujuh selama I kurang dari sama dengan N. Dengan kata lain, setelahi lebih besar dari N, baris kedelapan yang dijalankan.
Baris kelima meminta masukkan data yang ke-i.
Baris keenam menambah variabel I dengan 1. Perhatikan arti dari perintah i?i+1 adalah nilai i ditambah dengan 1 kemudian hasilnya disimpan pada variabel i kembali.
Baris ketujuh menambah variabel j dengan data yang dimasukkan pengguna. Sebagaimana dijelaskan di atas, variabel j digunakan untuk menyimpan hasil penjumlahan semua data, jadi untuk setiap masukan data, nilai variabel j harus ditambah dengan dt.
Baris kedelapan menghitung rata-rata dengan cara membagi hasil penjumlahan dengan banyaknya data.
Baris terakhir menuliskan rata-rata tersebut.
Tetapi banyak pemrogram yang sudah berpengalaman tidak pernah menuliskan algoritma di atas kertas lagi.. Artinya dia menuliskan algoritma itu di daalam kepalanya.
PENGERTIAN ALGORITMA
ALGORITMA adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis. Pertama kali dikemukakan oleh penulis buku arab abu jafar muhammad ibnu musa Al-khuwarizmi. Algoritma merupakan jantung dari informatika/ilmu komputer di mana harus dinyatakan dalam bentuk yang dimegerti oleh pemeroses agar dapat dilaksanakan oleh komputer. Algoritma harus itulis dalam notasi bahasa pemerograman.
Pemerograman adalah implementasi teknis algoritma yang itulis dalam bahasa pemrograman tertentu.
Belajar memprogram ≠ belajar bahasa pemrograman.
Belajar memprogram
· Belajar tentang metodelogi pemecahan masalah
· Menuangkan dalam suatu notasi tertentu yang mudah dibaca dan dipahami
Belajar bahasa pemrograman
· Belajar memakai suatu bahasa aturan-aturan tata bahasanya dan instruksi-instruksinya, tata cara pengoperasian compilernya, dan memanfaatkan instruksi-instruksi tersebut untuk membuat program
Produk yang dihasilkan pemrograman
· Program dengan rancangan yang baik
· Berfungsi dengan benar
· Sanggup melayani segala kemungkinan masukan
· Disertai dokumentasi
2.2.2. Algoritma Tabu Search
diperkenalkan oleh Fred Glover pada tahun 1986. Pada tahun 1988, Committee on the Next Decade of Operations Research (CONDOR) menetapkan TS, bersama dengan simulated annealing dan genetic algorithm, sebagai metode yang sangat menjanjikan untuk aplikasi praktis. Saat ini TS telah menjadi salah satu teknik optimasi yang digunakan secara luas di berbagai bidang dan metode ini telah mengalami banyak perkembangan melalui berbagai penelitian. TAbu Search adalah sebuah meta-heuristik yang menuntun prosedur local search untuk melakukan eksplorasi di daerah solusi di luar titik optimum lokal. Metode ini menerapkan konsep adaptive memory dan responsive exploration, untuk dapat melakukan proses pencarian secara efektif dan efisien dengan cara memanfaatkan informasi tentang ciri solusi yang baik pada saat menjelajahi daerah pencarian yang baru. Kenyataan ini memberi harapan bahwa algoritma TS dapat menghasilkan jadwal job shop dengan kualitas yang baik dalam waktu komputasi yang relative kecil dibandingkan metode enumerative.
Tabu Search adalah sebuah metode optimasi yang berbasis pada local search. Proses pencarian bergerak dari satu solusi ke solusi berikutnya, dengan cara memilih solusi terbaik dari neighborhood solusi sekarang (current) yang tidak tergolong solusi terlarang (tabu). Ide dasar dari algoritma tabu search adalah mencegah proses pencarian dari local search agar tidak melakukan pencarian ulang pada ruang solusi yang sudah pernah ditelusuri, dengan memanfaatkan suatu struktur memori yang mencatat sebagian jejak proses pencarian yang telah dilakukan.
Struktur memori fundamental dalam tabu search dinamakan tabu list. Tabu list menyimpan atribut dari sebagian move (transisi solusi) yang telah diterapkan pada iterasi-iterasi sebelumnya. Tabu search menggunakan tabu-list untuk menolak solusi-solusi yang memenuhi atribut tertentu guna mencegah proses pencarian mengalami cycling pada daerah solusi yang sama, dan menuntun proses pencarian menelusuri daerah solusi yang belum dikunjungi. Tanpa menggunakan strategi ini, local search yang sudah menemukan solusi optimum lokal dapat terjebak pada daerah solusi optimum lokal tersebut pada iterasi-iterasi berikutnya.
Perekaman solusi secara lengkap dalam sebuah forbidden list dan pengecekan apakah sebuah kandidat solusi tercatat dalam list tersebut merupakan cara yang mahal, baik dari sisi kebutuhan memori maupun kebutuhan waktu komputasi.
Jadi tabu list hanya menyimpan langkah transisi (move) yang merupakan lawan atau kebalikan dari langkah yang telah digunakan dalam iterasi sebelumnya untuk bergerak dari satu solusi ke solusi berikutnya. Dengan kata lain tabu list berisi langkah-langkah yang membalikkan solusi yang baru ke solusi yang lama.\
Pada tiap iterasi, dipilih solusi baru yang merupakan solusi terbaik dalam neighborhood dan tidak tergolong sebagai tabu. Kualitas solusi baru ini tidak harus lebih baik dari kualitas solusi sekarang. Apabila solusi baru ini memiliki nilai fungsi objektif lebih baik dibandingkan solusi terbaik yang telah dicapai sebelumnya, maka solusi baru ini dicatat sebagai solusi terbaik yang baru. Sebagai tambahan dari tabu-list, dikenal adanya kriteria aspirasi, yaitu suatu penanganan khusus terhadap move yang dinilai dapat menghasilkan solusi yang baik namun move tersebut berstatu tabu. Dalam hal ini, jika move tersebut memenuhi kriteria aspirasi yang telah ditetapkan sebelumnya, maka move tersebut dapat digunakan untuk membentuk solusi berikutnya (status tabunya dibatalkan). Berikut ini diberikan kerangka umum algoritma tabu search dalam notasi bahasa Pascal.
begin
{Buat solusi awal s yang feasibel dengan
menggunakan
suatu metode heuristik tertentu atau secara
acak}
best := cost(s);
s* := s; {s* adalah solusi terbaik yang
diperoleh}
tabu_list := null;
repeat
Candidate(s) := (s’ ∈ N(s): merupakan move dari s ke s’ yang tidak tergolong elemen dari tabu- list atau memenuhi kriteria aspirasi}; (pilih ∈ s Candidate(s): s adalah solusi yang memiliki nilai cost minimum ); (simpan move yang berlawanan ke dalam tabu- list, yait yang mengubah s ke s );
s := s ;
if (cost(s) <>
s* := s;
best := cost(s);
until (stopping-criteria = TRUE);
return(s*);
end;
Tabu Search kini dikenal sebagai salah satu teknik untuk optimalisasi yang cukup efektif setelah dilakukan beberapa percobaan komputasional. Algoritma tabu search mampu bersaing dengan teknik-teknik terkenal lainnya disebabkan fleksibilitasnya yang bisa menyaingi prosedur klasik lainnya. Karena sudah banyak terbukti bahwa tabu search adalah algoritma yang cukup efektif maka saat ini banyak sekali permasalahan dari berbagai bidang yang bisa menggunakan implementasi algoritma tabu search untuk mendapatkan solusi optimal. Salah satu contoh permasalahan yang juga dapat diselesaikan dengan algoritma tabu search adalah permasalahan job shop scheduling dimana permasalahan ini bertujuan untuk meminimasi waktu untuk menyelesaikan sederetan operasi dari job yang ada.
Metode pencarian tabu berprinsip pada penggunaan memori sebagai elemen esensial dalam pencariannya, karena pencarian tabu tidak hanya menyimpan nilai sebuah solusi terbaik seperti kebanyakan metode pencarian, namun juga menyimpan informasi selama pencarian melalui solusi terakhir yang dikunjungi. Sebuah informasi akan digunakan sebagai petunjuk untuk bergerak dari i ke solusi selanjutnya dalam N(i). Penggunaan memori sebagai pembatas dalam pemilihan beberapa subset dari N(i) dengan mencegah pergerakan ke beberapa solusi tetangga.
Lebih tepatnya, kita akan menyadari bahwa struktur N(i) sebagai solusi i akan berupa variabel dari satu iterasi ke iterasi lainnya. Oleh karena itu metode pencarian tabu dapat disebut sebagai kelas dari prosedur-prosedur yang disebut dynamic neighborhood search techniques.
Secara formal,kita dapat menganggap masalah optimalisasi dalam cara berikut: Diberikan sebuah himpunan solusi S dan sebuah fungsi f : S, temukan solusi i* dalam S sehingga f(i*) dapat diterima dengan beberapa kriteria. Secara umum kriteria untuk dapat diterima sebagai solusi i* harus memenuhi f(i*)=f(i) untuk setiap i dalam S. Dalam situasi metode pencarian tabu akan menjadi sebuah algoritma minimimasi secara pasti yang menyediakan proses eksplorasi yang menjamin setelah sejumlah langkah-langkah terhingga i* dapat dicapai. Walaupun tidak ada jaminan bahwa i* akan diperoleh, metode pencarian tabu dapat secara sederhana dipandang sebagai prosedur heuristic umum secara ekstrem. Karena metode pencarian tabu akan mencakup beberapa teknik heuristic dalam aturan-aturan operasi di dalamnya, maka akan lebih pantas untuk menggolongkan motode pencarian tabu sebagai metaheuristic. Perannya akan sering dijadikan sebagai petunjuk dan sebagai orientasi prosedur pencarian lainnya yang lebih lokal.
Untuk mendalami lagi prinsip kerja metode pencarian tabu, kita dapat memformulakan metoda menurun klasik (classical descent method) dalam beberapa langkah, yaitu:
1. Memilih sebuah solusi awal i dalam S
2. Membangkitkan subset V* sebagai solusi dalam N(i)
3. Mencari j ‘terbaik’ dalam V* dan menetapkan i=j
4. Jika f(j)=f(i) maka berhenti, namun jika tidak kembali ke langkah ke-2 Dalam metode menurun secara umum akan dapat langsung ditetapkan bahwa V* = N(i). Tetapi hal ini seringkali membutuhkan waktu yang lama. Untuk itulah cara pemilihan V* yang tepat seringkali dijadikan sebagai peningkatan yang penting dalam metode pencarian. Pada kasus yang berlawanan, akan ditetapkan |V*|=1. Hal ini akan menurunkan fase pemilihan j ‘terbaik’. Solusi j akan diterima jika f(j)=f(i), sebaliknya hal ini akan diterima dengan kemungkinan tertentu yang bergantung pada nilai-nilai f pada i dan j serta pada sebuah parameter yang disebut temperatur.
Tidak ada temperatur dalam metode pencarian tabu, namun pemilihan V* akan menjadi hal yang penting guna mendefinisikannya dalam setiap langkah di mana akan terjadi penggunaan memori secara sistematis untuk memanfaatkan informasi yang ada di luar fungsi f dan lingkungan N(i).
Sebagai pengecualian pada kasus-kasus istimewa, penggunaan prosedur menurun (descent procedure) secara umum lebih rumit karena kita akan terperangkap pada sebuah minimum lokal yang mungkin masih jauh dari minimum global.
Maka untuk proses iterasi dalam eksplorasi apapun sebaiknya dalam beberapa hal juga menerima langkah-langkah yang tidak akan memberikan perkembangan dari i ke j dalam V* (misal f(j)>f(i)). Metode pencarian tabu secara berbeda memilih j ‘terbaik’ dalam V*. Selama pergerakan yang tidak member perkembangan itu mungkin, resiko pengunjungan kembali sebuah solusi atau lebih umumnya disebut sebagai siklus mungkin untuk terjadi. Dalam hal inilah penggunaan memori sangat diperlukan untuk mencegah terjadinya pergerakan ke solusi yang telah dikunjungi. Jika memori seperti itu diperkenalkan, maka kita dapat menganggap struktur N(i) tergantung pada pengelilingan yang merupakan pengulangan k. Jadi kita dapat merujuk ke N(i,k) daripada N(i). Dengan perujukan ini kita dapat mencoba untuk melakukan peningkatan. Algoritma menurun dalam beberapa hal untuk lebih mendekatkan metode ini ke prosedur dalam metode pencarian tabu secara umum. Hal ini dapat didefinisikan dalam beberapa langkah (catatan i* adalah solusi ‘terbaik’ yang ditemukan dan k adalah penghitung dalam pengulangan) :
1. Memilih solusi awal I dalam S. Tetapkan i*=I dan k=0.
2. Tetapkan nilai k=k+1 dan membagkitkan subset V* sebagai solusi dalam N(i,k)
3. Pilih j ‘terbaik’ dalam V* dan tetapkan i=j.
4. Jika f(i) <>maka tetapkan i*=i.
5. Jika kondisi berhenti ditemukan, maka proses dihentikan, sedangkan jika belum kembali ke langkah 2.
Amati bahwa langkah-langkah pada metode penurunan klasik termasuk dalam formula ini (kondisi berhenti secara sederhana jika f(i)=f(i*) dan i* akan selalu menjadi solusi akhir). Selain itu kita juga dapat mempertimbangkan penggunaan f yang telah dimodifikasi daripada f yang dalam beberapa keadaan di deskripsikan kemudian.
Dalam metode pencarian tabu, kondisi berhenti dapat berupa:
• N(i,k+1) = tidak terdefinisi
• k lebih besar daripada bilangan maksimum pada pengulangan
• banyaknya pengulangan selama peningkatan terakhir i* lebih besar dari bilangan tertentu.
• Pembuktian dapat diberikan daripada solusi optimum yang telah didapatkan. Selama aturan-aturan berhenti ini memungkinkan untuk memiliki beberapa pengaruh dalam prosedur pencarian dan pada hasil-hasilnya, penting untuk menyadari bahwa pendefinisian N(i,k) dalam tiap pengulangan k dan pemilihan V* adalah hal yang krusial.
Definisi dari N(i,k) menyatakan secara tidak langsung bahwa beberapa solusi yang telah dikunjungi dihapus dari N(i), mereka dianggap sebagai solusi-solusi tabu yang harus dihindari dalam pengulangan selanjutnya. Sebagai contoh, pemeliharaan pada pengulangan k sebuah list T(list tabu) pada solusi yang telah dikunjungi terakhir |T| akan mencegah terjadinya siklus pada ukuran paling banyak sebesar |T|. Pada kasus ini, kita bisa mengambil N(i,k)=N(i)-T. Namun list T kemungkinan tidak dapat digunakan secara praktis. Oleh karena itu, kita akan mendeskripsikan proses eksplorasi pada S dalam masa pergerakan dari satu solusi ke solusi lainnya. Untuk setiap solusi I dalam S, kita dapat mendefinisikan M(i) sebagai himpunan gerak yang dapat digunakan oleh I untuk memperoleh solusi baru j (notasi: j=i∇m). Secara umum kita dapat menggunakan gerakan- gerakan yang dapat dibalik. Untuk setiap m terdapat gerakan m-1 sehingga (i∇m) ∇m-1 = i.
Jadi daripada mempertahankan list T dari solusi- solusi yang telah dikunjungi, kita dapat secara sederhana memelihara jalur gerak terakhir |T| atau gerak balik terakhir |T| yang diasosiasikan dengan gerakan-gerakan yang sebenarnya telah dilakukan. Maka dengan jelas bahwa pembatasan yang ada adalah kehilangan informasi, dan hal itu tidak menjamin tidak terjadinya siklus dengan panjang paling banyak.
Untuk kepentingan efisiensi, maka diperlukan penggunaan beberapa list Tγ dalam satu waktu maka beberapa unsur pokok tγ (dari i atau dari m) akan diberikan tabu status untuk mengindikasi bahwa unsur pokok ini sedang tidak diperbolehkan untuk terlibat dalam pergerakan. Secara umum pergerakan untuk tabu status adalah fungsi tabu status pada unsur- unsur pokoknya yang dapat diubah pada setiap pengulangan.
Suatu gerakan m (digunakan pada solusi i) akan menjadi gerak tabu jika semua kondisi telah dipenuhi. Ilustrasi dari konsep ini dapat lebih dimengerti pada penggunaan metode pencarian tabu pada penjadwalan pekerjaan (Job Scheduling).
Kekurangan lain dari simplifikasi pada list tabu (penggantian solusi menjadi gerak) adalah fakta bahwa kita mungkin memberikan status tabu ke solusi-solusi yang belum dikunjungi. Maka kita pun dapat memaksakan perenggangan dari tabu status. Kita dapat menguasai tabu status saat beberapa tabu solusi akan terlihat menarik. Hal ini akan dilakukan dimaksudkan untuk tingkat kondisi aspirasi (aspiration level conditions)
Gerak tabu m digunakan pada solusi i yang mungkin tampak menarik karena itu diberikan sebagai contoh sebuah solusi yang lebih baik dari pada yang telah ditemukan. Kita akan dapat menerima m tanpa memperhatikan statusnya. Kita akan melakukan hal tersebut jika memiliki tingkat aspirasi (aspiration level) a(i,m) yang lebih baik daripada permulaan A(i,m).
Sekarang kita dapat mendefinisikan karakteristik dari prosedur pencarian tabu dalam langkah-langkah berikut, antara lain:
1. Memilih solusi awal i dalam S. Tetapkan i*=I dan k=0.
2. Tetapkan k=k+1 dan bangkitkan sebuah subset V* dari solusi dalam N(I,k) sehingga salah satu dari kondisi tabu tγ yang melanggar (γ=1,2,…,t) atau setidaknya satu kondisi aspirasi aγ yang memiliki (γ=1,2,…,a).
3. Pilih j terbaik melalui j=i∇m dalam V* dan tetapkan i=j.
4. Jika f(i)
5. Perbaharui kondisi tabu dan aspirasi.
6. Jika kondisi berhenti ditemukan, maka proses dihentikan. Jika tidak, kembali ke langkah 2.
Hal-hal di atas dapat dikatakan sebagai bahan- bahan dasar dari metode pencarian tabu yang nantinya akan digunakan untuk memecahkan masalah penjadwalan pekerjaan (job scheduling) pada pembahasan selanjutnya.
Tabu Search adalah sebuah meta-heuristic untuk kendali local search yang secara deterministik mencoba untuk menghindari solusi yang baru-baru saja dikunjungi. Secara spesifik, algoritma ini mengelola sebuah tabu List yang berisi perpindahan yang terlarang. List ini mengikuti aturan LIFO dan biasanya sangat pendek (panjangnya biasanya sebesar O( N ), dimana N adalah jumlah total dari operasi). Setiap saat ada langkah yang diambil, maka langkah itu akan ditempatkan dalam tabu list.
Salah satu komponen paling penting dalam algoritma tabu search adalah Neighborhood function (NC), dimana fungsi tersebut secara signifikan akan mempengaruhi running time dan kualitas dari solusi yang dihasilkan. Dalam tabu list, elemen yang ditempatkan di dalam list adalah busar yang dibalik, dan langkah dianggap tabu jika ada komponen dalam busar adalah tabu.
Tujuan akhir dari semua algoritma optimalisasi adalah mendapatkan dengan cepat solusi optimal yang terdekat. Tabu Search sudah terbukti cukup efektif untuk menyelesaikan persoalan tersebut, namun beberapa pelaku riset telah menyatakan bahwa ada beberapa kondisi dimana algoritma tersebut bisa bekerja dengan lebih baik. Beberapa langkah yang bias membuat algoritma tabu search lebih optimal antara lain :
1. Aspiration Criterion. Ini adalah sebuah fungsi yang mengontrol, kapan saja dia bisa mengabaikan sebuah tabu-state dari sebuah langkah. Aspiration criterion, dalam gambaran general, akan menerima sebuah tabu move jika cost dari solusi tersebut akan bisa lebih baik daripada cost dari solusi terbaik yang sudah pernah dikunjungi.
2. Resizing the tabu list. Ini adalah teknik untuk memodifikasi panjang dari tabu list. Pada kebanyakan kasus, tabu list akan diperpendek jika solusi yang lebih baik ditemukan, dan sebaliknya, akan diperpanjang jika solusi yang lebih buruk ditemukan.
Asumsi utama dibalik teknik ini adalah ketika sebuah solusi yang memenuhi telah ditemukan, kemungkinan masih ada solusi lain dalam beberapa langkah selanjutnya, yang juga memenuhi. Menambah jumlah dari pergerakan neighboring yang valid akan membuat algoritma bisa menemukan solusi-solusi yang lebih baik dengan kemungkinan yang lebih besar.
3. Restoring the Best Known Solution. Salah satu cara untuk menghindari pemborosan waktu untuk memeriksa solusi yang kurang optimal adalah dengan mengeset ulang current solution sebagai the best known solution (solusi yang terbaik yang dari seluruh solusi yang sudah diperiksa) secara perodik. Waktu tunggu sebelum mengeset ulang harus diperhitungkan secara hati-hati, tidak bisa terlalu cepat ataupun terlalu lama. Dalam praktiknya, dengan delay time yang sesuai (misalnya 800-1000 iterasi), me-reset current solution akan bisa meningkatkan kualitas solusi yang sudah ditemukan.
2.2.3. Algoritma Rekursif
Algoritma Rekursif adalah algoritma yang memanggil dirinya sendiri. Maka algoritma rekursif selalu disusun oleh 2 bagian yaitu basis dan rekurens. Basis merupakan keadaan penghenti dari pemanggilan sendiri algoritma itu sedangkan rekurens merupakan pemanggilan algoritma itu sendiri.
Definisi rekursif Mendefinisikan sebuah objek dalam term objek itu sendiri
Definisi rekursif Mendefinisikan sequence, fungsi, dan himpunan Contoh :
Sequence untuk n = 0, 1, 2, …
- Term pertama sequence :
- Term berikutnya ditemukan dari term sebelumnya
Fungsi rekursif 2 langkah untuk mendefinisikan fungsi rekursif dalam domain integer non negatif :
Basis Step : tentukan nilai fungsi di 0
Recursive Step : berikan aturan (rule) untuk menemukan nilai fungsi di suatu integer dari nilai fungsi tersebut pada integer yang lebih kecil
Recursive = Inductive definition
Contoh :
Sebuah fungsi f didefinisikan secara rekursif sebagai berikut :
f(0) = 3
(Basis)
f(n+1) = 2 f(n) + 3 (Recursive)
Temukan f(1), f(2), f(3), dan f(4) !
Solusi :
f(1) = 2 f(0) + 3 = 2.3 + 3 = 9
f(2) = 2 f(1) + 3 = 2.9 + 3 = 21
f(3) = 2 f(2) + 3 = 2.21 + 3 = 45
f(4) = 2 f(3) + 3 = 2.45 + 3 = 93
Fungsi faktorial F(n) = n!
F(0) = 0! = 1
(Basis)
F(n+1) = (n+1)! = (n+1) . n!
= (n+1).F(n) (Recursive)
Contoh : Hitung F(5) !
Solusi :
F(5) = 5.F(4) = 5.4.F(3) = 5.4.3.F(2)
= 5.4.3.2.F(1) = 5.4.3.2.1.F(0)
= 5.4.3.2.1.1 = 120
untuk n = 2, 3, 4, …
Fibonacci numbers : 0, 1, 1, 2, 3, 5, 8, …
2.2.4. Algoritma Genetik
Algoritma genetik adalah algoritma pencarian heuristik yang adaptif yang didasarkan pada ide seleksi alam dalam proses evolusi dan genetik yang dikemukakan oleh Charles Darwin. Algoritma ini menggambarkan sebuah eksploitasi kecerdasan dari pencarian random yang digunakan untuk memecahkan masalah-masalah optimisasi. Meskipun bersifat “randomised”, algoritma genetic bukan berarti random (acak) melainkan ia menggunakan informasi historikal untuk mengarahkan pencarian ke dalam daerah yang lebih baik performanya di dalam sebuah ruang pencarian. Teknik-teknik dasar dari algoritma genetik didesain untuk mensimulasi proses-proses dalam sistem alamiah yang diperlukan untuk melakukan evolusi, khususnya proses-proses yang mengikuti prinsip Charles Darwin yaitu “ survival of the fittest “ atau kelangsungan hidup individu yang paling adaptif.
Pada tahun 1859, Charles Darwin mempublikasikan bukunya yang berjudul "On The Origin of Species by Means of Natural Selection". Darwin menggambarkan prinsip dasar yang ditemukannya untuk menjelaskan terjadinya banyak spesies makhluk hidup yang ada di dunia sekarang ini. Makhluk hidup yang dapa beradaptasi dengan lebih baik terhadap lingkungannya akan mempunyai kesempatan yang lebih besar untuk bertahan hidup dan bereproduksi sehingga mempengaruhi jumlah populasi spesies tersebut saat ini. Perubahan kecil fisik atau tingkah laku setiap individu mengakibatkan kemampuan beradaptasi mereka terhadap lingkungan berubah, baik menjadi semakin membaik ataupun semakin memburuk. Individu yang berhasil akan semakin kuat dan memiliki kesempatan yang lebih besar untuk bertahan, serta memiliki kesempatan untuk memberikan kelebihan-kelebihan tersebut pada generasi selanjutnya.
Konsep pada teori evolusi Darwin dapat diterjemahkan menjadi sebuah algoritma untuk mencari solusi atau penyelesaian suatu masalah dengan cara yang lebih natural. Algoritma inilah yang selanjutnya dikenal dengan istilah algoritma genetik. Algoritma genetik memulai dengan sekumpulan solusi (dinyatakan dalam genome) yang dinamakan populasi. Solusi ini kemudian diseleksi untuk mendapat solusi-solusi yang bagus. Proses evolusi dilakukan pada solusi-solusi terpilih untuk menghasilkan generasi baru dari solusi yang diharapkan lebih baik dari generasi sebelumnya. Solusi yang dipilih untuk membentuk solusi baru (keturunan/offspring) dipilih berdasarkan fitness mereka, semakin sesuai semakin besar kemungkina mereka bereproduksi.
Proses ini diulang secara terus-menerus sampai memenuhi kondisi-kondisi tertentu, misalnya jumlah generasi tertentu atau menghasilkan peningkatan dari solusi terbaik. Setiap iterasi dalam proses perulangan ini disebut satu generasi.
Biasanya untuk populasi generasi pertama dipilih secara random yang sesuai sebagai kandidat solusi masalah.
Keuntungan dari algoritma genetik adalah sifat metode pencariannya yang lebih optimal, tanpa terlalu memperbesar ruang pencarian, dan tanpa kehilangan kesempurnaan (completeness) sehingga dapat dengan mudah diimplementasikan ke suatu permasalahan. Selain itu teknik ini juga mampu mencari sebuah solusi yang baik dari banyak solusi yang mungkin, lebih daripada membatasi pencarian pada domain yang sempit di mana hasil yang diperoleh kurang memuaskan. Algoritma genetik mencoba untuk memberikan pencarian cerdas sebuah pemecahan dari pemecahan-pemecahan yang mungkin dan berjumlah hampir tak terbatas [Wibowo dalam Widiyantoro, 2003].
Sifat dari algoritma genetik adalah mencari kemungkinan-kemungkinan dari kandidat solusi untuk mendapatkan suatu solusi yang optimal bagi penyelesaian masalah. Ruang cakupan dari semua solusi yang layak (feasible) yaitu obyek-obyek di antara solusi yang sesuai dinamakan ruang pencarian (search space). Tiap titik dalam ruang pencarian merepresentasikan satu solusi yang layak. Tiap solusi yang layak dapat ditandai dengan nilai fitnessnya bagi masalah. Solusi yang dicari dalam algoritma genetik adalah titik (satu atau lebih) di antara solusi yang layak dalam ruang pencarian. Sifat dari pencarian inilah yang menyebabkan algoritma genetic baik diterapkan untuk menyelesaikan masalah NP-complete.
Dalam ruang pencarian, hal yang harus dipikirkan sehubungan dengan penggunaan algoritma genetik untuk masalah optimisasi adalah bahwa algoritma genetik harus dapat melakukan eksploitasi titik-titik solusi dalam ruang pencarian yang telah diperoleh kemudian mengevaluasinya, dan mengeksplorasi titik-titik baru dalam ruang pencarian. Eksploitasi dilakukan untuk mencari titik-titik terbaik yang telah dijelajahi dari ruang pencarian, sedangkan eksplorasi penting untuk menghindari terperangkapnya dalam hasil optimum lokal (local optima), yaitu titiktitik dalam ruang pencarian yang optimum pada bagian ruang pencarian tertentu saja. Sedangkan optimisasi, hasil yang diharapkan adalah hasil optimum global (global optima), yaitu titik-titik yang paling optimum dalam seluruh ruang pencarian.
Istilah fungsi evaluasi dan fungsi fitness sering sekali saling dipertukarkan penggunaannya. Akan tetapi, adalah berguna untuk membedakan kedua fungsi tersebut dalam algoritma genetik. Fungsi evaluasi, atau fungsi obyektif, merupakan suatu pengukuran performansi terhadap sekumpulan parameter tertentu. Fungsi fitness mentransformasikan pengukuran performansi tersebut ke dalam suatu alokasi kesempatan bereproduksi. Evaluasi terhadap suatu barisan yang menyatakan sekumpulam parameter tertentu adalah independen dari evaluasi terhadap barisan-barisan lain. Fitness suatu barisan selalu didefinisikan berdasarkan anggota-anggota lain dalam populai. Secara umum, fitness didefinisikan fi / f dengan fi adalah fungsi evaluasi dengan genome i dan f adalah evaluasi rata-rata dari semua genome dalam populasi.
Algoritma genetik secara umum dapat ditulis dalam pseudocode sebagai berikut:
begin
// mulai dengan waktu inisial t
t := 0;
// inisialisasi suatu populasi individu yang acak
initpopulation P(t);
// evaluasi fitness untuk semua individu dalam populasi
evaluate P(t);
// tes kriteria berhenti (waktu, fitness, dan sebagainya)
while not done do
// tambahkan pencacah waktu
t := t + 1;
// pilih suatu sub populasi untuk produksi keturunan
P’ := selectparent P(t);
// rekombinasi “gen-gen” dari orang tua terpilih
recombine P’(t);
// melakukan mutasi pada populasi yang berpasangan
mutate P’(t);
// evaluasi fitness baru
evaluate P’(t);
// pilih yang bertahan hidup berdasarkan fitnessnya
P := survive P, P’(t);
end while
end.
Kerangka algoritma genetik di atas masih sangat umum. Terdapat banyak hal berbeda yang dapat diimplementasikan dalam berbagai masalah. Berikut ini akan dibahas beberapa jenis implementasi dari representasi kromosom, pengkodean genome, serta operator-operator algoritma genetik berupa seleksi, perkawinan silang dan mutasi.
A. Kromosom dan Pola Representasi
Algoritma genetik dalam kenyataannya tidak bekerja secara langsung dengan titik pada himpunan Ω , tetapi cukup dengan mengkodekan kandidat solusi suatu masalah dalam bentuk barisan simbol-simbol. Tegasnya, dibutuhkan pemetaan pada sebuah himpunan yang terdiri dari barisan simbol-simbol (string) yang sama panjang. String tersebut dikatakan kromosom (chromosome). Tiap-tiap kromosom terdiri dari elemen-elemen yang berupa simbol-simbol dari himpunan terpilih, katakan alphabet. Sebagai contoh, alphabet yang lazim adalah himpunan {0,1}, dimana dalam kasus ini kromosom adalah string biner sederhana yang mempunyai panjang L yaitu banyaknya simbol 0 dan 1 di dalam string.
Tiap-tiap kromosom ada korespondensi nilai untuk fungsi sasaran, yang disebut sebagai fitness function. Untuk tiap-tiap kromosom x, biasa ditulis f(x) untuk fitness function-nya. Singkatnya, digunakan f untuk menunjukkan fungsi sasaran sebagai ukuran fitness pada himpunan kromosom.
Terpilihnya panjang kromosom, alphabet, dan pengkodean yang merupakan pemetaan dari himpunan Ω atas himpunan kromosom-kromosom disebut sebagai pola representasi (representation scheme) untuk suatu permasalahan. Identifikasi dari pola representasi yang tepat adalah langkah awal dalam menggunakan algoritma genetik untuk menyelesaikan suatu permasalahan optimisasi yang diberikan.
Segera setelah pola representasi sesuai terpilih, tahap selanjutnya adalah menginisialisasi populasi awal P(0) dari kromosom-kromosom. Hal ini biasanya dilakukan dengan memilih secara acak dari himpunan kromosom tersebut. Setela populasi awal terbentuk, kemudian kromosom-kromosom yang terpilih diseleksi menurut fitnessnya, dikawinkan silang, dan dimutasi dengan menggunakan operasi-operasi perkawinan silang dan mutasi pada populasi.
Selama tiap-tiap iterasi k melakukan proses, f (x(k ) ) dievaluasi untuk setiap anggota x(k ) pada populasi P(k). Setelah fitness keseluruhan terevaluasi, kemudian bentuk populasi baru P(k+1) dengan tingkatan seleksi dan evolusi.
B. Pengkodean
Beberapa jenis pengkodean yang sering digunakan dalam mengkodekan kandidat solusi suatu masalah dalam bentuk barisan simbol-simbol antara lain :
1. Pengkodean Biner (Binary Encoding)
Pengkodean biner ini merupakan cara pengkodean yang paling umum digunakan karena pengkodean ini merupakan yang pertama kali digunakan dalam algoritma genetik oleh Holland. Dalam pengkodean biner, setiap kromosom dinyatakan dalam barisan bit 0 atau 1.
Pengkodean biner memberikan banyak kemungkinan untuk kromosom walaupun dengan jumlah allele yang sedikit yaitu 0 atau 1. Pada pihak lain, pengkodean biner ini sering tidak sesuai untuk banyak masalah dan kadang pengoreksian harus dilakukan setelah proses evolusi (perkawinan silang dan/atau mutasi). Contoh masalah yang sesuai untuk pengkodean biner antara lain masalah knapsack (ransel).
2. Pengkodean Permutasi (Permutation Encoding)
Pengkodean permutasi dapat digunakan dalam masalah pengurutan (ordering problem). Dalam pengkodean permutasi, setiap kromosom merupakan suatu barisan bilangan yang menyatakan bilangan dalam suatu urutan.
Pengkodean permutasi hanya berguna bagi masalah pengurutan. Contoh masalah yang menggunakan pengkodean permutasi adalah masalah wiraniaga.
3. Pengkodean Nilai (Value Encoding)
Pengkodean nilai dapat digunakan untuk masalah yang mempunyai nilai yang rumit. Dalam pengkodean nilai, setiap kromosom merupakan suatu barisan dari nilai-nilai. Nilai dapat berupa apa saja yang berhubungan dengan masalah, bilangan biasa, bilangan riil, karakter sampai ke obyek-obyek yang rumit.
Pengkodean nilai sangat baik untuk beberapa masalah tertentu. Pada pihak lain, untuk mengkodekan tipe ini sering perlu mengembangkan perkawinan silang dan mutasi baru yang spesifik untuk permasalahannya. Contoh masalah yang menggunakan pengkodean nilai adalah masalah mencari bobot untuk jaringan syaraf (neural network).
4. Pengkodean Pohon (Tree Encoding)
Pengkodean pohon ini lebih banyak digunakan untuk menyusun program atau ekspresi bagi pemrograman genetik (genetic programming). Dalam pengkodean pohon, setiap kromosom merupakan suatu pohon dari beberapa obyek, seperti fungsi atau perintah dalam bahasa pemrograman.
Pengkodean pohon ini baik digunakan untuk menyusun program. Contoh masalah yang menggunakan pengkodean pohon adalah masalah mencari fungsi berdasarkan nilai-nilai yang diberikan.
C. Seleksi
Tingkatan pertama dalam algoritma genetik digunakan operasi yang dinamakan seleksi. Seleksi disini adalah membentuk himpunan mating pool M(k) dengan banyaknya elemen adalah sama dengan banyaknya elemen pada P(k). Setiap titik m(k ) M(k) diambil dari titik-titik x(k ) P(k).
Dengan kata lain, dipilih kromosom dari P(k) ke dalam M(k) dengan probabilitas proporsional untuk fitnessnya [Chong, 1996].
Seperti yang dapat dilihat pada algoritma genetik, kromosom dalam populasi dipilih sebagai orangtua untuk perkawinan silang. Proses seleksi ini menjamin bahwa individu/kromosom dengan kualitas atau fitness yang lebih baik lebih cenderung terpilih untuk perkawinan silang daripada yang berkualitas atau yang mempunyai fitness lebih rendah.
Himpunan M(k) dibentuk dari P(k) dengan menggunakan beberapa prosedur random. Terdapat beberapa metode bagaimana memilih kromosom, beberapa yang sering digunakan antara lain adalah seleksi roda roulette (roulette wheel selection), seleksi rangking (rank selection), dan seleksi turnamen (tournament selection).
1. Seleksi Roda Roulette (Roulette Wheel Selection)
Pada jenis seleksi ini, orangtua dipilih berdasarkan fitness mereka. Lebih baik suatu kromosom, lebih besar kesempatan terpilih. Probabilitas suatu individu terpilih untuk perkawinan silang sebanding dengan fitnessnya. Cara penyelesaian ini merupakan peniruan dari permainan roda roulette, dan dapat diilustrasikan dengan contoh berikut ini:
Dari contoh tersebut, kromosom A mempunyai probabilitas 37,5% untuk terpilih setiap kali suatu kromosom dipilih (setiap roda diputar). Probabilitas masing-masing individu dapat dicari dari pembagian fitness masing-masing individu dengan total fitness dalam populasi.
Skema seleksi dengan roda roulette ini adalah berdasarkan skala fitness (fitness scale). Karena terpilihnya suatu kromosom dalam populasi untuk dapat berkembang biak adalah sebanding dengan fitnessnya, maka akan terjadi kecenderungan kromosom yang baik akan tetap terpelihara terus sehingga dapat membawa ke hasil optimum lokal atau konvergensi dini (premature convergence) ke suatu hasil yang bukan optimum global. Sebaliknya, jika semua kromosom dalam populas mempunyai fitness yang hampir sama, maka seleksi ini akan menjadi seleksi yang bersifat acak.
Gambar 2.6. (i) Contoh populasi dengan 5 kromosom beserta fitnessnya,
(ii) Probabilitas terpilihnya suatu kromosom dalam roda roulette
2.4.2. Seleksi Rangking (Rank Selection)
Seleksi dengan menggunakan metode roda roulette sebelumnya memiliki kelemahan ketika fitness yang tersebar dalam populasi berbeda jauh. Misalnya, jika fitness dari kromosom terbaik adalah 90% dari keseluruhan roda roulette, maka kromosom lain akan mempunyai kesempatan yang kecil untuk terpilih.
Pada seleksi rangking, pertama yang dilakukan adalah merangkingkan kromosom dalam populasi kemudian setiap kromosom menerima nilai fitness dari rangking tersebut. Kromosom yang terjelek akan mendapatkan nilai fitness 1, yang kedua mendapatkan nilai fitness 2, dan seterusnya sampai yang terbaik mendapatkan nilai fitness N (jumlah kromosom dalam populasi).
Sebagai ilustrasi dapat dilihat pada gambar berikut (dari contoh sebelumnya) : Setelah populasi dirangking berdasarkan fitnessnya, semua kromosom mempunyai kemungkinan untuk terpilih. Tetapi metode ini dapat mengakibatkan konvergensi yang lebih lambat, karena tidak terdapat perbedaan yang besar antar kromosom dalam populasi.
Tabel 2.1. Contoh populasi dengan 5 kromosom yang diberi fitness baru setelah
dirangking
3. Seleksi Turnamen (Tournament Selection)
Seleksi turnamen merupakan jenis seleksi yang divariasi berdasarkan seleksi roda roulette dan seleksi rangking. Sejumlah k kromosom tertentu dari populasi dengan n kromosom (k ≤ n) dipilih secara acak dengan probabilitas yang sama. Dari k kromosom yang terpilih tersebut kemudian dipilih suatu kromosom dengan fitness terbaik, yang diperoleh dari hasil pengurutan rangking fitness kromosom-kromosom yang dipilih tersebut.
Perbedaan dengan seleksi roda roulette adalah bahwa pemilihan kromosom yang akan digunakan untuk berkembang biak tidak berdasarkan skala fitnessnya dari populasi.
Untuk k = 1, seleksi turnamen ini akan sama dengan seleksi secara acak karena hanya melibatkan satu kromosom. Untuk k = 2, maka dua kromosom dalam populasi akan dipilih secara acak, kemudian dari dua kromosom tersebut dipilih satu kromosom dengan fitness tersebut. Biasanya yang sering digunakan adalah untuk k = 2, tergantung dari ukuran populasi.
0 komentar:
Posting Komentar
Tinggalkan komentar untuk perbaikan atau kritik dan saran serta pertanyaan...thanks....:)