همچنین در تحقیقات دیگری [۴]، این پیشنهاد مطرح شده است که این واریانس نویز باید عدم قطعیت یک موفقیت را دنبال کند و تغییرات آن می تواند نقش مهمی را در بهینهسازی رفتار انتخاب بازی کند. علاوه بر این نشان داده شده که اگر مقدار هدف G، به صورت پویا کنترل گردد، می تواند هزینه تلاشها را بهینه سازد [۵].
در حقیقت، نویز و مقدار هدف به ترتیب عرض و عمق جستجو برای یافتن یک راهحل را کنترل می کنند. برای پی بردن به علت نیاز به داشتن احتمال موفقیت P و مقدار هدف G و هزینه C، فرض کنید که هزینه رسیدن به هدف (C)، یک متغیر تصادفی باشد و احتمال آنکه هدف با هزینه C بدست آید (احتمال آنکه هزینه دقیقاً برابر با C باشد). در این صورت امید ریاضی هزینه برابر است:
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
(۲-۲)
تابع توزیع برابر است با احتمال موفقیت برای هر هزینهایی. دانش توابع توزیع برای تصمیمات مختلف، این امکان را برای حلکننده مسئله فراهم میسازد تا هزینه های پیش بینی شده را محاسبه و بهترین قانون (استراتژی) را برای حل مسئله انتخاب نماید.
البته مشکل در این موقعیت، در حل مسئله برای اولین بار و نداشتن هیچگونه اطلاعاتی در زمینه میباشد. تنها راه ممکن برای تعیین این توزیعها، سعی در حل مسئله با بهره گرفتن از استراتژی های گوناگون میباشد. در این صورت سوالی که مطرح می شود این است که کی یک استراتژی را رها کنیم و به سراغ استراتژی دیگری برویم. این ویژگی، یعنی توانایی رهاکردن راهحلهایی با امید کمتر برای حل مسئله بدون اینکه آنها را به طور کامل بررسی کنیم (بدون آنکه آنها را تا انتها پیش ببریم)، یکی از ویژگیهای انسان در حل مسئله است. در بهبودی که بر این روش مطرح شده، به این سوال پاسخ داده شده است. بخش ۲-۴ به شرح این شیوه بهبود یافته می پردازد.
رفع ناسازگاری با بهره گرفتن از هزینه های تخمین زده شدهی تصادفی
یکی از مهمترین مشخصههای الگوریتمی که در بهبود روش قبلی مطرح شده [۲]، این است که دقیقاً مشخص میسازد که یک راهحل تا چه عمقی بررسی گردد.
برای توضیح این روش رفع ناسازگاری، ابتدا حل مسئله به عنوان مشاهدهایی[۱۹] از یک روند پواسن شرح داده می شود. فرض کنید که یک کامپیوتر تعدادی مسئله را با بهره گرفتن از یک الگوریتم مشخص حل می کند و هر بار پس از دستیابی به حالت هدف، کامپیوتر دوباره راه اندازی شده[۲۰] و مجدداً به حل مسئله می پردازد. حال اگر امید ریاضی هزینه یا هزینه مورد انتظار راهحلی که کامپیوتر از آن استفاده می کند برابر با باشد، آنگاه ما حالت هدف را هر ثانیه و یا با نرخ مشاهده خواهیم کرد که در این صورت میتوان رویداد حالت هدف را تحت یک روند پواسن بررسی نمود. در نتیجه احتمال مشاهده n رویداد در مدت زمان t برابر است با:
(۲-۳)
که در این رابطه نرخ مقدار میانگین[۲۱] نامیده می شود و برابر است با ،
و تعداد مشاهدات رویداد تا زمان t میباشد .
شکل۲-۱٫ یک کامپیوتر که یک الگوریتم را در یک حلقه اجرا می کند. وضعیت هدف با نرخ مشاهده میگردد که امید ریاضی هزینه (هزینه مورد انتظار) میباشد.
برطبق رابطه (۲-۳)، هنگامی که (یا ) باشد، احتمال برای هر t، برابر با صفر خواهد بود که متناظر است با حالتی که رویداد غیرممکن باشد. بنابراین، برای اینکه یک رویداد امکان پذیر باشد، باید (یا ). از اینرو در حل یک مسئله با یک نگاه خوشبینانه که فرض بر ممکن بودن حالت هدف است، داریم:
(۲-۴)
حال به بررسی برخی از موارد خاص از احتمال پواسن (رابطه (۲-۳)) میپردازیم:
احتمال شکست[۲۲]: احتمال اینکه رویداد رخ ندهد ، که برطبق رابطه (۲-۳) این احتمال برابر است با:
(۲-۵)
این تابع به صورت یک منحنی نزولی با خط تیره در شکل ۲-۲ نشان داده شده است.
احتمال موفقیت[۲۳]: احتمال اینکه رویداد حداقل یکبار رخ دهد :
(۲-۶)
این تابع به صورت یک منحنی با خط تیره در شکل ۲-۲ نشان داده شده است. این نمودار در صورتی که با زمان افزایش مییابد.
هنگامی که یک مسئله مخصوصاً برای اولین بار حل می شود، آنچه که در این روش مد نظر است اولین رخداد حالت هدف میباشد. بعلاوه، در اغلب موارد نیازی به حل مجدد مسئلهایی دقیقاً مانند مسئله قبل نیست. بنابراین، در این روش، مطلوب، احتمال اولین موفقیت میباشد.
احتمال اولین موفقیت: احتمال آنکه رویداد، دقیقاً یکبار رخ دهد که برابر است با:
(۲-۷)
این تابع به صورت یک منحنی با خط پیوسته در شکل ۲-۲ نشان داده شده است. این منحنی تا هنگامی که به یک مقدار بیشینه قطعی برسد، برحسب زمان افزایش و پس از آن کاهش مییابد.
شکل۲-۲٫ احتمال شکست که با زمان کاهش مییابد، احتمال موفقیت که با زمان افزایش مییابد و احتمال اولین موفقیت که دارای یک مقدار بیشینهی یکتا در میباشد.
برای بدست آوردن زمان[۲۴] متناظر با مقدار بیشینهی احتمال اولین موفقیت، داریم:
(۲-۸)
=>
این مقدار متناظر است با امید ریاضی هزینه . در این نقطه احتمال اولین موفقیت برابر است با احتمال شکست:
,
(۲-۹)
همانطور که مشاهده می شود برای یک سیستم با دو خروجی (اولین موفقیت و متمم آن)، این زمان متناظر با هنگام بیشترین بینظمی است و در نتیجه بهترین زمان برای بدست آوردن یک تخمین جدید برای با بهره گرفتن از اطلاعات جدید میباشد. اگر این تخمین جدید بسیار بزرگتر از مقدار مورد انتظار، از کار در آید، ممکن است زمان بهینه برای تغییر استراتژی و یا رها کردن نیز باشد.
تخمین امید ریاضی هزینه
در واقعیت، در هنگام حل یک مسئله، نرخ مجهول است و آنچه که ما سعی در تخمین آن داریم، امید ریاضی هزینه یا هزینه مورد انتظار میباشد. در این موقعیت، تعداد موفقیتها n و نیز مقدار زمان (یا هزینه) سپری شده، معلوم هستند. حال برای تخمین نرخ (و در ادامه )، با فرض اینکه n تعداد موفقیتها پس از سپری شدن زمان t باشد، میتوان از احتمال پسین[۲۵] که از طریق فرمول بیز قابل محاسبه است، استفاده نمود:
(۲-۱۰)
هنگامی که احتمال پیشین تمامی مقادیر مساوی باشد، آنگاه احتمال درستنمایی[۲۶] با بهره گرفتن از توزیع پواسن (رابطه ۲-۳) شرح داده می شود و احتمال پسین می تواند از طریق درستنمایی بدست آید:
(۲-۱۱)
حال با بهره گرفتن از رابطه فوق برای احتمال پسین، میتوان برآورد میانگین پسین را محاسبه نمود:
(۲-۱۲)
و بنابراین .
این برآورد به سمت موفقیتها اریب[۲۷] بوده (خوشبینانه) و نسبت به برآورد مفیدتر است زیرا می تواند حتی هنگامی که هیچ موفقیتی هنوز مشاهده نشده است(n=0) نیز بکار رود. به همین دلیل الگوریتم خوشبین[۲۸] نامیده می شود.
برآورد بازگشتی
برای روشنتر شدن موضوع، مثال حل مسئله توسط یک کامپیوتر (شکل ۲-۱) را در نظر بگیرید، اما با یک تفاوت، امید ریاضی هزینه E© نامعلوم باشد.
هدف، راه اندازی مجدد کامپیوتر به گونهایی است که حالت هدف با بیشترین نرخ ممکن ظاهر گردد. فرض کنید فاصلهی زمانی باشد که پس از آن کامپیوتر راه اندازی مجدد می شود. اگر کامپیوتر بسیار دیر راه اندازی مجدد شود ، آنگاه واضح است که نرخ وقوع حالت هدف بالاترین حد ممکن نخواهد بود. از طرف دیگر، اگر کامپیوتر بسیار زود راه اندازی مجدد شود ، آنگاه در اغلب موارد کامپیوتر، زمان لازم برای اتمام حل مسئله را نخواهد داشت. فرض کنید در یک دنباله از آزمایشات، اولین رویداد حالت هدف در فواصل زمانی ثبت گردد، در این صورت اگر حالت هدف ثبت شده باشد، کامپیوتر باید پس از آن به سرعت راه اندازی مجدد گردد و در غیر این صورت، پس از مجدداً راه اندازی شود. همانطور که مشاهده می شود، این آزمایشات تنها دو خروجی ممکن خواهد داشت (آزمایشات دو جملهایی[۲۹]):
شکست: حالتی که در آن حالت هدف هنوز بدست نیامده و تعداد موفقیتها n تغییر نیافته است، که در این صورت کل تلاش (زمان) سپری شده با ، افزایش خواهد یافت.
موفقیت: حالتی که در آن حالت هدف بدست آمده و تعداد موفقیتها n یک واحد افزایش یافته است، که در این صورت کل تلاش (زمان) سپری شده با ، افزایش خواهد یافت.
با شمارش تعداد موفقیتها n و مجموعگیری از زمان سپری شده در k آزمایش ، میتوان برآوردی از امید ریاضی هزینه با بهره گرفتن از فرمول میانگین پسین بدست آورد:
(۲-۱۳)
رفع ناسازگاری
در بخش قبل، توضیحاتی در رابطه با بدست آوردن برآوررد هزینه یک استراتژی مشخص (الگوریتم، تصمیم و یا قانون) با بهره گرفتن از تخمین نرخ یک روند پواسن فرضی ارائه و برای شرح بیشتر موضوع مثالی از یک کامپیوتر که به منظور حل یک مسئله، در یک حلقهی بی پایان قرار دارد (شکل ۲-۱) مطرح گردید. در یک روند مشابه میتوان یک ناسازگاری را به صورت زیر توصیف نمود: یک انتخاب از میان تعداد بسیاری کامپیوتر مانند کامپیوتر مثال فوق که سعی در حل مسئله همسانی دارند، اما تنها با بهره گرفتن از یک کامپیوتر در یک زمان.
