Penerapan Algoritma Genetik: Mencari Parameter Untuk Meminimalkan Fungsi Toytest

Apa itu fungsi Toytest? Fungsi toytest adalah suatu fungsi atau persamaan untuk mengetes performa algoritma yang ingin kita pakai, dalam hal ini algoritma optimasi. Ada banyak jenis fungsi toytest yang contoh-contoh bisa dilihat pada link ini.

Dari daftar fungsi-fungsi pada link yang diberikan tersebut, kita memilih fungsi booth yang bentuknya adalah sebagai berikut

Di sini kita mencoba untuk mencari nilai x dan y agar keluaran fungsi ini mencapai nilai yang sekecil mungkin yaitu 0. Sehingga, fitness function kita adalah fungsi booth dan fitness yang paling baik adalah nilai fitness yang paling kecil. Nilai x dan y untuk mendapatkan keluaran 0 dari fungsi ini adalah 1 dan 3. Kita akan mencari nilai 1 dan 3 ini melalu algoritma genetik dengan "wilayah pencarian" atau search domain dari -10 dan 10.

Script yang kita gunakan untuk mencari nilai-nilai tersebut adalah dibawah ini

	#!/usr/bin/python
	#created by @genomexyz
	import numpy as np
	import random
	#setting
	iterasi = 1000
	pool = 100
	ubound = 10.
	dbound = -10.
	survive = 30
	mutate = 0.2
	target = 0
	errtarget = 0.00000001
	#search for the lowest val
	def fitness(x, y):
	#booth function
	#global minimum f(1,3) = 0, search area -10 10
	return (x + 2*y + -7)**2.0 + (2*x + y - 5)**2.0
	def breeding(xy1, xy2):
	b1 = random.uniform(0,1)
	return (1.0-b1) * xy1 + b1 * xy2
	def mutation(xy):
	return xy*random.uniform(0.9,1)
	print fitness(10,10)
	print breeding(10,7)
	#print random.randrange(0,10)
	#print random.uniform(0,1)
	#################
	#init population#
	#################
	population = []
	for i in xrange(pool):
	population.append([random.uniform(dbound., ubound), random.uniform(dbound., ubound)])
	population = np.asarray(population)
	#real action
	for iterator in xrange(iterasi):
	###############
	#check fitness#
	###############
	populationfit = np.zeros((pool))
	for i in xrange(pool):
	populationfit[i] = fitness(population[i,0], population[i,1])
	rankfit = np.argsort(populationfit)
	#check fitness, is this the solution we want?
	print 'solution in in iteration ', iterator
	print population[rankfit[0]]
	print 'fitness', rankfit[0]
	if abs(rankfit[0]-target) < errtarget:
	break
	#sorting population
	populatioNew = np.zeros((pool, 2))
	for i in xrange(pool):
	populatioNew[i] = population[rankfit[i]]
	populationfit.sort()
	###########
	#selection#
	###########
	populatioNew = populatioNew[:survive]
	populationfit = populationfit[:survive]
	###########
	#crossover#
	###########
	poolmating = np.zeros((pool-survive, 2))
	rolet = np.zeros((survive+1))
	rolet[0] = 0
	#define domain of probability
	totprob = 0
	for i in xrange(survive):
	totprob += i+1
	for i in xrange(survive):
	rolet[i+1] = rolet[i] + survive - i
	#print rolet
	#define mating partner
	for i in xrange(pool-survive):
	#toss the ball for the rolet!
	balland = random.uniform(0, totprob)
	for j in xrange(survive):
	if balland < rolet[j+1]:
	choosenidx = j
	break
	poolmating[i] = populatioNew[choosenidx]
	#print poolmating
	newgen = np.zeros((pool-survive, 2))
	for i in xrange((pool-survive)/2):
	x1 = breeding(poolmating[i,0],poolmating[i+1,0])
	x2 = breeding(poolmating[i+1,0],poolmating[i,0])
	y1 = breeding(poolmating[i,1],poolmating[i+1,1])
	y2 = breeding(poolmating[i+1,1],poolmating[i,1])
	#print i*2, i*2+1
	newgen[i*2] = x1,y1
	newgen[i*2+1] = x2,y2
	#print newgen
	##########
	#mutation#
	##########
	for i in xrange(len(newgen)):
	chancemutation = random.uniform(0,1)
	if chancemutation < mutate:
	if random.uniform(0,1) < 0.5:
	newgen[i,0] = mutation(newgen[i,0])
	else:
	newgen[i,1] = mutation(newgen[i,1])
	##########
	#assemble#
	##########
	population[:survive] = populatioNew[:]
	population[survive:] = newgen[:]

