1-1- مقدمه
در ریاضیات و علوم رایانه یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. روش های حل متفاوتی برای این گونه مسائل وجود دارند که به سه دسته روش های سنتی ریاضی، روش های ابتکاری و روش های فرا ابتکاری تقسیم می شوند. در اکثر مسائل بهینه سازی با افزایش ابعاد مساله زمان حل آن نیز به صورت نمایی افزایش پیدا می کند. به این گونه مسائل، مسائل بهینه سازی ترکیبیاتی گفته می شود. به همین علت یکی از بهترین گزینه های برای حل مسائل بهینه سازی استفاده از الگوریتم های فرا ابتکاری است. مهمترین علت استفاده از الگوریتم های فرا ابتکاری، بدست آوردن یک جواب مناسب در زمان مناسب است. از همین رو است که توسعه و میزان استفاده از الگوریتم های فرا ابتکاری به شدت رشد داشته است.
1-2- تعریف مساله
هدف از بهینه‌سازی یافتن بهترین جواب قابل قبول با توجه به محدودیت‌ها و نیازهای مسأله است. بهینه‌سازی یک فعالیت مهم و تعیین‌کننده در بسیاری ار زمینه های علمی، اقتصادی، صنعتی و غیره است. بسیاری از مسائل بهینه‌سازی در مهندسی، طبیعتاً پیچیده‌تر و مشکل‌تر از آن هستند که با روش‌های مرسوم بهینه سازی نظیر روش های برنامه‌ریزی ریاضی و نظایر آن قابل حل باشند. از جمله راه حل‌های موجود در برخورد با این گونه مسائل، استفاده از الگوریتم‌های تکاملی است. دلیل دیگر استفاده از الگوریتم های تکاملی، زمان بسیار زیاد و غیر ممکن روش های دقیق ریاضی برای حل مسائلی با پارامتر های زیاد و پیچیده است. در سالهای اخیر یکی از مهمترین و امیدبخش‌ترین تحقیقات، «روش‌های ابتکاری برگرفته از طبیعت» بوده است. این روش‌ها شباهت‌هایی با سیستم‌های اجتماعی و یا طبیعی دارند. ساختار آنها برگرفته شده از روند تکاملی موجود در آن سیستم می باشد که در حل مسائل با ساختار پیچیده نتایج بسیار خوبی داشته است. در اکثر این گونه الگوریتم ها عملیات جستجو با تولید یک جمعیت تصادفی در ناحیه جستجو شروع می شود. سپس با استفاده هوش محاسباتی موجود در الگوریتم، جواب ها حرکت داده می شوند. این جابجایی به نحوی می باشد که بعد از گذشتن چند گام جمعیت به سمت نقطه بهینه همگرا می شوند. تفاوت اصلی الگوریتم های تکاملی در همین نحوه جابجایی جمعیت می باشد. در سال های اخیر توسعه و استفاده از الگوریتم های تکاملی رشد چشم گیری داشته است. هر یک از آن ها دارای نقاط ضعف و قوتی بوده است به طوری که هر از چند گاهی شاهد معرفی الگوریتمی جدید هستیم که برتری خود را نسبت به تعدادی از الگوریتم های قبلی نشان می دهد.
در این پایاننامه، یک الگوریتم جدید برای حل مسائل بهینه سازی پیوسته معرفی شده است. این الگوریتم مبتنی بر یک منطق ساده جستجو است. برای ارزیابی عملکرد الگوریتم های فرا ابتکاری از مسائل ریاضی موجود در ادبیات استفاده می شود. برای این الگویتم نیز از 11 مساله ریاضی برای مقایسه و ارزیابی عملکرد الگوریتم پیشنهادی استفاده شده است. در این مقایسات نتایج الگوریتم پیشنهادی با نتایج یازده الگوریتم فرا ابتکاری مقایسه شده است. این الگوریتم ها جزء پر رجوع ترین الگوریتم های فرا ابتکاری در این زمینه هستند.
1-3- هدف تحقیق
هدف از این پایان نامه معرفی یک الگوریتم فراابتکاری کارا برای حل مسائل بهینه سازی پیوسته است که بتواند نسبت به اغلب الگوریتم های فراابتکاری مشهور دارای برتری باشد.
1-4- فرضیات تحقیق
در این پایان نامه، فرضیات مسأله وجود ندارد و طراحی الگوریتم تکاملی جستجوگر فقط برای مسائل بهینه سازی پیوسته صورت میگیرد.
1-5- اهمیت و ضرورت تحقیق
گستره استفاده از الگوریتم های فراابتکاری در علوم مختلف به خصوص مهندسی صنایع در طی سال های گذشته بسیار زیاد بوده است. تعداد ارجاعات به مقالات اصلی این الگوریتم ها خود گواه این امر است. در ادامه به تعدادی از این موارد اشاره می شود.
الگوریتم تجمعی ذرات (1995) – 19927 ارجاع
الگوریتم هارمونی (2001) – 866 ارجاع
الگوریتم زنبور عسل (2007) – 590 ارجاع
الگوریتم فرهنگ (1994) – 517 ارجاع
الگوریتم رقابت استعماری (2007) – 195 ارجاع
الگوریتم گرانشی (2009) – 188 ارجاع
تعداد ارجاعات بسیار زیاد به مقالات الگوریتم های فراابتکاری نشان دهنده اهمیت فراوان این روش ها است. روش حل یا پدیده علمی که وسعت استفاده از آنها به این شکل باشد بسیار اندک است.
1-6- خلاصه فصل های آتی
در فصل دوم به مرور ادبیات الگوریتم های فرا ابتکاری پرداخته خواهد شد. الگوریتم هایی که در این فصل مرور می شود شامل الگوریتم ژنتیک، الگوریتم آنیلینگ شبیه‌سازی، الگوریتم ایمنی مصنوعی، الگوریتم جستجوی ممنوعه، الگوریتم بهینه‌سازی کلونی مورچه، الگوریتم اجتماع ذرات، تکامل تفاضلی، الگوریتم جستجوی هارمونی، جستجوی فاخته، الگوریتم دسته‌ی ماهی‌های مصنوعی، الگوریتم کرم شب تاب، الگوریتم خفاش، الگوریتم جستجوی گرانشی، الگوریتم کلونی زنبور عسل، الگوریتم رقابت استعماری، الگوریتم بهینه سازی فاخته است.
در فصل سوم به زمینه های علمی تحقیق پرداخته می شود. در این فصل روش های مختلف جستجو و بهینه سازی مورد بحث قرار می گیرد. مسائل بهینه سازی ترکیبیاتی و روش های حل آن شرح داده می شود.
در فصل چهارم ساختار الگوریتم جستجوگر تکاملی شرح داده خواهد شد و سپس ب
ا استفاده از چندین مساله ریاضی عملکرد آن با معروف ترین الگوریتم های فرا ابتکاری مورد مقایسه قرار خواهد گرفت.
فصل پنجم مربوط به نتیجه گیری و پیشنهادات آتی تحقیق خواهد بود.
فصل دوم
ادبیات و پیشینه تحقیق
2-1- مقدمه
در سالهای دهه 1950 برنامه نویسی کامپیوترهای اولیه توسط تغییر سیم ها و تنظیم هزاران کلید و سوییچ انجام می شد. بعد از آن افراد به دنبال ابزارهای سریع تر و راحت تری برای برنامه نویسی بودند. در اواخر دهه 1950 مفسرهای زبان های طبیعی و کامپایلرهای پا به عرصه ظهور گذاشتند. در این سال ها بود که زبان های برنامه نویسی به منظور استفاده در دنیای نرم افزارهای تجاری عرضه شدند. این امر باعث شد تا آشنایی با زبان های برنامه نویسی به صورت عام در بین متخصصان رواج پیدا کند. بعد از این رویداد مهم اکثر دانشمندان در زمینه های مختلف علمی سعی کردند از زبان برنامه نویسی استفاده کنند. یکی از موارد استفاده از زبان های برنامه نویسی، علم ریاضی و انجام محاسبات ریاضی بود. زمان حل بسیار کمتر این روش نسبت به حل دستی باعث شد تا سرعت استفاده از برنامه نویسی در شاخه های مختلف ریاضی یه شدت رشد کند. در دهه 1970 برای اولین بار دانشمندان برای حل مسائل بهینه سازی ترکیبیاتی از الگوریتم های فرا ابتکاری استفاده کردند. آن ها برای پیاده سازی الگوریتم ها از زبان برنامه نویسی استفاده کردند. نتیجه این کار بدست آمدن جواب های مناسب در زمان مناسب برای مسائل بهینه سازی ترکیبیاتی با اندازه بزرگ بود. تا آن زمان برای این گونه مسائل به دلیل زمان حل بسیار زیاد جواب مناسبی یافت نشده بود.
2-2- مرور ادبیات الگوریتم های فرا ابتکاری
در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند1 ایده استفاده از الگوریتم ژنتیک 2را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک های زیست‌شناسی فراگشتی مانند وراثت و جهش استفاده می‌کند. در واقع الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می کنند. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. در طبیعت، فرایند تکامل هنگامی ایجاد می‌شود که چهار شرط زیر برقرار باشد:
الف) یک موجود توانایی تکثیر داشته باشد (قابلیت تولید مثل).
ب) جمعیتی از این موجودات قابل تکثیر وجود داشته باشد.
پ) چنین وضعیتی دارای تنوع باشد.
ت) این موجودات به وسیله قابلیت‌هایی در زندگی از هم جدا شوند.
در طبیعت، گونه‌های متفاوتی از یک موجود وجود دارند که این تفاوت‌ها در کروموزوم‌های این موجودات ظاهر می‌شود و باعث تنوع در ساختار و رفتار این موجودات می‌شود.
این تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثیر می‌گذارد. موجوداتی که قابلیت‌ها و توانایی بیشتری برای انجام فعالیت‌ها در محیط دارند (موجودات متکامل‌تر)، دارای نرخ زاد و ولد بالاتری خواهند بود و طبعاً موجوداتی که سازگاری کمتری با محیط دارند، از نرخ زاد و ولد پایین‌تری برخوردار خواهند بود. بعد از چند دوره زمانی و گذشت چند نسل، جمعیت تمایل دارد که موجوداتی را بیشتر در خود داشته باشد که کروموزوم‌هایشان با محیط اطراف سازگاری بیشتری دارد. در طی زمان، ساختار افراد جامعه به علت انتخاب طبیعی تغییر می‌کند و این نشانه تکامل جمعیت است [1,2,3] .
الگوریتم آنیلینگ شبیه‌سازی3 شده توسط متروپولیس4 و همکاران در سال 1953 پیشنهاد شده و جهت بهینه‌سازی در سال 1983 مورد بازبینی قرار گرفته است. این روش در مسائل تاکسی تلفنی کاربرد دارد.
الگوریتم آنیلینگ شبیه‌سازی شده در شکل عمومی، بر اساس شباهت میان سرد شدن جامدات مذاب و حل مسائل بهینه‌سازی ترکیبی به وجود آمده است. در فیزیک مواد فشرده، گرم و سرد کردن فرایندی است فیزیکی که طی آن یک ماده جامد در ظرفی حرارت داده می‌شود تا مایع شود؛ سپس حرارت آن بتدریج کاهش می‌یابد. بدین ترتیب تمام ذرات فرصت می‌یابند تا خود را در پایین‌ترین سطح انرژی منظم کنند. چنین وضعی در شرایطی ایجاد می‌شود که گرمادهی کافی بوده و سرد کردن نیز به آهستگی صورت گیرد. جواب حاصل از الگوریتم گرم و سرد کردن شبیه‌سازی شده، به جواب اولیه وابسته نیست و می‌توان توسط آن جوابی نزدیک به جواب بهینه به دست آورد. حد بالایی زمان اجرای الگوریتم نیز قابل تعیین است. بنابراین الگوریتم گرم و سرد کردن شبیه‌سازی شده، الگوریتمی است تکراری که اشکالات روش‌های عمومی مبتنی بر تکرار را ندارد.
در روش آنیلینگ شبیه‌سازی شده، به صورت پی در پی از جواب جاری به یکی از همسایه‌های آن انتقال صورت میگیرد. این سازوکار توسط زنجیره مارکوف به صورت ریاضی قابل توصیف است. در این روش، یک مجموعه آزمون انجام میگیرد؛ این آزمون‌ها به نحوی است که نتیجه هر یک به نتیجه آزمون قبل وابسته است. در روش آنیلینگ شبیه‌سازی شده، منظور از یک آزمون، انتقال به نقطه جدید است و روشن است که نتیجه انتقال به نقطه جدید تنها وابسته به مشخصات جواب جاری است.
روش جستجوی همسایه و روش آنیلینگ شبیه
سازی شده، هر دو روش‌های تکراری هستند. در الگوریتم آنیلینگ شبیه‌سازی شده، هر بار که شاخص کنترل‌کننده به مقدار نهایی خود می‌رسد، در حقیقت یک عملیات تکراری انجام شده است. در الگوریتم جستجوی همسایه، هنگامی که تعداد تکرارها به سمت بی‌نهایت میل می‌کند، روش به جواب بهینه نزدیک می‌شود. اما عملکرد الگوریتم آنیلینگ شبیه‌سازی شده سریع‌تر است [4] .
دیکاستر5و و تیمیس6، اولین الگوریتم های ایمنی مصنوعی 7را در سال 1986 طراحی کردند. به طور کلی، سیستم‌های ایمنی مصنوعی جزء الگوریتم های الهام گرفته شده از بیولوژی هستند. این نوع الگوریتم‌ها، الگوریتم هایی کامپیوتری هستند که اصول و ویژگی‌های آنها نتیجه بررسی در خواص وفقی و مقاومت نمونه‌ها بیولوژیکی است. سیستم ایمنی مصنوعی نوعی الگو برای یادگیری ماشین است. یادگیری ماشین، توانایی کامپیوتر برای انجام یک کار با یادگیری داده‌ها یا از روی تجربه است. سیستم ایمنی مصنوعی توسط کاسترو به این صورت تعریف شده است:
سیستم های وفقی که با الهام از ایمونولوژی نظری و توابع، اصول و مدل های ایمنی سیستم بدن انسان مشاهده شده به وجود آمده‌اند و برای حل مسائل مورد استفاده قرار می‌گیرند [5] .
الگوریتم جستجوی ممنوعه8 برای اولین بار در سال 1986 توسط گلووِر9 معرفی شد. روش جستجوی ممنوع همانند روش آنیلینگ شبیه‌سازی شده بر اساس جستجوی همسایه بنا شده است. در این روش عملکرد حافظه انسان شبیه‌سازی شده است. حافظه انسان با به کارگیری ساختمانی مؤثر و در عین حال ساده از اطلاعات، آنچه را در قبل رؤیت شده، ذخیره می‌کند. این مرکز همچنین فهرستی از حرکات منع شده را تنظیم می‌کند و این فهرست همواره بر اساس آخرین جستجوها منظم می‌شود. این روش از انجام هر گونه عملیات مجدد و تکراری جلوگیری می‌کند.
شکل نوین جستجوی ممنوع توسط گلوور مطرح شده است. روش جستجوی مبتنی بر منع، با ایجاد تغییری کوچک در روش جستجوی همسایه به وجود می‌آید. هدف این روش آن است که بخش‌هایی از مجموعه جواب که پیش از این بررسی نشده است، مد نظر قرار گیرد. بدین منظور حرکت به جواب‌هایی که اخیراً جستجو شده، ممنوع خواهد بود.
ساختار کلی روش جستجوی ممنوع بدین صورت است که ابتدا یک جواب اولیه امکان‌پذیر انتخاب می‌شود؛ سپس برای جواب مربوط، بر اساس یک معیار خاص مجموعه‌ای از جواب‌های همسایه امکان‌پذیر در نظر گرفته می‌شود.
در گام بعد، پس از ارزیابی جواب‌های همسایه تعیین شده، بهترین آنها انتخاب می‌شود و جابه‌جایی از جواب جاری به جواب همسایه انتخابی صورت میگیرد. این فرایند به همین ترتیب تکرار می‌شود تا زمانی که شرط خاتمه تحقق یابد.
در روش جستجوی ممنوع، فهرستی وجود دارد که جابه‌جایی‌های منع شده را نگهداری می‌کند و به فهرست تابو معروف است و کاربرد اصلی آن، پرهیز از همگرا شدن به جواب‌های بهینه محلی است. به عبارت دیگر، به کمک فهرست تابو جابه‌جایی به جواب‌هایی که اخیراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هایی از مجموعه جواب که پیش از این مورد بررسی قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جایی از جواب جاری به جواب همسایه امکان‌پذیر زمانی انجام می‌شود که در فهرست تابو قرار نداشته باشد. در غیر این صورت، جواب همسایه دیگری که در ارزیابی جواب‌های همسایه در رده بعدی قرار گرفته است، انتخاب شده و جابه‌جایی به آن صورت میگیرد.
در روش جستجوی ممنوع بعد از هر جابه‌جایی، فهرست تابو بهنگام می‌شود، به نحوی که جابه‌جایی جدید به آن فهرست اضافه شده و جابه‌جایی که تا n تکرار مشخص در فهرست بوده است، از آن