FUZZY C MEANS BERBASISKAN PERMASALAHAN OPTIMISASI MULTI OBYEKTIF SEBAGAI PENDUKUNG KEPUTUSAN CERDAS PADA NON PLAYER CHARACTER GAME BISNIS

SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009

FUZZY C MEANS BERBASISKAN PERMASALAHAN OPTIMISASI MULTI OBYEKTIF SEBAGAI PENDUKUNG KEPUTUSAN CERDAS PADA NON PLAYER CHARACTER GAME BISNIS 1,2

1

I.G.P. Asto Buditjahjanto , Mochamad Hariadi , Mauridhi Hery Purnomo

1

1

Jurusan Teknik Elektro Institut Teknologi Sepuluh Nopember, Surabaya 2 Jurusan Teknik Elektro Universitas Negeri Surabaya, Surabaya 1,2 1 1 [email protected], [email protected], [email protected] Abstrak Setiap saat perusahaan menghadapi permasalahan dalam pengambilan keputusan. Jika perusahaan salah dalam mengambil keputusan maka akan berakibat fatal akibatnya, sedangkan saat ini permasalahan sudah kompleks dan dalam bentuk permasalahan multi obyektif. Mempelajari keputusan dengan cara bermain game akan menjadi sesuatu menarik, player seolah olah bermain game padahal sambil bermain game, player juga belajar dalam mengambil keputusan. Pada penelitian ini bertujuan membuat Non Player Character (NPC) untuk bermain game bisnis produksi listrik. Dua tahap digunakan untuk mengembangkan NPC ini, yaitu tahap pertama adalah optimisasi permasalahan multi obyektif dengan menggunakan metode Nondominated Sorting Genetic Algorithm (NSGA 2) yang akan menghasilkan sekumpulan solusi optimal. Sedangkan tahap kedua adalah clustering dengan menggunakan metode Fuzzy C Means (FCM) yang berfungsi untuk memperkecil sekumpulan solusi optimal tersebut menjadi beberapa solusi optimal. Hasil simulasi dengan menggunakan NSGA 2 dengan parameter masukan populasi sebesar 50 dan generasi sebesar 200 dihasilkan solusi optimal sebanyak 50 buah. Selanjutnya solusi tersebut di-cluster oleh FCM dengan iterasi maksimum sebesar 1000 dihasilkan 5 buah nilai tengah cluster yang mewakili solusi dengan nilai error sebesar 9.9191e-007. Kata kunci : Optimisasi, Multi Obyektif, NPC, Game Bisnis, Clustering 1. Pendahuluan Saat ini hampir permasalahan pada perusahaan tidak hanya permasalahan obyektif tunggal saja, melainkan sudah multiobyektif. Permasalahan multiobyektif ini juga terjadi pada proses produksi energi listrik pada perusahaan listrik, di mana permasalahan multiobyektif tersebut adalah permasalahan economic and emission dispatch (EED). Permasalahan EED ini berkenaan dengan trade off antara minimisasi biaya produksi dengan minimisasi tingkat emisi yang dihasilkan dari pembangkit listrik. Beberapa penelitian tentang EED yang telah dilaksanakan antara lain: penelitian pada [10] menggunakan Nondominated Sorting Genetic Algorithm II (NSGA2) dalam menyelesaikan permasalahan EED ini. Penelitian pada [17] menggunakan metode multiobjective particle swarm optimization (MOPSO) dalam menyelesaikan permasalahan tersebut dan membandingkannya dengan metode Multiobjective Evolutionary Algorithm (MOEA). Di mana pada kedua penelitian tersebut kurang mendalam pembahasannya terhadap keputusan yang dihasilkan oleh metode yang diajukan mereka. Oleh karena itu masih dibutuhkan proses lebih lanjut yaitu penggunaan metode clustering untuk memperkecil keputusan yang sangat banyak dari pareto optimal set menjadi beberapa keputusan sehingga pengambil keputusan akan lebih mudah dalam menentukan keputusan yang terbaik dari beberapa keputusan tersebut. Penelitian ini membuat suatu modul NPC (Non Player Character) pada game serius berupa game

