AI กับ Python - Genetic Algorithms

บทนี้จะกล่าวถึงอัลกอริทึมทางพันธุกรรมของ AI โดยละเอียด

Genetic Algorithms คืออะไร?

Genetic Algorithms (GAs) เป็นอัลกอริธึมที่ใช้การค้นหาตามแนวคิดของการคัดเลือกโดยธรรมชาติและพันธุศาสตร์ GAs เป็นชุดย่อยของสาขาการคำนวณที่ใหญ่กว่าที่เรียกว่า Evolutionary Computation

GAs ได้รับการพัฒนาโดย John Holland และนักศึกษาและเพื่อนร่วมงานของเขาที่ University of Michigan โดยเฉพาะอย่างยิ่ง David E. Goldberg ตั้งแต่นั้นมาได้มีการพยายามแก้ไขปัญหาการเพิ่มประสิทธิภาพต่างๆโดยประสบความสำเร็จในระดับสูง

ใน GAs เรามีแนวทางแก้ไขที่เป็นไปได้สำหรับปัญหาที่กำหนด จากนั้นวิธีการแก้ปัญหาเหล่านี้จะผ่านการรวมตัวกันใหม่และการกลายพันธุ์ (เช่นเดียวกับในพันธุศาสตร์ตามธรรมชาติ) สร้างลูกใหม่และกระบวนการนี้จะทำซ้ำหลายชั่วอายุคน แต่ละคน (หรือวิธีการแก้ปัญหาของผู้สมัคร) จะได้รับการกำหนดค่าสมรรถภาพ (ตามค่าฟังก์ชันวัตถุประสงค์) และบุคคลที่เหมาะสมจะได้รับโอกาสในการผสมพันธุ์และให้ผลผลิตสูงขึ้นfitterบุคคล ซึ่งสอดคล้องกับทฤษฎีดาร์วินของSurvival of the Fittest.

ดังนั้นจึงช่วยให้ evolving บุคคลที่ดีขึ้นหรือแนวทางแก้ไขในช่วงหลายชั่วอายุคนจนกว่าจะถึงเกณฑ์หยุด

อัลกอริทึมทางพันธุกรรมมีลักษณะสุ่มอย่างเพียงพอ แต่ทำงานได้ดีกว่าการค้นหาในท้องถิ่นแบบสุ่ม (ซึ่งเราแค่ลองใช้วิธีการแก้ปัญหาแบบสุ่มติดตามสิ่งที่ดีที่สุดจนถึงตอนนี้) เนื่องจากใช้ประโยชน์จากข้อมูลในอดีตเช่นกัน

วิธีใช้ GA สำหรับปัญหาการเพิ่มประสิทธิภาพ

การเพิ่มประสิทธิภาพเป็นการดำเนินการเพื่อให้การออกแบบสถานการณ์ทรัพยากรและระบบมีประสิทธิผลมากที่สุด แผนภาพบล็อกต่อไปนี้แสดงกระบวนการเพิ่มประสิทธิภาพ -

ขั้นตอนของกลไก GA สำหรับกระบวนการเพิ่มประสิทธิภาพ

ต่อไปนี้เป็นลำดับขั้นตอนของกลไก GA เมื่อใช้เพื่อเพิ่มประสิทธิภาพของปัญหา

  • ขั้นตอนที่ 1 - สร้างประชากรเริ่มต้นแบบสุ่ม

  • ขั้นตอนที่ 2 - เลือกโซลูชันเริ่มต้นที่มีค่าสมรรถภาพที่ดีที่สุด

  • ขั้นตอนที่ 3 - รวมโซลูชันที่เลือกใหม่โดยใช้ตัวดำเนินการการกลายพันธุ์และครอสโอเวอร์

  • ขั้นตอนที่ 4 - ใส่ลูกหลานเข้าไปในประชากร

  • ขั้นตอนที่ 5 - ตอนนี้หากตรงตามเงื่อนไขการหยุดให้ส่งคืนโซลูชันพร้อมค่าสมรรถภาพที่ดีที่สุด จากนั้นไปที่ขั้นตอนที่ 2

การติดตั้งแพ็คเกจที่จำเป็น

สำหรับการแก้ปัญหาโดยใช้ Genetic Algorithms ใน Python เราจะใช้แพ็คเกจที่มีประสิทธิภาพสำหรับ GA ที่เรียกว่า DEAP. เป็นคลังกรอบการคำนวณเชิงวิวัฒนาการใหม่สำหรับการสร้างต้นแบบและการทดสอบความคิดอย่างรวดเร็ว เราสามารถติดตั้งแพ็คเกจนี้ด้วยความช่วยเหลือของคำสั่งต่อไปนี้ใน command prompt -

pip install deap

หากคุณกำลังใช้ anaconda จากนั้นสามารถใช้คำสั่งต่อไปนี้เพื่อติดตั้ง deap -

conda install -c conda-forge deap

การนำโซลูชันไปใช้โดยใช้อัลกอริทึมทางพันธุกรรม

ส่วนนี้จะอธิบายเกี่ยวกับการใช้งานโซลูชันโดยใช้ Genetic Algorithms

การสร้างรูปแบบบิต

ตัวอย่างต่อไปนี้แสดงวิธีการสร้างสตริงบิตที่จะมี 15 สตริงโดยยึดตาม One Max ปัญหา.

นำเข้าแพ็คเกจที่จำเป็นตามที่แสดง -

import random
from deap import base, creator, tools

กำหนดฟังก์ชันการประเมิน เป็นขั้นตอนแรกในการสร้างอัลกอริทึมทางพันธุกรรม

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

ตอนนี้สร้างกล่องเครื่องมือด้วยพารามิเตอร์ที่ถูกต้อง -

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

เริ่มต้นกล่องเครื่องมือ

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)

ลงทะเบียนผู้ดำเนินการประเมิน -

toolbox.register("evaluate", eval_func)

ตอนนี้ลงทะเบียนตัวดำเนินการครอสโอเวอร์ -

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

ลงทะเบียนตัวดำเนินการกลายพันธุ์ -

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

กำหนดผู้ดำเนินการผสมพันธุ์ -

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')

ประเมินประชากรทั้งหมด -

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

สร้างและทำซ้ำหลายชั่วอายุคน -

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

การเลือกบุคคลรุ่นต่อไป -

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

ตอนนี้โคลนบุคคลที่เลือก -

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

ใช้ครอสโอเวอร์และการกลายพันธุ์กับลูกหลาน -

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

ลบค่าสมรรถภาพของเด็ก

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

ตอนนี้ใช้การกลายพันธุ์ -

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

ประเมินบุคคลที่มีสมรรถภาพไม่ถูกต้อง -

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')

ตอนนี้แทนที่ประชากรด้วยบุคคลรุ่นต่อไป -

population[:] = offspring

พิมพ์สถิติสำหรับคนรุ่นปัจจุบัน -

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")

พิมพ์ผลลัพธ์สุดท้าย -

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

ปัญหาการถดถอยสัญลักษณ์

เป็นหนึ่งในปัญหาที่ทราบกันดีที่สุดในการเขียนโปรแกรมทางพันธุกรรม ปัญหาการถดถอยเชิงสัญลักษณ์ทั้งหมดใช้การกระจายข้อมูลโดยพลการและพยายามปรับให้พอดีกับข้อมูลที่ถูกต้องที่สุดด้วยสูตรสัญลักษณ์ โดยปกติการวัดเช่น RMSE (Root Mean Square Error) จะใช้ในการวัดสมรรถภาพของแต่ละบุคคล มันเป็นปัญหาการถอยหลังแบบคลาสสิกและที่นี่เรากำลังใช้สมการ5x3-6x2+8x=1. เราจำเป็นต้องทำตามขั้นตอนทั้งหมดตามตัวอย่างข้างต้น แต่ส่วนหลักคือการสร้างชุดดั้งเดิมเนื่องจากเป็นองค์ประกอบพื้นฐานสำหรับแต่ละบุคคลเพื่อให้การประเมินเริ่มต้นได้ ที่นี่เราจะใช้ชุดดั้งเดิมของคลาสสิก

รหัส Python ต่อไปนี้อธิบายรายละเอียดนี้ -

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)

โปรดทราบว่าขั้นตอนพื้นฐานทั้งหมดจะเหมือนกับที่ใช้ในขณะสร้างรูปแบบบิต โปรแกรมนี้จะให้ผลลัพธ์เป็น min, max, std (ค่าเบี่ยงเบนมาตรฐาน) หลังจาก 10 ชั่วอายุคน