Algoritma Genetika dengan Python
Algoritma Genetika dikembangkan pertama kali oleh John Holand dari New York, Amarika Serikat yang dipublikasikan dalam bukunya yang berjudul “Adaption in Natural and Artificial Systems” tahun 1975. Algoritma Genetika merupakan Teknik untuk menemukan solusi optimal dari permasalahan yang mempunyai banyak solusi. Teknik ini akan melakukan pencarian dari beberapa solusi yang diperoleh sampai mendapatkan solusi terbaik sesuai dengan kriteria yang telah ditentukan atau yang disebut sebagai fungsi fitness. Algoritma ini masuk dalam kelompok algoritma evolusioner dengan menggunakan pendekatan evolusi Darwin di bidang Biologi seperti pewarisan sifat, seleksi alam, mutasi gen dan kombinasi (crossover). Karena merupakan Teknik pencarian optimal dalam bidang ilmu komputer, maka algoritma ini juga termasuk dalam kelompok algoritma metaheuristik.
Aplikasi algoritma genetika dapat ditemukan di berbagai bidang terutama bidang-bidang yang memerlukan solusi kombinatorik seperti penjadwalan, peramalan, jarak terpendek dan kombinasi ransum atau bahan. Algoritma genetika sering dipakai untuk melakukan simulasi dengan Komputer untuk mendapatkan solusi terbaik berdasarkan calon-calon solusi yang visible. Proses pencarian solusi terbaik dimulai dengan merepresentasikan solusi-solusi yang mungkin terjadi berdasarkan domain yang biasanya dalam bentuk string biner (0 dan 1). Dari representasi ini dibentuk populasi individual secara acak yang membentuk suatu generasi. Kemudian dari setiap populasi yang terbentuk dievaluasi dengan menggunakan fungsi fitness untuk dapat memilih populasi terbaik. Kemudian populasi dimodifikasi dengan mutasi dan kombinasi untuk mendapatkan populasi baru. Proses ini diulang sampai mendapatkan individu dari populasi yang mencapai nilai fitness.
Langkah-langkah algoritma genetika dapat diuraikan sebagai berikut:
- Penentuan representasi individu dari populasi
- Pembetukan populasi individu secara acak
- Evaluasi kecocokan setiap individu dalam populasi berdasarkan fungsi fitness
- Memilih individu dengan nilai kecocokan paling tinggi
- Kombinasi antar individu terpilih dalam populasi dan mutasi individu dengan tingkat tertentu untuk membentuk populasi baru
- Proses 3 diulang sampai mendapatkan solusi terbaik.
Contoh program python untuk mendapatkan solusi terbaik dari permasalahan polynomial dengan rumus:
| import numpy as np
import matplotlib.pyplot as plt def _fitness(x): if x>0 and x<32: y = 12*x**5 – 975*x**4 + 28000*x**3 -345000*x**2 + 1800000*x return round(y, 6) else: return 0 fitness = np.vectorize(_fitness) def mutate (parents, fitness_function): n = int(len(parents)) scores = fitness_function(parents) idx = scores > 0 scores = scores[idx] parents = np.array(parents)[idx] children = np.random.choice(parents, size=n, p=scores/scores.sum()) children = children + np.random.uniform(-0.51, 0.51, size=n) return children.tolist() def GA(parents, fitness_function, popsize=100, max_iter=100): History = [] best_parent, best_fitness = _get_fittest_parents(parents, fitness) #plot the initial x = np.linspace(0, 32, 200) plt.plot(x, fitness_function(x)) plt.scatter(parents, fitness_function(parents), marker= ‘X’) for i in range(max_iter): parents = mutate(parents, fitness_function=fitness_function) curr_parent,curr_fitness = _get_fittest_parents(parents, fitness_function) if curr_fitness > best_fitness: best_fitness = curr_fitness best_parent = curr_parent curr_parent,curr_fitness = _get_fittest_parents(parents, fitness_function) if i%10 == 0: print(‘generation: {} |best fitness: {} |curr fitness: {} |curr parent: {}’ .format(i, best_fitness, curr_fitness, curr_parent)) History.append((i, np.max(fitness_function(parents)))) plt.scatter(parents, fitness_function(parents)) plt.scatter(best_parent, fitness_function(best_parent), marker=’.’, c=’b’, s=200) plt.pause(0.09) plt.ioff() print(‘generation: {} | best fitness: {} | best parent: {}’ .format(i, best_fitness, best_parent)) return best_parent, best_fitness, History def _get_fittest_parents(parents, fitness): _fitness = fitness(parents) PFitness = list(zip(parents, _fitness)) PFitness.sort(key = lambda x:x[1], reverse=True) best_parent, best_fitness = PFitness[0] return round(best_parent, 4), round(best_fitness, 4) x = np.linspace(0, 32, 200) init_pop = np.random.uniform(low=0, high=32, size=100) parent_, fitness_, history_ = GA(init_pop, fitness) print(‘top parent x= {}, top fitness y= {}’ .format(parent_, fitness_))
|
Contoh output :
| generation: 0 |best fitness: 4399868.1626 |curr fitness: 4399868.1626 |curr parent: 19.9458
generation: 10 |best fitness: 4399991.5999 |curr fitness: 4397673.4731 |curr parent: 19.7714 generation: 20 |best fitness: 4399991.5999 |curr fitness: 4399850.0432 |curr parent: 20.0577 generation: 30 |best fitness: 4399998.9652 |curr fitness: 4399845.845 |curr parent: 19.9414 generation: 40 |best fitness: 4399999.9902 |curr fitness: 4399999.7289 |curr parent: 19.9975 generation: 50 |best fitness: 4399999.9902 |curr fitness: 4399959.6682 |curr parent: 20.0299 generation: 60 |best fitness: 4399999.9902 |curr fitness: 4399641.1671 |curr parent: 20.0891 generation: 70 |best fitness: 4399999.9902 |curr fitness: 4399981.1302 |curr parent: 20.0205 generation: 80 |best fitness: 4399999.9902 |curr fitness: 4399898.2702 |curr parent: 19.9524 generation: 90 |best fitness: 4399999.999 |curr fitness: 4399999.999 |curr parent: 19.9999 |
Penulis : Dr. Suharjito, S.Si., MT (suharjito@binus.edu)
Tanggal : 2 Maret 2021