bisnis produksi listrik. Modul ini akan memberikan beberapa solusi keputusan yang dihasilkan dari proses optimisasi permasalahan multi obyektif dengan meng-cluster pareto optimal set menjadi beberapa keputusan. Keputusan yang dihasilkan NPC menjadi menarik jika dalam game, sehingga pemain game dapat bermain sambil belajar terhadap keputusan– keputusan yang telah dibuatnya. Sesuai konsep game di mana pembelajaran diperoleh melalui proses learning by doing [3,5,13], maka pemain game akan mendapat pengetahuannya dengan mengamati keputusan yang telah dibuatnya terhadap game tersebut. 2. Metode 2.1 Formulasi Permasalahan EED Permasalahan Emission and Economic Dispatch merupakan permasalahan multiobyektif untuk meminimalkan biaya bahan bakar dan emisi yang dihasilkan oleh Pembangkit Listrik. Minimalisasi biaya bahan bakar Kurva biaya bahan bakar diasumsikan untuk diperkirakan dengan fungsi kuadratik dari output daya real generator sebagai : N

F1 ( PG ) = ∑ (ai + bi PGi + ci PGi2 ) i =1

(1)

di mana, PGi merupakan output daya real dari generator ke-i ; N merupakan jumlah total generator; ai, bi, ci, koefisien kurva biaya bahan bakar dari generator ke-i, secara berurutan.

B2-13


Minimimalisasi emisi Emisi yang dihasilkan dari generator ini adalah emisi jenis Nitrogen Oksida (Nox). Emisi ini diberikan sebagai sebuah fungsi dari output generator yang merupakan jumlah kuadratik dan fungsi eksponensial seperti sebagai berikut: N

F2 (PG ) = ∑10−2 (α i + βi PGi + γ i PGi2 ) + ξi exp(λi PGi )

(2)

i=1

di mana αi, βi, γi adalah koefisien dari generator ke – i yang menggambarkan karakteristik emisi. Kendala-kendala a. Kendala Kapasitas Pembangkitan Untuk operasi stabil, output daya nyata dari tiaptiap generator dibatasi oleh batas atas dan batas bawah sebagai berikut : PGimin ≤ PGi ≤ PGimax (3) b. Kendala Keseimbangan Daya Total pembangkitan daya listrik harus memenuhi total daya permintaan listrik PD, dan rugi-rugi daya nyata pada saluran transmisi PLoss sehingga: N

∑ PGi − PD = 0

i =1

(4)

Model Matematika Permasalahan pada EED dapat dirumuskan secara matematika sebagai optimasi permasalahan multiobyektif sebagai berikut : Minimalkan [F1(PG),F2(PG)] s.t : g(PG) = 0 h(PG) ≤ 0 (5) di mana g merupakan kendala equality mewujudkan keseimbangan daya, sedangkan h adalah kendala inequality mewujudkan kapasitas generator. 3. Prinsip – prinsip dari Optimisasi Multi Obyektif Multiobjective Optimization Problems merupakan suatu proses yang secara bersamaan dalam mengoptimasi dua atau lebih obyektif (tujuan) yang berkonflik terhadap kendala – kendala tertentu. Multiobjective Optimization Problems juga sering disebut dengan optimasi multi-criteria atau optimasi multi-atribute [2,6]. Secara matematika, Multiobjective Optimization Problems dapat ditulis sebagai suatu cara untuk mencari vektor X = [x1,x2,…,xk]T yang akan memenuhi m pertidaksamaan berikut : g (X) ≥ 0, i =1,2,3,……..m. (6) i dengan kendala – kendala l persamaan : h (X) = 0, i =1,2,3………l. (7) i dan mengoptimasi vektor fungsi obyektif berikut : F[X] = [f1(X), f2(X),..........fN(X)]T (8) Di mana X =[x1, x2,……,xk]T adalah vektor dari vektor variabel keputusan. 3.1 Pareto Optimal Solution Permasalahan dalam kehidupan nyata membutuhkan optimisasi secara bersamaan dari

