موضوع مقاله: روش نلدر-مید | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش نلدر-مید | مقدمه: راس‌های سیمپلکس با مقدار آنها مرتب می‌گردد، که ۱ دارای کمترین (بهترین) مقدار است. | ## بخش 1: روش نلدر-مید | روش نلدر-مید یا روش سیمپلکس سراشیبی، یک روش عددی رایج در پیدا کردن کمینه یا بیشینه یک تابع هدف در فضای بهینه‌سازی چند بعدی می‌باشد. این یک روش جستجوی مستقیم (بر اساس مقایسه عملکرد) است و اغلب برای مشکلات بهینه‌سازی غیرخطی است که مشتقات آن ممکن است مشخص نباشد، استفاده می‌شود. روش نلدر-مید توسط جان نلدر و راجر مید در سال ۱۹۶۵ پیشنهاد شد، که به عنوان توسعه ای از روش Spendley و همکاران بود. بررسی اجمالی در این روش از مفهوم سیمپلکس استفاده شده‌است، که یک چندبر ویژه با n+1 راس در یک n بعدی می‌باشد. نمونه‌هایی از سیمپلکس‌ها عبارتند از: یک پاره خط بر روی یک خط، یک مثلث در صفحه، یک چهار وجهی در فضای سه بعدی و غیره. هنگامی که تابع هدف به نرمی تغییر می‌کند و یکتا می‌باشد، این روش یک بهینه‌سازی محلی برای یک مسئله با n متغیر را تقریب می‌کند. پیاده‌سازی‌های معمولی توابع را به حداقل می‌رسانند، یا با به کمینه کردن ، را بیشینه می‌کنند. به عنوان مثال، در یک پل تعلیق مهندس باید انتخاب کند که هر بند، کابل و اسکله چقدر ضخیم باشد. این عناصر به هم وابسته هستند، اما تجسم تأثیر تغییر هر عنصر خاص کار ساده ای نیست. شبیه‌سازی چنین ساختارهای پیچیده‌ای از لحاظ محاسباتی اغلب پر هزینه بوده و احتمالاً ساعت‌ها برای اجرای آن طول می‌کشد. روش Nelder-Mead، در نوع اصلی نیاز به بیش از دو ارزیابی در هر تکرار ندارد، به جز عملیات منقبض شدن که در ادامه شرح داده شده‌است، که در مقایسه با برخی دیگر از روش‌های بهینه‌سازی جستجوی مستقیم، مورد توجه است. روش نلدر – مید در یک مسئله n بعدی، مجموعه از n+1 نقطه آزمایشی که به صورت سیمپلکس است را در نظر می‌گیرد. سپس به منظور پیدا کردن یک نقطه آزمایشی جدید و جایگزینی یکی از نقاط آزمایشی قدیمی با مورد جدید، رفتا تابع مورد نظر در هر نقطه آزمایشی، مورد بررسی قرار می‌گیرد و سپس این روش ادمه پیدا می‌کند. | ## بخش 2: روش نلدر-مید | ساده‌ترین رویکرد جایگزینی بدترین نقطه، از لحاظ مقدار، با یک نقطه منعکس شده، از طریق مرکز n نقطه باقی مانده می‌باشد. اگر این نقطه منعکس شده بهتر از نقطه فعلی باشد، می‌توانیم کشیدگی را در امتداد این خط امتحان کنیم. از طرفی دیگر، اگر این نکته جدید بهتر از مقدار نقطه قبلی نباشد، در واقع ما در یک دره قدم می‌گذاریم، بنابراین سیمپلکس را در جهت بدست آوردن یک نقطه بهتر منقبض می‌کنیم. توضیح شهودی الگوریتم از "دستور العمل‌های عددی":* روش سرازیر سیمپلکس یک سری مراحل را طی می‌کند به طوریکه بیشتر مراحل فقط نقاط سیمپلکس را در جایی که خروجی تابع بیشینه است، از طریق نقطه مقابل سیمپلکس، به یک نقطه کمینه انتقال می‌دهد. وقتی این مراحل انجام می‌شود، سیمپلکس در جهت یا جهت دیگر گسترش می‌یابد تا گام‌های بزرگتری برداشته شود. هنگامی که به «کف دره» رسید، این روش خود را در جهت عرضی منقبض می‌کند و سعی می‌کند از دره بیرون رود. اگر شرایطی وجود داشته باشد که سیمپلکس سعی کند «از چشم سوزن عبور کند»، خود را از همه جهات منقبض می‌کند، و خود را به پایین‌ترین (بهترین) نقطه می‌کشد. بر خلاف روش‌های بهینه‌سازی مدرن، روش اکتشافی نلدر-مید می‌تواند به یک نقطه غیر ثابت همگرا شود، مگر اینکه این ممسئله شرایط قوی تری از آنچه برای روش‌های نوین لازم است را برآورده کند. یک نوع رایج از یک سیمپلکس کوچک با اندازه ثابت استفاده می‌کند که تقریباً از جهت شیب پیروی می‌کند. اگر نقطه منعکس شده ، سپس با جایگزین کردن بدترین نقطه ، با نقطه منعکس شده ، سیمپلکس جدید را به دست آورید و به مرحله ۱ بازگردید. گسترش اگر نکته منعکس شده بهترین نقطه تا کنون است، ، سپس نقطه گسترش یافته را محاسبه کنید با . اگر نقطه گسترش یافته بهتر از نقطه منعکس شده باشد، ، سپس با جایگزین کردن بدترین نکته ، با نقطه گسترش یافته سیمپلکس جدید را بدست آورید و به مرحله ۱ بروید؛:: در غیر اینصورت با جایگزین کردن بدترین نکته ، با نکته منعکس شده سیمپلکس جدید را بدست آورید و به مرحله ۱ بروید. اگر نقطه انقباض شده بهتر از بدترین نقطه باشد، یعنی ، سپس با جایگزین کردن بدترین نکته ، با نقطه انقباض شده سیمپلکس جدید را بدست آورید و به مرحله ۱ بروید. | ## بخش 3: روش نلدر-مید | برای بازتاب، از آن زمان که راس با ارزش بالاتر در بین رئوس است، می‌توان انتظار داشت که در بازتاب، مقدار کمتری داشته باشد که توسط همه راسها جز در طرف مخالف شکل گرفته‌است. برای گسترش، اگر نقطه بازتاب کمینه جدید در بین رئوس باشد، می‌توان انتظار داشت که مقادیر جالبی را در طول مسیر از به پیدا کنیم. در مورد انقباض، اگر باشد، می‌توان انتظار داشت که یک مقدار بهتر در بین سیمپلکس تشکیل شده توسط همه راسها باشد. در نهایت، کوچک شدن یک مورد نادر است، که انقباض از بزرگترین نقطه ای که افزایش می‌یابد، اتفاق می‌افتد. در این صورت در انتظار یافتن دورنمایی ساده‌تر انقباض می‌یابد که به پایین‌ترین نقطه می‌رسیم. با این حال، نش اشاره می‌کند که با دقت محدود عددی گاهی اوقات نمی‌تواند در کوچک کردن سیمپلکس عمل کند، و بررسی ای را انجام داد که اندازه در واقع کاهش یافته‌است. در واقع، یک سیمپلکس اولیه خیلی کوچک می‌تواند به جستجوی محلی منجر شود، در نتیجه NM می‌تواند به راحتی جوابگو نباشد؛ بنابراین این سیمپلکس باید بستگی به ماهیت مسئله داشته باشد. با این حال، مقاله اصلی سیمپلکس ای را پیشنهاد می‌کند که یک نقطه اولیه به عنوان داده می‌شود، همراه با نقاط دیگر که با یک گام ثابت در طول هر بعد تولید می‌شود؛ بنابراین روش به مقیاس متغیرهای که را تشکیل می‌دهد، حساس است. نلدر و مید از انحراف استاندارد برای مقادیر تابع، به ازای سیمپلکس فعلی استفاده کردند. اگر مقادیر تابع کوچکتر از یک مقدار معین گردد، چرخه متوقف می‌شود و پایین‌ترین نقطه در سیمپلکس به عنوان یک نقطه بهینه پیشنهادی بازمی‌گردد. توجه داشته باشید که یک تابع بسیار «مسطح» ممکن است مقادیر عملکرد تقریباً برابر با یک دامنه بزرگ داشته باشد، به طوری که جواب به مقدار تلرانس حساس خواهد بود. | ## جمع‌بندی | توجه داشته باشید که برنامه‌ها خاتمه می‌یابند، در حالی که تکرارها ممکن است همگرا شوند.