Assalamu‘alaikum wr. wb.
Halo gais! Sebelumnya, kita telah membahas tentang Constraint Satisfaction Problem (CS). Sekarang, kita akan membahas tentang Genetic Algorithms dalam Artificial Intelligence. Genetic Algorithm sendiri mirip sekali dengan Genetika dalam Biologi dan dikemas dalam bentuk Algoritma dan Teknologi.
 |
| Ilustrasi Genetic Algorithms dalam Kecerdasan Buatan (AI) |
Sumber Materi : Towardsdatascience.com (Medium.com), Pub.Towardsai.net (Medium.com), Section.io, Geeksforgeeks.org, dan Socs.Binus.ac.id
MATERI
A. Pengertian Genetic Algorithm (GA)
Genetic Algorithm (GA) adalah bagian dari Evolutionary Algorithm yaitu suatu algoritma yang mencontoh proses evolusi alami dimana konsep utamanya adalah individu-individu yang paling unggul akan bertahan hidup, sedangkan individu-individu yang lemah akan punah. Keunggulan individu-individu ini diuji melalui suatu fungsi yang dikenal sebagai fitness function. Fitness dalam GA didefinisikan sebagai gambaran kelayakan suatu solusi terhadap suatu permasalahan. Fitness Function akan menghasilkan suatu nilai fitness value yang akan menjadi referensi untuk proses GA selanjutnya. Secara umum, proses GA ditunjukan pada Gambar di bawah ini :
 |
| Skema Genetic Algorithm |
B. Klasifikasi dan Cara Kerja Genetic Algorithm (GA)
Berikut ini adalah beberapa terminologi dasar yang dapat membantu kita untuk memahami Genetic Algorithms :
- Populasi : Adalah sub-himpunan dari semua kemungkinan solusi yang dapat memecahkan masalah yang diberikan.
- Kromosom : Kromosom adalah salah satu solusi dalam populasi.
- Gen : Adalah elemen dalam kromosom.
- Alel : Adalah nilai yang diberikan pada gen dalam kromosom tertentu.
- Fitness function : Adalah fungsi yang menggunakan input khusus untuk menghasilkan output yang lebih baik. Solusi digunakan sebagai input sedangkan output berupa kesesuaian solusi.
- Operator Genetika : Dalam Algoritma Genetika (Genetic Algorithm), pasangan individu terbaik untuk mereproduksi keturunan yang lebih baik dari induknya. Operator genetik digunakan untuk mengubah komposisi genetik generasi berikutnya.
Algoritma genetika (GA) adalah algoritma pencarian heuristik yang digunakan untuk memecahkan masalah pencarian dan optimisasi. Algoritma ini adalah bagian dari algoritma evolusioner, yang digunakan dalam komputasi. Algoritma genetika menggunakan konsep genetika dan seleksi alam untuk memberikan solusi masalah.
Algoritma ini memiliki kecerdasan yang lebih baik daripada algoritma pencarian acak karena mereka menggunakan data historis untuk melakukan pencarian ke wilayah dengan kinerja terbaik dalam ruang solusi.
GAs juga didasarkan pada perilaku kromosom dan struktur genetiknya. Setiap kromosom memainkan peran memberikan solusi yang mungkin. Fungsi kebugaran membantu dalam memberikan karakteristik semua individu dalam populasi. Semakin besar fungsinya, semakin baik solusinya.
Pengertian Seleksi Alam (Notion of Natural Selection)
Proses seleksi alam dimulai dengan pemilihan individu terkuat dari suatu populasi. Mereka menghasilkan keturunan yang mewarisi sifat-sifat induknya dan akan ditambahkan ke generasi berikutnya. Jika orang tua memiliki kebugaran yang lebih baik, keturunannya akan lebih baik dari orang tua dan memiliki peluang bertahan hidup yang lebih baik. Proses ini terus berulang dan pada akhirnya akan ditemukan generasi dengan individu yang paling cocok.
Gagasan ini dapat diterapkan untuk masalah pencarian. Kami mempertimbangkan satu set solusi untuk suatu masalah dan memilih satu set yang terbaik dari mereka.
Lima fase dipertimbangkan dalam Genetic Algorithms, yaitu :
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
Algoritma Genetika mengikuti fase-fase berikut untuk menyelesaikan masalah optimisasi yang kompleks :
1. Populasi Awal (Initial Population)
Proses dimulai dengan sekumpulan individu yang disebut Populasi. Setiap individu adalah solusi dari masalah yang ingin dipecahkan.
Seorang individu dicirikan oleh seperangkat parameter (variabel) yang dikenal sebagai Gen. Gen digabungkan menjadi string untuk membentuk Kromosom (solusi).
Dalam algoritma genetika, himpunan gen individu direpresentasikan menggunakan string, dalam bentuk alfabet. Biasanya, nilai biner digunakan (string 1s dan 0s). Kami mengatakan bahwa kami menyandikan gen dalam kromosom.
 |