B2-14 beberapa hal yang tidak mungkin diukur dan sering kali pada obyektif - obyektif yang saling bertentangan. Biasanya tidak ada solusi optimal tunggal, namun ada sekumpulan alternatif dari solusi. Hal ini dikenal dengan Pareto-Optimal Solution. Untuk mendefinisikan dapat dilihat pada permasalahan peminimalan dari dua vektor keputusan yaitu x1, x2 ∈ X. Di mana x1 dikatakan mendominasi x2 jika:

∀ i = {1, 2,...... N }: f i ( x1 ) ≤ f i ( x 2 ) dan ∃ j = {1,2,...... N }: f j ( x1 ) < f j ( x2 )

(9)

Jika salah satu kondisi di atas tidak terpenuhi, solusi x1 tidak mendominasi solusi x2. Jika x1 mendominasi solusi x2, x1 disebut solusi nondominated dengan kumpulan {x1,x2}. Untuk lebih jelasnya dapat dilihat pada gambar 1. 3.2 NSGA2 Salah satu jenis Multiobjective Genetic Algorithm (MOGA) adalah Nondominated Sorting Genetic Algorithm (NSGA2) yang dikembangkan oleh N. Srinivas and Kalyanmoy Deb [8] yang merupakan modifikasi dari prosedur perankingan. Algoritma NSGA2 didasarkan pada beberapa lapisan dari klasifikasi dari individu. Sebelum seleksi ditampilkan, populasi diranking pada dasar nondomination.

Gambar 1. Diagram Alir NSGA 2

4. Fuzzy C Means Algoritma clustering fuzzy yang terkenal adalah Fuzzy C-Means (FCM) yang diperkenalkan oleh Jim Bezdek [12]. Ia memperkenalkan ide dari parameter fuzzification (m) dalam jangkauan [1,n] yang menentukan derajat ke-fuzzy-an dari cluster. Tujuan


dari algoritma FCM adalah untuk meminimalkan fungsi biaya FCM sebagai berikut : C N

J (U ,V ) = ∑ ∑ ( µij ) m xi − v j

2

j =1i =1

(10)

V={v1,v2,…,vc} merupakan pusat cluster. U = (µij)NxC adalah sebuah matrik partisi fuzzy di mana tiap anggota µij menunjukkan derajat dari keanggotaan antara data vektor xi dan cluster j. Nilai dari matrik U harus memenuhi kondisi berikut : µij ∈ [0,1] ∀i = 1,..., N ∀j − 1,..., C (11)

B2-15 Tahap selanjutnya dari game bisnis ini player akan meminta informasi dari NPC game dengan memasukkan parameter-parameter dari pembangkit. Selanjutnya NPC akan memberikan beberapa solusi keputusan kepada player. Player harus dapat menentukan pilihan dari solusi keputusan yang telah diberikan oleh NPC untuk dapat memenangkan game ini.

FCM mengeksekusi sebuah konstrain langsung dari fungsi keanggotaan fuzzy terhubung dengan masing-masing titik sebagai berikut: C

∑ µij = 1, ∀i = 1,..., N

j =1

(12)

Minimalisasi fungsi biaya J(U,V) merupakan permasalahan optimisasi nonlinier yang dapat diminimalkan dengan algoritma iteratif berikut: 1 : Inisialisasi keanggotaan matrik U dengan nilai acak sehingga kondisi (12) dan (13) dipenuhi. Pilih eksponen m dengan tepat dan kriteria penghentian. 2 : Hitung pusat cluster V menurut persamaan : m ∑ iN=1 ( µij ) xi vj = N , ∀j = 1,..., C (13) m ∑ i =1 ( µij ) 3 : Hitung jarak baru

d ij = xi − v j , ∀i = 1,..., N ; ∀j = 1,..., C 4:

(14)

Perbaharui matrik partisi fuzzy U jika dij > 0 (menunjukkan bahwa xi≠ vj)

