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

الگوریتم ژنتیک چیست؟ در این آموزش به این سوال پاسخ خواهیم داد که الگوریتم ژنتیک چیست و چه کاربردی دارد ؟ با مفهوم الگوریتم ژنتیک آشنا میشویم . پس با آموزش الگورتیم ژنتیک به زبان ساده با ما همراه باشید.

مقدمه ای در خصوص الگوریتم ژنتیک :

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

الگوریتم های ژنتیک به طور کلی برای حل مسائل بهینه سازی و جستجو استفاده می شود.

این الگوریتم یک الگوریتم کلی است به طوری که در مسائل مختلف به راحتی قابل پیاده سازی است و می تواند نتایج بهتری را در هر تکرار از جستجو ارائه دهد.

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

اصطلاحات الگوریتم ژنتیک

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

  • جمعیت یا Population : مجموعه ای از راه حل های ممکن.
  • کروموزوم یا Chromosome : یک راه حل ممکن .
  • ژن یا Gene ، هر کروموزوم از چندین ژن ساخته شده است.
  • آلل یا Allele : مقداری که در یک ژن قرار میگیرد.
  • ژنوتیپ یا Genotype : عناصر موجود در کروموزوم ها.
  • فنوتیپ یا Phenotype: ارزش ژنوتیپ
  • Fitness function : تابع شایستگی یا برازش
  • Generation : تعداد نسل ها ، یا تعداد دفعات تکرار الگوریتم
اصطلاحات الگوریتم ژنتیک
اصطلاحات الگوریتم ژنتیک

مراحل الگوریتم ژنتیک: پنج مرحله اصلی در الگوریتم ژنتیک در نظر گرفته شده است:

  1. جمعیت اولیه : Initial population
  2. محاسبه شایستگی : Fitness function
  3. انتخاب : Selection
  4. کراس اوور یا ترکیب : Crossover
  5. جهش : Mutation
مراحل الگوریتم ژنتیک
مراحل الگوریتم ژنتیک : 5 مرحله اصلی الگوریتم ژنتیک

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

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

حال الگوریتم وارد یک چرخه یا تکرار میشود:

  1. مرحله انتخاب : از بین جمعیت فعلی ، تعدادی را بر تولید مثل انتخاب میکند و اصطلاحا در جایی بنام حوضچه ازدواج قرار میدهد.
  2. مرحله ترکیب : از حوضچه ازدواج دو نفر (که به آنها والدین میگوییم) انتخاب میشوند و با هم ترکیب میشوند و دو جواب جدید یا دو فرزند تولید میشود.
  3. مرحله جهش : پاسخ های تولید شده در مرحله ترکیب، یعنی فرزندان ، را بصورت اتفاقی کمی تغییر میدهیم.
  4. مرحله ارزیابی : در اینجا تعداد جواب جدید داریم (نسل جدیدی داریم که شامل همه فرزندان است) ، این فرزندان را با تابع شاستگی مورد ارزیابی قرار میدهیم.
  5. اگر شرط توقف الگوریتم بر قرار شده که تمام وگرنه به مرحله 1 یعنی مرحله انتخاب میرویم.

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

فنوتایپ چیست ؟ ژنوتایپ چیست؟ : در این بخش بهتر دیدم به سوالی که برای خیلی از دوستان پیش میاد پاسخ بدهم ، فرق بین فنوتایپ و ژنوتایپ چیه؟

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

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

مثال فنوتایپ : در اینجا ترتیب شهر ها جواب مسئله ما می باشد بعنوان مثال هر یک از موارد زیر یک جواب است:
  • تهران، اصفهان، اراک، قزوین ، تهران
  • تهران، اراک ، اصفهان ، قزوین ، تهران
  • تهران ، قزوین، اصفهان، اراک ، تهران
  • تهران، قزوین، اراک ، اصفهان ، تهران