| Populasi, Kromosom, dan Gen |
2. Fitness Score/Function
Fitness Score atau Fitness Function diberikan kepada setiap individu yang menunjukkan kemampuan individu untuk “berkompetisi”. Individu yang memiliki skor kebugaran optimal (atau mendekati optimal) dicari.
Ini memberikan skor kebugaran untuk setiap individu, yang selanjutnya menentukan kemungkinan terpilih untuk reproduksi. Semakin tinggi skor kebugaran, semakin tinggi peluang terpilih untuk reproduksi.
3. Pilihan (Selection)
Ide fase seleksi adalah memilih individu yang paling cocok dan membiarkan mereka mewariskan gen mereka ke generasi berikutnya.
Dua pasang individu (orang tua) dipilih berdasarkan skor kebugaran mereka. Individu dengan fitness tinggi memiliki peluang lebih besar untuk diseleksi untuk reproduksi.
4. Crossover
Crossover adalah fase paling signifikan dalam algoritma genetika. Untuk setiap pasang induk yang akan dikawinkan, titik persilangan dipilih secara acak dari dalam gen.
Misalnya, pertimbangkan titik persilangan menjadi 3 seperti yang ditunjukkan di bawah ini.
 |
| Crossover Point |
Keturunan (Offspring) diciptakan dengan menukar gen orang tua di antara mereka sendiri sampai titik persilangan tercapai.
 |
| Pertukaran Gen di antara Orang Tua |
Keturunan baru ditambahkan ke populasi.
 |
| Keturunan Baru (New Offspring) |
5. Mutasi
Pada keturunan baru tertentu yang terbentuk, beberapa gen mereka dapat mengalami mutasi dengan probabilitas acak yang rendah. Ini menyiratkan bahwa beberapa bit dalam string bit dapat dibalik.
 |
