نویسنده مطلب: مهندس عباس محمدی
همواره رفتار طبیعت برای بشر الهام بخش بوده است. وقتی که انسان تصمیم به پرواز کردن گرفت، مطالعه در احوال بالها و نحوه پرواز پرندگان، او را یاری رساند. نحوه تعلیق و حرکت بالهای پرندگان و حشرات در شرایط چالش برانگیز از جمله بادهای شدید، باعث شد که سیستم های کنترلی هواپیما با شناسایی میزان و جهت باد، بالها و شرایط خود را تطبیق دهد.
این الگوبرداری از طبیعت در همه رشته های علوم مهندسی، علوم پزشکی، علوم انسانی و هنر بسیار بارز است. واقعاً چگونه طبیعت توانسته است موجودات و پدیده هایی را اینگونه پرورش دهد؟
طبیعت، میلیاردها سال فرصت ایجاد، بازنگری و ویرایش در انواع گونه های موجودات، جهت تطبیق با خودش را داشته است. طبیعت اینقدر به اندازه کافی زمان در اختیار داشته است که توانسته برای مواجهه با هر چالشی یک راهکار ارائه دهد. این راهکارها همان راه حلهایی هستند که بشر برای حل بسیاری از مسائل مهندسی خود به آنها نیازمند است.
مهندسین علوم کامپیوتر، همواره در حال توسعه الگوریتم هایی هستند که بتوانند با صرف کمترین زمان و حافظه ممکن یک مسئله را حل نمایند. بسیاری از مسائل دنیای واقعی از جمله مسئله فروشنده دوره گرد (کاربرد: مسریابی در هاب سوئیچ و روترها) و مسئله کوله پشتی (کاربرد: تخصیص منابع با محدودیت‌های مالی و مسائل رمزنگاری) از جمله مواردی هستند که همواره حل آنها حتی برای کامپیوتر از منظر صرف زمان و حافظه بسیار پیچیده و بزرگ هستند. پیچیدگی مسئله با بزرگ شدن ابعاد و تعداد ورودی های آن به شدت بزرگ تر می شوند.
مثلاً اگر ۱۰۰ شهر داشته باشیم و بخواهیم کوتاهترین مسیر ممکن که همه شهرها را پوشش دهد و از هر شهر هم دقیقاً یکبار عبور کنیم و در نهایت به شهر اول بازگردیم، آنگاه چه تعداد راه حل (مسیر) را باید بررسی کنیم تا در نهایت به کوتاه ترین مسیر برسیم؟
سرراست‌ترین راه حل امتحان کردن تمامی جایگشتهای ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می‌شود (۱۰۰ فاکتوریل برابر با ۹ ضربدر ۱۰ به توان ۱۵۷ راه حل). تصورش هم بسیار وحشتناک است. محاسبه ۱۰۰ فاکتوریل خارج از قدرت محاسباتی معمولی کامیپوترها می باشد و هیچ متغیری توان ذخیره کردن چنین عدد بزرگی را ندارد.
اینگونه مسائل، تحت عنوان مسائل سخت (NP Hard) در علوم کامپیوتر شناخته می شوند. مسائل سخت مسائلی هستند تاکنون برای آنها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد.
اگرچه استفاده از روشهای برنامه نویسی پویا، حریصانه، برنامه نویسی خطی و انشعاب و تحدید از جمله روشهایی هستند که می توانند با پیچیدگی نمایی اینگونه مسائل را حل نمایند، ولی پیچیدگی نمایی فقط اندکی بهتر از پیچیدگی فاکتوریل است. پس چه باید کرد؟
جواب اینگونه مسائل هم در طبیعت نهفته است. در حدود سال ۱۸۶۰ یک نظریه از سوی آقای چارلز داروین، مسئله فرگشت جانداران (قانون انتخاب طبیعی) را به اثبات رسانید. قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می‌روند (تنازع بقا). مثلاً دایناسورها با وجود جثه عظیم و قوی‌تر بودن در طی روندی کاملاً طبیعی بازیِ بقاء و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها (برخی از پستانداران کوچک مثل موش) حیات خویش را ادامه دادند. ظاهراً طبیعت، مناسب ترین‌ها را انتخاب می‌کند نه بهترین‌ها را.
طبیعت قوانین ساده و قابل فهمی دارد. برای فهم این مسئله حالت فرگشت (تکامل) یک جانور را بررسی می کنیم. طبیعت در ابتدا یک گونه را به تعداد زیاد تولید می کند، در طی سالیان متمادی در اثر جفتگیری کروموزوم ها و جهش های ژنتیکی، فرزندانی پدید می آیند، اگر این فرزندان متولد شده با محیط سازگار باشند، ادامه نسل انجام خواهد شد در غیر اینصورت از بین می روند. آنچه که فرزندان متولد شده را برای بقا ارزیابی می کند، طبیعت و محیط زندگی آن جاندار است.
فرضیه فوق برای آقای جان هالند الهام بخش بود. اگر طبیعت می تواند جانداران را فرگشت-تکامل دهد، پس قطعاً مدلی از این فرضیه می تواند مسائل سخت و پیچیده را نیز حل نماید. این روش حل مسائل تحت عنوان الگوریتم ژنتیک معرفی گردید. این نوع الگوریتم در دسته الگوریتم های فرگشتی (Evolutionary algorithms) دسته بندی می شود.
اصولاً این دست مسائل جزو مسائل بهینه سازی طبقه بندی می شوند. مسائل بهینه سازی مسائلی هستند که یک پاسخ مشخص و دقیق ندارند و در ریاضیات و علوم رایانه یک مسئله بهینه‌سازی، مسئله یافتن بهترین راه حل از میان همه راه حلهای عملی می‌باشد.
برای حل مسئله فروشنده دوره گرد با ۱۰۰ شهر و یا بیشتر، توسط الگوریتم ژنتیک در مدت زمانی کوتاه (شاید حداکثرحدود ۱۰ دقیقه) می توان پاسخی قابل قبول، قابل اعتماد با فضای حافظه ای محدود دریافت کرد. چگونه؟
الگوریتم زیر تحت عنوان الگوریتم ژنتیک برگرفته از تولید مثل و تکامل در طبیعت است:
۱-راه حلهایی تصادفی ایجاد می کنیم.
(چندین «راه حل» یعنی چندین «مسیر» که از ۱۰۰ شهر می گذرد. خروجی این مرحله یک جمعیت اولیه از پاسخ هاست)
۲-این راه حل های اولیه توسط تابع ارزیابی، بررسی می شوند.
(هر یک از راه حل ها از نظر میزان هزینه که همان مسافت پیموده شده است، ارزیابی می شوند. خروجی این مرحله، یک جمعیت از پاسخهای ارزیابی شده است.)
۳-برخی از راه حلها برای تولید مثل انتخاب می شوند.
(در این مسئله هرچقدر عدد حاصل شده توسط تابع ارزیابی مقدار کوچکتری داشته باشد، طبق قانون بقاء اصلح داروین شانس بیشتری برای انتخاب شدن به عنوان والد را دارد. خروجی این مرحله یک جمعیت از والدین برازنده است)
۴-راه حلهای منتخب از مرحله قبل به عنوان والد با هم ترکیب (Crossover) می شوند.
(راه حلهای منتخب به عنوان کروموزوم باهم دوبه دو ترکیب می شوند، نتیجه حاصل از هر ترکیب، یک راه حل جدید است که ممکن است نتیجه بهتر یا بدتر داشته باشد. خروجی این مرحله جمعیتی از فرزندان تولید شده می باشد)
۵-برخی از راه حل های جدید (فرزندان تولید شده) دچار جهش (Mutation) می شوند.
(فرزندان جدید متولد شده، تحت عملیات جهش می توانند حالتی جدیدتر به خود بگیرند. ممکن است حالت جهش پاسخی بدتر یا بهتر را ایجاد نماید. خروجی ای مرحله جمعیتی از فرزندان جهش یافته است)
۶-محاسبه برازش جمعیت فرزندان صورت می گیرد.
(در این مرحله میزان شایستگی هر یک از فرزندان تولید شده که حاصل از عملیات ترکیب و جهش می باشند، بررسی می گردند. خروجی این مرحله جمعیت فرزندان ارزیابی شده است)
۷- از میان فرزندان تولید شده و والدین، شایسته ها انتخاب می شوند.
(در این قسمت با توجه به جمعیت والدین در قسمت ۳ و جمعیت فرزندان ارزیابی شده در قسمت ۶ یک لیست جدید از راه حلها شکل می گیرد. مطابق با میزان نیاز به تولید یک جمعیت، برای بررسی های مجدد، از این لیست راه حل انتخاب خواهیم کرد.)
۸- شرایط خاتمه الگوریتم بررسی می شود.
(در هربار اجرای الگوریتم بررسی خواهد شد که آیا شرایط خاتمه ارضاء شده است یا خیر؟ اگر خاتمه یافته باشد که راه حل انتخابی که بهترین در همان لیست مرحله ۷ باشد اعلام می گردد در غیر اینصورت برای تکرارهای بعدی به مرحله ۳ بازگشته و تا ارضاء شرایط خاتمه، کار انجام می پذیرد)
این روش که طی ۸ مرحله بیان شد، مدلی برگرفته از قانون بقاء اصلح برای حل مسائل با پیچیدگی بالا است. الکوریتم ژنتیک ساده ترین و قابل فهم ترین الگوریتم برگرفته از طبیعت است که معرفی آن موجب انقلابی در حل مسائل سخت و بهینه سازی گردید.
جالب است بدانید که اینگونه نیست که تصور کنید طبیعت فقط همین یک شیوه را برای حل مسائل پیچیده در خود نهفته دارد. برخی دیگر از الگوریتمهای بهینه سازی برگرفته از روشهای زیستی جانواران در دسته های جمعی (کلونی) خود می باشند. از جمله مهمترین و معروفترین این الگوریتم ها می توان به موارد زیر اشاره کرد:
الگوریتم پرندگان (ازدحام ذرات)
الگوریتم کلونی مورچگان
الگوریتم کلونی زنبور عسل
الگوریتم قورباغه جهنده
الگوریتم ازدحام گربه ها
الگوریتم پرنده فاخته
الگوریتم ازدحام ماهی ها
الگوریتم غذایابی باکتری ها
الگوریتم گله شیرها
الگوریتم گروه میگوها
برخی دیگر از الگوریتمهای بهینه سازی، برگرفته از رفتار پدیده ها فیزیکی، رفتار اجتماعی و سیاسی (روشهای غیرزیستی) می باشند. از جمله مهمترین و معروفترین این الگوریتم ها می توان به موارد زیر اشاره کرد:
الگوریتم شبیه سازی تبرید تدریجی
الگوریتم جستجوی گرانشی
الگوریتم جستجوی هارمونی
الگوریتم جستجوی ممنوعه
الگوریتم رقابت استعماری
تمام الگوریتم های بهینه سازی فوق الذکر که به نوعی برگرفته از طبیعت و جهان خلقت هستند تحت عنوان الگوریتم های فراابتکاری نامگذاری می گردند. علت این نامگذاری این است که الگوریتم با استفاده از یک تعداد راهکار ساده، با تولید تعداد زیادی پاسخ اولیه تصادفی در فضای مسئله (جستجوی موازی) و فرار از پاسخ های بهینه محلی، شانس بالایی در یافتن پاسخ بهینه سراسری دارند.
اینکه طبیعت بر اساس تطبیق پذیری پدیده ها با خودش عمل می کند و همواره در طول زمان سازگارترین ها (الزاماً نه شایسته ترین ها) را بر می گزیند، موجب شده که روشهای حل مسئله از حالت دقیق و کلاسیک به حالت هوشمند تصادفی هدایت شوند. الگوریتم‌هایی که ویژگی بارز آنها در عمل جستجو این است که از چندین نقطه (تولید پاسخها و جمعیت اولیه تصادفی) در فضای جواب، کار خود را آغاز می کنند و ادامه می دهند.
در واقع رفتار جمعی و گروهی اغلب جانداران همچون یک جستجوگر در فضای مسئله است که منجر به رسیدن به هدف و پاسخ می گردد. در واقع هر کدام از این جانداران در کلونی خود به عنوان یک نقطه آغازگر جستجو در فضای مسئله عمل می کند. این رفتار اجتماعی برخی از موجودات برای دانشمندان علوم مهندسی الهام بخش بوده است.
همچنین، روش غذایابی مورچه ها به شدت مورد توجه واقع شده بود و موجب ایجاد و معرفی یکی از قوی ترین الگوریتم های بهینه سازی به نام کلونی مورچگان (Ant Colony) شده است. این روش که از رفتار مورچه‌ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده، اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامه دکترایش مطرح شد.
در روش الگوریتم کلونی مورچگان، همواره مورچه ها مسیری را که کوتاه ترین مسافت به غذا باشد را در غالب یک تیم و با همکاری هم و با گذشت زمان پیدا می کنند. مورچه ها در طول مسیر حرکت خود، ماده ای شیمیایی به نام فرومون از خود ترشح می کنند. ماده فرمون با گذشت زمان تبخیر می شود. این ماده موجب ترغیب سایر مورچه ها به حرکت در این مسیر خواهد شد. با گذشت زمان مسیرهایی که طولانی تر هستند، بدلیل اینکه مقدار فرمون آنها بیشتر در معرض تبخیر شدن است، شانس کمتری برای انتخاب دارند و مسیرهایی که کوتاهترند، شانس انتخاب شدنشان بدلیل مقدار فرومون بیشتر بالاتر است.
نکته حائز اهمیت در این روشهای طبیعی که دو مورد آن ذکر شد، راه حلهای بهتر فقط شانس بیشتری برای انتخاب شدن دارند و نه شانس ۱۰۰ درصد، و حتی راه حلهای بدتر هم می توانند انتخاب شوند. این ویژگی ارزشمند باعث می گردد که شانس دوباره به راه حل های بد داده شود تا شاید در ادامه حل مسئله راه حلهای بهتری را ارائه کنند. (رفتار طبیعت هم اینگونه است).
برخی از الگوریتم ها مثل الگوریتم رقابت استعماری (Imperialistic Competition) برگرفته از رفتارهای اجتماعی، سیاسی و فرهنگی جوامع هستند. پایه‌های اصلی این الگوریتم را سیاست همسان سازی، رقابت استعماری و انقلاب تشکیل می‌دهد. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخشهایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه‌سازی کمک کنند. در واقع این الگوریتم جوابهای مسئله بهینه‌سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرایندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند. دکتر اسماعیل آتشپز گرگری، دانش آموخته کارشناسی ارشد مهندسی برق (کنترل) دانشگاه تهران و دانشجوی دکتری مهندسی برق دانشگاه تگزاس اِی اَند اِم، در دوران تحصیلات کارشناسی ارشد خود موفق به ارائه این الگوریتم جدید شده بود.
در همه الگوریتمهای فراابتکاری آنچه حائز اهمیت است، جستجوی فضای مسئله بصورت تصادفی و البته هوشمندانه است. ترکیب دو پارامتر تصادفی و هوشمندانه بودن، ایجاد چندین نقطه جستجوی در فضای مسئله و ارائه راهکارهای فرار از پاسخهای بهینه محلی، در واقع وجه تمایز و قدرت یک الگوریتم فراابتکاری نسبت به سایر الگوریتم های همتای خود محسوب می شود. این ویژگیهای ساده باعث کارآمدی این الگوریتم ها نسبت به الگوریتم های کلاسیک ریاضی شده اند.
تا پیش از ارائه الگوریتمهای فراابتکاری، آنچه که بهترین راه کار در حل این نوع مسائل بود، روش برنامه نویسی پویا و انشعاب-تحدید بود که در بهترین شرایط پیچیدگی نمایی داشت. اما بدلیل بررسی تمام پاسخ های ممکن، عملاً کاری از پیش نمی بردند و برای مسائل با ابعاد (شهرهای) زیاد، چند ماه و یا سال کامپیوتر زمان و میزان فوق العاده زیادی حافظه صرف می کرد.
برخی کاربردهای الگوریتم های فراابتکاری در مهندسی:
- برنامه ریزی دروس دانشگاهی
- آموزش شبکه عصبی برای الگو شناسی
- زمان بندی کارها برای ماشین‌های تولیدی
- دسته‌بندی اطلاعات
- بهینه‌سازی طراحی اجزای مکانیکی
- بهینه‌سازی چندهدفه
- تنظیم کردن پارامترهای کنترل‌کننده‌های منطق فازی