۴-۲: الگوریتم‌های تکاملی و محاسبات زیستی
۴-۲-۱: مقدمه‌ای بر الگوریتم‌های فرامکاشفه‌ای
جستجو یکی از شاخه‌های مهم در تحقیقات است. نیاز به روش‌های جستجوی با کارایی بیشتر، به علت بزرگ‌تر و پیچیده‌تر شدن مسائل، هر روز بیشتر می‌شود. در متون علمی سه نوع روش برای الگوریتم‌های جستجو وجود دارد ]۵۷[: روش‌های جستجوی تحلیلی، ناآگاهانه (کور) و آگاهانه (مکاشفه‌ای). الگوریتم‌های جستجوی تحلیلی با بهره گرفتن از یک تابع ریاضی هدایت می‌شوند. جستجوی ناآگاهانه به آن دسته از الگوریتم‌هایی اطلاق می‌شود که الگوریتم هیچ اطلاعات اضافه‌ای به جز آنچه در تعریف مسئله آمده است درباره هر نقطه (راه حل) از فضای جستجو ندارد. الگوریتم‌های جستجوی آگاهانه بر خلاف روش‌های جستجوی ناآگاهانه، با بهره‌مندی از یک تابع تخمینی،رویکرد هوشمندانه‌تری را برای کاوش فضای جستجو در پیش می‌گیرند ]۱۶[.
دو خانواده مهم الگوریتم‌های جستجوی آگاهانه شامل جستجوی اول‌بهترین* و جستجوی فرامکاشفه‌ای* است. جستجوی فرامکاشفه‌ای، الگوریتم جستجوی آگاهانه‌ای است که در آن‌ها از یک پدیده طبیعی، برای کاوش فضای جستجو، الهام گرفته می‌شود. برخی از الهام‌های طبیعی که بر اساس آن‌ها یک الگوریتم فرامکاشفه‌ای طراحی شده است عبارتند از: تکامل موجودات در طی نسل‌ها، فرایند سردشدن یا تبرید در فلزات، زندگی مورچه‌ها در یک کلونی، حرکت گروهی پرندگان و سیستم ایمنی در بدن انسان.
به طور خلاصه در مورد دسته‌بندی الگوریتم‌های جستجو، باید گفت که الگوریتم‌هایی که در دسته جستجوی آگاهانه قرار می‌گیرند، خود به دو دسته مکاشفه‌ای و فرامکاشفه‌ای قابل تفکیک هستند. الگوریتم‌های مکاشفه‌ای در یک فضای جستجوی منظم درختی سعی در یافتن جواب دارند و مهم‌ترین تفاوت آن‌ها با روش‌های جستجوی ناآگاهانه، در پیمایش هوشمندانه درخت جستجو است. الگوریتم‌های فراماکاشفه‌ای به عنوان به عنوان هوشمندانه‌ترین روش‌های جستجو به دو دسته زیستی و غیر زیستی تقسیم می‌شوند. روش‌های غیر زیستی به دو دسته مبتنی بر علم فیزیک (معمولا براساس یک قانون یا پدیده فیزیکی بنیان نهاده شده‌اند) و سایر فرامکاشفه‌های غیر زیستی قابل تفکیک هستند. الگوریتم‌های فرامکاشفه‌ای زیستی روش‌های احتمالی و با حافظه هستند که خود شامل دو دسته تکاملی و مبتنی بر هوش‌جمعی می‌باشند. الگوریتم‌های تکاملی به آن دسته از روش‌های جستجوی فرامکاشفه‌ای گفته می‌شود که مبتنی بر قانون بقاء اصلح نظریه تکاملی داروین هستند. از نقطه نظر انواع طبقه‌بندی روش‌های جستجوی فرامکاشفه‌ای این الگوریتم‌ها، جمعیتی (البته معمولا جمعیتی هستند)، زیستی، تکاملی، با حافظه و احتمالی می‌باشند. سیستم‌های مبتنی بر هوش‌جمعی به طور عمده از رفتار موجودات اجتماعی الهام می‌گیرند. در شکل ۴-۴ می‌توانید طبقه‌بندی الگوریتم‌های فرامکاشفه‌ای را مشاهده کنید.
شکل ۴-۴. طبقه‌بندی الگوریتم‌های فرامکاشفه‌ای ]۱۶[
۴-۲-۲: هوش‌جمعی
به طور کلی استفاده از روش‌های هوش‌جمعی یکی از موضوعات مورد تحقیق در سال‌های اخیر بوده است. تاکید اصلی در روش‌های مزبور طراحی یک سیستم هوشمند می‌باشد که از قابلیت‌های تطبیق‌شوندگی، توزیع شوندگی و انعطاف‌پذیری بالایی برخوردار بوده و همچنین توانایی بالایی را در حل مسائل مختلف دارا باشد. این سیستم‌ها که به سیستم‌های مبتنی بر هوش‌جمعی معروف هستند به طور عمده از رفتار موجودات اجتماعی الهام می‌گیرند. بدین صورت که با بررسی هوش‌جمعی و روش‌های ارتباطی که موجودات برای رسیدن به اهدافشان استفاده می‌کنند، که معمولا این روش‌ها به نظم خارق العاده و باورنکردنی نیز منجر می‌شود، سعی در شناخت مکانیزم‌های جستجو و ارتباطی آن‌ها می‌نمایند. پس از کشف این مدل، سعی می‌گردد مدلی ارائه شود که با پیروی از این رفتارها بتواند مسئله خاصی را حل کند ]۵۸[.
در اصطلاح، به گروه موجودات، جمعیت* گفته می‌شود. یک جمعیت را می‌توان گروهی از عامل‌های عموما متحرک که با یکدیگر از طریق فعالیت در محیط‌های محلی‌شان (به صورت مستقیم یا غیر مستقیم) ارتباط برقرار می‌کنند، تعریف کنیم ]۵۹[. هوش جمعیتی به رفتار حل مسئله‌ای گفته می‌شود که از تعامل چنین موجوداتی پدیدار می‌گردد و محاسبات هوش جمعیتی به همه مدل‌های الگوریتمی مبتنی بر چنین رفتاری گفته می‌شود. هوش جمعیتی به هوش‌جمعی* نیز معروف است.
مطالعات بر روی رفتار اجتماعی حیوانات و حشرات منجر به تولید تعدادی مدل‌های محاسباتی هوش‌جمعی شده است. موجوداتی که مدل‌های محاسباتی مبتنی بر هوش‌جمعی از آن‌ها الهام گرفته اند شامل مورچه‌ها، زنبورها، موریانه‌ها، عنکبوت‌ها، ماهی‌ها، دسته‌ه ای پرندگان و غیره هستند. در این جمعیت‌ها موجودات ساختارهای ساده‌ای دارند، اما رفتار جمعی آن‌ها معمولا بسیار پیچیده می‌باشد. رفتار پیچیده یک جمعیت در نتیجه الگوهای ارتباطی بین موجودات یک جمعیت در طول زمان است. این رفتار پیچیده ویژگی هیچ موجود به تنهایی نبوده و معمولا به آسانی از رفتار ساده موجودات قابل پیش‌بینی و نتیجه‌گیری نمی‌باشد ]۱۶.[
هوش‌جمعی به صورت غیر خطی از رفتار موجودات یک جمعیت پدیدار می‌گردد. یک اتصال محکم بین موجودات و رفتار اجتماعی وجود دارد: رفتار جمعی موجودات رفتار جمعیت را شکل می‌دهد و از طرف دیگر، رفتار جمعیت بر روی شرایطی که تحت آن هر موجود فعالیت خود را انجام می‌دهد تاثیر می‌گذارد. این فعالیت‌ها ممکن است محیط را تغییر دهد و بنابراین ممکن است رفتار موجودات و همسایگانشان تغییر کند، که دوباره ممکن است منجر به تغییر رفتار جمعی جمعیت شود. پس مهم‌ترین بخش هوش‌جمعی ، تعامل یا همکاری می‌باشد. تعامل بین موجودات به بهبود دانش تجربی درباره محیط کمک می‌کند ]۱۶[.
الگوریتم‌های جستجوی متنوع مبتنی بر هوش‌جمعی را می‌توان به دو دسته علامت محور و تقلید محور تقسیم کرد ]۱۶[. این دو روش در زیر تبیین شده‌اند:
روش‌های علامت محور: دسته‌ای از الگوریتم‌های مبتنی بر هوش‌جمعی ، از یک حافظه‌ی محیطی مشترک برای برقراری ارتباط غیر مستقیم میان موجودات بهره می‌برند. این حافظه محیطی، در الگوریتم‌های مبتنی بر رفتار مورچه‌ها، با ترشح و تبخیر فرومون مدیریت می‌شود. حافظه محیطی در الگوریتم‌های مبتنی بر رفتار زنبوران عسل، با توجه به رفتار رقص‌گونه زنبورها در هنگام یافتن مکان‌های غنی از گل‌های خوشبو مدل‌سازی می‌شود. در این تقسیم‌بندی الگوریتم‌هایی از این دست که ارتباط میان موجودات در آن‌ها به صورت غیرمستقیم بوده و فاقد هرگونه رفتار تقلیدگونه هستند، علامت محور نامیده می‌شوند. سر دسته الگوریتم‌های علامت محور، روش‌های جستجوی مبتنی بر رفتار مورچه‌ها در یک کلونی می‌باشد.
روش‌های تقلید محور: دسته‌ای از الگوریتم‌های مبتنی بر هوش‌جمعی، از یک مفهوم سرعت، اینرسی یا تمایل حرکتی در فرایند جستجوی خود بهره می‌برند. در این روش‌ها، ارتباط میان موجودات در جمعیت به صورت مستقیم می‌باشد و هیچ حافظه ی مشترکی وجود ندارد. در روش‌های مربوط به این دسته هر موجود یک حافظه دارد که در حافظه خود معمولا بهترین مکان یافت شده توسط خود (پاسخ برازنده محلی) و بهترین موجودات جمعیت (پاسخ برازنده سراسری) را نگهداری می‌کند. موجود مذکور، تمایلی را به سمت بهترین پاسخ‌های محلی و سراسری دارد. از آن‌جا که موجودات در این دسته از الگوریتم‌ها، تمایلی به سمت بهترین پاسخ‌های یافت‌شده توسط خودشان و دیگر موجودات دارند (رفتاری تقلیدگونه)، در این تقسیم‌بندی الگوریتم‌هایی که چنین ماهیتی دارند تقلید محور نامیده شده‌اند. تعداد روش‌های جستجوی فرامکاشفه‌ای مبتنی بر هوش‌جمعی و از نوع تقلید محور بسیار زیاد است (در مقایسه با نوع علامت محور). سر دسته الگوریتم‌های تقلید محور، روش فرامکاشفه‌ای بهینه‌سازی جمعیت ذرات است.
۴-۲-۳: الگوریتم بهینه‌سازی جمعیت ذرات
الگوریتم بهینه‌سازی جمعیت ذرات (PSO)، یک الگوریتم جستجوی مبتنی بر ذرات می‌باشد که رفتار اجتماعی دسته پرندگان را شبیه‌سازی می‌کند و اولین بار توسط کندی* و ابرهارت*در سال ۱۹۹۵ ارائه شده است ]۱۶ [. قصد اولیه در شبیه‌سازی رفتار پرندگان، شبیه‌سازی پرواز زیبا و غیرقابل پیش‌بینی دسته پرندگان بوده است. کشف الگوهایی که توانایی پرواز هماهنگ، تغییر مسیر ناگهانی و گروه‌بندی مجدد با بهینه‌ترین ترکیب را به پرندگان می‌دهد، هدف اصلی پژوهش بوده است؛ که در نهایت منجر به ایجاد الگوریتم بهینه‌سازی کارا و ساده PSO شده است.
در PSO، موجودات، ذره نامیده می‌شوند، که در فضای چند بعدی جستجو حرکت می‌کنند. تغییر در موقعیت ذرات در فضای جستجو مبتنی بر رفتار اجتماعی موجودات در تقلید از موقعیت سایر موجودات است. تغییرات یک ذره در جمعیت، تحت تاثیر سایر ذرات در جمعیت است (نوعی رفتار همکاری هم‌زیستی). با توجه به رفتار تقلیدگونه‌ای که هر ذره در مقابل یک یا چند ذره دیگر دارد، الگوریتم PSO یک روش تقلید محور محسوب می‌شود.
بهینه‌سازی جمعیت ذرات بیشتر برای مسائل بهینه‌سازی با پارامترهای پیوسته بکار رفته است. یکی از اولین کاربردهای این الگوریتم برای آموزش شبکه عصبی پیش‌رو ]۶۰,۶۱ [بوده است. این مطالعات نشان داد که کارایی بهینه‌سازی جمعیت ذرات برای آموزش شبکه‌های عصبی بسیار بالا می‌باشد. از آن پس، تحقیقات بیشماری برای بررسی توانایی بهینه‌سازی جمعیت ذرات به عنوان یک الگوریتم آموزشی برای معماری‌های مختلف شبکه‌های عصبی انجام پذیرفت. نتایج نشان داد که استفاده از PSO، منجر به افزایش دقت بدست آمده می‌شود. برخی از کاربردهای PSO عبارتند از: خوشه بندی ]۶۱ [، طراحی ]۶۵,۶۴,۶۳,۶۲ [، زمان بندی ]۶۸,۶۷,۶۶ [و داده کاوی ]۶۹ [.
موجودات در بهینه‌سازی جمعیت ذرات رفتار ساده‌ای را دنبال می‌کنند: تقلید از موفقیت موجودات همسایه و موفقیت خودشان. نتیجه چنین رفتاری یافتن نواحی بهینه در فضاهای جستجو با ابعاد بالا می‌باشد. یک الگوریتم PSO گروهی از ذرات را نگهداری می‌کند که هر ذره نمایش دهنده یک راه حل می‌باشد. در مقایسه با نمونه‌های محاسبات تکاملی، جمعیت معادل جمعیت و یک ذره معادل یک موجود می‌باشد. به اصطلاح ساده‌تر ذرات در فضای چندین بعدی جستجو حرکت می‌کنند و موقعیت آن‌ها مطابق با تجربیات خودشان و همسایگانشان تنظیم می‌شود.
فرض کنید که مشخص کننده موقعیت ذره i در فضای جستجو باشد؛ موقعیت ذره با اضافه کردن سرعت، به موقعیت کنونی تغییرمی‌کند. یعنی:
| (۴-۳) |
بردار سرعت، علاوه بر هدایت فرایند بهینه‌سازی، دانش تجربی ذره و نیز اطلاعات تغییرات ذرات همسایه را بازتاب می‌کند. دانش تجربی ذره، معمولا مؤلفه شناختی* نامیده می‌شود و متناسب با فاصله ذره از بهترین موقعیت خودش از ابتدای جستجو، می‌باشد. اطلاعات تغییرات اجتماعی به مؤلفه اجتماعی رابطه سرعت معروف است. معادله محاسبه سرعت نیز به صورت معادله (۴-۴) است:
| (۴-۴) |
در معادله بالا w وزن داخلی و و فاکتورهای یادگیری و ثابت هستند. در PSO استاندارد، مقدار w به طور خطی در کل فرایند اجرای رویه کاهش می‌یابد. و توابع توزیع نرمال هستند که می‌توانند اعداد تصادفی بین صفر و یک را تولید کنند. و نشان دهنده موقعیت جاری و بهترین تجربه ذره می‌باشند. بهترین تجربه همه ذرات در جمعیت با Gbesti نشان داده شده است.
رویه الگوریتم به صورت زیر شرح داده می‌شود:
مقدار دهی اولیه مکان و سرعت همه ذرات
تا زمانی که شرایط توقف (راه حل بهینه پیدا شده است یا بیشترین گام‌های حرکت حاصل شده است) رخ نداده است :
برای همه ذارت
مقدار Gbest و Pbest را بروزرسانی شده و ذرات بر طبق معادلات مکان و سرعتشان حرکت می‌کنند.
پایان
فصل پنجم
روش پیشنهادی برای پیش‌بینی سری‌های زمانی آشوبی
۵-۱: بیان مسئله
در این پژوهش تلاش نموده‌ایم تا دقت پیش‌بینی سری‌زمانی آشوب‌گونه را با ارائه روشی ترکیبی مبتنی بر هوش مصنوعی افزایش دهیم.
همان‌گونه در فصول گذشته به آن اشاره شد پیش‌بینی سری‌های زمانی آشوب‌گونه از پیچیدگی خاصی برخوردار است. این سیستم‌ها آنقدر پیچیده هستند که ممکن است در نگاه اول، یک فرایند تصادفی به نظر برسند، در صورتی که آن‌ها به طور کلی یک تابع ساده غیرخطی و معین هستند. همین طور اشاره شد که روش‌های هوش محاسباتی همچون شبکه‌های عصبی مصنوعی، هوش جمعیتی و … میتواند برای بدست آوردن پیش‌بینی دقیق‌تر، سری‌های زمانی آشوب‌گونه استفاده شوند.
هدف، بکارگیری ترکیبی از این روش‌هاست به‌طوری‌که بتوان به نتایج امیدوارکننده‌ای در پیش‌بینی سری‌های زمانی آشوب‌گونه، نسبت به روش‌های گذشته دست یافت. در روش‌های پیش‌بینی، تحلیل خطا کمتر مورد توجه بوده است. گفته شد که در برخی موارد، خطاهای پیش‌بینی به علت تصادفی بودن نیستند بلکه همبستگی بالای خطا‌ها را نشان می‌دهند و همچنین در مواردی خطا‌ها ویژگی‌های سیستم اصلی را به ارث می‌برند. در این پژوهش همراه با مدل پیش‌بینی از تحلیل خطا به منظور بهبود مدل بهره خواهیم گرفت.
۵-۲: مدل پیش‌بینی و تحلیل خطا
به طور کلی روش پیشنهادی شامل مراحل زیر است:
انتخاب سری زمانی و تشخیص آشوب
جاسازی سری زمانی در فضای حالت
