BAB 2 TINJAUAN PUSTAKA
Bab ini membahas tentang teori penunjang serta penelitian sebelumnya yang berhubungan dengan penerapan metode tournament selection pada metode seleksi parent dalam algoritma genetika untuk menyelesaikan masalah N-Queen. 2.1
Kecerdasan Buatan
Kecerdasan Buatan (Artificial Intelligence) adalah kecerdasan mesin dan cabang ilmu komputer yang bertujuan untuk menciptakan suatu sistem yang dapat merasakan
lingkungannya
dan
dapat
mengambiil
tindakan
dengan
memaksimalkan peluang yang dianggap sukses (Setiadi : 2012). Kecerdasan buatan juga dapat diartikan sebagai sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan lebih baik oleh manusia. Beberapa bidang perkembangan pada kecerdasan buatan adalah sebagai berikut (Prasetyo : 2012): 1.
Sistem Pakar (Expert System) Sistem pakar adalah program penasehat berbasis komputer yang mencoba meniru proses berpikir dan pengetahuan dari seorang pakar dalam menyelesaikan masalah-masalah spesifik. Contohnya adalah sistem pakar menentukan suatu jenis penyakit, sistem pakar untuk bisnis dan sebagainya.
2.
Bahasa Alamiah (Natural Languange) Suatu teknologi yang memberikan kemampuan kepada komputer untuk memahami
bahasa
manusia
sehingga
pengguna
komputer
dapat
berkomunikasi dengan komputer dengan menggunakan bahasa sehari-hari. 3.
Robotik dan Sistem Sensor Sistem sensor, seperti sistem vision, sistem tactile, dan sistem pemrosesan sinyal jika dikombinasikan dengan AI, dapat dikategorikan kedalam suatu sistem yang luas yang disebut sistem robotik.
Universitas Sumatera Utara
7
4.
Computer Vision Computer Vision merupakan suatu sarana untuk dapat menginterpretasikan gambar atau objek-objek yang tampak melalui komputer.
5.
Permainan (Games) Permainan merupakan suatu bidang AI yang sangat populer berupa permainan antara manusia melawan mesin yang memiliki intelektual untuk berpikir. Dalam pengaplikasiannya, ada sembilan tujuan akhir yang diharapkan
dalam penerapan kecerdasan buatan, yaitu (Akbar : 2011): 1.
Memahami pola pikir manusia, mencoba untuk mendapatkan pengetahuan ingatan manusia yang mendalam, kemampuan dalam memecahkan masalah, belajar, dan mengambil keputusan.
2.
Otomatisasi, menciptakan sistem yang dapat menggantikan manusia dalam tugas-tugas intelegensi. Menggunakan sistem yang performanya sebaik manusia dalam melakukan pekerjaan.
3.
Penguatan intelegensi, membangun sistem untuk membantu manusia agar mampu berpikir lebih baik dan lebih cepat.
4.
Intelegensi manusia super, membangun sistem yang mempunyai kemampuan untuk melebihi intelegensi manusia.
5.
Menyelesaikan permasalahan, sistem mampu menyelesaikan berbagai masalah yang luas.
6.
Wacana koheren, mampu berkomunikasi dengan manusia menggunakan bahasa alami.
7.
Belajar, mampu memperoleh data sendiri dan mengetahui bagaimana cara memperoleh data. Sistem mampu membuat hipotesis, penerapan atau pembelajaran secara heuristik dan membuat alasan dengan analogi.
8.
Otonomi, mempunyai sistem intelegensi yang beraksi atas inisiatif sendiri. Informasi, mampu menyimpan informasi dan mengetahui cara mengambil informasi.
Universitas Sumatera Utara
8
2.2
Algoritma Genetika
Algoritma genetika adalah suatu algoritma pencarian yang meniru mekanisme dari genetika alam. Algoritma Genetika banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan lainnya. Algoritma ini dimulai dengan kumpulan solusi yang disebut dengan populasi. Solusi-solusi dari sebuah populasi diambil dan digunakan untuk membentuk populasi yang baru. Hal ini dimotivasi dengan harapan bahwa populasi yang baru dibentuk tersebut akan lebih baik daripada yang lama. Solusi-solusi yang dipilih untuk membentuk solusisolusi yang baru dipilih sesuai dengan fitness mereka masing-masing (Juniawati : 2003).
Algoritma genetika digunakan untuk penyelesaian masalah optimasi yang kompleks
dan
sukar
diselesaikan
dengan
menggunakan
metode
yang
konvensional. Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu: operator reproduksi, operator crossover (persilangan) dan operator mutasi. Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut (Juniawati : 2003):
1.
Membangkitkan populasi awal, Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan
2.
Membentuk generasi baru, Dalam membentuk digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru.
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 dibentuk lagi generasi baru dengan mengulangi langkah 2.
Universitas Sumatera Utara
9
Dalam algoritma genetika pengkodean (encoding) solusi problem kedalam suatu kromosom merupakan isu penting. Populasi awal yang berisi N kromosom dibangkitkan secara random yang menjangkau keseluruhan ruang solusi. Proses evolusi dilakukan dengan melakukan operasi genetik (cross-over dan mutasi) dan melakukan seleksi kromosom untuk generasi berikutnya sampai sejumlah generasi yang dikehendaki dengan panduan fungsi fitness (Miller : 1995).
Fungsi fitness adalah fungsi yang digunakan untuk menentukan apakah suatu kromosom layak bertahan. Pada setiap generasi dipilih kromosom yang mendekati solusi dengan mengevaluasi fungsi kecocokan dari kromosom tersebut. Fungsi ini didefinisikan sedemikian sehingga semakin besar nilai fitness semakin besar probabilitas untuk terseleksi pada generasi berikutnya. Untuk maksimasi maka fungsi tujuan dapat dijadikan sebagai fungsi fitness, sehingga kromosom yang mewakili nilai fungsi besar akan memiliki probabilitas terseleksi yang besar juga. Untuk minimasi dapat dirumuskan sedemikian sehingga fungsi tujuan yang semakin kecil maka memiliki fungsi fitness yang besar (Miller : 1995).
Setiap anggota populasi diwakili deretan string (disebut kromosom) dengan panjang tertentu. Elemen string tersebut dapat berupa digit 0,1 (untuk binary encoding), bilangan real (untuk real encoding), atau elemen lain. Untuk ukuran populasi N yang biasanya dipertahankan tetap prosedur seleksi diperlukan untuk memilih anggota populasi yang mana yang akan tetap eksis pada generasi berikutnya (Akbar : 2011).
Fungsi fitness digunakan untuk menentukan apakah kromosom layak dipertahankan atau tidak dalam generasi berikutnya. Sebelum dilakukan seleksi jumlah anggota populasi ditambah dengan hasil offspring dari proses operasi genetik yang dapat berupa cross over dan mutasi. Hasil operasi genetik dan populasi semula selanjutnya diseleksi dengan metode tertentu untuk diambil n anggota populasi yang terbaik. Untuk kasus minimasi maka yang terpilih adalah n anggota populasi dengan nilai fitness yang terkecil (Akbar : 2011).
Universitas Sumatera Utara
10
Proses operasi crossover dirancang untuk mencari kemungkinan yang lebih baik dari anggota populasi yang telah ada. Dari pasangan induk yang terpilih berdasarkan seleksi fungsi fitness diambil sejumlah pasangan dengan probabilitas Pc untuk dikenakan operasi crossover (Blicke & Thiele : 1995).
Mutasi dalam konteks binary encoding adalah perubahan pada bit tunggal (bit 0 jadi 1 dan sebaliknya) anggota populasi yang terpilih. Banyaknya bit yang mengalami mutasi pada setiap generasi diatur oleh probabilitas mutasi (Pm) yang nilainya merupakan cacah bit mutasi dibagi cacah bit total dalam populasi (Blicke & Thiele : 1995).
2.3
Metode Tournament Selection
Tournament selection merupakan salah satu mekanisme seleksi parent pada algoritma genetika yang baik dan berguna. Hasil seleksi pada tournament selection sangat dipengaruhi pada
pemilihan jumlah turnamen serta jumlah
competitor (individu yang akan diikut sertakan di dalam turnamen). Semakin banyak jumlah turnamen dan jumlah kompetitor di dalam tournament selection, persaingan akan semakin ketat yang pada akhirnya akan menghasilkan hasil seleksi yang lebih baik (Filipovic : 2003).
Beberapa alasan mengapa tournament selection sangat berguna di dalam proses seleksi pada algoritma genetika adalah kesederhanaan bentuk algoritmanya serta kefisiensiannya jika digunakan baik pada arsitektur paralel maupun nonparalel. Demikian pula dengan fleksibilitas yang dimiliki metode ini terhadap perubahan input dan output yang diinginkan (Filipovic : 2003).
Tournament selection dimulai dengan memilih jumlah turnamen yang akan dilakukan. Pemilihan jumlah turnamen ini sebaiknya disesuaikan dengan jumlah parent yang diinginkan pada proses crossover berikutnya. Selanjutnya, untuk setiap turnamen, akan dipilih secara acak dua individu dari populasi awal untuk ditandingkan. Pemenang pada pertandingan ini ditentukan dengan melihat nilai fitness masing-masing individu, dimana individu dengan nilai fitness paling besar
Universitas Sumatera Utara
11
akan keluar sebagai pemenang. Setiap individu yang menjadi pemenang pada masing-masing turnamen kemudian dipilih menjadi parent yang akan digunakan pada proses crossover berikutnya (Filipovic : 2003).
2.4
N-Queen Problem
N-Queens Problem adalah salah satu permasalahan yang paling umum digunakan dalam berbagai buku pegangan untuk menjelaskan algoritma backtracking. Inti permasalahan yang diajukan adalah bagaimana menempatkan N buah bidak ratu dalam suatu papan catur berukuran N x N sedemikian rupa sehingga tidak satupun dari bidak ratu tersebut dapat memakan bidak ratu yang lain dalam satu gerakan. Sesuai dengan gerakan bidak ratu standar, suatu bidak ratu hanya dapat bergerak lurus dalam satu kolom, baris, atau diagonal. Untuk itu sebuah solusi harus dapat mengatur penempatan bidak ratu sehingga tidak ada dua bidak yang terletak dalam suatu kolom, baris, atau diagonal yang sama (Božikovic et. al : 2003).
N-Queens problem pertama kali diusulkan sebagai 8 Queens Problem, sesuai dengan ukuran papan catur sebenarnya yaitu 8 x 8, pada tahun 1848 oleh seorang pecatur Max Bezzel. Banyak matematikawan, termasuk Gauss dan Georg Cantor, telah berusaha mencari solusi permasalahan ini. Solusi pertama dipublikasikan
oleh
Franz
Nauck
pada
tahun
1850—termasuk
solusi
permasalahan umumnya, yaitu ketika jumlah bidak ratu dimisalkan sebagai N (Božikovic et. al : 2003).
Masalah ini dapat digeneralisasikan dengan cara meletakkan queen sejumlah n yang tidak saling bertabrakan di dalam sebuah papan catur. Karena setiap queen harus berada pada baris dan kolom yang berbeda, maka dapat diasumsikan bahwa queen pada posisi ke-i adalah queen yang diletakkan pada kolom ke-i. Solusi dari masalah ini dapat direpresentasikan sebagai q1, q2, … qn yang merupakan permutasi dari jumlah queen itu sendiri. Posisi dari queen pada kelompok solusi merupakan representasi dari posisi kolom queen, sedangkan nilai dari posisi queen tersebut merepresentasikan baris dari queen tersebut pada papan catur. Sebagai contoh, jika sebuah kelompok solusi bernilai 1,3,5,2,4 maka dapat
Universitas Sumatera Utara
12
diartikan bahwa pada kolom pertama posisi queen berada di baris pertama, pada kolom kedua posisi queen berada di baris ketiga, pada kolom ketiga posisi queen berada di baris kelima, pada kolom keempat posisi queen berada di baris kedua dan pada kolom kelima posisi queen berada di baris keempat. Sebagai ilustrasi, formasi queen dari kelompok 1,3,5,2,4 tersebut seperti digambarkan pada Gambar 2.1 (Pothumani : 2013).
Q Q Q Q Q Gambar 2.1 Ilustrasi Solusi 1,3,5,2,4 (Pothumani, 2013) Dalam mencari solusi posisi dalam permasalahan n-queen, sebagai acuan dari seberapa akurat kelompok solusi yang dihasilkan, digunakan fungsi fitness. Fungsi fitness dari masalah n-queen merupakan jumlah dari posisi queen yang mengalami tabrakan dibandingkan dengan total jumlah posisi queen dalam kelompok solusi tersebut. Sebagai contoh, jika dalam sebuah kelompok solusi dihasilkan nilai 3,2,5,1,4, maka langkah pertama dalam menghitung fungsi fitness kelompok solusi ini adalah menggambarkan posisi queen dari kelompok solusi tersebut ke dalam papan catur, sebagaimana terlihat pada Gambar 2.2 (Pothumani : 2013).
Q Q Q Q Q Gambar 2.2 Posisi Queen Dalam Papan Catur (Pothumani, 2013) Selanjutnya, setiap posisi akan diperiksa apakah mengalami tabrakan dengan posisi queen yang lain secara horizontal maupun diagonal. Untuk posisi queen pertama (kolom 1 baris 3), terlihat bahwa posisi ini mengalami tabrakan
Universitas Sumatera Utara
13
dengan posisi queen kedua (kolom 2 baris 2) secara diagonal, seperti terlihat pada ilustrasi di Gambar 2.3, dimana queen yang bertabrakan diberi warna merah (Pothumani : 2013).
Q Q Q Q Q Gambar 2.3 Contoh Queen Yang Saling Bertabrakan (Pothumani, 2013) Untuk posisi queen kedua, terlihat bahwa posisi ini mengalami tabrakan dengan posisi queen pertama secara diagonal. Untuk posisi queen ketiga (kolom 3 baris 5), terlihat bahwa posisi ini mengalami tabrakan dengan posisi queen pertama secara diagonal. Untuk posisi queen keempat (kolom 4 baris 1), terlihat bahwa posisi ini tidak mengalami tabrakan dengan posisi queen manapun, baik secara horizontal maupun diagonal. Untuk posisi queen kelima (kolom 5 baris 4) , terlihat bahwa posisi ini tidak mengalami tabrakan dengan posisi queen manapun (Pothumani : 2013).
Dari contoh kelompok solusi 3,2,5,1,4 di atas, terlihat bahwa dari lima posisi queen di dalam kelompok solusi tersebut, terdapat tiga posisi yang saling bertabrakan. Sehingga, dapat dihitung nilai fitness kelompok solusi tersebut, yaitu 3/5 atau 0,6. Dengan melihat contoh perhitungan nilai fitness kelompok solusi dari masalah n-queen ini, dapat disimpulkan bahwa nilai fitness yang semakin mendekati angka satu adalah nilai fitness yang paling jelek, karena di dalam kelompok solusi tersebut terdapat posisi queen yang banyak mengalami tabrakan. Sebaliknya, semakin mendekati angka nol, maka nilai fitness dari kelompok solusi tersebut akan semakin baik, dengan nilai nol adalah solusi yang paling sempurna (dimana tidak terdapat satupun posisi queen yang saling bertabrakan) (Pothumani : 2013).
Universitas Sumatera Utara
14
2.5
Penelitian Sebelumnya
Dalam masalah seleksi parent pada algoritma genetika menggunakan metode tournament selection, ada dua penelitian yang dapat dijadikan sebagai referensi mengenai cara kerja metode tersebut.
Penelitian pertama adalah penelitian yang dilakukan oleh Vladimir Filiponic pada tahun 2003. Penelitian yang diterbitkan pada jurnal Computing and Informatic Vol. 22 ini berjudul Fine-Grained Tournament Selection Operator In Genetic Algorithm. Penelitian ini mengangkat masalah pengembangan dari metode tournament selection, yang mana kemudian dinamakan sebagai finegrained tournament selection. Dalam jurnal yang diterbitan pada computing and informatic Vol. 22 tersebut, Filiponic menjelaskan bagaimana metode tournament selection sangat efektif digunakan dalam menyelesaikan masalah Simple Plant Location Problem (SPLP) dalam skala besar. Pengembangan metode tournament selection ini mampu menyelesaikan masalah SPLP dengan lebih dari 1000 lokasi produksi dan customer.
Penelitian kedua adalah penelitian yang dilakukan oleh Brad L. Miller dan David E. Goldberg pada tahun 1995. Penelitian yang diterbitkan pada jurnal Complex System Vol. 9 ini mengangkat masalah noise yang sering terjadi dalam penghitungan fungsi fitness di dalam algoritma genetika. Dalam penelitian ini, Brad L. Miller dan David E. Goldberg menjelaskan bagaimana metode tournament selection memiliki ketahanan yang sangat baik terhadap noise yang mungkin terjadi pada tahap penghitungan fungsi fitness di dalam algoritma genetika. Brad L. Miller dan David E. Goldberg juga menyimpulkan bahwa metode
tournament
selction
merupakan
metode
yang
gampang
untuk
diimplementasikan pada masalah-masalah yang bersifat paralel maupun nonparalel, sekaligus juga sangat fleksibel terhadap perubahan individu yang terjadi di dalam proses seleksi.
Universitas Sumatera Utara
15
Dari kedua penelitian tersebut, dapat disimpulkan beberapa kelebihan dari metode tournament selection dalam pemilihan parent di dalam algoritma genetika sebagai berikut :
1. Sangat efektif untuk menyelesaikan masalah dalam skala besar. 2. Memiliki ketahanan yang baik terhadap noise pada tahap penghitungan fungsi fitness. 3. Mudah untuk diimplementasikan pada masalah-masalah yang bersifat paralel maupun non-paralel. 4. Fleksibel terhadap perubahan yang terjadi pada individu di dalam proses seleksi parent. 5. Adapun inti dari kedua penelitian yang digunakan sebagai referensi terhadap metode tournament selection dalam proses seleksi parent pada algoritma genetika ini dapat ditunjukkan pada Tabel 2.1.
Tabel 2.1 Penelitian Sebelumnya Peneliti
Tahun
Vladimir
2003
Filipovic
Judul
Hasil
Fine-Grained Tournament
Tournament selection
Selection Operator In
merupakan metode yang
Genetic Algoritm
efektif digunakan dalam menyelesaikan masalah dalam skala besar.
Brad L.
Genetic Algoritm,
Tournament selection
Miller &
Tournament Selection and
merupakan metode yang
David E.
the Effevt of the Noise
memiliki ketahanan yang
Goldberg
1995
baik terhadap noise pada tahapan penghitungan fungsi fitness, mudah untuk diimplementasikan pada masalah yang bersifat paralal maupun non-paralel
Universitas Sumatera Utara
16
dan fleksibel terhadap perubahan individu yang terjadi pada proses seleksi parent. S.
2013
Pothumani
Solving N-Queen Problem
Variasi hasil solusi
Using Various Algorithm –
pemecahan masalah N-
A Survey
Queen dengan menggunakan berbagai algoritma.
Marko
2003
Bozikovic, Marin
Solving N-Queen Problem
Membuktikan bahwa
Using Global Parallel
algoritma genetika cocok
Genetic Algorithm
digunakan untuk
Golub &
memecahkan masalah N-
Leo Budin
Ahmed S.
Queen.
2015
Farhan,
Solving N-Queen Problem
Solusi-solusi yang
Using Genetic Algorithm
memungkinkan dari
Wadhah Z.
masalah N-Queen dengan
Tareq &
jumlah queen = 8.
Foiuad H. Awad Azwar W.
2007
Genetic Algorithm Versus
Algoritma genetika lebih
Hammad &
Particle Swarm
stabil dibandingkan Particle
Dr. Ban N.
Optimization In N-Queen
Swarm Optimization untuk
Thannoon
Problem
masalah non-linier.
Universitas Sumatera Utara