آموزش هوش مصنوعی با پایتون - الگوریتم‌های ژنتیک

این فصل الگوریتم‌های ژنتیک در هوش مصنوعی را به‌صورت مفصل بررسی می‌کند.

الگوریتم‌های ژنتیک چیستند؟

الگوریتم‌های ژنتیک (GAs) الگوریتم‌های مبتنی بر جست‌وجو هستند که بر اساس مفاهیم انتخاب طبیعی و ژنتیک طراحی شده‌اند. الگوریتم‌های ژنتیک زیرمجموعه‌ای از شاخه بسیار گسترده‌تری از محاسبات به نام محاسبات تکاملی هستند.

الگوریتم‌های ژنتیک توسط جان هالند و دانشجویان و همکارانش در دانشگاه میشیگان، به‌ویژه دیوید ای. گلدبرگ، توسعه داده شدند. از آن زمان تاکنون، این الگوریتم‌ها با موفقیت چشمگیری در مسائل مختلف بهینه‌سازی به کار گرفته شده‌اند.

در الگوریتم‌های ژنتیک، مجموعه‌ای از راه‌حل‌های احتمالی برای مسئله موردنظر در اختیار داریم. سپس این راه‌حل‌ها فرایندهای ترکیب مجدد و جهش را پشت سر می‌گذارند (مشابه آنچه در ژنتیک طبیعی رخ می‌دهد)، فرزندان جدیدی تولید می‌کنند و این فرایند در نسل‌های مختلف تکرار می‌شود. به هر فرد (یا راه‌حل کاندید) یک مقدار برازندگی اختصاص داده می‌شود که بر اساس مقدار تابع هدف آن تعیین می‌شود. افراد با برازندگی بیشتر، شانس بالاتری برای جفت‌گیری و تولید افراد برازش‌یافته‌تر دارند. این فرایند با نظریه داروینی بقای اصلح هم‌خوانی دارد.

به این ترتیب، این الگوریتم در طول نسل‌های مختلف به تکامل افراد یا راه‌حل‌های بهتر ادامه می‌دهد تا زمانی که به معیار توقف برسد.

الگوریتم‌های ژنتیک ذاتاً تا حد زیادی تصادفی هستند، اما عملکرد آن‌ها بسیار بهتر از جست‌وجوی محلی تصادفی است؛ روشی که در آن فقط راه‌حل‌های تصادفی را امتحان می‌کنیم و بهترین راه‌حل پیدا‌شده تا آن لحظه را نگه می‌داریم. دلیل این برتری آن است که الگوریتم‌های ژنتیک از اطلاعات تاریخی نیز بهره می‌برند.

چگونه از الگوریتم ژنتیک برای مسائل بهینه‌سازی استفاده کنیم؟

بهینه‌سازی به معنای طراحی یا تنظیم یک وضعیت، منبع یا سیستم به‌گونه‌ای است که تا حد امکان اثربخش باشد. نمودار بلوکی زیر فرایند بهینه‌سازی را نشان می‌دهد:

مراحل سازوکار الگوریتم ژنتیک در فرایند بهینه‌سازی

در ادامه، توالی مراحل سازوکار الگوریتم ژنتیک هنگام استفاده از آن برای بهینه‌سازی مسائل آمده است.

• مرحله ۱: جمعیت اولیه را به‌صورت تصادفی تولید کنید.

• مرحله ۲: راه‌حل اولیه با بهترین مقادیر برازندگی را انتخاب کنید.

• مرحله ۳: راه‌حل‌های انتخاب‌شده را با استفاده از عملگرهای جهش و تقاطع با یکدیگر ترکیب کنید.

• مرحله ۴: یک فرزند را به جمعیت اضافه کنید.

• مرحله ۵: اکنون، اگر شرط توقف برقرار شده است، راه‌حلی را که بهترین مقدار برازندگی را دارد برگردانید. در غیر این صورت، به مرحله ۲ بروید.

نصب بسته‌های موردنیاز

برای حل مسئله با استفاده از الگوریتم‌های ژنتیک در پایتون، از یک بسته قدرتمند به نام DEAP استفاده خواهیم کرد. این بسته، کتابخانه‌ای از یک چارچوب نوین محاسبات تکاملی است که برای نمونه‌سازی سریع و آزمایش ایده‌ها طراحی شده است. می‌توانیم این بسته را با اجرای دستور زیر در خط فرمان نصب کنیم:

pip install deap

اگر از محیط anaconda استفاده می‌کنید، می‌توانید برای نصب deap از دستور زیر استفاده کنید:

conda install -c conda-forge deap

پیاده‌سازی راه‌حل‌ها با استفاده از الگوریتم‌های ژنتیک

این بخش نحوه پیاده‌سازی راه‌حل‌ها با استفاده از الگوریتم‌های ژنتیک را توضیح می‌دهد.

تولید الگوهای بیتی

مثال زیر نشان می‌دهد که چگونه می‌توان بر اساس مسئله 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 (ریشه میانگین مربعات خطا) استفاده می‌شود. این یک مسئله کلاسیک رگرسیون است و در اینجا از معادله 5x³-6x²+8x=1 استفاده می‌کنیم. باید تمام مراحل مثال قبلی را دنبال کنیم، اما بخش اصلی کار، ایجاد مجموعه‌های اولیه (primitive sets) است؛ زیرا این مجموعه‌ها اجزای سازنده افراد هستند و امکان آغاز ارزیابی را فراهم می‌کنند. در اینجا از مجموعه کلاسیک عملگرهای اولیه استفاده خواهیم کرد.

کد پایتون زیر این موضوع را به‌صورت مفصل توضیح می‌دهد:

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)

توجه داشته باشید که تمام مراحل پایه همان مراحلی هستند که هنگام تولید الگوهای بیتی استفاده شدند. این برنامه پس از اجرای ۱۰ نسل، خروجی‌هایی شامل حداقل، حداکثر و انحراف معیار (std) را به ما ارائه می‌دهد.