pencarian jalur terpendek.pptx

23
Pencarian Jalur Terpendek Pada Pemodelan Pergerakan Agen Cerdas Dengan Algotitma Ant Colony System

Upload: chy-kia

Post on 06-Aug-2015

48 views

Category:

Documents


3 download

TRANSCRIPT

Page 1: Pencarian Jalur Terpendek.pptx

Pencarian Jalur TerpendekPada Pemodelan Pergerakan Agen Cerdas

Dengan AlgotitmaAnt Colony System

Page 2: Pencarian Jalur Terpendek.pptx

Latar Belakang..1

• Game yang realistis didukung oleh implementasi human like behavior pada player / Non Player Character / agen cerdas dalam game.

Page 3: Pencarian Jalur Terpendek.pptx

Latar Belakang..2

• Untuk menghidupkan perilaku dari agen cerdas pada gema simulasi perlu diterapkan AI (artificial intelligence). Pergerakan agen cerdas di suatu game sangat erat kaitannya dengan path finding (pencarian jalan). Path finding atau pencarian jalan adalah salah satu dasar algoritma dalam konsep menggerakkan karakter dalam game. Strategi Path finding biasanya digunakan sebagai inti dari setiap pergerakan AI

Page 4: Pencarian Jalur Terpendek.pptx

Latar Belakang..3

• Salah satu tantangan dalam desain realistis AI di komputer permainan agen adalah gerakan. AI merupakan teknologi yang mensimulasikan kecerdasan manusia dan mencoba menyelesaikan persoalan menggunakan komputer dengan meniru bagaimana manusia menyelesaikan dengan cepat.

Page 5: Pencarian Jalur Terpendek.pptx

Latar Belakang..4

• Banyak hal yang dapat diamati dari perilaku manusia didalam mall atau pusat perbelanjaan misalnya saja tentang pergerakan dan behavior.

Page 6: Pencarian Jalur Terpendek.pptx

Pengantar..

• Dalam game moderen berbasis artificial intelligence masih bergantung pada pendekatan behavior manusia dan kondisi dunia nyata. Game yang realistis didukung oleh implementasi human like behavior pada player / Non Player Character / agen cerdas dalam game. Untuk menghidupkan perilaku dari agen cerdas perlu diterapkan kecerdasan buatan. Pergerakan agen cerdas di suatu game sangat erat kaitannya dengan path finding (pencarian jalan). Path finding merupakan salah satu dasar algoritma dalam konsep menggerakkan karakter dalam game.• Dengan algoritma pencarian jalan , agen cerdas dalam game

bisa bergerak dan berperilaku human like behavior.

Page 7: Pencarian Jalur Terpendek.pptx

LANDASAN TEORI..

• Feromon merupakan zat kimia berasal dari kelenjar endokrin yang digunakan makluk untuk mengenali sesama jenisnnya, individu lain, kelompok, dan untuk membantu proses reproduksi.

Page 8: Pencarian Jalur Terpendek.pptx

LANDASAN TEORI..

• Berikut ini cara semut untuk mendapatkan jalur yang paling optimal :

1. Semut berjalan acak untuk menemukan makanan dan meninggalkan feremon pada jalan yang dilaluinya.

2. Feromon konsentrasi tinggi menarik semut lain untuk berpindah jalur, menuju jalur paling optimal.

Page 9: Pencarian Jalur Terpendek.pptx

LANDASAN TEORI..

Lintasan awal mencari makanan dari sarang (A) ke

makanan (B)

Page 10: Pencarian Jalur Terpendek.pptx

Probabilitas Dari Semut K Pada Node R Yang Menuju Node S..

( , )kp r s

( , ) . ( , )

( , ) . ( , )

0

k

r s r sjika S J r

r u r u

sebaliknya

12 2 2r s r s

k

= feromon

1 = merupaka visiblity (invers dari jarak (r, s))

(r, s) = kumpulan node yang dikunjungi oleh semut k

(r, s) =[(x -x ) + (y -y ) ]

J (r) = kumpulan node yang akan

dikunjungi oleh

semut k yang sedang berada pada node r

= parameter yang mengontrol bobot relatif dari

feremon terhadaf jarak relatif ( >0)

Page 11: Pencarian Jalur Terpendek.pptx

Pembaharuan Feremon Global..

1

, 1 . , ,m

kkr s r s r s

,k r s 1 ,

0 k

jika r s Tour dilakukan semut kL

sebaliknya

k

= parameter feremon decay (0< <1)

L = panjang tour yang dilakukan oleh semut

