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

۱۹۶۳ بازدید
آخرین به‌روزرسانی: ۱۸ تیر ۱۴۰۲
زمان مطالعه: ۲۸ دقیقه
محاسبات تکاملی چیست؟ — به زبان ساده

در این مطلب، با مبحث «محاسبات تکاملی» (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) ایجاد می‌شوند. همچنین، از عملگرهای تکاملی نظیر ترکیب یا آمیزش جهت تولید نمونه‌های فرزند استفاده می‌شود؛ در این عملگر، ژن‎‌های تشکیل دهنده دو نمونه والد با یکدیگر ترکیب می‌شوند و فرزندان حاصل، ویژگی‌های ژنی نمونه‌های والد را به ارث می‌برند.

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

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

1function varargout = tsp_ga(varargin)
2    
3    % Initialize default configuration
4    defaultConfig.xy          = 10*rand(50,2);
5    defaultConfig.dmat        = [];
6    defaultConfig.popSize     = 100;
7    defaultConfig.numIter     = 1e4;
8    defaultConfig.showProg    = true;
9    defaultConfig.showResult  = true;
10    defaultConfig.showWaitbar = false;
11    
12    % Interpret user configuration inputs
13    if ~nargin
14        userConfig = struct();
15    elseif isstruct(varargin{1})
16        userConfig = varargin{1};
17    else
18        try
19            userConfig = struct(varargin{:});
20        catch
21            error('Expected inputs are either a structure or parameter/value pairs');
22        end
23    end
24    
25    % Override default configuration with user inputs
26    configStruct = get_config(defaultConfig,userConfig);
27    
28    % Extract configuration
29    xy          = configStruct.xy;
30    dmat        = configStruct.dmat;
31    popSize     = configStruct.popSize;
32    numIter     = configStruct.numIter;
33    showProg    = configStruct.showProg;
34    showResult  = configStruct.showResult;
35    showWaitbar = configStruct.showWaitbar;
36    if isempty(dmat)
37        nPoints = size(xy,1);
38        a = meshgrid(1:nPoints);
39        dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nPoints,nPoints);
40    end
41    
42    % Verify Inputs
43    [N,dims] = size(xy);
44    [nr,nc] = size(dmat);
45    if N ~= nr || N ~= nc
46        error('Invalid XY or DMAT inputs!')
47    end
48    n = N;
49    
50    % Sanity Checks
51    popSize     = 4*ceil(popSize/4);
52    numIter     = max(1,round(real(numIter(1))));
53    showProg    = logical(showProg(1));
54    showResult  = logical(showResult(1));
55    showWaitbar = logical(showWaitbar(1));
56    
57    % Initialize the Population
58    pop = zeros(popSize,n);
59    pop(1,:) = (1:n);
60    for k = 2:popSize
61        pop(k,:) = randperm(n);
62    end
63    
64    % Run the GA
65    globalMin = Inf;
66    totalDist = zeros(1,popSize);
67    distHistory = zeros(1,numIter);
68    tmpPop = zeros(4,n);
69    newPop = zeros(popSize,n);
70    if showProg
71        figure('Name','TSP_GA | Current Best Solution','Numbertitle','off');
72        hAx = gca;
73    end
74    if showWaitbar
75        hWait = waitbar(0,'Searching for near-optimal solution ...');
76    end
77    for iter = 1:numIter
78        % Evaluate Each Population Member (Calculate Total Distance)
79        for p = 1:popSize
80            d = dmat(pop(p,n),pop(p,1)); % Closed Path
81            for k = 2:n
82                d = d + dmat(pop(p,k-1),pop(p,k));
83            end
84            totalDist(p) = d;
85        end
86        
87        % Find the Best Route in the Population
88        [minDist,index] = min(totalDist);
89        distHistory(iter) = minDist;
90        if minDist < globalMin
91            globalMin = minDist;
92            optRoute = pop(index,:);
93            if showProg
94                % Plot the Best Route
95                rte = optRoute([1:n 1]);
96                if dims > 2, plot3(hAx,xy(rte,1),xy(rte,2),xy(rte,3),'r.-');
97                else plot(hAx,xy(rte,1),xy(rte,2),'r.-'); end
98                title(hAx,sprintf('Total Distance = %1.4f, Iteration = %d',minDist,iter));
99                drawnow;
100            end
101        end
102        
103        % Genetic Algorithm Operators
104        randomOrder = randperm(popSize);
105        for p = 4:4:popSize
106            rtes = pop(randomOrder(p-3:p),:);
107            dists = totalDist(randomOrder(p-3:p));
108            [ignore,idx] = min(dists); %#ok
109            bestOf4Route = rtes(idx,:);
110            routeInsertionPoints = sort(ceil(n*rand(1,2)));
111            I = routeInsertionPoints(1);
112            J = routeInsertionPoints(2);
113            for k = 1:4 % Mutate the Best to get Three New Routes
114                tmpPop(k,:) = bestOf4Route;
115                switch k
116                    case 2 % Flip
117                        tmpPop(k,I:J) = tmpPop(k,J:-1:I);
118                    case 3 % Swap
119                        tmpPop(k,[I J]) = tmpPop(k,[J I]);
120                    case 4 % Slide
121                        tmpPop(k,I:J) = tmpPop(k,[I+1:J I]);
122                    otherwise % Do Nothing
123                end
124            end
125            newPop(p-3:p,:) = tmpPop;
126        end
127        pop = newPop;
128        
129        % Update the waitbar
130        if showWaitbar && ~mod(iter,ceil(numIter/325))
131            waitbar(iter/numIter,hWait);
132        end
133        
134    end
135    if showWaitbar
136        close(hWait);
137    end
138    
139    if showResult
140        % Plots the GA Results
141        figure('Name','TSP_GA | Results','Numbertitle','off');
142        subplot(2,2,1);
143        pclr = ~get(0,'DefaultAxesColor');
144        if dims > 2, plot3(xy(:,1),xy(:,2),xy(:,3),'.','Color',pclr);
145        else plot(xy(:,1),xy(:,2),'.','Color',pclr); end
146        title('City Locations');
147        subplot(2,2,2);
148        imagesc(dmat(optRoute,optRoute));
149        title('Distance Matrix');
150        subplot(2,2,3);
151        rte = optRoute([1:n 1]);
152        if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'r.-');
153        else plot(xy(rte,1),xy(rte,2),'r.-'); end
154        title(sprintf('Total Distance = %1.4f',minDist));
155        subplot(2,2,4);
156        plot(distHistory,'b','LineWidth',2);
157        title('Best Solution History');
158        set(gca,'XLim',[0 numIter+1],'YLim',[0 1.1*max([1 distHistory])]);
159    end
160    
161    % Return Output
162    if nargout
163        resultStruct = struct( ...
164            'xy',          xy, ...
165            'dmat',        dmat, ...
166            'popSize',     popSize, ...
167            'numIter',     numIter, ...
168            'showProg',    showProg, ...
169            'showResult',  showResult, ...
170            'showWaitbar', showWaitbar, ...
171            'optRoute',    optRoute, ...
172            'minDist',     minDist);
173        
174        varargout = {resultStruct};
175    end
176    
177end
178
179% Subfunction to override the default configuration with user inputs
180function config = get_config(defaultConfig,userConfig)
181    
182    % Initialize the configuration structure as the default
183    config = defaultConfig;
184    
185    % Extract the field names of the default configuration structure
186    defaultFields = fieldnames(defaultConfig);
187    
188    % Extract the field names of the user configuration structure
189    userFields = fieldnames(userConfig);
190    nUserFields = length(userFields);
191    
192    % Override any default configuration fields with user values
193    for i = 1:nUserFields
194        userField = userFields{i};
195        isField = strcmpi(defaultFields,userField);
196        if nnz(isField) == 1
197            thisField = defaultFields{isField};
198            config.(thisField) = userConfig.(userField);
199        end
200    end
201    
202end

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

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