1 (15) d ij  2 C    ∑ k =1    d ik  m − 1 5 : Jika kriteria penghentian telah terpenuhi, hentikan dan jika lain pergi ke langkah 2. Kriteria penghentian yang tepat dapat untuk mengevaluasi fungsi biaya (10) dan untuk mengetahui jika hal ini berada dibawah nilai toleransi tertentu atau jika perbaikannya dibandingkan terhadap iterasi sebelumnya adalah dibawah batas tertentu, serta jumlah maksimum dari siklus iterasi dapat digunakan sebagai kriteria penghentian.

µij =

5. Hasil dan Pembahasan Desain game bisnis produksi listrik ditunjukkan pada gambar 3, pada awal permainan player akan memilih skenario yang akan dimainkan atau dipelajarinya. Skenario yang dipilih akan dipengaruhi oleh faktor – faktor sebagai berikut : Perubahan Biaya Bahan Bakar, Permintaan Daya Listrik, Tuntutan Perusahaan untuk laba yang tinggi, Regulasi pemerintah untuk penurunan tingkat pencemaran dan Permintaan Penurunan Biaya Produksi. Selanjutnya player akan menentukan jumlah pembangkit yang dipilih, di sini player harus dapat memperhitungkan kendala – kendala dari pembangkit.

Gambar 2. Desain Game Bisnis Produksi Listrik

Hasil pilihan player ini akan dihitung dengan biaya-biaya lainnya. Scoring keputusan terhadap player akan mempertimbangkan Penalty Pencemaran Udara, Pemenuhan Kapasitas Produksi, Biaya Produksi dan Tingkat keuntungan yang akan menjadi faktor penentu kemenangan, karena jika tidak terpenuhi faktor tersebut akan mengurangi nilai dari game. Menang atau kalahnya player ini ditentukan berdasarkan ranking nilai player dalam bermain game. Bagian NPC dari game bisnis ini saja yang dibahas pada penelitian ini. Simulasi dari penelitian ini dengan menggunakan seluruh pembangkit listrik (6 buah) seperti pada tabel 1 untuk data karakteristik pembangkit listrik dan tabel 2 untuk data emisi dari


B2-16

pembangkit. Pada penelitian ini digunakan data dari sistem tes standard IEEE 6 generator 30 bus [1,10,17]. Tabel 1 Data karakteristik generator Generator No.

1 2 3 4 5 6

Generator No.

F=a+bP +cP 2 Gi Gi a

b

c

100 120 40 60 40 100

200 150 180 100 180 150

10 10 20 10 20 10

PGimax (MW)

0.05 0.05 0.05 0.05 0.05 0.05

0.5 0.6 1.0 1.2 1.0 0.6

Tabel 2 Data emisi generator E = 10 −2 (α + β PG + γPG2 ) + ξ exp( λPG )(ton / h) α

1 2 3 4 5 6

PGimin (MW)

4.091 2.543 4.258 5.326 4.258 6.131

β

γ

-5.554 -6.047 -5.094 -3.550 -5.094 -5.555

6.490 5.638 4.586 3.380 4.586 5.151

ξ 2.0E-4 5.0E-4 1.0E-6 2.0E-3 1.0E-6 1.0E-5

Gambar 3. Hasil Clustering dengan FCM λ 2.857 3.333 8.000 2.000 8.000 6.667

