Tugas Makalah Perbandingan 3 Jurnal SIG

 

Nama                          : SITI FITRIANAH

NIM                            : 18.01.013.120

Mata Kuliah                : Sistem Informasi Geografis

Dosen  Pengampu       : Nawassyarif, S.Kom.,M.Pd

Link UTS                    : www.uts.ac.id

Facebook Nusa Baca   : https://www.facebook.com/nusa.baca.18 

 

SILAHKAN DOWNLOAD DISINI !

DOWNLOAD

Resume Video 3 : Mechine learning

 RESUME VIDEO PEMBELAJARAN 3
MECHINE LEARNING
SITI FITRIANAH (18.01.013.120)

ALGORITMA K-NN

1. Apa itu K-NN?

Algoritma K-Nearest Neighbor (K-NN) adalah sebuah metode klasifikasi terhadap sekumpulan data berdasarkan pembelajaran data yang sudah terklasifikasikan sebelumya. Termasuk dalam supervised learning, dimana hasil query instance yang baru diklasifikasikan berdasarkan mayoritas kedekatan jarak dari kategori yang ada dalam K-NN.

K-Nearest Neighbor atau yang sering disingkat dengan KNN adalah salah satu algoritma yang digunakan untuk melakukan klasifikasi terhadap objek berdasarkan dari data pembelajaran (data training) yang jaraknya paling dekat dengan objek tersebut. Tujuan dari algoritma KNN adalah mengklasifikasikan objek baru berdasarkan atribut dan sampel-sampel dari data training.

KNN adalah algoritma supervised learning yang maksudnya algoritma ini menggunakan data yang telah ada dan outputnya telah diketahui. KNN banyak dipergunakan pada aplikasi data mining, pattern recognition, image processing, dll.

2. Tahapan Langkah Algoritma K-NN

a. Menentukan parameter k (jumlah tetangga paling dekat).

b. Menghitung kuadrat jarak eucliden objek terhadap data training yang diberikan.

c. Mengurutkan hasil no 2 secara ascending (berurutan dari nilai tinggi ke rendah)

d. Mengumpulkan kategori Y (Klasifikasi nearest neighbor berdasarkan nilai k)

e. Dengan menggunakan kategori nearest neighbor yang paling mayoritas maka dapat dipredisikan kategori objek.

3. Kelebihan dan Kekurangan dari Algoritma K-NN

a. Kelebihan

 Sangat nonlinear

KNN merupakan salah satu algoritma (model) pembelajaran mesin yang bersifat nonparametrik. Pembahasan mengenai model parametrik dan model nonparametrik bisa menjadi artikel sendiri, namun secara singkat, definisi model nonparametrik adalah model yang tidak mengasumsikan apa-apa mengenai distribusi instance di dalam dataset. Model nonparametrik biasanya lebih sulit diinterpretasikan, namun salah satu kelebihannya adalah garis keputusan kelas yang dihasilkan model tersebut bisa jadi sangat fleksibel dan nonlinear.

 Mudah dipahami dan diimplementasikan

Dari paparan yang diberikan dan penjelasan cara menghitung jarak dalam artikel ini, cukup jelas bahwa algoritma kNN mudah dipahami dan juga mudah dimplementasikan. Untuk mengklasifikasi instance x menggunakan kNN, kita cukup mendefinisikan fungsi untuk menghitung jarak antar-instance, menghitung jarak x dengan semua instance lainnya berdasarkan fungsi tersebut, dan menentukan kelas x sebagai kelas yang paling banyak muncul dalam k instance terdekat.

b. Kekurangan

 Perlu menunjukkan parameter K (jumlah tetangga terdekat)

 Tidak menangani nilai hilang (missing value) secara implisit

Jika terdapat nilai hilang pada satu atau lebih variabel dari suatu instance, perhitungan jarak instance tersebut dengan instance lainnya menjadi tidak terdefinisi. Bagaimana coba, menghitung jarak dalam ruang 3-dimensi jika salah satu dimensi hilang? Karenanya, sebelum menerapkan kNN kerap dilakukan imputasi untuk mengisi nilai-nilai hilang yang ada pada dataset. Contoh teknik imputasi yang paling umum adalah mengisi nilai hilang pada suatu variabel dengan nilai rata-rata variabel tersebut (mean imputation).

 Sensitif terhadap data pencilan (outlier)