| Sebelum dan Sesudah Mutasi |
Mutasi terjadi untuk menjaga keragaman dalam populasi dan mencegah konvergensi prematur.
Seluruh Algoritma dapat diringkas sebagai :
1) Inisialisasi populasi secara acak p 2) Tentukan kebugaran populasi 3) Sampai konvergensi ulangi: a) Pilih orang tua dari populasi b) Crossover dan menghasilkan populasi baru c) Melakukan mutasi pada populasi baru d) Hitung kebugaran untuk populasi baru
C. Penerapan Bidang Genetic Algorithm (GA)
Genetic Algorithm diterapkan pada bidang-bidang berikut :
1. Transportasi
Algoritma genetika digunakan dalam masalah travelling salesman untuk mengembangkan rencana transportasi yang mengurangi biaya perjalanan dan waktu yang dibutuhkan. Mereka juga digunakan untuk mengembangkan cara pengiriman produk yang efisien.
2. Analisis DNA
Mereka digunakan dalam analisis DNA untuk membangun struktur DNA menggunakan informasi spektrometri.
3. Optimasi Multimodal
Mereka digunakan untuk memberikan beberapa solusi optimal dalam masalah optimasi multimodal.
4. Desain Pesawat
Mereka digunakan untuk mengembangkan desain pesawat parametrik. Parameter pesawat dimodifikasi dan ditingkatkan untuk memberikan desain yang lebih baik.
5. Ekonomi
Mereka digunakan dalam ekonomi untuk menggambarkan berbagai model seperti teori permainan, model sarang laba-laba, penetapan harga aset, dan pengoptimalan jadwal.
D. Contoh Program Solusi pada Genetic Algorithm (GA)
Diberi string target, tujuannya adalah untuk menghasilkan string target mulai dari string acak dengan panjang yang sama. Dalam implementasi berikut, analogi berikut dibuat :
- Karakter A-Z, a-z, 0-9, dan simbol khusus lainnya dianggap sebagai gen.
- Sebuah string yang dihasilkan oleh karakter ini dianggap sebagai kromosom/solusi/Individu.
Berikut ini adalah Contoh Program dalam Python :
import random# Number of individuals in each generationPOPULATION_SIZE = 100# Valid genesGENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''# Target string to be generatedTARGET = input("Input Strings :")class Individual(object):'''Class representing individual in population'''def __init__(self, chromosome):self.chromosome = chromosomeself.fitness = self.cal_fitness()@classmethoddef mutated_genes(self):'''create random genes for mutation'''global GENESgene = random.choice(GENES)return gene@classmethoddef create_gnome(self):'''create chromosome or string of genes'''global TARGETgnome_len = len(TARGET)return [self.mutated_genes() for _ in range(gnome_len)]def mate(self, par2):'''Perform mating and produce new offspring'''# chromosome for offspringchild_chromosome = []for gp1, gp2 in zip(self.chromosome, par2.chromosome):# random probabilityprob = random.random()# if prob is less than 0.45, insert gene# from parent 1if prob < 0.45:child_chromosome.append(gp1)# if prob is between 0.45 and 0.90, insert# gene from parent 2elif prob < 0.90:child_chromosome.append(gp2)# otherwise insert random gene(mutate),# for maintaining diversityelse:child_chromosome.append(self.mutated_genes())# create new Individual(offspring) using# generated chromosome for offspringreturn Individual(child_chromosome)def cal_fitness(self):'''Calculate fitness score, it is the number ofcharacters in string which differ from targetstring.'''global TARGETfitness = 0for gs, gt in zip(self.chromosome, TARGET):if gs != gt: fitness+= 1return fitness# Driver codedef main():global POPULATION_SIZE#current generationgeneration = 1found = Falsepopulation = []# create initial populationfor _ in range(POPULATION_SIZE):gnome = Individual.create_gnome()population.append(Individual(gnome))while not found:# sort the population in increasing order of fitness scorepopulation = sorted(population, key = lambda x:x.fitness)# if the individual having lowest fitness score ie.# 0 then we know that we have reached to the target# and break the loopif population[0].fitness <= 0:found = Truebreak# Otherwise generate new offsprings for new generationnew_generation = []# Perform Elitism, that mean 10% of fittest population# goes to the next generations = int((10*POPULATION_SIZE)/100)new_generation.extend(population[:s])# From 50% of fittest population, Individuals# will mate to produce offsprings = int((90*POPULATION_SIZE)/100)for _ in range(s):parent1 = random.choice(population[:50])parent2 = random.choice(population[:50])child = parent1.mate(parent2)new_generation.append(child)population = new_generationprint("Generation: {}\tString: {}\tFitness: {}".\format(generation,"".join(population[0].chromosome),population[0].fitness))generation += 1print("Generation: {}\tString: {}\tFitness: {}".\format(generation,"".join(population[0].chromosome),population[0].fitness))if __name__ == '__main__':main()
Output :
Input Strings : Inzaghi Generation: 1 String: q.Y.FPi Fitness: 6 Generation: 2 String: q.Y.FPi Fitness: 6 Generation: 3 String: snqrFIi Fitness: 5 Generation: 4 String: snqrFIi Fitness: 5 Generation: 5 String: snqrFIi Fitness: 5 Generation: 6 String: In9/WBi Fitness: 4 Generation: 7 String: In9/WBi Fitness: 4 Generation: 8 String: In9/WBi Fitness: 4 Generation: 9 String: In9/WBi Fitness: 4 Generation: 10 String: In9/WBi Fitness: 4 Generation: 11 String: In9/WBi Fitness: 4 Generation: 12 String: In9/WBi Fitness: 4 Generation: 13 String: In9/WBi Fitness: 4 Generation: 14 String: In9/WBi Fitness: 4 Generation: 15 String: In9/WBi Fitness: 4 Generation: 16 String: In9/WBi Fitness: 4 Generation: 17 String: In9/WBi Fitness: 4 Generation: 18 String: InsaoEi Fitness: 3 Generation: 19 String: InsaoEi Fitness: 3 Generation: 20 String: InsaoEi Fitness: 3 Generation: 21 String: InsaoEi Fitness: 3 Generation: 22 String: InzaFai Fitness: 2 Generation: 23 String: InzaFai Fitness: 2 Generation: 24 String: InzaFai Fitness: 2 Generation: 25 String: InzaFai Fitness: 2 Generation: 26 String: Inzagai Fitness: 1 Generation: 27 String: Inzagai Fitness: 1 Generation: 28 String: Inzagai Fitness: 1 Generation: 29 String: Inzagai Fitness: 1 Generation: 30 String: Inzagai Fitness: 1 Generation: 31 String: Inzagai Fitness: 1 Generation: 32 String: Inzagai Fitness: 1 Generation: 33 String: Inzagai Fitness: 1 Generation: 34 String: Inzagai Fitness: 1 Generation: 35 String: Inzagai Fitness: 1 Generation: 36 String: Inzagai Fitness: 1 Generation: 37 String: Inzagai Fitness: 1 Generation: 38 String: Inzagai Fitness: 1 Generation: 39 String: Inzagai Fitness: 1 Generation: 40 String: Inzagai Fitness: 1 Generation: 41 String: Inzagai Fitness: 1 Generation: 42 String: Inzagai Fitness: 1 Generation: 43 String: Inzagai Fitness: 1 Generation: 44 String: Inzagai Fitness: 1 Generation: 45 String: Inzagai Fitness: 1 Generation: 46 String: Inzagai Fitness: 1 Generation: 47 String: Inzagai Fitness: 1 Generation: 48 String: Inzagai Fitness: 1 Generation: 49 String: Inzagai Fitness: 1 Generation: 50 String: Inzagai Fitness: 1 Generation: 51 String: Inzagai Fitness: 1 Generation: 52 String: Inzagai Fitness: 1 Generation: 53 String: Inzagai Fitness: 1 Generation: 54 String: Inzagai Fitness: 1 Generation: 55 String: Inzagai Fitness: 1 Generation: 56 String: Inzagai Fitness: 1 Generation: 57 String: Inzaghi Fitness: 0
Catatan : Algoritma setiap waktu dimulai dengan string acak, jadi hasilnya mungkin berbeda.
Seperti yang dapat kita lihat dari output, Algoritma kami terkadang terhenti pada solusi optimal lokal, hal ini dapat ditingkatkan lebih lanjut dengan memperbarui algoritme penghitungan skor kebugaran atau dengan mengutak-atik operator mutasi dan persilangan.
VIDEO
Untuk memahami lebih lanjut terkait dengan Genetic Algorithms (GA), lihatlah Video-video YouTube di bawah ini.
Itulah Materi tentang Genetic Algorithms dalam Kecerdasan Buatan (AI) dan Machine Learning (ML). Mohon maaf apabila ada kesalahan apapun.
Terima Kasih 😄😘👌👍 :)
Wassalamu‘alaikum wr. wb.