AI_Tupro1¶

Kaenova Mahendra Auditama¹
Adhe Akram Azhari²
Elita Aurora Az Zahra³
¹kaenova@student.telkomuniversity.ac.id
²adheakramazhari@student.telkomuniversity.ac.id
³elitaaurora@student.telkomuniversity.ac.id
Informatics Engineering, Telkom University, Indonesia
2021

Proyek ini merupakan proyek pertama dari Mata Kuliah Pengantar Kecerdasan Buatan dari 3 proyek yang akan di buat. Proyek pertama ini mengimplementasikan teknik searching dalam Kecerdasan Buatan dengan Genetic Algorithm. Pada algoritma ini kami membuat populasi dan generasi yang dapat diatur. Hal lain juga kami mengimplementasikan Elitisme. Pada penyeleksian orang tua, kami menggunakan fitness kompetisi dimana akan diambil sebanyak (Jumlah Populasi - Jumlah Elitism) sehingga generasi yang terbaru akan dibuat dari Elitisme serta hasil Crossover.

Pada algoritma ini dibutuhkan library tqdm. Untuk menginstallnya gunakan command berikut:

pip install tqdm

atau

conda install tqdm

Overview Tugas¶

Pada tugas yang diberikan, kami diminta untuk membuat suatu program yang menerapkan suatu teknik searching dengan menggunakan suatu konsep kecerdasan buatan. Dalam hal ini kami diminta untuk membuat dengan menggunakan Genetic Algorithm.

Tugas tersebut memberikan kita suatu masalah untuk mencari nilai maksimum dari suatu fungsi:

dengan batasan x = [-1, 2] dan y = [-1, 1]

Rancangan Algoritma¶

Untuk menyelesaikan tugas tersebut kami merancang algoritma sesuai pada diagram di bawah:

Dengan algoritma yang sudah dibuat kami juga menentukan bentuk kromosom yang ingin dibuat. Kromosom yang dibuat terdiri dari 8 genotip yang akan dibagi menjadi 2 bagian. Untuk 3 genotip pertama akan merepresentasikan untuk nilai x dan 3 genotip setelahnya digunakan untuk merepresentasikan nilai y. Pada setiap genotip tersebut akan diisi dengan suatu nilai bilangan bilangan bulat mulai dengan batasan [0, 9]

Untuk merubah genotip-genotip tersebut menjadi suatu nilai x dan y kami menggunakan suatu rumus seperti di bawah ini:

The Code¶

Import Libraries¶

Library python yang harus di masukkan untuk menjalankan algoritma ini

import random
    import math
    import matplotlib.pyplot as plt
    from time import sleep
    from tqdm import tqdm

Chromosome Class¶

Untuk membuat kromosom, kami merancang bahwa kromosom akan dibuat sebagai suatu objek yang memiliki beberapa prosedur seperti pengdekodean genotip menjadi suatu nilai x dan y serta untuk menghitung fitness dari kromosom itu sendiri.

class kromosome():
        panjang = 8
        
        def decodeX(self):
            Rmin = -1
            Rmax = 2
            self.x = 0
            self.x = Rmin + (Rmax - Rmin)*((self.kromosom[0]*10**-1)+(self.kromosom[1]*10**-2)+(self.kromosom[2]*10**-3)+(self.kromosom[3]*10**-4))/((9*10**-1)+(9*10**-2)+(9*10**-3)+(9*10**-4))
            
        def decodeY(self):
            Rmin = -1
            Rmax = 1
            self.y = 0
            self.y = Rmin + (Rmax - Rmin)*((self.kromosom[4]*10**-1)+(self.kromosom[5]*10**-2)+(self.kromosom[6]*10**-3)+(self.kromosom[7]*10**-4))/((9*10**-1)+(9*10**-2)+(9*10**-3)+(9*10**-4))
    
        def CalculateFitness(self):
            self.fitness = (math.cos(self.x**2)* math.sin(self.y**2))+(self.x+self.y)
    
        def PrintKromosome(self):
            print("Fitness: {}".format(self.fitness))
            print("Fenotip X: {} Y: {}".format(self.x, self.y))
            print("Genotipe: {} \n".format(self.kromosom))
    
        def __init__(self):
            self.kromosom = []
            self.fitness = 0
            self.x = 0
            self.y = 0
            for i in range(8):
                self.kromosom.append(random.randint(0, 9)) 
            self.decodeX()
            self.decodeY()

Genetic Algorithm Procedure and Function¶

Fungsi dan Prosedur utama yang dibutuhkan untuk menjalankan algoritma ini

Initialize Population¶

Dalam prosedur ini digunakan sebagai generasi pertama, dimana akan digunakan untuk membuat kromosom sebanyak jumlah yang ditentukan.

def initialize_population(population_made):
        population = []
        for i in range(population_made): #variable
            kromosome_temp = kromosome()
            population.append(kromosome_temp)
        return population

CalculateKromosomeFitness¶

Fungsi ini digunakan untuk menghitung fitness pada setiap kromosom.

def calculateKromosomeFitness(population):
        for i in range(len(population)):
            population[i].CalculateFitness()

PopulationFitnessSort¶

Dalam algoritma ini kami akan melakukan elitism dan selection parent sehingga dibutuhkan fungsi yang mengembalikan kromosom secara terurut mengecil dari berdasarkan fitness tersebut.

def PopulationFitnessSort(population: [kromosome()]):
        population = sorted(population, key=lambda x: x.fitness, reverse= 1)
    
        return population

GetElitism¶

Fungsi ini akan mengambil kromosom terbaik dari suatu populasi yang sudah diurutkan dari yang terbesar menuju ke terkecil. Banyaknya yang diambil sebesar 1/5 dari total populasi yang ada.

def getElitism(population):
        get_selection = (math.floor(len(population)/ 5))
        if get_selection % 2 != 0:
            get_selection += 1
        elitism = []
        for i in range(get_selection):
            elitism.append(population[i])
    
        return elitism

TournamentSelection¶

Fungsi ini akan mengambil kromosom-kromosom dari populasi berdasarkan fitness. Yang terambil sebanyak 4/5 dari populasi dan index yang mulai diambil merupakan index dari 1/10 populasi.

def tournamentSelection(population):
        get_selection = (math.floor(len(population)/ 5))
        if get_selection % 2 != 0:
           get_selection += 1
        jum_parent = (len(population) - get_selection)
        start_parent = int((get_selection / 2) - 1)
        parent = []
        for i in range(jum_parent) :
            parent.append(population[start_parent + i])
    
        return parent

Gambaran untuk Tournament Selection dan Mengambil Elitism Tersebut seperti di bawah ini:

MatingPool¶

Dari Fungsi TournamentSelection, pada mating pool ini akan memasangkan parent-parent tersebut untuk dipersiapkan melakukan crossover.

def MatingPool(parent = [kromosome()]):
        parent_temp = parent
        pasangan = []
        j = 0
    
        for i in range(int(len(parent)/2)):
            pasangan_temp = []
            random_angka_parent = random.randint(1, (len(parent_temp)-1))
            # Copyrighted by Kaenova Mahendra Auditama, Adhe Akram Azhari, Elita Aurora Az Zahra
            pasangan_temp.append(parent_temp[0])
            pasangan_temp.append(parent_temp[random_angka_parent])
            pasangan.append(pasangan_temp)
            parent_temp.pop(random_angka_parent)
            parent_temp.pop(0)
            j = j + 1
    
        return pasangan

Crossover¶

Crossover ini mempunyai kemungkinan sebesar 0.85 untuk terjadi hal tersebut. Setelah melakukan pemasang-masangan pada fungsi MatingPool dilakukan crossover pada titik yang random di genotip. Sehingga pada suatu pasangan akan menghasilkan 2 anak (child).

def crossover(pasangan = [[kromosome],[kromosome]]):
        populasi_anak = []
        for i in range(len(pasangan)):
            temp_pasangan = pasangan[i]
            random_num = random.uniform(0, 1)
            if random_num < 0.85:
                parent1 = temp_pasangan[0]
                parent2 = temp_pasangan[1]
                panjang_potong = random.randint(1,parent1.panjang - 2)
                kromosome_temp_1 = kromosome()
                kromosome_temp_2 = kromosome()
                kromosome_temp_1.kromosom = parent1.kromosom[:panjang_potong] + parent2.kromosom[panjang_potong:]
                # Copyrighted by Kaenova Mahendra Auditama, Adhe Akram Azhari, Elita Aurora Az Zahra
                kromosome_temp_2.kromosom = parent2.kromosom[:panjang_potong] + parent1.kromosom[panjang_potong:]
                populasi_anak.append(kromosome_temp_1)
                populasi_anak.append(kromosome_temp_2) 
            else:
                populasi_anak.append(temp_pasangan[0])
                populasi_anak.append(temp_pasangan[1])
    
        return populasi_anak

Mutation¶

Dalam genetika kita tidak boleh melupakan kemungkinan terjadinya suatu mutasi pada genotip-genotiup tertentu. Disini saya membuat bahwa besarnya mutasi pada suatu genotip adalah acak dari range dengan kemungkinan terjadinya mutasi dibawah 1%

def mutation(children):
        for i in range(len(children)):
            for j in range(children[i].panjang):
                random_mutation = random.uniform(0,1)
                if (random_mutation < 0.1 ): #Setup mutasi
                    if (children[i].kromosom[j] + 1 == 10):
                        children[i].kromosom[j] -= 1
                    elif ((children[i].kromosom[j] - 1 == -1)):
                        children[i].kromosom[j] += 1
                    else:
                        random_mutation = random.uniform(0,1)
                        if (random_mutation > 0.5):
                            children[i].kromosom[j] += 1
                        else:
                            children[i].kromosom[j] -= 1
        
        return children

Other Procedure or Function¶

Kami juga membutuhkan prosedur atau fungsi lain yang bukan menjadi hal utama dalam algoritma ini, tetapi untuk membantu tracking generasi dan kromosom yang terjadi ketika algoritma ini berjalan

