Materi tentang Simulated Annealing (SA) Algorithm dalam Kecerdasan Buatan (AI) dan Machine Learning (ML) (+ Video Materi)

Assalamu‘alaikum wr. wb.

Halo gais! Sebelumnya, kita telah membahas tentang Genetic Algorithms (GA). Sekarang, kita akan membahas tentang Simulated Annealing (SA) Algorithm dalam Artificial Intelligence dan Machine Learning.

Ilustrasi Simulated Annealing Algorithm pada AI

Sumber Materi : en.Wikipedia.org, Machinelearningplus.com, Towardsdatascience.com (Medium.com), dan Geeksforgeeks.org

MATERI

A. Pengertian Simulated Annealing (SA)

Simulated Annealing (SA) adalah teknik Probabilistik untuk mendekati optimum global dari fungsi yang diberikan. Secara khusus, ini adalah Metaheuristik untuk memperkirakan pengoptimalan global dalam ruang pencarian besar untuk masalah pengoptimalan. Ini sering digunakan ketika ruang pencarian diskrit (misalnya masalah salesman keliling, masalah Kepuasan Boolean, Prediksi Struktur Protein, dan Penjadwalan Job-shop).

Nama algoritma berasal dari anil dalam metalurgi, teknik yang melibatkan pemanasan dan pendinginan terkontrol dari suatu material untuk mengubah sifat fisiknya. Keduanya adalah atribut material yang bergantung pada energi bebas termodinamika mereka. Memanaskan dan mendinginkan material mempengaruhi suhu dan energi bebas termodinamika atau energi Gibbs. Anil simulasi dapat digunakan untuk masalah pengoptimalan komputasi yang sangat sulit di mana algoritme yang tepat gagal; meskipun biasanya mencapai solusi perkiraan minimum global, itu bisa cukup untuk banyak masalah praktis.

Masalah yang dipecahkan oleh SA saat ini dirumuskan oleh fungsi objektif dari banyak variabel, tunduk pada beberapa kendala. Dalam praktiknya, kendala dapat dihukum sebagai bagian dari fungsi tujuan.

Untuk masalah di mana menemukan perkiraan optimal global lebih penting daripada menemukan optimal lokal yang tepat dalam jumlah waktu yang tetap, Simulated Annealing mungkin lebih baik daripada algoritma eksak seperti penurunan gradien atau cabang dan ikatan.

Dalam hal pemilihan fitur :

• Kumpulan fitur mewakili susunan molekul dalam material (logam).
• Jumlah Iterasi mewakili waktu. Oleh karena itu, sebagai no. iterasi menurun penurunan suhu.
• Perubahan kinerja Prediktif antara iterasi sebelumnya dan saat ini mewakili perubahan energi material.

Setelah probabilitas penerimaan dihitung, hasilkan angka acak antara 0 – 1 dan :

• Jika Angka Acak > Probabilitas Penerimaan maka set fitur baru Ditolak dan set fitur sebelumnya akan terus digunakan.
• Jika Angka Acak < Probabilitas Penerimaan maka set fitur baru Diterima.

Dampak keacakan oleh proses ini membantu simulasi anil agar tidak terjebak pada optimum lokal dalam mencari optimum global.

B. Rumus-rumus Simulated Annealing (SA)

Inilah beberapa Rumus pada Simulated Annealing (SA)

1. Rumus untuk probabilitas penerimaan

Rumus probabilitas penerimaan adalah sebagai berikut :

Di mana :

• i = Jumlah Iterasi,
• c = Mengontrol jumlah gangguan yang dapat terjadi,
• old = Skor lama,
• new = Skor baru.

Probabilitas penerimaan dapat dipahami sebagai fungsi waktu dan perubahan kinerja dengan konstanta 'c', yang digunakan untuk mengontrol laju gangguan yang terjadi pada fitur. Biasanya, 'c' diatur menjadi 1.

2. Contoh kerja rumus probabilitas penerimaan

Pertimbangkan masalah yang dihadapi adalah mengoptimalkan akurasi model pembelajaran mesin. Asumsikan bahwa solusi sebelumnya adalah 77% dan solusi saat ini adalah 73% :

Ketika :

Jumlah iterasi i = 1 dan c = 1

iterasi i = 5 dan c = 1

Dan terakhir saat iterasi i = 10 dan c = 1

Seperti yang Anda lihat setelah 10 iterasi, probabilitas penerimaan turun menjadi 0,0055453. Jadi, sebagai no. iterasi meningkat, kemungkinan menerima solusi yang lebih buruk menurun.

C. Contoh Program Solusi pada Simulated Annealing (SA)

