الگوریتم ژنتیک genetic algorithm
الگوریتم ژنتیک genetic algorithm
الگوریتم ژنتیک یا (GA) از دیگر استراتژی های جست وجوی محلی و شکلی از "جست وجوی پرتوی اتفاقی" است که در آن حالتهای پسین از طریق ترکیب دو حالت والد تولید میشود. در مقایسه با انتخاب طبیعی مثل جست وجوی پرتوی اتفاقی عمل میکند. با این تفتوت که در اینجا با تولید مثل جنسی سروکار داریم نه غیر جنسی.
الگوریتم ژنتیک با مجموعه ای از k حالت که بطور تصادفی تولید شده اند، شروع میکند که جمعیت نام دارد.هر حالت یا فرد بصورت رشته ای بر روی الفبای متناهی نمایش داده میشود. هر حالت توسط یک "تابع هدف" یا یک تابع برازش ارزیابی میشود. تابع برازش باید برای حالتهای بهتر، مقادیر بزرگتری را برگرداند. در شکل خاصی از الگوریتم ژنتیک (مانند مسئله هشت وزیر) احتمال انتخاب برای تولیدمثل مستقیما متناسب با امیتاز برازش است. در ادامه حل مسئله به روش الگوریتم ژنتیک، دو زوج بطور تصادفی برای تولید مثل انتخاب میشوند. برای هر زوجی که باید جفت گیری کنند، یک نقطه پیوند بطور تصادفی بین موقعیت ها انتخاب میشود.
وقتی دو حالت والد، کاملا فرق میکنند عملیات پیوند میتواند حالتی را تولید کند که از هر دو والد به یک فاصله است. معمولا ابتدا جمعیت در فرآیند متنوع است، لذا عمل پیوند (همانند الگوریتم simulated annealing) معمولا در ابتدا مراحل طولانی را در فضای حالت انتخاب میکند و به تدریج که افراد کاملا مشابه میشوند، مراحل کوتاهتر را انتخاب میکند.
همانند جست وجوی پرتوی اتفاقی، الگوریتم ژنتیک نوعی تپه نوردی همراه با اکتشاف تصادفی را با تبادل اطلاعات بین نخ های جست وجوی موازی، با هم ترکیب میکند. امتیازات الگوریتم ژنتیک ناشی از عملیات پیوند است. نتیجه ی این ترکیب است این است که عملکرهای مفیدی را ارائه میکند. لذا منجر به افزایش دقت عملکرد جست وجو میشود.
نظریه های الگوریتم های ژنتیک توضیح میدهند که این کار چگونه با استفاده از ایده ی الگو انجام میشود. الگو زیر رشته ای است که بعضی از موقعیت های آن مشخص نشده باقی میمانند. رشته هایی که با الگو مطابقت میکنند نمونه هایی از الگو نامیده میشوند. الگوریتم های ژنتیک وقتی به خوبی کار میکنند که الگوها متناظر با قطعات با معنایی از جواب باشند.
در عمل الگوریتم های ژنتیک اثر وسیعی در مسئله های بهینه سازی مثل زمانبندی کار و طراحی مدارات مجتمع داشته است.
شبه کد الگوریم ژنتیک:
function GENETIC-ALGPRITHM (population, FITNESS-FN) returns an individual
inputs : population, a set of individuals
FITNESS-FN, a function that measure the fitness of an individual
repeat
new_population <-- empty set
for i= = 1 to SIZE(population) do
x <-- RANDOM-SELECTION (population, FITNESS-FN)
y <-- RANDOM-SELECTION (population, FITNESS-FN)
Child <-- REPRODUCE (x ,y)
if (small random probability) then child <-- MUTATE(child)
add child to new_population
Population <-- new_population
until some individual is fit enough , or enough time has elapsed
return the best individual in population, according to FITNESS-FN
function REPRODUCE (x, y) returns an individual
input : x , y , parent individuals
n <-- LENGTH (x); c <-- random number from 1 to n
return APPEND (SUBSTRING(x,1, c), SUBSTRING(y, c+1, n))
