بخشی از مقاله
چکیده
موازیسازی الگوریتمهای اکتشافی برای حل مسائل بهینهسازی ترکیبیاتی یکی از زمینههای تحقیقاتی مورد علاقه پژوهشگران حوزه بهینهسازی است. هدف این مقاله تحلیل محاسباتی الگوریتم تبرید شبیهسازیشده موازی برای حل مساله مکانیابی تسهیلات ظرفیتدار تک-منبع است. از آنجا که سرعت انجام محاسبات در اکثر مسائل کاربردی، عاملی تعیین کننده بشمار میآید، با استفاده از واسطهای برنامه نویسی موازی OpenMp و MPI، ایدههای موازیسازی یکسان روی الگوریتم تبرید شبیهسازیشده موازی به کار گرفته شد. نتایج عددی نشان دادهاند که علاوه بر سرعت اجرای بالا، هر دو مدل MPI و OpenMP جوابهای قابل قبولی از لحاظ انحراف معیار نسبت به جواب حالت سری نتیجه میدهند.
-1 مقدمه
م ساله مکانیابی ت سهیلات، یکی از م سائل مهم در بهینه سازی ترکیبیاتی ا ست که از دهه ش صت میلادی توجه ب سیاری از پژوه شگران را به خود جلب نمودهاست. منظور از مکانیابی، فرمولبندی و حل مسائلی است که چگونگی مکانیابی یک مجموعه از تسهیلات را مورد بررسی قرار میدهد به طوریکه یک تابع هدف را تحت مجموعهای از محدودیتها بهینه نماید. شکل پرکاربردی از م ساله مکانیابی ت سهیلات، م ساله مکانیابی ت سهیلات ظرفیتدار تک- منبع 1 - SSCFL - نامیده میشود که درآن تقاضاهای مشتریان تنها از طریق یکی از تسهیلات برآورده میشود.
تعلق مساله مکانیابی تسهیلات ظرفیتدار تک-منبع به کلاس مسائل سخت، و کارآمد نبودن روشهای حل دقیق برای مسائل بزرگ مقیاس، انگیزهای قوی برای روی آوردن محققان به استفاده از روشهای ابتکاری شده است 5]، 6، 7، 8، .[10 در مرجع [8]، الگوریتمی مبتنی بر روش تبرید شبیه سازی شده ارائه شده ا ست که در این پژوهش به تحلیل پیاده سازی موازی آن بر ا ساس با ا ستفاده از رابط کاربری OpenMP و وا سط انتقال پیام MPI میپردازیم 4]، .[6
سازماندهی این مقاله به این صورت ا ست که، در بخش دوم فرمولبندی م ساله مکانیابی ت سهیلات ظرفیتدار تک منبع بیان می شود. در بخش سوم، ساختار کلی روش تبرید شبیه سازی شده و نحوه بکارگیری آن برای حل م ساله مکانیابی ت سهیلات ظرفیتدار تک منبع ت شریح می شود. در بخش چهارم نحوه پیاده سازی موازی روش تبرید شبیه سازی شده بیان می شود. نهایتا در بخش پنجم، نتایج عددی حا صل از اعمال الگوریتمهای سری و موازی ارائه میشود.
-2 فرمولبندی مساله مکانیابی تسهیلات ظرفیتدار تک منبع
فرض کنید = {1,2, … , } مجموعهای از مکانهای بالقوه و = {1,2, … , } مجموعهای از مشتریان باشند. همچنین فرض کنید ظرفیت تسهیلات موجود در مکان i ام برابر bi و هزینه باز کردن یک تسهیلات در این مکان ثابت و برابر fi باشد. همچنین فرض کنید هر مشتری ∈ دارای تقاضای dj باشد و هزینه عرضه یک تسهیلات از یک مکان بالقوه ∈ برای برآورده کردن تقاضای مشتری برابر cij باشد. هدف از مساله مکانیابی تسهیلات ظرفیتدار تک منبع، این است که هر مشتری تنها از یک مکان تسهیلات دریافت کند طوری که برآورده نمودن تقاضای مشتریان با یک هزینه کمینه صورت پذیرد.
در ادامه، برای اطمینان از این که به ازای هر مشتری ∈ دقیقا یک تسهیلات باز میشود، قید ∑ ∈ = 1 را درنظر میگیریم. محدودیت دیگری که باید در نظر بگیریم این است که مجموع تقاضاهای مشتریانی که توسط یک تسهیلات خاص سرویس داده میشوند، از ظرفیت آن تسهیلات بیشتر نباشد، لذا به ازای هر ∈ ، محدودیت ∑ ∈ ≤ را به مدل اعمال میکنیم. نهایتا با توجه به تعریف متغیرهای تصمیم، محدودیتهای ∈ {0,1} و ∈ {0,1} به مدل ریاضی مساله اضافه میشوند. همانطور که قبلا ذکر شدهاست، هدف از مساله مکانیابی تسهیلات ظرفیتدار تک منبع، کمینهسازی مجموع هزینههای ثابت حاصل از باز کردن تسهیلات و هزینههای عرضه تسهیلات به مشتریان است. بدین منظور تابع هدف مدل به صورت ∑ ∈ ∑ ∈ + ∑ ∈ تعریف میشود. با توجه به موارد ذکر شده، مدل ریاضی مساله مکانیابی تسهیلات ظرفیتدار تک منبع به صورت زیر بیان میشود:
-3 الگوریتم تبرید شبیهسازیشده - SA -
در دههی 1980 میلادی Kirkpatrick و دیگران از یکسو و Cerny از سوی دیگر روش توانمندی را در بهینهسازی ترکیباتی بنا نهادند که روش تبرید شبیهسازیشده نام گرفت 8]،7،.[3 این روش که براساس شباهتهایی میان فرایند سرد شدن تدرجی یک ماده جامد از فیزیک و حل مسائل بهینهسازی ترکیباتی بنا شده بود بعدها در زمرهی بهترین روشهای جستجوی محلی2 قرار گرفت .[8] در علم ترمودینامیک تبرید تدریجی، به فرایند گرمایی گفته میشود که طی آن یک مادهی جامد در حمام گرما به حال پایدار خود - حالتی با انرژی پایین - دست مییابد. این فرایند، همچنان که در مرجع [2] بدان اشاره شده، شامل دو مرحله زیر است:
• افزایش دمای حمام گرما تا بدان حد که مادهی جامد ذوب شود.
• کاهش تدریجی دما در حمام گرما تا جایی که ذرات ماده خود رادرحالت پایداری از مادهی جامد آرایش دهند.
به این ترتیب مادام که ماده در حالت مایع بهسر میبرد ذرات آرایشهای تصادفی متقارنی به خود میگیرند تا اینکه سرانجام در پایدارترین حالت خود تشکیل کریستال خواهند داد که در آن ماده از کمترین سطح انرژی خود برخوردار است. چنین حالت پایداری اغلب با افزایش دمای حمام گرما به اندازهی کافی - مرحلهی اول - و همچنین سرد نمودن آن با آهستگی کافی بدست خواهد آمد حال آنکه در غیراینصورت به نحو ناپایداری منجمد خواهد شد.
مشاهدهی فرایند فوق Metropolis و دیگران [11] را برآن داشت که الگوریتم سادهای بمنظور شبیهسازی تکامل ماده جامد در حمام گرما ارائهدهند. الگوریتم ارائه شده توسط Metropolis و همکارانش را میتوان برای تولید کردن جوابهای یک مساله بهینهسازی ترکیبیاتی هم مورد استفاده قرار داد. به این منظور سیستم فیزیکی ذرات در ماده جامد با مساله بهینهسازی ترکیبیاتی همارز گرفتهمیشود که این همارزی برپایه دوشباهت .1 جوابهای مساله بهینهسازی ترکیبیاتی با حالتهای سیستم فیزیکی مادهی جامد همسان فرض میشود و .2 هزینهی هرجواب از مساله بهینهسازی ترکیبیاتی با انرژی حالت همسان از ماده، یکی گرفته میشود استوار است. علاوه برآن بمنظور شبیهسازی نقش دما در الگوریتم Metropolis، پارامتری تحت عنوان "پارامتر کنترلی"3 نیز روی مساله بهینهسازی ترکیبیاتی درنظر گرفته میشود.
