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

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

مقالات/ هوش مصنوعی دوشنبه, 15 دی 1399 مهران زیدی

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

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

 

نسل برتر الگوریتم تکاملی

 

بطور کلی یکی از اهداف اصلی روش‌های الگوریتم‌های تکاملی، بهبود کیفیت راه‌حل‌های ضعیف تولید شده برای یک مسئله داده شده است. برای بهبود کیفیت راه‌‌حل‌های ضعیف تولید شده، الگوریتم‌های تکاملی از عملگرهای ژنتیکی مثل جهش (mutation) و کراس‌اور (crossover) استفاده می‌کنند. به عبارت دیگر، الگوریتم‌های تکاملی، در یک فرایند تکراری (iterative process)، آنقدر راه‌حل‌های ضعیف تولید شده را با استفاده از عملگر‌هایی نظیر جهش (mutation) دستکاری می‌کنند تا سیستم بتواند با دقت (accuracy) مطلوبی مسئله مورد نظر را حل کند.
لازم به ذکر است در الگوریتم‌های تکاملی، ابتدا یک مجموعه تشکیل می‌دهیم که به آن جمعیت اولیه می‌گوییم.

یادگیری تقویتی چیست؟ 

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

 

تقویت نسل‌ها در الگوریتم تکاملی

 

حال نوبت آن رسیده است که کمی دقیق‌تر بررسی کنیم: 

الگوریتم‌های تکاملی، مبتنی بر رویکردهای ابتکاری(heuristic) برای حل مسائلی است که به راحتی در پیچیدگی زمانی چند جمله‌ای حل نمی‌شوند، مثل مسائل کلاسیک NP-Hard و هر چیز دیگری که پردازش کامل آن خیلی طولانی و زمان‌بر شود. الگوریتم‌های تکاملی زمانی که به تنهایی استفاده می‌شوند ، معمولاً برای مسائل ترکیبی مورد استفاده قرار می‌گیرند. 
با این حال الگوریتم‌های ژنتیک اغلب به طور همزمان با روش‌های دیگر استفاده می‌شوند، و به عنوان یک روش سریع برای یافتن محلی مطلوب برای شروع کار الگوریتم‌های دیگر عمل می‌کنند.

فرضیه الگوریتم تکاملی (که بیشتر تحت عنوان EA شناخته می‌شود) با توجه به اینکه با روند انتخاب طبیعی آشنا هستید کاملاً ساده است. EA شامل چهار مرحله کلی است:

  1. مقداردهی اولیه
  2. انتخاب
  3. عملگرهای ژنتیکی
  4. خاتمه.

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

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

 

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

 

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

 

نگاهی به Agile و watefall

 

انتخاب


پس از ایجاد جمعیت، اکنون اعضای جمعیت باید با توجه به عملکرد تابع تناسب یا همان Fitness function ارزیابی شوند. تابع تناسب تابعی است که ورودی آن خصوصیات یک عضو است و خروجی آن نمایشی عددی از میزان سودمند بودن راه‌حل. ایجاد تابع تناسب اغلب ممکن است بسیار دشوار باشد و یافتن یک تابع خوب که متناسب با مسئله باشد بسیار مهم است. سپس، مقدار تابع تناسب همه‌ی اعضا را محاسبه کرده و بخشی از اعضایی که بالاترین امتیاز را دارند، انتخاب می‌کنیم.


توابع چند منظوره


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

 

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

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


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

نگاهی به توزیع المنتری (elementary OS)

 

خاتمه


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

مثال


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

 

نحوه‌ی عملکرد الگوریتم تکاملی

1. gif، جیف است نه گیف! حواستان به این موضوع نیز باشد.

 


ذخیره مقاله:

اشتراک گذاری:




...

مهران زیدی

هم-بنیان‌گذار و عضو ارشد CGC

Working on ML


مطالب پیشنهادی



              
                 انواع پردازنده
انواع پردازنده(CPU)

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


              
                 امنیت شبکه لایه بندی شده
امنیت شبکه لایه بندی شده (قسمت دوم)

پیش از این در مورد امنیت شبکه لایه بندی صحبت کردیم. در این مطلب موارد باقی مانده را ذکر میکنیم و با تکنولوژی‌های IDS و IPS آشنا خواهیم شد. اگر به شبکه علاقه مند هستید این مطلب را پیشنهاد می‌کنیم.


              
                 نرم افزار ادیت عکس
پنج اپلیکیشن کاربردی ادیت و طراحی عکس ساده برای کاربران آماتور

در این مطلب از جامعه گیک‌های کامپیوتر 5 مورد از بهترین اپلیکیشن‌ها و نرم افزارها که برای ادیت تصاویر استفاده می‌شوند را معرفی می‌کنیم.


نظری برای نمایش وجود ندارد. شما اولین نظر باشید.


ارسال دیدگاه

برای ثبت دیدگاه باید ابتدا وارد شوید