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

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

الگوریتم‌های ژنتیک

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

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

این الگوریتم‌ها از بخش‌های زیر تشکیل می‌شوند: تابع برازش – نمایش – انتخاب – تغییر

 

 

روش‌های نمایش

 

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

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

خاصیت هر ۳تای این روش‌ها این است که آنها تعریف سازنده‌ایی را که تغییرات تصادفی در آنها ایجاد می‌کنند را آسان می‌کنند: ۰ را به ۱ و برعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.

how-to-implement-a-genetic-algorithm

توضیحات بالا در شکل قابل مشاهده است

یک روش دیگر که توسط John Koza توسعه یافت، برنامه‌نویسی ژنتیک (genetic programming)است؛ که برنامه‌ها را به عنوان شاخه‌های داده در ساختار درخت نشان می‌دهد. در این روش تغییرات تصادفی می‌توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

 

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

 

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است:در ابتدا روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. در روش سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسه‌ها نمایش داده می‌شود. دومین جزء اساسی الگوریتم ژنتیک روشی است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می‌تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود، که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است. تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه‌گیری می‌شود.

 

شبه کد

 ۱ Genetic Algorithm
 ۲ begin
 ۳ Choose initial population
 ۴ repeat
 ۵ Evaluate the individual fitness of a certain proportion of the population
 ۶ Select pairs of best-ranking individuals to reproduce
 ۷ Apply crossover operator
 ۸ Apply mutation operator
 ۹ until terminating condition
۱۰ end

شمای کلی شبه کد how-to-implement-a-genetic-algorithm[ویرایش]

ایده اصلی

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن ۱ می‌تواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتفاق اول جهش (Mutation) است. «جهش» به این صورت است که بعضی ژن‌ها بصورت کاملاً تصادفی تغییر می‌کنند. البته تعداد این گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر «جهش» اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به «جهش» رخ می‌دهد چسبیدن دو کروموزوم از طول به یکدیگر و تبادل برخی قطعات بین دو کروموزوم است. این مسئله با نام Crossover شناخته می‌شود. این همان چیزیست که باعث می‌شود تا فرزندان ترکیب ژنهای متفاوتی را (نسبت به والدین خود) به فرزندان خود انتقال دهند.

 

روش‌های انتخاب

 

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

انتخاب Elitist

مناسب‌ترین عضو هر اجتماع انتخاب می‌شود. Elitist Selection

انتخاب Roulette

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

Roulette Selection

انتخاب Scaling

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

انتخاب Tournament

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

بعضی از روش‌های دیگر عبارتند از:Hierarchical Selection, Steady-State Selection, Rank Selection, Tournament Selection

مثال عملی

در این مثال می‌خواهیم مسئلهٔ ۸ وزیر را بوسیلهٔ این الگوریتم حل کنیم. هدف مشخص کردن چیدمانی از ۸ وزیر در صفحهٔ شطرنج است به نحوی که هیچ‌یک همدیگر را تهدید نکند. ابتدا باید نسل اولیه را تولید کنیم. صفحه شطرنج ۸ در ۸ را در نظر بگیرید. ستونها را با اعداد ۰ تا ۷ و سطرها را هم از ۰ تا ۷ مشخص می‌کنیم. برای تولید حالات (کروموزومها) اولیه بصورت تصادفی وزیرها را در ستونهای مختلف قرار می‌دهیم. باید در نظر داشت که وجود نسل اولیه با شرایط بهتر سرعت رسیدن به جواب را افزایش می‌دهد (اصالت نژاد) به همین خاطر وزیر i ام را در خانهٔ تصادفی در ستون i ام قرار می‌دهیم (به جای اینکه هر مهره‌ای بتواند در هر خانه خالی قرار بگیرد). با اینکار حداقل از برخورد ستونی وزیرها جلوگیری می‌شود. توضیح بیشتر اینکه مثلاً وزیر اول را بطور تصادفی در خانه‌های ستون اول که با ۰ مشخص شده قرار می‌دهیم تا به آخر. i=۰٬۱، … ۷ حال باید این حالت را به نحوی کمی مدل کرد. چون در هر ستون یک وزیر قرار دادیم هر حالت را بوسیلهٔ رشته اعدادی که عدد k ام در این رشته شمارهٔ سطر وزیر موجود در ستون i ام را نشان می‌دهد. یعنی یک حالت که انتخاب کردیم می‌تواند بصورت زیر باشد: ۶۷۲۰۳۴۲۲ که ۶ شمارهٔ سطر ۶ است که وزیر اول که شمارهٔ ستونش ۰ است می‌باشد تا آخر. فرض کنید ۴ حالت زیر به تصادف تولید شده‌اند. این چهار حالت را بعنوان کروموزومهای اولیه بکار می‌گیریم.

  1. ) ۶۷۲۰۳۴۲۰
  2. ) ۷۰۰۶۳۳۵۴
  3. ) ۱۷۵۲۲۰۶۳
  4. )۴۳۶۰۲۴۷۱

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

  1. )۶۷۲۰۳۴۲۰ ← ۶
  2. )۷۰۰۶۳۳۵۴ ← ۸
  3. )۱۷۵۲۲۰۶۳ ← ۲
  4. )۴۳۶۰۲۴۷۱ ← ۴

