محاسبات تکاملی چیست؟ – به زبان ساده

در این مطلب، با مبحث «محاسبات تکاملی» (Evolutionary Computation)، مفاهیم این حوزه و مهم‌ترین الگوریتم‌های تکاملی آشنا خواهید شد. روش‌های محاسبات تکاملی، محققان و فعالان حوزه هوش مصنوعی و «بهینه‌سازی عددی» (Numerical Optimization) را قادر می‌سازند تا از ایده فرایندهای تکاملی (Evolutionary Process) و شبیه‌سازی (Simulation) آن‌ها برای حل مسائل جهان واقعی استفاده کنند؛ مسائلی که شاید پیش از این برای حل آن‌ها، راهکار امکان‌پذیر (Feasible) و معقولی وجود نداشت.

اولین مفهومی که برنامه‌نویسان و یا توسعه‌دهندگان برنامه‌های کاربردی با آن دست و پنجه نرم می‌کنند، مفهوم «الگوریتم» (Algorithm) است. وقتی که کاربر یا یک برنامه‌نویس به دنبال راه حل برای یک مسأله (به عنوان نمونه، یک مسأله بهینه‌سازی (Optimization)) است، یک استراتژی یا مجموعه دقیقی از دستورالعمل‌های لازم برای حل مسأله مورد نظر را مشخص می‌کند که به آن الگوریتم گفته می‌شود. حال سناریویی را فرض کنید که در آن مسأله داده شده به قدری پیچیده باشد که حل آن توسط الگوریتم‌های مرسوم امکان‌پذیر نباشد. در چنین حالتی، چگونه می‌توان استراتژی لازم برای حل این مسأله (الگوریتم حل مسأله) را کد نویسی کرد؟

این سناریو، یکی از حوزه‌های اصلی کاربرد «هوش مصنوعی» (Artificial Intelligence) در حل مسائل جهان واقعی محسوب می‌شود. به عبارت دیگر، زمانی می‌توان از پتانسیل کامل الگوریتم‌های هوش مصنوعی بهره‌برداری کرد که الگوریتم‌های مرسوم حل مسأله پاسخگوی نیازهای مسأله مورد نظر نباشند و برای حل کردن این دسته از مسائل، روش‌های بدیع حل مسأله با استفاده از تکنیک‌های هوش مصنوعی نیاز باشد.

یکی از مقرون به صرفه‌ترین و ساده‌ترین تکنیک‌های حل مسأله (از لحاظ بار محاسباتی و زمان لازم برای اجرای الگوریتم) در حوزه هوش مصنوعی، روش‌های محاسبات تکاملی هستند. به طور کلی، الگوریتم‌های محاسبات تکاملی بر پایه به‌کارگیری «نظریه تکامل داروین» (Darwin's Theory of Evolution) جهت پیاده‌‌سازی برنامه‌های کامپیوتری شکل گرفته‌اند.

یکی از اهداف مهم روش‌های محاسبات تکاملی و الگوریتم‌های تکاملی به طور خاص، بهبود کیفیت راه حل‌های ضعیف تولید شده برای یک مسأله داده شده است. جهت بهبود کیفیت راه حل‌های ضعیف تولید شده، الگوریتم‌های محاسبات تکاملی از فرایندهای تکاملی نظیر «جهش» (Mutation) و سایر موارد استفاده می‌کنند؛ به عبارت دیگر، الگوریتم‌های محاسبات تکاملی، در یک فرایند تکراری (Iterative Process)، آنقدر راه حل‌های ضعیف تولید شده را با استفاده از عملگر‌هایی نظیر جهش (Mutation) دستکاری می‌کنند تا سیستم بتواند با دقت (Accuracy) مطلوبی مسأله مورد نظر را حل کند.

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

محاسبات تکاملی

در حوزه «علوم کامپیوتر» (Computer Science) و هوش مصنوعی، محاسبات تکاملی خانواده‌ای از الگوریتم‌ها جهت «بهینه‌سازی سراسری» (General Optimization) هستند که از فرایندهای «تکامل زیستی» (Biological Evolution) الهام گرفته شده‌اند. به عبارت دیگر، به زیر شاخه‌ای از هوش مصنوعی و «محاسبات نرم» (Soft computing) که به مطالعه و پیاده‌سازی الگوریتم‌های الهام گرفته شده از فرایندهای تکامل زیستی می‌پردازد، الگوریتم‌های محاسبات تکاملی گفته می‌شود.

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

کلیک کنید

از دیدگاه فنی، الگوریتم‌های محاسبات تکاملی خانواده‌ای از روش‌های حل مسأله محسوب می‌شوند که مبتنی بر جمعیت (Population-based) و آزمون و خطا (Trial and Error) هستند و از مکانیزم‌های بهینه‌سازی تصادفی (Stochastic Optimization) یا بهینه‌سازی فرا اکتشافی (Meta-Heuristic) جهت همگرایی به جواب بهینه سراسری یا تقریبی (Approximation) از جواب بهینه استفاده می‌کنند.

در محاسبات تکاملی، ابتدا یک مجموعه ابتدایی متشکل از «جواب‌های کاندید» (Candidate Solutions) تشکیل می‌شود. در طول فرایند تکاملی، الگوریتم‌های محاسبات تکاملی با دستکاری و به‌روزرسانی جمعیت متشکل از جواب‌های کاندید، جمعیت را به سمت ناحیه حاوی جواب «بهینه سراسری» (Global Optimum) حرکت می‌دهند. در هر تکرار از الگوریتم‌های محاسبات تکاملی (که به آن «نسل» (Generation) نیز گفته می‌شود)، از طریق حذف کردن جواب‌های نامطلوب در جمعیت و ایجاد تغییرات بسیار کوچک و البته تصادفی در جواب‌های کاندید، فرایند تکاملی شکل خواهد گرفت.

با الگو گرفتن از فرایند‌های تکامل طبیعی در زیست‌شناسی، جمعیت متشکل از جواب‌های کاندید (در الگوریتم‌های محاسبات تکاملی)، تحت تاثیر فرایندهای تکاملی نظیر «انتخاب طبیعی» (Natural Selection) و جهش قرار می‌گیرد؛ در واژه‌شناسی الگوریتم‌های محاسبات تکاملی، به فرایند انتخاب طبیعی، فرایند انتخاب مصنوعی (Artificial Selection) نیز گفته می‌شود. در نتیجه، بر اساس مکانیزم‌های تعریف شده در فرایند تکامل، جمعیت متشکل از جواب‌های کاندید (در الگوریتم‌های محاسبات تکاملی) به نحوی تکامل پیدا می‌کنند که با مرور زمان و گذر نسل‌های متوالی، «برازندگی» (Fitness) آن‌ها افزایش پیدا کند؛ از «تابع برازندگی» (Fitness Function) برای محاسبه برازندگی جواب‌های کاندید در الگوریتم‌های محاسبات تکاملی استفاده می‌شود.

روش‌های محاسبات تکاملی قادر هستند تا مجموعه‌ای از جواب‌های بهینه (Optimized Solutions) را برای یک مسأله خاص و در شرایط مختلف آن تولید نمایند؛ چنین ویژگی مهمی در سیستم‌های محاسبات تکاملی و الگوریتم‌های تکاملی، آن‌ها را در نقطه مقابل روش‌های بهینه‌سازی مرسومی قرار می‌دهد که قادر هستند تنها یک جواب قطعی (Deterministic Solutions) و یا تعداد محدودی جواب تقریبی (Approximated Solutions) برای مسأله مورد نظر تولید نمایند. علاوه بر این، قابلیت تولید مجموعه‌ای از جواب‌های کاندید برای یک مسأله مورد نظر، الگوریتم‌های محاسبات تکاملی را به یکی از محبوب‌ترین روش‌های حل مسأله در حوزه علوم کامپیوتر تبدیل کرده است.

تاکنون نسخه‌های مختلفی از الگوریتم‌های محاسبات تکاملی ارائه شده است. بسیاری از الگوریتم‌های محاسبات تکاملی که در سال‌های اخیر ارائه شده‌اند، «مستقل از دامنه» (Domain-independent) و «مستقل از مسأله» (Problem-independent) هستند که آن‌ها را به گزینه بسیار مناسبی برای حل دامنه وسیعی از مسائل، به ویژه مسائل و ساختارهای داده‌ای (Data Structures) خاص، تبدیل می‌کند. بعضا از الگوریتم‌های محاسبات تکاملی، به عنوان یک روش آزمایش کامپیوتری (In Silico Experimental Procedure)، جهت مطالعه جنبه‌های مشترک فرایندهای تکاملی عمومی استفاده می‌شود.

تکامل، محاسبات تکاملی و مفاهیم مهم

هدف از پیاده‌سازی الگوریتم‌های محاسبات تکاملی (Evolutionary Computation)، شبیه‌سازی فرایند تکامل در یک سیستم کامپیوتری است. نتیجه شبیه‌سازی فرایند تکامل، تولید مجموعه‌ای از الگوریتم‌های بهینه‌سازی (Optimization Algorithm) است که معمولا مبتنی بر یک مجموعه ساده از ویژگی‌های مشخصه (ژن‌ها) و دستکاری آن‌ها در یک فرایند تکراری و تکاملی هستند. ویژگی مهم الگوریتم‌های محاسبات تکاملی این است که در هر تکرار از فرایند تکامل، به صورت تدریجی، کیفیت جواب‌های تولید شده برای یک مسأله بهینه‌سازی بهبود بخشیده می‌شود و در نهایت، یک جواب بهینه (یا حداقل یک تقریب مناسب از جواب بهینه) حاصل می‌شود.

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

کلیک کنید

همانطور که پیش از این نیز اشاره شد، ایده اصلی محاسبات تکاملی بر پایه نظریه تکامل داروین (Darwin's Theory of Evolution) بنا نهاده شده است. اصول مهم در نظریه تکامل داروین عبارتند از:

• «بقای برازنده‌ترین‌ها» (Survival of the Fittest). بر مبنای نظریه تکامل داروین، نمونه‌های موجود در یک محیط (طبیعت برای موجودات زنده نقش محیط را ایفا می‌کند) با گذشت زمان خود را با شرایط محیط وفق نمی‌دهند. بلکه، در هر نسل تنها آن دسته از نمونه‌هایی که برازندگی بیشتری نسبت به دیگر نمونه‌ها دارند باقی می‌مانند و به بقای خود ادامه می‌دهند.
• انتخاب بر مبنای فنوتایپ (Phenotype).
• به ارث بردن ژنوتایپ (Genotype) نمونه‌های والد توسط نمونه‌های فرزند.
• تولید مثل (Reproduction).
• تغییرات تصادفی در ژن‌های نمونه‌های موجود در محیط.

نظریه تکامل داروین از چهار فرضیه اصلی تشکیل شده است:

1. نمونه‌های موجود در یک جمعیت یا گونه‌های جاندار، تفاوت‌های معناداری با یکدیگر دارند. اگر بخواهیم این فرضیه را در قالب الگوریتم‌های محاسبات تکاملی تصویر کنیم، به این نتیجه خواهیم رسید که نمونه‌های موجود در جمعیت اولیه تولید شده در یک الگوریتم تکاملی باید ویژگی‌ها یا مقادیر متغیری متفاوت از یکدیگر داشته باشند. چنین فرضی به جمعیت اولیه تولید شده کمک می‌کند تا بتوانند در فضای جستجوی مسأله پراکنده شود و بیشتر مناطق موجود در این فضا را پوشش دهد. از آنجایی که مکان جواب بهینه سراسری در فضای جستجوی مسأله مشخص نیست، پراکنده شدن نمونه‌ها در مناطق موجود در جمعیت، احتمال رسیدن به جواب بهینه سراسری (یا تقریبی از آن) را افزایش می‌دهد.
2. در طول فرایند تکامل و در گذار (Transition) از هر نسل به نسل بعدی، برخی از ویژگی‌های موجودات زنده به فرزندان (Offspring | Child) منتقل می‌شوند. برای شبیه‌سازی چنین فرایندی در تکامل طبیعی از عملگرهایی نظیر تولید مثل (Reproduction)، جهش و ترکیب یا آمیزش (Recombination | Crossover) استفاده می‌شود. با استفاده از عملگر تولید مثل، یک نمونه کپی برابر با اصل از نمونه والد ایجاد می‌شود. عملگر جهش نیز از طریق اعمال تغییرات جزئی و تصادفی در ژن‌های نمونه‌های والد، سبب تولید نمونه‌های فرزند جدید در جمعیت می‌شود. علاوه بر این، از طریق عملگر ترکیب یا آمیزش، دو نمونه والد با یکدیگر ترکیب می‌شوند و هر یک از فرزندان ایجاد شده، ژن‌های والدین را به طور تصادفی به ارث می‌برند.
3. در هر نسل (تکرار) از فرایند تکامل، تعداد نمونه‌های فرزند ایجاد شده از تعداد نمونه‌هایی که زنده خواهند ماند، بیشتر خواهد بود. در الگوریتم‌های محاسبات تکاملی، از فرایندی به نام «انتخاب» (Selection) برای مشخص کردن نمونه‌هایی که باید از نسل فعلی به نسل بعدی منتقل شوند استفاده می‌شود. در الگوریتم‌های محاسبات تکاملی روش کار بدین صورت که نمونه‌های برازنده‌تر شانس (یا احتمال) بیشتری برای انتخاب شدن و قرار گرفتن در جمعیت نسل بعد خواهند داشت.
4. «بقاء» (Survival) و تولید مثل نمونه‌ها به صورت تصادفی انجام نمی‌شود. نمونه‌هایی که باقی می‌مانند و شروع به تولید مثل می‌کنند (و یا نمونه‌هایی که نرخ تولید مثل بالاتری نسبت به دیگر نمونه‌ها دارند)، نمونه‌هایی هستند که ویژگی‌ها یا مقادیر متغیر مطلوب‌تری نسبت به دیگر نمونه‌ها دارند؛ به عبارت دیگر، در ناحیه‌ای از فضای جستجو قرار دارند که به احتمال زیاد به جواب بهینه سراسری نزدیک‌تر هستند. به چنین فرایند، انتخاب طبیعی (Natural Selection) گفته می‌شود.

فیلم آموزش خوشه بندی با الگوریتم های تکاملی و فراابتکاری در فرادرس

کلیک کنید

با توجه به اصول و فرضیه‌های مطرح شده در محاسبات تکاملی، یک الگوریتم تکاملی از چهار مؤلفه اصلی تشکیل خواهد شد:

• مؤلفه «جمعیت» (Population) که مجموعه نمونه‌های موجود در جمعیت را مدل‌سازی می‌کند.
• مؤلفه «عملگرهای تکاملی» (Evolutionary Operators) که سبب تغییر کدهای ژنتیکی نمونه‌های موجود در جمعیت می‌شود. همچنین این مؤلفه سبب افزایش «تنوع» (Diversity) در جواب‌های کاندید تولید شده می‌شود.
• مؤلفه برازندگی که کیفیت جواب‌های کاندید تولید شده (نزدیکی یا همگرایی آن‌ها به جواب بهینه سراسری) را می‌سنجد.
• مؤلفه انتخاب (Selection) که اصل بقای برازنده‌ترین‌ها (Survival of the Fittest) را در الگوریتم‌های محاسبات تکاملی شبیه‌سازی می‌کند.

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

انتخاب طبیعی (Natural Selection)

همانطور که پیش از این نیز اشاره شد، یکی از اصول اساسی الگوریتم‌های محاسبات تکاملی (الگوریتم‌های تکاملی) بقای برازنده‌ترین‌ها (Survival of the Fittest) است. به عبارت دیگر، بقاء در طبیعت بسیار سخت است و موجوداتی که می‌تواند به بقای خود در طبیعت ادامه دهند، شانس بیشتری برای تولید مثل خواهند داشت. محیط زندگی موجودات زنده (طبیعت)، به طور طبیعی موجوداتی را که از بیشترین برازندگی برخوردار هستند، برای تولید مثل انتخاب می‌کند و باقی موجوداتی را که قادر به بقا نیستند از بین می‌برد.

فیلم آموزش انتخاب طبیعی در تکامل موجودات زنده (رایگان) در فرادرس

کلیک کنید

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

مکانیزم مشابه با انتخاب طبیعی را می‌توان در برنامه‌های کامپیوتری و جهت پیاده‌سازی الگوریتم‌های محاسبات تکاملی مورد استفاده قرار داد. اگر سیستم محاسبات تکاملی یک جواب تقریبی (Approximate Solution) برای یک مسأله بهینه‌سازی در اختیار داشته باشد، با ایجاد تغییرات تصادفی در جواب و محاسبه برازندگی جواب‌های جدید می‌توان مشخص کرد که آیا تغییرات ایجاد شده، سبب بهبود کیفیت جواب‌ها شده است یا نه. در صورتی که چنین فرایندی به صورت متوالی و تکراری انجام شود، به احتمال زیاد در هر مرحله، به حداقل یک جواب بهتر (با برازندگی بیشتر) یا برابر دست پیدا خواهد شد. انتخاب طبیعی یکی از حیاتی‌ترین مؤلفه‌های محاسبات تکاملی محسوب می‌شود که قوه محرکه آن عملگرهای تکاملی نظیر جهش تصادفی در ژن‌ها (متغیرها) است.

فنوتایپ (Phenotype) و ژنوتایپ (Genotype)

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

شکل ظاهری موجودات زنده توسط مجموعه‌ای از دستورالعمل‌های کدبندی شده (Encoded) در سلول‌های آن‌ها مشخص می‌شود. به این مجموعه دستورالعمل‌های کدبندی شده، ژنوتایپ (Genotype) گفته می‌شود. به عبارت دیگر، ژنوتایپ به اطلاعاتی اطلاق می‌شود که در DNA موجودات زنده کدبندی شده است.با اینکه فنوتایپ شکل ظاهری موجودات زنده پس از پدید آمدن را مشخص می‌کند، ژنوتایپ موجودات زنده همان طرح (Blueprint) ابتدایی است که شکل نهایی طاهر موجودات زنده از آن مشتق شده است.

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

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

در این میان و در حین انجام فرایند کپی شدن DNA والدین و انتقال به فرزندان ممکن است جهش‌های تصادفی در DNA رخ بدهد که سبب ایجاد تغییراتی در DNA فرزندان شود. چنین تغییراتی پتانسیل ایجاد تغییر در فنوتایپ موجودات زنده را دارند.

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

ساختارهای الگوریتم‌های محاسبات تکاملی

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

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

بهینه محلی (Local Optimum | Local Maximum | Local Minimum)

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

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

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

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

در حوزه «هوش مصنوعی» (Artificial Intelligence)، یک الگوریتم تکاملی (Evolutionary Algorithm) زیر مجموعه‌ای از خانواده روش‌های هوش محاسباتی است. بنابراین، الگوریتم تکاملی را می‌توان یک الگوریتم فرا اکتشافی و مبتنی بر جمعیت برای حل مسائل بهینه‌سازی به شمار آورد. یک الگوریتم تکاملی از مکانیزم‌هایی استفاده می‌کند که از فرایندهای تکامل زیستی  نظیر «تولید مثل» (Reproduction)، جهش، ترکیب یا آمیزش و انتخاب الهام گرفته شده‌اند. به فرایندهای تکامل زیستی در محاسبات تکاملی، «عملگرهای تکاملی» (Evolational Operators) گفته می‌شود.

فیلم آموزش هوش مصنوعی – مقدماتی + گواهینامه در فرادرس

کلیک کنید

در الگوریتم‌های مبتنی بر محاسبات تکاملی (الگوریتم‌های تکاملی)، جواب‌های کاندید برای یک مسأله بهینه‌سازی نقش «نمونه‌ها» (Individuals) در یک جمعیت (Population) را ایفا خواهند کرد. تابع برازندگی نیز کیفیت جواب‌های کاندید تولید شده را مشخص می‌کند. «تکامل جمعیت» (Evolution of Population) زمانی حاصل می‌شود که در یک فرایند تکراری و در نسل‌های متوالی از الگوریتم تکاملی، عملگرهای تکاملی روی نمونه‌های موجود در جمعیت اعمال و جمعیت به سمت ناحیه حاوی جواب بهینه سراسری مسأله بهینه‌سازی همگرا شود.

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

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

یکی از ویژگی‌های مهم الگوریتم‌های محاسبات تکاملی این است که در یافتن جواب‌های بهینه (یا تقریب مناسبی از جواب‌های بهینه) مسائل بهینه‌سازی، عملکرد بسیار خوبی از خود نشان می‌دهند. دسته‌ای از مسائل که جهت بهینه‌سازی آن‌ها از الگوریتم‌های محاسبات تکاملی استفاده می‌شود، «مسائل بهینه‌سازی ترکیبیاتی» (Combinatorial Optimization Problems) نام دارند که از لحاظ محاسباتی بسیار سخت و پیچیده هستند؛ انتظار می‌رود که زمان محاسباتی لازم برای بهینه‌سازی چنین مسائلی، با زیاد شدن ابعاد (اندازه) مسأله، به طور نمایی افزایش پیدا کند.

به عنوان نمونه، «مسأله فروشنده دوره‌گرد» (Travelling Salesman Problem) یکی از مسائل بهینه‌سازی ترکیبیاتی محسوب می‌شود. در الگوریتم‌های مرسوم ارائه شده برای حل مسأله فروشنده دوره‌گرد، پیش از این که بتوان یکی از مسیر‌های موجود در فضای جستجوی مسأله را به عنوان مسیر بهینه انتخاب کرد، باید تعداد قابل توجهی از مسیرهای ممکن میان شهر پیمایش و ارزیابی شوند. حالا فرض کنید که تعداد شهرهای موجود در مسأله یک عدد بسیار بزرگ باشد.

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

مسأله فروشنده دوره‌گرد را به راحتی می‌توان با استفاده از الگوریتم‌‌های محاسبات تکاملی (به عنوان نمونه، الگوریتم ژنتیک (Genetic Algorithm)) و به شکل به مراتب بهینه‌تری نسبت به روش‌های مرسوم حل مسأله، بهینه‌سازی کرد. برای چنین کاری، از ساختاری که در ادامه نمایش داده شده است استفاده می‌شود:

• در ابتدا، جمعیتی متشکل از جواب‌های کاندید (تعدادی شهر که بر اساس یک ترتیب تصادفی (یا شبه تصادفی) در فضای جستجوی مسأله تولید شده‌‌اند)، به عنوان جمعیت اولین نسل در فرایند تکاملی الگوریتم ژنتیک، تولید می‌شود.
• برازندگی هر یک از نمونه‌های موجود در جمعیت (که نقش یک جواب کاندید برای مسأله مورد نظر را ایفا می‌کنند) محاسبه می‌شود.
• زمانی که قرار است جمعیت نسل بعد مشخص شود، بهترین نمونه‌های موجود در جمعیت (یا نمونه‌هایی که کمترین مسافت لازم را برای پیمایش می‌طلبند) نگه‌داری و نمونه‌هایی که برازندگی کمتری دارند، نادیده گرفته می‌شوند.
• علاوه بر نمونه‌هایی که بیشترین برازندگی را دارند (نمونه‌هایی که در هر نسل نگه‌داری می‌شوند)، از نمونه‌های جدیدی که به آن‌ها نمونه‌های فرزند (Offspring | Child) نیز گفته می‌شود جهت تشکیل جمعیت نسل بعد استفاده می‌شود.
  • نمونه‌های فرزند، معمولا از طریق اعمال عملگر جهش روی نمونه‌های والد (Parents) ایجاد می‌شوند. همچنین، از عملگرهای تکاملی نظیر ترکیب یا آمیزش جهت تولید نمونه‌های فرزند استفاده می‌شود؛ در این عملگر، ژن‎‌های تشکیل دهنده دو نمونه والد با یکدیگر ترکیب می‌شوند و فرزندان حاصل، ویژگی‌های ژنی نمونه‌های والد را به ارث می‌برند.

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

کدهای لازم برای حل مسأله فروشنده دوره‌گرد با استفاده از زبان برنامه‌نویسی متلب:

خروجی حاصل از بهینه‌سازی مسأله فروشنده دوره‌گرد:

کدهای لازم برای حل مسأله فروشنده دوره‌گرد با استفاده از زبان برنامه‌نویسی پایتون:

خروجی حاصل از بهینه‌سازی مسأله فروشنده دوره‌گرد:

از یک دیدگاه انتزاعی‌تر به الگوریتم‌های محاسبات تکاملی، چنین رویکردهایی در دسته «الگوریتم‌های احتمالی» (Probabilistic Algorithms) طبقه‌بندی می‌شوند. الگوریتم‌هایی نظیر «شبیه‌سازی تبرید» (Simulated Annealing)، الگوریتم بهینه‌سازی فاخته (Cuckoo Optimization Algorithm)، الگوریتم کلونی مورچگان (Ant Colony Optimization) و الگوریتم کرم شب تاب (Firefly Algorithm)، از جمله الگوریتم‌های تکاملی محسوب می‌شوند. الگوریتم شبیه‌سازی تبرید که مدل یک فرایند طبیعی و فیزیکی را شبیه‌سازی می‌کند، ویژگی‌های مشترک زیادی با الگوریتم ژنتیک دارد:

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

به چنین فرایندی «تپه‌ نوردی» (Hill Climbing) در فضای جستجوی مسأله نیز گفته می‌شود. با این حال، از آنجایی که معمولا معیار دقیقی برای مشخص کردن میزان نزدیکی یا همگرایی یک جواب کاندید به جواب بهینه وجود ندارد و فرایند تکامل در الگوریتم‌های محاسبات تکاملی یک فرایند تصادفی است، یک جواب کاندید با برازندگی کمتر (جواب کاندیدی که همگرایی کمی با جواب بهینه دارد) نیز می‌تواند در فرایند تکامل شرکت کند و مقادیر متغیرهای آن دستخوش تغییر شود؛ البته، جواب‌های کاندیدی که برازندگی کمتری نسبت به دیگر جواب‌ها دارند، با احتمال کمتری نسبت به جواب‌های کاندید برازنده‌تر، می‌توانند در فرایند تکامل شرکت کنند.

اگر چه در تئوری نشان داده شده است که «استراتژی‌های تکاملی» (Evolutionary Strategies) را می‌توان در دامنه وسیعی از مسائل بهینه‌سازی مورد استفاده قرار داد، ولی به‌کارگیری آن‌ها به صورت عملی و در مسائل جهان واقعی نشان داد که استفاده از الگوریتم‌های محاسبات تکاملی در مسائل خاص، نیازمند ایجاد تغییرات در فرایند تکاملی تعبیه شده است تا جواب‌های حاصل از کیفیت مناسبی برخوردار باشند.

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

در یک دسته‌بندی جامع و کلی‌تر، الگوریتم‌های محاسبات تکاملی در روش‌های «هوش محاسباتی» (Computational Intelligence) یا «محاسبات نرم» (Soft Computing) طبقه‌بندی می‌شوند.

فیلم آموزش هوش مصنوعی – مقدماتی + گواهینامه در فرادرس

کلیک کنید

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

• روش‌های «هوش محاسباتی» (Computational Intelligence) یا «محاسبات نرم» (Soft Computing)
  • «شبکه‌های عصبی مصنوعی» (Artificial Neural Network)
  • «سیستم‌های فازی» (Fuzzy Systems)
  • محاسبات تکاملی (Evolutionary Computation) یا الگوریتم‌‌های تکاملی (Evolutionary Algorithms)
    • روش «برنامه‌نویسی تکاملی» (Evolutionary programming)
    • روش «استراتژی‌های تکاملی» (Evolutionary Strategies)
    • روش «الگوریتم ژنتیک» (Genetic Algorithm)
    • روش «برنامه‌نویسی ژنتیک» (Genetic Programming)
    • و دیگر الگوریتم‌های محاسبات تکاملی

انواع تکنیک‌های محاسبات تکاملی

تفاوت میان تکنیک‌های مختلفی محاسبات تکاملی، در نحوه «نمایش کدبندی جواب‌های کاندید» (Representation of Candidate Solutions Representation)، جزئیات مرتبط با پیاده‌سازی این دسته از الگوریتم‌ها و ذات مسأله بهینه‌سازی مورد نظر است.

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

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

پیاده‎‌سازی الگوریتم ژنتیک در زبان متلب: در ادامه، کدهای پیاده‌سازی الگوریتم ژنتیک برای مدل‌سازی و حل «الگوریتم راسو» (Weasel algorithm) [+] نمایش داده شده است. هدف این الگوریتم این است که نشان دهد تغییرات تصادفی در ژ‌ن‌ها و ترکیب آن‌ها با یک مکانیزم انتخاب غیر تصادفی، منجر به تولید نتایجی متفاوت و بهتر از شانس خالص در فرایندهای تکاملی خواهد شد. مشخصات این مسأله به شکل زیر است:

1. جمعیت اولیه: یک آرایه 28 عنصری متشکل از الفبای ABCDEFGHIJKLMNOPQRSTUVWXYZ.
2. هدف نهایی: تبدیل رشته ورودی یا جمعیت اولیه به رشته METHINKS IT IS LIKE A WEASEL.
3. تابع برازندگی: تابعی که شباهت آرگومان ورودی را به رشته نهایی یا هدف نهایی مشخص می‌کند.
4. عملگرهای تکاملی (پیاده‌سازی عملگر انتخاب و جهش ضروری است، ولی پیاده‌سازی عملگر ترکیب اختیاری است)

اجرا:

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

• «برنامه‌نویسی ژنتیک» (Genetic Programming): در این روش محاسبات تکاملی، جواب‌ها به فرم برنامه‌های کامپیوتری و معمولا در قالب درخت LISP نمایش داده می‌شوند. همچنین، برازندگی جواب‌های کاندید به وسیله قابلیت آن‌ها در حل یک مسأله محاسباتی سنجیده می‌شود.

پیاده‎‌سازی برنامه‌نویسی ژنتیک در زبان پایتون:

• برنامه‌نویسی تکاملی (Evolutionary Programming): مشابه برنامه‌نویسی ژنتیک است، با این تفاوت که ساختار برنامه‌های کامپیوتری ثابت است و پارامترهای عددی این الگوریتم را می‌توان در فرایند تکامل بهینه کرد.
• برنامه‌‎نویسی عبارات ژنی (Gene expression programming): همانند برنامه‌نویسی ژنتیک، الگوریتم برنامه‌‎نویسی عبارات ژنی نیز برای تکامل برنامه‌های کامپیوتری مورد استفاده قرار می‌گیرند. با این تفاوت که در این الگوریتم، یک سیستم ژنوتایپ-فنوتیپ (Genotype-Phenotype) مورد بررسی قرار می‌گیرد که در آن برنامه‌های کامپیوتری با اندازه مختلف، در کروموزم‌های خطی با اندازه ثابت کد بندی شده‌اند.
• استراتژی تکاملی (Evolution strategy): در این روش، از بردارهای متشکل از مقادیر حقیقی برای نمایش جواب‌های کاندید استفاده می‌شود. همچنین، این دسته از الگوریتم‌های محاسبات تکاملی از نرخ جهش خود تطبیقی (Self-adaptive Mutation Rate) استفاده می‌کنند.

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

• «تکامل تفاضلی» (Differential Evolution): این الگوریتم بر مبنای تفاوت میان بردارها بنا نهاده شده است. بنابراین بیشتر برای مسائل «بهینه‌سازی عددی» (Numerical Optimization) مناسب خواهد بود.
• «تکامل عصبی» (Neuroevolution): مشابه الگوریتم برنامه‌نویسی ژنتیک است. این دسته از الگوریتم‌های محاسبات تکاملی فرمی از هوش مصنوعی هستند که از الگوریتم‌های تکاملی برای تولید شبکه‌های عصبی مصنوعی (Artificial Neural Network)، قوانین، توپولوژی شبکه و پارامترها استفاده می‌کنند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های الگوریتم‌‌های بهینه‌‌سازی هوشمند
• آموزش تئوری و عملی الگوریتم‌های ژنتیک
• مجموعه آموزش‌‌های هوش مصنوعی
• الگوریتم بهینه سازی فاخته — از صفر تا صد
• الگوریتم ژنتیک — از صفر تا صد
• الگوریتم کلونی مورچگان — از صفر تا صد
• الگوریتم کرم شب تاب — از صفر تا صد

^^