هوش مصنوعی با پایتون – الگوریتم های ژنتیک

هوش مصنوعی با پایتون – الگوریتم های ژنتیک

در این درس از مجموعه آموزش برنامه نویسی سایت سورس باران، الگوریتم های ژنتیک هوش مصنوعی (Genetic Algorithms) به طور مفصل مورد بحث قرار می گیرد.

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

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

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

پیشنهاد ویژه : پکیج آموزش پروژه محور پایتون

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

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

الگوریتم های ژنتیک ماهیت کاملاً تصادفی دارند، اما عملکرد آنها بسیار بهتر از جستجوی محلی تصادفی است (جایی که ما فقط راه حل های تصادفی را امتحان می کنیم و بهترین ها را ردیابی می کنیم)، زیرا از اطلاعات تاریخی نیز بهره برداری می کنند.

چگونه می توان از GA برای مشکلات بهینه سازی استفاده کرد؟

بهینه سازی عملی است که باعث می شود طراحی، وضعیت، منابع و سیستم تا حد ممکن موثر باشد. نمودار بلوکی زیر روند بهینه سازی را نشان می دهد –

مراحل مکانیسم GA برای فرآیند بهینه سازی

موارد زیر دنباله ای از مراحل مکانیسم GA است که برای بهینه سازی مشکلات استفاده می شود.

• مرحله ۱ – جمعیت اولیه را به طور تصادفی ایجاد کنید.
• مرحله ۲ – راه حل اولیه را با بهترین مقادیر تناسب اندام انتخاب کنید.
• مرحله ۳ – راه حلهای انتخاب شده را با استفاده از عملگرهای جهش و کراس اوور ترکیب کنید.
• مرحله ۴ – فرزندان را در جمعیت وارد کنید.
• مرحله ۵ – اکنون ، اگر شرط توقف برآورده شود ، محلول را با بهترین مقدار تناسب اندام خود برگردانید. در غیر اینصورت به مرحله ۲ بروید.

نصب پکیج های ضروری

برای حل مسئله با استفاده از الگوریتم های ژنتیک در پایتون، ما قصد داریم از یک بسته قدرتمند برای GA به نام 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:
[۰, ۰, ۰, ۱, ۰, ۰, ۰, ۰, ۰, ۱, ۰, ۰, ۰, ۰, ۱, ۰, ۱, 
 ۱, ۰, ۰, ۰, ۱, ۰, ۰, ۰, ۱, ۱, ۰, ۰, ۰, ۱, ۰, ۰, ۰,
 ۱, ۰, ۰, ۱, ۱, ۱, ۰, ۰, ۱, ۰, ۱]
Number of ones: 15

مشکل رگرسیون نمادین

این یکی از بهترین مشکلات شناخته شده در برنامه نویسی ژنتیکی است. تمام مشکلات رگرسیون نمادین از توزیع دلخواه داده استفاده می کنند و سعی می کنند دقیق ترین داده ها را با یک فرمول نمادین متناسب کنند. معمولاً برای اندازه گیری تناسب اندام فردی از معیارهایی مانند (RMSE (Root Mean Square Error  استفاده می شود. این یک مسئله رگرسیون کلاسیک است و در اینجا ما از معادله ۵×۳-۶×۲ + ۸x = 1 استفاده می کنیم. ما باید تمام مراحل را مانند مثال بالا دنبال کنیم ، اما قسمت اصلی ایجاد مجموعه های ابتدایی است زیرا آنها عناصر سازنده افراد هستند تا ارزیابی شروع شود. در اینجا ما از مجموعه کلاسیک بدوی استفاده خواهیم کرد.

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 (انحراف معیار) به ما می دهد.

منبع.

لیست جلسات قبل آموزش هوش مصنوعی با برنامه نویسی پایتون

1. آموزش هوش مصنوعی با برنامه نویسی پایتون – مفهوم کلی
2. شروع آموزش هوش مصنوعی با برنامه نویسی پایتون
3. یادگیری ماشین در هوش مصنوعی با برنامه نویسی پایتون
4. هوش مصنوعی با برنامه نویسی پایتون، آماده ‌سازی داده ها
5. هوش مصنوعی با پایتون، یادگیری نظارت شده و طبقه بندی
6. هوش مصنوعی با برنامه نویسی پایتون – یادگیری تحت نظارت: رگرسیون
7. هوش مصنوعی با برنامه نویسی پایتون – برنامه نویسی منطقی
8. هوش مصنوعی با پایتون – یادگیری بدون نظارت: خوشه بندی
9. هوش مصنوعی با پایتون – پردازش زبان طبیعی
10. هوش مصنوعی با پایتون – پکیج NLTK
11. هوش مصنوعی با پایتون – تجزیه و تحلیل داده های سری زمانی
12. هوش مصنوعی با پایتون – تشخیص گفتار
13. هوش مصنوعی با پایتون – جستجوی کاشف
14. هوش مصنوعی با پایتون – بازی
15. هوش مصنوعی با پایتون – شبکه های عصبی
16. هوش مصنوعی با پایتون – یادگیری Reinforcement