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

-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

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