Ilmukuilmumu

Amalkan apa yang telah kau pelajari, karena itulah sesungguhnya ilmu yang kau miliki

Teknik Optimasi

on November 12, 2009

Setiap orang pasti ingin mendapatkan yang terbaik dalam hidupnya, memaksimalkan atau mengoptimalkan apa yang dia punya untuk mendapatkan sesuatu yang lebih baik. Hal tersebut juga terjadi dalam dunia pemrograman khususnya dalam bidang algoritma pemrograman, dimana setiap algoritma yang dibuat diharapkan bisa memecahkan sebuah permasalahan yang ada dengan seoptimal mungkin. Dalam perkembangannya banyak sekali algoritma yg muncul, baik itu algoritma baru maupun algoritma hasil pengembangan dari algoritma yang sudah ada.

 

Penilaian performansi sebuah algoritma biasanya dilakukan terhadap nilai waktu yang dibutuhkan algoritma tersebut untuk berjalan (running) dan juga terhadap presisi atau keakuratan hasil dari sebuah algoritma. Kecepatan waktu pemrosesan sebuah algortima biasanya akan berbanding terbalik dengan tingkat presisi atau keakuratan hasil dari algoritmanya, dimana semakin cepat waktu yang dibutuhkan untuk running maka tingkat presisi/keakuratannya akan semakin kecil. Dan sebaliknya, ketika algoritma tersebut membutuhkan waktu yang lama untuk running maka presisi/keakuratan hasil algoritmanya akan semakin baik. Yang menjadi permasalahan sekarang adalah algoritma mana yang harus kita pilih, apakah algoritma yang memiliki nilai waktu running yang cepat atau algoritma yang memiliki tingkat presisi yang baik. Pertanyaan selanjutnya adalah apakah ada sebuah algoritma yang memiliki tingkat presisi yang baik dan sekaligus memiliki waktu running yang cepat.

 

Beberapa contoh kasus yang termasuk dalam kasus optimasi diantaranya adalah masalah TSP (Travelling Salesman Problem), MST (Minimum Spanning Tree), dan Knapsack Problem. Beberapa kasus diatas merupakan kasus yang membutuhkan teknik optimasi dalam algoritmanya, algoritma tersebut harus bisa memilih salah satu  solusi yang terbaik dari sejumlah solusi pemecahan masalah yang ada. Beberapa metode algoritma yang dipakai dalam menyelesaikan beberapa kasus optimasi diantaranya metode Brute force, Greddy, Dynamic Programming dan Monte Carlo.  Setiap metode memiliki sifat dan ciri yang berbeda-beda misalnya metode Brute Force memiliki sifat optimal akan tetapi lama dalam waktu running, Greedy memiliki sifat cepat tapi tidak optimal, Dynamic Programming memiliki sifat optimal dan agak cepat dalam waktu running, sedangkan Monte Carlo memiliki sifat mendekati optimal dan sangat cepat.

Algoritma Optimasi terbagi menjadi dua jenis, yaitu algoritma optimasi dengan pendekatan berbasis deterministic dan algoritma optimasi dengan pendekatan berbasis probabilistic. yang termasuk kedalam algoritma berbasis deterministic diantaranya State Space Search, Dynamic Programming, dan Branc and Bound. Sedangkan algoritma optimasi yang termasuk kedalam algoritma yang berbasis pendekatan probabilistic adalah algoritma Monte Carlo dengan berbagai macam turunannya.

 

Evolutionary Computation merupakan salah satu algoritma yang termasuk kedalam algoritma optimasi berbasis probabilistic. definisi dari algoritma Evolutionary Computation adalah abstraksi dari teori evolusi biologis yang digunakan untuk membuat prosedur atau metodologi optimasi, biasanya diterapkan pada komputer, yang digunakan untuk memecahkan masalah. Algoritma ini memiliki ide dasar dari bagaimana proses evolusi yang terjadi pada makhluk hidup. Yang menganggap bahwa hasil setiap evolusi itu akan membawa sesuatu menjadi lebih baik dan optimal.

 

Beberapa algoritma yang termasuk kedalam algoritma Evolutionary Computation diantaranya adalah swarm intelligence dimana algoritma ini didasarkan dari kecerdasan berkelompok. Dengan semakin banyaknya anggota kelompok dan terkumpulnya kecerdasan-kecerdasan individual maka akan menyebabkan terkumpulnya kecerdasan kelompok yang luar biasa. Beberapa yang termasuk kedalam algoritma swarm intelligent diantaranya Particel Swarm Optimization, Ant Colony Optimization, Artificial Bee Colony Optimization.

 

Particel Swarm Optimization dimulai dengan suatu populasi yang terdiri dari sejumlah individu (yang menyatakan solusi) yang dibangkitkan secara acak. Selanjutnya melakukan pencarian solusi optimum melalui perbaikan individu untuk sejumlah generasi tertentu.

 

Evolutionary Algoritm (EAs) merupakan algoritma-algoritma yang mengimplementasikan abstraksi Evolutionary Computation. Algoritma ini terinspirasi dari suatu mekanisme dalam ilmu biologi yaitu tentang mutasi, crossover, seleksi alam, dan kelangsungan hidup. Yang termasuk kedalam EAs adalah : Genetic Algorithms (GA) : binary string, Evolution Strategies (ES) : real-valued vectors, Evolutionary Programming (EP) : finite state machine, Genetic Programming (GP) : LISP trees, Differential Evolution (DE) : perkembangan dari ES, Grammatical Evolution (GE) : perkembangan GP.

 

Algoritma optimasi ini telah banyak diterapkan dalam berbagai aplikasi diantaranya untuk simulasi, Image & Graphics, Pemotongan bahan, Pengepakkan barang, Games, Penjadwalan waktu kegiatan proyek, penjadwalan perkuliahan, Instalasi jaringan telekomunikasi, dan sebagainya.

 

Masa depan dari penerapan algoritma optimasi ini masih luas cakupannya, beberapa masalah atau alasan kenapa algoritma optimasi ini digunakan diantaranya adalah bagaimana menemukan forecasting rules, membangun bargaining strategies, pemodelan ekonomi, ukuran dan kompleksitas data semakin besar, perkembangan prosesor dan memori komputer relatif lebih lambat dibandingkan kompleksitas data. Oleh karena itu, teknik optimasi algoritma  khususnya yang berbasis probabilistik sangat penting dimasa depan.


One response to “Teknik Optimasi

  1. […] https://ilmukuilmumu.wordpress.com/2009/11/12/teknik-optimasi/ http://davidliauw.com/article/apa-itu-swarm-intelligence Swarm Intelligence: From Natural to Artificial Systems Eric Bonabeau, Marco Dorigo and Guy Theraulaz Share this:TwitterFacebookLike this:SukaBe the first to like this post. Bookmark the permalink. Tinggalkan Komentar […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: