AI dengan Python - Algoritma Genetika

Bab ini membahas Algoritma Genetika AI secara detail.

Apa itu Algoritma Genetika?

Genetic Algorithms (GAs) adalah algoritma berbasis pencarian berdasarkan konsep seleksi alam dan genetika. GAs adalah bagian dari cabang komputasi yang jauh lebih besar yang dikenal sebagai Komputasi Evolusioner.

GAs dikembangkan oleh John Holland dan mahasiswa serta koleganya di Universitas Michigan, terutama David E. Goldberg. Sejak itu telah dicoba pada berbagai masalah pengoptimalan dengan tingkat keberhasilan yang tinggi.

Di GAs, kami memiliki kumpulan solusi yang mungkin untuk masalah yang diberikan. Larutan ini kemudian mengalami rekombinasi dan mutasi (seperti pada genetika alami), menghasilkan anak baru, dan prosesnya berulang untuk berbagai generasi. Setiap individu (atau solusi kandidat) diberi nilai kesesuaian (berdasarkan nilai fungsi objektifnya) dan individu yang lebih bugar diberi kesempatan lebih tinggi untuk kawin dan menghasilkan.fitterindividu. Ini sejalan dengan Teori Darwin tentangSurvival of the Fittest.

Jadi, itu disimpan evolving individu atau solusi yang lebih baik dari generasi ke generasi, hingga mencapai kriteria penghentian.

Algoritma Genetika cukup diacak di alam, tetapi mereka bekerja jauh lebih baik daripada pencarian lokal acak (di mana kami hanya mencoba solusi acak, melacak yang terbaik sejauh ini), karena mereka juga mengeksploitasi informasi sejarah.

Bagaimana Menggunakan GA untuk Masalah Pengoptimalan?

Optimasi merupakan tindakan membuat desain, situasi, sumber daya dan sistem seefektif mungkin. Diagram blok berikut menunjukkan proses pengoptimalan -

Tahapan mekanisme GA untuk proses optimasi

Berikut urutan langkah-langkah mekanisme GA saat digunakan untuk optimasi masalah.

• Langkah 1 - Hasilkan populasi awal secara acak.

• Langkah 2 - Pilih solusi awal dengan nilai kebugaran terbaik.

• Langkah 3 - Gabungkan kembali solusi yang dipilih menggunakan operator mutasi dan crossover.

• Langkah 4 - Masukkan keturunan ke dalam populasi.

• Langkah 5 - Sekarang, jika kondisi berhenti terpenuhi, kembalikan solusi dengan nilai kebugaran terbaiknya. Lain pergi ke langkah 2.

Menginstal Paket yang Diperlukan

Untuk memecahkan masalah dengan menggunakan Algoritma Genetika dengan Python, kita akan menggunakan paket yang kuat untuk GA bernama DEAP. Ini adalah pustaka kerangka kerja komputasi evolusioner baru untuk pembuatan prototipe dan pengujian ide yang cepat. Kami dapat menginstal paket ini dengan bantuan perintah berikut pada command prompt -

pip install deap

Jika Anda menggunakan anaconda lingkungan, maka perintah berikut dapat digunakan untuk menginstal deap -

conda install -c conda-forge deap

Menerapkan Solusi menggunakan Algoritma Genetika

Bagian ini menjelaskan implementasi solusi menggunakan Algoritma Genetika.

Menghasilkan pola bit

Contoh berikut menunjukkan kepada Anda cara menghasilkan string bit yang akan berisi 15 string, berdasarkan One Max masalah.

Impor paket yang diperlukan seperti yang ditunjukkan -

import random
from deap import base, creator, tools

Tentukan fungsi evaluasi. Ini adalah langkah pertama untuk membuat algoritma genetika.

def eval_func(individual):
   target_sum = 15
   return len(individual) - abs(sum(individual) - target_sum),

Sekarang, buat kotak alat dengan parameter yang tepat -

def create_toolbox(num_bits):
   creator.create("FitnessMax", base.Fitness, weights=(1.0,))
   creator.create("Individual", list, fitness=creator.FitnessMax)

Inisialisasi toolbox

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
   toolbox.attr_bool, num_bits)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Daftarkan operator evaluasi -

toolbox.register("evaluate", eval_func)

Sekarang, daftarkan operator crossover -

toolbox.register("mate", tools.cxTwoPoint)

Daftarkan operator mutasi -

toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)

Tentukan operator untuk berkembang biak -

toolbox.register("select", tools.selTournament, tournsize = 3)
return toolbox
if __name__ == "__main__":
   num_bits = 45
   toolbox = create_toolbox(num_bits)
   random.seed(7)
   population = toolbox.population(n = 500)
   probab_crossing, probab_mutating = 0.5, 0.2
   num_generations = 10
   print('\nEvolution process starts')

Evaluasi seluruh populasi -

fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
   ind.fitness.values = fit
print('\nEvaluated', len(population), 'individuals')

Buat dan ulangi dari generasi ke generasi -

for g in range(num_generations):
   print("\n- Generation", g)

Memilih individu generasi berikutnya -

offspring = toolbox.select(population, len(population))

Sekarang, kloning individu yang dipilih -

offspring = list(map(toolbox.clone, offspring))

