Materi tentang Genetic Algorithms (GA) dalam Kecerdasan Buatan (AI) dan Machine Learning (+ Video Materi)

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 : Towardsdatascien ce.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 generation
POPULATION_SIZE = 100
  
# Valid genes
GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP
QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''
  
# Target string to be generated
TARGET = input("Input Strings :")
  
class Individual(object):
    '''
    Class representing individual in population
    '''
    def __init__(self, chromosome):
        self.chromosome = chromosome 
        self.fitness = self.cal_fitness()
  
    @classmethod
    def mutated_genes(self):
        '''
        create random genes for mutation
        '''
        global GENES
        gene = random.choice(GENES)
        return gene
  
    @classmethod
    def create_gnome(self):
        '''
        create chromosome or string of genes
        '''
        global TARGET
        gnome_len = len(TARGET)
        return [self.mutated_genes() for _ in range(gnome_len)]
  
    def mate(self, par2):
        '''
        Perform mating and produce new offspring
        '''
  
        # chromosome for offspring
        child_chromosome = []
        for gp1, gp2 in zip(self.chromosome, par2.chromosome):    
  
            # random probability  
            prob = random.random()
  
            # if prob is less than 0.45, insert gene
            # from parent 1 
            if prob < 0.45:
                child_chromosome.append(gp1)
  
            # if prob is between 0.45 and 0.90, insert
            # gene from parent 2
            elif prob < 0.90:
                child_chromosome.append(gp2)
  
            # otherwise insert random gene(mutate), 
            # for maintaining diversity
            else:
                child_chromosome.append(self.mutated_genes())
  
        # create new Individual(offspring) using 
        # generated chromosome for offspring
        return Individual(child_chromosome)
  
    def cal_fitness(self):
        '''
        Calculate fitness score, it is the number of
        characters in string which differ from target
        string.
        '''
        global TARGET
        fitness = 0
        for gs, gt in zip(self.chromosome, TARGET):
            if gs != gt: fitness+= 1
        return fitness
  
# Driver code
def main():
    global POPULATION_SIZE
  
    #current generation
    generation = 1
  
    found = False
    population = []
  
    # create initial population
    for _ in range(POPULATION_SIZE):
                gnome = Individual.create_gnome()
                population.append(Individual(gnome))
  
    while not found:
  
        # sort the population in increasing order of fitness score
        population = 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 loop
        if population[0].fitness <= 0:
            found = True
            break
  
        # Otherwise generate new offsprings for new generation
        new_generation = []
  
        # Perform Elitism, that mean 10% of fittest population
        # goes to the next generation
        s = int((10*POPULATION_SIZE)/100)
        new_generation.extend(population[:s])
  
        # From 50% of fittest population, Individuals 
        # will mate to produce offspring
        s = 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_generation
  
        print("Generation: {}\tString: {}\tFitness: {}".\
              format(generation,
              "".join(population[0].chromosome),
              population[0].fitness))
  
        generation += 1
  
      
    print("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.

Materi tentang Genetic Algorithms (GA) dalam Kecerdasan Buatan (AI) dan Machine Learning (+ Video Materi)

MATERI

A. Pengertian Genetic Algorithm (GA)

B. Klasifikasi dan Cara Kerja Genetic Algorithm (GA)

C. Penerapan Bidang Genetic Algorithm (GA)

D. Contoh Program Solusi pada Genetic Algorithm (GA)

VIDEO

Post a Comment

Inilah Pengertian Kerangka Kualifikasi Nasional Indonesia (KKNI)

Inilah Sistematika Penulisan Skripsi yang Baik dan Benar

Categories

Main Tags

Contact Form

Popular Posts

Inilah Sistematika Penulisan Skripsi yang Baik dan Benar

Inilah 10+ Pekerjaan yang Tidak dapat digantikan oleh AI

Konsistensi dan Replikasi dalam Sistem Terdistribusi

Contact Form