Genetic Algorithm Neural Network (GANN)

Pada kesempatan kali ini saya akan berbagi mengenai salah satu bentuk hybrid dalam metode soft computing. Seperti yang kita ketahui bahwa penerapan genetic algorithm atau algoritma genetika sangat banyak dalam bidang - bidang seperti data mining, text classification, peramalan dll. Algoritma genetika merupakan algoritma yang sangat power full dalam masalah-masalah optimalisasi. Meskipun algoritma genetika dapat diandalkan dalam masalah-masalah optimalisasi namun algoritma genetika bukanlah algoritma yang memiliki proses pembelajaran yang cukup baik.

Neural network atau jaringan saraf tiruan juga merupakan salah satu metode dalam soft computing. Penerapan jaringan saraf tiruan sangat banyak misalnya adalah untuk memproses pengenalan sidik jari, tulisan, peramalan, pemodelan dan lain sebagainya. Mesikipun jaringan saraf tiruan sangat baik dalam proses pembelajaran namun tidak seperti algoritma genetika yang handal dalam proses optimalisasi. Jadi itulah perbedaan mendasa dalam algoritma genetika dan jaringan saraf tiruan.

Karena masing-masing kelebihan dan kekurangan kedua metode tersebut maka lahirlah sebuah metode yang menggabungkan kedua metode tersebut sehingga dapat saling menghilangkan kelemahan. Metode hasil penggabungan algoritma genetika dan jaringan saraf tiruan salah satunya adalah Genetic Algorithm Neural Network (GANN). GANN diharapkan handal dalam proses-proses optimalisasi dan pembelajaran.

Ide awal GANN berangkat dari jaringan saraf tiruan yang disupport oleh algoritma genetika. Dalam GANN ada tiga pendekatan yang umumnya dilakukan pertama algoritma genetika untuk optimalisasi input-input jaringan saraf tiruan, kedua algoritma genetika digunakan untuk optimalisasi arsitektur jaringan saraf tiruan, terakhir algoritma genetika digunakan untuk optimalisasi bobot-bobot jaringan saraf tiruan.

Algoritma genetika digunakan sebagai optimalisasi input - input jaringan saraf tiruan maksudnya adalah untuk menyeleksi variabel-variabel mana saja yang dijadikan sebagai input jaringan saraf tiruan. Misalkan dalam jaringan saraf tiruan kita menggunakan 10 variabel input maka algoritma genetika dapat kita gunakan untuk memilih variabel mana saja yang dijadikan input. Tujuan akhir dari optimalisasi input jaringan saraf tiruan adalah untuk mengefisienkan waktu pemrosesan dan melihat input mana saja yang memberikan kontribusi yang signifikan.

Algoritma genetika digunakan sebagai optimalisasi arsitektur jaringan saraf tiruan maksudnya adalah untuk mencari arsitektur seperti apa yang efisien untuk jariangan saraf tiruan. Misalkan kita ingin mencari berapa banyak node di hidden layer atau berapa banyak hidden layer yang digunakan dalam arsitektur tersebut. 

Algoritma genetika digunakan sebagai optimalisasi bobot-bobot jaringan saraf tiruan. Aritnya bobot-bobot dalam jaringan sarat tiruan dioptimalisasi dan diperbaiki menggunakan algoritma genetika. Tujuannya adalah untuk mencari bobot-bobot yang optimal dalam jaringan saraf tiruan tersebut.

Itulah penjelasan sederhana dari hybrid Algoritm genetika dan jaringan saraft tiruan, semoga tulisan ini bermanfaat bagi kita semua.

sumber gambar : http://sites.psu.edu/renko/files/2013/03/dna.jpg

Genetic Algoritm dan Paralel Genetic Algoritm

Genetic algorithm merupakan algoritma yang terispirasi dari proses evaluasi yang ada di alam. Genetic algorithm diperkenalkan pertama kali oleh John Holand. Genetic algorithm merupakan algoritma yang sangat baik dalam proses-proses optimalisasi. Proses-proses optimalisasi itu misalnya seperti mencari nilai maksimal untuk suatu fungsi, mencari jalan terpendek untuk mengunjungi beberapa kota sekaligus, dan lain sebagainya. 

Seperti pada proses biologi sesungguhnya, pada genetic algorithm juga memiliki istilah-sitilah seperti kromosom, gen, individu, populasi, generasi, mutasi, dan crossover. Biasanya sebuah solusi dari suatu masalah akan direpresentasikan sebagai individu. Kumpulan dari individu tersebut disebut populasi, jadi populasi juga bisa dikatakan sebagai kumpulan dari solusi-solusi masalah yang akan dioptimasi. Untuk mencapai individu terbaik maka pada genetic algorithm koromosom-koromsom akan mengalami crossover dan mutasi sehingga akan dihasilkan individu terbaik. 