پس احتمالها بصورت زیر است:

p(۳)>p(۴)>p(۱)>p(۲

در اینجا کروموزومهایی را انتخاب می‌کنیم که برازندگی کمتری دارند. پس کروموزوم ۳ برای crossover با کروموزومهای ۴ و ۱ انتخاب می‌شود. نقطهٔ ترکیب را بین ارقام ۶ و ۷ در نظر می‌گیریم.

۴ و ۳:

  1. )۱۷۵۲۲۰۷۱
  2. )۴۳۶۰۲۴۶۳

۱ و ۳:

  1. )۱۷۵۲۲۰۲۰
  2. )۶۷۲۰۳۴۶۳

حال نوبت به جهش می‌رسد. در جهش باید یکی از ژنها تغییر کند

. فرض کنید از بین کروموزومهای ۵ تا ۸ کروموزوم شمارهٔ ۷ و از بین ژن چهارم از ۲ به ۳ جهش یابد. پس نسل ما شامل کروموزومهای زیر با امتیازات نشان داده شده می‌باشد: (امتیازات تعداد برخوردها می‌باشد)

  1. )۶۷۲۰۳۴۲۰ ← ۶
  2. )۷۰۰۶۳۳۵۴ ← ۸
  3. )۱۷۵۲۲۰۶۳ ← ۲
  4. )۴۳۶۰۲۴۷۱ ← ۴
  5. )۱۷۵۲۲۰۷۱ ← ۶
  6. )۴۳۶۰۲۴۶۳ ← ۴
  7. )۱۷۵۳۲۰۲۰ ← ۴
  8. )۶۷۲۰۳۴۶۳ ← ۵

کروموزوم ۳ کاندیدای خوبی برای ترکیب با ۶ و ۷ می‌باشد. (فرض در این مرحله جهشی صورت نگیرد و نقطهٔ اتصال بین ژنهای ۱ و ۲ باشد)

  1. )۶۷۲۰۳۴۲۰ ← ۶
  2. )۷۰۰۶۳۳۵۴ ← ۸
  3. )۱۷۵۲۲۰۶۳ ← ۲
  4. )۴۳۶۰۲۴۷۱ ← ۴
  5. )۱۷۵۲۲۰۷۱ ← ۶
  6. )۴۳۶۰۲۴۶۳ ← ۴
  7. )۱۷۵۳۲۰۳۰ ← ۴
  8. )۶۷۲۰۳۴۶۳ ← ۵
  9. )۱۳۶۰۲۴۶۳ ← ۲
  10. )۴۷۵۲۲۰۶۳ ← ۲
  11. )۱۷۵۲۲۰۲۰ ← ۴
  12. )۱۷۵۲۲۰۶۳ ← ۲

کروموزومهای از ۹ تا ۱۲ را نسل جدید می‌گوییم. بطور مشخص کروموزوم‌های تولید شده در نسل جدید به جواب مسئله نزدیکتر شده‌اند. با ادامهٔ همین روند پس از چند مرحله به جواب مورد نظر خواهیم رسید. پایان

how-to-implement-a-genetic-algorithm

همان‌طور که در شکل بالا مشاهده می‌کنید شمای کلی از نحوهٔ عملکرد این الگوریتم را به شما نشان می‌دهد در ادامه به تعریف و انواع و کابرد این الگوریتم در مسائل می‌پردازیم.

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

روش جستجوی تکاملی

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

نظریه داروین

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

انواع مختلف الگوریتم‌های تکاملی

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

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

الگوریتم تکاملی

Evolutionary Strategies

Evolutionary Programming

Differential Evolution

Cultural Evolution

هم‌فرگشتی

در ادامه قصد داریم بحث خود را بر روی الگوریتم‌های ژنتیکی سوق دهیم.

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

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

how-to-implement-a-genetic-algorithm

شکل انواع کرموزوم‌های بدن انسان که در نحوهٔ نمایش گذاری نیز مؤثر می‌باشد

کدگذاری و نحوه نمایش

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

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

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

فلو چارت این الگوریتم

 
how-to-implement-a-genetic-algorithm

















منبع: http://mehrmihan.ir/how-to-implement-a-genetic-algorithm/
این مطلب را به اشتراک بگذارید :
a b