BAB 2 LANDASAN TEORI
2.1
Kecerdasan Buatan Menurut Rich dan Knight (1991, p1), artificial intelligence atau sering disebut
dengan kecerdasan buatan, merupakan suatu proses belajar mengenai cara membuat komputer melakukan hal-hal yang pada saat itu dapat dilakukan lebih baik oleh manusia. Dari pengertian di atas dapat disimpulkan bahwa komputer dapat mengantikan manusia dalam berbagai hal, tetapi bukan dalam semua hal seperti halnya pengambilan keputusan, karena bagaimana pun juga keputusan tetap ada di tangan manusia. Menurut Sri Kusumadewi (2003), kecerdasan buatan jika dibandingkan dengan kecerdasan alami memiliki beberapa keuntungan, antara lain : a. Kecerdasan buatan lebih bersifat permanen dan konsisten, karena kecerdasan alami hanya bergantung kepada ingatan manusia, yang mungkin saja menjadi lupa pada waktu tertentu. Sedangkan kecerdasan buatan bergantung pada sistem komputer dan program dari aplikasi kecerdasan buatan tersebut, sehingga selama aplikasi dan sistem komputer tidak berubah maka kecerdasan buatan tersebut tidak akan berubah. b. Kecerdasan buatan lebih mudah diduplikasi dan disebarkan karena berupa sistem, sehingga dengan mudah memindahkan pengetahuan yang ada pada sistem tersebut dari suatu komputer ke komputer lain. Sedangkan kecerdasan alami sulit diduplikasi karena menyampaikan pengetahuan dari satu orang ke orang lain lebih sulit untuk dilakukan. Selain membutuhkan proses yang 8
9 sangat lama, juga diperlukan suatu keahlian khusus untuk menyampaikannya dan tidak semua orang dapat menyampaikan hal yang sama persis dari satu orang ke orang lain. c. Kecerdasan buatan lebih murah dan cepat dibandingkan dengan kecerdasan alami. Menyediakan layanan komputer akan lebih mudah dan lebih murah dibandingkan harus mendatangkan seseorang untuk mengerjakan sejumlah pekerjaan dalam jangka waktu yang lama. d. Kecerdasan buatan dapat didokumentasikan dengan mudah. Keputusan yang dibuat oleh komputer dapat didokumentasikan lebih mudah dengan cara melacak setiap aktivitas dari sistem tersebut. Sedangkan kecerdasan alami sulit didokumentasikan karena manusia selalu berubah dan sulit untuk melacak setiap aktivitas yang berhubungan dengan kasus yang sedang dikerjakan serta membutuhkan waktu lama dalam pelacakan tersebut.
Sedangkan kecerdasan alami memiliki beberapa keuntungan sebagai berikut : a. Kercerdasan alami bersifat kreatif yaitu kemampuan untuk berkreasi yang yang melekat pada manusia. Kecerdasan buatan belum mampu berkreasi sendiri. b. Kecerdasan alami memungkinkan manusia untuk menggunakan pengalaman secara langsung. Sedangkan kecerdasan buatan bekerja berdasarkan input yang dimasukkan oleh pengguna dan bentuk dari inputan tersebut berupa kode – kode tertentu yang telah ditentukan pada awal pembuatan sistem.
Dari dahulu hingga sekarang, kecerdasan buatan terus berkembang pesat dari
10 mulai perhitungan sampai dengan pembuatan robot yang intinya kecerdasan buatan adalah membuat komputer lebih cerdas. Sampai sekarang kecerdasan buatan memiliki berbagai macam cabang ilmu seperti expert system, neural network, fuzzy logic dan machine learning. Expert system (sistem pakar) adalah sistem yang berusaha mengadopsi pengetahuan manusia ke dalam komputer agar komputer dapat menyelesaikan masalah seperti yang biasa dilakukan oleh para ahli (Luger, 2002, p20). Sistem pakar yang baik dirancang agar dapat menyelesaikan suatu permasalahan tertentu dengan meniru kerja dari para ahli. Dengan sistem pakar, orang awam pun dapat menyelesaikan masalah yang cukup rumit yang sebenarnya hanya dapat diselesaikan dengan bantuan para ahli. Sistem pakar memiliki beberapa keuntungan dan kerugian, keuntungan dari sistem pakar antara lain : a. Memungkinkan orang awam dapat mengerjakan pekerjaan yang hanya dapat diselesaikan dengan bantuan para ahli b. Dapat melakukan proses secara berulang secara otomatis c. Menyimpan pengetahuan dan keahlian para pakar yang dijadikan dasar dari pembuatan sistem d. Mampu menyimpan dan mendokumentasikan keahlian para pakar e. Memiliki kemampuan untuk bekerja dengan informasi yang tidak lengkap dan mengandung ketidakpastian f. Menghemat waktu dalam proses pengambilan keputusan
11 Sedangkan kerugian yang dimiliki oleh sistem pakar yaitu : a. Biaya yang diperlukan untuk membuat dan memelihara sistem pakar yang ada membutuhkan biaya yang cukup mahal b. Sulit untuk dikembangkan karena sulitnya mendapatkan ketersediaan pakar yang ahli di bidangnya
Contoh dari sistem pakar adalah alat pendeteksi penyakit dalam bidang kedokteran dimana pengetahuan dokter ditransfer ke dalam komputer oleh programmer sehingga menghasilkan suatu aplikasi yang memiliki kecerdasan hampir setara dengan dokter tersebut. Machine learning digunakan oleh sistem untuk melakukan adaptasi terhadap lingkungan yang berubah-ubah, mendeteksi serta mengekstrapolasi pola - pola (Russel dan Norvig, 2003, p3). Sistem yang dihasilkan dapat secara terus menerus melakukan peningkatan ,oleh karena itu meningkatkan efisiensi serta efektivitas. Fuzzy logic dikembangkan oleh Lotfi Zadeh dari University of California. Fuzzy logic merupakan sebuah logika yang memiliki banyak nilai, yang memungkinkan pendefinisian nilai intermediate diantara penilaian yang konfensional seperti ya/tidak benar/salah, hitam/putih. Nilai seperti agak hangat atau sangat dingin dapat diformulasikan secara matematis dan diproses oleh computer. Neuron merupakan sebuah sel pada otak yang berfungsi untuk mengumpulkan, memproses dan penyebaran dari sinyal elektrik. Kemampuan otak untuk memproses informasi digagaskan muncul dari sebuah jaringan (network) dari neuron -neuron tersebut. Untuk alasan tersebut, kecerdasan semu bertujuan untuk membuat jaringan syaraf tiruan (artificial neural network) (Russel dan Norvig, 2003, p736). Neural
12 network banyak digunakan dalam aplikasi untuk mengenali pola pada objek, seperti alikasi pengenalan sidik jari, tanda tangan dan pengenalan wajah. Seperti artificial neural network, analogi biologis sedikit banyak juga telah mempengaruhi algoritma machine learning. Algoritma untuk pembelajaran mengikuti proses yang terjadi dalam evolusi yaitu membentuk sebuah populasi dari individu individu melalui proses survival dari anggota-anggotanya (Luger, 2002, p469). Keampuhan seleksi pada suatu populasi dari individu – individu yang bervariasi telah didemonstrasikan oleh pembentukan spesies - spesies baru pada proses evolusi alam. Ini telah dipelajari melalui penelitian - penelitian dalam cellular automata, algoritma genetika, genetic programming dan bentuk-bentuk lain dari komputasi yang mulai berkembang.
2.2
Algoritma Genetika Algoritma genetika merupakan algoritma pencarian yang berdasarkan pada cara
kerja seleksi alam dan ilmu genetika (Goldberg, 1989, p1). Algoritma genetika pertama kali dikembangkan oleh John Holland dari Universitas Michigan pada tahun 1975. John Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan)
dapat diformulasikan dalam terminologi genetika. Algoritma genetika
merupakan simulasi dari proses evolusi Darwin dan operasi genetika atas kromosom. Algoritma genetika mengimplementasikan bentuk yang baik, memelihara banyak solusi, membuang solusi yang tidak menjanjikan dan meningkatkan solusi yang baik. Setelah beberapa generasi, solusi yang dihasilkan akan semakin baik kualitasnya (Luger, 2002, p479). Tidak semua solusi yang buruk langsung dibuang, tetapi solusi yang buruk pun dapat memberikan kontribusi untuk solusi yang akan datang dengan bantuan
13 operator genetika. Fitness dari suatu individu adalah nilai dari suatu fungsi objektifitas dari suatu individu (Sivanandaman & Deepa, 2008, p56). Untuk menghitung nilai fitness awalnya kromosom harus di-decode pertama dan fungsi objektifnya harus dievaluasi. Fitness tidak hanya diindikasikan untuk suatu solusi yang bagus tapi juga mengkorespondensi bagaimana kromosom mendekati nilai optimal. Tiga tahapan pemecahan masalah algoritma genetika menurut Luger (2002, p470) yaitu : a. Individu yang berpotensi sebagai solusi dari permasalahan tersebut diubah (encode) ke dalam representasi data yang mendukung variasi yang dibutuhkan serta operator seleksi b. Algoritma mating dan mutasi yang menganalogikan aktivitas seksual dari bentuk kehidupan biologis, menghasilkan generasi baru dari individu individu yang mengkombinasikan fitur - fitur dari orang tua mereka c. Fungsi fitness digunakan untuk menentukan individu-individu mana yang terbaik, yang cocok sebagai solusi atas permasalahan yang diberikan.
Prinsip dari GA menurut Jean-Philippe Rennard (2000) adalah : a. Encoding masalah ke string binary b. Buat populasi secara acak yang terdiri dari kolam genetika untuk mewakili sekumpulan solusi yang memungkinkan c. Tentukan nilai fitness untuk tiap subyek yang secara langsung bergantung pada jaraknya ke nilai optimum d. Seleksi subyek yang akan dikawinkan sesuai bagian mereka dalam nilai
14 global fitness populasi e. Crossover dan mutasi genom f. Ulangi lagi dari langkah 3 hingga didapat hasil optimum.
2.2.1 Operator – Operator Algoritma Genetika Jalannya algoritma genetika sangat dipengaruhi oleh operator-operator yang digunakan (Marczyk, 2004). Operator-operator itu meliputi pengkodean kromosom, crossover, mutasi dan seleksi. a. Pengkodean kromosom Kromosom merupakan salah satu solusi yang diinginkan dari beberapa solusi yang mungkin ada dan ditulis dalam bentuk kode –kode. Tipe pengkodean (encoding) yang sering digunakan adalah string biner. Contoh kromosom yang di-encoding dengan menggunakan string biner : Kromosom A
:
110010101100
Kromosom B
:
101001010011
Setiap kromosom memiliki satu string biner. Setiap bit dari string ini mewakili karakteristik dari solusi atau dapat juga seluruh kromosom mewakilkan satu angka. Encoding tidak hanya dapat dilakukan dengan string biner tetapi juga dengan bilangan real. b. Seleksi Proses seleksi dilakukan untuk memilih beberapa kromosom berdasarkan fitness value-nya. Kromosom hasil seleksi nantinya akan digunakan sebagai orang tua dalam proses penyilangan dan mutasi. Elitism adalah metode seleksi dimana satu atau lebih kromosom dengan fitness value tertinggi
15 langsung disalin ke generasi berikutnya tanpa mengalami manipulasi. Hal ini dilakukan untuk mencegah kromosom - kromosom terbaik hilang karena proses crossover dan mutasi sehingga kualitas generasi berikutnya dapat membaik. c. Crossover (Rekombinasi) Crossover adalah proses pertukaran atau penyilangan satu atau lebih gen antara suatu kromosom dengan kromosom yang lain sehingga menghasilkan dua kromosom baru. Crossover dapat menggunakan representasi biner dan representasi permutasi. Crossover untuk representasi biner memiliki dua cara yaitu one point crossover dan two point crossover. One point crossover adalah penyilangan pada satu titik secara acak yang digambarkan sebagai berikut: Kromosom orang tua : Kromosom A
:
110010 | 101100
Kromosom B
:
101001 | 010011
Kromosom A
:
110010010011
Kromosom B
:
101001101100
Kromosom anak:
Pada two points crossover akan dipilih dua titik penyilangan secara acak. Dari dua titik penyilangan tersebut, satu titik akan menjadi titik awal penyilangan dan titik lainnya akan menjadi titik akhir penyilangan. Two points crossover digambarkan sebagai berikut:
16 Kromosom orang tua: Kromosom A
:
1100 | 1010 | 1100
Kromosom B
:
1010 | 0101 | 0011
Kromosom A
:
110001011100
Kromosom B
:
101010100011
Kromosom anak :
Crossover untuk representasi permutasi yaitu menggunakan order crossover, pada metode ini diambil secara acak bagian kromosom untuk dipertukarkan, tetapi urutan gen yang bukan bagian dari kromosom pertukaran tersebut tetap dijaga urutannya. Berikut ilustrasi dari rekombinasi menggunakan order crossover :
Gambar 2.1 Kromosom Awal dan Kromosom Baru Hasil Crossover
Pada gambar 2.1, kolom yang berwarna kuning pada kromosom awal dan kromosom baru menunjukan sebagian kromoson yang tidak berubah ketika crossover, tetapi dijadikan sebagai patokan dalam melakukan crossover. Tetapi isi kromosom awal dan kromosom baru berbeda yang terdapat pada kolom – kolom berwarna putih. Langkah – langkah pembentukan kromosom baru tersebut adalah sebagai berikut :
17
Gambar 2.2 Proses Pembentukan Kromosom dengan Metode Order Crossover
Pada kromosom awal (kromoson orang tua) dilakukan random untuk mencari bagian yang menjadi gen tetap selama proses pertukaran. Bagian gen yang didapat pada gambar 2.2 ditunjukkan dengan kolom- kolom berwarna kuning. Selanjutnya bagian gen yang ditunjuk dengan warna kolom kuning tersebut akan menjadi bagian gen anak – anaknya(kromosom – kromosom baru). Kromosom anak 1 berasal dari bagian gen orang tua satu, kromosom anak 2 berasal dari bagian gen orang tua 2.
18 Lalu anak 1 disilangkan dengan kromosom orang tua 2, dan anak 2 disilangkan dengan kromosom orang tua 1. Pada gambar 2.2 ditunjukkan dengan panah biru yang saling menyilang. Kromosom anak 1 akan ditambah dengan kromosom orang tua 2, penambahan dimulai dari kolom berwarna biru pada gambar 2.2, setiap kolom diperiksa apakah gen tersebut sudah terdapat pada kromosom anak, apabila ada maka ditandai dengan warna merah dan gen tersebut tidak dimasukkan ke dalam kromosom anak lalu dilanjutkan dengan kolom berikutnya, apabila gen pada kolom berikutnya tidak terdapat gen yang sama pada kromosom anak, maka gen tersebut disalin ke dalam kromosom anak pada kolom berikutnya setelah kolom terisi. Begitu seterusnya sehingga semua kolom anak terisi. Langkah yang sama juga dilakukan untuk pengisian kolom pada kromosom anak 2. Setelah semua kolom terisi maka terbentuklah kromosom baru hasil rekombinasi menggunakan metode order crossover. d. Mutasi Mutasi adalah proses perubahan satu atau lebih gen dalam suatu kromosom. Gen yang akan mengalami mutasi ditentukan secara acak atau mutasi gen (Luger,. 2002, 473). Pada mutasi acak, gen yang mengalami mutasi akan diganti dengan gen lain dimana gen pengganti tersebut dipilih secara acak. Mutasi acak digambarkan sebagai berikut : Kromosom awal
:
110001011100
Kromosom hasil mutasi
:
110000011100
Mutasi pada representasi permutasi harus menghasilkan kromosom yang dapat digunnakan. Sehingga, proses mutasi dilakukan dengan suatu cara
19 tertentu yang menjamin kromosom hasil mutasi tetap dapat digunnakan. Salah satu cara yang digunakan adalah mutasi pertukaran atau lebih dikenal dengan swap mutation. Pada mutasi pertukaran, dipilih dua posisi gen secara acak. Kemudian tukarkan gen pada kedua posisi tersebut. Mutasi pertukaran digambarkan sebagai berikut :
2.3
Kromosom awal
:
163982754
Kromosom hasil mutasi
:
168932754
Basis Data Basis data (database) adalah kumpulan data yang berelasi secara logika beserta
deskripsi data tersebut yang didesain untuk memenuhi kebutuhan informasi dari organisasi (Connolly, 2002). Perangkat lunak yang digunakan untuk memanggil dan memanipulasi kumpulan data tersebut disebut Database Management System (DBMS). DBMS
adalah
sistem
software
yang
memungkinkan
pengguna
untuk
mendefinisikan, membuat, memelihara database dan menyediakan akses kontrol terhadap database yang bersangkutan. Adapun fasilitas – fasilitas yang disediakan DBMS, antara lain : a. Data Definition Language (DDL) Memungkinkan pengguna untuk mendeklarasikan tipe data, struktur dan batasan – batasan data (constraint). b. Data Manipulation Language (DML) Memungkinkan pengguna untuk memanipulasi data seperti insert, update, delete dan retrieve data pada database.
20 c. Mengontrol akses pada database Kontrol akses pada database meliputi sistem keamanan, sistem integritas data, sistem kontrol konkurensi, sistem kontrol recovery dan katalog hak akses user. d. Mekanisme view Menampilkan data - data yang diperlukan dan digunakan berdasar pada permintaan pengguna (user requirement).
2.3.1
Entity Relationship Diagram Entitas adalah kata benda yang mempresentasikan bentuk nyata, misalnya
“buku”, “penjual”, ”nasabah”, atau sebagai abstraksi seperti “pemesanan”, “rincian pemesanan” dan lainnya dalam terminologi softwere engineering. Jadi Entity Relationship Diagram (ERD) adalah diagram yang menunjukkan hubungan antara para entitas. Sebagai contoh hubungan antara entitas karyawan dan mobil dan dinyatakan dalam kotak :
Karyawan
Mobil
Gambar 2.3 Contoh Hubungan Antar Entitas
Kardinalitas adalah batasan untuk relationship yang menyatakan berapa banyak entitas mempunyai relasi satu dengan yang lain. Sebagai contoh : •
Karyawan dapat tidak mempunyai mobil (kardinalitas bernilai 0);
21 •
Karyawan mempunyai 1 mobil (kardinalitas bernilai 1);
•
Karyawan mempunyai lebih dari 1 mobil (kerdinalitas bernilai n).
Untuk menentukan berapa banyak, tergantung atas kondisi nyata atau disebut aturan bisnis yang ada. Gambar berikut mengekspresikan hubungan antara seorang karyawan memiliki 0 mobil dan seorang karyawan memiliki banyak mobil:
Karyawan
Mobil Karyawan memiliki
Gambar 2.4 Contoh Hubungan Antar Entitas Menyatakan 0 dan Banyak
Gambar berikut mengekspresikan hubungan antara setiap mobil dimiliki oleh satu orang saja
Karyawan memiliki
Mobil
Karyawan
Dimiliki oleh Gambar 2.5 Contoh Hubungan Entitas Satu dan 0 atau Banyak
2.4
SQL Server 2000 Structure Query Language (SQL) adalah sebuah contoh dari transform-oriented
language
atau
sebuah
bahasa
yang
didesain
untuk
menghubungkan
dan
mentransformasikan input ke output yang dibutuhkan. Sebagai sebuah bahasa, standar
22 ISO SQL mempunyai dua komponen utama yaitu Data Definition Language (DDL) dan Data Manipulation Language (DML) (Connolly 2005, p113). SQL Server 2000 adalah Relational Database Managemet Systems (RDBMS) yang menggunakan bahasa Transact – SQL (T-SQL) untuk menerima request dari SQL – Client atau dari SQL – Server 2000 lainnya.
RDBMS bertanggung
jawab atas konsistensi database, yaitu dengan
melakukan hal – hal berikut: a. Menjaga hubungan antar data b. Data tersimpan secara konsisten sesuai dengan aturan yang telah didefinisikan dan aturan tersebut tidak terlanggar c. Mampu mengembalikan kondisi database ke posisi dimana pada posisi tersebut database dalam keadaan konsisten, terutama bila di tengah proses transaksi terjadi kegagalan atau crash.
Sistem yang mendukung untuk SQL SERVER 2000 dijalankan adalah: a. Kompatibel dengan sistem keamanan dan fasilitas enkripsi dari Windows NT Server dan Windows 2000 b. Layanan data terintegrasi dengan Windows Web Server dan Internet Information Services (ISS) c. Bersama dengan Site – Server dapat membentuk situs Web untuk e – Commerce
23 d. Socket TCP/IP dari SQL SERVER 2000 dapat berkomunikasi dengan Microsoft Proxy Server dan Microsoft Internet Security dan Acceleration Server (ISA – Server 2000)
2.5
Penjadwalan Permasalahan penjadwalan merupakan masalah yang rumit karena adanya
batasan - batasan terhadap sumber daya yang tersedia (Russel dan Norvig, 2003, p420). Edmund K. Burke, et al mendefinisikan penjadwalan (timetabling) sebagai sebuah set dari serangkaian peristiwa - peristiwa (sebagai contoh: ujian, perkuliahan, penerbangan) terhadap suatu alur waktu, sehingga tidak ada orang atau sumber daya yang berada lebih dari satu lokasi pada waktu yang sama dan terdapat cukup ruang tersedia pada tiap lokasi untuk sejumlah orang yang diharapkan. Permasalahan penjadwalan di lembaga pendidikan khususnya perkuliahan merupakan masalah yang sangat kompleks untuk diselesaikan, karena banyak hal yang perlu dibenahi, seperti halnya pembuatan jadwal yang memiliki banyak komponen – seperti mata kuliah yang diajarkan, pengajar, mahasiswa, ruangan yang dipakai, dan waktu pengajaran yang tepat. Semua itu harus disusun secara rapi, dan tidak ada konflik yang terjadi sehingga proses pengajaran dapat berjalan dengan baik. Para proses penyusunan jadwal biasanya dilakukan penyusunan secara manual, sehingga membutuhkan banyak waktu dalam proses penyusunan tersebut apalagi pada universitas berskala besar. Mereka harus mensinkronisasikan antara mata kuliah, pengajar, ruang, waktu, dan mahasiswa. Masalah tersebut pasti terjadi dan terus berulang, yaitu pada saat pergantian semester perkuliahan. Mereka harus menyusun ulang jadwal yang diperlukan untuk proses belajar – mengajar pada semester berikutnya,
24 karena setiap pergantian semester, jumlah mata kuliah, pelajaran yang akan diajarkan, dan jumlah dosen yang mengajar tidak sama dengan semester sebelumnya. Meskipun rumit untuk skala pendidikan terutama universitas yang memiliki skala yang besar, penjadwalan sangatlah dibutuhkan agar perkuliahan dapat berjalan dengan baik dan terencana sehingga dapat berhasil mencapai tujuan yang ingin dicapai. Dengan kata lain, penjadwalan sangatlah penting karena meskipun sulit dan rumit dalam pembuatannya, penjadwalan harus dibuat secara berkala dan teratur.