1import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt
2
3class City:
4    def __init__(self, x, y):
5        self.x = x
6        self.y = y
7    
8    def distance(self, city):
9        xDis = abs(self.x - city.x)
10        yDis = abs(self.y - city.y)
11        distance = np.sqrt((xDis ** 2) + (yDis ** 2))
12        return distance
13    
14    def __repr__(self):
15        return "(" + str(self.x) + "," + str(self.y) + ")"
16
17class Fitness:
18    def __init__(self, route):
19        self.route = route
20        self.distance = 0
21        self.fitness= 0.0
22    
23    def routeDistance(self):
24        if self.distance ==0:
25            pathDistance = 0
26            for i in range(0, len(self.route)):
27                fromCity = self.route[i]
28                toCity = None
29                if i + 1 < len(self.route):
30                    toCity = self.route[i + 1]
31                else:
32                    toCity = self.route[0]
33                pathDistance += fromCity.distance(toCity)
34            self.distance = pathDistance
35        return self.distance
36    
37    def routeFitness(self):
38        if self.fitness == 0:
39            self.fitness = 1 / float(self.routeDistance())
40        return self.fitness
41
42def createRoute(cityList):
43    route = random.sample(cityList, len(cityList))
44    return route
45
46def initialPopulation(popSize, cityList):
47    population = []
48
49    for i in range(0, popSize):
50        population.append(createRoute(cityList))
51    return population
52
53def rankRoutes(population):
54    fitnessResults = {}
55    for i in range(0,len(population)):
56        fitnessResults[i] = Fitness(population[i]).routeFitness()
57    return sorted(fitnessResults.items(), key = operator.itemgetter(1), reverse = True)
58
59def selection(popRanked, eliteSize):
60    selectionResults = []
61    df = pd.DataFrame(np.array(popRanked), columns=["Index","Fitness"])
62    df['cum_sum'] = df.Fitness.cumsum()
63    df['cum_perc'] = 100*df.cum_sum/df.Fitness.sum()
64    
65    for i in range(0, eliteSize):
66        selectionResults.append(popRanked[i][0])
67    for i in range(0, len(popRanked) - eliteSize):
68        pick = 100*random.random()
69        for i in range(0, len(popRanked)):
70            if pick <= df.iat[i,3]:
71                selectionResults.append(popRanked[i][0])
72                break
73    return selectionResults
74
75def matingPool(population, selectionResults):
76    matingpool = []
77    for i in range(0, len(selectionResults)):
78        index = selectionResults[i]
79        matingpool.append(population[index])
80    return matingpool
81
82def breed(parent1, parent2):
83    child = []
84    childP1 = []
85    childP2 = []
86    
87    geneA = int(random.random() * len(parent1))
88    geneB = int(random.random() * len(parent1))
89    
90    startGene = min(geneA, geneB)
91    endGene = max(geneA, geneB)
92
93    for i in range(startGene, endGene):
94        childP1.append(parent1[i])
95        
96    childP2 = [item for item in parent2 if item not in childP1]
97
98    child = childP1 + childP2
99    return child
100
101def breedPopulation(matingpool, eliteSize):
102    children = []
103    length = len(matingpool) - eliteSize
104    pool = random.sample(matingpool, len(matingpool))
105
106    for i in range(0,eliteSize):
107        children.append(matingpool[i])
108    
109    for i in range(0, length):
110        child = breed(pool[i], pool[len(matingpool)-i-1])
111        children.append(child)
112    return children
113
114def mutate(individual, mutationRate):
115    for swapped in range(len(individual)):
116        if(random.random() < mutationRate):
117            swapWith = int(random.random() * len(individual))
118            
119            city1 = individual[swapped]
120            city2 = individual[swapWith]
121            
122            individual[swapped] = city2
123            individual[swapWith] = city1
124    return individual
125
126def mutatePopulation(population, mutationRate):
127    mutatedPop = []
128    
129    for ind in range(0, len(population)):
130        mutatedInd = mutate(population[ind], mutationRate)
131        mutatedPop.append(mutatedInd)
132    return mutatedPop
133
134def nextGeneration(currentGen, eliteSize, mutationRate):
135    popRanked = rankRoutes(currentGen)
136    selectionResults = selection(popRanked, eliteSize)
137    matingpool = matingPool(currentGen, selectionResults)
138    children = breedPopulation(matingpool, eliteSize)
139    nextGeneration = mutatePopulation(children, mutationRate)
140    return nextGeneration
141
142def geneticAlgorithm(population, popSize, eliteSize, mutationRate, generations):
143    pop = initialPopulation(popSize, population)
144    print("Initial distance: " + str(1 / rankRoutes(pop)[0][1]))
145    
146    for i in range(0, generations):
147        pop = nextGeneration(pop, eliteSize, mutationRate)
148    
149    print("Final distance: " + str(1 / rankRoutes(pop)[0][1]))
150    bestRouteIndex = rankRoutes(pop)[0][0]
151    bestRoute = pop[bestRouteIndex]
152    return bestRoute
153
154cityList = []
155
156for i in range(0,25):
157    cityList.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))
158
159geneticAlgorithm(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)
160
161def geneticAlgorithmPlot(population, popSize, eliteSize, mutationRate, generations):
162    pop = initialPopulation(popSize, population)
163    progress = []
164    progress.append(1 / rankRoutes(pop)[0][1])
165    
166    for i in range(0, generations):
167        pop = nextGeneration(pop, eliteSize, mutationRate)
168        progress.append(1 / rankRoutes(pop)[0][1])
169    
170    plt.plot(progress)
171    plt.ylabel('Distance')
172    plt.xlabel('Generation')
173    plt.show()
174
175geneticAlgorithmPlot(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)

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

