8

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 angka-

angka 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

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 angka-

angka 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.

• Alas permainan kotak 16 x 16 dengan wilayah hexudoku.

2.2 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 :

• Mengerti setiap langkah dalam algoritma

• Mengerjakan operasi yang sesuai dengan langkah tersebut.

2.2.1 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 variable-

variabel 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 :

Catatan :

Untuk memisahkan antara kata dalam judul algoritma menggunakan tanda “_”

bukanlah suatu keharusan. Anda dapat menuliskan LuasLingkarang atau

Luas_Lingkaran. Tetapi sebaiknya anda tidak menggunakan spasi “ ” untuk

memisahkan antara kata didalam algoritma.

Program Luas_Kubus {Judul Algoritma}

{Menghitung luas kubus untuk ukuran sisi yang dibaca dari piranti masukan

lalu mencetak hasil ke piranti keluaran} {Spesifikasi 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 : <hh,mm,ss : integer> {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 terus-

menerus 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 perkembang-

biakan 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 solusi-

solusi parsial baru yang konsisten dengan himpunan pembatas saat ini.

Sisipkan solusi-solusi parsial kedalam graph pencarian (search)

Contoh: initial state (pernyataan awal)

S E N D M O R E

--------------- + M O N E Y

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