حل مسئله Subset Sum توسط الگوريتم فراابتكاري تبريد شبيه سازي شده (Simulated Annealing)

مسئله Subset Sum يك مسئله بهينه سازي و جزء مسايل NP مي باشد كه در آن به دنبال زيرمجموعه از اعداد در يك مجوعه مي باشيم با شرط كمينه بودن تعداد اعداد و در عين حال جمع اعداد مجموعه هر چه بيشتر به عدد هدف ما نزديك باشد.روش هاي كه به صورت دقيق براي اين مسئله ارايه گرديده داراي پيچيدگي زماني نمايي O(2k) مي باشد. در اين مقاله الگوريتم طراحي شده از روش الگوريتم تبريد شبيهسازي شده ،(Simulated Annealing) (SA) كه يك الگوريتم بهينهسازي فراابتكاري ساده و اثربخش در حل مسائل بهينهسازي مي باشد استفاده نموده و در نهايت يك جواب در زمان بسيار كم حتي براي مجموعه هاي بزرگ و با ضريب تقريب بسيار بالا ارائه مي نمايد . الگوريتم تبريد شبيهسازي شده، توسط كريك پاتريك و كرني و در سالهاي 1983 و 1985 ارائه گرديده. است.كه اين الگوريتم بر تكنيك تبريد تدريجي، به وسيله متالورژيستها براي رسيدن به حالتي كه در آن ماده جامد، به خوبي مرتب و انرژي آن كمينه شده باشد، استفاده ميشود. اين تكنيك شامل قرار دادن ماده در دماي بالا و سپس كم كردن تدريجي اين دماست.