بسیاری اوقات آنچه که حل یک مسأله را از روش‌های قطعی بسیار مشکل می‌کند، این است که بیش از یک مورد تصمیم‌گیری وجود دارد، مانند موقعیت ماشین‌آلات و تخصیص کار، تخصیص بار به وسائل نقلیه و مسیریابی. هر یک از این موارد تصمیم‌گیری ممکن است به تنهایی پیچیده نباشند، اما در نظر گرفتن همه آنها در یک مدل به طور همزمان، چندان آسان نیست. روش ابتکاری تجزیه ^[۴۹] می‌تواند در چنین مسائلی مفید واقع شود. در این روش، جواب به دو یا چند بخش (که فرض می‌شود از هم مستقل هستند) تجزیه شده و هر یک جداگانه حل می‌شوند؛ سپس یک روش برای هماهنگ کردن و ترکیب این جواب‌های جزیی و به دست آوردن یک جواب خوب ابتکاری، به کار گرفته می‌شود.

۳-۵-۱-۳- تکرار
یکی از روش‌های تجزیه، تکرار ^[۵۰] است. در این روش، مسأله به زیرمسأله‌های جداگانه‌ای تبدیل می‌شود و در هر زمان یکی از زیرمسأله‌ها با ثابت در نظر گرفتن متغیرهای تصمیم موجود در سایر زیرمسأله‌ها در بهترین مقدار شناخته شده‌شان، بهینه می‌شود؛ سپس یکی دیگر از زیرمسأله‌ها در نظر گرفته می‌شود و این عمل به طور متناوب تا رسیدن به یک جواب رضایت‌بخش، ادامه می‌یابد.
۳-۵-۱-۴- روش تولید ستون^[۵۱]
این نیز یکی از روش‌های تجزیه است که عموماً برای مسائلی که دارای عناصر زیادی هستند (مانند مسأله کاهش ضایعات برش با تعداد الگوهای زیاد) کاربرد دارد. در این روش، حل مسأله به دو بخش تقسیم می‌شود:
یافتن ستون‌ها (یا عناصر) جواب (مثلاً در مسأله کاهش ضایعات برش و یافتن الگوهای برش).
یافتن ترکیب بهینه این عناصر، با توجه به محدودیت‌ها (در مسأله کاهش ضایعات برش و یافتن ترکیب مناسب الگوها). یکی از روش‌های معمول برای یافتن ستون‌ها، مقدار متغیرهای دوگانه مسأله اصلی است، اما هر روش دیگری نیز می‌تواند مورد استفاده قرار گیرد.
۳-۵-۱-۵- جستجوی سازنده ^[۵۲]
در این روش، با شروع از یک جواب تهی، تصمیم‌ها مرحله به مرحله گرفته می‌شود تا یک جواب کامل به دست آید. هر تصمیم، یک تصمیم آزمند است؛ یعنی قصد دارد با بهره گرفتن از اطلاعات به دست آمده از آنچه که تا کنون انجام شده است، بهترین تصمیم را بگیرد.
آنچه که یک الگوریتم سازنده و یک الگوریتم آزمند را از هم متمایز می‌کند، نحوه ساختن جواب‌ها می‌باشد. یک الگوریتم سازنده، جواب را به هر طریق ممکن تولید می‌کند، اما در یک الگوریتم آزمند، جواب مرحله به مرحله و با توجه به یافته‌ها، ساخته می‌شود (در هر مرحله، بخشی از جواب ساخته می‌شود). جستجوی سازنده در مسائلی مانند زمانبندی ماشین و بودجه‌بندی سرمایه کاربرد داشته است. در اینجا مثال مسیریابی کامیون مطرح می‌شود. در این مسأله کالا باید به نقاط مشخصی (هر یک با میزان مشخصی از تقاضا برای کالا) حمل شود؛ مسأله، سازماندهی این نقاط در مسیرهای مشخص با توجه به محدودیت ظرفیت کامیون است.
۳-۵-۱-۶- جستجوی بهبود یافته^[۵۳]
بر خلاف روش جستجوی سازنده، این روش با جواب‌های کامل کار می‌کند. جستجو با یک یا چند جواب (مجموعه‌ای از مقادیر متغیرهای تصمیم) شروع می‌شود و در هر مرحله، حرکت‌ها یا تغییرات مشخصی در مجموعه فعلی در نظر گرفته می‌شود و حرکت‌هایی که بیشترین بهبود را ایجاد می‌کنند، انجام می‌شود و عمل جستجو ادامه می‌یابد. یک مسأله در طراحی این روش، انتخاب جواب اولیه است. گاهی اوقات جواب اولیه یک جواب تصادفی است و گاهی نیز برای ساختن یک جواب اولیه، از روش‌هایی نظیر جستجوی سازنده استفاده می‌شود. مسأله دیگر، تعیین حرکت‌ها یا به عبارتی، تعریف همسایگی (مجموعه جواب‌هایی که با یک حرکت از جواب فعلی قابل دسترسی هستند) در مسأله است.
۳-۵-۱-۷- روش جستجوی همسایه ^[۵۴]
استفاده از الگوریتم مبتنی بر تکرار مستلزم وجود یک سازوکار تولید جواب است. سازوکار تولید جواب، برای هر جواب i یک همسایه به وجود می‌آورد که می‌توان از i به آن منتقل شد. الگوریتم‌های تکراری به عنوان جستجوی همسایه یا جستجوی محلی نیز شناخته می‌شوند. الگوریتم بدین صورت بیان می‌شود که از یک نقطه (جواب) شروع می‌شود و در هر تکرار، از نقطه جاری به یک نقطه همسایه جابه‌جایی صورت می‌گیرد. اگر جواب همسایه مقدار کمتری داشته باشد، جایگزین جواب جاری می‌شود (در مسأله حداقل‌سازی) و در غیر این صورت، نقطه همسایه دیگری انتخاب می‌شود. هنگامی که مقدار جواب از جواب تمام نقاط همسایه آن کمتر باشد، الگوریتم پایان می‌یابد.
مفهوم روش جستجوی همسایه از حدود چهل سال پیش مطرح شده است. از جمله اولین موارد آن، کارهای کرز می‌باشد که برای حل مسأله فروشنده دوره‌گرد از مفهوم جستجوی همسایه استفاده کرده است. در کارهای اخیر ریوز نیز جنبه‌هایی از این شیوه یافت می‌شود.
اشکالات الگوریتم فوق بدین شرح است:
ممکن است الگوریتم در یک بهینه محلی متوقف شود، اما مشخص نباشد که آیا جواب به دست آمده یک بهینه محلی است یا یک بهینه سراسری.
بهینه محلی به دست آمده به جواب اولیه وابسته است و در مورد چگونگی انتخاب جواب اولیه هیچ راه حلی در دسترسی نیست.
به طور معمول نمی‌توان یک حد بالا برای زمان اجرا تعیین کرد.
البته الگوریتم‌های مبتنی بر تکرار مزایایی نیز دارند؛ از جمله اینکه یافتن جواب اولیه، تعیین مقدار تابع و سازوکار تولید جواب همسایه به طور معمول ساده است.
با وجود آنکه تعیین حد بالای زمان اجرا امکان‌پذیر نیست، ولی با اطمینان می‌توان گفت که یک تکرار از الگوریتم در زمان مشخص قابل اجراست.
۳-۵-۲- روش‌های فرا ابتکاری ^[۵۵] برگرفته از طبیعت
در سال‌های اخیر یکی از مهمترین و امیدبخش‌ترین تحقیقات، «روش‌های ابتکاری برگرفته از طبیعت» بوده است؛ این روش‌ها شباهت‌هایی با سیستم‌های اجتماعی و یا طبیعی دارند. کاربرد ‌آنها برگرفته از روش‌های ابتکاری پیوسته می باشد که در حل مسائل مشکل ترکیبی نتایج بسیار خوبی داشته است.
در ابتدا با تعریفی از طبیعت و طبیعی بودن روش‌ها شروع می‌کنیم؛ روش‌ها برگرفته از فیزیک، زیست‌شناسی و جامعه‌شناسی هستند و به شکل زیر تشکیل شده‌اند:
استفاده از تعداد مشخصی از سعی‌ها و کوشش‌های تکراری
استفاده از یک یا چند عامل (نرون، خرده‌ریز، کروموزوم، مورچه و غیره)
عملیات (در حالت چند عاملی) با یک سازوکار همکاری ـ رقابت
ایجاد روش‌های خود تغییری و خود تبدیلی
طبیعت دارای دو تدبیر بزرگ می‌باشد:
انتخاب پاداش برای خصوصیات فردی قوی و جزا برای فرد ضعیف‌تر؛
جهش که معرفی اعضای تصادفی و امکان تولد فرد جدید را میسر می‌سازد.
به طور کلی دو وضعیت وجود دارد که در روش‌های ابتکاری برگرفته از طبیعت دیده می‌شود، یکی انتخاب و دیگری جهش. انتخاب ایده‌ای مبنا برای بهینه‌سازی و جهش ایده‌ای مبنا برای جستجوی پیوسته می‌باشد.
از خصوصیات روش‌های ابتکاری برگرفته از طبیعت، می‌توان به موارد زیر اشاره کرد:
پدیده‌ای حقیقی در طبیعت را مدل‌سازی می‌کنند.
بدون قطع می‌باشند.
اغلب بدون شرط ترکیبی همانند (عامل‌های متعدد) را معرفی می‌نمایند.
تطبیق‌پذیر هستند.
خصوصیات بالا باعث رفتاری معقول در جهت تأمین هوشمندی می‌شود. تعریف هوشمندی نیز عبارت است از قدرت حل مسائل مشکل؛ بنابراین هوشمندی به حل مناسب مسائل بهینه‌سازی ترکیبی منجر می‌شود.
۳-۶- جمع بندی
در این فصل به مباحث پیرامون بهینه سازی پرداخته شد. هدف از بهینه‌سازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت‌ها و نیازهای مسأله است. مسائل مختلف بهینه‌سازی به دو دسته مسائل بهینه‌سازی بی‌محدودیت و مسائل بهینه‌سازی با محدودیت تقسیم می شوند. روش های گوناگونی مانند روش شمارشی، روش محاسباتی، روش ابتکاری و روش فرا ابتکاری برای مسائل بهینه وجود دارد. یکی از مشکل ترین مسائل بهینه سازی، مسائل بهینه سازی ترکیبیاتی می باشد. مهمترین دلیل دشواری این گونه مسائل زمان بسیار زیاد حل این گونه مسائل به کمک روش های سنتی ریاضی است که عملا این کار را غیر ممکن می کند. بهترین گزینه برای حل اینگونه مسائل روش های ابتکاری و فرا ابتکاری می باشند. تفاوت این دو نوع روش در زمان حل و دقت در جزئیات مسائل می باشد. روش های ابتکاری دارای دقت زیاد تر در جزئیات هستند که طبیعتا زمان حل را نیز افزایش می دهد. روش های فرا ابتکاری نیز دارای مکانیزم حرکت تصادفی هدایت شده می باشند که اغلب آن ها از طبیعت الگو گرفته اند.
فصل چهارم
ارائه الگوریتم جدید پیشنهادی
۴-۱- مقدمه
هدف از بهینه‌سازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت‌ها و نیازهای مسأله است. از این رو بهینه‌سازی یک فعالیت مهم و تعیین‌کننده است. برای یک مسأله، ممکن است جواب‌های مختلفی موجود باشد که برای مقایسه آن ها و انتخاب جواب بهینه، تابعی به نام تابع هدف تعریف می‌شود. بسیاری از مسائل بهینه‌سازی، پیچیده‌تر و مشکل‌تر از آن هستند که بتوان آن ها را با روش‌های مرسوم بهینه‌سازی نظیر روش برنامه‌ریزی ریاضی و نظایر آن حل کرد. از جمله راه ‌حل‌های موجود در برخورد با این گونه مسائل، استفاده از الگوریتم‌های تکاملی است. این الگوریتم‌ها در زمان بسیار کوتاه تری نسبت روش های ریاضی، جواب مطلوب تری بدست می آورند.
۴-۲- الگوریتم جستجوگر تکاملی (Seeker Evolutionary Algorithm)
الگوریتم جستجوگر تکاملی الگوریتمی مبتنی بر یک منطق ساده جستجو است. فرض کنید تعدادی انسان می خواهند در منطقه ای به دنبال هدف خود بگردند. در واقع فضای جستجوی آن ها همان فضای موجه یک مساله بهینه سازی است. هدف آن ها نیز معادل هدف کمینه سازی یا بیشینه سازی در مسائل بهینه سازی است. بدترین حالت این است که هر یک از اعضای گروه به صورت نامنظم و انفرادی به جستجو به پردازند. نتیجه این نوع جستجو اتلاف زمان و در اکثر مواقع نیافتن حد مطلوبی از هدف خواهد بود. در نتیجه برای یک جستجوی هدفمند این نوع روش مناسب نخواهد بود. برای انجام یک جستجو بهینه و پرهیز از موازی کاری گروه جستجو به چند گروه تقسیم می شوند و ناحیه جستجو را به چند قسمت تقسیم می کنند و هر کدام از گروها به قسمتی می روند و به جستجو می پردازند. اگر به هدف مد نظرشون رسیده باشند عملیات جستجو به اتمام رسیده است در غیر این صورت بعد از جمع آوری و آنالیز اطلاعات بدست آمده، بهترین ناحیه شناسایی می شود. مسلما این ناحیه در مرحله قبل جستجو بهترین برازندگی را داشته است. در مرحله بعد تیم جستجو ناحیه برگزیده را به چند قسمت کوچکتر تقسیم می کند و هر گروه به قسمتی می رود و در آن جا به جستجو می پردازد. دوباره اگر تیم جستجو به هدف مد نظر خود رسیده باشد عملیات جستجو متوقف خواهد شد در غیر این صورت این روند تا برقراری شرط توقف ادامه پیدا می کند.
شرط توقف می تواند تحقق یک حدی از هدف یا زمان و یا نداشتن بهبود تکاملی قابل توجه در روند جستجو باشد. در واقع بعد از سپری شدن مدتی از زمان یا بدست آمدن مقدار مطلوب مورد نظر یا نداشتن بهبود هدف بدست آمده در چند مرحله پیاپی عملیات متوقف می شود.
می توان گفت که در تمام الگوریتم های فرا ابتکاری پیوسته نیز روند حرکت به همین شکل است. جواب ها به سمت منطقه ای که تا به حال برازندگی مطلوبی داشته اند حرکت می کنند. اما با این تفاوت که انجام حرکت به طور نامنظم و مبتنی بر یک پدیده در طبیعت و غیره انجام می گیرد.
روند الگوریتم تکاملی جستجوگر مبتنی بر همین شیوه جستجو منظم و هدفمند است. در این الگوریتم هر جواب یک عضو از گروه جستجو است. در هر مرحله هر جواب در قسمتی از فضای جستجو که برایش تعیین می شود به جستجو می پردازد. بعد از آنالیز اطلاعات بدست آمده از همه اعضای گروه جستجو، بهترین قسمت های ناحیه جستجو برای مرحله بعد تعیین می شود. در مرحله بعد قسمت های برگزیده به قسمت های کوچکتر تقسیم می شوند و گروه جستجو به جستجو در آن ها می پردازد. همین روند تا برقراری شرط توقف ادامه پیدا خواهد کرد. در صورت برقراری شرایط شروع مجدد الگوریتم به مرحله اول باز می گردد و در واقع عملیات جستجو دوباره از نو انجام می شود. این شرایط می تواند مشاهده نشدن بهبود قابل انتظار و یا رسیدن به تعداد خاصی از تکرار ها باشد. به طور مثال هر ۲۰ تکرار عملیات جستجو از دوباره انجام شود یا در صورتی که بهبود کمتر از ۰٫۰۰۰۱ بود این کار انجام شود. البته بهترین حالت برای شرط شروع مجدد می تواند نداشتن بهبود در نظر گرفته شده در مضرب های تعداد تکرار در نظر گرفته شده باشد.
در ادامه فلوچارت الگوریتم جستجوگر تکاملی آورده شده است.
ناحیه برگزیده : فضای جواب