Seperti yang telah dijelaskan Ali pada artikel sebelumnya, kNN bisa jadi sangat fleksibel jika k kecil. Fleksibilitas ini mengakibatkan kNN cenderung sensitif terhadap data pencilan, khususnya pencilan yang terletak di “tengah-tengah” kelas yang berbeda. Lebih jelasnya, perhatikan ilustrasi di bawah. Pada gambar kiri, seluruh instance bisa diklasifikasikan dengan benar ke dalam kelas biru dan jingga. Tetapi, ketika ditambahkan instance biru di antara instance jingga, beberapa instance jingga menjadi salah terklasifikasi.Perlu dipilih k yang tepat untuk mengurangi dampak data pencilan dalam kNN.

 Rentan terhadap variabel yang non-informatif

Meskipun kita telah menstandardisasi rentang variabel, kNN tetap tidak dapat mengetahui variabel mana yang signifikan dalam klasifikasi dan mana yang tidak.

4. Algoritma Perhitungan KNN

a. Menentukan parameter K sebagai banyaknya jumlah tetangga terdekat dengan objek baru.

b. Menghitung jarak antar objek/data baru terhadap semua objek/data yan gtelah di training.

c. Urutkan hasil perhitungan tersebut.

d. Tentukan tetangga terdekat berdasarkan jarak minimum ke K.

e. Tentukan kategori dari tetangga terdekat dengan objek/data.

f. Gunakan kategori mayoritas sebagai klasifikasi objek/data baru.

5. Contoh soal Perhitungan KNN

Diberikan data Training berua dua atribut Bad dan Good untuk mengklasiikasikan sebuah data apakah tergolong Bad atau Good , berikut ini adalah contoh datanya :

Kita diberikan data baru yang akan kita klasifikasikan, yaitu X = 3 dan Y = 5. Jadi termasuk klasifikasi apa data baru ini ? Bad atau Good ?

Langkah penyelesaian

Pertama, Kita tentukan parameter K. Misalnya kita buat jumlah tertangga terdekat K = 3.

Ke-dua, kita hitung jarak antara data baru dengan semua data training. Kita menggunakan Euclidean Distance. Kita hitung seperti pada table berikut :

Ke-tiga, kita urutkan jarak dari data baru dengan data training dan menentukan tetangga terdekat berdasarkan jarak minimum K.

Dari kolom 4 (urutan jarak) kita mengurutkan dari yang terdekat ke terjauh antara jarak data baru dengan data training. ada 2 jarak yang sama (yaitu 4) pada data baris 2 dan baris 6, sehingga memiliki urutan yang sama. Pada kolom 5 (Apakah termasuk 3-NN?) maksudnya adalah K-NN menjadi 3-NN , karena nilai K ditentukan sama dengan 3.

Ke-empat, tentukan kategori dari tetangga terdekat. Kita perhatikan baris 3, 4, dan 5 pada gambar sebelumnya (diatas). Kategori Ya diambil jika nilai K<=3. Jadi baris 3, 4, dan 5 termasuk kategori Ya dan sisanya Tidak.

penentuan kategori yang termasuk K=3

Kategori ya untuk K-NN pada kolom 6, mencakup baris 3,4, dan 5. Kita berikan kategori berdasarkan tabel awal. baris 3 memiliki kategori Bad, dan 4,5 memiliki kategori Good.

Ke-lima, gunakan kategori mayoritas yang sederhana dari tetangga yang terdekat tersebut sebagai nilai prediksi data yang baru.

Data yang kita miliki pada baris 3, 4 dan 5 kita punya 2 kategori Good dan 1 kategori Bad. Dari jumlah mayoritas (Good > Bad) tersebut kita simpulkan bahwa data baru (X=3 dan Y=5) termasuk dalam kategori Good.

Resume Video 2 : Mechine learning

RESUME VIDEO PEMBELAJARAN 2

MECHINE LEARNING

SITI FITRIANAH (18.01.013.120)

OPERATOR IDENTITAS

Pengertian dan Contoh Operator Identitas

Operator identitas adalah operator yang bisa dipakai untuk memeriksa apakah nilai sebuah variabel ada di tempat yang sama (di memory) atau tidak. Operator ini dikenal juga sebagai identity operators.

Operator ini terdiri dari 2 jenis:

Operator Penjelasan

is Bernilai True jika kedua operand merujuk ke object yang sama dan berisi nilai yang sama

is not Bernilai True jika kedua operand merujuk ke object yang tidak sama

Berikut contoh penggunaannya:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

 a = 5

b = 5

c = 6

print('a is b :', a is b)

print('a is c :', a is c)

print('a is not c :', a is not c)

print('\n')

i = 'Duniailkom'

j = 'Duniailkom'

print('i is j :', i is j)

print('i is not j :', i is not j)

print('\n');

x = ['a','b','c']

y = ['a','b','c']

print('x is y :', x is y)

print('x is not y :', x is not y)

Hasil kode program:

a is b : True

a is c : False

a is not c : True

i is j : True

i is not j : False

x is y : False

x is not y : True

Untuk tipe data dasar seperti number atau string, jika dua buah variabel berisi nilai yang sama, maka operator is akan menghasilkan nilai True.

Namun dalam contoh terakhir, variabel x dan y berisi tipe data list. Meskipun nilai element-nya sama persis, tapi Python menyimpannya di alamat memory yang berbeda, sehingga dianggap tidak identik. Hasilnya, x is y adalah False.

Resume Video 1

 

RESUME VIDEO PEMBELAJARAN 1

MECHINE LEARNING

SITI FITRIANAH (18.01.013.120)

MENGENAL BOOLEAN VALUE, JENIS-JENIS OPERATOR DAN KONDISIONAL 

Pendahuluan : Operator adalah bagaimana cara mengoperasikan vc dari variable. Semua pengoperasian tersebut bisa diselesaikan menggunakan Operator. Operator merupakan sebuah symbol atau istilah yang digunakan untuk memanipulasi nilai.

A. Boolean Value

1. Nilai dari Boolean jika bukan true ya false, hanya dua itu, antara iya dan tidak, benar dan salah. Namanya diambil dari ahli matematika Inggris, George Boole, yang pertama kali merumuskan aljabar Boolean - yaitu beberapa aturan mengenai penalaran dan kombinasi dari dua nilai tersebut. Inilah asal muasal dan dasar dari semua logika komputer moderen yang kita kenal dan pakai saat ini.

Di Python, dua nilai Boolean itu dimanakan dengan True dan False (huruf besarnya wajib seperti yang terlihat), dan nama tipenya adalah bool.

1

2

3

4

5

6 >>> type(True)

<class 'bool'>

>>> type(true)

Traceback (most recent call last):

File "<interactive input>", line 1, in <module>

NameError: name 'true' is not defined

?

Ekspresi Boolean merupakan ekspresi yang menilai dan menghasilkan hasil dalam bentuk nilai Boolean. Contohnya, operator == akan menguji apakah dua nilai tersebut sama. Ia akan menghasilkan (atau memberikan - yield) sebuah nilai Boolean:

?

1

2

3

4

5

6

7 >>> 5 == (3 + 2) # Apakah lima sama dengan 5 yang merupakan hasil dari 3 + 2?

True

>>> 5 == 6

False

>>> j = "hel"

>>> j + "lo" == "hello"

True

Pada pernyataan pertama, dua operand yang dinilai nilainya adalah sama, jadi ekspresi memberikan nilai True; namun pada pernyataan kedua, 5 tidak sama dengan 6, jadi kita dapat False.

Operator == adalah satu dari enam operator perbandingan yang paling sering digunakan yang semuanya akan menghasilkan nilai bool; ini adalah daftar keenam operator tersebut:

?

1

2

3

4

5

6 x == y # Menghasilkan True jika ... x adalah sama dengan y

x != y # ... x adalah tidak sama dengan y

x > y # ... x adalah lebih besar dari y

x < y # ... x adalah lebih kecil dari y

x >= y # ... x adalah lebih besar atau sama dengan y

x <= y # ... x adalah lebih kecil atau sama dengan y

Meskipun operasi tersebut mungkin tidak asing, simbol-simbol Python berbeda dengan simbol matematika. Kesalahan yang paling sering terjadi adalah menggunakan tanda sama dengan (=) daripada sama dengan dobel (==). Ingat kalau = adalah operator pemberian nilai dan == adalah operator perbandingan. Juga, di Python tidak ada penulisan semacam =< atau =>. Jadi menulisnya jangan sampai terbalik.

Sama seperti tipe-tipe lainnya yang telah kita lihat sejauh ini, nilai-nilai Boolean bisa diberikan ke variabel, dicetak, dll.

?

1

2

3

4

5

6 >>> umur = 18

>>> cukup_umur_untuk_buat_sim = umur >= 17

>>> print(cukup_umur_untuk_buat_sim)

True

>>> type(cukup_umur_untuk_buat_sim)

<class 'bool'>

B. Jenis-jenis Operator

1. Assignment Operator / Operator Penugasan

Assignment Operator (operator penugasan) adalah operator yang menggunakan tanda sama dengan (=) untuk mengisi sebuah nilai dalam suatu variabel.

2. Arithmetic Operator / Operator Aritmatika

Arithmetic Operator (operator aritmatika) adalah operator yang digunakan untuk melaksanakan operasi aritmatika. Beberapa operator aritmatika antara lain:

* : untuk perkalian

+ : untuk penjumlahan

– : untuk pengurangan

/ : untuk pembagian

% : untuk sisa pembagian (modulus)

3. Logical Operator / Operator Logika / Boolean Operator

Operator Boolean atau Operator Logika adalah operator yang digunakan untuk melakukan operasi logika yaitu operator yang menghasilkan nilai TRUE (benar) atau FALSE (salah).

Bebarapa macam operator logika antara lain:

a. and : menghasilkan nilai TRUE jika kedua operand bernilai TRUE

b. or : menghasilkan nilai TRUE jika salah satu operand bernilai TRUE

c. xor : menghasilkan nilai TRUE jika salah satu operand bernilai TRUE tetapi bukan keduaduanya bernilai TRUE

d. ! : mengasilkan nilai tidak TRUE

e. && : menghasilkan nilai TRUE jika kedua operand bernilai TRUE

f. || : menghasilkan nilai TRUE jika salah satu operand bernailai TRUE

4. Comparison Operator / Operator Pembanding

Operator Pembanding adalah operator yang digunakan untuk membandingkan dua buah nilai atau operand. Operator perbandingan ini antara lain :

< : untuk kurang dari

> : untuk lebih dari

<= : untuk kurang dari atau sama dengan

>= : untuk lebiih dari atau sama dengan

== : untuk sama dengan

!= : untuk tidak sama dengan

<> : untuk tidak sama dengan

C. Kondisional

Agar dapat menulis program yang berguna, kita selalu memerlukan kemampuan untuk mengecek kondisi dan demikian pula merubah prilaku program untuk menyesuaikan diri. Pernyataan kondisional memberikan kita kemampuan ini. Bentuk paling sederhana dari pernyataan if adalah:

?

1

2

3

4

5

6

7 if x % 2 == 0:

print(x, " is even.")

print("Did you know that 2 is the only even number that is prime?")

else:

print(x, " is odd.")

print("Did you know that multiplying two odd numbers " +

"always gives an odd result?")

Ekspresi Boolean setelah pernyataan if dinamakan kondisi. Jika kondisi true, maka semua pernyataan bertakuk di bawahnya akan dieksekusi. Jika tidak, maka semua pernyataan yang bertakuk di bawah klausa else lah yang akan dieksekusi.

Flowchart dari pernyataan if dengan klausa else

Flowchart pernyataan if.png

Syntaks dari pernyataan if terlihat seperti ini:

?

1

2

3

4 if BOOLEAN EXPRESSION:

STATEMENTS_1 # Executed if condition evaluates to True

else:

STATEMENTS_2 # Executed if condition evaluates to False

Sama seperti pendefinisian fungsi pada bab sebelumnya dan pernyataan majemuk lainnya seperti for, pernyataan if juga terdiri dari barsis header dan body. Baris header dimulai dengan keyword if diikuti dengan ekspresi Boolean dan diakhiri dengan titik dua (:). Pernyataan yang bertakuk yang mengikutinya dinamakan dengan block. Pernyataan yang paling pertama yang tidak bertakuk menandakan akhir dari block.

Masing-masing pernyataan di dalam block pertama dari pernyataan dieksekusi untuk menentukan apakan ekspresi Boolean bernilai True. Semua pernyataan yang ada di block pertama akan dilewati jika ekspresi Boolean bernilai False, dan kemudian semua pernyataan pada klausa else lah yang akan dieksekusi.

Tidak ada batasan seberapa banyak pernyataan yang bisa masuk pada kedua klausa dari pernyataan if, tapi setidaknya harus ada satu pernyataan pada masing-masing block. Terkadang, akan sangat berguna untuk memiliki section tanpa pernyataan (biasanya sebagai penanda tempat, atau perancah, untuk kode yang kita belum tulis). Pada kasus seperti itu, kita bisa menggunakan pernyataan pass, yang tidak akan melakukan apapun kecuali hanya sebagai placeholder.

?

1

2

3

4 if True: # This is always True,

pass # so this is always executed, but it does nothing

else:

pass

Genetic Algirithm

RESUME VIDEO PEMBELAJARAN 3
KECERDASAN BUATAN

SITI FITRIANAH (18.01.013.120)

GENETIC ALGORITHM

Outline :

1. What is Solution?

2. Metahuristic Search

- Evolutionary Algorithms

Genetic Algorithm

a. Chromosome

b. Fitness

c. Parent Selection

d. Crossover and Mutation

e. Survivor Selection

Genetic Algorithm adalah sebuah teknik searching untuk mencari solusi dari suatu permasalahan optimasi. Teknik ini diinspirasi dari biologi evolutionary termasuk masalah inheritance, mutation, selection, and crossover. Metode ini melakukan proses searching dengan langkah-langkah sebagai berikut:

1. Populasi diciptakan secara random

2. Setiap individu dari populasi dievaluasi

3. Beberapa individu dipilih untuk berdasarkan nilai fitnessny