Modul NPC game bisnis produksi listrik ini meliputi tahap optimisasi permasalahan multi obyektif dengan menggunakan metode NSGA 2, kemudian dilanjutkan ke tahap berikutnya yaitu proses clustering dengan menggunakan metode FCM. Pada tahap optimisasi permasalahan multi obyektif dihasilkan solusi optimal yang cukup banyak. Pada tahap selanjutnya yaitu tahap clustering, FCM akan meng-cluster solusi optimal dari NSGA2 menjadi beberapa keputusan saja. Pada tahap optimisasi permasalahan multi obyektif (minimisasi biaya bahan bakar dan emisi), data masukan bagi NSGA 2 adalah dengan menggunakan populasi sebesar 50 dan generasi sebanyak 200. Hasil optimisasi permasalahan multi obyektif ditunjukkan pada gambar 4. Terdapat solusi optimal yang dihasilkan yaitu sebanyak 50 solusi. Solusi yang begitu banyak akan menyulitkan bagi player untuk menentukan keputusannya. Tahap clustering dengan menggunakan FCM akan memperkecil solusi-solusi tersebut menjadi beberapa keputusan saja. Parameter masukan bagi FCM adalah dengan menggunakan jumlah cluster sebesar 5 buah, nilai parameter fuzzification (m) sebesar 2, iterasi maksimum sebesar 1000 dan dengan toleransi error sebesar 1e-6. Hasil dari proses clustering menghasilkan 5 buah solusi yang merupakan pusat cluster dari masing – masing cluster (5 cluster), seperti yang ditunjukkan pada tabel 3. Error yang dihasilkan adalah sebesar 9.9191e-007. Dengan solusi keputusan hanya 5 buah, maka player akan lebih mudah dalam menentukan keputusannya.

Solusi keputusan yang berjumlah 5 buah, player akan dapat menentukan keputusannya dalam bermain game, jika player ingin biaya yang murah maka player akan memilih solusi yang ke -5 dengan nilai sebesar 158.5826 $/h namun dengan konsekuensi emisi yang akan dihasilkan sebesar 0.2444 (ton/h) maka player akan dapat mendapat penalty jika pencemaran yang dihasilkan melebihi ketentuan yang ditentukan dalam skenario game. Begitu pula sebaliknya jika player memperhatikan faktor lingkungan, player akan memilih solusi ke-1 dengan emisi yang paling rendah sebesar 0.1868 (ton/h) namun dengan konsekuensi biaya produksi menjadi paling besar yaitu 656.8695 $/h, maka perusahaan akan merugi karena biaya produksi yang tinggi. Jika player ingin bermain aman-aman saja maka player akan memilih solusi ke-3 dengan biaya produksi sebesar 397.7678 $/h dan emisi sebesar 0.2028 (ton/h).Sehingga diperlukan kejelian dari player dalam menentukan keputusannya untuk dapat memenangkan game bisnis ini. Tabel 3. Solusi yang dihasilkan Pusat Cluster Biaya Bahan Emisi (ton/h) Bakar ($/h) Solusi ke -1 656.8695 0.1868 Solusi ke -2 530.4855 0.1912 Solusi ke -3 397.7678 0.2028 Solusi ke -4 261.3000 0.2224 Solusi ke -5 158.5826 0.2444 Iterasi 67 Error 9.9191e-007

6. Kesimpulan Hasil penelitian menunjukkan bahwa keputusan yang dihasilkan oleh NSGA 2 sebesar 50 solusi keputusan menjadi terlalu besar bagi player untuk menentukan keputusannya. Metode clustering dengan menggunakan metode FCM akan membantu player dengan menentukan jumlah cluster yang dikehendaki, pada penelitian ini ditentukan sebesar 5 cluster. Dengan jumlah solusi keputusan yang lebih sedikit maka akan memudahkan player dalam menganalisa dan menentukan keputusannya. Clustering untuk optimasi permasalahan multi obyektif dapat digunakan sebagai pendukung keputusan bagi player dalam bermain game dalam bentuk NPC.


B2-17

Saran Penelitian ini sebatas mensimulasikan NPC pada game bisnis produksi listrik. Pada pengembangan selanjutnya dapat ditambahkan fungsi ke 3 yaitu rugi-rugi daya transmisi sehingga akan mendekati dengan permasalahan sesungguhnya. Serta sudah dalam bentuk game yang dapat dipakai untuk mempelajari keputusan dalam memainkan peranan sebagai manager produksi dalam menentukan jumlah produksi listrik dan konsekuensi dalam pemilihan keputusan keputusan tersebut.

[11]

Konak Abdullah, David W. Coit, Alice E. Smith, 2006, Multi-objective optimization using genetic algorithm : A tutorial, International Journal of Reliability Engineering and System Safety Vol 91, hal 9921007.

