1) روش نلدرمید
در سال 1965 نلدرومید کارایی روش هکس، اسپندلی، هیمسورف را با تعیین
سیمپلکس های بدون قاعده افزایش داده اند.
روش آنها یکی از روشهای کارآمد معمولی و در دسترس بود که اگر تعداد متغیرها فراتر از 5 یا 6 نبود به خوبی کار می کرد. مسئله مینیمم سازی f(x) را در نظر بگیرید. فرض کنید x1 یک تخمین اولیه از x* باشد. و فرض کنید رئوس اولیه سیمپلکس به طوری که : که بردارهایی که متناظر و اسکالرهای براساس فاصله ممکن کمیتهای انتخاب می شوند و یا می توان
(A-1)
که در آن بردارهایی که متناظر و است در سیمپلکس کنونی فرض کنید:
یک راس با بیشترین مقدار تابع باشد.
یک راس با دومین مقدار بعد از بیشترین مقدار تابع باشد.
یک راس با کمترین مقدار تابع باشد.
مرکز ثقل تمام رئوس به جز راس باشد. یعنی:
همچنین فرض کنید و ...
سپس روش پیشنهادی نلدرمید را برای min سازی f(x) به صورت زیر توصیه می کنیم:
1) راس های سیمپلکس اولیه را همانطور که در بالا شرح داده شد انتخاب کنید و مقدار f(x) را برای هر کدام از آن راس ها مشخص کنید.
2) بازتاب: بازتاب xh را با استفاده از عامل بازتاب تعیین کنید یعنی را طوری پیدا کنید که
یا
3) اگر پس را با جایگزین کنید و سپس به مرحله 2 بازگردید.
4) انبساط: اگر ، سیمپلکس را با استفاده از عامل بسط بسط دهید یعنی را به صورت زیر پیدا کنید. (شکل 3-3)
یا
الف) اگر باشد را با جایگزین کنید و به مرحله 2 بازگردید.
ب) اگر را با جایگزین کنید و سپس به مرحله 2 بازگردید.
5) انقباض: اگر باشد. سیمپلکس را با استفاده از عامل انقباض منقبض کنید. دو حالت در نظر بگیرید:
الف) اگر (شکل 3. 4) پیدا کنید را چنان که :
ب) اگر (شکل 3. 5) پیدا کنید را چنان که :
اگر (5 الف) یا (5 ب) به کار برده شود دوباره دو حالت را بررسی می کنیم:
ج) اگر و باشد را با جایگزین کنید و به مرحله (2) بازگردید.
د) اگر یا اندازه سیمپلکس را با نصف کردن فاصله از کاهش دهید و به مرحله (2) بازگردید.
نلدر و مید، را به ترتیب برای عامل های انقباض وانبساط وبازتاب پیشنهاد می کنند.
یک معیار همگرایی مناسب برای پایان محاسبه وقتی است که انحراف استاندارد از کمتر از مقدار مقرر در نظر گرفته شده باشد یعنی هنگامی که:
که در آن
باکس و دیویس و سوان معیار مطمئن تری پیشنهاد می کنند: بدین ترتیب که S را بعد از هر تعیین مقدار تابع k ، تعیین کنیم که k مقرر شده است. هنگامی که دو مقدار متوالی از s کمتر از شد و مقدارهای متناظر از با کمتر از مقدار مقرر شده تفاوت داشت توقف می کنیم.
2) اکسترمم کلی از یک جستجوی اکسترمم نسبی با شروع های احتمالی
بهینه کننده های موضعی می توانند جستجوی کلی را تکمیل کنند وقتی که مکررا
از نقاط مختلف شروع شوند. آسان ترین روش شروع، جستجوی با قاعده از نقاط است یا
می توان نقاط را تصادفی انتخاب کرد. در مورد اول، ما احتیاج داریم بدانیم که برای
محاسبه ی اندازه ی شبکه چه تعداد شروع انجام می شود. در مورد بعدی از اطلاعات ما
درباره ی جستجوهای گذشته استفاده نمی شود. ممکن است اکسترمم های نسبی یکسانی در
چندین دفعه پیدا کنیم که این یک تلاش پرهزینه و غیر ضروری است. در کاری که پیش رو
داریم تعداد شروع ها از قبل نامعلوم است زیرا این باعث می شود تعداد زیادی بررسی
های تحمیلی بر الگوریتم وارد شود و هزینه ی هر جستجوی موضعی نامعلوم است. یک روش
شبکه ای نمی تواند در اینجا کاربردی باشد. همچنین فضایی از جستجوهای موضعی قبل با
ایجاد چگالی احتمال ویژه از شروع یک جستجو حفظ می شود.
2-1) شروع احتمالی:
این روش می تواند به عنوان نسخه ی هموار از تکنیک های نموداری در نظر گرفته شود، که نمودارها می توانند در نقاط نمونه ی انتخاب شده متمرکز شوند.
احتمال به صورت زیر نوشته میشود.
(1)
که N تعداد نقاط نمونه ی قبلی است و تابع چگالی احتمال چند بعدی نرمال است.
(2)
که n بعد است (تعداد متغیرها) و ماتریس کوواریانس است.
(3)
واریانس به وسیله رابطه زیر برآورد می شود.
(4)
که یک پارامتر مثبت است که
طول گوسی را کنترل می کند و و کران ها درj امین جهت هستند. به منظور حفظ آسانی و کم هزینه
بودن روش تا حد امکان واریانس ها ثابت نگه داشته شده اند. این استراتژی به علت
بزرگی تعداد بررسی ها
هزینه ای خواهد داشت.
چگالی احتمال است اما چون یک دامنه کراندار بررسی می شود پس یک احتمال معرفی می شود.
(5)
که می باشد. چگالی احتمال یک نقطه نمونه گیری جدید ، چگالی احتمال یک نمونه قبلی نیست. برای برآورد آن فرض های زیر را می پذیریم. فقط بزرگترین نقطه از از نمونه ی داده شده در تکرار بعدی احتمال صفر دارد. بنابراین احتمال به صورت زیر محاسبه می شود:
(6)
که است.
شکل (1) ، را در یک دامنه ی دو بعدی تصویر می کند.
ماکزیمم در ابتدا دقیقا به دست نمی آید. اولا به خاطر مقدار عددی آن و ثانیا همان طور که در بخش 301 خواهیم دید آن برای جستجو زیان آور است در عوض نقاط به طور تصادفی انتخاب شده و نقطه ی ماکزیمم برای شروع جستجوی بعدی انتخاب شده است. توجه کنید که به منظور ماکزیمم سازی محاسبه M از(5)وH از(6)لازم نیست چرا که ماکزیمم می نیمم P است بنابراین فقط P محاسبه می شود.
سه پارامتر بر چگالی احتمال P و در نتیجه بر نقاط شروع تاثیر می گذارند:
1) نقاطی که برای محاسبه ی احتمال نگهداری می شوندP
2) تعداد نقاط تصادفی استفاده شده برای ماکزیمم سازی
3) پارامتر طول گوسی
آنها در نتایج عددی (بخش 3-1) بحث شده اند. فرآیند شروع احتمالی برای هر بهینه کننده ی موضعی می تواند کاربردی باشد. در این مورد الگوریتم نلدرمید بهبود یافته پیشنهاد میشود.
2-2) جستجوی نلدرمید بهبود یافته :
الگوریتم GBNM از الگوریتم نلدرمید به علت مجموعه ای از انتخاب های شروع متفاوت است(دیگر تفاوتها در رابطه با قیدها هستند).
هدف از شروع ها دو چیز است:
اولا: شروع های احتمالی روی چگالی P (رابطه 1) پایه گذاری شده است. هدف از تکرار جستجوهای اکسترمم های نسبی رسیدن به یک مقدار کلی ثابت است، که به آن رسیده ایم.
این شکل کلی روش است. در انجام شروع احتمالی رایج اندازه ی سیمپلکس جدید، a (تعریف شده در رابطه ی A-1) ، یک متغیر تصادفی یکنواخت به دست آمده بین 2% و 10% از کوچکترین بعد دامنه است.
ثانیا : شروعها همگرایی الگوریتم را بررسی کرده و بهبود میدهند. شکلهای دو شروع
که همگرا هستند با شروع یک سیمپلکس جدید به بهترین رأس جاری مرتبط هستند. امتحان کوچک و بزرگ بودن شروعها یک سیمپلکس کوچک و بزرگ با اندازههای به ترتیب as وa ، خواهدبود.
همگرایی برای جستجوهای اکسترمم نسبی نلدرـ مید از میان سه معیار زیر تعیین میشود. امتحان کوچک، مسطح یا تباهیده بودن سیمپلکس.
سیمپلکس کوچک است اگر :
(7)
که i امین مولفه از K امین یال، و کرانهای i امین راستا و تعیین کننده مجاز است.
سیمپلکس مسطح است اگر:
که fH و fL بزرگترین و کوچکترین توابع هدف در سیمپلکس و مقدار مجاز است.
سیمپلکس تباهیده است اگر : در زیر فضایی از دامنهی جستجو ادغام شده باشد. این رایجترین حالت معمول در روش جستجوی نلدرـ مید است زیرا روش نمیتواند از زیرفضا رها شود، به طور دقیق تر یک سیمپلکس در اینجا تباهیده نامیده میشود اگر آن به اندازهای کوچک باشد که در تماس با یک متغیر کراندار نباشد و یکی از دو شرط زیر را برآورده سازد.
(9) یا
که ek ، kامین یال است. e ماتریس یال و ||0|| نرم اقلیدسی را نمایش میدهد و و ثابتهای مثبت کوچک میباشند. ارتباط سه شروعها و سه آزمون همگرایی در الگوریتم GBNM در شکل (2) نمایش داده شده است.
حافظهای همگرایی قبلی تعیین شده را نگهداری میکند. که این از محاسبه غیرضروری روی نقاط قبلی جلوگیری میکند. (سومین امتحان، T3 در فلورچارت شکل2) هنگامیکه سیمپلکس مسطح است یک شروع احتمالی انجام شده است. (T4).
سیمپلکسی که تباهیده شده است موجب یک امتحان بزرگ تکرار میشود (T8). هنگامی که بهینگی از همگرایی روی نقاط نامطمئن است، چنین همگرایی روی متغیری کراندار که سیمپلکس تباهیده دارد رخ میدهد. (T6) امتحان کوچکی که کنترل بهینگی را متوقف میکند انجام میشود.
اگر سیمپلکس کوچک به نقاط همگرایی یکسان برگردد آن نقطه بعنوان بهینه موضعی در نظر گرفته میشود.
این باید یادآوری شود که شرایط کان – تاکر از برنامهریزی ریاضی قابل اجرا برای قالبهای دیفرانسیل ناپذیر کنونی نیست. تولرانسها برای سیمپلکسهای کوچک و تباهیده یعنی و ] ، [ به ترتیب ممکن است به سختی به دست آیند. پس یک سیمپلکس که کوچک است ممکن است قبلاً تباهیده باشد، اگر یک تباهیدگی دردو نقطه ی متوالی یکسان
یافت شود نقطه بعنوان یک بهینه ی ممکن گرفته می شودویک شروع احتمالی نامیده میشود.متشابها اگر یک تباهیدگی بعد از یک امتحان کوچک رخ دهد این نقطه نیز بعنوان یک بهینه ی ممکن در نظر گرفته میشودویک امتحان بزرگ باید انجام شود.
3) نتایج عددی
در این قسمت روش GBNM را با یک الگوریتم ریشهگیری (EA) برای یک مسئله مقایسه میکنیم. الگوریتم ریشهگیری یک ساختار تدریجی ، رمزگذاری واقعی و تقاطع پیوسته و جهش گوسی با واریانس دارد. برای بیان جزئیات پارامترهای EA انتخاب شده هر بررسی آنهایی هستند که در بین صد سه تایی مستقل از میان همهی ترکیبات با اندازه های جمعیت (20 یا 50) و احتمال های جهش( 15/0 یا /20 و احتمالهای تقاطع( 4 /0 یا 5/0) بهتر عمل میکنند.
3- 1انتخاب پارامترهای GBNM
3-1-1پارامتر طول گوسی، a:
در این کار a مجموعهای با 01/0 که به معنی یک تقسیم استاندارد از روش گوسی که حدود 20/0 دامنه را پوشانده است میباشد.
3-1-2 نقاط نگهداری شده برای محاسبه احتمالی
سه استراتژی در رابطه با احتمال یافت نشدن حداقل یکی از مینیممهای موضعی، Pnfm مقایسه شده بودند.
Xi ها بکاررفته در رابطه (1) و (2) :
(i) – نقاط شروع
(ii) – نقاط شروع و نقاط همگرایی موضعی
(iii) – همه نقاط نمونهای در طول جستجو می باشند.
از آزمونهای مقدماتی نتیجه شده است که استراتژی (iii) برای تحلیل، حافظه و زمان میخواهد، که نسبت به استراتژیهای (i) و (ii) در سطح پایین تر قرار دارد.
بنابراین دلایل، استراتژی (iii) برای بررسیهای بیشتر در نظر گرفته نمیشود.
استراتژیهای (i) و (ii) با Nr متغیر از 1 تا 1000 روی سه تابع زیر بررسی می شوند.
F1(x1,x2)=2+0.01(x2-x12)2+(1-x1)2+2(2-x2)2+sin(0.5x1)sin(0.7x2x1)
x1,x2Î[0,5]
f2(x1,x2)=(4-2.1x12+x12)x12+x1 x2+(-4+4x22)x22
x1,x2Î[-3,3]
f3(x1,x2)=(x2-x12+x1-6)2+10(1-)cos(x1)+10
x1Î[-5,10] , x2Î[0,15]
f1 چهار مینیمم و f2 شش و f3 سه مینیمم دارد( شکل 3 را ببینید) . f2 به عنوان تابع شش کوهانه، f3 به عنوان تابع "برانینز آرکوس" شناخته شده است. برای استراتژیهای اول و دوم نتایج پس از 500 تحلیل و بر اساس 100 اجرای مستقل در جدول (1) و (2) به ترتیب نمایش داده شدهاند. استراتژی دوم بطور مستقل از Nr بهتر عمل میکند . این نشان میدهد که نقاط شروع و همگرایی موضعی به اندازه کافی در توپولوژی اساس تکرار جمعبندی میشوند این قالب برای به روز کردن P انتخاب شده است.
3-1-3 تعداد نقاط تصادفی Nr
اگر Nr=1 باشد شروعها تصادفی است. اگر Nr بزرگ باشد نقاط شروع بر اساس نقاط شروع و همگرایی جستجوهای قبل توزیع میشوند که یک الگوی هندسی کامل را به وجود میآورد.
اگر Nr یک عدد کوچک بزرگتر از یک باشد شروعها تصادفی اریب هستند. باید یک سازگاری بین استراتژیهای شبکهای و تصادفی دیده شود. مقدار بهینه ی Nr وابسته به تابع آزمایش است اگر اساس تکرار، توزیع با قاعده باشد شروعها با یک الگوی با قاعده (یعنی Nr بزرگ) بهینه هستند و برعکس.
از نتایج آزمایشها در سه تابع چندوجهی ارائه شده در جدول (2) استراتژی بهینه، Nr بزرگ برای f1 و f3 است در حالیکه برای f2 ،Nr=2 می باشد.
Nr=10 بعنوان یک سازگاری برای تابع بهینه ی کلی انتخاب شده است.
3-2- تابع مینیمم سازی گریوانک
تابع آزمایش مینیمم سازی گریوانک را به صورت زیر در نظر بگیرید
(11)
xiÎ[-1000,1000]
که بعد n=12 و مینیمم کلی برابر 1.0- در Xi=0.0 و n وi=1 .این تابع چندین مینیمم موضعی دارد شکل (4) آن را در حالت یک بعدی (n=1) و xÎ[-20-20] نشان میدهد جدول (3) GBNM و بهترین نقطه در الگوریتم ریشهگیری جمعیت (EA) در 200، 1000، 5000 و 10000 تابع رافراخوانی میکند.
جدول (3) صد اجرای مستقل با نقاط شروع GBNM که به طور تصادفی انتخاب شدهاند را معدل گیری میکند. معیار زیر با فرض اینکه EA به مینیمم کلی همگرا شده است بکار میرود.
(12)
که x بهترین نقطه یافت شده و x مینیمم کلی است. نتیجهی کلی این است که روش GBNM به طور متوسط مقادیر تابع هدف بهتر با احتمال یافتن بیشتر مینیمم کلی از آنچه EA انجام میدهد را مییابد. فایدهی روش GBNM ذاتاً در تعداد کم بررسیها و رشد پایین مقادیر عددی است.
4- نتیجهگیری
یک روش بهینه سازی کلی و موضعی بر اساس شروع احتمالی نشان داده شد. جستجوهای موضعی به وسیله الگوریتم نلدرمید بهبود یافته تعیین میشوند که متغیرهای مساله می توانند کراندار یا با قیدهای نامساوی داده شده باشند.این روش جستجوی نلدرمید کراندار یا کلی (GBNM) نامیده میشود که نیاز به حساسیت و ساختار مورد استفادهی کامپیوتر ندارد و بهینه های موضعی که شامل بهینه ی کلی است را با افزایش احتمال که با افزایش دفعات محاسبه انجام پذیر است را تعیین میکند.