Decision Support System

Metaheuristic Optimization – Advanced

rahmadya Algoritma, Decision Support System

Metaheuristic pengertiannya telah sedikit diulas pada postingan yang lalu. Di sini sedikit diulas metode-metode yang dapat dikatakan advanced. Namun di sini advanced tidak serta-merta untuk tingkat lanjut melainkan sekedar memberitahukan metode-metode terbaru berdasarkan artikel-artikel jurnal yang sudah diterbitkan.

Metode heuristik terkini dapat diklasifikasikan berdasarkan aliran algoritma pencariannya, antara lain:

  • Mengambil inspirasi dari sifat-sifat alami (nature)
  • Mengambil inspirasi dari sifat-sifat fisika

Sifat-sifat yang diambil dari hukum alam telah banyak diteliti di metaheuristik, tetapi yang terkini dapat dirinci sebagai berikut:

  • PSO, bersasarkan sekolompok binatang dalam mencari makan
  • Dolphin     Echolocation (DE), berdasarkan teknik sonar yang dimiliki oleh lumba-lumba
  • Big Bang-Big Crunch (BB-BC), berdasarkan teori evolusi alam
  • Cuckoo Search (CS), berdasarkan sifat burung
  • Imperialist Competitive Algorithm (ICA)

Sementara itu ada algoritma-algoritma yang diambil dari sifat fisika, antara lain:

  • Charged System Search (CSS) dan Magnetic Charged System Search (MCSS), berdasarkan hukum Coulomb dan Newton
  • Colliding Bodies Optimization (CBO), berdasarkan tumbukan satu dimensi partikel
  • Ray Optimization (RO), berdasarkan hukum refraksi cahaya (snell)

Demikian kira-kira metode advanced metaheuristic yang bisa dibaca dari literatur-literatur baik jurnal maupun buku. Sekian informasinya, mudah-mudahan bisa dijelaskan lebih detil pada postingan berikutnya.

Metaheuristic Optimization

rahmadya Decision Support System, Riset dan Penulisan

Optimalisasi (optimization) merupakan usaha menemukan hasil maksimal (maximization) atau minimal (minimization), tergantung dari kasus yang ingin dioptimalkan. Besar atau kecilnya hasil optimalisasi berdasarkan hitungan sebuah fungsi yang dikenal dengan nama fungsi objective (terkadang untuk bidang RS-GIS lebih disukai fungsi kriteria – criteria function). Secara algoritmik fungsi objektif dikenal dengan istilah fitness function. Selain itu ada batasan-batasan (constraint) tertentu dalam mencapai harga optimal dari objective tersebut.

Deterministik atau Stochastic

Untuk mencapai nilai minimal/maximal fungsi objective beragam metode sudah dikembangkan. Secara garis besar metode-metode yang ada dibagi menjadi deterministic dan stochastic. Deterministic merupakan metode lama dengan bantuan gradient, khusus untuk fungsi-fungsi kontinyu. Di sekolah dulu kita pernah menghitung nilai minimal sebuah fungsi dengan menurunkan dan menyamakannya dengan nol (dikenal dengan metode Newton). Metode stochastic muncul ketika yang akan dioptimalisasi bukan fungsi kontinyu, tidak konvergen, tidak bisa diturunkan dan aspek-aspek analitis lainnya. Beberapa literatur-literatur terkini menyebut metode stochastic dengan sebutan baru yang dikenal dengan nama metaheuristic. Pertama kali istilah ini diperkenalkan oleh Fred Glover di tahun 1986. Dalam proses pencarian, ada dua aspek yang ingin dikejar, diversifikasi (focus ke global optimal secepatnya, dikenal dengan istilah exploration), dan aspek lokalitas untuk mencari yang benar-benar optimal di suatu wilayah tertentu (dikenal dengan sebutan exploitation). Dua aspek tersebut (exploration dan exploitation) harus dikompromikan untuk menghasilkan metode heuristik yang tepat.

Metaheuristic

Metaheuristic merupakan gabungan kata Meta dan Heuristic. Heuristic artinya mencari jawaban dengan cara trial & error sementara meta berarti melampaui atau tingkat yang lebih dari. Jadi metaheuristic tidak hanya mencari jawaban dengan coba-coba saja melainkan dengan bantuan atau arahan dari faktor-faktor lain. Faktor-faktor itulah yang membuat banyaknya variasi dari metaheuristic ini. Algoritma-algoritma metaheuristic yang banyak dikenal dan diterapkan antara lain:

1. Simulated Annealing

Metode ini meniru proses pendinginan baja yang dicor. Fungsi yang digunakan adalah fungsi eksponensial:

dengan kB konstanta Boltzmann dan T adalah suhu (kelvin). E merupakan energi yang perubahannya setara dengan perubahan fungsi objektif:

Dengan gamma konstanta yang biasanya berharga 1 untuk penyederhanaan.

2. Genetic Algorithm

Algoritma genetika diperkenalkan oleh John Holland di tahun 60-an. Metode ini meniru sifat alami evolusi dimana yang adaptif adalah yang optimal. Setelah fungsi objektif ditentukan, maka serentetan algoritma bekerja mencari nilai optimal fungsi tersebut. Keunikan metode ini adalah mengkombinasikan antar nilai sementara yang diperoleh dengan kawin silang (crossover) dan mutasi. Awalnya nilai-nilai tersebut harus di-encode menjadi biner agar beberapa bitnya bisa disalingtukarkan dengan nilai lainnya dan juga untuk mutasi. Namun saat ini banyak dikembangkan metode tanpa mengkonversi bilangan tersebut menjadi biner. Pemilihannya pun (selection) berdasarkan bentuk peluang (roulette wheel) dimana nilai yang memiliki harga fitness besar akan memiliki peluang yang besar pula.

3. Differential Evolution

Differential Evolution (DE) merupakan metode pengembangan dari algoritma genetika yang diperkenalkan oleh R. Storn dan K. Price di tahun 96-97. Jika pada algoritma genetika kromosom dalam bentuk biner, DE menggunakan vektor sebagai kromosom.

Mutasi, crossover, dan selection sedikit lebih rumit dari algoritma genetika. Secara detail silahkan buka makalah aslinya.

4. Ant Colony Optimization

Metode ini meniru prinsip semut dalam usaha mencari makanan. Semut menggunakan senyawa kimia bernama pheromone ketika berjalan. Jalur yang banyak dilalui semut akan memiliki konsentrasi pheromone yang lebih banyak. Penurunan fungsi konsentarasi pheronome adalah berikut ini.

Jika ada jalur yang memiliki konsentrasi pheromone melebihi jalur yang lain maka jalur ini dikatakan favorit dan umpan balik positif berlaku di sini dan lama kelamaan berlaku kondisi “self-organized”.

5. Bee Algorithms

Sesuai dengan namanya, algoritma ini mengikuti pergerakan lebah dalam mencari sumber materi pembuatan madu. Mirip dengan semut, tawon juga mengeluarkan pheromone yang disertai dengan tarian “waggle dance”. Bee algorithm dikembangkan oleh Moritz and Southwick 1992, Craig A Tovey, Xin-She Yang, dan lain-lain.

Turunan algoritma ini cukup banyak, antara lain: honeybee algorithm, artificial bee colony, bee algorithm, virtual bee algorithm, dan honyebee mating algorithm. Banyak dikembangkan untuk optimasi posisi tertentu dalam suatu jaringan (misal server).

6. Particle Swarm Optimization

Particle Swarm Optimization (PSO) meniru pergerakan sekelompok binatang (ikan, burung, dll) dalam mencari makanan. Berbeda dengan algoritma genetika yang berganti individu (punah, baru, dan mutasi), PSO menjaga jumlah kelompok individu dan hanya perubahan posisi saja. Algoritma ini dikembangkan oleh Kennedy dan Eberhart (lihat pos yang lalu).

PSO memiliki dua nilai sebagai patokan pergerakan kerumunan: local optima dan global optima. Local optima merupakan nilai terbaik tiap individu di masa lampau (biasanya hanya sebelumnya saja) sementara global optima adalah nilai terbaik di kerumunan tersebut. Bobot antara keduanya menggambarkan karakter PSO apakah selfish atau sosialis. Selain itu langkah pergerakan menentukan karakter PSO apakah lebih tinggi daya jelajah atau lebih sempit tetapi berkualitas.

7. Tabu Search