[12]

Kusuma. Sri, Sri Hartati, 2006, Neuro - Fuzzy Integrasi Sistem Fuzzy dan Jaringan Syaraf, Yogyakarta, Graha Ilmu.

[13]

Maja Pivec, 2004, Game-Based Learning in Universities and Lifelong Learning: UniGame: Social Skills and Knowledge Training Game Concept, Journal of Universal Computer Science, vol. 10, no. 1, hal. 14-26.

Daftar Pustaka:

[14]

Munakata Toshinori, 2008, Fundamental of the New Artificial Intelligence-Neural, Evolutionary, Fuzzy and more, second edition, Springer-Verlag London Limited.

[15]

Stapleton A., 2004, Serious Games: Serious Opportunities. Paper presented at the Australian Game Developers’ Conference, Academic Summit, Melbourne, VIC

[16]

Woods. Allen J. and Bruce F. Wollenberg, 1996, Power Generation, Operation and Control, John Willy and Son Inc

[17]

Zhao Bo, Cao Yi-jian, 2005, Multiple-obyektif particle swarm optimizatio technique for economic load dispatch, Journal of Zhejiang University SCIENCE, 2005, 6A(5), hal 420-427.

[1]

Abido. M. A, 2006, Multiobjecive Evolutionary Algorithms for Electric Power Dispatch Problem, IEEE Transaction On Evolutionary Computation, Vol.10, No 3, June 2006.

[2]

Branke Jürgen, Kalyanmoy Deb,Kaisa Miettinen, Roman Słowi´nski, (2008), Multiobyektif Optimization Interactive and Evolutionary Approaches, Berlin Heidelberg, Springer-Verlag.

[3]

Buditjahjanto I.G.P. Asto, Fressy N, Mochammad Hariadi, Mauridhi Hery Purnomo, (2008a), Using Business Games to Offer Life Skills for The Vocational High School Students, VTE Research and Networking 2008, An International Conference of Senior Administrators, Policymakers, Researchers and other Practitioners ,“Nurturing Local VTE Research Efforts: A Response to Global Challenges”, Bali, Indonesia, 7-8 July 2008.

[4]

Buditjahjanto I.G.P. Asto, Mochammad Hariadi, Mauridhi Hery Purnomo, (2008b), Using Simulated Annealing for Simulation Based Optimization on Power Plant Scheduling, The 4th International Congress on Logistics and SCM Systems, Effective Supply Chain & Logistic Management for Sustainable Development, Bangkok, THAILAND 26-28 November, 2008.

[5]

Clark Aldrich, 2005, Learning by Doing: A Comprehensive Guide to Simulations, Computer Games, and Pedagogy in e-Learning and Other Educational Experiences, John Wiley & Sons.

[6]

Coello Coello. C.A., Gary B. L, David A., 2007, Evolutionary Algorithms for Solving Multi-Obyektif Problems, second edition, Springer Science + Business Media

[7]

Deb Kalyanmoy, Tushar Goel, A Hybrid MultiObjective Evolutionary Approach to Engineering Shape Design.

[8]

Deb, K. Agarwal, S. Pratap, Meriyan. T, 2000, A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II, KanGal Report Number 200001, Indian Institute of Technology, Kanpur, India.

[9]

Hideyuki Mizuta, Yoshiki Yamagata, 2002, Transaction Cycle of Agents and Web-Based Gaming Simulation for International Emissions Trading, Proceedings of the 2002 Winter Simulation Conference, hal. 801-806.

[10]

King Robert T.F. Ah, Harry C.S. Rughooputh, Kalyanmoy Deb, Evolutionary Multi-Objective Environmental/Economic Dispatch : Stocastic vs Deterministic Approaches.

FUZZY C MEANS BERBASISKAN PERMASALAHAN OPTIMISASI MULTI OBYEKTIF SEBAGAI PENDUKUNG KEPUTUSAN CERDAS PADA NON PLAYER CHARACTER GAME BISNIS

Recommend Documents