Archive for September 2017

PENCARIAN BERBENTUK DAN EKSPLORASI

1. Strategi Pencarian Berbentuk yaitu meliputi :

A) Greddy 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)

B) 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)

C) Memory-Bounded Heuristic Search

2. Fungsi Heuristik

Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

3. Algoritma pencarian lokal dan masalah optimisasi yaitu meliputi :

A) Hill Climbing Search

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

B) Simulated Annealing Search

Simulated Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir kristal atau logam. Algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu

Berikut ini adalah pemetaan dari Physical Annealing ke Simulated Annealing :

Fisika (termodinamika)	Simulated Annealing
Keadaan sistem	Solusi yang mungkin
Energi	Biaya
Perubahan keadaan	Solusi tetangga
Temperatur	Parameter kontrol
Keadaan beku	Solusi heuristik

Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.

Secara umum ada 3 hal pokok pada simulated annealing, yaitu:

a. Nilai awal untuk temperatur (T0).

Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati nol), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperatur awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.

b. Kriteria yang digunakan untuk memutuskan apakah temperatur sistem seharusnya dikurangi.

c. Berapa besarnya pengurangan temperatur dalam setiap waktu.

Contoh Simulated Annealing

Source : http://tomatcoklat.wordpress.com/2012/07/10/simulated-annealing/

C) Local Beam Search

Beam Search adalah algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.

Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :

a. Masalah yang akan di selesaikan

Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.

b. Kumpulan aturan-aturan heuristik untuk pemangkasan

Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.

c. Memori dengan kapasitas yang terbatas

Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi tidak akan melebihi memori yang tersedia.

Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini. Kelemahan utama Beam Search adalah metode pencarian ini mungkin tidak dapat mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus: nodetujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.

Beam A*

Algoritma ini memberikan sedikit variasi pada A*, yaitu dengan membatasi simpul yang bisa disimpan di dalam OPEN. Ketika jumlah simpul di OPEN sudah melebihi batas tertentu, maka simpul dengan nilai f terbesar akan dihapus. Sedangkan jumlah simpul yang di dalamCLOSED tetap dibiarkan tanpa batasan karena simpul yang di dalamCLOSED memang tidak mungkin dihapus. Dengan membatasi jumlah simpul di OPEN, maka pencarian menjadi lebih terfokus seperti sinar (beam). Sehingga variasi ini dinamakan Beam A*.

Implementasi algoritma BA* sama dengan A* tetapi ada sedikit fungsi tambahan untuk pengecekan dan penghapusan simpul terburuk di OPEN.

Algoritma Beam A* menggunakan dua senarai : OPEN danCLOSED. OPEN adalah adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup).

Terdapat tiga kondisi bagi setiap sukseror yang dibangkitkan, yaitu : sudah berada di OPEN, sudah berada di CLOSED, dan tidak berada di OPEN maupun CLOSED. Pada ketiga kondisi tersebut diberikan penanganan yang berbeda-beda.

Jika suksesor sudah pernah berada di OPEN, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak tergantung pada nilai g-nya melalui parent lama atau parent baru. Jika melaluiparent baru memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent. Jika pengubahan parent dilakukan, maka dilakukan pula perbaruan (update) nilai g dan f pada suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai simpul terbaik (best node).

Jika suksesor sudah pernah berada di CLOSED, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak. Jika ya, maka dilakukan perbaruan nilai g dan f pada suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah berada di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best node).

Jika suksesor tidak berada di OPEN maupun CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h.

PENCARIAN BERBENTUK DAN EKSPLORASI

Kamis, 28 September 2017

Author : aditya Comments : 0

Tag :

AGEN PEMECAHAN MASALAH

Graf Keadaan
Pohon Pelacakan
Pohon AND/OR

Graf Keadaan

Pada graf keadaan dengan arah di atas:

>> Ada 4 lintasan yang mencapai tujuan, yakni :

1. M-A-B-C-E-T

2. M-A-B-C-E-H-T

3. M-D-C-E-T

4. M-D-C-E-H-T

>> Ada 5 lintasan yang tidak mencapai tujuan yakni :

1. M-A-B-C-E-F-G

2. M-A-B-C-E-I-J

3. M-D-C-E-F-G

4. M-D-C-E-I-J

5. M-D-I-J

Kelemahan graf berarah:

>> Memungkinkan terjadi siklus (perulangan) seandainya graf tidak memiliki arah.

>> Sulit mencapai tujuan

b. Pohon Pelacakan

Untuk menghindari kemungkinan adanya proses pelacakan suatu node secara berulang, maka digunakan struktur pohon

à Keuntungan pohon pelacakan:

>> Tujuan tercapai

>> Tidak terjadi siklus

à Kelemahan pohon pelacakan:

>> Proses pelacakan agak lama (perlu waktu

lama)

c. Pohon AND/OR

Kelemahan pada teknik pohon pelacakan dapat diselesaikan dengan teknik pelacakan menggunakan pohon AND/OR.

Metode Pencarian dan Pelacakan

Pencarian sebagai solusi masalah

Hal penting dalam menentukan keberhasilan sistem cerdasadalah kesuksesan dalam pencarian. Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

• Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :

- Completeness : apakah metode tsb menjamin penemuan solusi jika solusinya memang ada?

- Time complexity : berapa lama waktu yang diperlukan?

- Space complexity : berapa banyak memori yg diperlukan

- Optimality : apakah metode tsb menjamin menemukan

solusi yg terbaik jika terdapat beberapa solusi berbeda?

. Best First Search

• Metode best first search merupakan kombinasi dari metode depth first search & breadth first search dengan mengambil kelebihan dari kedua metode tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node yang lebih rendah meskipun node tersebut memiliki nilai heuristik lebih baik. Pada best first search, pencarian diperbolehkan mengunjungi node yang lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk. Untuk mengimplementasikan metode ini, dibutuhkan 2 antrian yang berisi node-node, yaitu :

• OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristik namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.

• CLOSED : berisi node-node yang sudah diuji.

.UCS (Uniform Cost Search)
UCS (Uniform Sost Search) adalah perpaduan antara BFS dan DFS. Pada UCS, teknik pencariannya memperhatikan cost/jarak antara 1 node ke node lain.
Berikut ini adalah ilustrasinya :

Pada permasalahan diatas telah ditentukan jarak antara node. Maka pada model UCS, teknik yang akan dilakukan adalah membuka node yang memiliki nilai/cost antar node yang terendah.

pada gambar diatas jika kita buka :

c = 10

b = 20

a = 10

Karena nilai c dan a sama maka teserah mau membuka yang mana lebih dahulu.

Seandainya kita membuka c maka kita teruskan pencariannya, lalu kita buka :

d = 10+5 =15

DFS (Depth-first Search)
DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemuakn “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.
Dengan menggunakan permasalahan yang sama dengan penjelasan di awal tadi, maka pada model DFS akan di dapatkan solusi seperti gambar di bawah ini.

Jadi, solusi node yang di lalui pada DFS adalah a,b,e,h.
DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.

e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)

Maka kita buka node d, lalu akan diperoleh hasil :

e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a.

Setelah kita buka node a, maka akan di dapat hasil :

e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)

Dari kasus diatas, dapat kita lihat bahwa ada banyak cara unuk mendapatkan solusi. Namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari model UCS.