Inilah beberapa Contoh Program Solusi pada Simulated Annealing (SA) dengan Library (Numpy dan Matplotlib) dan Tanpa Library.

1. Tanpa menggunakan Library

Ada banyak teknik pengoptimalan lainnya, meskipun anil simulasi berguna, heuristik pengoptimalan stokastik untuk ruang pencarian diskrit yang besar di mana optimalitas diprioritaskan dari waktu ke waktu. Di bawah ini, saya telah menyertakan kerangka kerja dasar untuk anil simulasi berbasis lokasi (mungkin jenis pengoptimalan yang paling dapat diterapkan untuk anil simulasi). Tentu saja, fungsi biaya, fungsi pembangkit kandidat, dan fungsi ketetanggaan harus didefinisikan berdasarkan masalah spesifik yang ada, meskipun rutinitas pengoptimalan inti telah diterapkan.

Berikut ini adalah Contoh Program dalam Python :

import random
import math
 
 
class Solution:
    def __init__(self, CVRMSE, configuration):
        self.CVRMSE = CVRMSE
        self.config = configuration

T = 1
Tmin = 0.0001
alpha = 0.9
numIterations = 100

def genRandSol():
    # Instantiating for the sake of compilation
    a = [1, 2, 3, 4, 5]
    return Solution(-1.0, a)
 
 
def neighbor(currentSol):
    return currentSol
 
 
  
def cost(inputConfiguration):
    return -1.0
 
