روش جستجوی طلایی از روش های برنامه ریزی غیرخطی تک متغیره

بهینه‌سازی، فرآیندی حیاتی در بسیاری از رشته‌های علمی و مهندسی است. هدف از بهینه‌سازی، یافتن بهترین راه حل برای یک مسئله با توجه به محدودیت‌ها و قیود موجود است. در این میان، روش جستجوی طلایی به عنوان یک ابزار قدرتمند و کارآمد و یکی از انواع روش های جستجوی غیرخطی برای حل مسائل بهینه‌سازی تک‌بعدی شناخته می‌شود. این روش، با استفاده از نسبت طلایی، به طور سیستماتیک فضای جستجو را پیمایش کرده و به سمت کمینه (یا بیشینه) تابع هدف حرکت می‌کند.

در این مقاله، به بررسی عمیق روش جستجوی طلایی خواهیم پرداخت. ابتدا مفاهیم پایه و اصول این روش را توضیح می‌دهیم، سپس الگوریتم آن را به طور گام به گام شرح می‌دهیم. در ادامه، مزایا و معایب روش Golden Search را بررسی کرده و کاربردهای آن را در زمینه‌های مختلف معرفی می‌کنیم. در نهایت، این روش را با سایر روش‌های بهینه‌سازی مقایسه کرده و نکات و ترفندهای بهبود عملکرد آن را ارائه می‌دهیم.

آنچه می خوانید

هدف از این مقاله، ارائه یک راهنمای جامع و کاربردی برای دانشجویان و علاقه‌مندان به بهینه‌سازی است. با مطالعه این مقاله، شما قادر خواهید بود روش جستجوی طلایی را درک کرده و از آن برای حل مسائل بهینه‌سازی تک‌بعدی استفاده کنید.

روش جستجوی طلایی چیست؟

روش جستجوی طلایی یک روش عددی برای یافتن حداقل یا حداکثر یک تابع تک متغیره در یک بازه مشخص است. این روش از نسبت طلایی (0.618) برای تقسیم بازه جستجو به دو قسمت استفاده می کند.

روش های جستجویی که ما در این بخش و بخش بعدی مورد بحث قرار می دهیم به منظور تعیین کمینه تابع f: R-> R بر روی بازه بسته بکار می رود به طوری که [a₀ ,b₀] . تنها ویژگی که ما برای تابع هدفf فرض می نماییم تک مدی بودن آن است، به این معنی که f فقط داری یک مینیمم محلی است. مثالی از چنین تابعی در شکل روبرو نشان داده شده است.

روش جستجوی طلایی

مفاهیم پایه و اصول روش جستجوی طلایی

روش جستجوی طلایی یک الگوریتم بهینه‌سازی تک‌بعدی است که برای یافتن کمینه (یا بیشینه) یک تابع پیوسته و یک‌متغیره استفاده می‌شود. این روش بر اساس اصل “تقسیم و غلبه” (Divide and Conquer) عمل می‌کند، به این معنی که فضای جستجو را به طور مکرر به بخش‌های کوچکتر تقسیم می‌کند تا به سمت راه حل بهینه همگرا شود.

مفهوم اصلی روش Golden Search استفاده از نسبت طلایی (Golden Ratio) است که تقریباً برابر با 1.618 است. این نسبت در ریاضیات و طبیعت به طور گسترده‌ای یافت می‌شود و خواص منحصر به فردی دارد که آن را برای بهینه‌سازی مناسب می‌سازد. در روش جستجوی طلایی، نسبت طلایی برای تعیین نقاط آزمایشی در بازه جستجو استفاده می‌شود.

اساس کار روش جستجوی طلایی بر این اصل استوار است که با ارزیابی تابع هدف در دو نقطه آزمایشی که با استفاده از نسبت طلایی تعیین شده‌اند، می‌توان بازه جستجو را به طور موثرتری کاهش داد. این فرآیند تا زمانی که به یک نقطه همگرایی برسیم (یعنی تغییرات تابع هدف در بازه جستجو بسیار کوچک باشد) تکرار می‌شود.

الگوریتم حل روش جستجوی طلایی

روش جستجوی طلایی در مورد ارزیابی تابع هدف در نقاط مختلف بازه [a₀ ,b₀] می باشد. این نقاط را چنان انتخاب می نماییم که یک تقریب ممکن به نقطه کمینه را با چند ارزیابی ممکن به دست آورد . هدف محدود کردن تدریجی دامنه با دقت کافی به منظور قرار گرفتن کمینه در بازه مد نظر می باشد.

تابع تک مدی f را با یک متغیر و بازه [a₀ ,b₀] در نظر بگیرید. اگر f را فقط در یک نقطه میانی از بازه در نظر بگیریم قادر نخواهیم بود در میان این طیف گسترده کمینه را قرار دهیم لذا باید به منظور ارزیابی f تابع را در دو نقطه میانی همانطور که در شکل زیر نشان داده شده است در نظر بگیریم.

نقاط میانی را چنان انتخاب می نماییم که کاهش در محدوده متقارن باشد، به این معنا که

a₁ – a₀ = b₀ – b₁ = p (b₀ – a₀) به طوری که p< 0.5

سپس به ارزیابی تابع f در نقطه میانی می پردازیم. اگر f(a₁)<f(b₁) باشد، کمینه در بازه [a₀, b₁] نهفته است.

از سوی دیگر، اگر (f(a₁)≥f(b₁ باشد، کمینه در بازه [a₁, b₀] قرار گرفته است. درادامه با کاهش دامنه عدم قطعیت، ما می توانیم این روند را تکرار و به همین ترتیب دو نقطه جدید a₂ و b₂ را با مقدار p=0.5 پیدا نماییم. در عین حال، ما علاقمندیم که تعداد ارزیابی تابع هدف را در حالی که بازه عدم قطعیت را کاهش می دهیم کمینه نماییم.

برای مثال فرض کنید که (f(a₁)<f(b₁ باشد. ما می دانیم نقطه بهینه x* متعلق به بازه [a₀, b₁] خواهد بود. از آنجا که a₁ در حال حاضر در فاصله عدم اطمینان است و f تابعی شناخته شده، می توانیم a₁ را با b₂ یکی و منطبق بر هم در نظر بگیریم. بنابراین، تنها یک ارزیابی جدید از تابع f در نقطه a₂ ضروری خواهد بود. برای پیدا کردن مقدار p که منجر به تنها یک ارزیابی جدید گردد شکل زیر را مشاهده نمایید.

بدون از دست دادن کلیت، تصور کنید که محدوده اصلی [a₀ ,b₀] طول واحد است. لذا به منظور داشتن تنها یک ارزیابی از f کافی است که p مناسب را انتخاب نماییم.

P (b₁– a₀) = b₁ – b₂

از آنجایی که مقدار b₁ – b₀ = 1- p و مقدار b₁ – b₂ = 1 -2p می باشد، لذا خواهیم داشت:

P (1 – p) = 1 – 2p *

تابع درجه دوم عبارت فوق را به صورت زیر می نویسیم:

P²‑3p+1=0 -> p1 = (3+√5)/2 , p2 = (3-√5)/2

از آنجایی که مقدار p<0.5 را نیاز خواهیم داشت مقدار p2 =0.382 را در نظر می گیریم. با جایگزینی مقدار تابع در عبارت * مشاهده می کنیم که p/(1-P) = (1-p)/1 خواهد بود. از این عبارت در یونان باستان به عنوان قانون طلایی یاد شده است.

1-p=0.618031

کاهش می یابد. از این رو، N مرحله کاهش با استفاده از روش طلایی با نرخ زیر کاهش خواهد یافت:

(1 – p)^N = (0.61803)^N

مزایای روش جستجوی طلایی

روش جستجوی طلایی یک روش عددی برای یافتن حداقل یا حداکثر یک تابع تک متغیره در یک بازه مشخص است. این روش از مزایای زیر برخوردار است:

سادگی:

روش Golden Search بسیار ساده و قابل فهم است.
پیاده سازی آن در برنامه های کامپیوتری آسان است.
نیاز به دانش ریاضی پیچیده ای ندارد.

عدم نیاز به مشتق:

برخلاف برخی روش های دیگر مانند روش نیوتن-رافسون، روش جستجوی طلایی نیازی به مشتق تابع ندارد.
این مزیت در مواردی که محاسبه مشتق تابع دشوار یا غیرممکن است، بسیار مفید است.

همگرایی:

روش Golden Search به طور همگرا به نقطه بهینه نزدیک می شود.
به عبارت دیگر، با تکرار مراحل روش، به تدریج به نقطه ای می رسیم که تابع در آن نقطه به حداقل یا حداکثر خود می رسد.

قابلیت اطمینان:

روش جستجوی طلایی یک روش قابل اعتماد و robust است.
این روش در بسیاری از مسائل مختلف به طور موفقیت آمیز به کار گرفته شده است.

معایب روش جستجوی طلایی

روش جستجوی طلایی، مانند هر روش دیگری، معایبی هم دارد که باید قبل از استفاده از آن در نظر گرفته شود:

سرعت:

روش Golden Search کندتر از برخی روش های دیگر مانند روش نیوتن-رافسون است.
این روش از نظر سرعت بهینه نیست و ممکن است برای حل مسائل پیچیده زمان زیادی را صرف کند.

دقت:

دقت روش جستجوی طلایی به طور کلی کمتر از روش های دیگر مانند روش نیوتن-رافسون است.
این روش ممکن است برای یافتن دقیق نقطه بهینه مناسب نباشد.

محاسبات:

روش جستجوی طلایی به محاسبات بیشتری نسبت به برخی روش های دیگر مانند روش تنظیم خطی نیاز دارد.
این امر می تواند در مسائل بزرگ و پیچیده مشکل ساز باشد.

محدودیت به توابع تک متغیره:

روش جستجوی طلایی فقط برای توابع تک متغیره قابل استفاده است.
برای توابع چند متغیره باید از روش های دیگر مانند روش های گرادیان یا روش های تکرار نقطه ثابت استفاده کرد.

محدودیت به بازه جستجو:

روش جستجوی طلایی فقط در یک بازه جستجو مشخص قابل استفاده است.
یافتن بازه جستجو مناسب می تواند دشوار باشد و بر دقت و کارایی روش تاثیر بگذارد.

در مجموع، روش جستجوی طلایی یک روش ساده و قابل فهم است، اما سرعت و دقت آن به اندازه برخی روش های دیگر مانند روش نیوتن-رافسون نیست.

کاربردهای روش جستجوی طلایی

روش جستجوی طلایی، به دلیل مزایای ذکر شده، در زمینه های مختلف کاربرد دارد.

برخی از کاربردهای این روش عبارتند از:

یافتن ریشه معادلات غیرخطی: روش Golden Search می تواند برای یافتن ریشه معادلات غیرخطی تک متغیره به کار رود.
بهینه سازی توابع: از این روش می توان برای یافتن حداقل یا حداکثر توابع تک متغیره در مسائل مختلف مهندسی و علمی استفاده کرد.
مسائل مالی: روش Golden Search در مسائل مالی مانند تحلیل سهام، مدیریت ریسک و قیمت گذاری اوراق قرضه کاربرد دارد.
مهندسی: از این روش در مهندسی برای حل مسائل مختلفی مانند طراحی سازه ها، تحلیل سیستم ها و کنترل فرآیندها استفاده می شود.
علوم کامپیوتر: روش جستجوی طلایی در علوم کامپیوتر برای حل مسائل مختلفی مانند هوش مصنوعی، یادگیری ماشین و پردازش تصویر کاربرد دارد.

چند نمونه از کاربردهای روش جستجوی طلایی در دنیای واقعی

طراحی آنتن: از روش Golden Search برای یافتن بهترین ابعاد و شکل آنتن برای حداکثر رساندن قدرت سیگنال استفاده می شود.
طراحی موتور هواپیما: از این روش برای یافتن بهترین شکل و ابعاد پره های موتور هواپیما برای افزایش راندمان و کاهش مصرف سوخت استفاده می شود.
طراحی ربات: از روش Golden Search برای یافتن بهترین پارامترهای کنترلی ربات برای انجام وظایف مختلف استفاده می شود.
تشخیص چهره: از این روش برای یافتن بهترین ویژگی های چهره برای تشخیص چهره افراد استفاده می شود.

در مجموع، روش جستجوی طلایی یک روش قدرتمند و انعطاف پذیر است که در طیف وسیعی از مسائل مختلف کاربرد دارد. در ادامه می توانید مثال روش جستجوی طلایی را مشاهده نمایید.

مثال روش جستجوی طلایی

در ادامه مثال روش جستجوی طلایی را تشریح می نماییم. می خواهیم با استفاده از روش Golden Search نقطه x را طوری تعیین نماییم که تابع هدف f(x) = x⁴-14x³+60x²-70x را در بازه [0, 2] کمینه نماید. طول بازه را 0.3 در نظر بگیرید.

گام های حل مثال روش Golden Search

به منظور یافتن تعداد تکرار جهت کمینه شدن از فرمول فوق استفاده می نماییم:

(0.3/2) = (0.61803)^N-> N =4 تعداد تکرار

تکرار اول:

تابع f را در دو نقطه میانی a₁ و b₁ در نظر می گیریم. خواهیم داشت:

a₁ = a₀ + p (b₀ –a₀) = 0.7639

b₁ = a₀ + p (1 – p) (b₀ –a₀) = 1.236

مقدار p = (3-√5)/2 پس

f (a₁) = -24.36 f(b₁) = -18.96

تکرار دوم:

از آنجایی که مقدار f(a₁) < f(b₁) است، لذا بازه عدم قطعیت کاهش یافته و برابر [a₀ ,b₁] = [0, 1.236] خواهد بود.

نقطه b2 را به عنوان نقطه منطبق با a1 در نظر می گیریم لذا تنها به ارزیابی در یک نقطه جدید نیاز خواهیم داشت:

a₂ = a₀ + p (b₁ –a₀) = 0.4721

f (a₂) = -21.10 f(b₂) = f(a₁) = -24.36

از آنجایی که مقدار f(b₂) < f(a₂) است، لذا بازه عدم قطعیت کاهش یافته و برابر [a₂ ,b₁] = [0.4721, 1.236] خواهد بود.

تکرار سوم:

نقطه a3 را به عنوان نقطه منطبق با b2 در نظر می گیریم لذا تنها به ارزیابی در یک نقطه جدید نیاز خواهیم داشت:

b₃ = a₂ +(1- p) (b₁ –a₂) = 0.9443

f (a₃) =f (b₂) = -24.36 f(b₂) = f(a₁) = -23.59

از آنجایی که مقدار f(b₃) > f(a₃) است، لذا بازه عدم قطعیت کاهش یافته و برابر [a₂ ,b₃] = [0.4721, 0.9443] خواهد بود.

تکرار چهارم:

نقطه .b4 = a3

a₄ = a₂ + p (b₃ –a₂) = 0.6525

f (a₄) = -23.84 f(b₄) = f(a₃) = -24.36

از آنجایی که مقدار f(a₄) > f(b₄) است، لذا بازه عدم قطعیت کاهش یافته و برابر [a₂ ,b₃] = [0.6525, 0.9443] خواهد بود.با محاسبه مقدار زیر

b3 – a4 = (0.9443 – 0.6525) => 0.292

مشاهده می کنیم که مقدار بدست آمده کمتر از 3 می باشد و ما به نقطه مورد نظر رسیدیم.

دانلود فیلم آموزشی، فایل اکسل و کد متلب روش جستجوی طلایی

مقایسه روش جستجوی طلایی با سایر روش‌های بهینه‌سازی

روش جستجوی طلایی را می‌توان با سایر روش‌های بهینه‌سازی تک‌بعدی مانند جستجوی دودویی (Binary Search) مقایسه کرد. جستجوی دودویی نیز یک روش تقسیم و غلبه است، اما به جای نسبت طلایی از تقسیم بازه به دو نیمه مساوی استفاده می‌کند. روش جستجوی طلایی معمولاً از جستجوی دودویی کارآمدتر است، زیرا در هر مرحله بازه جستجو را به طور موثرتری کاهش می‌دهد.

همچنین، روش جستجوی طلایی را می‌توان با روش‌های بهینه‌سازی مبتنی بر گرادیان (Gradient-Based Optimization) مقایسه کرد. روش‌های مبتنی بر گرادیان از مشتق تابع هدف برای یافتن جهت حرکت به سمت کمینه استفاده می‌کنند. روش جستجوی طلایی نیازی به مشتق‌گیری ندارد، که این امر آن را برای توابعی که مشتق‌گیری از آنها دشوار یا غیرممکن است، مناسب می‌سازد.

نکات و ترفندهای بهبود عملکرد روش جستجوی طلایی

برای بهبود عملکرد روش جستجوی طلایی، می‌توان از چند نکته و ترفند استفاده کرد. یکی از مهم‌ترین نکات، تعیین یک بازه اولیه مناسب است. بازه اولیه باید به گونه‌ای انتخاب شود که تابع هدف در آن بازه کمینه (یا بیشینه) داشته باشد.

همچنین، می‌توان از تکنیک‌های کاهش نرخ یادگیری (Learning Rate Decay) استفاده کرد. این تکنیک‌ها به طور تدریجی نرخ یادگیری را کاهش می‌دهند، که این امر می‌تواند به بهبود همگرایی روش جستجوی طلایی در مسائل پیچیده کمک کند.

ترکیب روش جستجوی طلایی با سایر روش‌های بهینه‌سازی نیز می‌تواند عملکرد آن را بهبود بخشد. به عنوان مثال، می‌توان از روش جستجوی طلایی برای یافتن یک تخمین اولیه از راه حل بهینه استفاده کرد و سپس از یک روش بهینه‌سازی پیچیده‌تر برای بهبود این تخمین استفاده کرد.

نتیجه‌گیری

روش جستجوی طلایی یک روش بهینه‌سازی تک‌بعدی قدرتمند و کارآمد است که در زمینه‌های مختلفی کاربرد دارد. این روش به دلیل سادگی پیاده‌سازی، کارآمدی در مسائل تک‌بعدی و عدم نیاز به مشتق‌گیری، به یک ابزار ارزشمند برای حل مسائل بهینه‌سازی تبدیل شده است.

امیدواریم این مقاله به شما در درک و استفاده از روش جستجوی طلایی کمک کرده باشد. با تسلط بر این روش، شما قادر خواهید بود مسائل بهینه‌سازی تک‌بعدی را به طور موثرتری حل کنید و به نتایج بهتری دست یابید. روش جستجوی طلایی ابزاری ارزشمند در جعبه ابزار هر مهندس و دانشمندی است.

اگر به مباحث بهینه‌سازی و تحقیق در عملیات علاقه‌مند هستید، پیشنهاد می‌شود در کنار این مقاله، مطالب مرتبطی مانند روش گرادیان، روش تندترین شیب، روش جستجوی فیبوناچی، روش سکانت، روش نیوتن رافسون و انواع روش‌های جستجوی خطی را نیز مطالعه کنید. این روش‌ها از مهم‌ترین الگوریتم‌های بهینه‌سازی هستند و شناخت تفاوت‌ها، مزایا و کاربردهای هر یک، در انتخاب مناسب‌ترین تکنیک برای حل مسائل مختلف نقش مهمی دارد.

همچنین برای آشنایی با سایر روش‌های تصمیم‌گیری و بهینه‌سازی، مطالعه مقالات روش LINMAP و روش تبادل و جانشینی نیز توصیه می‌شود. این مطالب به درک بهتر الگوریتم‌های بهینه‌سازی، روش‌های جستجو و تکنیک‌های حل مسائل پیچیده در تحقیق در عملیات کمک کرده و دید جامع‌تری نسبت به ابزارهای موجود در اختیار شما قرار می‌دهند.