Paralel genetic algorithm digunakan agar indivu yang dihasilkan akan mencapai hasil terbaik. Salah satu motode dalam paralel genetic algorithm adalah dengan menggunakan island - island atau pulau - pulau. Setiap pulau akan diisi oleh sebuah populasi yang terdiri dari berbagai individu. Nantinya setiap individu dari setiap pulau akan dicari yang terbaik untuk mewakili masing-masing pulau. Jumlah individu perwakilan pulau bisa bervariasi bisa juga sama antar pulau tergantung kebutuhan si peneliti. Individu-individu perwakilan setiap pulau akan di seleksi dan di crossover serta di mutasi agar dapat individu yang lebih bagus lagi.

Dalam genetic algorithm terdapat sebuah isu penting yaitu waktu pencarian individu yang mamakan banyak waktu dan sumber daya. Begitu pula halnya dengan paralel genetik algorithm akan makan lebih banyak sumber daya untuk pengolahanya, sehingga sangat disarankan untuk menyesuaikan pemakaian paralel genetic algorith dengan tujuan dan sumber daya yang dimiliki dan  masalah yang dioptimalisasi. Jika masala yang akan di optimalisasi sederhana saja maka sebaiknya gunakan saja genetic algorithm. Namun juka masalah sudah cukup kompleks misalnya masalah multidimensi makan paralel genetic algorithm bisa menjadi pilihan alternatif. 

Jika kita memiliki masalah-masalah yang berhubungan dengan optimasi maka genetic algorithm merupakan metode yang cukup disarankan untuk pemecahannya. Namun kita juga bisa untuk memodifikasi dan menggabungkan genetic algorithm dengan metode-metode lainya misalnya seperti artificial neural network, logika fuzzy, simulated aneling, particle swarm, ant colony dan lain sebagainya masih banyak lagi.

Intinya dari algoritma genetika agar efisien dalam memecahkan masalah-masalah optimasi adalah kita harus kreatif dalam memodifikasi genetic algorithm. Misalnya dalam proses merepresentasikan solusi masalah menjadi kromosom atau individu. 

Ant Colony Optimization Algorithm / Algoritma Semut

Algoritma semut adalah algoritma yang baru berkembang dalam dunia komputer. Algoritma semut terinspirasi dari tingkah laku semut. Algoritma semut sangat cocok untuk masalah-masalah yang memerlukan optimalisasi.  Algoritma semut pertama kali diperkenalkan oleh Dorigo dan kawan-kawan. 

Algoritma Semut merupakaan algoritma yang terinspirasi dari alam yang bertipe phenotypic. Berbeda dengan algoritma genetika yang bertipe genotypic. Maksud dari phenotypic adalah representasi dari solusinya sudah bisa bernilai real value, biasanya kalau algoritma yang bertipe genotypic representasi solusinya masih dalam bentuk kode-kode seperti bilangan biner.

Cara kerja dari algoritma semut adalah mirip seperti tingkah laku semut yang ada di alam. Semut memiliki sebuah mekanisme yang dapat mereka gunakan agar mereka tidak tersesat dalam mencari makanan. Semut memiliki zat khusus yang bernama feromon, zat inilah yang mereka gunakan dalam menjelajah diluar sarang mereka. Zat feromon dapat mereka gunakan untuk menandai jalur yang mereka pergunakan.

Semut dalam mencari makanan diluar sarang sangat berbahaya untuk hidupnya. Oleh karena itu semut mencari jalur yang paling aman dan paling cepat untuk mereka lewat dengan aman. Biasanya semakin bagus jalur dari sarang kepusat makana maka akan semakin banyak feromon yang ada pada jalur tersebut. feromon yang dikeluarkan oleh semut itu pada hakikatnya dapat menguap, namun apabila jalur tersebut sangat bagus maka semut senantiasa mempertebal zat feromon tersebut pada jalur tersebut. Berbeda dengan jalur yang kurang bagus, biasanya feromon akan mereka biarkan menguap begitu saja sehingga apabila zat tersebut sudah menghilang maka jalur tersebut tidak akan mereka gunakan lagi.

