Menentukan Solusi Nilai Minimum Suatu Fungsi Dengan Algoritma Sa

𝕸𝖆𝖘 𝕬𝖓𝖉𝖞 𝕯𝖎𝖌𝖎𝖙𝖆𝖑 𝕸𝖊𝖉𝖎𝖆

3 min read

·

Apr 16, 2025

64

Share

Menentukan Solusi Nilai Minimum Suatu Fungsi Dengan Algoritma Simulated Annealing (SA)

Algoritma Simulated Annealing (SA) merupakan teknik metaheuristik yang terinspirasi dari proses pendinginan logam dalam metalurgi. Teknik ini efektif dalam mencari solusi nilai minimum suatu fungsi, khususnya untuk masalah optimasi kompleks dengan ruang pencarian yang luas dan banyak minimum lokal. Artikel ini akan menjelaskan langkah-langkah lengkap dalam menentukan solusi nilai minimum suatu fungsi dengan algoritma SA.

Memahami Konsep Dasar Simulated Annealing

SA mensimulasikan proses pendinginan logam secara perlahan. Pada suhu tinggi, logam memiliki energi tinggi dan atom-atomnya bergerak secara acak. Seiring penurunan suhu, pergerakan atom menjadi lebih terbatas dan logam mencapai keadaan energi terendah (kristal). Analogi ini diterapkan dalam algoritma SA untuk mencari solusi optimal:

• Suhu (T): Parameter kontrol yang menentukan probabilitas penerimaan solusi yang lebih buruk. Suhu tinggi memungkinkan penerimaan solusi yang lebih buruk, sementara suhu rendah hanya menerima solusi yang lebih baik.
• Energi (E): Nilai fungsi objektif yang ingin diminimumkan. Solusi yang lebih baik memiliki energi yang lebih rendah.
• Probabilitas Penerimaan: Probabilitas untuk menerima solusi baru yang mungkin lebih buruk, dihitung berdasarkan selisih energi dan suhu saat ini.

Langkah-langkah Implementasi Algoritma Simulated Annealing

Berikut langkah-langkah implementasi algoritma SA untuk mencari nilai minimum suatu fungsi:

1. Inisialisasi:

   • Tentukan fungsi objektif f(x) yang ingin diminimumkan.
   • Tentukan suhu awal T_0. Suhu awal yang tinggi memungkinkan eksplorasi ruang pencarian yang lebih luas.
   • Tentukan laju pendinginan α (0 < α < 1). Laju pendinginan menentukan seberapa cepat suhu menurun. Nilai α yang kecil menyebabkan pendinginan lambat dan pencarian yang lebih menyeluruh, sementara nilai α yang besar menyebabkan pendinginan cepat dan pencarian yang lebih cepat tetapi mungkin kurang optimal.
   • Tentukan kriteria berhenti, misalnya jumlah iterasi maksimum atau perubahan energi yang sangat kecil.
   • Bangkitkan solusi awal x_0 secara acak.

2. Iterasi:

   • Bangkitkan solusi baru: Bangkitkan solusi baru x_new di sekitar solusi saat ini x_current dengan menambahkan gangguan acak. Besarnya gangguan acak bisa disesuaikan.
   • Hitung perubahan energi: Hitung perubahan energi ΔE = f(x_new) - f(x_current).
   • Penerimaan solusi:
     • Jika ΔE ≤ 0 (solusi baru lebih baik), terima solusi baru (x_current = x_new).
     • Jika ΔE > 0 (solusi baru lebih buruk), terima solusi baru dengan probabilitas P = exp(-ΔE/T). Probabilitas ini akan semakin kecil seiring dengan penurunan suhu. Anda bisa menggunakan fungsi random number generator untuk menentukan apakah solusi baru diterima atau tidak.
   • Penurunan suhu: Kurangi suhu T = αT.
   • Ulangi langkah 2 sampai kriteria berhenti terpenuhi.

3. Solusi Optimal: Setelah kriteria berhenti terpenuhi, solusi x_current yang memiliki nilai fungsi objektif terendah dianggap sebagai solusi nilai minimum yang telah ditemukan.

Contoh Implementasi Sederhana (Python)

Berikut contoh implementasi sederhana dalam Python (tanpa library khusus) untuk menggambarkan konsep:

import random
import math

def simulated_annealing(f, x0, T0, alpha, iterations):
    x_current = x0
    T = T0
    min_x = x_current
    min_f = f(x_current)

    for i in range(iterations):
        x_new = x_current + random.uniform(-1, 1) # Contoh gangguan acak
        delta_e = f(x_new) - f(x_current)

        if delta_e <= 0:
            x_current = x_new
        else:
            probability = math.exp(-delta_e / T)
            if random.random() < probability:
                x_current = x_new

        if f(x_current) < min_f:
            min_f = f(x_current)
            min_x = x_current

        T *= alpha

    return min_x, min_f


# Contoh fungsi objektif (parabola)
def objective_function(x):
    return x**2

# Parameter SA
x0 = 10  # Titik awal
T0 = 100 # Suhu awal
alpha = 0.95 # Laju pendinginan
iterations = 1000 # Iterasi

# Menjalankan SA
min_x, min_f = simulated_annealing(objective_function, x0, T0, alpha, iterations)

print(f"Minimum ditemukan di x = {min_x}, dengan nilai f(x) = {min_f}")

Kesimpulan

Algoritma Simulated Annealing (SA) merupakan teknik yang ampuh untuk menyelesaikan masalah optimasi kompleks. Keberhasilan penerapannya bergantung pada pemilihan parameter yang tepat, seperti suhu awal, laju pendinginan, dan kriteria berhenti. Eksperimen dan penyesuaian parameter diperlukan untuk mendapatkan hasil yang optimal untuk setiap masalah spesifik. Semoga penjelasan ini membantu Anda memahami dan mengimplementasikan algoritma SA.