Tabu search dikembangkan oleh Fred Glover di tahun 1970 (tapi baru dipublikasikan dalam bentuk buku di tahun 1997-an). Berbeda dengan PSO yang menggunakan data lampau satu atau dua iterasi sebelumnya, tabu search merekam seluruh data yang lampau. Manfaatnya adalah mengurangi jumlah komputasi karena data yang lama sudah ada dan tidak perlu dihitung ulang. Algoritma ini masih banyak peluang untuk dikembangkan dengan cara hybrid dengan metode lain.

8. Harmony Search

Ide dari algoritma ini adalah musik. Metode ini diperkenalkan oleh Z.W. Geem di tahun 2001. Prinsipnya adalah di tiap iterasi ada tiga jenis pencarian antara lain berdasarkan: daftar irama yang sudah terkenal dimainkan, mirim dengan yang ada dengan beberapa penekanan (pitching), dan merancang komposisi yang benar-benar baru. Pitch adjustment mengikuti pendekatan Markov Chain:

dengan b merupakan bandwidth yang mengontrol pitch adjustmant.

9. Firefly Algorithm

Metode ini dikembangkan oleh Xin-She Yang pada tahun 2008 dengan mendasari prinsip kerjanya dengan seekor kunang-kunang. Fakta unik kunang-kunang antara lain:

  • Kunang-kunang tidak memiliki jenis kelamin, interaksi dengan kunang-kunang lain tidak berdasarkan jenis kelamin.
  • Ketertarikan berdasarkan kecerahan dari cahaya. Kunang-kunang yang lebih bercahaya, lebih menarik kunang-kunang lain yang kurang bercahaya.

Kecerahan berdasarkan lanskap dari fungsi objektif-nya:

dengan beta merupakan tingkat kecerahan. Pergerakan kunang-kunang i mengikuti ketertarikan dengan kunang-kunang lain, j ditentukan dengan persamaan:

10 Advanced Method

Beberapa metode masuk kategori terkini dan sangat advanced, misalnya Cuckoo Search (CS) yang akan dibahas di lain waktu bersama-sama metode-metode terkini lainnya. Diyakini metode-metode terbaru tersebut lebih baik dari yang saat ini banyak digunakan (algoritma genetika, dan PSO). Sekian, semoga bisa membantu bagi yang tertarik dengan metode-metode optimasi metaheuristik.

Business Intelligence

rahmadya Decision Support System

Membicarakan Business Intelligence (BI), berarti membicarakan penerapan teknologi informasi untuk meningkatkan produktivitas dan daya saing sebuah organisasi. Ada salah satu makalah yang bisa diunduh gratis untuk merunut dasar-dasar istilah andalan bidang Sistem Informasi (SI) ini. Selain itu silahkan baca artikel-artikel referensi yang disitasi oleh artikel jenis review tersebut.

Singkat kata, BI memanfaatkan metode-metode baik yang lawas yang terdapat dalam Sistem Pengambil Keputusan (Decesion Support System) dengan teknologi pendukungnya seperti Data Warehouse, Machine Learning, maupun teknologi terkini yang masuk Industri 4.0 seperti Big Data, AI, dan lainya. Bagan berikut bisa dijadikan patokan framework BI:

Sebelumnya harus bisa dibedakan Online Transaction Processing (OLTP) yang bertanggung jawab terhadap data transaksi dengan Online Analytical Processing (OLAP) untuk analisis yang dipakai pada framework BI. Data Mart sangat penting untuk mendukung pengambil keputusan. Data ini memang ekstrak dari data total yang bersumber dari Data Warehouse yang menggunakan istilah Extract Transform Load (ETL) yang sumbernya bisa dari dalam dan bisa juga dari luar (internet).

Jadi BI memang luas dan melibatkan teknologi-teknologi sehingga beberapa institusi sudah menjadikan BI sebagai jurusan baru yang terpisah dari jurusan Teknik Informatika, Teknologi Informasi, maupun Sistem Informasi. Yuk, yang tertarik dengan bidang ini segera mempelajari informasi terkininya lewat jurnal-jurnal.

Merekam dan Memainkan Suara dengan Matlab (Versi Lama dan Baru)

rahmadya Decision Support System, Matlab

