الگوریتم بهینه سازی نوردیدن و کاربرد آن در نمونه برداری فضایی-موسسه چشم انداز
نویسنده :ساره حدادی :نویسنده کتاب های آمار فضایی
درباره ساره حدادی:
ساره حدادی پژوهشگر آمار فضایی در موسسه چشم انداز هزاره سوم ملل میباشد. مدرک کارشناسی و کارشناسی ارشد خود را به ترتیب در سال 1388 و 1392 در رشته آمار و آمار ریاضی اخذ کرده. اکنون وی دانشجوی دکترای رشته آمار دانشگاه بیرجند است. ایشان از سال 1394 فعالیت خود را با موسسه چشم انداز آغاز نموده است. وی مولف 4 کتاب و چندین مقاله در زمینه آمار فضایی است.
آمار فضایی و کاربردهای آن یکی از موضوعات مورد علاقه وی میباشد.
یکی از ویژگی اصلی ایشان سخت کوشی برای درک مباحثی است که به آن علاقه مند است.
ایدۀ این الگوریتم بر اساس علم فیزیک آماری میباشد. فرض کنید قرار گرفتن ماده در مکانی با کمترین انرژی مورد نظر باشد به طوری که آن ماده منجمد شود. برای این منظور باید ماده از موقعیت i با انرژی (E(i به موقعیت j با انرژی (E(j در دمای T منتقل شود، به طوری که اگر (E(j)≤ E(i باشد انتقال پذیرفته میشود و اگر (E(j) > E(i انتقال با احتمال بولتزمن که مساوی است، پذیرفته میشود. اکنون اگر به تعداد لازم از انتقالها روی هر دمای داده شده انجام شود و دما نیز به تدریج کاهش یابد، در این صورت با احتمال زیاد ماده در مکانی با کمترین انرژی جای گرفته و منجمد میشود. در مسائل ریاضی به منظور تعیین نقاط ماکسیمم یا مینیمم یک تابع، در صورتی که استفاده از روشهای عددی مورد نیاز باشد، یک راه حل، به کارگیری الگوریتم نوردیدن شبیه سازی شده است (کیرک پاتریک و همکاران،1983). برای تعیین طرح نمونه برداری فضایی بهینه، ونگرونیگن و اشتین (1998) و ژئو و اشتین (٢٠٠۵) استفاده از الگوریتم نوردیدن شبیه سازی شده را پیشنهاد کردند با این تشابه که موقعیت ذکر شده، طرح نمونه برداری (S(i بوده و انرژی، همان تابع معیار طرح است. برای ارائۀ الگوریتم مورد نظر، ابتدا مفروضات زیر در نظر گرفته می شود.
دمای اولیه ، دمایی که الگوریتم با آن شروع می شود و هر عدد مثبتی می تواند باشد.
دمای پایانی ، که با رسیدن دما به این مقدار، الگوریتم پایان می یابد و باید کوچک و نزدیک به صفر اختیار شود.
شعاع ، که با استفاده از آن نقطۀ جدید و بالاخره طرح جدید بدست میآید و مقدار آن با توجه به ناحیۀ مورد مطالعه تعیین می شود.
فاکتور کاهشی دما و فاکتور کاهشی شعاع
، که با استفاده از آنها دما و شعاع به ترتیب به صورت
و
کاهش می یابند و مقادیری که این دو فاکتور میگیرند بین صفر و یک است.
تعداد تکرارها در هر سطح دما، که حلقۀ الگوریتم در هر سطح دما به تعداد آن تکرار می شود و هر عدد مثبتی می تواند باشد.
لازم به ذکر است که انتخاب مقادیر پارامترهای مورد نیاز الگوریتم، به پیچیدگی مسئله وابسته است. مثلاً اگر فاکتور کاهشی دما نزدیک به یک اختیار شود، در آن صورت تعداد سطح دمای مورد بررسی برای الگوریتم بیشتر میشود و یا اگر تعداد تکرارهای
بزرگ در نظر گرفته شود، در آن صورت تعداد انتقال های بیشتری برای هر سطح دما بررسی می شود. در هر دو حالت دقت الگوریتم بیشتر می شود ولی زمان اجرای الگوریتم نیز افزایش می یابد.
نحوۀ انجام این الگوریتم به این صورت است که ابتدا برای طرح اولیۀ داده شدۀ معیار طرح یعنی
محاسبه می شود. سپس در سطح دما و شعاع اولیۀ داده شده،حلقۀ الگوریتم شروع می شود، به طوری که ابتدا برای بدست آوردن طرح جدید
یک نقطه از طرح اولیۀ
مانند
به طور تصادفی انتخاب و حذف میشود. سپس با استفاده از زاویۀ تصادفی
و شعاع داده شده
نقطۀ جدیدی به صورت
بدست می آید. حال اگر این نقطۀ جدید داخل ناحیۀ D باشد، الگوریتم ادامه مییابد. در غیر این صورت، اگر نقطه خارج از ناحیه باشد، روند انتخاب ادامه مییابد تا نقطۀ جدید داخل ناحیه قرار گیرد. با فرض قرارگیری نقطۀ جدید داخل ناحیه، این نقطه با نقطۀ قبلی طرح مقایسه میشود تا نقطۀ جدید بر هیچ یک از نقاط قبلی طرح منطبق نباشد. زیرا در این صورت طرح از n موقعیت به
مکان کاهش خواهد یافت. در صورتی که نقطۀ جدید منطبق بر یکی از
نقطۀ قبلی طرح باشد، این نقطۀ جدید مورد قبول نبوده و باید دوباره نقطۀ جدید دیگری بدست آید. ولی در صورت تمایز نقطۀ جدید با نقاط قبلی طرح، این نقطۀ جدید مورد قبول بوده و با جایگزینی آن به جای نقطۀ حذف شده از طرح اولیه، طرح جدید
اکنون معیار طرح برای این طرح جدید به صورت
محاسبه شده و با
مقایسه می شود. اگر
باشد، طرح جدید جایگزین طرح اولیه میشود. در غیر این صورت، مقدار
محاسبه و با عدد تصادفی a که از فاصلۀ
انتخاب شده است، مقایسه می شود. اگر
باشد مجدداً انتقال پذیرفته شده و طرح
جایگزین طرح
می شود. در غیر این صورت طرح
انتخاب می شود. این حلقه به اندازۀ تعداد تکرارهای
که در ابتدای الگوریتم در نظر گرفته شده است، تکرار میشود. سپس در انتهای حلقه، با استفاده از دو فاکتور کاهشی
و
دما و شعاع کاهش یافته و برای سطح جدید دما و شعاع بدست آمده، حلقه مانند قبل اجرا میشود. این روند تا زمانی که الگوریتم به دمای پایانی برسد، ادامه مییابد. سرانجام با اتمام الگوریتم، آخرین طرح بدست آمده، طرح نمونهبرداری بهینه میباشد. یک مسئله در استفاده از الگوریتم های بهینهسازی از جمله الگوریتم نوردیدن شبیهسازی شده، بعضاً حساس بودن نتایج به نقطۀ شروع طرح اولیه الگوریتم میباشد. بنا براین، برای بررسی این مسئله، چند طرح مختلف را به عنوان طرح اولیۀ الگوریتم در نظر گرفته و برای هر کدام از طرحها الگوریتم را اجرا میکنیم. اگر طرحهای حاصل از این الگوریتم ها یکسان و یا مشابه هم باشند، نشاندهندۀ عدم حساسیت به طرح اولیه است.