view raw cgen.py hosted with ❤ by GitHub

Jika tidak kelihatan, bisa klik di sini untuk mendownloadnya.

Algoritma dari script yang dibagikan di sini sama konsepnya seperti yang pernah dijelaskan pada pembahasan sebelumnya. Berikut uraiannya

1. Initialization

	#################
	#init population#
	#################
	population = []
	for i in xrange(pool):
	population.append([random.uniform(dbound, ubound), random.uniform(dbound, ubound)])
	population = np.asarray(population)

view raw gistfile1.txt hosted with ❤ by GitHub

Di sini kita menginisialisasi solusi awal yang nilainya acak dengan search domain -10 sampai 10. Langkah ini cuma dilakukan sekali dan tidak masuk dalam iterasi sehingga iterasi dilakukan setelah langkah ini yang bisa dilihat pada full source code di atas yang menggunakan fungsi for.

2. Selection

	#real action
	for iterator in xrange(iterasi):
	###############
	#check fitness#
	###############
	populationfit = np.zeros((pool))
	for i in xrange(pool):
	populationfit[i] = fitness(population[i,0], population[i,1])
	rankfit = np.argsort(populationfit)
	#check fitness, is this the solution we want?
	print 'solution in in iteration ', iterator
	print population[rankfit[0]]
	print 'fitness', rankfit[0]
	if abs(rankfit[0]-target) < errtarget:
	break
	#sorting population
	populatioNew = np.zeros((pool, 2))
	for i in xrange(pool):
	populatioNew[i] = population[rankfit[i]]
	populationfit.sort()
	###########
	#selection#
	###########
	populatioNew = populatioNew[:survive]
	populationfit = populationfit[:survive]

view raw gistfile1.txt hosted with ❤ by GitHub

Fase ini adalah fase yang masuk iterasi pertama kali bersama-sama dengan fase-fase selanjutnya, berbeda dengan fase initialization. Sama seperti pada penjelasan di postingan terdahulu, selection dilakukan berdasarkan nilai fitness function terbaik. Pada kasus ini, semakin kecil nilai dari fitness function maka solusi tersebut dianggap semakin baik. Oleh karena itu sebelum dilakukan selection, dilakukan terlebih dahulu pengukuran nilai fitness function untuk semua solusi yang ada sekarang. Lalu solusi-solusi itu disortir dari yang paling kecil sampai yang paling besar nilai fitness functionnya. Selection adalah fase yang sederhana dimana kita mengkeep beberapa jumlah solusi terbaik yang kita inginkan dan sisanya dibuang.

3. Crossover

	###########
	#crossover#
	###########
	poolmating = np.zeros((pool-survive, 2))
	rolet = np.zeros((survive+1))
	rolet[0] = 0
	#define domain of probability
	totprob = 0
	for i in xrange(survive):
	totprob += i+1
	for i in xrange(survive):
	rolet[i+1] = rolet[i] + survive - i
	#print rolet
	#define mating partner
	for i in xrange(pool-survive):
	#toss the ball for the rolet!
	balland = random.uniform(0, totprob)
	for j in xrange(survive):
	if balland < rolet[j+1]:
	choosenidx = j
	break
	poolmating[i] = populatioNew[choosenidx]
	#print poolmating
	newgen = np.zeros((pool-survive, 2))
	for i in xrange((pool-survive)/2):
	x1 = breeding(poolmating[i,0],poolmating[i+1,0])
	x2 = breeding(poolmating[i+1,0],poolmating[i,0])
	y1 = breeding(poolmating[i,1],poolmating[i+1,1])
	y2 = breeding(poolmating[i+1,1],poolmating[i,1])
	#print i*2, i*2+1
	newgen[i*2] = x1,y1
	newgen[i*2+1] = x2,y2
	#print newgen

