آشنایی با الگوریتم ژنتیک در پایتون

زمان مطالعه: 8 دقیقه

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

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

الگوریتم ژنتیک (Genetic Algorithms) چیست؟

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

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

مبنای تعریف الگوریتم ژنتیک

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

ژن‌ها و کروموزوم‌ها (Genes and Chromosomes)

در موجودات بیولوژیکی، ژن‌ها حاوی اطلاعات رمزگذاری شده‌ای هستند که ویژگی‌های یک موجود زنده را تعیین می‌کنند. در GA، این ایده تحت‌عنوان «کروموزوم» تعریف می‌شود که نشان دهنده راه‌حل‌های موجود در فضای جستجو (یا فضای محلول) است. هر کروموزوم متشکل از ژن‌هایی است که پارامترها (یا متغیرهای) راه‌حل را رمزگذاری می‌کنند.

جمعیت (Population)

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

تابع تناسب (Fitness Function)

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

انتخاب (Selection)

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

بازترکیب (Crossover)

در تولید مثل بیولوژیکی، فرزندان صفات ژنتیکی را از هر دو والد به ارث می‌برند. در GAs، متقاطع یا بازترکیب بخش‌هایی از دو کروموزوم والد را برای تولید فرزندان (راه‌حل‌های) جدید ترکیب و در نهایت نقاط جدیدی از فضای جستجو را پیدا می‌کند.

جهش (Mutation)

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

الگوریتم ژنتیک چطور کار می‌کند

الگوریتم ژنتیک چطور کا می کند

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

۱. مقداردهی اولیه

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

۲. ارزیابی تناسب اندام

هر کروموزوم (فرد) با تابع تناسب اندام ارزیابی می‌شود. این تابع به ما می‌گوید که یک ‌راه‌حل چقدر برای حل مسئله مناسب است. امتیاز بالاتر تناسب اندام به معنای عملکرد بهتر کروموزوم است.

برای مثال، اگر هدف به حداکثر رساندن مقدار تابعf(x)d باشد، امتیاز تناسب اندام برای فرد x همان f(x)d است. مسائل پیچیده‌تر ممکن است به ارزیابی تناسب اندام پیچیده نیاز داشته باشند، مانند بهینه‌سازی چند معیاری، که در آن چندین تابع معیار به‌طور همزمان بهینه می‌شوند.

۳. انتخاب والدین

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

استراتژی‌های محبوب انتخاب والدین عبارتند از:

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

۴. بازترکیب (متقاطع)

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

اپراتورهای متقاطع انواع مختلفی دارند:

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

۵. جهش

جهش تغییرات تصادفی را در ژن‌های فرزندان ایجاد می‌کند و برای جلوگیری از گیر افتادن الگوریتم در بهینه‌های محلی اهمیت زیادی دارد. این مرحله برای حفظ تنوع ژنتیکی در جمعیت بسیار مهم است و معمولا نرخ جهش پایین نگه داشته می‌شود تا از ایجاد اختلال در ‌راه‌حل‌های خوب جلوگیری شود.

جهش‌ها بسته به نمایش کروموزوم متفاوتند:

جهش Bit-Flip (باینری): در کروموزوم‌های دوتایی، جهش یک بیت تصادفی را از ۰ به ۱ یا برعکس تغییر می‌دهد.
جهش مبادله (جایگشتی): در هر جایگشت‌، دو ژن به طور تصادفی مبادله می‌شوند.
جهش گاوسی (حقیقی): برای کروموزوم‌های با ارزش واقعی، جهش با افزودن یک مقدار تصادفی کوچک توزیع شده گاوسی به ژن انجام می‌شود.

۶. جایگزینی

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

استراتژی‌های مختلف جایگزینی جمعیت عبارتند از:

جایگزینی نسل: کل جمعیت با فرزندان جایگزین می‌شود.
جایگزینی حالت پایدار: تنها تعداد کمی از افراد جمعیت در هر نسل جایگزین می‌شوند.
نخبه‌گرایی: نخبه‌گرایی با تضمین انتقال بدون تغییر بهترین افراد جمعیت فعلی به نسل بعدی، جلوی از دست رفتن بهترین ‌راه‌حل‌ها را می‌گیرد.

۷. شرط خاتمه

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

نسل‌ها به تعداد مشخصی می‌رسند.
دستیابی به ‌راه‌حلی با ارزش تناسب که هدف مورد نظر را برآورده می‌کند.
مشاهده هم‌گرایی در جمعیت، جایی که بهترین تناسب اندام برای چندین نسل تغییر نمی‌کند.

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

