در سال‌های اخیر بصورت گسترده‌‌ای از الگوریتم های تکاملی و فرامکاشفه‌های زیستی برای حل مسائل گوناگون و بهینه‌سازی استفاده شده است. مهمترین موضوعی که باعث رشد استفاده از این الگوریتم‌ها شده است، سادگی پیاده‌سازی و کاربردپذیری آن‌ها در مسائل مختلف است.
الگوریتم های تکاملی، جواب‌های با کیفیت بالا و زمان قابل قبولی را ارائه می‌کنند. همین قابلیت باعث می‌شود تا بتوان از آن‌ها با کمترین زمان محاسبه برای یافتن پاسخ‌هایی نزدیک به بهینه استفاده کرد.
جایگاه الگوریتم های تکاملی در حل مسائل پیچیده
دنیایی که ما در آن زندگی می‌کنیم به صورت مستمر در حال تغییر است. تکامل براساس تطبیق‌پذیری شکل می‌گیرد. ما برای اینکه با محیط اطراف خود بتوانیم تطابق پیدا کنیم باید توانایی‌های خود را بهبود دهیم. به همین دلیل گفته می‌شود که تکامل یک فرآیند بهینه‌سازی می‌باشد که هدف آن بهبود توانایی‌های یک سیستم برای حضور بهتر در یک محیط متغییر و پویا می‌باشد.
تکامل و نظریه داروین
در تعریف تکامل دو نظریه داروین و لامارکی مشهور می‌باشند. نظریه تکامل لامارکی به انتقال موروثی صفات تکیه دارد. ایده اصلی در این نظریه این است که موجودات در طول زندگی، یاد می‌گیرند و خود را با شرایط محیطی وفق می‌دهند و آن ویژگی‌ها را به فرزندان خود انتقال می‌دهند.
مطابق نظریه داروین، در دنیایی با منابع محدود و جمعیت رو به رشد، هر موجودی با سایر موجودات بر سر زنده ماندن رقابت می‌کند. موجوداتی با ژن برتر احتمال بیشتری برای نجات یافتن و تولیدمثل خواهند داشت.
پردازش تکاملی و نظریه داروین
علم پردازش تکاملی(Evolutionary Computation) با الهام از نظریه تکامل داروین، به حل مسائل گوناگون نظیر بهینه‌سازی، جستجو و یادگیری ماشین می‌پردازد. در این راستا از مفاهیمی هم‌چون انتخاب طبیعی، بقاء و تولیدمثل که از مولفه‌های اساسی در نظریه تکاملی داروین هستند به نحو موثری بهره‌برداری می‌شود.
مفاهیم اساسی در الگوریتم های تکاملی
در سال ۱۹۵۳ با کشف ساختار DNA تحولی شگرف در نظریه تکاملی داروین ایجاد شد. این ساختار می‌تواند از یک نسل به نسل دیگر منتقل شود، ساختار مارپیچی در DNA در صورت بازشدن، کدهای بسط یافته از آن استخراج می‌شود که به آن‌ها ژن می‌گوییم. یک دسته ژن می‌تواند ایجاد کننده یک موجود زنده باشند. همین ایده پایه و اساس الگوریتم‌های تکاملی، زیستی و فرامکاشفه‌ای می‌باشد. در زیر به معرفی برخی از مفاهیم مهم در الگوریتم‌های تکاملی می‌پردازیم:
۱- کروموزوم(Chromosome)
اطلاعات ژنی یک موجود در کروموزوم ذخیره می‌شود. هر کروموزوم از DNA تشکیل می‌شود. در الگوریتم های تکاملی منظور از کروموزوم، یک رشته، گراف، درخت یا دنباله‌ای از صفر و یک‌ها می‌باشد که معادل یک پاسخ برای حل یک مسئله می‌باشند.
۲- ژن(Gene)
کروموزوم‌ها به چندین قسمت تقسیم می‌شوند که ژن نام دارند. ژن‌ها خصوصیات گونه‌ها یا افراد را تشکیل می‌دهند. در یک الگوریتم تکاملی، هر پاسخ از چندین بخش تشکیل شده است که به هر کدام از آن بخش‌ها یک مشخصه یا ویژگی گفته می‌شود. مشخصه یا ویژگی در هر پاسخ معادل ژن در کروموزوم است.
۳- آلل(Allele)
هر ژن مجموعه‌ای از مقادیر مجاز را می‌تواند اختیار کند. به هر کدام از این مقادیر یک آلل گفته می‌شود. به عنوان مثال یک ژن مربوط به رنگ چشم است و آلل‌های ممکن برای آن عبارتند از: سیاه، خاکستری، قهوه‌ای، آبی، سز و عسلی. درالگوریتم های تکاملی مقادیر مجاز برای مشخصه‌های هر پاسخ معادل مفهوم آلل است.
۴- ژنوتایپ(Genotype)
ترکیب کامل تمامی ژن‌ها برای یک فرد مشخص، ژنوتایپ(ژنوتیپ) نامیده می‌شود. دنباله ژنی به هر پاسخ در یک الگوریتم تکاملی ژنوتایپ آن پاسخ را نشان می‌دهد.
۵- فنوتایپ(Phenotype)
خصوصیات ظاهری یک شخص که از رمزگشایی یک ژنوتایپ حاصل می‌شود، فنوتایپ(فنوتیپ) نامیده می‌شود. به عبارت دیگر، تجلی معنایی ژنوتایپ مربوط به یک پاسخ در دنیای واقعی ، گویای فنوتایپ آن پاسخ است.
۶- برازش(Reproduction)
شایستگی یک موجود در یک جمعیت، برازش آن موجود نامیده می‌شود. برازش هر پاسخ در جمعیت، با توجه به شایستگی فنوتایپ آن پاسخ تعیین می‌گردد. در یک الگوریتم تکاملی، با استفاده از یک یا چند تابع، برازش هر پاسخ محاسبه می‌شود. تابع برازش، تنها ارتباط یک الگوریتم تکاملی با مسئله مورد تحلیل می‌باشد.
مراحل ایجاد الگوریتم های تکاملی
فرآیند تکامل، از طریق انتخاب طبیعی موجودات در یک جمعیت، را می‌توان به صورت یک جستجو در فضای مقادیر ممکن کروموزوم‌ها در نظر گرفت. مراخل ایجاد یک الگوریتم تکاملی عبارتند از:
مرحله۱: تولید جمعیت اولیه
در این مرحله، یک جمعیت از کروموزوم‌ها یا همان پاسخ‌های مسئله تولید می‌شود. بدیهی است که قبل از تولید جمعیت اولیه بایستی نحوه نمایش کروموزوم‌ها، که یک پاسخ برای مسئله مورد بررسی است، تعیین شود. خروجی مرحله اول یک جمعیت از پاسخ‌ها می‌باشد.
مرحله۲: محاسبه برازش جمعیت ورودی
در این مرحله، برازش تک‌تک کروموزوم‌های جمعیت تولیدشده، با توجه به تابع برازش تعیین شده، محاسبه می‌گردد. خروجی این مرحله، یک جمعیت از پاسخ‌های ارزیابی شده می‌باشد.
مرحله۳: انتخاب برای تولید مثل
در این مرحله، آن دسته از اعضا جمعیت ورودی که برازش بالاتری نسبت به سایر اعضا دارند، برای تبیین قانون بقاء اصلح داروین، انتخاب می‌شوند. خروجی این مرحله، جمعیتی از والدین برازنده است.
مرحله۴: باز ترکیب والدین انتخاب شده
در این مرحله، با توجه به جمعیت والدین برازنده و با استفاده از عملگر بازترکیب، جمعیتی از فرزندان تولید می‌شوند. اعمال عملگر بازترکیب، با توجه به یک پارامتر احتمالی انجام می‌شود. خروجی این مرحله جمعیتی از فرزندان تولید شده می‌باشد.
مرحله۵: جهش فرزندان تولید شده
در این مرحله، فرزندان جدید مرحله قبل تحت عملگر جهش قرار می‌گیرند. البته عملگر جهش با یک احتمال بر روی دنباله ژنی فرزندان رخ می‌دهد. این احتمال با نام احتمال جهش شناخته می‌شود. خروجی این مرحله جمعیتی از فرزندان جهش یافته است.
مرحله۶: محاسبه برازش جمعیت فرزندان
در این مرحله، شایستگی فرزندان جهش یافته، با استفاده از تابع برازش، محاسبه می‌شود. خروجی در این مرحله، جمعیت فرزندان ارزیابی شده است.
مرحله۷: انتخاب برای جایگزینی
در این مرحله، با توجه به جمعیت والدین(ورودی مرحله سوم) و جمعیت فرزندان ارزیابی شده(خروجی مرحله ششم) یک جمعیت جدید برای نسل بعد تولید می‌شود. بدیهی است که خروجی این مرحله جمعیتی است که در آن بخشی از والدین نسل قبل و تعدادی از فرزندان جدید تولید شده نسل جاری وجود دارند.
مرحله۸: بررسی شرط توقف
در این مرحله، در مورد ادامه فرآیند تکاملی الگوریتم تصمیم‌گیری می‌شود. در صورت عدم ارضاء شرط توقف، فرآیند تکاملی الگوریتم با رجوع به مرحله ۳ ادامه می‌یابد. در غیر اینصورت الگوریتم متوقف شده و بهترین پاسخ در آخرین نسل به عنوان حاصل جستجوی تکاملی در خروجی ارائه می‌شود.
انواع الگوریتم های تکاملی
با توجه به روش‌های مختلفی که برای ایجاد مراحل فوق وجود دارد انواع مختلفی از الگوریتم‌های تکاملی پیاده‌سازی می‌شوند. انواع الگوریتم‌های تکاملی عبارتند از:
- الگوریتم ژنتیک(GA)
- برنامه‌نویسی ژنتیک(GP)
- استراتژی تکامل(ES)
- برنامه‌نویسی تکاملی(EP)
- تکامل تفاضلی(DE)
- الگوریتم ممتیک(MA)
- الگوریتم فرهنگی(CA)
- الگوریتم ژنتیک تاگوچی(TGA)
- الگوریتم هم تکاملی(CoEA)
- الگوریتم تکاملی دیلوئیدی(DEA)
- بهینه‌سازی تولیدمثل غیرجنسی(ARO)
- سیستم ایمنی مصنوعی(AIS)
لازم به ذکر است که چهار الگوریتم ابتدایی یعنی GA،GP،ES و EP الگوریتم‌های پایه‌ای در تکامل هستند.
مولفه‌های تاثیرکذار بر روی الگوریتم‌های تکاملی
- طریقه کد کردن راه‌حل مسئله به عنوان کروموزوم
- طراحی تابعی که با آن برازش کروموزوم‌ها(پاسخ‌ها) بررسی شود
- الگوریتم تولید جمعیت اولیه
- الگوریتم مربوط به عملگرهای انتخاب، بازترکیب و جهش
- نحوه تولید جمعیت در نسل‌های بعدی
- تعیین شرط توقف
الگوریتم های تکاملی با یک جمعیّت اولیّه کار خود را شروع می‌کنند و با تکثیر نسل‌های بعدی از روی والدین، سعی در حل مسائل پیچیده به بهترین شکل دارند. این الگوریتم‌ها که زیرشاخه‌ای از علم هوش مصنوعی هستند را می‌توان در علوم نظیر برق، مکانیک، صنایع، زیست‌شناسی، شیمی و رباتیکز به کار گرفت. در مطالب بعدی بطور مفصل به معرفی انواع الگوریتم‌های تکاملی خواهیم پرداخت.
