| Judul | : | CONSTRUCTION OF MIXTURE-OF-MONOCYCLIC ERLANG REPRESENTATIONS FOR PHASE-TYPE DISTRIBUTIONS |
| Abstrak | : |
Pemodelan stokastik banyak digunakan dalam berbagai bidang. Salah satu model yang banyak digunakan adalah distribusi phase-type (PH). Distribusi PH sering digunakan pada teori antrian, teori reliabilitas, pemodelan kematian, dan lain-lain. Namun, seringkali model yang dibentuk dari permasalahan nyata menjadi terlalu rumit untuk dianalisis. Oleh karena itu, perlu dilakukan penyederhanaan terhadap model yang telah dibangun.
Penyederhanaan representasi dari distribusi PH dapat dilakukan dengan membuat jumlah transisi menjadi sesedikit mungkin. Salah satu representasi yang menggunakan konsep ini adalah representasi Mixture of Monocyclic Erlang (MME). Representasi ini dibangun dari penggabungan subgenerator yang dibentuk dari pole Laplace-Stieltjes Transform (LST) dari distribusi PH awal. Pole yang berupa bilangan real akan membentuk generator distribusi eksponensial, sementara pole kompleks akan membentuk generator yang disebut generator monocyclic erlang. Generator ini berupa rangkaian state dengan total transisi keluar yang sama, dengan setiap state hanya memiliki transisi menuju state yang ada di depannya, dan satu transisi balik dari state terakhir menuju ke state pertama.
Penelitian ini akan mengembangkan teori untuk mengubah sembarang representasi dari suatu distribusi PH menjadi representasi MME berdasarkan teori dasar invariant polytope. Dalam penelitian ini juga akan dibangun sebuah aplikasi yang mengimplementasikan teori yang telah dikembangkan.
Latar belakang :
- 1. Latar Belakang
Distribusi phase-type (Distribusi PH) merupakan sebuah model yang banyak digunakan dalam pemodelan stokastik, misalnya teori antrian (Asmussen, 1992), analisis resiko (Bladt, 2005), pemodelan kematian (Liu, 2008), dan teori reliabilitas. Distribusi PH banyak digunakan, karena model ini dapat menampilkan properti dan karakter khusus dari model, yang memudahkan dalam analisis. Untuk itu, perlu dibuat suatu representasi, yang mampu menampilkan properti dan karakter tersebut.
Suatu distribusi PH terdiri dari rangkaian state dan transisi. Suatu matriks dapat dibentuk sebagai representasi dari distribusi PH tersebut, di mana setiap elemen diagonal pada matriks menunjukkan total nilai transisi keluar (total outgoing rate) dari suatu state pada distribusi PH, dan elemen lain menunjukkan transisi antar state pada distribusi PH. Representasi ini juga memuat probabilitas awal untuk setiap state. Dengan representasi yang berupa matriks, maka muncul suatu permasalahan, yaitu apabila terdapat jumlah state yang sangat banyak (state-space explosion). State-space explosion merupakan permasalahan saat melakukan komposisi, yaitu jumlah state hasil komposisi adalah hasil cross product dari jumlah state semua subsistem yang dikomposisikan.Sebagai contoh, suatu sistem mempunyai 100 state dan sistem lain mempunyai 150 state, jika dilakukan komposisi maka akan menghasilkan sebuah sistem dengan jumlah state sebanyak 15.000 buah. Apabila jumlah subsistem yang dikomposisikan semakin banyak, maka jumlah state akan bertambah dengan sangat cepat. Bentuk fungsi distribusi dan kepadatan dari suatu distribusi PH dinyatakan dalam suatu bentuk eksponensial matriks, yang dalam perhitungannya memiliki kompleksitas yang tinggi. Dengan jumlah state yang sangat banyak, tentu pemrosesan akan menjadi lambat, dan memakan banyak memori komputer yang berakibat buruk pada unjuk kerja analisis distribusi PH tersebut. Oleh karena itu sangat dibutuhkan agar jumlah state dalam suatu distribusi PH menjadi sesedikit mungkin.
Jumlah state dalam suatu distribusi PH dapat menjadi sangat banyak. Agar dapat diperoleh distribusi PH yang dapat digunakan, maka diperlukan suatu representasi, yang dapat dihitung dalam waktu yang dapat ditolerir. Untuk mencapai kondisi ini, salah satu cara yang digunakan adalah dengan mereduksi jumlah state dalam distribusi PH tersebut. Untuk itu, telah dilakukan beberapa penelitian. Aldous dan Shepp (1987) mencari batas jumlah state minimal yang diperlukan untuk suatu distribusi PH. Markovski dan Trčka (2006) menggunakan metode lumping untuk mereduksi jumlah state dalam distribusi PH. He dan Zhang (2008) meneliti mengenai algoritma untuk membentuk representasi Coxian (Cox, 1955) yang minimal dari suatu distribusi PH.
Meskipun begitu, sampai saat ini belum ada cara untuk secara pasti menghasilkan representasi minimal dari suatu distribusi PH. Oleh karena itu, muncul gagasan untuk membuat suatu distribusi PH bukan dengan jumlah state yang minimal, namun memiliki transisi sesedikit mungkin. Salah satu representasi yang dikembangkan adalah representasi yang disebut Mixture of Monocyclic Erlang (MME) oleh Mocanu dan Commault (1999). Representasi ini memiliki struktur yang sangat sederhana. State disusun secara urut menurut total transisi keluarnya. Setiap state memiliki satu transisi ke depan, yaitu ke state berikutnya. Transisi balik hanya mungkin terjadi pada rangkaian state yang memiliki total transisi keluar yang sama, yaitu dari state paling akhir menuju state paling awal dari rangkaian state yang memiliki total transisi keluar yang sama. Dengan didapatnya jumlah transisi yang sedikit, diharapkan meskipun jumlah state yang ada tidak minimal, namun waktu yang digunakan dalam pemrosesan masih dapat ditolerir.
Pengembangan representasi MME ini sebenarnya merupakan ide yang cukup baik dalam penggunaan distribusi PH. Namun sampai saat ini, belum ada aplikasi untuk membentuk representasi distribusi PH ke dalam representasi MME, yang dapat digunakan dengan mudah. Aplikasi yang telah ada sebelumnya masih memiliki banyak sekali kekurangan, baik dari segi kemudahan penggunaan, maupun dalam sisi kebenaran output. Oleh karena itu, dirasa perlu untuk melakukan pembuatan aplikasi yang mampu digunakan untuk mengubah representasi suatu distribusi PH ke dalam representasi MME, yang mudah digunakan dan menghasilkan output yang benar.
Tujuan Penelitian :
Tujuan penelitian ini adalah:
1. Mengembangkan teori yang mendasari transformasi dari sembarang representasi suatu distribusi PH ke representasi MME yang didasarkan pada teknik invariant polytope.
- Membangun suatu prototipe implementasi dari teori yang telah dikembangkan tersebut.
Luaran :
Penelitian ini ditargetkan menghasilkan luaran berupa: software untuk transformasi representasi suatu distribusi PH menjadi representasi MME dan publikasi di konferensi internasional.
Studi literatur :
Neuts (1981), memperkenalkan phase-type distribution sebagai distribusi penggunaan waktu dalam rantai Markov, yang memiliki jumlah state yang terbatas, dan time-homogeneous. Neuts memperkenalkan distribusi PH sebagai sebuah alat untuk menyatukan berbagai macam model stokastik dan untuk membangun model baru yang dapat menghasilkan analisis yang algoritmik.
O’Cinneide (1990) memberikan beberapa properti yang dimiliki oleh distribusi PH. O’Cinneide menyatakan bahwa apabila jumlah state dalam distribusi PH sama dengan nilai algebraic degree dari distribusi PH tersebut, maka distribusi PH tersebut sudah dalam representasi yang minimal. Algebraic degree didefinisikan sebagai pangkat terbesar pada polinomial penyebut dari transformasi Laplace Stieltjes (LST), di mana LST tersebut sudah tidak dapat direduksi lagi. O’Cinneide juga menyatakan bahwa suatu distribusi merupakan distribusi PH apabila density function-nya bernilai positif, serta ada satu pole real dari LST yang terbesar dari semua bagian real pada semua pole LST.
Commault dan Chemla (1996) menunjukkan bahwa jumlah state minimal yang harus dikunjungi dalam suatu distribusi PH sebelum mencapai absorbing state dapat diketahui dari pembilang dan penyebut dari transformasi Laplace Stieltjes (LST) dari distribusi PH tersebut (pembilang dan penyebut dalam LST berupa polinomial). Jumlah state minimal yang harus dikunjungi ini adalah sejumlah selisih pangkat tertinggi antara penyebut dan pembilang dari LST.
Penelitian untuk mencari representasi dari distribusi PH yang dapat digunakan dalam waktu yang dapat ditolerir masih terus dilakukan. Ada beberapa metode yang dikembangkan, yaitu mencari representasi yang memiliki jumlah state minimal, dan ada yang mencari representasi dengan jumlah transisi yang minimal. Markovski dan Trčka (2006) melakukan penelitian mengenai penggunaan metode lumping pada rantai Markov yang memiliki silent step. Prinsip kerja metode lumping pada dasarnya adalah mencari sejumlah state dengan sifat yang mirip, lalu menggabungkannya menjadi satu state tunggal tanpa mempengaruhi sifat-sifat dari rantai Markov aslinya. Sementara, silent step dalam sistem yang dinamis adalah sebuah langkah yang dianggap tidak terlihat, dan dapat dihilangkan. Pencarian representasi distribusi PH dengan jumlah state yang minimal menjadi masalah yang hingga kini belum terselesaikan. Beberapa penelitian mulai mengarah pada bagian tertentu dari distribusi PH, yaitu acyclic phase-type distribution (distribusi APH). Suatu distribusi APH didefinisikan sebagai distribusi PH yang tidak memiliki transisi balik. He dan Zhang (2006) mengembangkan suatu algoritma untuk mencari representasi bidiagonal dari suatu distribusi PH dan Matrix Exponential distribution. Algoritma yang dikembangkan ini disebut Spectral Polynomial Algorithm, dan disusun menggunakan spektrum dari representasi aslinya.
He dan Zhang (2008) merancang suatu algoritma untuk menyusun representasi Coxian yang dengan jumlah state yang minimal, untuk suatu distribusi PH, yang transformasi Laplace-Stieltjes-nya hanya memiliki pole yang berupa bilangan real.
Pulungan (2009) merancang suatu algoritma untuk mereduksi jumlah state pada distribusi APH. Prinsip kerjanya adalah dengan mengurangi state pada distribusi APH satu per satu, hingga jumlah state tidak dapat dikurangi lagi tanpa membuatnya menjadi distribusi non-PH. Algoritma ini menghasilkan representasi yang hampir pasti minimal.
Sebagai alternatif, dari representasi dengan jumlah state yang minimal, pencarian representasi dari distribusi PH yang dapat digunakan dengan waktu yang dapat ditolerir dilakukan dengan mencari representasi yang memiliki jumlah transisi yang minimal. Mocanu dan Commault (1999) merancang algoritma untuk mengubah bentuk suatu distribusi PH ke dalam suatu bentuk yang sparse, yang disebut bentuk monocyclic, serta membuktikan bahwa semua bentuk distribusi PH memiliki representasi MME (Mixture of Monocyclic Erlang) yang merupakan kombinasi dari bentuk monocyclic.
Penelitian yang akan dilakukan ini merupakan implementasi dari algoritma yang dirancang oleh Mocanu dan Commault untuk mengubah representasi dari suatu distribusi PH menjadi representasi MME. Dalam penelitiannya, Mocanu dan Commault telah membuktikan secara matematis bahwa metode yang dikembangkan berhasil membuat representasi MME dari distribusi PH yang ekuivalen dengan distribusi PH aslinya. Implementasi dari algoritma yang dirancang oleh Mocanu dan Commault ini akan memberikan verifikasi hasil, yaitu untuk melihat apakah dalam penerapannya, representasi yang dihasilkan merupakan suatu distribusi PH yang sama dengan distribusi PH aslinya.
Metode Penelitian
Metode penelitian yang digunakan pada penelitian ini dimulai dengan studi pustaka untuk mempelajari konsep-konsep mengenai distribusi PH dan representasi MME. Studi literatur dilakukan dengan mengumpulkan dan mempelajari berbagai referensi dalam bentuk buku, jurnal, laporan penelitian, dan tugas akhir, mengenai teori-teori yang dibutuhkan dalam penelitian ini. Adapun teori yang dibutuhkan meliputi teori dasar phase-type distribution, pembentukan representasi MME, dekomposisi matriks, dan perhitungan eksponensial matriks.
Bahan dan alat yang digunakan dalam penelitian ini berupa literatur-literatur, baik berupa jurnal maupun buku-buku yang berhubungan dengan distribusi PH dan representasi MME. Perangkat lunak untuk pemrograman dan seperangkat komputer merupakan komponen pendukung utama pada implementasi solusi dan pengujian solusi nantinya.
Alur besar penelitian mengacu pada tahapan pengembangan sistem yang dapat dijabarkan sebagai berikut:
- 1. Analisis masalah
Berdasarkan permasalahan utama, dilakukan analisis untuk mencari metode yang tepat untuk menyelesaikan permasalahan yang muncul dalam penyelesaian permasalahan utama. Permasalahan yang muncul dalam proses pembentukan representasi MME ini misalnya metode apa yang harus digunakan dalam pencarian akar-akar LST. Berdasarkan hasil studi literatur, terdapat beberapa macam metode yang dapat digunakan untuk menyelesaikan permasalahan-permasalahan tersebut. Analisis dilakukan untuk memilih metode yang sesuai untuk menyelesaikan permasalahan-permasalahan tersebut, dengan mempertimbangkan kemudahan implementasi, kompleksitas, dan akurasi masing-masing metode.
- 2. Penyusunan solusi
Berdasarkan hasil analisis masalah, selanjutnya dilakukan penyusunan solusi. Penyusunan solusi ini meliputi penyusunan konsep baru yang digunakan untuk mendukung kebenaran dari solusi dan penerapan konsep baru yang diperoleh ke dalam sebuah algoritma baru. Penyusunan konsep baru dilakukan dengan memperhatikan konsep-konsep matematis sehingga dapat dipertanggungjawabkan secara matematis. Sedangkan algoritma baru yang terbentuk merupakan penerapan dari konsep baru yang diperoleh.
- 3. Implementasi solusi
Tahap implementasi ini bertujuan untuk menyusun suatu aplikasi sederhana yang mampu menyediakan solusi bagi permasalahan utama, yaitu membentuk representasi MME dari PH distribution. Implementasi dilakukan dalam bentuk pemrograman dengan menggunakan bahasa pemrograman Java.
- 4. Pengujian solusi
Pengujian dilakukan untuk mengetahui kemampuan sistem dalam menyelesaikan permasalahan. Pengujian dilakukan untuk mengetahui apakah sistem mampu menyelesaikan permasalahan utama, yaitu membentuk representasi MME dari distribusi PH, serta mencari batasan dari kemampuan sistem dalam penyelesaian masalah.