برای استفاده از الگوریتم‌های ژنتیک در پایتون، می‌توانید از کتابخانه‌های پایتون که برای پیاده‌سازی این الگوریتم‌ها ساخته شده‌اند استفاده کنید. سه کتابخانه کاربردی پایتون برای پیاده‌سازی Genetic Algorithms عبارتند از:

DEAP (Distributed Evolutionary Algorithms in Python)
PyGAD
GeneticAlgorithmPython

در بین این کتابخانه‌ها، DEAP از محبوبیت بیشتری برخوردار است.

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

کد زیر یک مثال ساده از الگوریتم ژنتیک در پایتون با استفاده از کتابخانه DEAP است که در آن، مسئله یافتن عددی است که مقدار تابع f(x)=x2 را به حداکثر برساند.

import random
from deap import base, creator, tools, algorithms

# ایجاد نوع فرد با امتیاز وزن مثبت
creator.create(“FitnessMax”, base.Fitness, weights=(1.0,))
creator.create(“Individual”, list, fitness=creator.FitnessMax)

# تنظیمات پایه
toolbox = base.Toolbox()
toolbox.register(“attr_int”, random.randint, 0, 100)
toolbox.register(“individual”, tools.initRepeat, creator.Individual, toolbox.attr_int, 1)
toolbox.register(“population”, tools.initRepeat, list, toolbox.individual)

# تابع تناسب اندام
def evalOneMax(individual):
return individual[0]**2,

toolbox.register(“evaluate”, evalOneMax)
toolbox.register(“mate”, tools.cxTwoPoint)
toolbox.register(“mutate”, tools.mutFlipBit, indpb=0.05)
toolbox.register(“select”, tools.selTournament, tournsize=3)

# الگوریتم ژنتیک
def main():
pop = toolbox.population(n=300)
hof = tools.HallOfFame(1)

algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40,
halloffame=hof, verbose=False)

print(“Best individual:”, hof[0])
print(“Fitness of best individual:”, hof[0].fitness.values[0])
if __name__ == “__main__”:
main()

import random

from deap import base, creator, tools, algorithms

# ایجاد نوع فرد با امتیاز وزن مثبت

creator.create(“FitnessMax”, base.Fitness, weights=(1.0,))

creator.create(“Individual”, list, fitness=creator.FitnessMax)

# تنظیمات پایه

toolbox = base.Toolbox()

toolbox.register(“attr_int”, random.randint, 0, 100)

toolbox.register(“individual”, tools.initRepeat, creator.Individual, toolbox.attr_int, 1)

toolbox.register(“population”, tools.initRepeat, list, toolbox.individual)

# تابع تناسب اندام

def evalOneMax(individual):

return individual[0]**2,

toolbox.register(“evaluate”, evalOneMax)

toolbox.register(“mate”, tools.cxTwoPoint)

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

toolbox.register(“select”, tools.selTournament, tournsize=3)

# الگوریتم ژنتیک

def main():

pop = toolbox.population(n=300)

hof = tools.HallOfFame(1)

algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40,

halloffame=hof, verbose=False)

print(“Best individual:”, hof[0])

print(“Fitness of best individual:”, hof[0].fitness.values[0])

if __name__ == “__main__”:

main()

مزایا و معایب الگوریتم ژنتیک

با توجه به ساختار و نحوه عملکرد الگوریتم ژنتیک در پایتون، این ابزار یکی از کاربردی‌ترین الگوریتم‌های بهینه‌سازی است. از مزایای اصلی GAها می‌توانیم به موارد زیر اشاره کنیم:

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

معایب الگوریتم ژنتیک در پایتون

در کنار مزایایی که این الگوریتم‌ها ارائه می‌دهند، معایب و محدودیت‌هایی هم دارند که در ادامه به آن‌ها اشاره می‌کنیم:

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

کلام آخر

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

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

منابع

datacamp.com

سوالات متداول

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

DEAP: انعطاف‌پذیر و قدرتمند برای طراحی الگوریتم‌های تکاملی
PyGAD: ساده برای شروع و دارای مستندات قابل‌فهم
inspyred: برای مسائل تحقیقاتی و قابل‌توسعه

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

🏷️ برچسب‌ها: پایتون

آشنایی با الگوریتم ژنتیک در پایتون