def printAllKromosome(population = [kromosome()]):
        for i in range(len(population)):
            population[i].PrintKromosome()
    
    def printBestKromosom(best: kromosome, generasi):
        print(" Best Fitness from Generation {}".format(generasi+1))
        # Coded by Kaenova Mahendra Auditama (kaenova@gmail.com)
        # *not responsible if someone plagirized or copied my code
        print("Fitness: {}".format(best.fitness))
        print("Fenotip X: {} Y: {}".format(best.x, best.y))
        print("Genotipe: {} \n".format(best.kromosom))

MAIN¶

if __name__ == "__main__":
        population_number = int(input("How many population do you want to have? \n [Input Even Number over 10] : "))
        while (population_number % 2 != 0) or (population_number < 10):
            population_number = int(input("How many population do you want to have? \n [Input Even Number over 10] : "))
    
        generation = int(input("How many generation do you want to have?: "))
        while generation <= 0:
            generation = int(input("How many generation do you want to have?: "))
            
        fitness_genertaion = []
        generation_numbering = []
        changing_best_kromosome = []
        changing_best_generation = []
        
        populasi = []
        populasi = initialize_population(population_number)
        best_kromosom = kromosome()
    
        for i in tqdm(range(generation)):
            calculateKromosomeFitness(populasi)
            populasi = PopulationFitnessSort(populasi)
            
            #This is for plotting
            generation_numbering.append(i + 1)
            fitness_genertaion.append(populasi[0].fitness)
            # Copyrighted by Kaenova Mahendra Auditama, Adhe Akram Azhari, Elita Aurora Az Zahra
            if best_kromosom.fitness < populasi[0].fitness:
                changing_best_kromosome.append(populasi[0])
                changing_best_generation.append(i)
                best_kromosom = populasi[0]
            
            elitism = getElitism(populasi)
            parent = tournamentSelection(populasi)
            pasangan = MatingPool(parent)
            populasi_anak = crossover(pasangan)
            populasi_anak = mutation(populasi_anak)
            populasi = elitism + populasi_anak
    
        
        #make a plot
        for i in range(len(changing_best_generation)):
            printBestKromosom(changing_best_kromosome[i], changing_best_generation[i])
        plt.figure(figsize=(10,4))
        plt.title("Grafik Fitness")
        plt.xlabel("Generation")
        plt.ylabel("Fitness")
        plt.plot(generation_numbering, fitness_genertaion)
        plt.savefig("./Presentasi/plot.png",dpi=1200, format='png', transparent=False)

How many population do you want to have? 
     [Input Even Number over 10] : 100
    How many generation do you want to have?: 1000

100%|██████████| 1000/1000 [00:03<00:00, 272.93it/s]

 Best Fitness from Generation 1
    Fitness: 2.451372766969522
    Fenotip X: 0.9672967296729678 Y: 0.9907990799079907
    Genotipe: [6, 5, 6, 7, 9, 9, 5, 3] 
    
     Best Fitness from Generation 77
    Fitness: 2.465504749946626
    Fenotip X: 0.9204920492049209 Y: 0.9929992999299928
    Genotipe: [8, 1, 4, 8, 8, 6, 4, 4] 
    
     Best Fitness from Generation 197
    Fitness: 2.4670687633302135
    Fenotip X: 0.7980798079807978 Y: 0.995999599959996
    Genotipe: [7, 3, 7, 8, 2, 5, 1, 7] 
    
     Best Fitness from Generation 283
    Fitness: 2.469902723074565
    Fenotip X: 0.8709870987098713 Y: 0.9933993399339935
    Genotipe: [4, 6, 8, 4, 7, 6, 4, 6] 
    
     Best Fitness from Generation 315
    Fitness: 2.4718754711467725
    Fenotip X: 0.8034803480348036 Y: 0.9979997999799981
    Genotipe: [2, 5, 9, 7, 6, 8, 3, 2] 
    
     Best Fitness from Generation 424
    Fitness: 2.4719776499171346
    Fenotip X: 0.9138913891389142 Y: 0.9961996199619962
    Genotipe: [1, 6, 1, 6, 1, 4, 3, 6] 
    
     Best Fitness from Generation 516
    Fitness: 2.472104200272737
    Fenotip X: 0.8007800780078009 Y: 0.9983998399839984
    Genotipe: [6, 3, 4, 7, 6, 8, 5, 1] 
    
     Best Fitness from Generation 518
    Fitness: 2.479922961544548
    Fenotip X: 0.8718871887188722 Y: 0.9989998999899989
    Genotipe: [6, 3, 5, 7, 6, 3, 6, 6] 
    
     Best Fitness from Generation 633
    Fitness: 2.4816982333887143
    Fenotip X: 0.8637863786378641 Y: 1.0
    Genotipe: [6, 2, 6, 5, 1, 6, 3, 9]

Endnote by Author¶

Pertama-tama kami mengucapkan terima kasih kepada Tuhan Yang Maha Esa serta, dosen kami, Ibu Fhira Nhita dan tidak lupa juga Asisten Doesn yang telah membantu kami mendapatkan ilmu serta menyelesaikan tugas ini.
Kami tidak bertanggungjawab jika ada yang melakukan plagiarisme atau menyalin kode yang telah kami buat.