از یک دیدگاه انتزاعی‌تر به الگوریتم‌های محاسبات تکاملی، چنین رویکردهایی در دسته «الگوریتم‌های احتمالی» (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)

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

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

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

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

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

  1. جمعیت اولیه: یک آرایه 28 عنصری متشکل از الفبای ABCDEFGHIJKLMNOPQRSTUVWXYZ.
  2. هدف نهایی: تبدیل رشته ورودی یا جمعیت اولیه به رشته METHINKS IT IS LIKE A WEASEL.
  3. تابع برازندگی: تابعی که شباهت آرگومان ورودی را به رشته نهایی یا هدف نهایی مشخص می‌کند.
  4. عملگرهای تکاملی (پیاده‌سازی عملگر انتخاب و جهش ضروری است، ولی پیاده‌سازی عملگر ترکیب اختیاری است)
1%This class impliments a string that mutates to a target
2classdef EvolutionaryAlgorithm
3 
4    properties
5 
6        target;
7        parent;
8        children = {};
9        validAlphabet;
10 
11        %Constants
12        numChildrenPerIteration;
13        maxIterations;
14        mutationRate;
15 
16    end
17 
18    methods
19 
20        %Class constructor
21        function family = EvolutionaryAlgorithm(target,mutationRate,numChildren,maxIterations)
22 
23            family.validAlphabet = char([32 (65:90)]); %Space char and A-Z
24            family.target = target;
25            family.children = cell(numChildren,1);
26            family.numChildrenPerIteration = numChildren;
27            family.maxIterations = maxIterations;
28            family.mutationRate = mutationRate;
29            initialize(family);
30 
31        end %class constructor
32 
33        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
34        %Helper functions and class get/set functions
35        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36 
37        %setAlphabet() - sets the valid alphabet for the current instance
38        %of the EvolutionaryAlgorithm class.
39        function setAlphabet(family,alphabet)
40 
41            if(ischar(alphabet))
42                family.validAlphabet = alphabet;
43 
44                %Makes change permanent
45                assignin('caller',inputname(1),family); 
46            else
47                error 'New alphabet must be a string or character array';
48            end            
49 
50        end
51 
52        %setTarget() - sets the target for the current instance
53        %of the EvolutionaryAlgorithm class.
54        function setTarget(family,target)
55 
56            if(ischar(target))
57                family.target = target;
58 
59                %Makes change permanent
60                assignin('caller',inputname(1),family); 
61            else
62                error 'New target must be a string or character array';
63            end            
64 
65        end
66 
67        %setMutationRate() - sets the mutation rate for the current instance
68        %of the EvolutionaryAlgorithm class.
69        function setMutationRate(family,mutationRate)
70 
71            if(isnumeric(mutationRate))
72                family.mutationRate = mutationRate;
73 
74                %Makes change permanent
75                assignin('caller',inputname(1),family); 
76            else
77                error 'New mutation rate must be a double precision number';
78            end            
79 
80        end
81 
82        %setMaxIterations() - sets the maximum number of iterations during
83        %evolution for the current instance of the EvolutionaryAlgorithm class.
84        function setMaxIterations(family,maxIterations)
85 
86            if(isnumeric(maxIterations))
87                family.maxIterations = maxIterations;
88 
89                %Makes change permanent
90                assignin('caller',inputname(1),family); 
91            else
92                error 'New maximum amount of iterations must be a double precision number';
93            end            
94 
95        end
96 
97        %display() - overrides the built-in MATLAB display() function, to
98        %display the important class variables
99        function display(family)
100            disp([sprintf('Target: %s\n',family.target)...
101                  sprintf('Parent: %s\n',family.parent)...
102                  sprintf('Valid Alphabet: %s\n',family.validAlphabet)...
103                  sprintf('Number of Children: %d\n',family.numChildrenPerIteration)...
104                  sprintf('Mutation Rate [0,1]: %d\n',family.mutationRate)...
105                  sprintf('Maximum Iterations: %d\n',family.maxIterations)]);                 
106        end
107 
108        %disp() - overrides the built-in MATLAB disp() function, to
109        %display the important class variables
110        function disp(family)
111            display(family);
112        end
113 
114        %randAlphabetElement() - Generates a random character from the
115        %valid alphabet for the current instance of the class.
116        function elements = randAlphabetElements(family,numChars)
117 
118            %Sample the valid alphabet randomly from the uniform
119            %distribution
120            N = length(family.validAlphabet);
121            choices = ceil(N*rand(1,numChars));
122 
123            elements = family.validAlphabet(choices);
124 
125        end
126 
127        %initialize() - Sets the parent to a random string of length equal
128        %to the length of the target
129        function parent = initialize(family)
130 
131            family.parent = randAlphabetElements(family,length(family.target));
132            parent = family.parent;
133 
134            %Makes changes to the instance of EvolutionaryAlgorithm permanent
135            assignin('caller',inputname(1),family); 
136 
137        end %initialize
138 
139        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
140        %Functions required by task specification
141        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
142 
143        %mutate() - generates children from the parent and mutates them
144        function mutate(family)
145 
146            sizeParent = length(family.parent);
147 
148            %Generate mutatant children sequentially
149            for child = (1:family.numChildrenPerIteration)
150 
151                parentCopy = family.parent;
152 
153                for charIndex = (1:sizeParent) 
154                    if (rand(1) < family.mutationRate)
155                        parentCopy(charIndex) = randAlphabetElements(family,1);
156                    end
157                end
158 
159                family.children{child} = parentCopy;
160 
161            end
162 
163            %Makes changes to the instance of EvolutionaryAlgorithm permanent
164            assignin('caller',inputname(1),family);  
165 
166        end %mutate
167 
168        %fitness() - Computes the Hamming distance between the target
169        %string and the string input as the familyMember argument
170        function theFitness = fitness(family,familyMember)
171 
172            if not(ischar(familyMember))
173                error 'The second argument must be a string';
174            end
175 
176            theFitness = sum(family.target == familyMember);
177        end
178 
179        %evolve() - evolves the family until the target is reached or it 
180        %exceeds the maximum amount of iterations        
181        function [iteration,mostFitFitness] = evolve(family)
182 
183            iteration = 0;
184            mostFitFitness = 0;
185            targetFitness = fitness(family,family.target);
186 
187            disp(['Target fitness is ' num2str(targetFitness)]);
188 
189            while (mostFitFitness < targetFitness) && (iteration < family.maxIterations)
190 
191                iteration = iteration + 1;
192 
193                mutate(family);
194 
195                parentFitness = fitness(family,family.parent);                
196                mostFit = family.parent;
197                mostFitFitness = parentFitness;
198 
199                for child = (1:family.numChildrenPerIteration)
200 
201                    childFitness = fitness(family,family.children{child});
202                    if childFitness > mostFitFitness
203                        mostFit = family.children{child};
204                        mostFitFitness = childFitness;
205                    end
206 
207                end               
208 
209                family.parent = mostFit;
210                disp([num2str(iteration) ': ' mostFit ' - Fitness: ' num2str(mostFitFitness)]);
211 
212            end
213 
214            %Makes changes to the instance of EvolutionaryAlgorithm permanent
215            assignin('caller',inputname(1),family);
216 
217        end %evolve
218 
219    end %methods
220end %classdef

