بخشی از مقاله
چکیده
موازیسازی الگوریتمهای اکتشافی برای حل مسائل بهینهسازی ترکیبیاتی یکی از زمینههای تحقیقاتی مورد علاقه پژوهشگران حوزه بهینهسازی است. هدف این مقاله تحلیل محاسباتی الگوریتم جستجوی ممنوعه موازی برای حل مساله مکانیابی تسهیلات ظرفیتدار تک-منبع است.
از آنجا که سرعت انجام محاسبات در اکثر مسائل کاربردی، عاملی تعیین کننده بشمار میآید، با استفاده از واسطهای برنامه نویسی موازی OpenMp و MPI، ایدههای موازیسازی یکسان روی الگوریتم جستجوی ممنوعه موازی به کار گرفته شد. نتایج عددی نشان دادهاند که علاوه بر سرعت اجرای بالا، هر دو مدل MPI و OpenMP جوابهای قابل قبولی از لحاظ انحراف معیار نسبت به جواب حالت سری نتیجه میدهند.
-1 مقدمه
مسائل مکانیابی تسهیلات، از مسائل مهم در بهینهسازی ترکیبیاتی هستند که از دهه شصت میلادی توجه بسیاری از پژوهشگران را به خود جلب نمودهاست. منظور از مکانیابی، فرمولبندی و حل مسائلی است که چگونگی مکانیابی یک مجموعه از تسهیلات را مورد بررسی قرار میدهد به طوریکه یک تابع هدف را تحت مجموعهای از محدودیتها بهینه نماید. شکل پرکاربردی از م ساله مکانیابی ت سهیلات، م ساله مکانیابی ت سهیلات ظرفیتدار تک- منبع 1 - SSCFL - نامیده میشود که درآن، تقاضاهای مشتریان تنها از طریق یکی از تسهیلات برآورده میشود.
تعلق مساله مکانیابی تسهیلات ظرفیتدار تک-منبع به کلاس مسائل سخت، و کارآمد نبودن روشهای حل دقیق برای مسائل بزرگ مقیاس، انگیزهای قوی برای روی آوردن محققان به استفاده از روشهای ابتکاری شده است 2] ، 3 ، 4، 6، .[8 در مرجع [7]، الگوریتمی مبتنی بر روش جستجوی ممنوعه تکراری ارائه شده است که در این پژوهش به تحلیل پیاده سازی موازی آن بر اساس با استفاده از رابط کاربری OpenMP و واسط انتقال پیام MPI میپردازیم
سازماندهی این مقاله به این صورت ا ست که، در بخش دوم فرمولبندی م ساله مکانیابی ت سهیلات ظرفیتدار تک منبع بیان می شود. در بخش سوم، ساختار کلی روش جستجوی ممنوعه و نحوه بکارگیری آن برای حل مساله مکانیابی تسهیلات ظرفیتدار تک منبع تشریح میشود. در بخش چهارم نحوه پیاده سازی موازی الگوریتم ج ستجوی ممنوعه بیان می شود. نهایتا در بخش پنجم، نتایج عددی حا صل از اعمال الگوریتمهای سری و موازی ارائه میشود.
-2 فرمولبندی مساله مکانیابی تسهیلات ظرفیتدار تک منبع
فرض کنید = {1,2, … , } مجموعهای از مکانهای بالقوه و = {1,2, … , } مجموعهای از مشتریان باشند. همچنین فرض کنید ظرفیت تسهیلات موجود در مکان i ام برابر bi و هزینه باز کردن یک تسهیلات در این مکان ثابت و برابر fi باشد. همچنین فرض کنید هر مشتری ∈ دارای تقاضای dj باشد و هزینه عرضه یک تسهیلات از یک مکان بالقوه ∈ برای برآورده کردن تقاضای مشتری برابر cij باشد. هدف از مساله مکانیابی تسهیلات ظرفیتدار تک منبع، این است که هر مشتری تنها از یک مکان تسهیلات دریافت کند طوری که برآورده نمودن تقاضای مشتریان با یک هزینه کمینه صورت پذیرد. به منظور فرمولبندی ریاضی مساله مکانیابی تسهیلات ظرفیتدار تک منبع، ابتدا، به ازای هر ∈ و ∈ ، متغیرهای تصمیم زیر را تعریف میکنیم:
در ادامه، برای اطمینان از این که به ازای هر مشتری ∈ دقیقا یک تسهیلات باز میشود، قید ∑ ∈ = 1 را درنظر میگیریم. محدودیت دیگری که باید در نظر بگیریم این است که مجموع تقاضاهای مشتریانی که توسط یک تسهیلات خاص سرویس داده میشوند، از ظرفیت آن تسهیلات بیشتر نباشد، لذا به ازای هر ∈ ، محدودیت ∑ ∈ ≤ را به مدل اعمال میکنیم. نهایتا با توجه به تعریف متغیرهای تصمیم، محدودیتهای ∈ {0,1} و ∈ {0,1} به مدل ریاضی مساله اضافه میشوند.
همانطور که قبلا ذکر شدهاست، هدف از مساله مکانیابی تسهیلات ظرفیتدار تک منبع، کمینهسازی مجموع هزینههای ثابت حاصل از باز کردن تسهیلات و هزینههای عرضه تسهیلات به مشتریان است.
با توجه به موارد ذکر شده، مدل ریاضی مساله مکانیابی تسهیلات ظرفیتدار تک منبع به صورت زیر بیان میشود:
-3 روش جستجوی ممنوعه - TS -
الگوریتم جستجوی ممنوعه تکراری حالتی خاص از الگوریتم جستجوی محلی تکراری است که در آن، فاز جستجوی محلی با یک جستجوی ممنوعه جایگزین می شود . الگوریتم ج ستجوی ممنوعه برای ر سیدن به جواب بهینه در یک م سئله بهینه سازی، شامل پنج ق سمت ا سا سی، -1 پیداکردن جواب اولیه، -2 حرکت ممنوعه، -3 ناموجه بودن جواب و توابع هزینه، -4 ساختارهای همسایگی و -5 وضعیتهای ممنوعه و معیار تنفس است. در ادامه به طور خلاصه به تشریح هرکدام از این قسمت ها میپردازیم.
1-3 پیداکردن جواب اولیه
پیدا کردن یک جواب اولیه در دو مرحله انجام میگیرد. در مرحله اول یک زیر مجموعه I باز میشود و در مرحله دوم مشتری به تسهیلات باز شده تخصیص داده میشود. به منظور تعیین این که کدام تسهیلات باید باز شود، در ابتدا تسهیلات به صورت صعودی بر اساس نسبت مرتب میشوند. با شروع از تسهیلاتی با کمترین ، به صورت حریصانه، به تعدادی از تسهیلات باز میشوند تا نیاز کل تقاضاها برآورده شود. به نزدیکترین تسهیلات باز
شده یک مشتری تخصیص داده میشود . این تخصیص میتواند سبب بروز نوساناتی در قیود ظرفیت تعدادی از تسهیلات شود و یا چند تسهیلات بتوان یافت که هیچ مشتری به آنها تخصیص داده نشد.
2-3 حرکت ممنوعه
جستجوی ممنوعه یک فرایند تکراری است که در هر تکرار آن، روند الگوریتم از جواب 's به بهترین جواب پیدا شده در همسایگی آن حرکت می کند. به منظور جلوگیری از دیدار مجدد یک جوابی که قبلا دیده شد و به منظور پرهیز از گیرافتادن در جواب بهینه محلی، تعداد خاصی از آخرین حرکتهای انجام شده قبل از تکرار فعلی الگوریتم، به عنوان حرکتهای ممنوعه در نظر گرفته میشوند. وضعیت ممنوعه برای یک حرکت خاص ممکن است با برقراری یک معیار تنفس لغو شود
3-3 ناموجه بودن جواب و توابع هزینه
الگوریتم جستجوی ممنوعه اجازه میدهد تا جوابها در طی جستجوی همسایه نشدنی شوند. یک جواب را نشدنی گویند هرگاه قیود ظرفیت تسهیلات را نقض کند. مجموع نقض قیود ظرفیت در جواب به صورت - ′ - = ∑ ∈ {0, ∑ ∈ − } محاسبه میشود. هر جواب با یک تابع هدف - ′ - = - ′ - + - ′ - ارزیابی میگردد که در آن، ضابطه تابع هدف - ′ - از جواب به صورت ∑ ∈ + ∑ ∈ در نظر گرفته میشود و پارامتری مثبت است که در هر تکرار الگوریتم اصلاح میشود. اگر جواب، شدنی باشد پارامتر بر - 1 + - تقسیم میشود و در غیر این صورت در - 1 + - ضرب میشود. پارامتری مثبت است .
4-3 ساختارهای همسایگی
همسایگی 1 - - برای جواب s، شامل همه جوابهایی است که میتوانند از s با مکانیابی مجدد مشتری j از تسهیلات فعلی k در تسهیلات l با شرط ≠ به دست آیند. تسهیلات l ممکن است باز یا بسته باشد. در صورتی که تسهیلات l بسته باشد، بعد از تخصیص j به l باز میشود. در مواردی که k دارای تنها یک مشتری تخصیص یافته به خود باشد، بعد از تخصیص j به l بسته میشود. این حرکت به صورت - , , - برچسبگذاری میشود. فرض کنید شماره تکرار فعلی و - , - شماره آخرین تکراری باشد که در آن، ممنوعیت گذر j از به l هنوز فعال باشد، در این صورت . - , - ≥ همسایگی 2 - - برای جواب s با تعویض مشتری 1 از تسهیلات k با مشتری 2 با شرط ≠ به دست آید. چنین حرکتی با برچسب - 1, 2, , - نشان داده میشود. در صورتی که - 1, - ≥ و - 2, - ≥ ، تبادل مشتری 1 از تسهیلات k با مشتری 2 ممنوع میباشد
5-3 وضعیتهای ممنوعه و معیار تنفس
وقتی که یک حرکت ممنوعه ثبت شده باشد، به تعداد = 7 + - ⁄ - تکرار ممنوعه باقی میماند. پارامتر ، تعداد دفعاتی است که حرکتی از جواب s به جواب ساخته شده است. مقدار بیشینه برای همه حرکات ساخته شده میباشد. هدف از ثبت حرکات ممنوعه، جلوگیری از جستجوی جوابهایی است که قبلا دیده شده اند. با این حال این قانون محکم نیست، یعنی با برقراری یک معیار تنفس قابل لغو شدن است. فرض کنید ̌ و ̃ به ترتیب، بهترین جواب شدنی و بهترین جواب - شدنی یا نشدنی - شناخته شدهای باشند که در جستجوی ممنوعه فعلی مشخص شدهاند. در این صورت دو معیار تنفس 1 و 2 مورد استفاده قرار میگیرند که اولی مقدار ارزیابی ̌ و دومی مقدار ارزیابی است. این ارزیابیها با استفاده از تابع - - . انجام میگیرد که در زیربخشهای قبلی معرفی شده است