view raw gistfile1.txt hosted with ❤ by GitHub

Fase ini diawali dengan penentuan sepasang solusi yang akan melakukan crossover. Disini, sepasang solusi yang melakukan crossover akan melahirkan sepasang solusi baru juga. Kita tahu bahwa semakin baik kualitas pasangan solusi tersebut (dilihat dari nilai fitness fuction) maka kemungkinan besar solusi "anak"nya juga akan semakin baik. Oleh karena itu, solusi yang baik akan memiliki kemungkinan besar terpilih melakukan crossover dibanding dengan solusi yang kurang baik. Solusi yang kurang baik tetap diberi kesempatan untuk melakukan crossover karena mereka mempunyai kemungkinan memiliki "gen" yang baik untuk "masa depan" nanti atau bisa dibilang juga agar solusi final yang dihasilkan bukan berasal dari local optima, akan tetapi merupakan solusi sejati atau merupakan solusi dari global optima.

Penetuan mating pool atau kumpulan solusi-solusi yang akan melakukan crossover ditentukan pada baris 11-27 pada potongan script di atas. Bisa diliht di situ bahwa semakin baik ranking suatu solusi maka semakin besar kemungkinan solusi itu terpilih untuk masuk mating pool. Besarnya kemungkinan suatu solusi masuk mating pool pada script yang digunakan di sini adalah

Dimana survive adalah banyaknya solusi yang dikeep pada saat fase selection dan rank adalah ranking solusi yang ditinjau.

4.  Mutation

	##########
	#mutation#
	##########
	for i in xrange(len(newgen)):
	chancemutation = random.uniform(0,1)
	if chancemutation < mutate:
	if random.uniform(0,1) < 0.5:
	newgen[i,0] = mutation(newgen[i,0])
	else:
	newgen[i,1] = mutation(newgen[i,1])

view raw gistfile1.txt hosted with ❤ by GitHub

Solusi yang baru dilahirkan mempunyai kemungkinan kecil akan menyimpang sedikit dari induknya atau hasil crossover. Di sini kemungkinan penyimpangan itu terjadi adalah 20%. Ketika mutasi itu terjadi, pada solusi yang baru lahir tersebut untuk kasus ini, pada vektor solusi tersebut salah satu anggotanya nilainya akan menyimpang sedikit.

5. Pengaturan kembali populasi baru

	##########
	#assemble#
	##########
	population[:survive] = populatioNew[:]
	population[survive:] = newgen[:]

view raw gistfile1.txt hosted with ❤ by GitHub

Setelah fase 2, 3, dan 4 terlewati, selanjutnya adalah pengaturan populasi baru untuk menjalankan kembali fase 2, 3, dan 4 sampai nilai fitness function untuk solusi terbaik sudah memenuhi syarat yang diinginkan atau jumlah iterasi yang diinginkan sudah tercapai.

Contoh keluaran

Hasil running dari script yang dipakai di sini adalah sebagai berikut

Bisa dilihat bahwa iterasi yang dilakukan untuk setiap kali running bisa berbeda-beda (kita tahu bahwa script akan berhenti melakukan iterasi ketika nilai fitness function untuk solusi terbaik sudah dianggap memuaskan). Ini merupakan akibat dari algoritma genetik yang sifatnya acak cara kerjanya sama seperti neural network dan algoritma AI lainnya yang sering dibahas di sini. Bisa dilihat juga bahwa solusi terbaik yang dihasilkan tidak pas 1 dan 3 akan tetapi iterasinya tetap diakhiri. Untuk mendapatkan solusi yang lebih pas dengan nilai 1 dan 3 maka kriteria nilai fitness function yang dinginkan juga harus diperketat. Sekian.

referensi:
https://commons.wikimedia.org/wiki/File:Booth%27s_function.pdf, diakses pada 2 September 2018
https://en.wikipedia.org/wiki/Test_functions_for_optimization, diakses pada 2 September 2018