Banyak aplikasi cerdas dengan Matlab yang membutuhkan pengolahan sinyal suara. Sebelum mengolah, salah satu fungsi penting adalah menangkap suara yang akan diolah. Postingan berikut ini membahas fungsi-fungsi yang diperlukan untuk menangkap suara, termasuk juga membunyikan hasil tangkapan suara tersebut (untuk menguji apakah fungsi perekaman berhasil).

Versi Lama

Matlab versi 2008 (versi 7.7) sedikit berbeda dengan versi terbaru. Versi lama ini menggunakan fungsi wavrecord, wavplay, dan wavwrite yang berfungsi berturut-turut untuk merekam, memainkan dan menulis. Kode singkat berikut ini bermaksud merekam, menyimpan dan memainkan suara. Tentu saja diperlukan fasilitas mic dan speaker (biasanya sudah ada pada setiap laptop).

  • clear all;
  • fs=8000;
  • y= wavrecord(5.0*fs, fs, ‘double’); %merekam suara
  • wavwrite(y,fs,‘aiueo.wav’);        %simpan rekaman ke hardisk
  • wavplay(y,fs);                %mainkan hasil rekaman
  • figure,plot(y);                %sinyal hasil rekaman di plot

Versi 2013 ke atas (Baru)

Sebenarnya kode sebelumnya bisa digunakan, hanya saja ada pesan (warning) dari Matlab bahwa wavrecord dan wavplay sebaiknya diganti dengan audiorecorder dan audioplayer untuk merekam dan memainkan.

Ganti kode sebelumnya dengan fungsi yang terbaru berikut ini, lihat referensinya di link resminya. Disini frekuensi sampling dan parameter lainnya standar 8000 Hz dan 8 bit.

  • % Record your voice for 5 seconds.
  • recObj = audiorecorder;
  • disp(‘Start speaking.’)
  • recordblocking(recObj, 5);
  • disp(‘End of Recording.’);
  • % Play back the recording.
  • play(recObj);
  • % Store data in double-precision array.
  • myRecording = getaudiodata(recObj);
  • % Plot the waveform.
  • plot(myRecording);

Jika fungsi menangkap bisa dijalankan, maka untuk mengolah lanjut dapat dilakukan dengan mudah. Banyak terapan-terapan yang menggunakan sinyal suara, antara lain:

  • Pengenalan suara
  • Deteksi kelainan detak jantung
  • Deteksi kerusakan mesin, dll

Suara yang terekam dapat dilihat grafiknya seperti di bawah ini. Sekian, semoga postingan singkat ini bermanfaat.

Penjelasan Sederhana Jaringan Syaraf Tiruan – Kasus Logika OR

rahmadya Artificial Neural Network, Decision Support System

Dulu sempat ambil mata kuliah “Artificial Intelligent & Neuro-Fuzzy” dengan buku referensi yang digunakan adalah “Neural Network Design” karangan Hagan. Materinya cukup berat karena satu buku tersebut harus dikuasai dalam setengah semester (sampai UTS/Midterm Examination). Selain itu buku tersebut sepertinya ditujukan untuk level advance (lanjut). Postingan ini bermaksud menjelaskan secara sederhana prinsip kerja jaringan syaraf tiruan. Kasus yang dijadikan contoh adalah bagaimana jaringan syaraf tiruan (JST) sederhana mampu menjalankan Logika OR.

Gambar berikut adalah JST dengan jumlah neuron hanya satu buah. Neuron adalah sel di otak yang memiliki kemampuan menyimpan dan mentransfer informasi. Disimpan dalam bentuk bobot dan bias serta mentransfer dengan fungsi aktivasi.

W1 dan W2 adalah bobot yang mengalikan tiap input yang akan diteruskan ke neuron lainnya. Sementara itu b adalah bias yang menjumlahkan total masukan yang telah dikalikan bobot. Pada gambar di atas fungsi aktivasi belum dilibatkan. Persamaan matematis gambar di atas adalah sebagai berikut:

Dengan cara training, misal backpropagation, W dan b dapat ditemukan. Tetapi sebenarnya dengan intuisi kita dapat menemukan bahwa W1 dan W2 berharga masing-masing “1” dan biasnya “nol”. Kita coba memasukan ke persamaan y di atas diperoleh akurasi yang baik hanya saja di bagian akhir, yaitu ketika masukan X1 dan X2 kedua-duanya “1” yang seharusnya keluaran y = 1 di sini berharga “2”. Oleh karena itu diperlukan fungsi aktivasi seperti gambar di bawah ini.