4. Individu yang terpilih tersebut kemudian dimodifikasi (di-crossover atau dimutasi

5. Semua individu yang dimodifikasi disatukan menjadi satu populasi baru. Apabila individu yang baru yang terbentuk mempunyai nilai fitness yang lebih rendah dari orang tuanya, individu yang baru tidak dimasukkan di dalam populasi baru, dan dapat tetap menggunakan individu yang lama.

6. Apabila banyaknya jumlah pembentukan populasi telah mencapai angka tertentu, atau level fitness yang memuaskan sudah dicapai, maka proses dihentikan. Apabila belum, populasi baru kemudian digunakan untuk melakukan proses yang sama mulai dari tahap nomor 2.

Menyimpulkan pada langkah-langkah yang tersebut di atas, maka metode ini memerlukan pendefinisian representasi genetic dari domain solusi, dan fungsi fitness untuk mengevaluasi domain solusi. Khusus untuk modifikasi crossover dan mutasi, crossover melakukan kombinasi ulang dari dua atau lebih parents dan mutasi melakukan perubahan terhadap 1 atau lebih dari bagian-bagian yang terdapat pada individu yang dimodifikasi. Bagian-bagian dari individu yang akan dimodifikasi dalam proses ini dapat ditentukan secara random. Kedua jenis fungsi modifikasi ini sangat berguna karena dapat menghindarkan proses searching dari permasalahan local minima.

Genetic Algorithm (GA) adalah bagian dari Evolutionary Algorithm yaitu suatu algoritma yang mencontoh proses evolusi alami dimana konsep utamanya adalah individu-individu yang paling unggul akan bertahan hidup, sedangkan individu-individu yang lemah akan punah[1]. Keunggulan individu-individu ini diuji melalui suatu fungsi yang dikenal sebagai fitness function. Fitness dalam GA didefinisikan sebagai gambaran kelayakan suatu solusi terhadap suatu permasalahan. Fitness Function akan menghasilkan suatu nilai fitness value yang akan menjadi referensi untuk proses GA selanjutnya.

Proses GA dimulai dengan menentukan populasi awal initial population yang terdiri dari beberapa kromosom yang disusun oleh beberpa gen yang merupakan representasi dari kandidat-kandidat solusi dari suatu masalah. Kandidat-kandidat terbaik akan dipilih melalui proses selection, berdasarkan fitness value yang telah dihitung untuk setiap kromosom dalam populasi. Kandidat – kandidat terpilih dari proses ini adalah individu-individu yang akan mengisi mating pool yaiu suatu set dimana dua parents akan dibentuk dari sini. Dalam Evolutionary Algorithm prinsip bertahan muncul karena adanya proses reproduksi. Turunan offspring yang dihasilkan akan membawa sifat gen orangtuanya (parents) , oleh sebab itu parents dipilih dari mating pool yang merupakan kumpulan kandidat-kandidat terbaik dari suatu populasi. Dengan demikian turunan yang dihasilkan adalah turunan yang memiliki sifat unggul dari kedua orang tuanya.

GA adalah salah satu algoritma yang digunakan untuk proses optimisasi. Dalam optimisasi, kondisi optimal solusi-solusi yang diperoleh adalah target utama yang akan dicapai. Namun dalam algoritma optimisasi, kondisi optimum lokal local optimum sering terjadi. Optimum lokal adalah suatu kondisi dimana algoritma mencapai nilai tertinggi atau terendah pada beberapa nilai kandidat solusi. Hal ini berlawanan dengan kondisi optimum global (global optimum) yaitu algoritma mencapai niai teringgi atau terendah untuk seluruh kandidat solusi dalam suatu masalah tertentu. Optimum lokal dapat terjadi salah satunya diakibatkan oleh populasi mencapai format konvergensi terlalu dini premature convergence. Menurut Rajeev dan Krisnamoorthy [2] kriteria tercapainya konvergensi adalah apabila sekitar 80% atau 85 % dari jumlah kromosom memiliki nilai gen yang sama. Salah satu cara untuk mencegah masalah prematur dini ini adalah dengan mempertahankan keragaman kromosom dari suatu populasi. Dalam GA, keragaman kromosom dari suatu populasi dapat dipertahankan dengan mengimplementasikan operator crossover dan mutasi (mutation).

Crossover adalah suatu operator rekombinasi yang bertujun untuk memperloleh individu yang lebih baik. Operator crossover melakukan rekombinasi dari set parents yang akan dipilih secara acak dari mating pool yang telah terbentuk dari proses seleksi. Crossover akan menghasilkan satu set turunan offspring yang keragamannya akan tetap dipertahankan dengan proses selanjutnya yaitu mutasi. Pada operator mutasi, keragaman akan dipertahankan dengan menukar salah satu atau lebih gen dalam kromosom dengan nilai kebalikannya. Sebagai contoh, jika kromosom kita memiliki nilai biner 0 dan 1 maka jika secara acak titik mutasi yang terpilih memiliki nilai 1, nilai ini akan ditukar menjadi nilai 0 atau sebaliknya. Hasil dari operator mutasi ini adalah turunan baru yang selanjutnya akan kembali diuji pada funsi fitness untuk melihat kelayakan populasi baru dari hasil proses GA ini sebagai kandidat solusi dari masalah yang diberikan. Proses pengujian fitness, seleksi,crossover dan mutasi akan dilakukan secara berulang sedemikian hingga telah dipenuhi salah satu kontrol perulangan proses GA berikut yaitu iterasi, konvergensi atau nilai fitness.

Resume Video Pem

 RESUME VIDEO PEMBELAJARAN 2

KECERDASAN BUATAN

SITI FITRIANAH (18.01.013.120)

HEURISTIC (INFORMED) SEARCH

Outline :

1. Heuristic Function

2. Hill Climbing

3. Simulated Annealing

4. Best-First Search

5. A* Search

Para peneliti awal kecerdasan buatan menitik beratkan pada penyelesaian masalah yang tidak menggunakan metoda komputasi konvensional, hal ini disebabkan metoda pemecahan masalah konvensional tidak dapat lagi digunakan. Permasalahan pada sistem kecerdasan buatan tidak memiliki algoritma tertentu, kalaupun ada tentulah sangat kompleks. Karena itu haruslah ditemukan sebuah teknik baru yang mirip dengan cara yang digunakan oleh manusia untuk menyelesaikan masalah dan dapat diimplementasikan pada komputer. Salah satu metoda yang cukup terkenal adalah metoda searching.

Searching dalam sebuah struktur data telah menjadi dasar bagi algoritma komputer, tetapi proses searching pada kecerdasan buatan memiliki perbedaan. Metoda searching pada kecerdasan buatan merupakan searching terhadap problem space bukan searching data (e.g., angka, karakter, string) tertentu. Para peneliti awal kecerdasan buatan menitik beratkan pada penyelesaian masalah yang tidak menggunakan metoda komputasi konvensional, hal ini disebabkan metoda pemecahan masalah konvensional tidak dapat lagi digunakan.

Permasalahan pada sistem kecerdasan buatan tidak memiliki algoritma tertentu, kalaupun ada tentulah sangat kompleks. Karena itu haruslah ditemukan sebuah teknik baru yang mirip dengan cara yang digunakan oleh manusia untuk menyelesaikan masalah dan dapat diimplementasikan pada komputer. Salah satu metoda yang cukup terkenal adalah metoda searching. Searching dalam sebuah struktur data telah menjadi dasar bagi algoritma komputer, tetapi proses searching pada kecerdasan buatan memiliki perbedaan.

Metoda searching pada kecerdasan buatan merupakan searching terhadap problem space bukan searching data (e.g., angka, karakter, string) tertentu

Pencarian Heuristic

1. Pencarian buta tidak selalu dapat diterapkan dengan baik

a. Waktu aksesnya yang cukup lama

b. Besarnya memori yang diperlukan

2. Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.

3. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan ➔ disebut fungsi heuristic

4. Aplikasi yang menggunakan fungsi heuristic : Google

Operator

 Ubin kosong geser ke kanan

 Ubin kosong geser ke kiri

 Ubin kosong geser ke atas

 Ubin kosong geser ke bawah

Langkah Awal

1. Langkah Awal hanya 3 operator yang bisa digunakan

 Ubin kosong digeser ke kiri, ke kanan dan ke atas.

2. Jika menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang)

3. Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut

Informasi yang bisa diberikan

 Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)

 Untuk jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

 Menghitung total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Resume Video Kecerdasan Buatan

 RESUME VIDEO PEMBELAJARAN 1

KECERDASAN BUATAN

SITI FITRIANAH (18.01.013.120)

INTRODUCING TO SEARCHING

OF ARTIFICIAL INTELLIGENT

Outline :

1. Why Searching

2. Space Representation

3. Search Space

4. Un-Informated Serach

5. Informed Search

Searching adalah mekanisme pemecahan masalah yang paling umum di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error secara sistematis pada eksplorasi setiap alternatif jalur yang ada.Algoritma searching di dalam kecerdasan buatan yang umumnya dikenal adalah :

1. Uninformed Search Algorithm

Algoritma yang tidak memberikan informasi tentang permasalahan yang ada, hanya sebatas definisi dari algoritma tersebut.

2. Informed Search Algorithm

Walaupun dengan menggunakan Uninformed Search Algorithm, banyak permasalahan dapat dipecahkan, namun tidak semuanya dari algoritma tersebut dapat menyelesaikan masalah dengan efisien.

A. Uninformed Search Algorithm

1. Breadth First Search (BFS)

Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

Gambar 1 Penelusuran Ekspansi Node pada Breadth First Search

2. Uniform Cost Search (UCS)

Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.

Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

3. Depth First Search (DFS)

Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

4. Depth Limited Search

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.

5. Iterative Deepening Depth First Search

Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.

6. Bidirectional Search

Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.

