بخشی از مقاله
چکیده: هدف از این مقاله بهکارگیری روش شبیهسازی آنیلینگ برای حل دستگاه معادلات خطی با ماتریس ضرایب بدوضع است. یک دستگاه معادلات خطی بدوضع نامیده میشود هرگاه عدد شرطی آن بزرگ باشد. دستگاه معادلات خطی بدوضع به کمک موازنه ماتریسی به یک دستگاه معادلات خطی با عدد شرطی کمتر تبدیل میشود. موازنه ماتریسی توسط الگوریتم شبیهسازی آنیلینگ انجام میشود. کارایی این روش با مثالهای عددی در مورد دستگاه معادلات خطی بدوضع بررسی میشود. نتایج عددی نشان می دهند که شبیه سازی آنیلینگ قادر است با موازنه ماتریسی، عدد شرطی دستگاه معادلات را کاهش دهد.
.1 مقدمه:
الگوریتم شبیهسازی آنیلینگ - SA - 1 که با اسامی دیگری همچون شبیهسازی تبرید، شبیهسازی بازپخت یا شبیهسازی انجماد نیز معرفی میشود، یک الگوریتم فرا ابتکاری جستجوی محلی است که قابلیت فرار از دام بهینههای محلی را داراست. سادگی اجرا و خواص همگرایی و همینطور حرکات تپه نوردی برای فرار از دام بهینه محلی سبب شده است که SA یکی از روشهای پراستفاده در دو دهه اخیر شود. ایده اولیهای که بعدها مبانی الگوریتم SA قرار گرفت، اولین بار توسط متروپلیس در سال 1953 بر اساس فرآیند سرمایش و آنیلینگ موادعمدتاً - فلزات کریستالی - در علم ترمودینامیک آماری مطرح گردید. اما این الگوریتم اولین بار بهطور رسمی توسط کرک پاتریک و همکارانش با الهام از پدیده بازپخت فلزات ابداع گردیده است.
البته سرنی نیز دو سال بعد از کرک پاتریک در مقاله مستقلی مدعی شد که برای اولین بار این الگوریتم را توسعه داده است .[1] در ترمودینامیک آماری رابطه بین ساختار اتمی، بینظمی - یا آنتروپی - و دما در طول فرآیند سرمایش ماده مورد مطالعه قرار میگیرد. واژه آنیلینگ به معنای گرم کردن - و به دمای استینت رسیدن و استینه شدن فولاد یا دیگر آلیاژها - و سپس بهتدریج سرد کردن است. در فیزیک مواد فشرده، گرم و سرد کردن فرایندی است فیزیکی که طی آن یک ماده جامد در ظرفی حرارت داده میشود تا مایع شود؛ سپس حرارت آن بهتدریج کاهش مییابد. بدین ترتیب تمام ذرات فرصت مییابند تا خود را در پایینترین سطح انرژی منظم کنند. چنین وضعی در شرایطی ایجاد میشود که گرمادهی کافی بوده و سرد کردن نیز به آهستگی صورت گیرد.
جواب حاصل از الگوریتم شبیهسازی آنیلینگ، به جواب اولیه وابسته نیست و میتوان توسط آن جوابی نزدیک به جواب بهینه به دست آورد. حد بالایی زمان اجرای الگوریتم نیز قابل تعیین است. در هر تکرار از الگوریتم SA یک جواب ایجاد میگردد و با بهترین جوابی که تاکنون به دست آمده است، مقایسه میگردد. جوابهای بهبوددهنده همیشه پذیرفته میشوند، در عین اینکه بخشی از جوابهای غیر بهبوددهنده نیز به امید کمک به فرار از دام بهینههای محلی پذیرفته میشوند.
احتمال پذیرش جوابهایغیر بهبود دهنده به پارامتر دما بستگی دارد و عموماً تابعی غیرافزایشی در طول تکرارهای الگوریتم است. ویژگی کلیدی SA در استفاده از حرکات تپهنوردی برای فرار از دام بهینههای محلی است. با کاهش پارامتر دما به سمت صفر - افزایش تکرارها - حرکات تپهنوردی کمتر و کمتر صورت میگیرند و توزیع جوابهای متناظر با یک زنجیره مارکوف ناهمگن خواهد شد که حالات پایدار آن همان جوابهای بهینه سراسری خواهند بود و این امر مستلزم آن است که احتمالات حدی این حالات بزرگتر از صفر باشد. از اینرو در مسائل بهینهسازی از دما به عنوان یک پارامتر کنترلی استفاده میشود.