Di antara ketiga fungsi aktivasi, yaitu tangen sigmoid, tangga, dan purelin, yang cocok dengan kasus kita adalah tangen sigmoid. Di sini tangga bisa diterapkan, tetapi agak sulit jika digunakan untuk backpropagation yang membutuhkan diferensiasi. Tangen sigmoid (juga log sigmoid) jika diturunkan berharga -1, mudah untuk dikalkulasi saat proses pembobotan ulang (rambat balik dari target ke input). Sementara purelin tidak cocok karena jika input 2 keluarnya akan 2 juga (jika y=x persamaan purelin-nya). Dengan menambah fungsi aktivasi sebelum ke output, nilai 2 dengan fungsi tangen sigmoid bernilai 1 sehingga sesuai dengan table kebenaran logika OR. Gambar di atas sebenarnya cuplikan video yang saya upload di youtube berikut ini:

 

 

 

Kuesioner (Questionnaire) untuk AHP

rahmadya Decision Support System, Riset dan Penulisan

Analytic Hierarchy Process (AHP) merupakan teknik untuk membandingkan satu pilihan dengan pilihan lainnya. Sangat bermanfaat bagi pengambil keputusan. Vendor terkenal yang serius mengenai hal ini adalah expert choice, yang juga menyediakan software berbayarnya. Lihat post sebelumnya. Postingan kali ini mencoba sharing tentang kuesionar yang diperlukan untuk mengisi data sebelum diolah oleh AHP yang dicetuskan pertama kali oleh L. Saaty (Saaty, 2008).

Pairwise Comparison

Terus terang saya malah belum pernah mendapatkan kuesioner dalam bahasa Indonesia. Dalam jurnal-jurnal internasional, yang sering disebutkan adalah pairwise comparison survey, yang isinya membandingkan antara satu pilihan dengan pilihan lainnya.

Survey dapat dilakukan dalam bentuk lembaran kertas ataupun online. Biasanya menggunakan Google Form, dengan tampilan yang menarik, serta mudah untuk direkap via Ms Excel. Jumlah koresponden karena ini membutuhkan pakar (expert) maka tidak perlu banyak-banyak, dan bisa di bawah sepuluh orang.

Memulai

Ada baiknya menjelaskan terlebih dahulu secara singkat masalah yang akan disurvey. Jangan lupa data tentang koresponden sangat penting untuk diketahui. Berikut tampilan awalnya.

Bagian Inti

AHP membutuhkan perbandingan satu pilihan (choice) dengan lainnya. Ada enam pilihan dengan tingkat paling rendah hingga tinggi, berturut-turut: less, equal, moderate, strong, very strong, dan extreme. Berikut contohnya:

AHP mengharuskan kondisi dimana tingkat konsistensi harus kurang dari 0.1. Ini penting untuk menjaga keanehan-keanehan dalam perbandingan. Misal tikus takut kucing, kucing takut dengan seorang ibu, dan seorang ibu takut tikus. Pada contoh di atas, Physical Health akan dibandingkan dengan Psychological Condition, Social Relationships, Environment, Economic Condition & Development, dan Access to Facilities & Services. Berikut contoh survey yang pernah saya sebar.

Minta Contoh Penulis Jurnal

Terkadang ada baiknya meminta contoh kuesioner dari seorang penulis jurnal, baik nasional maupun internasional. Walau terkadang tidak dibalas, tetapi banyak juga yang membalas dan memberikan respon. Setidaknya jika tidak memberikan sample dia menjelaskan apa isinya saja. Contoh di atas saya peroleh ketika meminta dari jurnal internasional ini (Bhatti, Tripathi, Nitivattananon, Rana, & Mozumder, 2015). Silahkan baca sumber referensi tentang AHP dari Springer ini.

Referensi:

Bhatti, S. S., Tripathi, N. K., Nitivattananon, V., Rana, I. A., & Mozumder, C. (2015). A multi-scale modeling approach for simulating urbanization in a metropolitan region. Habitat International, 50, 354–365. http://doi.org/10.1016/j.habitatint.2015.09.005