B. Informed Search Algorithm

Informed Search sering disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan knowledge yang spesifik kepada permasalahan yang dihadapi disamping dari definisi masalahnya itu sendiri. Metode ini mampu menemukan solusi secara lebih efisien daripada yang bisa dilakukan pada metode uninformed strategy.

Pada pencarian dengan menggunakan metode Uniform Cost Search (salah satu bagian dari Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada, dan kemudian akan melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). Lebih lanjut lagi dari metode pencarian tersebut, pada Informed Search Algorithm, kita akan mengenal nilai estimasi (prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.

1. Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.

                     f(n) = h(n)

2. A* Search

Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).

                    f(n) = g(n) + h(n)

Uninformed and Informed Search Exercise

Gambar Uninformed dan Informed Search Problem

Apabila diberikan kondisi tree seperti gambar di atas, dimana biaya lintasan (path), dan nilai prediksi/estimasi diberikan, maka kita dapat melakukan simulasi proses ekspansi node untuk algoritma Uniform Cost Search, Greedy Best First Search, dan A* Search.

1. Uniform Cost Search

Proses ekspansi pada Uniform Cost Search dihitung berdasarkan nilai lintasan g(n) sehingga proses akan berjalan sebagai berikut:

f = {S};

f = {C, A, K}; // 1, 2, 2

f = {A, K, D}; // 2, 2, 2

f = {K, D, B}; // 2, 2, 4

f = {D, L, B}; // 2, 3, 4

f = {L, E, B}; // 3, 3, 4

f = {E, B}; // 3, 4

f = {B, F}; // 4, 4

f = {F, H, G}; // 4, 6, 7

f = {G, H, G}; // 5, 6, 7

f = {H, G}; // 6, 7

Proses eksplorasi node dimulai dari S sebagai initial state. Eksplorasi node dari S akan menuju ke A, C, K sebagai successornya. Pada simulasi eksplorasi di atas, untuk mempermudah proses eksplorasi maka dituliskan dengan C, A, K karena urutannya dituliskan secara ascending dari nilai g(n) terkecil sehingga akan dihasilkan urutan node yang akan dieksplorasi selanjutnya. Pada eksplorasi node selanjutnya, nilai g(n) diakumulasikan dari node awal sampai pada node current yang baru dieksplorasikan.

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 10 kali, dan path yang dilalui dengan menggunakan algoritma Uniform Cost Search adalah S-C-D-E-F-G.

2. Greedy Best First Search

Proses ekspansi dengan menggunakan algoritma Greedy Best First Search adalah dengan merujuk pada nilai estimasinya yaitu h(n). Berbeda halnya dengan nilai g(n) yang diakumulasikan, nilai h(n) tidak diakumulasikan. Proses eksplorasi akan berjalan seperti berikut ini:

f = {S};

f = {A, C, K}; // 2, 4, 5

f = {B, C, K}; // 3, 4, 5

f = {G, C, H, K}; // 0, 4, 4, 5

f = {C, H, K}; // 4, 4, 5

Proses yang dilakukan pada Greedy Best First Search sama seperti Uniform Cost Search, namun parameter yang digunakan hanya nilai estimasinya.

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 4 kali, dan path yang dilalui dengan menggunakan algoritma Greedy Best First Search adalah S-A-B-G.

3. A* Search

Eksplorasi node dari metode A* dilakukan dengan cara menjumlahkan kombinasi nilai path g(n) dan nilai estimasi h(n). Penjumlahan dari nilai tersebut akan dibandingkan untuk menentukan node mana dulu yang akan dieksplorasikan. Prosesnya akan berjalan sebagai berikut ini:

f = {S};

f = {A, C, K}; // 4, 5, 7

f = {C, K, B}; // 5, 7, 7

f = {D, K, B}; // 5, 7, 7

f = {E, K, B}; // 5, 7, 7

f = {F, K, B}; // 5, 7, 7

f = {G, K, B}; // 5, 7, 7

f = {K, B}; // 7, 7

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 7 kali, dan path yang dilalui dengan menggunakan algoritma A* Search adalah S-C-D-E-F-G.