Algoritma DLS (Depth Limited Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.
Algoritma ini merupakan variasi dari Algoritma DFS (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth First Search) melakukan perhitungan (yang dimulai dengan titik terakhir) dengan cara menghabiskan semua tingkatan / kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kedalaman tertentu. Setelah semua kemungkinan pada kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.

Menyelesaikan Masalah Dalam Proses Pencarian

Author : aditya Comments : 0

Tag :

PENGERTIAN ARTIFICIAL INTELLIGENCE (AI)

Kecerdasan buatan (Artificial Intelligence) merupakan bagian dari ilmu komputer yang mempelajari bagaimana membuat mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia bahkan bisa lebih baik daripada yang dilakukan manusia.

PERBEDAAN KECERDASAN BUATAN DAN KECERADASAN ALAMI

Kelebihan Kecerdasan Buatan :

Kecerdasan buatan lebih bersifat permanen.
Kecerdasan buatan lebih mudah diduplikasi dan disebarkan.
Kecerdasan buatan Lebih murah.
Kecerdasan buatan bersifat konsisten
Kecerdasan buatan dapat didokumentasi.
Kecerdasan buatan lebih cepat dibandingan kecerdasan alami.
Kecerdasan buatan lebih baik dibandingkan kecerdasan alami.

Kelebihan Kecerdasan Alami :

Kecerdasan alami lebih kreatif
Kecerdasan alami memungkinkan seseorang untuk menggunakan pengalaman secara langsung.
Kecerdasan alami menggunakan pemikiran manusia yang dapat digunakan secara luas

SEJARAH KECERDASAN BUATAN

Kecerdasan Buaran Sendiri dimunculkan oleh seorang profesor dari Massachus Institute of Tecnology yang bernama John McCarthy pada tahun 1956 pada Dartmouth Conferense yang dihadiri oleh para peneliti AI. Pada konferensi tersebut juga didefinisikan tujuan utama dari Kecerdasan Buatan, yaitu : mengetahui dan memodelkan proses-proses berfikir manusia dan mendesain mesin agar menirukan kelakuan manusia tersebut.

4.Agen dan lindunganya

. Agen sosialisasi yang pertama adalah keluarga. Mengenai keluarga ini dikatakan sebagai agen sosialisasi pertama dan utama yang paling dianjurkan dalam kehidupan bersosialisasi. Keluarga sebagai langkah awal kita dalam mengenal segala sesuatu yang berhubungan dengan lingkungan sekitar. Sebelum mengenal lingkungan, tentunya kita dikenalkan dulu pada lingkungan keluarga. Keluarga akan mengajarkan kita banyak hal, yang membuat kita menjadi siap untuk hidup bersosialisasi dengan masyarakat sekitar. Kita mengenal orang tua serta saudara-saudara tujuannya untuk memberi gambaran awal mengenai karakteristik orang lain di luar lingkungan keluarga.
2. Agen yang kedua yakni agen kelompok bermain. Dalam kehidupan sehari-hari tentunya masa pertumbuhan selanjutnya adalah mencari teman-teman atau kelompok bermain. Kelompok bermain akan membentuk karakter pribadi manusia. Hal ini didasarkan pada seberapa sering mereka bermain, berinteraksi serta saling mengenal satu sama lain. Dengan memiliki kelompok bermain tentunya kita bisa belajar bagaimana cara menyelesaikan masalah, mencari solusi, menghindari konflik. Sehingga penting untuk memilih kelompok bermain yang tepat serta sesuai dengan yang kita inginkan.
3. Selanjutnya adalah agen media massa. Siapa yang tahu media massa? Media massa sekarang ini gencar memberitakan berbagai peristiwa. Melalui berita-berita yang ada di media massa sama halnya media massa tersebut sedang mensosialisasikan serta mengabarkan berbagai kehidupan sosial yang terjadi. Dengan begitu, maka media massa sangat erat kaitannya dengan kehidupan sosial masyarakat. Untuk mengetahui kondisi masyarakat pada saat ini, maka bisa dilihat dengan melihat tayangan yang ada di media massa.
4. Yang terakhir adalah agen pendidikan. Selain mengetahui kehidupan sosial lewat media massa, kita juga belajar mengenai agen sosial yang satu ini. Pendidikan berarti lingkungan sekolah yang banyak memberikan pelajaran bagi kita bagaimana cara bersosialisasi secara benar pada orang lain. Di lingkungan sekolah atau lembaga pendidikan kita diajarkan untuk mulai mengenal orang lain, mulai mengetahui konflik, serta mulai mencari tahu pemecahan masalah yang seharusnya dihadapi. Jadi lingkungan sekolah bisa dikatakan tempat yang tepat untuk dijadikan agen sosial.

Konsep Rasionalitas

Tidak mudah untuk membuat pengetahuan informal dan menyatakan pengetahuan tersebut ke dalam formalterm yang diperlukan oleh notasi logika.
Terdapat perbedaan besar antara dapat memecahkan masalah “secara prinsip” dan memecahkannya “dalam dunia nyata”.

Acting Rationally : The Rational Agent Approach

Membuat inferensi logis merupakan bagian dari suatu rational agent .
Dengan menalar secara logis, maka bisa didapatkan kesimpulan bahwa aksi yang dilakukan akan mencapai tujuan atau tidak.

Struktur agen

Sistem Pakar (Expert System)
Pengolahan Bahasa Alami (Natural Language Processing)
Pengenalan Ucapan (Speech Recognition)
Robotika & Sistem Sensor (Robotics & Sensory System)
Computer Vision
Intelligent Computer-aided Intruction
Game Playing

ROBOTIKA

Robot adalah agen – agen fizikal yang melakukan tugas dengan memanipulasi dunia fisik. Untuk melakukannya, dilengkapi dengan effectors seperti kaki, roda, sendi, dan grippers.

Tiga katagori utama robot :

Manipulator
Mobile Robot
Mobile Manipulator.

KESIMPULAN

Dari pemaparan diatas dapat disimpulkan bahwa Artificial Intelligence atau Kecerdasan Buatan adalah kecerdasan yang dibuat agar mesin (komputer) dapat melakukan pekerjaan sebaik atau bahkan lebih dari manusia. Salah satu implementasi dari kecerdasan buatan ini adalah robotika dan sensor. Robotika adalah agen-agen fisik yang melakukan tugas dengan memanipulasi dunia fisik. Jika manusia mempunyai otak sebagai pusat syarafnya, maka robot mempunyai kecerdasan buatan sebagai pusat syarafnya. Penggunaan robot saat ini sangaat beragam mulai dari industri, pertanian, mobil robot, kesehatan, sampai hiburan dan augmentasi manusia.

Sumber Referensi:

Dokumen Rangkuman

http://sunny.staff.gunadarma.ac.id/Downloads/files/20201/Kecerdasan_buatan+Ibu+Idha.pdf
https://books.google.co.id/books?id=MocuEV7C96YC&pg=PA3&dq=TEORI+KECERDASAN+BUATAN&hl=id&sa=X&ved=0ahUKEwi8gf3x_rbPAhWFmpQKHcmOA7kQ6AEIGjAA#v=onepage&q=TEORI%20KECERDASAN%20BUATAN&f=false
http://yuliana.lecturer.pens.ac.id/Kecerdasan%20Buatan/Buku/Bab%201%20Pengenalan%20Kecerdasan%20Buatan.pdf
http://lppm.trigunadharma.ac.id/public/fileJurnal/hpOmJurnal%2012-2-2013%20Zulfian_7.pdf
http://entin.lecturer.pens.ac.id/Kecerdasan%20Buatan/Buku/Bab%201%20Pengenalan%20Kecerdasan%20Buatan.pdf

http://library.binus.ac.id/eColls/eThesisdoc/Bab2/2013-2-00421-MTIF%20Bab2001.pdf

http://yuliana.lecturer.pens.ac.id/Kecerdasan%20Buatan/Buku/Bab%201%20Pengenalan%20Kecerdasan%20Buatan.pdf

http://entin.lecturer.pens.ac.id/Kecerdasan%20Buatan/Buku/Bab%201%20Pengenalan%20Kecerdasan%20Buatan.pdf