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. 

Contoh Soal Vektor dan Kecepatan

Soal 1

Sebuah pesawat berangkat dari kota B menuju kota A yang berada persis di Utara kota B dalam perjalanannya pesawat mendapat pengaruh dari arah angin yang bertiup tegak lurus arah terhadap kota A. Jika Pesawat berangkat dari kota B pukul 07.00 dan diasumsikan kecepatan pesawat konstan 300 km per jam sedangkan kecepatan angin 30 km per jam. Jam berapakah pesawat tiba di kota A (jarak kota A dan B 3000 km) !

Penyelesaian 

Perhatikan gambar berikut

Karena arah angin bergerak tegak lurus terhadap Kota A maka pesawat harus diarahkan sedemikian rupa supaya sampai kekota A. jika pesawat arahnya langsung lurus ke Kota A maka pesawat tidak akan sampai ke kota A karena angin yang bertiup kan mengakibatkan pesawat berbelok arah. Sehingga pesawat perlu diarahkan sedemikian rupa agar dapat mencapai kota A. untuk mendapatkan arah tersebut maka kita harus menghitung sudutnya, perhatikan gambar berikut :

Tan A = Kecepatan angin / kecepatan pesawat = 30/300 = 1/10. sehingga besarnya sudut A adalah sebagai Berikut : A = arctan 0.1artinya pesawat harus diarahkan ke arah barat laut sebesar arctan0.1 derajat dari sumbu y positif. kemudian resultan vektornya adalah R = (300² - 30^2)0.5 = 298.5 km perjam. Sehingga Waktu tempuhnya adalah 3000/298.5 = 10.05 jam atau jika di konversi kemenit jadi 10 jam 3 menit sehingga waktu tibanya adalah 17.03 sore

Contoh soal Kinematika

Kinematika adalah suatu ilmu yang mempelajari tentang gerakan suatu benda dengan tanpa memerdulikan sebab-sebab benda tersebut dalam bergerak. Bergerak dapat diartikan sebagai perpindahan posisi dari suatu benda terhadap titik acuan tertentu. titik acuan dalam koordinat kartesius misalnya bisa saja kita tetapka bahwa titik acuannya adalah titik asal atau titik (0,0).

Pada kesempatan kali ini kita akan membahas soal tentang posisi, kecepatan dan percepatan dari sebuah benda yang terbatas pada gerak lurus. Posisi suatu benda dapat kita tetapkan dengan notasi vektor dan begitu pula kecepatan dan percapatan bisa kita nyatakan sebagai vektor. Simak contoh soal berikut ini.

Contoh soal 1

Kecepatan didifinisikan sebagai perpindahan posisi suatu benda terhadap selang waktu tertentu. Misal diberikan posisi awal sebuah benda dalam koordinat kartesius adalah pada titik A(0.3) dan setelah waktu berlalu selama 10 detik maka posisi benda sekarang adalah di titik B(4,0) maka berapakah kecepatan benda tersebut.(asumsikan tidak ada gaya luar yang bekerja pada benda tersebut sehingga resultan gaya yang bekerja sama dengan nol)

Jawab

Pada gambar dapat kita lihat bahwa V adalah kecepatan benda, Vx dan Vy adalah uraian vektor kecepatan benda yang sesuai dengan sumbu x dan sumbu y. Kita akan hitung terlebih dahulu masing-masing kecepatan pada arah sumbu x dan sumbu y. 

kecepatan pada arah sumbu x : Vx = (perpindahan posisi pada sumbu X)/waktu  = (0-3)/10 = -0,3 m/s

kecepatan pada arah sumbu y : Vy = (perpindahan posisi pada sumbu Y)/waktu = (4-0)10 = 0.4 m/s

jadi kecepatannya adalah -0.3i + 0.4j m/s. dengan arah  α = arctan (0.4/-0.3) radian dari sumbu x positif.