اجرا:

1>> instance = EvolutionaryAlgorithm('METHINKS IT IS LIKE A WEASEL',.08,50,1000)
2Target: METHINKS IT IS LIKE A WEASEL
3Parent: UVEOCXXFBGDCSFNMJQNWTPJ PCVA
4Valid Alphabet:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
5Number of Children: 50
6Mutation Rate [0,1]: 8.000000e-002
7Maximum Iterations: 1000
8 
9>> evolve(instance);

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

1from string import letters
2from random import choice, random
3 
4target  = list("METHINKS IT IS LIKE A WEASEL")
5charset = letters + ' '
6parent  = [choice(charset) for _ in range(len(target))]
7minmutaterate  = .09
8C = range(100)
9 
10perfectfitness = float(len(target))
11 
12def fitness(trial):
13    'Sum of matching chars by position'
14    return sum(t==h for t,h in zip(trial, target))
15 
16def mutaterate():
17    'Less mutation the closer the fit of the parent'
18    return 1-((perfectfitness - fitness(parent)) / perfectfitness * (1 - minmutaterate))
19 
20def mutate(parent, rate):
21    return [(ch if random() <= rate else choice(charset)) for ch in parent]
22 
23def que():
24    '(from the favourite saying of Manuel in Fawlty Towers)'
25    print ("#%-4i, fitness: %4.1f%%, '%s'" %
26           (iterations, fitness(parent)*100./perfectfitness, ''.join(parent)))
27 
28def mate(a, b):
29    place = 0
30    if choice(xrange(10)) < 7:
31        place = choice(xrange(len(target)))
32    else:
33        return a, b
34 
35    return a, b, a[:place] + b[place:], b[:place] + a[place:]
36 
37iterations = 0
38center = len(C)/2
39while parent != target:
40    rate = mutaterate()
41    iterations += 1
42    if iterations % 100 == 0: que()
43    copies = [ mutate(parent, rate) for _ in C ]  + [parent]
44    parent1 = max(copies[:center], key=fitness)
45    parent2 = max(copies[center:], key=fitness)
46    parent = max(mate(parent1, parent2), key=fitness)
47que()
  • «برنامه‌نویسی ژنتیک» (Genetic Programming): در این روش محاسبات تکاملی، جواب‌ها به فرم برنامه‌های کامپیوتری و معمولا در قالب درخت LISP نمایش داده می‌شوند. همچنین، برازندگی جواب‌های کاندید به وسیله قابلیت آن‌ها در حل یک مسأله محاسباتی سنجیده می‌شود.

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