# Mapping from [0, M*N] --> [0,M]x[0,N]
 
 
def indexToPoints(index):
    points = [index % M, index//M]
    return points
 
 
M = 5
N = 5
sourceArray = [['X' for i in range(N)] for j in range(M)]
min = Solution(float('inf'), None)
currentSol = genRandSol()
 
while T > Tmin:
    for i in range(numIterations):
        # Reassigns global minimum accordingly
        if currentSol.CVRMSE < min.CVRMSE:
            min = currentSol
        newSol = neighbor(currentSol)
        ap = math.exp((currentSol.CVRMSE - newSol.CVRMSE)/T)
        if ap > random.uniform(0, 1):
            currentSol = newSol
    T *= alpha  # Decreases T, cooling phase
 
# Returns minimum value based on optimization
print(min.CVRMSE, "\n\n")
 
for i in range(M):
    for j in range(N):
        sourceArray[i][j] = "X"
 
# Displays
for obj in min.config:
    coord = indexToPoints(obj)
    sourceArray[coord[0]][coord[1]] = "-"
 
# Displays optimal location
for i in range(M):
    row = ""
    for j in range(N):
        row += sourceArray[i][j] + " "
    print(row)

Output :

-1.0 


X - X X X 
- X X X X 
- X X X X 
- X X X X 
- X X X X

2. Menggunakan Library (Numpy dan Matplotlib)

Pertimbangkan masalah mendaki bukit. Pertimbangkan seseorang bernama 'Mia' mencoba mendaki ke puncak bukit atau global optimum. Dalam perburuan pencarian menuju global optimum ini, atribut yang dibutuhkan adalah :

1. Area ruang pencarian. Katakanlah area menjadi [-6,6]
2. Titik awal di mana 'Mia' dapat memulai perburuan pencariannya.
3. Step_size yang akan diambil 'Mia'.
4. Jumlah upaya yang akan dilakukan 'Mia'. Pada algoritma ini akan menjadi no. iterasi.
5. Tanjakan dan tanjakan yang dia daki saat dia mencoba mencapai puncak/optimal global. Pada algoritma ini akan menjadi suhu.

Hal lain yang perlu diperhatikan di sini adalah suhu dan nomor argumen iterasi akan ditentukan sebelumnya.

Langkah-langkahnya divalidasi oleh fungsi yang disebut 'objektif'. Fungsi tujuan akan menjadi 'kuadrat dari langkah yang diambil'. Ini karena langkah-langkah yang akan diambil 'Mia' akan benar-benar acak di antara batas-batas area yang ditentukan dan itu berarti ada kemungkinan mendapatkan nilai negatif juga. Untuk menjadikannya positif, fungsi tujuan digunakan. Jika langkah baru ini lebih baik maka dia akan melanjutkan jalan itu.

Jika langkahnya tidak baik: Probabilitas penerimaan/Kriteria penerimaan Metropolis dihitung. Setelah itu, nomor acak akan dihasilkan menggunakan rand().

If random_number > Acceptance probability:
  Reject the new step
Else:
  Accept the new step

Sekedar gambaran :

Dalam kode ini, langkah-langkah yang diambil oleh 'Mia' akan menjadi nilai acak dan bukan nilai yang diumpankan pengguna. Setiap kali ada peningkatan/perbaikan dalam langkah-langkah yang diambil menuju optimal global, nilai-nilai tersebut di samping nilai sebelumnya disimpan ke dalam daftar yang disebut outputs.

Langkah awal adalah mengimpor library yang diperlukan.

from numpy import asarray, exp
from numpy.random import randn, rand, seed
from matplotlib import pyplot

Mari kita tentukan fungsi tujuan untuk mengevaluasi langkah-langkah yang diambil oleh mia.

# Fungsi tujuan adalah kuadrat dari langkah-langkah yang diambil
def objective(step):
  return step[0] ** 2

Sekarang fungsi objective telah ditentukan. 'Mia' perlu memulai perburuan pencarian dari beberapa titik, kan? Hanya jika dia memiliki titik awal dia dapat maju menuju optimal global.

Sel kode di bawah ini memberi kita titik awal acak antara rentang area ruang pencarian. Mari kita lihat juga evaluasi start_point ini.

seed(1)
area = asarray([[-6.0, 6.0]])

# area[:,0] = -6.0, area[:,1] = 6.0, ran(len(area)) menghasilkan angka acak dalam panjang area.
# panjang dari interval adalah 1.

start_point = area[:, 0] + rand( len( area ) ) * ( area[:, 1] - area[:, 0] )
print(start_point)
print('start_point=', start_point)
print('objective function evaluation of start point=',objective(start_point))

Program Lengkap dari Kode di atas :

from numpy import asarray, exp
from numpy.random import randn, rand, seed
from matplotlib import pyplot
# Fungsi tujuan adalah kuadrat dari langkah-langkah yang diambil
def objective(step):
  return step[0] ** 2
seed(1)
area = asarray([[-6.0, 6.0]])
# area[:,0] = -6.0, area[:,1] = 6.0, ran(len(area)) menghasilkan angka acak dalam panjang area.
# panjang dari interval adalah 1.
start_point = area[:, 0] + rand( len( area ) ) * ( area[:, 1] - area[:, 0] )
print(start_point)
print('start_point=', start_point)
print('objective function evaluation of start point=',objective(start_point))

Output :

[-0.99573594]
start_point = [-0.99573594]
objective function evaluation of start point = 0.9914900693154707

Sepertinya titik baru yang diperoleh (titik evaluasi fungsi objektif) lebih baik daripada titik_awal.

seed(1) adalah Pseudorandom_number_generator.

Dengan menggunakan seed(1) nomor acak yang sama akan dihasilkan setiap kali sel kode dijalankan.

Sekarang mari kita tentukan algoritma annealing yang disimulasikan sebagai sebuah fungsi. Parameter yang dibutuhkan adalah:

• Fungsi objektif.
• Area ruang pencarian.
• Jumlah iterasi.
• step_size.
• Suhu.

Setelah mendefinisikan fungsi, start_point diinisialisasi kemudian, start_point ini dievaluasi oleh fungsi tujuan dan disimpan ke dalam start_point_eval.

def sa(objective, area = ([[-6.0,6.0]]), n_iterations = 1200, step_size = 0.1, temperature = 12):
    # Generating a random start point for the search hunt
    start_point = area[:, 0] + rand( len( area ) ) * ( area[:, 1] - area[:, 0] )
    # Evaluating the start_point
    start_point_eval = objective(start_point)

Sekarang start_point dan evaluasi fungsi tujuan dari start point (start_point_eval) perlu disimpan sehingga setiap kali peningkatan terjadi, perkembangannya dapat dilihat.

# Menyimpan titik awal dan evaluasi fungsi tujuannya ke dalam mia_start_point dan mia_start_eval.
mia_start_point, mia_start_eval = start_point, start_point_eval

# Daftar kosong ini akan diperbarui seiring waktu setelah perulangan dimulai.
outputs = []

Titik awal 'Mia' dan evaluasi titik awalnya disimpan ke mia_start_point dan mia_start_eval. Keluaran adalah daftar kosong yang akan diperbarui seiring waktu setelah perulangan dimulai. Sampai sekarang, 'Mia' mulai dari satu titik dan mengevaluasi titik itu. Sekarang dia harus mengambil langkah pertamanya menuju perburuan pencariannya dan untuk melakukannya, perulangan for didefinisikan mulai dari 0 hingga nomor iterasi yang kita tentukan.

# Looping dari 0 ke nomor iterasi yang kita tentukan
for i in range(iterations):
    # First step taken by mia
    mia_step = mia_start_point + randn( len( area ) ) * step_size

Langkah pertama akan sesuai dengan distribusi Gaussian dimana rata-rata adalah titik saat ini dan standar deviasi ditentukan oleh step_size. Singkatnya, ini berarti langkah yang diambil adalah 3 * step_size dari titik saat ini.

# Mengevaluasi langkah pertama
mia_step_eval = objective(mia_step)

Titik baru yang didapat ini harus dicek apakah lebih baik dari titik yang sekarang, jika lebih baik maka ganti titik yang sekarang dengan titik yang baru. Kemudian tambahkan poin-poin baru tersebut ke dalam daftar keluaran kami. Jika poin baru lebih baik :

• Iteration count
• Previous best
• New best are printed.

# Langkah baru diperiksa apakah lebih baik dari langkah saat ini. Jika lebih baik, titik saat ini diganti dengan titik baru.
if mia_step_eval < start_point_eval:
    start_point, start_point_eval = mia_step, mia_step_eval
    # Langkah akan ditambahkan ke dalam daftar
    outputs.append(start_point_eval)
  # mencetak nomor iterasi, best_so_far dan new_best
    print('iteration Number = ',i," ", 'best_so_far = ',start_point," " ,'new_best = ',start_point_eval)

Jika poin baru bukanlah solusi yang menjanjikan, maka perbedaan antara evaluasi fungsi tujuan dari solusi saat ini (mia_step_eval) dan solusi kerja saat ini (mia_start_eval) dihitung. Salah satu cara yang populer untuk menghitung suhu adalah dengan menggunakan Metode Fast Simulated Annealing yaitu sebagai berikut :

temperature = initial_temperature / (iteration_number + 1)

difference = mia_step_eval - mia_start_eval
# Suhu dihitung
t = temperature / float(i + 1)

Variabel difference memberi kita perbedaan antara titik lama dan titik baru sehingga probabilitas penerimaan/kriteria penerimaan metropolitan dapat dihitung. Ini membantu dalam menghitung kemungkinan menerima poin dengan kinerja yang lebih buruk daripada poin saat ini.

# Probabilitas penerimaan dihitung
mac = exp(-difference / t)

Kemudian nomor acak dihasilkan menggunakan rand() dan jika Angka Acak > Probabilitas Penerimaan maka poin baru akan Ditolak dan jika Angka Acak < Probabilitas Penerimaan maka poin baru akan Diterima.

if difference < 0 or rand() < mac:
  # Menyimpan nilai
    mia_start_point, mia_start_eval = mia_step, mia_step_eval
return [start_point, start_point_eval, outputs] #indenting is outside because return belongs to 'SA' function

Langkah terakhir adalah meneruskan nilai ke Parameter Fungsi Anil (Annealing Function) yang disimulasikan.

seed(1)
# menentukan luas ruang pencarian
area = asarray([[-6.0, 6.0]])
# suhu awal
temperature = 12
# tentukan jumlah total iterasi
iterations = 1200
# tentukan step_size maksimum
step_size = 0.1
# melakukan pencarian simulated annealing
start_point, output, outputs = sa(objective, area, n_iterations, step_size, temp)

Menyatukan semua Kode ini ke dalam Satu sel kode, seperti inilah tampilan Kode akhir :

from numpy import asarray, exp
from numpy.random import randn, rand, seed
from matplotlib import pyplot
# Define objective function
def objective(step):
    return step[0] ** 2.0
# Define simulated annealing algorithm
def sa(objective, area, iterations, step_size, temperature):
    # create initial point
    start_point = area[:, 0] + rand( len( area ) ) * ( area[:, 1] - area[:, 0] )
    # evaluate initial point
    start_point_eval = objective(start_point)
    # Assign previous and new solution to previous and new_point_eval variable 
    mia_start_point, mia_start_eval = start_point, start_point_eval
    outputs = []
    for i in range(iterations):
        # First step by mia
        mia_step = mia_start_point + randn( len( area ) ) * step_size  
        mia_step_eval = objective(mia_step)
        if mia_step_eval < start_point_eval:
            start_point, start_point_eval = mia_step, mia_step_eval
      #Append the new values into the output list
            outputs.append(start_point_eval)
            print('Acceptance Criteria = %.5f' % mac," ",'iteration Number = ',i," ", 'best_so_far = ',start_point," " ,'new_best = %.5f' % start_point_eval)
        difference = mia_step_eval - mia_start_eval
        t = temperature / float(i + 1)
        # calculate Metropolis Acceptance Criterion / Acceptance Probability
        mac = exp(-difference / t)
        # check whether the new point is acceptable 
        if difference < 0 or rand() < mac:
            mia_start_point, mia_start_eval = mia_step, mia_step_eval
    return [start_point, start_point_eval, outputs]
seed(1)
# define the area of the search space
area = asarray([[-6.0, 6.0]])
# initial temperature
temperature = 12
# define the total no. of iterations
iterations = 1200
# define maximum step_size
step_size = 0.1
# perform the simulated annealing search
start_point, output, outputs = sa(objective, area, iterations, step_size, temperature)
#plotting the values
pyplot.plot(outputs, 'ro-')
pyplot.xlabel('Improvement Value')
pyplot.ylabel('Evaluation of Objective Function')
pyplot.show()

Output :

Acceptance Criteria = 0.76232   iteration Number =  37   best_so_far =  [-0.95340594]   new_best = 0.90898
Acceptance Criteria = 0.87733   iteration Number =  39   best_so_far =  [-0.91563305]   new_best = 0.83838
Acceptance Criteria = 1.44710   iteration Number =  40   best_so_far =  [-0.85680363]   new_best = 0.73411
Acceptance Criteria = 1.42798   iteration Number =  41   best_so_far =  [-0.8221177]   new_best = 0.67588
Acceptance Criteria = 1.22608   iteration Number =  42   best_so_far =  [-0.68541443]   new_best = 0.46979
Acceptance Criteria = 2.09273   iteration Number =  43   best_so_far =  [-0.61804282]   new_best = 0.38198
Acceptance Criteria = 1.16478   iteration Number =  50   best_so_far =  [-0.42564785]   new_best = 0.18118
Acceptance Criteria = 0.81414   iteration Number =  66   best_so_far =  [-0.35632231]   new_best = 0.12697
Acceptance Criteria = 1.74595   iteration Number =  67   best_so_far =  [-0.33780667]   new_best = 0.11411
Acceptance Criteria = 1.02155   iteration Number =  72   best_so_far =  [-0.3368772]   new_best = 0.11349
Acceptance Criteria = 1.20897   iteration Number =  75   best_so_far =  [-0.29671621]   new_best = 0.08804
Acceptance Criteria = 1.47133   iteration Number =  88   best_so_far =  [-0.29346186]   new_best = 0.08612
Acceptance Criteria = 1.78859   iteration Number =  89   best_so_far =  [-0.2525718]   new_best = 0.06379
Acceptance Criteria = 0.29369   iteration Number =  93   best_so_far =  [-0.20893326]   new_best = 0.04365
Acceptance Criteria = 1.68933   iteration Number =  94   best_so_far =  [-0.12724854]   new_best = 0.01619
Acceptance Criteria = 1.24284   iteration Number =  95   best_so_far =  [-0.00883141]   new_best = 0.00008
Acceptance Criteria = 0.99774   iteration Number =  102   best_so_far =  [0.00581387]   new_best = 0.00003
Acceptance Criteria = 1.05301   iteration Number =  118   best_so_far =  [0.00137051]   new_best = 0.00000
Acceptance Criteria = 0.99611   iteration Number =  138   best_so_far =  [0.0009528]   new_best = 0.00000
Acceptance Criteria = 1.33458   iteration Number =  158   best_so_far =  [-0.00047896]   new_best = 0.00000
Acceptance Criteria = 0.50157   iteration Number =  473   best_so_far =  [0.00045742]   new_best = 0.00000
Acceptance Criteria = 1.02387   iteration Number =  482   best_so_far =  [0.00010925]   new_best = 0.00000

Jadi keluaran ini menunjukkan kepada kita, di mana iterasi peningkatan terjadi, titik terbaik sebelumnya, dan titik terbaik baru. Grafik menunjukkan bahwa ada sekitar 22 perbaikan (lingkaran merah) saat algoritma mencapai optima global. Ada tempat-tempat tertentu di mana tidak ada peningkatan besar tetapi saat algoritme mencapai akhir, ada banyak peningkatan.

Ini adalah implementasi python dari algoritma anil yang disimulasikan.

Jangan ragu untuk mengubah area, step_size, dan masukan lainnya untuk melihat apa yang Anda dapatkan.

VIDEO

Untuk memahami lebih lanjut terkait dengan Simulated Annealing Algorithm, lihatlah Video-video YouTube di bawah ini.

Itulah Materi tentang Simulated Annealing (SA) Algorithms dalam Kecerdasan Buatan (AI) dan Machine Learning (ML). Mohon maaf apabila ada kesalahan apapun.

Terima Kasih 😄😘👌👍 :)

Wassalamu‘alaikum wr. wb.