catatan : kecepatan yang dimaksud pada soal ini adalah kecepatan rata-rata.

Contoh soal 2

kembali ke soal 1, berapakah besar kecepatan dan percepatanya.

jawab

Besar kecepatan dapat dicari dengan cara |R| = (-0.3² + 0.4²)^0.5 = 0.5 m/s dengan arah  α = arctan (0.4/-0.3) radian dari sumbu x positif. Karena asumsinya tidak ada gaya luar yang bekerja maka percepatan sama dengan Nol. Ingat dengan hukum kedua newton yang menyatakan suatu benda dapat dipercepat/diperlambat ketika ada gaya luar yang bekerja pada benda tersebut.

Semoga dua soal tersebut dapat membantu dan menambah pemahaman kita tentang gerakan suatu benda. dalam dunia nyata, benda-benda tidak hanya bergerak lurus tapi juga bergerak melingkar, parabola, elips, dasb.

Contoh soal momentum

Pada kesempatan kali ini, kami akan menampilkan pembahasan dari sebuah soal tentang momentum. Seperti yang kita ketahui bahwa momentum dari sebuah sistem selalu kekal, dan inilah yang dikenal dengan hukum kekekalan momentum. yang perlu diingat adalah bahwa dalam momentum yang kekal adalah sistem bukan benda yang berada pada sistem tersebut. ini artinya sebuah benda dalam sistem bisa saja momentumnya tidak kekal namun momentum sistemnya harus kekal.

Agar lebih jelas untuk memahami apa itu momentum maka akan di sajikan dua contoh soal momentum sebagai berikut :

Contoh 1.

Sebuah sistem yang terdiri dari sebuah meriam dan sebutir peluru didalamnya. Kemudian meriam menembakan peluru yang ada padanya sehingga peluru terlontar sangat jauh sekali. Pertanyaanya apakah momentum peluru kekal? jelaskan!

Jawab

Jika yang ditanya adalah momentum peluru saja maka jawabannya adalah tidak kekal. Ini bisa dijelaskan sebagai berikut. Pada awalnya peluru masih berada didalam perut meriam sehingga kecepatan awal peluru adalah nol sehingga momentumnya nol (ingat p = mv). Setelah peluru ditembakkan maka peluru akan bergerak dengan kecepata tertentu dengan arah misalnya kearah sumbu x positif. Karena setelah ditembakkan peluru mempunyai kecepatan maka peluru sekaran mempunyai momentum sehingga momentum awal peluru berbeda dengan momentum akhir peluru jadi kesimpulannya tidak kekal(tidak kekal artinya terjadi perubahan).

Contoh 2.

Dari contoh 1, apakah kejadian tersebut melanggar hukum kekekalan momentum? jelaskan!

Jawab

Kejadian tersebut tidak melanggar hukum kekekalan momentum. Yang perlu diingat adalah yang kekal bukan momentum benda didalam sistem melainkan melainkan momentum sistem secara keseluruhan. Sistem tersebut terdiri dari meriam dan peluru pada awalnya keduanya masih diam sehingga momentum awal sistem nol. Namun pada saat peluru sudah ditembakan dengan kecepatan tertentu dengan arah sumbu x positif maka peluru sudah memiliki momentum. pada saat yang bersamaan meriam juga terlontar kebelakan kearah sumbu x negatif sehingga meriam juga memiliki momentum namun karena meriam jauh lebih berat dari pada peluru maka kecepatan meriam jauh lebih kecih dari pada peluru. Karena arah kecepatan dari meriam dan peluru berlawanan maka momentumnya juga tanda yang berlawana (peluru positif meriam negatif) sehingga jika momentum peluru dan meriam dijumlahkan hasilnya harus nol sehingga momentum sistem secara keseluruhan menjadi nol. Kesimpulannya momentum awal sistem sama dengan momentum akhir sistem maka kejadian tersebut tidak berlawanan dengan hukum kekekalan momentum.

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.