Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.9-545-0270-1
Autonomous Agen Pembeli dengan Pendekatan Multi Objective Evolutionary Optimization (MOEA) NSGA II Dwi Rolliawati 1) Supeno Mardi 2) Moch.Hariadi 3) I Ketut Eddy Purnama4) Teknik Elektro ITS, Surabaya, Indonesia, email: ro l li a wati0 9 @mhs.its.ac.id1 Teknik Elektro ITS, Surabaya, Indonesia2,3,4 Abstrak Sebuah game dikatakan menarik jika melibatkan permasalahan multi obyektif. Inti dari game terletak pada perilaku agennya yang dibekali kecerdasan buatan. Dalam penelitian ini, didesain perilaku agen pembeli dengan pendekatan optimasi multi obyektif menggunakan algoritma MOEA (Multi Objective Evolutionary Optimization) NSGA-II. Konsep multi kriteria pada agen dalam penelitian ini didasarkan teori Constraint Satisfaction Problem (CSP) sedangkan state perilaku agen diatur dengan finite stste machine (FSM). Dari penelitian ini dihasilkan solusi optimal bagi agen yang ditampilkan bentuk grafik. Dari hasil simulasi tersebut dibangkitkan perilaku agen pembeli dalam memutuskan `membeli`, `negosiasi` atau `tidak membeli` Kata Kunci: game, multi obyektif, agen, pembeli,, MOEA NSGA-II, CSP, FSM, simulasi .
1. Pendahuluan A g e n a d a l a h suatu entitas perangkat lunak komputer yang memungkinkan user (pengguna) untuk mendelegasikan tugas kepadanya secara mandiri (autonomously). Agen memiliki kemampuan cerdas untuk berkolaborasi dengan user, melakukan fungsi monitoring dan learning untuk memenuhi kebutuhan user. Dalam melakukan fungsi monitoring dan learning, seorang agen harus dibekali kecerdasan buatan. Dalam dunia nyata, pembeli memiliki kecerdasan dalam memilih barang yang akan dibeli, memilih penjual yang menurutnya nyaman dan menguntungkan. Seorang pembeli akan mempertimbangkan banyak hal (multi criteria) ketika akan memutuskan membeli sesuatu. Variabel pertimbangan yang paling umum dari sisi pembeli adalah harga minimal dengan kualitas yang baik. 2 kriteria ini sangat bertentangan, inilah yang dinamakan kasus multi objektif. Penelitian tentang agent pembeli telah banyak dilakukan [1,2,3,4]. Dalam penelitian sebelumnya [1] dibuat agen pembeli berbasis hierarchical finite state machine (HFSM) untuk mensimulasikan keputusan SCM Procurement. Akan tetapi persoalan multiobjektif dalam penelitian tersebut masih belum dikembangkan dan system yang digunakan banyak kelemahannya. Rumusan dalam bentuk model matematis dari strategi agent pembeli dan penjual supaya saling menguntungkan [2]. Masih berkorelasi tentang agen pembeli, [3] mengembangkan agen pembeli berbasis logika Fuzzy untuk proses negosiasi otomatis dalam ecommerce. Sedangkan peneliti yang lain [4] telah mengembangkan pendekatan optimasi multi objektif pada agen pembeli dan penjual menggunakan teknik priority based matchmacing algoritma genetika. Merujuk dari berbagai penelitian tersebut, diusulkan
autonomous agen pembeli studi kasus agen pembelian laptop dengan pendekatan Multi Objective Evolutionary Optimization (MOEA) menggunakan Non Dominant Sort Genetic Algorithm II atau lebih dikenal dengan nama MOEA NSGA-II. Adapun konstrain dari multi kriteria variabel didasarkan pada teori Constraint Satisfaction Problem (CSP). Penelitian ini bertujuan untuk mensimulasikan perilaku pembeli mandiri (autonomous) yang dapat diaplikasikan dalam membantu pengambilan keputusan seorang purchasing/agen pembelian laptop dalam bentuk game. Akan tetapi simulasi game dalam penelitian belum terimplementasikan. Hasil akhir dari penelitian ini untuk sementara adalah varian nilai fungsi fitness yang merupakan output dari agen pembeli ini. Sehingga pembeli akan memutuskan pada state membeli, bernegosiasi atau tidak membeli. State perilaku agen ditunjukkan melalui model Finite State Machine (FSM). Formula dan simulasi dalam penelitian ini bisa digunakan sebagai sarana edutainment untuk mata pelajaran ekonomi. 2. Metode yang diterapkan Untuk membuat autonomous agen pembeli dari parameter multi objektif yang saling bertentangan maka dibuat suatu pengendali optimisasi multi objektif Non Dominant Sort Genetic Algorithm II (NSGA-II). Gambaran sistem pada penelitian ini,terlihat pada gambar 1. Dimulai dari inisial variabel criteria pembeli, kemudian diolah menggunakan algoritma NSGA-II, sehingga menghasilkan nilai fitness yang dapat menentukan keputusan bagi pembeli tersebut. Kriteria pembeli pada penelitian ini didasarkan dari hasil survey pembeli laptop masyarakat umum. Sedangkan alur sistem dari algoritma NSGA 2 dapat dilihat pada gambar 2.
Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.9-545-0270-1
Multi Kriteria Pembeli: Harga Prosesor Memori Harddisk Bobot
MOEA NSGA 2
Keputusan Agen pembeli
Nilai fitness
Gambar 1. Desain sistem secara keseluruhan Start
Initialise Populasi gen
Pop Classified
No
Fitness
Gen= gen+1 Crossover
Mengidentifikasi Individu yang dominan
Mutation Yes
Apakah Pop Terklasifikasi NO
STOP
Untuk tiap front Fi, n jumlah individu: – initialize Fi(dj ) = 0, – for each objective function m Sort the individuals in front Fi based on objective I =sort(Fi,m). – Tetapkan jarak infinite pada tiap individu I(d1) = ∞ dan I(dn) = ∞ – for k = 2 to (n − 1): I(dk) = I(dk) + (I(k + 1).m− I(k − 1).m)/fmax − fmin
2.1 Perspektif Pembeli Perilaku konsumen sebagai perilaku pembeli akhir baik individu maupun rumah tangga yang membeli produk untuk konsumsi personal. Dari definisi tersebut ditarik kesimpulan yaitu : 1) Perilaku konsumen menyoroti perilaku individu dan rumah tangga 2) Perilaku konsumen menyangkut suatu proses keputusan sebelum membeli serta tindakan memperoleh, memakai, mengkonsumsi dan menghabiskan produk. Dari teori tersebut, agen pembeli pada penelitian ini memiliki variabel harga, spesifikasi/kapasitas barang (prosesor, memori, harddisk), yang dipengaruhi oleh faktor ketertarikan pembeli (buyer preference). Variabel ketertarikan pembeli berhubungan dengan factor psikologi dari agen. Seorang agen pembeli tidak selamanya menginginkan mempunyai barang yang murah dengan kapasitas sempurna. Aksi autonomous agen dalam penelitian ini digambarkan sebagai berikut: Penawaran Penjual
Gambar 2. Alur Algoritma NSGA 2
Proses seleksi memilih individu yang baik (fit) pada algoritma NSGA II menggunakan teknik non dominant sort dan crowding distance. Kedua teknik tersebut ditunjukkan pada tabel 1 dan 2.
Penilaian Harga
Ekpektasi Pembeli
Kemampuan Minimal Pembeli
AGEN PEMBELI Penilaian Kualitas
Kemampuan Maksimal Pembeli
Tabel 1: Algoritma Non Dominant Sort Non Dominant Sort7 Untuk tiap individu p dalam populasi P lakukan: – inisialisasi Sp = ∅. Himpunan individu yang didominasi p – Initialize np = 0. Julah individu yang di domianasi p – Untuk tiap individu q pada P: – jika p mendonimasi q maka: add q pada Sp i.e. Sp = Sp ∪ {q} – else jika q mendominasi p maka: increment jumlah dominasi untuk p: np = np + 1 – jika np=0 maka: prank = 1. Sehingga F1 = F1 ∪ {p} 2. Ambil semua populasi P 3. Inisialisasi front i=1 4. Untuk i berjalan : – Q = ∅. i= (i + 1) – Tiap individu p pada front Fi – Untuk tiap individu q pada Sp: nq = nq−1, if nq = 0 maka tidak ada invidu yang mendominasi pada front qrank = i + 1. – Tambahkan cacah front dengan 1 – Hinga front berikutnya sampai Fi = Q.
Preference Pembeli
1.
Tabel 2: Algoritma Crowding Distance Crowding Distance7
Gambar 3. Diagram blok autonomous agen pembeli
2.2 Constraint Satisfaction Problem Dalam menyelesaikan suatu kasus diberikan nilai konstrain dibagi menjadi 2 yaitu konstrain tegas (hard constraint) dan lunak (soft constraint). Konstrain tegas adalah fungsi yang harus sama persis (equal to). Sedangkan konstrain lunak adalah fungsi yang fleksibel, memiliki range tertentu dalam menyelesaikan permasalahan, dan konstrain inilah yang digunakan untuk penyelesaian penelitian ini. Dalam perspektif agen pembeli notebook konstrain lunak ini dikategorikan 1. lebih banyak adalah lebih baik, meliputi parameter prosesor, memori, harddisk. Dalam penelitian ini dinamakan fungsi maksimal kapasitas
Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.9-545-0270-1
2.
lebih sedikit adalah lebih baik, yaitu harga. Dalam penelitian ini dinamakan fungsi minimal harga.
2.3 Model Matematis Fungsi Fitness Visi umum dari penelitian ini adalah penyelesaian kasus multi objektif yang saling bertentangan. Berdasarkan teori ekonomi, dalam kasus pembelian, seorang pembeli memutuskan membeli dengan mempertimbangkan:
dipengaruhi oleh nilai penawaran penjual ( kemampuan maksimum pembeli ( ekpektasi pembeli (
Dimana xi-n adalah variabel preference dari pembeli itu sendiri dengan . Maka dari perumusan tersebut, ditentukan : 1. Fungsi maksimal (f1), yaitu fungsi kapasitas. Fungsi ini dipengaruhi oleh penilaian pembeli bigf , bobot ketertarikan agen terhadap masing-masing kapasitas laptop yang ditawarkan (Prosesor, memory dan harddisk). Selain memiliki bobot tersebut yang berbentuk matrik 3 x N, fungsi ini juga memiliki bobot kumulatif . Bobot ini adalah sebagai variabel pembanding terhadap fungsi harga. Adapun bigf dipengaruhi oleh nilai
pembeli (
), kemampuan minimal
), nilai ekpektasi pembeli (
),
), nilai
. Dengan i adalah pembeli,
f sebagai fungsi konstrain lunak dan g adalah produk yang ditawarkan. Sehingga dapat dituliskan :
P = x1 . harga + x2. Kualitas + x3. Kultur + x4. Learning ….+ xn.yn
penawaran penjual (
dengan harga yang murah, akan tetapi bergantung pada bobot ketertarikan agen terhadap sesuatu yang ditawarkan. Hampir sama dengan fungsi yang pertama, dalam menentukan bigf fungsi ini
.
Dengan i sebagai pembeli, f sebagai fungsi
konstrain lunak, k jumlah variabel kapasitas (Prosesor, hardisk, memory) dan g adalah produk yang ditawarkan. Sehingga dapat dituliskan : dimana: dengan
) Dimana :
Perhitungan nilai fitness dari beberapa fungsi diatas akan menentukan keputusan state autonomous agen pembeli. Dimana: bigf : fungsi penilaian pembeli agf : penawaran penjual eif : nilai ekspektasi pembeli eifmin: kemampuan minimum pembeli eifmax: kemampuan maksimal pembeli : fungsi intermediate agen : fungsi objektif agen : bobot ketertarikan terhadap kapasitas : bobot kumulatif kapasitas : bobot kumulatif harga 2.4 Finite State Machine Autonomous Agen Finite State Machine (FSM) atau disebut juga finite state automata merupakan suatu model abstraksi matematis yang biasanya digunakan untuk merepresentasikan logika digital atau pemrograman computer. Dalam penelitian ini FSM digunakan untuk memodelkan perilaku autonomous agen pembeli yang terdiri dari beberapa state seperti terlihat pada gambar dibawah ini.
2. Fungsi minimal (f2) yaitu fungsi harga Fungsi ini dipengaruhi oleh penilaian pembeli bigf, bobot ketertarikan agen terhadap harga yang ditawarkan dan fungsi kapasitas f1 . Tidak selamanya agen pembeli menginginkan produk
Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.9-545-0270-1
Negosiasi Kembali Cari penjual baru Negosiasi Tidak terpenuhi
Negosiasi
Idle
Memilih penjual Bertanya Harga+spesifikasi
Negosiasi harga
Konfirmasi potongan harga
Konfirmasi perubahan spesifikasi
Action Beli
Bertanya ke penjual untuk potongan harga
Tidak ada potongan
Negosiasi spesifikasi
Cocok Bertanya ke penjual untuk mengubah spesifikasi
Tidak diubah
Gambar 4. FSM Perilaku Agen Pembeli
3. Pembahasan Hasil Pada penelitian ini proses optimisasi multi objektif berbasis NSGA-II menggunakan sejumlah 202 sampel data. Data yang digunakan memiliki 17 kolom, Masing-masing kolom merupakan variabel yang digunakan dalam menghitung nilai fitness. Berikut potongan tabel data terlihat pada gambar 3. Keterangan gambar: Penawaran penjual (Prosesor,Memory, Hardisk) Penawaran penjual (harga) kemampuan minimal Pembeli (P, M, H) ekspektasi pembeli (P, M, H) Ekspektasi harga pembeli Harga Maksimal Pembeli Bobot pembeli terhadap P, M, H ,Bobot pembeli terhadap 2 fungsi minimal dan maksimal
Gambar 5. Data sampel
Dari data sampel yang ada diperoleh hasil observasi dari algoritma MOEA NSGA-II berupa grafik pada gambar 5. Sumbu x menunjukkan fungsi fx1 yaitu fungsi kapasitas , sumbu y menunjukkan fungsi fx2 yaitu fungsi harga. Grafik gambar 5 menunjukkan adanya hubungan linear berbanding terbalik diantara 2 fungsi tersebut. Hal ini sangat sesuai dengan formula matematis yang telah dijelaskan pada bagian 2.3.
Gambar 5. Hasil observasi dari algoritma NSGA-II
Tabel 3: Tabel Hasil Observasi p
w1
w2
b11
b12
b13
bi
fx1
fx2
1 0.6 2 0.7
0.4
1
0
0
0.75
1.18
0.12
0.3
0.4
0.5
0
0.5
0.905
0.245
3 0.8 4 0.9
0.2
1
1
1
1
0.4
0.8
0.1
0.33
0.5
0.5
1
0.68
0.42
5 0.3 6 0.6
0.7
1
0
1
0
0.88
0.12
0.4
0
1
1
1
1.04
0.36
7 0.5 8 0.3
0.5
0.33
0
1
1
1.35
0.15
0.7
0
0
0.5
1
1.67
0.03
9 0.7 10 0.2
0.3
1
1
0.5
0.2
0.43
0.63
0.8
1
0
1
0.5
1.3
0.1
Dari hasil yang ditunjukkan pada tabel diatas dibuat rule base, jika 4. Kesimpulan Dengan menggunakan MOEA NSGA II, dapat diperoleh solusi yang optimal untuk permasalahan multi objektif pada autonomous agen pembeli laptop. Sekalipun memerlukan waktu yang agak lama dalam proses eksekusi pencarian non dominat sort nya. Perilaku autonomous agen pembeli akan lebih baik lagi jika ditambahkan lebih banyak parameter seperti: waktu pengiriman, lama garansi, dan servis. Semakin banyak knowledge yang diberikan pada automonomus agen pembeli maka akan semakin akurat dalam proses pengambilan keputusan. Kedepan, penelitian ini akan dikembangkan dengan penambahan autonomous agen penjual dan diimplementasikan dalam bentuk game. 5. Penghargaan Ucapan terima kasih saya sampaikan kepada Kemendiknas yang telah menyelenggarakan Program Beasiswa Program Beasiswa Peneliti, Pencipta, Penulis, Seniman, Wartawan, Olahragawan, dan Tokoh (P3SWOT) dan telah memberikan beasiswa bagi penulis. Ucapan
Seminar Nasional Pascasarjana XI – ITS, Surabaya 27 Juli 2011 ISBN No.9-545-0270-1
terima kasih juga disampaikan pada semua pihak yang telah membantu dalam penyelesaian penelitian ini. 6. Pustaka [1] Prajitno Imam, Simulasi Pengambilan Keputusan Multi Objektif SCM Procurement menggunakan Hierarki State Machine, , Seminar Nasional MMT - ITS, 2009 [2] Claudia V.Goldman, Sarit Kraus, Onn Shehory, Agent Strategies : for sellers to satify purchase-orders, for buyer to select sellers, NSF under grant No.IIS980657, IBM. [3] R. Manjavacas, J.J Castro Schez, A Fuzzy Buyer Agent for An Automatic Negotiation Framework On ECommerce, EUSFLAT – FLA, 2005. [4] Xiaohui Li, Tomohiro Murata,Priority based Matchmaching Method of Buyer and Supplier in B2B e-marketplace Using Multi-objektif Optimization, Proceedings of International MultiConference of Engineers and Computer Scientists (IMECS) Vol.1, 2009 [5] Deswindi Leli, Kecepatan Tingkat Penerimaan dan Perilaku Konsumen terhadap produk lama yang Mengalami Perubahan dan Produk Inovasi Baru dalam Upaya Memasuki dan Merebut Pasar, Business & Management Journal Bunda Mulia Vol.3, 2007
[6] Jong-Jin Jung, Geun-Sik Jo, Brokerage between buyer and seller agents using Constraint Satisfaction Problem models, ELSIVIER. Decision Support Systems 28 2000 293–304. [7] Aravind Seshadri, Multi-Objective Optimization Using Evolutionary Algorithms (MOEA). [8] Abdullah Konak, David W. Coit, Alice E. Smith. Multi-objective optimization using genetic algorithms: A tutorial, 2006. [9] Srivanandam SN, Deepa SN. Introduction to Genetic Algorithms. ISBN 978-3-54073189-4, Springer Berlin Heidelberg New York. 2008 [10] Frederick C. Hennie, Finite-State Models for Logical Machines, Wiley, New York.
