الگوریتم های ترکیبی
بهینه سازی ترکیبی
الگوریتم های طبقه بندی شده
بهینه سازی کلنی زنبوری
الگوریتم بهینه سازی کلنی زنبور که ملهم شده توسط رفتار کلنی زنبور عسل در مجموعه های شهى می باشد.این دیدگاه ملهم شده بیولوزیکی اخیرا برای حل مسائل مستمر بهینه سازی ،شبکه های عصبی آموزشی ،
بهینه سازی اجزای طرح الکترونیکی ومکانیکی ،مسائل بهینه سازی ترکیبی مانند طراحی شغل مغازه ،مسئله
بهینه سازی سرویس دهی اینترنتی ،مسئله فروشندگان دوره گرد ،غیره مورد استفاده قرار می گیرد.
بهینه سازی کلنی زنبور در مسئله طراحی شغل مغازه داری
استراتزی موثر جستجو زنبور عسل می تواند در مسائل برنامه ریزی شغل مغازه داری مورد استفاده واقع شود.یک راه حل محتمل دردر مسئله برنامه ریزی شغل مغازه داری یک برنامه کامل از عملیات های اختصاص داده شده در مسئله می باشد.ما می توانیم به هر راه حل تحت عنوان یک راه از مرکز تجمع به منبع غذایی می باشد.شکل زیر چنین همانندی را شرح می دهد.
محدوده راه حل با سوددهی منبع غذا در زمینه فاصله وخوشمزه گی شهد قابل مقایسه است.از این رو، هر چقدر مدت زمان زمان تولید کوتاهتر باشد ،سوددهی راه حل بیشتر خواهد بود.ما بدین گونه کلنی از زنبورها را نگهداری می کنیم ،جایی که هر زنبور راه حل بالقوه ای را پیمایش می کند.هر بار که یک راه حل محتمل یافته می شود،هر زنبور برای اجرای رقص چرخشی به کندو باز می گردد.رقص چرخشی توسط لیستی از راه حل های Elite(Chong et al., 2006) ارایه می شود،از جایی که زنبورهای دیگر می توانند راه زنبور های دیگر را ادامه دهند.زنبورها ی با تولید بهتر دارای سوددهی بیشتری از افزودن راه خود به لیست الیت
خواهد داشت ،انحراف را به راه حل بهینه تغییر مسیر دادن.استفاده از طرح بالا استراتزی طبیعی سازمانی جستجوی زنبور عسل می تواند در مسئله طرح ریزی شغل مغازه د اری کاربرد داشته باشد.
الگوریتم چرخه یافتن فلوید
الگوریتم چرخه یافتن فلوید الگوریتمی است که می تواند چرخه را در مراحل قراردادی تعیین کند،حال در ساختارهای اطلاعات پایه یا تولید شده در پرواز(که به طور برجسته در برگیرنده آنهایی است که در شکل ها ومراحل عدد شبه تصادفی )در فضای 0(1) است .الگوریتم به نام Robert W. Floyd که آنرا در سال 1967 اختراع کرده است نام گذاری شده است.گاهی اوقات آنرا الگوریتم لاک پشت وخرگوش می نامند و نباید آنرا با الگوریتم راه های کوتاه فلوید-وارشال اشتباه گرفت .
متصور ساختن الگوریتم
بهترین راه برای متصور ساختن این الگوریتم ایجاد دیاگرامی از مرحله است که مانند لغت یونانی p
می باشد .مرحله در پایین دنباله آغاز می شود،و به سمت بالا ودر جهت غقربه های ساعت به دور حلقه
می گردد.با دنبال کردن الگوریتم ،دو مثال مرحله در a6 بعد از 6 بار تکرار همدیگر را قطع می کنند.
اگر الگوریتم ادامه پیدا کند ،مراحل دوباره همدیگر رابعد از 6 بار تکرار در المان مشابه قبلی قطع خواهند کرد. از آنجایی که طول چرخه در واقع 6 می باشد ،نتیجه مشابه دوباره حاصل می شود.
اجراء
اولین مرحله الگوریتم حداقل نیازمند بیشنیه (گاما ومیکرو)وحداکثر سنجش های(گاما +میکرو) برای یافتن تساوی می باشد.یافتن ابتدای چرخه نیازمند سنجش گاما ی دیگری می باشد.یافتن طول دقیق چرخه می تواند
با سنجش افزودنی میکرو انجام شود، از این رو می تواند با سنجه های کمتری با سودبردن از این واقعیت که m حاصلضربی از میکرو می باشد.
الگوریتم از انباری از 0(1) استفاده می کند.
متغیر ها
شاید معروفترین متغیر شناخته شده ی چرخه الگوریتم فلوید ،الگوریتم Pollard`s rho می باشد،یک الگوریتم فاکتور گیری عدد کامل که مراحل عدد شبه تصادفی را برای فاکتور گرفتن از اعداد کامل
استفاده می کند.همچنین الگوریتمی برای محاسبه لگاریتم های مجزا بر پایه ی الگوریتم چرخه فلوید می باشد.
مسئله بهینه سازی
در علوم کامپیوتر ،یک مسئله بهینه سازی ،مسئله یافتن بهترین راه حل ازبین راه حل های محتمل می باشد.
به طور رسمی ،یک مسئله بهینه سازی A چهارگانه (I,f,m,g) می باشد که:
I یک سری از مثال ها می باشد.
یک مثال ؟؟؟؟؟؟اریه شده است ،f(x) یک سری از راه حل های محتمل می باشد.
یک مثال x وراه حلی y ازx اریه میشود ،m(x,y) اندازه y را تعیین می کند ،که معمولا یک واقعیت مثبت است.
g تابع نهایی است، و ممکن است بیشینه یا کمینه باشد.
هدف یافتن راه حل بهینه برای نمونه x می باشد ،که یک راه حل محتمل y با ؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟می باشد.
برای هر مسئله بهینه سازی ،یک مسئله مشابه وجود دارد که می پرسد آیا راه حل محتملی برای برخی سنجه ی خاص m0 وجود دارد.برای مثال،یک گراف G داشته باشیم که دارای راس های u وv می باشد،
یک مسئله بهینه سازی ممکن است وجود داشته باشد که راهی از u بهv بیابد که کمترین لبه های برآمده را استفاده کند.این مسئله ممکن است پاسخ 4 داشته باشد.یک مسئله تصمیم گیری متشابه این است که"آیا راهی از u به v وجود دارد که از 10 تا ابه برآمده یا کمتر استفاده کند؟"این مسئله می تواند با یک بله یا خیر ساده پاسخ داده شود.
یک مسئله بهینه سازی NP دارای محدودیت های زیر می باشد:
I می تواند در زمان چند جمله ای شناسایی شود.
سایز یک راه حل محتمل به صورت چند جمله ای توسط سایز نمونه محدود شده است.
این مسئله بازگو می کند که مسئله متشابه تصمیم گیری در NP می باشد.از آنجایی که مسائل
بهینه سازی مورد نظر معمولا این محدودها را پوشش می دهد، "مسئله بهینه سازی"اغلب بی نام
با مسئله بهینه سازی NP مورد استفاده قرار می گیرد.
الگوریتم Steinhaus-Johnson-Trotter
الگوریتم Steinhaus-Johnson-Trotter یا الگوریتم Johnson-Trotter الگوریتمی
که تغییراتی را با المان های قابل انتقال می سازد.