m = jumlah ants

Page 12: Pencarian Jalur Terpendek.pptx

Perumusan Masalah..

• Bagaimana memberikan perilaku pergerakan agen cerdas pada game simulasi berperilaku di mall.

• Bagaimana cara agen cerdas menemukan jalur pemilihan lorong yang menyerupai perilaku manusia di mall dengan menggunakan algoritma ant system.

Page 13: Pencarian Jalur Terpendek.pptx

Desain node dan path pada Environment mall..

Page 14: Pencarian Jalur Terpendek.pptx

FSM (Finite State Machine)..

• FSM merupakan pemodelan dari perilaku dari sebuah obyek yang kompleks dengan state/keadaan yang didefinisikan dan mode transisi yang berubah sesuai keadaan. Misalnya saja pada FSM behavior anak, pada kondisi ”berjalan di lorong mall” akan berubah menjadi ”menoleh kanan/kiri” jika anak sedang ”berfikir” dan akan berlaku ”mencari jalan lain” jika ada ”badut”.

Page 15: Pencarian Jalur Terpendek.pptx

RBS (Rule Base System)..

• Perilaku agen cerdas yang telah digambarkan dalam bentuk FSM kemudian diubah terjemahkan ke dalam tabel RBS yang berisi peraturan – peraturan berdasarkan keadaan dan peristiwa yang terjadi sehingga mendapatkan goal yang dituju. Misalnya saja pada “rule 1” agen anak dengan kondisi lelah dan jalan padat maka anak akan mencari jalur alternative menghindari jalan yang rame untuk mencari tempat duduk.

Page 16: Pencarian Jalur Terpendek.pptx

RBS (Rule Base System)..

Page 17: Pencarian Jalur Terpendek.pptx

RBS (Rule Base System)..

• Penerapan RBS pada koding pemrograman ditulis dalam format “IF.......THEN…” atau juga bisa dituliskan lebih lengkap sebagai berikut ”IF.....THEN.....ELSE.....BECAUSE.....”.

• 3 : tempat duduk• 4 : counter minum• 7 : counter minum di food court

Page 18: Pencarian Jalur Terpendek.pptx

Pencarian Jalur Terpendek..

• Pada pemodelan pergerakan agen cerdas yang berperilaku menggunakan environment di mall ini memerlukan suatu algoritma pencarian jalur terpendek untuk menggerakan agen cerdas dari tempat agen berada menuju goal tertentu yang telah diatur dalam tabel RBS dengan jarak yang seminimal mungkin.

Page 19: Pencarian Jalur Terpendek.pptx

Pencarian Jalur Terpendek..

• Sebagai langkah awal percobaan pemodelan pergerakan agen ini dengan mencoba algoritma Ant Colony pada aplikasi Travelling Salesmen Problem.

• Node-node Travelling Salesmen Problem diasumsikan sama dengan posisi took atau lokasi yang dituju pada aplikasi pemodelan pergerakan agen cerdas dimall. Sedangkan jalur antar node diasumsikan sebagai lorong-lorong di mall.

Page 20: Pencarian Jalur Terpendek.pptx

Pencarian Jalur Terpendek..

• Untuk simulasi aplikasi ini diawali dengan pembuatan :1. tabel inisialisasi posisi node-node (dalam grap) yang

dituliskan dalam matrik.2. dibutuhkan juga tabel jarak antar node3. tabel kadar feremon pada lintasan/path. Algoritma

ant colony system diperlukan proses untuk perhitungan propabilitas sejumlah ant untuk berjalan dari sejumlah yang dilalui

4. kemudian diteruskan dengan proses updating feromon yang ada pada lintasan antar node

Page 21: Pencarian Jalur Terpendek.pptx

• Dari percobaan yang telah dilakukan menggunakan jumlah node 15 , β =5, α = 1 dan variasi jumlah ant dari 10 sampai 800 didapatkan hasil bahwa jumlah semut akan mempengaruhi iterasi panjang tour pembelajaran. Lebih detil dapat dilihat dari tabel berikut :

Page 22: Pencarian Jalur Terpendek.pptx

• Dari percobaan didapatkan jumlahsemut 100 didapat hasil yang optimal, yaitu 45.562 kali iterasi. Untuk jumlah ant di atas 100 nilainya sama dengan jumlah iterasi jika menggunakan 100 ant. Nilai iterasi merupakan nilaiperulangan untuk mengetahui dan mendapatkanjalar terpendek antar node.

Page 23: Pencarian Jalur Terpendek.pptx