Terapkan persilangan dan mutasi pada keturunan -

for child1, child2 in zip(offspring[::2], offspring[1::2]):
   if random.random() < probab_crossing:
   toolbox.mate(child1, child2)

Hapus nilai kebugaran anak

del child1.fitness.values
del child2.fitness.values

Sekarang, terapkan mutasi -

for mutant in offspring:
   if random.random() < probab_mutating:
   toolbox.mutate(mutant)
   del mutant.fitness.values

Evaluasi individu dengan kebugaran yang tidak valid -

invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
   ind.fitness.values = fit
print('Evaluated', len(invalid_ind), 'individuals')

Sekarang, ganti populasi dengan individu generasi berikutnya -

population[:] = offspring

Cetak statistik untuk generasi saat ini -

fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print('Min =', min(fits), ', Max =', max(fits))
print('Average =', round(mean, 2), ', Standard deviation =',
round(std, 2))
print("\n- Evolution ends")

Cetak hasil akhir -

best_ind = tools.selBest(population, 1)[0]
   print('\nBest individual:\n', best_ind)
   print('\nNumber of ones:', sum(best_ind))
Following would be the output:
Evolution process starts
Evaluated 500 individuals
- Generation 0
Evaluated 295 individuals
Min = 32.0 , Max = 45.0
Average = 40.29 , Standard deviation = 2.61
- Generation 1
Evaluated 292 individuals
Min = 34.0 , Max = 45.0
Average = 42.35 , Standard deviation = 1.91
- Generation 2
Evaluated 277 individuals
Min = 37.0 , Max = 45.0
Average = 43.39 , Standard deviation = 1.46
… … … …
- Generation 9
Evaluated 299 individuals
Min = 40.0 , Max = 45.0
Average = 44.12 , Standard deviation = 1.11
- Evolution ends
Best individual:
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 
 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0,
 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Number of ones: 15

Masalah Regresi Simbol

Ini adalah salah satu masalah paling terkenal dalam pemrograman genetik. Semua masalah regresi simbolik menggunakan distribusi data yang berubah-ubah, dan mencoba menyesuaikan data yang paling akurat dengan rumus simbolik. Biasanya, ukuran seperti RMSE (Root Mean Square Error) digunakan untuk mengukur kebugaran seseorang. Ini adalah masalah regressor klasik dan di sini kami menggunakan persamaannya5x³-6x²+8x=1. Kita perlu mengikuti semua langkah seperti pada contoh di atas, tetapi bagian utamanya adalah membuat himpunan primitif karena mereka adalah blok bangunan untuk individu sehingga evaluasi dapat dimulai. Di sini kita akan menggunakan set klasik primitif.

Kode Python berikut menjelaskan ini secara rinci -

import operator
import math
import random
import numpy as np
from deap import algorithms, base, creator, tools, gp
def division_operator(numerator, denominator):
   if denominator == 0:
      return 1
   return numerator / denominator
def eval_func(individual, points):
   func = toolbox.compile(expr=individual)
   return math.fsum(mse) / len(points),
def create_toolbox():
   pset = gp.PrimitiveSet("MAIN", 1)
   pset.addPrimitive(operator.add, 2)
   pset.addPrimitive(operator.sub, 2)
   pset.addPrimitive(operator.mul, 2)
   pset.addPrimitive(division_operator, 2)
   pset.addPrimitive(operator.neg, 1)
   pset.addPrimitive(math.cos, 1)
   pset.addPrimitive(math.sin, 1)
   pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
   pset.renameArguments(ARG0 = 'x')
   creator.create("FitnessMin", base.Fitness, weights = (-1.0,))
   creator.create("Individual",gp.PrimitiveTree,fitness=creator.FitnessMin)
   toolbox = base.Toolbox()
   toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
   toolbox.expr)
   toolbox.register("population",tools.initRepeat,list, toolbox.individual)
   toolbox.register("compile", gp.compile, pset = pset)
   toolbox.register("evaluate", eval_func, points = [x/10. for x in range(-10,10)])
   toolbox.register("select", tools.selTournament, tournsize = 3)
   toolbox.register("mate", gp.cxOnePoint)
   toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
   toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset)
   toolbox.decorate("mate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   toolbox.decorate("mutate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   return toolbox
if __name__ == "__main__":
   random.seed(7)
   toolbox = create_toolbox()
   population = toolbox.population(n = 450)
   hall_of_fame = tools.HallOfFame(1)
   stats_fit = tools.Statistics(lambda x: x.fitness.values)
   stats_size = tools.Statistics(len)
   mstats = tools.MultiStatistics(fitness=stats_fit, size = stats_size)
   mstats.register("avg", np.mean)
   mstats.register("std", np.std)
   mstats.register("min", np.min)
   mstats.register("max", np.max)
   probab_crossover = 0.4
   probab_mutate = 0.2
   number_gen = 10
   population, log = algorithms.eaSimple(population, toolbox,
      probab_crossover, probab_mutate, number_gen,
      stats = mstats, halloffame = hall_of_fame, verbose = True)

Perhatikan bahwa semua langkah dasar sama seperti yang digunakan saat membuat pola bit. Program ini akan memberi kita keluaran sebagai min, max, std (standar deviasi) setelah 10 jumlah generasi.