خب اگر بخواهیم این مسئله را با الگورتیم ژنتیک جل کنیم ، ما در برنامه خود به هر شهر یک کد میدهیم ، مثلا تهران عدد 1 ، اراک عدد 2 ، اصفهان عدد 3 و قزوین عدد 4 ، حالا با این فرض راه حل هایی که در بالا بصورت فنوتایپ مثال زدیم به شکل زیر خواهند شد:

  • 1 ، 3 ، 2 ، 4 ، 1
  • 1 ، 2 ، 3 ، 4 ، 1
  • 1 ، 4 ، 3 ، 2 ، 1
  • 1 ، 4 ، 2 ، 3 ، 1

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

فنوتایپ : نمایش راه حل ها در دنیای واقعی می باشد . ژنوتایپ : نمایش راه حل در حالت محاسباتی یا در برنامه کامپیوتری می باشد.

مفهوم فنوتایپ و ژنوتایپ
مفهوم فنوتایپ و ژنوتایپ

جمعیت در الگوریتم ژنتیک (Population)

به مجموعه ای از راه حل ها در الگوریتم ژنتیک، جمعیت گفته میشود. بعنوان مثال ما در بالا برای فروشنده دوره گرد 4 راه حل را لیست کردیم ، این 4 راه حل را میتوانیم یک جمعیت برای این مسئله در نظر بگیریم. (یک جمعیت 4 نفره)

در حالت کلی جمعیت : یک زیر مجموعه از تمام راه حل های ممکن (رمزگذاری شده) برای مسئله ارائه شده می باشد.

معمولا در الگوریتم Genetic ، جمعیت را با یک آرایه یا ماتریس نمایش میدهند. به تصویر زیر دقت کنید.

کروموزوم در الگوریتم ژنتیک (Chromosomes)

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

اگر جمعیت را بصورت یک ماتریس نمایش دهیم ، هر سطر این ماتریس یک کروموزوم می باشد.

مفهوم ژن در الگوریتم ژنتیک (Gene)

هر کروموزوم از یک یا چند ژن ساخته شده است. ژن ها در واقع مشخص میکنند که هر کروموزوم چند ویژگی یا چند مولفه دارید.

اگر کروموزوم را یک آرایه در نظر بگیریم، هر خانه آرایه یک ژن خواهد بود.

آلل در الگوریتم ژنیتک (َAllele)

مقداری که در یک ژن قرار میگیرد را آلل مینامیم.

هر ژن ، داری یک مجموعه مقادیر مجاز می باشد. مثلا اگر رنگ چشم را در ژن انسان در نظر بگیریم رنگ هایی مثل سیاه، قهوه ای ، سبز ، آبی بعنوان مقادیر مجاز برای این ژن می باشد.

مفاهیم الگوریتم ژنتیک
جمعیت ،کروموزوم، ژن، آلل

برای یک مسئله باینری ، مقدار یک آلل یا 0 و یا 1 خواهد بود.

نمایش راه حل در الگوریتم ژنتیک

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

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

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

  • بازنمایی باینری ،
  • بازنمایی اعداد صحیح ،
  • بازنمایی اعشاری ،
  • بازنمایی جایگشتی.
نمایش راه حل در الگوریتم ژنتیک ، بازنمایی راه حل
نمایش راه حل در الگوریتم ژنتیک ، بازنمایی راه حل

بازنمایی باینری : Binary Representation

این یکی از ساده ترین و پرکاربردترین نمایش ها در GA است. در این نوع نمایش ژنوتیپ از رشته های بیت تشکیل شده است (یعنی مقدار هر ژن یا 0 است یا 1).

برای مسالی که فضای حل متغیرهای تصمیم بولیم باشد ( بله یا خیر ) ، نمایش باینری طبیعی است.

به عنوان مثال مسئله کوله پشتی 0/1 را در نظر بگیرید. در این مسئله از بین n کالا میخواهیم تعدادی را در یک کوله پشتی قرار دهیم و بدنبال برداشتن با ارزش ترین اجناس هستم. در این مسئله برای هر کالا ، ما دو حالت داریم یا آن را در کوله پشتی قرار میدهیم (1) یا قرار نمیدهیم (0) . پس نمایش باینری برای این مسئله کاملا مناسب است.

بعنوان مثال اگر ما 10 کالا برای انتخاب داشته باشیم یک راه حل میتواند بصورت زیر باشد:

1001011100
ترتیب پردازش کروموزوم از چپ به راست است.

به این معنی که : کالای شماره3و4و5و7و10 را در کوله پشتی قرار دهیم.

نمایش اعداد صحیح (Integer Representation)

برای مسائلی که گسسته هستند ، نمایش عدد صحیح یک نمایش مناسب است. یعنی مقدار هر ژن یک عدد صحیح و گسسته خواهد بود.

بعنوان مثال مسئله تخصیص وظایف را در نظر بگرید. در این مسئله مثلا 3 نفر داریم که کارها را انجام میدهند و 10 کار برای انجام دادن وجود دارد. حال میتوانیم متغیر مسئله را این در نظر بگیریم که هر کار توسط چه کسی انجام شود. پس هر کار میتواند توسط سرویس دهنده شماره 1 یا 2 یا 3 انجام شود. یعنی ما 10 ژن خواهیم داشت و مقدار هر ژن یک عدد بین 1 تا 3 خواهد بود.

2313321132
ترتیب پردازش کروموزوم از چپ به راست است.
  • کار شماره 3 و 4 و 8 توسط سرویس دهنده 1 انجام شود،
  • کار شماره 1 و 5 و 10 توسط سرویس دهنده 2 انجام شود ،
  • کار شماره 2 و 6 و 7 و 9 توسط سرویس دهنده 3 انجام شود ،

بازنمایی اعشاری : Real Valued Representation

برای مسائلی که مقدار متغیرهای آنها عدی حقیقی باشد ، بهتر است که از نمایش اعشاری استفاده کنیم. بعنوان مثال برای حل تابع y=3.14+x1+x2 که بازه هر متغیر بین -100 تا 100 است بهتر است که از نمایش اعشاری استفاده کنیم ، چونکه متغیر x1 و x2 متغیرهای حقیقی و پیوسته هستند.

نمایش جایگشتی : Permutation Representation

برخی مسائل هستند که متغیرهای آنها گسسته و عددی است اما مقدار تکرار در جواب نباید باشد . یعنی ترتیب راه حل ها مهم است ، در این حالت بازنمایی جایگشتی بهترین گزینه است.

بعنوان مثال در مسئله فروشنده دوره گرد ، هدف فروشنده این است که از هر شهر فقط یک بار عبور کند ، در این مسئله ما اگر 9 شهر داشته باشیم، راه حل باید یک ترتیب از این 9 شهر باشد. که ترتیب رفتن به شهرها را برای فروشنده دوره گرد مشخص کند. مقدار هر ژن یک عدد بین 1 تا 9 می باشد.

652974138
ترتیب پردازش کروموزوم از چپ به راست است.
  • ترتیب رفتن شهر ها مشخص شده است که از شهر 8 شروع کرده به شهر شماره 3 برود از آنجا به شهر 1 و الی آخر

دقت کنید که هیچ عدد تکراری ای در نمایش جایگشتی وجود ندارد.

جمعیت اولیه در الگوریتم ژنتیک : Initial Population In Genetic Algorithms

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

دو تا نکته در مورد این تعریف قابل توجه است

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

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

بعنوان مثال اگر بخواهیم تابع ریاضی y=3.14+x1+x2 را مینیمم کنیم و بازه مجاز هر متغیر از -100 تا 100 در نظر گرفته شود. یک راه حل یا یک کروموزوم باید بصورت یک بردار 2 تایی در نظر گرفته شود. چرا ؟ (چون که مقدار 2 تا متغیر x1 و x2 را باید پیدا کنیم.)

پس یک کروموزوم یک بردار با 2 خانه (2 ژن) می باشد که مقدار هر خانه آن میتواند عددی بین -100 تا 100 باشد.

در این مسئله نمایش راه حل بصورت اعداد حقیقی می باشد.

یک راه حل دارای 2 ژن خواهد بود .

یک کروموزوم فرضی مشابه زیر میتواند باشد:

22.6895.13
نمونه ای از یک کروموزوم فرضی

