BAB 2 LANDASAN TEORI
2.1
Sudoku Sudoku adalah sebuah permainan teka-teki berdasarkan logika dengan
kombinasi penempatan angka. Dalam permainan sudoku,
pemain diminta untuk
mengisi N x N kotak yang dimana pada tiap kotak dapat diisi dengan angka dari 1 sampai dengan N itu sendiri. Aturan permainan pada tiap baris yang sejajar dan pada tiap kolom yang sejajar tidak boleh memiliki angka yang sama, yang dimana angkaangka tersebut merupakan angka dari 1 sampai dengan N itu sendiri. N memiliki M x M kotak yang dimana nilai dari M adalah akar dari N. Kotak M x M juga memilki aturan yang sama dengan kotak N x N. Contoh pada gambar 1 adalah Sudoku dengan kotak M = 3. N M
M
N
Gambar 2.1 Contoh Sudoku 3x3
8
9 Tujuannya adalah untuk mengisi sembilan x sembilan grid sehingga tiap baris dan kolom mengandung angka satu sampai sembilan masing-masing hanya satu kali, dimana tiap tiga x tiga grid juga mengandung angka satu sampai sembilan. Hal yang membuat permainan Sudoku menarik adalah Sudoku memiliki peraturan yang mudah untuk dimengerti, tetapi untuk mendapatkan jawaban yang benar dan tepat ternyata sangat kompleks dan tidaklah mudah. Tingkat kesulitan pada permainan Sudoku dapat juga disesuaikan dengan kemampuan dari pemain.
2.1.1
Sejarah Sudoku Menurut
website
http://en.wikipedia.org/wiki/Sudoku
(2009)
dan
http://www.sudokudaily.net/history.php (2005), Sudoku memiliki sejarah yang menarik. Teka-teki angka pertama muncul dalam surat kabar pada akhir abad ke-19, ketika surat kabar harian Perancis, Le Siècle puzzle setters mulai percobaan dengan menghapus nomor dari sembilan kali sembilan magic square dan tiga kali tiga sub-kotak pada 1892. Ini bukanlah sudoku karena berisi dua digit angka dan aritmatika diperlukan daripada logika untuk memecahkan, namun ia bersama karakteristik kunci: setiap baris, kolom dan sub-persegi ditambah hingga nomor yang sama. Dalam waktu tiga tahun surat kabar pesaing dari Le Siècle yaitu La France memunculkan tekateki serupa yang menyederhanakan sembilan kali sembilan magic square sehingga tiap baris dan kolom hanya berisi angka-angka satu sampai sembilan. Hal ini dianggap sebagai asal-usul Sudoku. Pada abad ke-18, matematikawan dari Swiss yang bernama Leonhard Euler menciptakan konsep dari “Latin Square” yang dimana angka pada tiap batasan hanya muncul sekali secara vertikal dan horizontal. Pada akhir tahun 1970-an, majalah Dell di Amerika mulai menerbitkan permainan yang dimana sekarang dikenal dengan Sudoku
10 dengan menggunakan konsep Euler yang menggunakan kotak 9 x 9. Mereka menyebutnya sebagai penempat angka (Number Place), dan permainan tersebut diciptakan oleh Howard Garnes. Pada pertengahan tahun 1980-an, Maki Kaji seorang presiden dari sebuah perusahaan puzzle di Jepang yang bernama Nikoli, mendesak perusahaannya untuk menerbitkan versi Jepang dari permainan penempat angka (Number Place) kedalam majalah Nikolist, permainan teka-teki ini disebut sebagai “Suuji wa dokushin ni kagiru” yang dapat diterjemahkan sebagai “angka harus tunggal”. Kemudian hari, nama ini disingkat oleh Maki Kaji dengan mengambil kanji pertama dari tiap kata majemuk, menjadi kata Sudoku. Pada tahun 1997, sudah banyak Puzzle Sudoku ditemukan pada toko buku Jepang. Beberapa tahun kemudian, Wayne Gould seorang pensiunan hakim dari Hong Kong yang aslinya berasal dari Selandia Baru mengembangkan permainan Sudoku menjadi program komputer. Dan pada tahun 2005, untuk pertama kalinya permainan Sudoku menjadi bagian dari acara TV berjudul Sudoku Show, Sudoku Live. Permainan ini sangat popular di Jepang dan meluas hingga ke seluruh dunia. Di Indonesia pun permainan ini banyak digemari oleh para pecinta permainan teka-teki dan matematika. Banyak penelitian yang dilakukan oleh para ahli terkait dengan pengembangan aplikasi permainan dan pencarian solusi Sudoku. Penelitian dilakukan dengan memasukan peraturan permainan Sudoku ke dalam komputer untuk kemudian diproses dengan algoritma tertentu yang ditujukan untuk mencari solusi terbaik dari persoalan Sudoku tersebut. Banyak penelitian yang dilakukan dengan menerapkan kecerdasan buatan ( Artificial Inteligence ) pada computer untuk memecahkan masalah ini.
11 2.1.2
Cara Bermain Permainan Sudoku pada umumnya terdiri dari tabel dengan jumlah kotak 9 x 9,
yang dibuat dengan wilayah (region) 3 x 3. Untuk memulai bermain pada permainan Sudoku, ada beberapa kotak yang sebelumnya telah diisi dengan angka-angka yang dimana angka-angka tersebut digunakan sebagai petunjuk (clue) untuk mencari angkaangka yang lain pada kotak yang belum terisi. Tujuan dari permainan ini adalah mengisi semua kotak yang masih kosong di mana setiap kotak hanya dapat diisi oleh 1 angka. Dalam setiap baris, kolom dan wilayah diisi dengan angka 1 (satu) sampai dengan 9 (sembilan) dengan kemungkinan hanya sekali. Setiap angka dalam solusi ini terjadi hanya sekali dalam 3 kondisi (baris, kolom dan wilayah).
Gambar 2.2 Sudoku yang sudah diselesaikan
Pada gambar diatas terdapat angka yang berwarna hitam yang merupakan angka petunjuk (clue) dan angka yang berwarna ungu yang merupakan angka yang berhasil dicari oleh pemain.
12 2.1.3
Jenis Sudoku Dalam perkembangannya, permainan Sudoku tidak hanya dimainkan dengan
menggunakan angka saja tetapi juga menggunakan huruf, gambar dan bentuk yang dimana tiap simbol tersebut memiliki tingkat kesulitan yang berbeda-beda pada tiap orang yang memainkannya. Dan untuk alas permainannya dapat dimainkan dengan beraneka ragam ukuran dan bentuk, sedangkan untuk wilayahnya dapat divariasikan dengan bentuk yang bermacam-macam. Berikut ini adalah beberapa contoh variasi yang dapat diciptakan pada permainan sudoku: •
Alas permainan kotak 4 x 4 dengan wilayah 2 x 2.
•
Alas permainan kotak 5 x 5 dengan wilayah berupa pentomino.
•
Alas permainan kotak 7 x 7 dengan wilayah berupa heptomino.
•
Alas permainan kotak 9 x 9 dengan wilayah berupa nonomino. wilayah ini yang paling sering digunakan dalam permainan Sudoku dan sebagai jenis sudoku yang akan dibahas pada skripsi ini.
•
2.2
Alas permainan kotak 16 x 16 dengan wilayah hexudoku.
Algoritma Algoritma adalah jantung dari ilmu komputer. Banyak sekali cabang dari ilmu
komputer yang masuk dalam terminologi algoritma. Dalam kehidupan sehari-hari banyak terdapat proses yang dapat dinyatakan dalam suatu algoritma. Contohnya adalah langkah-langkah dalam membuat kopi, tahapan-tahapan yang dilakukan bila ingin bepergian dengan kendaraan tertentu, dapat juga disebut sebagai algoritma. Pada saat membuat kopi selalu ada urutan langkah-langkah dalam pembuatannya. Secara umum,
13 pihak (benda) yang mengerjakan proses disebut pemroses (processor). Pemroses tersebut dapat berupa manusia, computer, robot, alat-alat elektronik, atau benda-benda lainnya. Pemroses melakukan suatu proses dengan melaksakan atau mengeksekusi algoritma yang menjabarkan proses tersebut (Alex Budianto, 2003). Melaksanakan Algoritma berarti mengerjakan langkah-langka di dalam Algoritma tersebut. Pemroses mengerjakan proses sesuai dengan algoritma yang diberikan kepadanya. Juru masak membuat masakan berdasarkan resep yang diberikan kepadanya, pemain musik memainkan lagu berdasarkan papan not balok. Oleh karena itu, suatu Algoritma harus dinyatakan dalam bentuk yang dapat dimengerti oleh pemroses. Jadi suatu pemroses harus :
2.2.1
•
Mengerti setiap langkah dalam algoritma
•
Mengerjakan operasi yang sesuai dengan langkah tersebut.
Sejarah Algoritma Asal-usul kata Algoritma mempunyai sejarah yang unik. Para ahli sejarah
matematika menemukan bahwa rupanya kata Algoritma berasa dari nama seorang ahli matematika dari Uzbekistan yang hidup di masa tahun 770-840 masehi yaitu Abu Ja’far Muhammad Ibnu Musa Al-Khuwarizmi. Kata “Al-Khuwarizmi” dibaca oleh orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar Wal Muwabala yang memiliki arti “Buku Pemugaran dan pengurangan”. Dari judul buku ini juga diperoleh asal usul kata “Aljabar” (Algebra).
Perubahan dari kata
Algorism menjadi Algorithm muncul karena kata Algorism sering dikelirukan dengan Arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan menggunakan angka Arab sudah menjadi hal yang biasa, maka kata Algorithm
14 berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam Bahasa Indonesia, kata Algorithm diserap menjadi Algoritma (Alex Budianto, 2003)
2.2.2
Definisi Algoritma Definisi dari Algoritma adalah “Urutan langkah-langkah logis penyelesaian
masalah dalam bentuk kalimat dengan jumlah kata terbatas, tetapi disusun secara sistematis dan logis”. (Alex Budianto, 2003)
2.2.3
Ciri Algoritma Algoritma memiliki beberapa ciri, antara lain : a. Mempunyai awal dan akhir Setiap Algoritma memiliki tahap-tahap di mana algoritma akan mulai dan tahap algoritma akan berakhir. b. Setiap langkah didefinisikan dengan tepat Setiap langkah dalam suatu metode algoritma harus didefinisikan dengan tetap agar tidak terjadi kercanuan dan kesalahan saat algoritma dijalankan. c. Memiliki masukan (input) Algoritma dalam menyelesaikan suatu masalah harus memiliki variablevariabel tertentu yang dijadikan masukan untuk menyelesaikan suatu masalah. Contoh: dalam algoritma perhitungan luas segitiga biasanya terdapat dua variable masukan yaitu panjang alas dan tinggi.
15 d. Memiliki keluaran (output) Algoritma jika sudah selesai dijalankan harus menghasilkan suatu hasil yang merupakan solusi dalam permasalah yang diselesaikan dalam algoritma tersebut. Contoh : dalam algoritma perhitungan luas segitiga, suatu algoritma akan mengeluarkan output berupa luas segitiga tersebut. e. Harus efektif (bisa menyelesaikan persoalan) Suatu algoritma harus dapat menyelesaikan persoalan yang ada, untuk tujuan tersebutlah suatu algoritma dibangun. Contoh : dalam algoritma perhitungan luas segitiga, maka suatu algoritma harus dapat menyelesaikan perhitungan luas segitiga tersebut.
2.2.4
Sifat Algoritma Sifat-sifat dari algoritma adalah: a. Input Sifat ini berarti, suatu algoritma memiliki kondisi awal sebelum dilaksanakan. b. Output Sifat ini berarti, suatu algoritma menghasilkan keluaran setelah dilaksanakan. c. Definitif Sifat ini berarti, langkah-langkah dari suatu algoritma terdefinisi dengan jelas d. Finit Sifat ini berarti, suatu algoritma melakukan langkah yang terbatas jumlahnya dalam mengolah input menjadi output.
16 e. Efektif Sifat ini berarti, suatu algoritma dapat memberi solusi sesuai harapan. f. General Sifat ini berarti, suatu algoritma berlaku untuk setiap himpunan input.
2.2.5
Struktur Algoritma Setiap Algoritma akan selalu terdiri dari tiga bagian yaitu : •
Judul (Header)
•
Kamus
•
Algoritma
Pada setiap bagian tersebut apabila akan dituliskan komentar mengenai setiap bagian tersebut dituliskan di antara kurung kurawal, contoh {Komentar}. Notasi algoritma yang dituliskan di antara tanda ini tidak akan dieksekusi oleh program Contoh : Judul { Komentar mengenai algoritma seperti cara kerja program, kondisi awal dan kondisi akhir dari algoritma } Kamus { Pada bagian ini, didefinisikan nama konstanta, nama variable, nama prosedur dan nama fungsi } Algoritma { Pada bagian ini algoritma dituliskan. Semua teks yang ditulis tidak diantara tanda kurung
kurawal dianggap sebagai notasi
17 algorima yang akan
berpengaruh
terhadap
kebenaran
algoritma} 2.2.5.1 Judul (Header) Judul adalah bagian teks algoritma yang digunakan sebagai tempat mendefinisikan nama dengan menentukan apakah teks tersebut adalah program, prosedur, fungsi. Setelah judul disarankan untuk menuliskan spesifikasi singkat dari teks algoritma tersebut.
Nama algoritma sebaiknya singkat namun cukup
menggambarkan apa yang akan dilakukan oleh algoritma tersebut. Contoh :
Program Luas_Kubus
{Judul Algoritma}
{Menghitung luas kubus untuk ukuran sisi yang dibaca dari piranti masukan lalu mencetak hasil ke piranti keluaran}
{Spesifikasi Algoritma}
Catatan : Untuk memisahkan antara kata dalam judul algoritma menggunakan tanda “_” bukanlah
suatu
Luas_Lingkaran.
keharusan.
Anda
dapat
menuliskan
LuasLingkarang
atau
Tetapi sebaiknya anda tidak menggunakan spasi “ ” untuk
memisahkan antara kata didalam algoritma.
18
2.2.5.2 Kamus (Deklarasi) Kamus adalah bagian teks algoritma sebagai tempat untuk mendefinisikan : •
Nama Tipe.
•
Nama Konstanta.
•
Nama Variable.
•
Nama Fungsi.
•
Nama Prosedur.
Semua nama tersebut baru akan dapat dipakai di dalam algoritma jika telah didefinisikan terlebih dahulu di dalam kamus.
Penulisan sekumpulan nama dalam
kamus sebaikanya dikelompokan menurut jenis nama tersebut. Nama variabel belum terdefinisi nilainya ketika didefinisikan. Pendefinisian nama konstanta sekaligus memberi harga konstanta tersebut, pendefinisian nama fungsi dilakukan sekaligus dengan domain / range serta spesifikasinya. Pendefinisian nama prosedur sekaligus dengan pendefinisian parameter (jika ada) dan spesifikasi prosedur (kondisi awal “Initial State” , kondisi akhir “Final State” dan proses yang dilakukan).
Contoh : Kamus {Nama type, hanya untuk type yang bukan type dasar} type jam :
{Type jam terdiri dari 3 masukan yaitu “hh” sebagai jam . “mm” sebagai menit dan “ss” sebagai detik }
19
{Nama konstanta harus menyebutkan type dan nilai} constant phi : real = 3,14159 constant nama : string = ‘Niko’ constant benar : Boolean = true
{Nama Informasi, menyebutkan type} x,y : integer {suatu nilai yang bertype bilangan bulat} NMax : real {nilai maksimal yang bertype bilangan real} Nama : string {nilai yang merupakan kumpulan karakter} P : point{nilai pada bilangan kartesian} Cari : Boolean {suatu nilai logika}
{Nama fungsi , menyebutkan domain dan range} function RealToInt (x : real)
integer
{mengubah harga x yang bertype real menjadi harga ekivalen yang Bertype integer}
{Nama prosedur, menyebutkan “IS” initial state, “FS” final state dan proses} procedure tukar (input/output x,y : real) {IS x dan y terdefinisi, x = a dan y = b FS x = b dan y = a Prose : menukar isi informasi bilangan x dan y }
20
2.2.5.3 Algoritma (Pendeskripsian) Algoritma adalah bagian inti dari suatu algoritma yang berisi instruksi atau pemanggilan aksi yang telah didefinisikan. Komponen teks algoritma dalam pemrograma prosedural dapat berupa: •
Instruksi dasar, seperti input atau output atau assignment.
•
Sequence (rangkaian atau urutan).
•
Analisa kasus.
•
Perulangan.
Setiap langkah algoritma dibaca dari atas ke bawah. Urutan deskripsi penulisan menentukan urutan langkah pelaksanaan perintah.
2.3
Artificial Intelligence Dewasa ini Artificial Intelligence (AI) banyak menarik minat dan perhatian dari
masyarakat luas, tetapi apakah sebenarnya AI itu? Menurut Kusumadewi (2003, p1), AI adalah salah satu bagian ilmu komputer yang membuat agar komputer dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia. Pada awal diciptakannya, komputer hanya dipakai sebagai alat hitung saja, Namun, seiring dengan perkembangan zaman maka peran komputer semakin mendominasi kehidupan umat manusia. Manusia bisa menjadi pandai dalam menyelesaikan suatu persoalan karena manusia mempunyai pengetahuan dan disertai pengalaman. Pengetahuan diperoleh dari belajar.
Semakin banyak bekal pengetahuan yang dimiliki seseorang, maka orang
tersebut diharapkan dapat lebih mampu dalam menyelesaikan suatu persoalan. Agar komputer pun dapat bertindak seperti dan sebaik manusia, maka komputer juga harus
21 diberi bekal pengetahuan dan mempunyai kemampuan untuk berpikir. Pada AI, komputer dibekali beberapa metode yang diharapkan agar komputer dapat menjadi benda yang pintar.
2.3.1
Sejarah Artificial Intelligence Program AI pertama yang bekerja ditulis pada 1951, yang saat itu digunakan
untuk menjalankan mesin Ferranti Mark I di University of Manchester: yaitu sebuah program permainan yang ditulis oleh Christopher Strachey dan program permainan catur yang ditulis oleh Dietrich Prinz. John McCarthy membuat istilah “kecerdasan buatan” pada konferensi pertama yang disediakan untuk pokok persoalan ini pada 1956, John McCarthy juga menemukan bahasa pemrograman Lisp. Sedangkan Alan Turing memperkenalkan “Turing Test” sebagai sebuah cara untuk mengoperasionalkan tes perilaku cerdas. Joseph Weizenbaum membangun ELIZA, sebuah chatterbor yang menerapkan psikoterapi Rogerian. Selama tahun 1960-an dan 1970-an, Joel Moses mendemonstrasikan kekuatan pertimbangan simbolis untuk mengintegrasikan masalah dalam program Macsyma, program berbasis pengetahuan yang sukses pertama kali dalam bidang matematika. Marvin Minsky dan Seymour Papert menerbitkan Perceptrons, yang mendemosntrasikan batas jaringan syaraf sederhana dan Alain Colmerauer mengembangkan bahasa komputer Prolog. Ted Shortliffe mendemosntrasikan kekuatan sistem berbasis aturan untuk representasi pengetahuan dan inferensi dalam diagnosa serta terapi medis yang kadang kala disebut sebagai sistem pakar pertama. Hans Moravec mengembangkan kendaraan terkendali computer pertama yang dapat mengatasi jalan berlintang secara mandiri.
22 Pada tahun 1980-an, jaringan syaraf digunakan secara meluas dengan algoritma perambatan balik, yang pertama kali diterangkan oleh Paul John Werbos pada 1974. Di tahun 1990-an sebuah prestasi besar dalam bidang AI ditandai dengan munculnya Deep Blue, sebuah komputer pemain catur yang mengalahkan Garry Kasparov dalam pertandingan enam ronde yang terkenal pada tahun 1997. Perkembangan ini terus berlanjut hingga kini.
2.3.2 Definisi Artificial Intelligence •
Menurut Winston dan Prendergast (1984): “Kecerdasan buatan (Artificial Intelligence) adalah sebuah mesin yang lebih pintar, lebih bermamfaat dan dapat memahami apa itu kecerdasan”
•
Menurut H. A. Simon (1987): “Kecerdasan buatan (Artificial Intelligence) merupakan kawasan penelitian, aplikasi dan istruksi yang terkait dengan pemrograman komputer untuk melakukan sesuatu hal yang dalam pandangan manusia adalah cerdas.”
•
Menurut Rich and Knight (1991): “Kecerdasan buatan (Artificial Intelligence) merupakan sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan lebih baik oleh manusia.”
23 •
Menurut Kusumadewi (2003) “Kecerdasan buatan (Artificial Intelligence) adalah salah satu bagian ilmu komputer yang membuat agar komputer dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia.”
2.3.3
Bidang-Bidang Kecerdasan Buatan
a.
Sistem Pakar (Expert System) Sistem pakar adalah program komputer yang didesain untuk berlaku sebagai seorang ahli dalam suatu bidang khusus. Namun sekarang sistem pakar biasanya hanya digunakan untuk membantu para ahli dalam memecahkan suatu masalah.
b.
Natural Language Processing (NLP) Natural Language Processing adalah komputer yang dimaksudkan untuk mengenal makna dari bentuk kalimat berbeda-beda. Selain mampu mengerti bahasa sehari-hari, NLP juga mencakup kemampuan membentuk kalimat dalam bahasa sehari-hari.
c.
Pengenalan Pola (Recognition) Recognition adalah program komputer yang ditujukan untuk mengenali suatu objek. Contohnya dalam Speech Recognation, komputer dapat mengenali suara, dan sekaligus bias membedakan berbagai macam bentuk sinyal. Contoh lain dalam Character Recognation, komputer dapat mengenali karakter, sekaligus dapat membedakan berbagai macam bentuk karakter.
24 d.
Computer Vision Ilmu pengetahuan dan teknologi komputer yang berkaitan dengan pengolahan citra komputer seakan dapat melihat benda, terkait dengan teori untuk membangun suatu sistem yang terdiri dari gambar. Contoh yang sering digunakan adalah pendeteksian plat nomor kendaraan.
e.
Robotic Mesin yang diprogram untuk melakukan tugas-tugas mekanik, berintelegensi dan dapat member respon terhadap perubahan lingkungan. Contohnya adalah Asimo dan Aibo.
f.
Automatic Programming komputer yang dapat membuat program sendiri dan menyesuaikan dengan spesifikasi yang dinginkan oleh pemrogram.
g.
Planning and Decision Support Komputer yang memiliki kemampuan khusus untuk membantu manajer dalam membuat perancanaan dan pengambilan keputusan.
h.
Soft computing Soft Computing adalah koleksi dari beberapa metodologi yang bertujuan untuk mengeksploitasi adanya toleransi terhadap ketidaktepatan, ketidakpastian dan kebenaran parsial untuk dapat diselesaikan dengan mudah, kuat, dan biaya penyelesaiannya murah. Definisi ini pertama kali diungkapkan oleh Prof. Lofti A. Zadeh pada tahun 1992. Soft Computing merupakan inovasi baru dalam membangun sistem cerdas. Sistem cerdas ini merupakan sistem yang memiliki
25 keahlian seperti manusia pada domain tertentu, mampu beradaptasi dan belajar agar dapat bekerja lebih baik jika terjadi perubahan lingkungan. Unsur-unsur pokok dalam Soft Computing, adalah: 1.
Sistem Fuzzy (mengakomodasi ketidaktepatan)
2.
Jaringan Syaraf (menggunakan pembelajaran)
3.
Probabilistic Reasoning (mengakomodasi ketidakpastian)
4.
Evolutionary Computing (optimalisasi)
Keempat unsur tersebut bukan merupakan pesaing antara satu dengan yang lainya, namun diantaranya bisa saling melengkapi bahkan pada kenyataanya, biasanya unsur-unsur pokok tersebut akan digunakan secara sinergis daripada dikerjakan sendiri-sendiri.
Karakteristik soft Computing: a.
Soft Computing memerlukan keahlian manusia, apabila direpresentasikan dalam bentuk aturan (If-Then).
b.
Model komputasinya diilhami oleh proses biologis.
c.
Soft Computing merupakan teknik optimasi baru.
d.
Soft Computing menggunakan komputasi numeris.
e.
Soft Computing memiliki toleransi kegagalan (meskipun kualitasnya berangsur-angsur memburuk).
26 2.4
Algoritma Genetika (Genetic Algorithm) Algoritma Genetika adalah algoritma yang memanfaatkan proses seleksi alamiah
yang dikenal dengan proses evolusi. Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Dalam proses evolusi, individu secara terusmenerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. Pada dasarnya ada 4 kondisi yang sangat mempengaruhi proses evolusi, yaitu: a.
Kemampuan organisme untuk melakukan reproduksi.
b.
Keberadaan populasi organisme yang bisa melakukan reproduksi.
c.
Keberagaman organisme suatu populasi.
d.
Perbedaan kemampuan untuk bertahan. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu
melalui proses perkembang-biakan. Dalam Algoritma Genetika ini, proses perkembangbiakan ini menjadi proses dasar yang menjadi perhatian utama, dengan dasar berpikir: “Bagaimana mendapatkan keturunan yang lebih baik”.
Algoritma genetika ini
ditemukan oleh John Holland (1975) dari Universitas Michigan dan dikembangkan oleh muridnya David Goldberg. John Hollan mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami atau buatan) dapat diformulasikan dalam teminologi genetika.
2.4.1
Definis dalam Algoritma Genetika
Beberapa Definisi Penting Dalam Algoritma Genetika •
Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter.
27 •
Allele, nilai dari gen.
•
Kromosom, gabungan gen-gen yang membentuk nilai tertentu.
•
Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat
•
Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.
•
Generasi, menyatakan satu-satuan siklus proses evolusi.
•
Nilai Fitness, menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.
2.4.2 Tahapan dalam menggunakan Algoritma Genetika Hal-Hal Yang Harus Dilakukan Untuk Menggunakan Algoritma Genetika: •
Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
•
Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu atau baik-tidaknya solusi yang didapatkan.
•
Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk.
•
Menentukan proses seleksi yang akan digunakan.
•
Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akan digunakan
Algoritma
Genetika
pada
dasarnya
adalah
program
komputer
yang
mensimulasikan proses evolusi. Dalam hal ini populasi dari kromosom dihasilkan secara
28 random dan memungkinkan untuk berkembangbiak sesuai dengan hukum-hukum evolusi dengan harapan akan menghasilkan individu kromosom yang prima. Kromosom ini pada kenyataannya adalah kandidat penyelesaian dari masalah, sehingga bila kromosom yang baik berkembang, solusi yang baik terhadap masalah diharapkan akan dihasilkan.
Algoritma Genetika ini banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan. Algoritma ini dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimal dari satu variabel atau multi variabel. Sebelum algoritma ini dijalankan, masalah apa yang ingin dioptimalkan itu harus dinyatakan dalam fungsi tujuan, yang dikenal dengan fungsi fitness. Jika nilai fitness semakin kecil, maka solusi yang dihasilkan semakin baik. Walaupun pada awalnya semua nilai fitness kemungkinan sangat besar (karena algoritma ini menghasilkannya secara random), sebagian akan lebih baik dari yang lain. Kromosom dengan nilai fitness yang baik ini akan memberikan probabilitas yang tinggi untuk bereproduksi pada generasi selanjutnya. Sehingga untuk setiap generasi pada proses evolusi, fungsi fitness yang mensimulasikan seleksi alam, akan menekan populasi kearah fitness yang semakin kecil.
2.4.3
Struktur Algoritma Genetika
Algoritma genetika sangat tepat 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
29 (persilangan) dan operator mutasi. Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:
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 untuk berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain: •
Berhenti pada generasi tertentu.
•
Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah.
•
Berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.
30 2.5
Pemenuhan Konstrain (Constraint Satisfaction)
Constraint Satisfaction adalah suatu prosedur pencarian yang dioperasikan pada sekumpulan set-set pembatasan (Constraint) tertentu. Pertama-tama constraint ditemukan dan disebarkan sejauh mungkin kedalam sistem. Jika masih belum ditemukan solusi,maka akan dilakukan pencarian. Prosedur Pemenuhan Konstrain (Constraint Satisfaction) adalah sebagai berikut: •
Pilihlah sebuah simpul yang belum dikembangkan dalam graph pencarian.
•
Terapkan aturan-aturan inferensi pembatas (constraint) untuk simpul yang dipilih untuk menghasilkan semua pembatas baru yang dimungkinkan.
•
Jika sebuah pembatas berisi sebuah kontradiksi (pertentangan), maka laporkanlah bahwa lintasan ini terhenti.
•
Jika himpunan pembatas menggambarkan sebuah solusi yang lengkap, maka laporkanlah adanya kesuksesan.
•
Jika tidak ditemukan adanya kontradiksi atau solusi lengkap , maka solusisolusi parsial baru yang konsisten dengan himpunan pembatas saat ini. Sisipkan solusi-solusi parsial kedalam graph pencarian (search)
Contoh: initial state (pernyataan awal) SEND MORE --------------- + MONEY
31 Maka dapat diselesaikan dengan:
Gambar 2.3 Penjelesan Pemenuhan Konstrain
32 Keterangan: 1) Pada tahap ini terdapat 2 constraint yaitu 1 karakter mewakili 1 digit angka dan range angka dari 1 sampai dengan 9. 2) Setelah dilakukan perhitungan maka ditemukan bahwa nilai M = 1, sehingga konstrain bertambah menjadi 3. 3) Dapat diketahui bahwa nilai S bisa 8 atau 9 dan nilai O bisa 0 atau 1. 4) Didapat bahwa nilai S = 9 dan nilai O = 0, sehingga nilai konstrain bertambah menjadi 5. 5) Diketahui bahwa E = N - 1. 6) Nilai R = 8 atau 9 7) Didapat nilai R adalah 8, sehingga konstrain bertambah menjadi 6. 8) Diketahui bahwa nilai E = 5 atau 6. 9) Didapat bahwa nilai E = 5 sehingga konstrain bertambah menjadi 7. 10) Dari semua itu dapat diketahui bahwa nilai dari N = 6, D = 7 dan Y = 2.
Sehingga didapat jawaban yang benar adalah: S = 9; E = 5; N = 6; D = 7 ; M =1; O = 0; R = 8; Y = 2
