Posted by : trihandoyo
Selasa, 16 April 2013
Algoritma Komputasi
1. Definisi
Algoritma
Kata
algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan
Al
Khawārizmi (hidup ± abad ke-9), sebagaimana tercantum pada
terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de
numero Indorum".
Pada
awalnya kata algorisma adalah istilah yang
merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan
menggunakan bilangan numerik arab (sebenarnya dari India). Pada abad ke-18,
istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur
atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.
2. Dalam
Matematika dan Komputasi
Algoritma
merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah
ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut
dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria
kondisi awal yang harus dipenuhi sebelum menjalankan algoritma.
Algoritma
akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam
hal ini berbeda dengan heuristik.
Algoritma
sering mempunyai langkah pengulangan (iterasi)
atau memerlukan keputusan (logika Boolean
dan perbandingan)
sampai tugasnya selesai.
Kompleksitas
dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang
dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal,
algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat
memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu
lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
3. Jenis-Jenis
Algoritma
·
Terdapat beragam klasifikasi algoritma
dan setiap klasifikasi mempunyai alasan tersendiri.
·
Salah satu cara untuk melakukan
klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode
yg diinginkan untuk mendesain algoritma.
4. Beberapa paradigma yang digunakan dalam
menyusun algoritma :
a.
Divide dan Conquer
Paradigma untuk membagi suatu permasalahan
besar menjadi permasalahan- permasalahan
yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang
mudah untuk dipecahkan. Singkatnya menyelesaikan
keseluruhan masalah dengan membagi masalah besar kemudian memecahkan permasalahan-permasalahan kecil
yang terbentuk.
b.
Dynamic Programming
Paradigma
pemrograman dinamik akan sesuai jika diinginkan pada suatu masalah yang
mengandung sub-struktur yang optimal dan mengandung beberapa bagian permasalahan yang tumpang tindih. Paradigma ini sekilas terlihat mirip dengan paradigma Divide dan Conquer,
sama-sama mencoba untuk membagi permasalahan menjadi sub-permasalahan yang lebih
kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang
dihadapi.
c.
Metode Serakah
Algoritma serakah mirip dengan
sebuah pemrograman dinamik, bedanya
jawaban dari sub-masalah tidak perlu diketahui dalam suatu tahap dan menggunakan
pilihan "serakah" apa yang dilihat terbaik pada saat itu.
5.
Desain dan
Analis Algoritma
Suatu cabang khusus dalam ilmu
komputer yang mempelajari
karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah,
terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini
algoritma dipelajari secara abstrak, terlepas dari sistem
komputer atau bahasa pemrograman yang
digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan
kriteria yang sama.
6.
Contoh
Aplikasi Sistem Informasi
Algoritma genetika adalah algoritma komputasi yang
diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk
mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”. Salah satu aplikasi
algoritma genetika yaitu pada permasalahan optimasi kombinasi, yang mendapatkan
suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak
kemungkinan solusi.
7.
Teori Dasar
Algoritma Genetika
Algoritma genetika yang dikembangkan oleh Goldberg
yaitu algoritma komputasi yang diinspirasi teori evolusi Darwin yang menyatakan
bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat : yang menang”.
Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk dapat
dipertahankan melalui proses reproduksi, crossover, dan mutasi.
Konsep dalam teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma
komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih
“alamiah”.
·
Sebuah solusi
yang dibangkitkan dalam algoritma genetika disebut sebagai chromosome.
·
Kumpulan
chromosome disebut sebagai populasi.
·
Chromosome
dibentuk dari komponen-komponen penyusun yang disebut gen dan nilainya dapat
berupa bilangan numerik, biner, simbol atau karakter tergantung dari permasalahan
yang ingin diselesaikan.
·
Chromosome
akan berevolusi secara berkelanjutan yang disebut generasi.
·
Dalam tiap generasi
chromosome dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang
ingin diselesaikan (fungsi objektif) menggunakan ukuran yang disebut fitness.
·
Untuk memilih
chromosome yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses
yang disebut seleksi. Proses seleksi chromosome menggunakan konsep
aturan evolusi Darwin yang telah disebutkan sebelumnya yang chromosome yang
mempunyai nilai fitness tinggi memiliki peluang lebih besar untuk terpilih lagi
pada generasi selanjutnya.
·
Chromosome-chromosome
baru disebut offspring, dibentuk dengan cara melakukan perkawinan antar
chromosome-chromosome dalam satu generasi yang disebut proses crossover.
·
Jumlah
chromosome dalam populasi yang mengalami crossover ditentukan oleh paramater
disebut crossover rate.
·
Mekanisme
perubahan susunan unsur penyusun mahkluk hidup akibat adanya faktor alam
disebut mutasi, direpresentasikan sebagai proses berubahnya satu atau lebih
nilai gen dalam chromosome dengan suatu nilai acak.
·
Jumlah gen dalam
populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan mutation
rate.
Setelah beberapa generasi dihasilkan
chromosome-chromosome yang nilai gen-gennya konvergen ke suatu nilai tertentu
yang merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap
permasalahan yang ingin diselesaikan.