تحقیق درباره روش نلدرميد

دانلود تحقیق و مقاله رایگان با عنوان تحقیق درباره روش نلدرميد

تحقیق درباره روش نلدرميد
در سال 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.5×1)sin(0.7x2x1)

x1,x2Î[0,5]

f2(x1,x2)=(4-2.1×12+x12)x12+x1 x2+(-4+4×22)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) ناميده مي‌شود كه نياز به حساسيت و ساختار مورد استفاده‌ي كامپيوتر ندارد و بهينه هاي موضعي كه شامل بهينه ي كلي است را با افزايش احتمال كه با افزايش دفعات محاسبه انجام پذير است را تعيين مي‌كند.

---