Dari konsep tersebut maka algoritma semut sangat berguna untuk mencari solosi masalah-masalah optimasi seperti masalah NP hard. Masalah dalam NP hard yang lumayan terkenal adalah Travelling salesmen Problem (TSP). pada TSP bertujuan untuk mencari jalur terpendek untuk seorang penjual barang agar melalui setiap kota dengan jalur terpendek. 

Algoritma semut dalam TSV dapat dijelaskan dengan langkah-langkah berikut :

1. inisialisasi semua jalur dan feromon awal
2. tempatkan tiap-tiap semut pada masing-masing kota
3. ulangi langkah 3 sampai 7 jika belum habis iterasinya
4. untuk setiap semut telusuri semua kota
5. pilih jalur antara dua kota dengan mempertimbangkan feromon
6. setelah semut mengunjungi tiap kota maka lakukan pengecekan jalur terpendek
7. jika jalur terpendek baru lebih pendek dari jalur terpendek lama maka simpan jalur baru.

Demikian sekilas tentang algoritma semut. Semoga artikel singkat ini bermanfaat untuk pembaca.

Artificial Neural Network

Artificial Neural Network(ANN) atau yang sering disebut dengan jaringan saraf tiruan adalah suatu struktur yang terinspirasi dari cara kerja otak manusia. ANN memiliki cara kerja mirip dengan cara kerja otak dimana dalam ANN juga terdapat node-node yang berfungsi sama seperti pada Neuron pada otak manusia. secara umum komponen-komponen pada ANN adalah sebagai berikut :

1. Neuron,  yaitu node yang berfungsi sebagai pemproses data atau informasi yang masuk kedalam neuron, dalam sebuah neuron terdapat fungsi aktivasi yang bertugas sebagai pemroses data yang diterma. setelah melewati fungsi aktivasi maka data akan dikeluarkan sebagai output node jika memenuhi suatu kriteria tertentu. output ini bisa di terima sebagai input dari neuron lainya atau diterima sebagai solusi dari suatu masalah yang dimodelkan dengan ANN.
2. fungsi Aktivasi, yaitu fungsi yang berfungsi sebagai pengolah data yang diterima neuron. cara kerja fungsi aktivasi adalah dengan cara membandingkan dengan suatu nilai batas tertentu atau theshold. jika input yang diterima neuron inputnya kurang dari nilai batas maka outputnya tidak akan dikeluarkan oleh neuron, sebaliknya apa bila memenuhi nilai batas ini maka input kan diolah dan dijadikan output oleh neuron.

apabila suatu neuron memiliki input dari beberapa neuron maka,semua input ini jumlahkan dulu baru diolah atau dibandingkan oleh fungsi aktivasi dengan suatu nilai batas tertentu. berikut gambar tentang arsitektur ANN atau jaringan saraf tiruan :

Pada gambar diatas, ada tiga node atau neuron yang memberikan input pada node 4. Masing-masing node 1,2,3 mempunyai input yang berbeda-beda. Kemudian sebelum dibandingkan dengan sebuah fungsi aktivasi semua input itu dijumlahkan terlebih dahulu. Setelah dijumlahkan baru dibandingkan dan setelah memenuhi fungsi aktivasi tertentu baru node 4 mengeluarkan outputnya. Output ini bisa digunakan sebagai input pada neuron lainya atau output ini sudah merupakan solusi yang dicari.

ANN memiliki banyak variasi arsitektur. Arsitektur ANN yang banyak digunakan seerti backpropogation(BP), Multi Layer Perceptron(MLP), Bidirectional Associative Memory(BAM), Grup Methode of Data Handling (GMDH), dan lain sebagainya.

Algoritma-algoritma yang terispirasi dari alam

Alam memang tidak ada habisnya memberikan manfaatnya untuk kehidupan manusia. Banyak hal yang bisa diambil dari alam yang bisa dimanfaatkan manusia misalnya, obat-obatan herbal yang berasal dari alam telah lama dimanfaatkan manusia untuk penyembuhan penyakitnya. Contoh lain adalah dalam pembuaran pesawat dan helikopter yang terinspirasi dari hewan-hewan seperti burung dan capung.

Selain obat-obatan, alam juga masih banyak menginspirasi berbagai bidang kehidupan manusia. Salah satunya adalah alam telah menjadi inspirasi untuk membuat metode-metode atau algoritma-algoritma baru di bidang computing. Algoritma-algoritma yang ditemukan terbukti handal untuk menyelesaikan masalah-masalah yang sangat kompleks di bidang komputasi. Dalam tulisan ini, kita akan berkenalan dengan beberapa algoritma-algoritma yang terinspirasi dari alam. 

