NAMA : NI LUH KARMILA SARI

NIM : 08021181621064
TUGAS : GEOFISIKA INVERSI
DOSEN PENGAMPU : M. YUSUF NUR KHAHIM, Ph. D

1. Algoritma Simulated Annealing (SA)

Algoritma SA diperkenalkan oleh Metropolis et al. pada tahun 1953. Simulated
Annealing dikembangkan berdasarkan ide dari mekanisme perilaku pendinginan dan
proses kristalisasi (annealing) material panas. Algoritma ini melakukan peningkatan
iteratif untuk memperbaiki solusi yang dihasilkan teknik-teknik penjadwalan heuristik,
dalam hal ini adalah sebuah solusi awal yang dibuat dengan teknik heuristik ataupun
random, diiterasi secara berulang dengan metode annealing dengan menggunakan
perturbasi lokal hingga tidak ada peningkatan lagi atau hingga jumlah iterasi yang
diinginkan sudah dicapai.
Struktur algoritma simulated annealing secara umum adalah sebagai berikut
(Widyadana dan Pamungkas, 2002) :
1. Cari solusi awal S menggunakan parameter awal dan metode heuristik awal
yang dapat ditentukan sendiri.
2. Tetapkan suatu nilai temperatur awal T yang cukup tinggi, dimana T > 0
3. Pada keadaan tidak frozen, lakukan:
a. Lakukan L kali :
i. Cari solusi neighbourhood S’ dari S menggunakan metode yang dapat
ditetapkan sendiri.
ii. Ä = Nilai objektif (S’) – Nilai objektif (S).
iii. Jika Ä<0, maka tetapkan S=S’, jika tidak maka tetapkan S=S’ dengan
probabilitas exp(-Ä/T).
b. T = r x T, dimana r adalah faktor reduksi suhu.
4. Dapatkan solusi optimal.
Parameter awal yang diperlukan:
• Temperatur Awal, merupakan penanda awal iterasi. Dimana nanti
temperatur awal ini akan terus berkurang hingga mencapai temperatur akhir.
 • Temperatur Akhir, merupakan batas akhir penanda iterasi sudah dapat
dihentikan.
• Faktor Reduksi Suhu, merupakan angka yang digunakan untuk menurunkan
suhu secara bertahap dan terkendali.
• Angka replikasi, merupakan angka yang menunjukkan berapa kali loop
dalam harus dilakukan sebelum menurunkan suhu (Widyadana dan
Pamungkas, 2002).
Kelebihan simulated annealing dibandingkan dengan metode lain adalah
kemampuannya untuk menghindari jebakan optimal lokal. Algoritmanya merupakan
algoritma pencarian acak, tetapi tidak hanya menerima nilai obyektif yang selalu turun,
melainkan terkadang menerima nilai obyektif yang naik juga.
2. Algoritma Genetika (GA)
Algoritma Genetika (AG) adalah suatu algoritma pencarian yang berbasis pada
mekanisme seleksi alam dan genetika. Algoritma genetika merupakan salah satu
algoritma yang sangat tepat digunakan dalam menyelesaikan masalah optimasi
kompleks, yang sulit dilakukan oleh metode konvensional. Sifat algoritma genetika
adalah mencari kemungkinan - kemungkinan dari calon solusi untuk mendapatkan yang
optimal bagi penyelesaian masalah. Ruang cakupan dari semua solusi yang layak, yaitu
obyek-obyek di antara solusi yang sesuai, dinamakan ruang pencarian. Tiap titik dalam
ruang pencarian mempresentasikan suatu solusi yang layak. Tiap solusi yang layak
dapat ditandai dengan nilai fitness. Algoritma genetika bergerak dari suatu populasi
kromosom (bit string yang direpresentasikan sebagai calon solusi suatu masalah) ke
populasi baru dengan menggunakan 3 operator yaitu seleksi, crossover dan mutasi.
Kromosom-kromosom yang diseleksi menurut nilai fitness masing-masing. Kromosom
yang kuat mempunyai kemungkinan tinggi untuk bertahan hidup pada generasi
berikutnya, tetapi tidak menutup kemungkinan juga bagi kromosom lemah untuk tetap
bertahan hidup. Proses seleksi tersebut kemudian ditentukan oleh kromosom-kromosom
baru (offspring) melalui proses crossover dan mutasi dari kromosom yang terpilih
(parents). Dari dua proses tersebut di atas maka terbentuk suatu generasi baru yang akan
diulangi terus-menerus hingga mencapai suatu konvergensi, yaitu sebanyak generasi
yang diinginkan.
 Algoritma genetika secara umum dapat diilustrasikan dalam diagram alir berikut
ini:

Gambar 1. Diagram Alir Algoritma Genetika.

Algoritma genetika memberikan suatu pilihan bagi penentuan nilai parameter
dengan meniru cara reproduksi genetika, pembentukan kromosom baru serta seleksi
alami seperti yang terjadi pada makhluk hidup. Variabel dan parameter yang digunakan
pada algoritma genetika adalah:
a. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk
menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin
dicapai.
b. Populasi jumlah individu yang dilibatkan pada setiap generasi.
c. Probabilitas terjadinya persilangan (crossover) pada suatu generasi.
d. Probabilitas terjadinya mutasi pada setiap individu.
e. Jumlah generasi yang akan dibentuk yang menentukan lama penerapan AG
(Krisnandi dan Agung, 2017).