1. BEST
FIRST SEARCH
Best-First Search merupakan sebuah metode yang membangkitkan simpul dari simpul sebelumnya. Best-first search memilih simpul baru yang memiliki biaya terkecil diantara semualeaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n).fungsi evaluasi best-first search dapat berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut.
a. Ambil simpul terbaik yang ada di OPEN.
b. Jika simpul tersebut sama dengan goal,
maka sukses c. Jika
tidak, masukkan simpul tersebut ke dalam CLOSED d. Bangkitkan
semua aksesor dari simpul tersebut e. Untuk
setiap suksesor kerjakan:Sebagai contoh, pada Gambar 2.34
Jelas bahwa jalur melalui C selalu lebih baik daripada melalui B. Tetapi jika
biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B tidak
sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik.
Sebagai contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11
(10+1), dengan demikian biaya node A apabila memilih jalur lewat C adalah 12
(11+1). Tentu saja akan
lebih baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila
kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih
buruk lagi ketimbang jalur dengan melalui node C.
Pada setiap
langkah proses pencarian terbaik pertama, kita memilih node-node dengan
menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita
pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan
penggantinya. Fungsi heuristic merupakan suatu strategi untuk melakukan proses
pencarian ruang keadaan suatu problema secara selektif, yang memandu proses
pencarian yang kita lakukan sepanjang jalur yang memiliki kemungkinan sukses
paling besar.
Algoritma best-first search
Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan
dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya
paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian
harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B
paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan
selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai
ditemukan node tujuan. Ilustrasi algoritma best-first search dapat dilihat pada
gambar 3.4 dibawah ini.
Untuk mengimplementasikan algoritma pencarian
ini, diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-node yang
pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node
yang pernah dibangkitkan dan sudah dievaluasi. Algoritma selengkapnya adalah
sebagai berikut.
1. OPEN
berisi initial state dan CLOSED masih kosong.
2. Ulangi
sampai goal ditemukan atau sampai tidak ada di dalam OPEN.
i. Jika suksesor tersebut belum
pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat
parent.
ii. Jika suksesor tersebut sudah
pernah dibangkitkan, ubah parent-nyajika jalur melalui parent ini lebih baik
daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk
suksesor tersebut dn nodes lain yang berada di level bawahnya.
Algoritma yang menggunakan metode best-first
search, yaitu:
a. Greedy Best-First
Greedy Best-First adalah algoritma best-first
yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated
cost) saja, yakni f(n)
= h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan.
Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya,
maka algoritma ini menjadi tidak optimal.
b. A*
A* adalah algoritma best-first search yang
menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang
diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan.
Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan
perhitungan biaya seperti ini, algoritma A* adalahcomplete dan optimal.
2.PROBLEM REDUCTION
Problem reduction atau yang biasa dikenal dengan constraint,
intinya adalah berusaha mengurangi masalah dengan harapan masalah yang
bersangkutan menjadi lebih mudah diselesaikan. Sekarang ini sudah diketahui
teknik konsistensi ini sangat penting dalam penyelesaian constraint
satisfactionproblem yang sangat berat sehingga semua aplikasi komersial
penyelesaian constraint satisfactionproblem menggunakan teknik konsistensi ini
sebagai langkah dasar. Sejarah konsistensi constraint dapat ditlusuri dari peningkatan efisiensi
program pengenalan gambar oleh peneliti di intelejensi semu. Pegenalan gambar melibatkan pemberian label kepada semua garis
pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada
garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit
yang konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk
pembeian nilai yang konsisten.Untuk mengilustrasikan teknik konsistensi ini
akan diberikan sebuah contoh constraint satisfaction problem yang sangat
sederhana.
Walaupun teknik konsistensi ini jarang digunakan sendirian untuk
menghasilkan solusi, teknik konsistensi ini membantu menyelesaikan constraint
satisfactionproblem dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian
maupun pada saat pencarian.
Kebanyakan solusi menggunakan
pohonOR,dimana lintasan dari awal sampai tujuan tidak terletak pada satu
cabang. Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu
cabang, maka kita akan dapat menemukan tujuan lebih cepat.
Pada dasarnya sama dengan algoritma Best First Search, dengan
mempertimbangkan adanya arc AND. Gambar berikut menunjukkan bahwa untuk
mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal
mempunyai uang.Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk
biaya solusi.
3. CONSTRAINT SATISFACTION
Penjadwalan perkuliahan merupakan suatu hal yang sangat kompleks
dan rumit untuk dipecahkan. Kompleksitasnya dapat dilihat dari sisi mahasiswa,
dosen yang mengajar, mata kuliah yang diajarkan, waktu perkuliahan, dan juga
ruangan untuk melaksanakan perkuliahan tersebut. Kemungkinan-kemungkinan
tersebut sangat mempengaruhi kinerja keseluruhan aktifitas akademis dalam suatu
kampus yang akhirnya berdampak pada kompetensi kampus tersebut.
Dalam proses penjadwalan mata kuliah ada beberapa hal yang harus
diperhatikan. Pertama, terdapat jadwal-jadwal di mana dosen yang bersangkutan
tidak bisa mengajar. Kedua, distribusi jadwal perkuliahan diharapkan dapat
merata tiap harinya untuk setiap kelas. Ketiga, pekerjaan penjadwalan mata
kuliah ini akan semakin berat jika melibatkan semakin banyak kelas per
angkatannya. Keempat, terdapat mata kuliah tertentu yang menggunakan ruang
laboratorium yang harus dijadwalkan pada ruang laboratorium.
Karena itu dibutuhkan sebuah metode optimasi yang dapat
diterapkan untuk mengerjakan penjadwalan mata kuliah ini. Metode heuristik
biasanya menghasilkan solusi yang baik atau memecahkan masalah yang kompleks.
Namun, kesulitan utama dalam menggunakan metode heuristik adalah heuristik
bukanlah satu algoritma umum. Dalam pemecahan masalahnya metode ini mengabaikan
apakah solusi dapat dibuktikan benar atau tidak. Metode heuristik berfungsi
seperti algoritma tetapi tanpa jaminan optimalitas. Algoritma Genetika
merupakan salah satu algoritma yang tepat digunakan dalam menyelesaikan masalah
optimasi kompleks, yang sulit dilakukan oleh metode konvensional. Akan tetapi
Algoritma Genetika menerapkan proses heuristik, sehingga dibutuhkan metode lain
untuk membuat proses heuristik pada Algoritma Genetika menjadi terarah dan
membuat keseluruhan proses menjadi lebih efisien. Metode yang tepat untuk
dikombinasikan dengan Algoritma Genetika adalah Metode Constraint Satisfaction
Problem (CSP). Constraint Satisfaction Problem merupakan sebuah pendekatan
untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek
yang memenuhi sejumlah persyaratan atau kriteria.
Constraint Satisfaction Problem adalah suatu permasalahan
seseorang harus mencari nilai untuk set variabel (finite) yang memenuhi set
constraint (finite). Komponen-komponen yang terdapat pada Constraint
Satisfaction Problem adalah Variabel yang merupakan penampung dapat diisi
berbagai nilai, Constraint yang merupakan suatu aturan yang ditentukan untuk
mengatur nilai boleh diisikan ke variabel, atau kombinasi variable, Domain yang
merupakan kumpulan nilai legal dapat diisi ke variable, Solusi yang merupakan assignment
nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar.
Constraint Satisfaction Problem
dimulai dari solusi kosong dan diakhiri dengan sebuah solusi yang memenuhi
semua constraint (consistent). Pencarian solusi dilakukan dengan mencoba
mengisi nilai domain pada setiap variabel satu demi satu tanpa melanggar
constraint, sampai solusi ditemukan. Algoritma
yang paling banyak dipakai untuk melakukan pencarian sistematik untuk
menyelesaikan Constraint Satisfaction Problem adalah backtracking. Algoritma
backtracking search (penelusuran kembali) adalah suatu bentuk algoritma
depth-first-search. Backtracking dapat dilihat sebagaimana searching dalam
tree, karena setiap node mewakili state dan turunan dari setiap node mewakili ekstensi
dari state tersebut.
Pada metode backtracking, variabel diisi secara sequential
selagi semua variabel relevan dengan constraint yang sudah diinisialisasi. Jika
solusi partial melanggar constraint, backtracking melakukan langkah kembali ke
solusi partial sebelumnya dan memilih nilai lain yang belum dicoba untuk
variabel yang ingin diisikan. Langkah tersebut berguna untuk menghindari
eksplorasi lebih lanjut dari solusi partial yang salah. Keuntungan backtracking
adalah pemeriksaan consistency hanya perlu dilakukan terhadap assignment yang
terakhir dilakukan karena pemeriksaan terhadap assignment yang sebelumnya sudah
dilakukan sebelumnya.
Pada algoritma backtracking, teknik look ahead digunakan untuk
meramalkan efek pemilihan variabel branching untuk mengevaluasi nilai-nilai
variabel tersebut. Forward checking adalah salah satu cara untuk melakukan look
ahead. Forward checking mencegah terjadinya konflik dengan melarang nilai-nilai
yang belum diisikan ke variable untuk dipakai. Ketika suatu nilai diisikan ke
suatu variabel, nilai yang berada di domain dari variabel yang konflik dengan
assignment tersebut akan dihilangkan dari domain.
Minimum Remaining Value (MRV) adalah suatu teknik yang
dikembangkan untuk menangani masalah kemungkinan besar gagal pada pencarian
menggunakan Constraint Satisfaction Problem. Minimum Remaining Value berkerja
dengan memilih variabel yang memiliki domain legal dan paling sedikit (memiliki
kemungkinan untuk membuat suatu dead-end paling besar) untuk diisikan terlebih
dulu.
Algoritma Genetika pada dasarnya adalah program komputer yang
mensimulasikan proses evolusi. Algoritma Genetika juga merupakan algoritma yang
berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas
pemecahan masalah (problem solving). Pendekatan yang diambil oleh algoritma ini
adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di
dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu
pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness.
Algoritma Genetika bekerja menggunakan kode dari parameter yang
menjadi permasalahan. Parameter problem tersebut dikodekan menjadi sebuah
kromosom. Setiap kromosom terdiri dari bagian-bagian yang disebut gen. Gen-gen
ini dapat berupa angka biner (‘1’ dan ‘0’), sehingga kromosom yang terbentuk
merupakan sebuah deretan string biner. Pencarian solusi pada algoritma ini melibatkan
sejumlah populasi dari titik-titik pada ruang parameter. Setiap titik tersebut
disebut individu. Variable dan parameter yang digunakan yaitu fitness (nilai
hasil evaluasi Objective Function yang dipakai untuk tolak ukur kualitas
kromosom) untuk menentukan tingkat kesesuaian suatu individu dengan kriteria
yang ingin dicapai, populasi jumlah individu per generasi, probabilitas
terjadinya crossover pada suatu generasi, probabilitas terjadinya mutasi, serta
banyaknya generasi yang dilibatkan.
4. MEANS AND ANALYSIS
Means-Ends Analysis terdiri dari tiga unsur kata yakni; Mean, End
dan Analysis. Mean menurut bahasa yakni berarti, banyaknya cara. Sedangkan End
adalah akhir atau tujuan, dan Analysis berarti analisa atau penyelidikan secara
sistematis.
Means-Ends Analysis pertama kali diperkenalkan oleh Newell dan
Simon (wikipedia, 2007) dalam General Problem Solving (GPS), yang menyatakan
bahwa Means-Ends Analysis adalah suatu teknik pemecahan masalah di mana
pernyataan sekarang dibandingkan dengan tujuan, dan perbedaan di antaranya
dibagi ke dalam sub-subtujuan untuk memperoleh tujuan dengan menggunakan
operator yang sesuai.
http://mitraikhtiar.blogspot.co.id/2013/03/mean-ends-analisys-mea.html
Tidak ada komentar:
Posting Komentar