بخشی از مقاله
چکیده:
مسئله Subset Sum یک مسئله بهینه سازي و جزء مسایل NP می باشد که در آن به دنبال زیرمجموعه از اعداد در یک مجوعه می باشیم با شرط کمینه بودن تعداد اعداد و در عین حال جمع اعداد مجموعه هر چه بیشتر به عدد هدف ما نزدیک باشد. روش هاي که به صورت دقیق براي این مسئله ارایه گردیده داراي پیچیدگی زمانی نمایی O - 2k - می باشد. در این مقاله الگوریتم طراحی شده از روش الگوریتم تبرید شبیهسازي شده - Simulated Annealing - - SA - ، که یک الگوریتم بهینهسازي فراابتکاري ساده و اثربخش در حل مسائل بهینهسازي می باشد استفاده نموده و در نهایت یک جواب در زمان بسیار کم حتی براي مجموعه هاي بزرگ و با ضریب تقریب بسیار بالا ارائه می نماید . الگوریتم تبرید شبیهسازي شده، توسط کریک پاتریک و کرنی و در سالهاي 1983 و 1985 ارائه گردیده. است.که این الگوریتم بر تکنیک تبرید تدریجی، به وسیله متالورژیستها براي رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژي آن کمینه شده باشد، استفاده میشود. این تکنیک شامل قرار دادن ماده در دماي بالا و سپس کم کردن تدریجی این دماست.
مقدمه
با پیشرفت علم بشر سعی دارد تا با حل مسائل پیچیده گامی در جهت ارتقاء دانش جهانی بردارد.در دنیاي امروز هم بشر با کمک کامپیوتر توانسته مسایل گوناگونی را حل نماید. یکی از روشهاي ابداع شده براي حل مسائل سخت و پیچیده روش تبرید شبیه سازي شده می باشد که روش الگوریتم SA به این صورت می باشد که ابتدا از یک جواب اولیه شروع میکند و سپس در یک حلقه تکرار به جوابهاي همسایه حرکت میکند. اگر جواب همسایه بهتر از جواب فعلی باشد، الگوریتم آن را به عنوان جواب فعلی قرار میدهد - به آن حرکت میکند - ، در غیر این صورت، الگوریتم آن جواب را با احتمال exp - -ΔE/T - به عنوان جواب فعلی میپذیرد. در این رابطه ΔE تفاوت بین تابع هدف جواب فعلی و جواب همسایهاست و Tیک پارامتر به نام دما است.
در هر دما، چندین تکرار اجر میشود و سپس دما به آرامی کاهش داده میشود. در گامهاي اولیه دما خیلی بالا قرار داده میشود تا احتمال بیشتري براي پذیرش جوابهاي بدتر وجود داشته باشد. با کاهش تدریجی دما، در گامهاي پایانی احتمال کمتري براي پذیرش جوابهاي بدتر وجود خواهد داشت و بنابراین الگوریتم به سمت یک جواب خوب همگرا میشود. الگوریتمSA یک الگوریتم غیرمقید می باشد که براي طراحی هاي سخت به کار می رود.حال با این مقدمات از مسئله Subset Sum و روش حل SA معرفی شده جزئیات الگوریتم پیشنهادي را بررسی می نماییم.
– 1 تعریف الگوریتم تبرید شبیه سازي شده
در این بخش، به معرفی الگوریتم شبیه سازي تبرید براي حل مسأله پرداخته میشود. این الگوریتم و یک رهیافت تکراري براي حل مسأله بوده و ایده آن از فرآیند ذوب یک جامد به سمت یک حالت داراي حداقل انرژي به وجود آمده است. فرآیند فعالیت این الگوریتم همانند شکلگیري کریستالهاي فلزگداخته درهنگام سرد شدن است. فرآیند فیزیکی سرمایش که هدف از آن کاهش دماي ماده به پایین ترین سطح انرژي است، تعادل گرمایی نامیده میشود.
فرآیند سرمایش با ماده اي در وضعیت گداخته آغاز میشود و سپس بتدریج دماي آن کاهش مییابد. در هر دما جسم، مجاز به رسیدن تعادل گرمایی است. دما نباید خیلی به سرعت کاهش یابد، بویژه در مراحل اولیه، در غیراین صورت، برخی کاستیها در ماده پدیدار شده و ماده به وضیعت انرژي کمینه نخواهد رسید . کاهش دما شبیه به کاهش مقدار تابع هدف در مسایل کمینهسازي است که توسط یک سري تغییرات بهبود دهنده انجام میگیرد. براي اینکه دما به آهستگی کاهش یابد، باید تغییرات غیر بهبود دهنده تابع هدف نیز با احتمال معینی انتخاب شوند بطوریکه وقتی تابع هدف کاهش مییابد این احتمال نیز کاهش یابد. این امر موجب میشود که الگوریتم در بهینه هاي موضعی گرفتارنشود.
1 تعاریف تبرید شبیه سازي شده
1-1 نحوه نمایش:1 جهت نمایش داده ها در الگوریتم و کار کردن روي داده به کار می رود.
2-1 مقدار اولیه:2انتخاب تصادفی یا هدف دارتعدادي از مقادیر قابل قبول جهت شروع الگوریتم و پیدا کردن همسایگی
3-1 تابع همسایگی : تابعی که همسایه یا همسایگان حالت فعلی را مشخص می نماید.
4-1 دما:3 مقدار عددي که براي انتخاب حالت هاي غیر بهبود دهنده بکار می رود به مرور از آن کاسته می شود و شانس انتخاب حالت غیر بهبود دهنده را کمتر می نماید.
5-1 انرژي: بنا به خواسته مسئله محاسبه شده در هر حالت مشخص می کند وضعیت بهبود داشته است یا خیر.
6-1 تابع تبرید:4 براي کاهش دما مورد استفاده قرار می گیرد و داراي دو حالت همگن - 5در هر حالت بهبود - و ناهمگن6 - در هر تکرار الگوریتم - می باشد و کم شدن دما در هر حالت خود نیز شامل روشهاي مانند هندسی - ضرب در یک عدد اعشاري مانند - 0.9 و یا کم کردن ثابت دما در هر مرحله از الگوریتم.
7-1 شرط خاتمه: در صورتی که دما به حد پایین برسد و یا در صورت محاسبه بهبود جواب به حد تقریب مورد نظر ما رسیده باشد.
2 پارامترها و توابع انتخابی براي الگوریتم پیشنهادي
بعد از معرفی پارامترها و توابع کلی الگوریتم SA حال به پارامترها و توابع الگوریتم پیشنهادي می پردازیم:
نحوه نمایش: از آرایه متناظر با مجموعه اصلی اعداد می باشد و که عدد 0 نشان دهنده عدم انتخاب آن عدد در مجموعه اصلی و عدد 1 نشان دهنده انتخاب آن عدد می باشد.
مقدار اولیه: یک دهم از اعداد مجموعه اصلی به صورت تصادفی7 انتخاب می گردد و بیت هاي متناظر آن در آرایه نمایش یک می گردد. تابع همسایگی: دو حالته و به شرح ذیل در نظر گرفته شده است:
حالت اول : در صورت بزرگتر بودن جمع اعداد انتخابی مجموعه از عدد هدف یکی از اعداد انتخابی به تصادف انتخاب و از مجموعه انتخابی حذف می گردد که باعث کوچکتر شدن مجموعه و کاهش مجموع اعداد آن می گردد.
حالت دوم : در صورت کوچکتر بودن جمع اعداد انتخابی مجموعه از عدد هدف یکی از اعداد انتخاب نشده از مجموعه به تصادف انتخاب و به مجموعه انتخابی اضافه می گردد که باعث بزرگتر شدن مجموعه و افزایش مجموع اعداد آن می گردد.
دماي اولیه : بنا به بررسی انجام شده و مقایسه جوابهاي مشخص شده دو برابر تعداد اعداد مجموعه اصلی در نظر گرفته شده است. انرژي: در هر مرحله مجموع اعداد انتخابی از مجموعه اصلی بوده و بهبود در هر مرحله نزدیک شدن مجموع اعداد به عدد هدف می باشد. تابع تبرید: حالت همگن انتخاب گردیده و به روش هندسی و مقدار 0.9 به عنوان ضریب کاهش انتخاب گردیده است.
شرط خاتمه: در حالت یافتن جواب دقیق و یا کاهش دما به زیر عدد یک ،الگوریتم خاتمه می یابد.