1from random import random, randint, seed
2from statistics import mean
3from copy import deepcopy
4import matplotlib.pyplot as plt
5from IPython.display import Image, display
6from graphviz import Digraph, Source 
7
8POP_SIZE        = 60    # population size
9MIN_DEPTH       = 2     # minimal initial random tree depth
10MAX_DEPTH       = 5     # maximal initial random tree depth
11GENERATIONS     = 250   # maximal number of generations to run evolution
12TOURNAMENT_SIZE = 5     # size of tournament for tournament selection
13XO_RATE         = 0.8   # crossover rate 
14PROB_MUTATION   = 0.2   # per-node mutation probability 
15BLOAT_CONTROL   = False # True adds bloat control to fitness function
16
17def add(x, y): return x + y
18def sub(x, y): return x - y
19def mul(x, y): return x * y
20FUNCTIONS = [add, sub, mul]
21TERMINALS = ['x', -2, -1, 0, 1, 2] 
22
23def target_func(x): # evolution's target
24    return x*x*x*x + x*x*x + x*x + x + 1
25
26def generate_dataset(): # generate 101 data points from target_func
27    dataset = []
28    for x in range(-100,101,2): 
29        x /= 100
30        dataset.append([x, target_func(x)])
31    return dataset
32
33class GPTree:
34    def __init__(self, data = None, left = None, right = None):
35        self.data  = data
36        self.left  = left
37        self.right = right
38        
39    def node_label(self): # return string label
40        if (self.data in FUNCTIONS):
41            return self.data.__name__
42        else: 
43            return str(self.data)
44    
45    def draw(self, dot, count): # dot & count are lists in order to pass "by reference" 
46        node_name = str(count[0])
47        dot[0].node(node_name, self.node_label())
48        if self.left:
49            count[0] += 1
50            dot[0].edge(node_name, str(count[0]))
51            self.left.draw(dot, count)
52        if self.right:
53            count[0] += 1
54            dot[0].edge(node_name, str(count[0]))
55            self.right.draw(dot, count)
56        
57    def draw_tree(self, fname, footer):
58        dot = [Digraph()]
59        dot[0].attr(kw='graph', label = footer)
60        count = [0]
61        self.draw(dot, count)
62        Source(dot[0], filename = fname + ".gv", format="png").render()
63        display(Image(filename = fname + ".gv.png"))
64
65    def compute_tree(self, x): 
66        if (self.data in FUNCTIONS): 
67            return self.data(self.left.compute_tree(x), self.right.compute_tree(x))
68        elif self.data == 'x': return x
69        else: return self.data
70            
71    def random_tree(self, grow, max_depth, depth = 0): # create random tree using either grow or full method
72        if depth < MIN_DEPTH or (depth < max_depth and not grow): 
73            self.data = FUNCTIONS[randint(0, len(FUNCTIONS)-1)]
74        elif depth >= max_depth:   
75            self.data = TERMINALS[randint(0, len(TERMINALS)-1)]
76        else: # intermediate depth, grow
77            if random () > 0.5: 
78                self.data = TERMINALS[randint(0, len(TERMINALS)-1)]
79            else:
80                self.data = FUNCTIONS[randint(0, len(FUNCTIONS)-1)]
81        if self.data in FUNCTIONS:
82            self.left = GPTree()          
83            self.left.random_tree(grow, max_depth, depth = depth + 1)            
84            self.right = GPTree()
85            self.right.random_tree(grow, max_depth, depth = depth + 1)
86
87    def mutation(self):
88        if random() < PROB_MUTATION: # mutate at this node
89            self.random_tree(grow = True, max_depth = 2)
90        elif self.left: self.left.mutation()
91        elif self.right: self.right.mutation() 
92        
93    def size(self): # tree size in nodes
94        if self.data in TERMINALS: return 1
95        l = self.left.size()  if self.left  else 0
96        r = self.right.size() if self.right else 0
97        return 1 + l + r
98
99    def build_subtree(self): # count is list in order to pass "by reference"
100        t = GPTree()
101        t.data = self.data
102        if self.left:  t.left  = self.left.build_subtree()
103        if self.right: t.right = self.right.build_subtree()
104        return t
105                        
106    def scan_tree(self, count, second): # note: count is list, so it's passed "by reference"
107        count[0] -= 1            
108        if count[0] <= 1: 
109            if not second: # return subtree rooted here
110                return self.build_subtree()
111            else: # glue subtree here
112                self.data  = second.data
113                self.left  = second.left
114                self.right = second.right
115        else:  
116            ret = None              
117            if self.left  and count[0] > 1: ret = self.left.scan_tree(count, second)  
118            if self.right and count[0] > 1: ret = self.right.scan_tree(count, second)  
119            return ret
120
121    def crossover(self, other): # xo 2 trees at random nodes
122        if random() < XO_RATE:
123            second = other.scan_tree([randint(1, other.size())], None) # 2nd random subtree
124            self.scan_tree([randint(1, self.size())], second) # 2nd subtree "glued" inside 1st tree
125# end class GPTree
126                   
127def init_population(): # ramped half-and-half
128    pop = []
129    for md in range(3, MAX_DEPTH + 1):
130        for i in range(int(POP_SIZE/6)):
131            t = GPTree()
132            t.random_tree(grow = True, max_depth = md) # grow
133            pop.append(t) 
134        for i in range(int(POP_SIZE/6)):
135            t = GPTree()
136            t.random_tree(grow = False, max_depth = md) # full
137            pop.append(t) 
138    return pop
139
140def error(individual, dataset):
141    return mean([abs(individual.compute_tree(ds[0]) - ds[1]) for ds in dataset])
142
143def fitness(individual, dataset): 
144    if BLOAT_CONTROL:
145        return 1 / (1 + error(individual, dataset) + 0.01*individual.size())
146    else:
147        return 1 / (1 + error(individual, dataset))
148                
149def selection(population, fitnesses): # select one individual using tournament selection
150    tournament = [randint(0, len(population)-1) for i in range(TOURNAMENT_SIZE)] # select tournament contenders
151    tournament_fitnesses = [fitnesses[tournament[i]] for i in range(TOURNAMENT_SIZE)]
152    return deepcopy(population[tournament[tournament_fitnesses.index(max(tournament_fitnesses))]]) 
153            
154def prepare_plots():
155    fig, axarr = plt.subplots(2, sharex=True)
156    fig.canvas.set_window_title('EVOLUTIONARY PROGRESS')
157    fig.subplots_adjust(hspace = 0.5)
158    axarr[0].set_title('error', fontsize=14)
159    axarr[1].set_title('mean size', fontsize=14)
160    plt.xlabel('generation', fontsize=18)
161    plt.ion() # interactive mode for plot
162    axarr[0].set_xlim(0, GENERATIONS)
163    axarr[0].set_ylim(0, 1) # fitness range
164    xdata = []
165    ydata = [ [], [] ]
166    line = [None, None]
167    line[0], = axarr[0].plot(xdata, ydata[0], 'b-') # 'b-' = blue line    
168    line[1], = axarr[1].plot(xdata, ydata[1], 'r-') # 'r-' = red line
169    return axarr, line, xdata, ydata
170
171def plot(axarr, line, xdata, ydata, gen, pop, errors, max_mean_size):
172    xdata.append(gen)
173    ydata[0].append(min(errors))
174    line[0].set_xdata(xdata)
175    line[0].set_ydata(ydata[0])
176    sizes = [ind.size() for ind in pop]
177    if mean(sizes) > max_mean_size[0]:
178        max_mean_size[0] = mean(sizes)
179        axarr[1].set_ylim(0, max_mean_size[0])
180    ydata[1].append(mean(sizes))
181    line[1].set_xdata(xdata)
182    line[1].set_ydata(ydata[1])
183    plt.draw()  
184    plt.pause(0.01)
185
186def main():      
187    # init stuff
188    seed() # init internal state of random number generator
189    dataset = generate_dataset()
190    population= init_population() 
191    best_of_run = None
192    best_of_run_error = 1e20 
193    best_of_run_gen = 0
194    fitnesses = [fitness(ind, dataset) for ind in population]
195    max_mean_size = [0] # track maximal mean size for plotting
196    axarr, line, xdata, ydata = prepare_plots()
197
198    # go evolution!
199    for gen in range(GENERATIONS):        
200        nextgen_population=[]
201        for i in range(POP_SIZE):
202            parent1 = selection(population, fitnesses)
203            parent2 = selection(population, fitnesses)
204            parent1.crossover(parent2)
205            parent1.mutation()
206            nextgen_population.append(parent1)
207        population=nextgen_population
208        fitnesses = [fitness(ind, dataset) for ind in population]
209        errors = [error(ind, dataset) for ind in population]
210        if min(errors) < best_of_run_error:
211            best_of_run_error = min(errors)
212            best_of_run_gen = gen
213            best_of_run = deepcopy(population[errors.index(min(errors))])
214            print("________________________")
215            best_of_run.draw_tree("best_of_run",\
216                                  "gen: " + str(gen) + ", error: " + str(round(best_of_run_error,3)))
217        plot(axarr, line, xdata, ydata, gen, population, errors, max_mean_size)
218        if best_of_run_error <= 1e-5: break
219    
220    endrun = "_________________________________________________\nEND OF RUN (bloat control was "
221    endrun += "ON)" if BLOAT_CONTROL else "OFF)"
222    print(endrun)
223    s = "\n\nbest_of_run attained at gen " + str(best_of_run_gen) + " and has error=" + str(round(best_of_run_error,3))
224    best_of_run.draw_tree("best_of_run",s)
225    
226if __name__== "__main__":
227  main()
  • برنامه‌نویسی تکاملی (Evolutionary Programming): مشابه برنامه‌نویسی ژنتیک است، با این تفاوت که ساختار برنامه‌های کامپیوتری ثابت است و پارامترهای عددی این الگوریتم را می‌توان در فرایند تکامل بهینه کرد.
  • برنامه‌‎نویسی عبارات ژنی (Gene expression programming): همانند برنامه‌نویسی ژنتیک، الگوریتم برنامه‌‎نویسی عبارات ژنی نیز برای تکامل برنامه‌های کامپیوتری مورد استفاده قرار می‌گیرند. با این تفاوت که در این الگوریتم، یک سیستم ژنوتایپ-فنوتیپ (Genotype-Phenotype) مورد بررسی قرار می‌گیرد که در آن برنامه‌های کامپیوتری با اندازه مختلف، در کروموزم‌های خطی با اندازه ثابت کد بندی شده‌اند.
  • استراتژی تکاملی (Evolution strategy): در این روش، از بردارهای متشکل از مقادیر حقیقی برای نمایش جواب‌های کاندید استفاده می‌شود. همچنین، این دسته از الگوریتم‌های محاسبات تکاملی از نرخ جهش خود تطبیقی (Self-adaptive Mutation Rate) استفاده می‌کنند.

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