یک جمعیت با اندازه 5 میتواند بصورت زیر تولید شود:

22.6895.13
83.165.6
93.279.01
0.00121.30
34.552.999
تابع شایستگی در الگوریتم ژنتیک Fitness function

تابع شایشتگی در الگوریتم ژنتیک Fitness function (تابع فیتنش در الگوریتم ژنتیک)

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

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

یعنی هر راه حل را به تابع شایستگی میدهیم و تابع شایستگی میزان مناسب بودن آن راه حل را به ما میدهد.

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

شرایطی که تابع شایستگی باید داشته باشد:

  • عملکرد تابع برازش باید به وضوح مشخص شود. خواننده باید بتواند نحوه محاسبه امتیاز شایستگی را به روشنی درک کند.
  • تابع شایستگی باید به طور کارآمد اجرا شود. اگر تابع شایستگی کارامد نباشد، بازده کلی الگوریتم ژنتیک کاهش می یابد.
  • تابع شایستگی باید به طور کمی میزان مناسب بودن یک راه حل داده شده در حل مسئله را اندازه گیری کند.
  • تابع برازش باید برای هر ورودی داده شده ، یک عدد مثبت بزرگتر از 0 ایجاد کند.

تا اینجا جمع بندی کنیم:

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

در ابتدای کار ، باید یک جمعیت اولیه ساخته شود.

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

آموزش عملگر های الگوریتم ژنتیک : Genetic Algorithm Operators

عملگر های اصلی الگوریتم ژنتیک عبارتند از :

  • عملگر انتخاب یا Selection
  • عملگر ترکیب یا Crossover
  • عملگر جهش یا Mutation
  • انتخاب نسل بعد Survivor selection
الگوریتم ژنتیک چیست؟

عملگر انتخاب در الگوریتم ژنتیک : بررسی Selection در Genetic Algorithm

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

عملگر انتخاب ، از بین جمعیت فعلی ، افرادی را به منظور ساخت نسل بعد انتخاب میکند.

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

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

  • Random Selection یا انتخاب تصادفی : در این روش بدون توجه به شایستگی افراد ، بصورت تصادفی والدین انتخاب میشوند.
  • انتخاب تورنومنت یا Tournament selection : در این روش والدین بر اساس مسابقه انتخاب میشوند.
  • انتخاب چرخ گردان یا Roulette Wheel Selection : در این روش انتخاب والیدن بر اساس احتمال انتخاب آنها می باشد.
  • انتخاب نمونه برداری تصادفی یا Stochastic Universal Sampling یا (SUS) : همانند روش چرخ گردان است اما چند نقطه انتخاب دارد.
  • انتخاب مبتنی بر رتبه یا Rank Selection : در این روش انتخاب بر اساس میزان شایستگی صورت میگیرد.

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

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

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

Crossover فرآیندی برای تولید کروموزوم های جدید است. کراس اوور بین دو یا چند کروموزوم انجام می شود . در کراس آور ، خصوصیات ژنی به اشتراک گذاشته میشود.

در الگوریتم ژنتیک ، عملگرهای کراس اور یا ترکیب متعددی معرفی شده است که در زیر اشاره میکنیم:

  1. کراس اوور تک نقطه ای یا One Point : در این کراس اوور یک نقطه ای ، یک نقطه برش تصادفی انتخاب شده و خصوصیات دو والد از آن نقطه برش جابجا میشود.

کراس اوور یکنواخت یا Uniform Crossover : این کراس اوور براساس احتمال ، ژن ها را از یک کروموزوم به کروموزوم دیگر مبادله می کند. هر ژن مانند سکه احتمال دارد ، به عنوان مثال اگر سروی سکه ر ظاهر شود ، رد و بدل می شود و اگر زیر سکه ظاهر شود ، موقعیت ژن باقی می ماند.

2.کراس اور چند نقطه ای یا دو نقطه ای یا Multi Point Crossover : در این حالت ، دو یا چند نقطه برش در نظر گرفته میوشد.

عملگر جهش در الگوریتم ژنتیک Mutation Operation

انتخاب نسل بعد Survivor selection

0 پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *