روش جستجوی فیبوناچی
به یاد بیاورید که روش جستجوی طلایی در سراسر روش از همان مقدار P استفاده می نماید. حالا فرض کنید که ما مجاز به تغییر مقدارP از هر مرحله به مرحله دیگر باشیم به طوری که در مرحله k ام در روند کاهش، از مقدار Pk ، در مرحله بعدی از Pk+1 و به همین ترتیب باشیم.
روش جستجوی فیبوناچی
همانطور که در بخش جستجو طلایی گفته شد، هدف ما انتخاب مقادیر متوالی از Pk است به طوری که 0< Pk < 1/2 قرار داشته باشد که منجر به تنها یک تابع ارزیابی جدید در هر مرحله می گردد. جهت بدست آوردن استراتژی مناسب برای انتخاب نقاط ارزیابی، شکل زیر را در نظر بگیرید. در این شکل مشاهده می کنیم که کافی است نقطه Pk را طوری انتخاب نماییم که شرط زیر در آن برقرار باشد:
Pk+1(1-Pk) = 1-2pk
بعد از چندین محاسبه، به فرمول زیر خواهیم رسید:
Pk+1 = 1 – ( Pk / 1 – Pk )
دنباله های بسیاری P1, P2, … وجود دارد که شرط فوق در آنها برقرار است به شرطی که Pk در بازه 0< Pk < 1/2 قرار داشته باشد.
P3 =… = (3 – √5) /2 در شرایط فوق صدق نموده و بهبودی در روش جستجوی طلایی ایجاد می نماید. حال فرض کنید که ما یک دنباله از P1, P2, … داده می شود که شرط های فوق را راضی می نماید و ما از این الگوریتم جستجو در این دنباله استفاده می نماییم. سپس، پس از N بار تکرار الگوریتم، محدوده عدم قطعیت توسط عامل (1- P1) … (1-PN) کاهش می یابد.
بسته به نوع دنباله P1, P2, …، ما عامل کاهش متفاوتی را بدست خواهیم آورد. حال این سوال به ذهن ما خطور می نماید که کدام دنباله P1, P2, … عامل کاهش بالا را به حداقل می رساند؟ این مساله یک مسئله بهینه سازی محدود است که می تواند به طور زیر عنوان گردد:
Min (1- P1) … (1-PN)
S.to Pk+1 = 1 – (Pk / 1 – Pk), k = 1… N -1
0< Pk < 1/2, k = 1… N
قبل از پاسخ دادن به مساله بهینه سازی فوق، ابتدا لازم است دنباله فیبوناچی F1, F2, …را تعریف نماییم. این دنباله به صورت زیر تعریف می گردد. ابتدا با توجه به تعریف مقادیر F-1 =0 , F0 = 1 تعیین می شود. سپس برای هر مقدار k≥0
Fk+1 = Fk + Fk-1
برخی از مقادیر عناصر در روش فیبوناچی به صورت زیر می باشد:
| F8 | F7 | F6 | F5 | F4 | F3 | F2 | F1 |
| 34 | 21 | 13 | 8 | 5 | 3 | 2 | 1 |
حال معلوم است که راه حل مساله بهینه سازی بالا به شرح زیر است:
P1 = 1 – (FN / FN+1), P2 = 1 – (FN -1/ FN) … Pk = 1 – (FN-k+1 / FN-k+2), P1 = 1 – (F1 / F2)
که Fk عناصر دنباله فیبوناچی می باشند. به الگوریتم فوق روش جستجوی فیبوناچی گفته می شود. در روش جستجوی فیبوناچی محدوده عدم قطعیت بوسیله عامل زیر کاهش می یابد:
(1- P1) … (1-PN) = (FN / FN+1)*(FN -1/ FN) … (F1 / F2) = F1 / FN+1 = 1 / FN+1
از آنجا که روش فیبوناچی از مقادیر مطلوب P1, P2, … استفاده می نماید، عامل کاهش دهنده فوق از روش جستجوی طلایی کمترخواهد بود. به عبارت دیگر، روش فیبوناچی بهتر از روش جستجوی طلایی می باشد چرا که طیف عدم قطعیت نهایی را کوچکتر می نماید.
این نکته قابل ذکر اشاره است که یک ناهنجاری در تکرار پایانی روش جستجو فیبوناچی وجود دارد ، زیرا
PN = 1 – (F1 / F2) = 1/2.
به یاد بیاورید که ما به دو نقطه میانی در هر مرحله نیاز داریم، یکی که از تکرار قبلی و دیگری با ارزیابی نقطه جدید بدست می آید. با این حال، با PN =1/2، دو نقطه میانی همزمان در وسط فاصله عدم قطعیت بدست آمده و در نتیجه نمی توانیم محدوده عدم قطعیت را بیشتر کاهش دهیم. برای رفع این مشکل، ما یک ارزیابی جدید برای آخرین تکرار با استفاده از PN =1/2 – e انجام می دهیم که در آن e مقدار کمی می باشد. به عبارت دیگر، نقطه های جدید ارزیابی نزدیک به سمت چپ یا راست از نقطه میانی فاصله عدم قطعیت قرار خواهند گرفت. این تغییر در روش فیبوناچی، تغییر قابل توجهی در نتیجه عملی به همراه نخواهد داشت.
به عنوان یک نتیجه از تغییر بالا، کاهش عدم قطعیت در آخرین تکرار ممکن است یکی از دو حالت
1 – PN =1/2 یا PN =1 – (PN – e) = 1/2 + e = (1 +2e)/2
بسته به این که کدام یک از دو نقطه مقدار تابع هدف کوچکتری دارد، باشد. بنابراین در بدترین حالت، عامل کاهش دهنده در محدوده عدم قطعیت برای روش فیبوناچی برابر با مقدار زیر خواهد بود:
(1 +2e)/ FN+1