1"""
2The basic idea about Nature Evolution Strategy with visualation.
3Visit my tutorial website for more: https://morvanzhou.github.io/tutorials/
4Dependencies:
5Tensorflow >= r1.2
6numpy
7matplotlib
8"""
9import numpy as np
10import matplotlib.pyplot as plt
11import tensorflow as tf
12from tensorflow.contrib.distributions import MultivariateNormalFullCovariance
13
14DNA_SIZE = 2         # parameter (solution) number
15N_POP = 20           # population size
16N_GENERATION = 100   # training step
17LR = 0.02            # learning rate
18
19
20# fitness function
21def get_fitness(pred): return -((pred[:, 0])**2 + pred[:, 1]**2)
22
23# build multivariate distribution
24mean = tf.Variable(tf.random_normal([2, ], 13., 1.), dtype=tf.float32)
25cov = tf.Variable(5. * tf.eye(DNA_SIZE), dtype=tf.float32)
26mvn = MultivariateNormalFullCovariance(loc=mean, covariance_matrix=cov)
27make_kid = mvn.sample(N_POP)                                    # sampling operation
28
29# compute gradient and update mean and covariance matrix from sample and fitness
30tfkids_fit = tf.placeholder(tf.float32, [N_POP, ])
31tfkids = tf.placeholder(tf.float32, [N_POP, DNA_SIZE])
32loss = -tf.reduce_mean(mvn.log_prob(tfkids)*tfkids_fit)         # log prob * fitness
33train_op = tf.train.GradientDescentOptimizer(LR).minimize(loss) # compute and apply gradients for mean and cov
34
35sess = tf.Session()
36sess.run(tf.global_variables_initializer())                     # initialize tf variables
37
38# something about plotting (can be ignored)
39n = 300
40x = np.linspace(-20, 20, n)
41X, Y = np.meshgrid(x, x)
42Z = np.zeros_like(X)
43for i in range(n):
44    for j in range(n):
45        Z[i, j] = get_fitness(np.array([[x[i], x[j]]]))
46plt.contourf(X, Y, -Z, 100, cmap=plt.cm.rainbow); plt.ylim(-20, 20); plt.xlim(-20, 20); plt.ion()
47
48# training
49for g in range(N_GENERATION):
50    kids = sess.run(make_kid)
51    kids_fit = get_fitness(kids)
52    sess.run(train_op, {tfkids_fit: kids_fit, tfkids: kids})    # update distribution parameters
53
54    # plotting update
55    if 'sca' in globals(): sca.remove()
56    sca = plt.scatter(kids[:, 0], kids[:, 1], s=30, c='k');plt.pause(0.01)
57
58print('Finished'); plt.ioff(); plt.show()

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

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

^^

بر اساس رای ۱۸ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
Alan ZucconiWikipediaClever Algorithms
۲ دیدگاه برای «محاسبات تکاملی چیست؟ — به زبان ساده»

سلام
رفرنس این مطالب را هم ذکر بفرمایید.
ممنون

سلام، وقت شما بخیر؛

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

از اینکه با مجله فرادرس همراه هستید از شما بسیار سپاسگزاریم.

نظر شما چیست؟

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