1. Algorima Artificial neural network. Artifiial neural network (ANN) adalah algoritma yang terispirasi dari cara kerja otak manusia. Pada otak manusia banyak terdapat neuron-neorun yang saling berhubungan satu sama lain. Nah, konsep inilah yang dipakai dalan ANN untuk mencari dan memprediksi suatu solusi dari suatu masalah komputasi. Dewasa ini banyak pengembangan dari metode ANN ini misalnya, algorima backpropogation, multi layer perceptron(MLP), grup method of data handling(GMDH) sampai dengan hybrid dengan algoritma lainya misalnya Genetic algorithm neural network(GANN),  dan fuzzy neural network(FNN) serta masih banyak lagi algoritma-algoritma yang dikembangan dari ANN. Pada ANN kelebihan utamanya dalah dalam proses belajarnya.
2. Genetic Algorithm. Genetic algorithm(GA) adalah algoritma yang di temukan oleh profesor John Holland. algoritma ini terispirasi dari proses seleksi alam pada teori evolusi Darwin, GA memiliki kelebihan dalam menyelesaikan masalah-masalah optimasi. Saat ini perkembangan GA sangat pesat sekali.
3. Defferential Evolution Algorithm. Defferential evolution(DE) algorithm  adalah algoritma yang dikembangkan dari GA. Pada DE juga terdapat proses seleksi dan mutasi serta crossover seperti pada GA, namun dengan sedikit modifikasi. DE dikembangkan oleh Storn dan Price, DE juga sangat cocok untuk masalah-masalah optimasi.
4. Ant Colony Optimization.  Ant colony optiization(ACO) adalah algoritma yang terispirasi dari pola tingkah laku semut dan koloninya. ACO dikembangkan oleh Dorigo, M., Maniezzo, V. and Colorni. inti dari algoritma ini adalah seperti pencarian jalur terpendek antara sumber makanan dan koloni semut. 
5. Particle Swarm Optimization. Particle swarm optimization(PSO) adalah algoritma yang terispirasi dari pola tingkah laku kawanan burung dan kawan ikan. Arti swarm maksudnya adalah individu yang bergerobol seperti pada kelompok burung atau ikan. Algoritma ini dikembangkan oleh Eberhart dan Kennedy.
6. Artificila Bee Colony Algorithm. Artificial bee colony (ABC) algorithm adalah algoritma yang kembangkan oleh Karaboga. prinsip utamanya adalah pengetahuan kolektif dari kumpulan lebah.

Itulah beberapa algoritma yang terinspirasi dari alam. Algoritma-algoritma ini sangat membantu dalam memecahkan masalah komputasi yang semakin kompleks. Kedepannya mungkin masih banyak algoritma-algoritma baru yang ditemukan yang terispirasi dari alam dan tentunya akan memperkaya metode komputasi modern.

Knapsack Problem dan Algoritma Genetika

Knapsack problem adalah permasalah untuk memilih n barang dari N barang yang tersedia dimana n barang tadi akan dimasukan kedalam sebuah kantong. Namun terdapat masalah dimana kekuatan kantong untuk menahan beban terbatas kekuatannya. Sehingga n barang yang terpilih harus memiliki berat maksimum namun masih bisa menahan berat dari n benda yang terpilih tadi.

sumber : vi.wikipidia.org

Untuk menyelesaikan masalah ini diperlukan sebuah metode atau algoritma untuk mencari n barang dengan berat maksimum yang dapat ditempuh tersebut. misalnya kita memiliki 10 barang dimana akan diambil beberapa barang untuk dimasukkan kedalam kantong, kita akan menggunakan algoritma genetika. Individu didifinisikan sebagai daftar barang-barang yang dimasukan kedalam kantong, misalnya diantaranya adalah (1000010000) dan (1110000001) dimana 1 dinyatakan barang masuk kedalam kantong dan 0 tidak dimasukan sehingg untuk individu petama hanya barang 1 dan 6 yang masuk sedangkan untuk individu kedua hanya barang 1,2,3 dan 10 yang akan masuk. masing-masing individu akan dihitung nilai fitnessnya dimana fungsinya menyatakan selisih antara kapasitas maksimum kantong dikurangi berat benda-benda yang akan dimasukan. Fungsi dinyatakan maksimum jika mendekati 0 dan tidak negatif. Semua individu akan di crossoverkan dan dimutasikan sehingga misalnya sampai pada generasi ke 10 maka didapat sebuah solusi optimal dengan individu terpilih (1111000011) dimana hanya barang 1,2,3,4,9 dan 10 yang hanya dimasukan.