Saaty, T. L. (2008). Decision making with the analytic hierarchy process. International Journal of Services Sciences, 1(1), 83. http://doi.org/10.1504/IJSSCI.2008.017590

Link dari Google

 

Klasifikasi, Pengklusteran dan Optimasi

rahmadya Artificial Neural Network, Decision Support System, Puisi Kehidupan

Bahasa merupakan pelajaran pertama tiap manusia. Untuk mempelajari komputasi pun pertama-tama membutuhkan bahasa. Sebagai contoh adalah judul di atas yang terdiri dari tiga kata: klasifikasi (classification), pengklusteran (clustering) dan optimasi (optimization). Postingan ringan ini membahas secara gampang tiga kata di atas.

Klasifikasi

Sesuai dengan arti katanya, klasifikasi berarti memilah obyek tertentu ke dalam kelas-kelas yang sesuai. Komponen utama dari klasifikasi adalah classifier yang artinya pengklasifikasi. Jika tertarik dengan bidang ini maka akan bermain pada bagian pengklasifikasi ini. Jika menggunakan jaringan syaraf tiruan (JST) maka akan meramu bobot, bias, dan layer pada JST agar mampu mengklasifikasi suatu obyek. Jika menggunakan Support Vector Machine (SVM) meramu persamaan pemisah antara dua kelas atau banyak kelas (multi-class).
Sepertinya tidak ada masalah untuk konsep ini. Masalah muncul ketika ada konsep baru, misalnya pengklusteran.

Pengklusteran

Manusia itu makin belajar makin bertambah merasa bodoh, karena makin banyak pertanyaan yang muncul. Ketika klasifikasi tidak ada masalah dalam memahami maksudnya, munculnya konsep pengklusteran membuat pertanyaan baru di kepala, apa itu? Paling gampang memahami arti dari kluster, yaitu satu kelompok dalam area tertutup, zona, atau istilah lain yang menggambarkan kelompok yang biasanya memiliki kesamaan. Pengklusteran berarti mengelompokan beberapa obyek berdasarkan kesamaannya. Jadi harus ada obyeknya dulu, karena kalau tidak ada apa yang mau dikelompokan?

Lalu bedanya dengan klasifikasi? Penjelasan gampangnya adalah klasifikasi memisahkan berdasarkan kelas-kelas yang sudah didefinisikan dengan jelas sementara pengklusteran kelompok yang akan dipisahkan tidak didefinisikan lebih dahulu. Bisa juga dengan melatih berdasarkan data yang sudah ada kelasnya (target/label nya). Misal untuk kasus penjurusan, kita bisa saja mengklasifikasikan siswa masuk IPA jika nilai IPA nya lebih baik dari IPS dan sebaliknya untuk jurusan IPS. Sementara pengklusteran kita biarkan sistem memisahkan sekelompok siswa menjadi dua kelompok yaitu kelompok IPA dan IPS. Masalah muncul ketika mengklasifikasikan berdasarkan nilai IPA dan IPS-nya, jika guru IPAnya “Killer” sementara yg guru IPS “baik hati”, maka dengan classifier itu tidak akan ada yang masuk jurusan IPA. Sementara pengklusteran akan memisahkan siswa-siswa itu menjadi dua kelompok. Bisa saja yang nilai IPA nya misalnya 6 masuk ke kelas IPA karena nilai 6 itu udah top di sekolah itu.

Optimasi

Nah, apalagi ini? Kembali lagi sesuai dengan arti katanya optimasi berarti mencari nilai optimal. Optimal tentu saja tidak harus maksimal/minimal, apalagi ketika faktor-faktor yang ingin dicari nilai optimalnya banyak, atau dikenal dengan istilah multiobjective. Apakah bisa untuk klasifikasi? Ya paling hanya mengklasifikasikan optimal dan tidak optimal saja. Biasanya optimasi digunakan untuk mengoptimalkan classifier dalam mengklasifikasi, misal untuk JST adalah komposisi neuron, layer, dan paramter-parameter lainnya. Atau gampangnya, kalau klasifikasi mengklasifikasikan siswa-siswi ganteng dan cantik, optimasi mencari yang ter-ganteng dan ter-cantik. Sederhana bukan? Ternyata tidak juga. Banyak orang baik di negara kita, tetapi mencari beberapa yang terbaik saja ternyata malah “hang” sistemnya.