Algoritma Genetika (genetic algorithm) dan TSP problem

Algoritma genetik adalah suatu metode yang baru ditemukan pada abad ke 20. Algoritma genetika ditemukan oleh john holland prinsip dari algoritma genetika terinspirasi dari proses seleksi alam seperti teori yang di kemukakan oleh Darwin. Dalam algoritma genetika juga dapat disebut sebagai metode pencarian yang pararel. konsep dari algoritma genetika adalah penyeleksi individu - individu dimana tiap-tiap individu mewakili sebuah solusi dari permasalahan yang diberikan. Dalam algoritma genetika terdapat dua operator utama yaitu, crossover dan  mutasi. 

Salah satu permasalahan yang dapat diselesaikan oleh algoritma genetika adalah masalah travelling salesmen problem (TSP problem). Inti dari masalah TSP ini adalah untuk menemukan rute tercepat untuk menelusuri beberapa kota dimana satu kota hanya dikunjungi satu kali.

Gambar diatas digambarkan ada 4 kota yang saling terhubung, maka akan dicari susunan kota yang akan dikunjungi dengan harapan dapat meminimumkan jarak yang ditempuh.

Pada gambar 2 akan dicari jarak terpendek dari 8 kota. kita akan generate individu-individu yang akan jadi kandidat solusi dimana tiap2 kormosom berisi gen dengan susunan kota yang akan dikunjungi, misal didifinisikan funsi fetness adalah jumlah jarak yang ditempuh dari kunjungan 8 kota. salah satu conoh kromosom adalah sebaai berikut (1,2,4,3,5,6,8,7). kita akan melakukan crossover dan mutasi namun kalau melakukan crossover biasa kita akan kesulitan karena dapat menghilangkan kunjungan kesalah satu kota dan ada kota yang di kunjungi lebih dari sekali. Solusinya kita akan melakukan order crossover. langkahnya sebagai berikut.

parent 1 : (1 2 | 3 5 4 7| 6 8)

parent 2 : (2 3 | 1 4 5 6 |7 8)

kemudian O1 nya : (- - | 3547|--)

dan O2 nya (--|1456|--)

kemudian susunan q nya 78231456 kemudian eliminasi 3 5 4 7 sehingga tersisa 8216 sehingga :

O1 : (16354782 )

dengan cara serupa untuk O2 didapat : ( 37145682)  

sehingga dengan melakukan crossover dan mutasi selama beberapa generasi akan dihasilkan solusi terbaik misalnya setelah generasi ke tujuh didapat susunan 61253478 misalnya dengan jarak minimum 20 km. 

Logika FUZZY dan Sistem Inferensi Fuzzy

Logika fuzzy sering berkaitan dengan cara kerja himpunan fuzzy. Dalam logika fuzzy, sebuah elemen dalam suatu himpunan dinyatakan dengan derajat keanggotaannya. Tidak seperti himpunan crisp, elemen dari suatu himpunan dinyatakan dengan iya atau tidak. Misalnya seekor bebek adalah angota himpunan unggas atau tidak.

Dalam logika fuzzy keanggotaan suatu elemen dalam suatu himpunan sering dinyatakan dengan derajat kebebasan. misalnya untuk suhu 39 derajat celcius, dia masuk himpunan hangat dan bisa juga masuk dalam himpunan panas, tetapi dia hanya ikut pada himpunan panas 0.2 dan pada himpunan hangat 0.8.

untuk mencari nilai/derajat keanggotaan perlu sebuah funsi keanggotaan. Fungsi keanggotan dalam logika fuzzy ada banyak. Yang sering digunakan misalnya adalah fungsi segitiga, trapesium atau gauss. untuk mendapatkan nilai/derajat keanggotaan cukup masukan nilai x ke dalam fungsi yang bersangkutan.

Sistem inferensi fuzzy adalah sekumpulan dari aturan - atauran IF - THAN yang digunakan untuk mencari nilai sesuatu. Contoh dari aturan fuzzy misalnya adalah sebagai berikut : misalkan x adalah suhu, y adalah angin, dan z adalah kelembapan udara. maka aturan fuzzy nya adalah  IF x is panas AND y is sedang THAN  z is sedang. maksudnya adalah jila suhu panas dan angin bertiup sedang maka kelembapan udara sedang.

Sistem inferensi fuzzy banyak digunakan untuk mengakuisisi dari pengetahuan seorang pakar akan sesuatu. misalnya seperti contoh diatas, kita berusaha untuk mengakuisisi pengetahuan seorang ahli cuaca untuk memprediksi kelembapan udara.