دانلود رایگان
...
درباره سایت
دانلود رایگان
آخرین مطالب
امکانات وب
-->-->-->
-->-->-->
رویکردهای اصلی به کمینه سازی سراسری
در این زمینه گروههای زیر تشخیص داده می شوند:
• تکنیکهای پوشش دهنده (فضای) مجموعه
• روشهای جستجوی تصادفی
• الگوریتمهای تکاملی و ژنتیک
• روشهای مبنی بر جستجوهای محلی چندگانه (چند شروعه) با استفاده از خوشه بندی
• سایر روشها( آنیلینگ شبیه سازی شده، تکنیکهای خط سیر، رویکرد تونل سازی، روشهای تحلیلی بر پایه مدل احتمالی تابع هدف)
• روشهای پوششی (فضای مجموعه).در این حالت فضای پارامتری X ، با N زیرمجموعهء X1,…,XN پوشانده می شود به نحوی که اجتماع آنها کل X را پوشش دهد. پس تابع هدف در N نقطه {x1,…,xN} که هرکدام یک زیرمجموعه را نشان می دهند ارزیابی می گردد و نقطه ای با کوچکترین مقدار تابع، به عنوان تقریبی از مقدار سراسری درنظر گرفته می شود. اگر کل نقاط قبلی انتخاب شده {x1,…,xk} و مقادیر تابع {f(x1),…,f(xk)} در زمان انتخاب نقطه بعدی xk+1 به کارروند، الگوریتم ، پوششی (فعال) متوالی نامیده می شود (و اگر وابستگی موجود نباشد، غیرفعال است) . این الگوریتمها کارا نیستند.
• جستجوی تصادفی مستقیم خالص (نمونه برداری یکنواخت) . N نقطه با توزیع یکنواخت در X انتخاب می شود و تابع f روی آنها ارزیابی می گردد، کمترین مقدار تابع، ارزیابی f* کمینه است. اگر f پیوسته باشد، ضمانت همگرایی مجانبی وجود دارد ولی تعداد ارزیابی تابع نسبت به n به طور نمایی رشد می کند. یک بهبود این است که تولید نقاط ارزیابی به نحو متوالی انجام شود که مقادیر تابع شناخته شده از قبل را در زمان انتخاب نقطه بعدی به حساب آورد، تا یک جستجوی تصادفی تطبیقی تولید شود.
• جستجوی تصادفی کنترل شده (CRS). این روش متناظر با نام W.L.Price است که چندین نسخه از الگوریتم را پیشنهاد کرده که در آن نقطه آزمایشی جدید در فضای (پارامتری) جستجو، بر پایه زیرمجموعه انتخابی تصادفی از نقاط تولید شده قبلی، ایجاد می گردد. روشی که بسیار مورد استفاده قرار می گیرد CRC2 است. در هر تکرار، از یک نمونه یک Simplex تولید می گردد و نقطه آزمایشی جدید به عنوان بازتاب یک نقطه در مرکزثقل سایر نقاط در این Simplex تولید می شود. اگر بدترین نقطه در مجموعه تولید شده اولیه ، بدتر از نقطه جدید است، با آن جایگزین می شود. ایده الگوریتم های CRS بعدها به صورت CRS4 و CRS5 گسترش پیدا کرد. در CRS4 اگر بهترین نقطه جدید یافت شود، یک جستجوی اضافه در اطراف آن توسط نقاط نمونه برداری شده از توزیع بتا به عنوان جایزه انجام می شود. این روش بسیار کارامد گزارش شده است.
• استراتژی های تکاملی و الگوریتمهای ژنتیک. خانواده الگوریتم های تکاملی برپایه ایده مدلسازی فرایند جستجوی تکاملی طبیعت قرار دارند گرچه این مدلها ساده سازی خام واقعیت بیولوژیکی است. الگوریتم های تکاملی، تغییراتی از جستجوی تصادفی هستند و اصطلاحات ژنتیک و زیست شناسی را به کار می برند. به طور مثال، برای هر نمونه تصادفی در هر تکرار، جفت افراد والد (نقاط) که بر پایه میزان شایستگی انتخاب می شوند (مقدار تابع)، مجددا ترکیب شده و فرزند جدیدی تولید می کنند . بهترین آنها برای نسل بعد انتخاب می شود. همچنین می تواند جهش یابد یعنی به طور تصادفی موقعیت خود را درفضا تغییر دهد . ایده این عمل آن است که والدین مناسب احتمالا فرزندان مناسب تری تولید می کنند. تولید نقطه تصادفی معادل جهش است و گام برداری به سوی کمینه بعد از آزمایش موفق به عنوان انتخاب درنظر گرفته می شود.
از لحاظ سابقه الگوریتم های تکاملی سه دسته هستند: استراتژی های تکاملی (ES) ، برنامه نویسی تکاملی (EP) و الگوریتم های ژنتیک (GA). آنها از لحاظ نوع عملگرهای جهش، ترکیب مجدد و انتخاب تفاوت عمده دارند. در GA کدگذاری باینری مولفه ها وجود دارد پس یک متغیر l بیتی برای نمایش کد صحیح مولفه xi به کار می رود که مقداری بین 0 تا دارد که می تواند به بازه صحیح [ai,bi] نگاشت شود. رشته باینری سراسری به طول nl به نام کروموزوم برای هر نقطه با اتصال کد همه مولفه ها ایجاد می شود. عملگر جهش، یک بیت را که به طور تصادفی در رشته G انتخاب شده با مکمل کردن تغییر می دهد. عملگر ترکیب (ادغام )، دو والد( نقطه) S و T را براساس قوانینی انتخاب کرده ، عدد را بین 1 و nl انتخاب کرده و سپس یا نقطه جدید s’ را می سازد یا نقاط جدید S’ و T’ را با نگهداشتن بیتهای سمت چپ مقادیر مولفه از والد و بیتهای سمت راست والد دیگر ، ایجاد می کند. در استراتژی های تکاملی جهش مولفه ها با توجه به تغییرات متناظر توزیع نرمال n بعدی مشخصی انجام می شود و نسخه های متعددی از ترکیب تعریف می گردد.
• شروع چندگانه و خوشه بندی. ایده اصلی روشهای چندآغازه ، چندین بار اعمال رویه جستجو و سپس انتخاب ارزیابی بهینه ساز سراسری است. یکی از نسخه های معمول آن براساس خوشه بندی است یعنی تولید گروههایی از نقاط جداگانه که امیدواریم با نواحی جذب شروع بالقوه متناظر باشند. منطقه جذب کمینه محلی x* ، مجموعه نقاطی از X است که با شروع از آنها، رویه جستجوی محلی P به x* همگرا می شود.
در روش پوشش خوشه بندی تطبیقی (ACCO) در مرحله اول از خوشه بندی و سپس از جستجوی تصادفی سراسری به جای جستجوی محلی استفاده می شود.
مراحل :
1. خوشه بندی
2. پوشش زیردامنه های کوچک شونده
3. تطبییق
4. تصادفی سازی تناوبی
ACCOL: ترکیب ACCO با چندین جستجوی محلی
ACD : ترکیب ACCO و سرازیری های Simplex رو به پایین
مرجع:
Genetic and other global optimization algorithms - comparison and use in calibration
problems
Proc. 3rd Inte. Conference on Hydroinformatics, Copenhagen, Denmark, 1998. Balkema Publishers. pp.1021-102
• تکنیکهای پوشش دهنده (فضای) مجموعه
• روشهای جستجوی تصادفی
• الگوریتمهای تکاملی و ژنتیک
• روشهای مبنی بر جستجوهای محلی چندگانه (چند شروعه) با استفاده از خوشه بندی
• سایر روشها( آنیلینگ شبیه سازی شده، تکنیکهای خط سیر، رویکرد تونل سازی، روشهای تحلیلی بر پایه مدل احتمالی تابع هدف)
• روشهای پوششی (فضای مجموعه).در این حالت فضای پارامتری X ، با N زیرمجموعهء X1,…,XN پوشانده می شود به نحوی که اجتماع آنها کل X را پوشش دهد. پس تابع هدف در N نقطه {x1,…,xN} که هرکدام یک زیرمجموعه را نشان می دهند ارزیابی می گردد و نقطه ای با کوچکترین مقدار تابع، به عنوان تقریبی از مقدار سراسری درنظر گرفته می شود. اگر کل نقاط قبلی انتخاب شده {x1,…,xk} و مقادیر تابع {f(x1),…,f(xk)} در زمان انتخاب نقطه بعدی xk+1 به کارروند، الگوریتم ، پوششی (فعال) متوالی نامیده می شود (و اگر وابستگی موجود نباشد، غیرفعال است) . این الگوریتمها کارا نیستند.
• جستجوی تصادفی مستقیم خالص (نمونه برداری یکنواخت) . N نقطه با توزیع یکنواخت در X انتخاب می شود و تابع f روی آنها ارزیابی می گردد، کمترین مقدار تابع، ارزیابی f* کمینه است. اگر f پیوسته باشد، ضمانت همگرایی مجانبی وجود دارد ولی تعداد ارزیابی تابع نسبت به n به طور نمایی رشد می کند. یک بهبود این است که تولید نقاط ارزیابی به نحو متوالی انجام شود که مقادیر تابع شناخته شده از قبل را در زمان انتخاب نقطه بعدی به حساب آورد، تا یک جستجوی تصادفی تطبیقی تولید شود.
• جستجوی تصادفی کنترل شده (CRS). این روش متناظر با نام W.L.Price است که چندین نسخه از الگوریتم را پیشنهاد کرده که در آن نقطه آزمایشی جدید در فضای (پارامتری) جستجو، بر پایه زیرمجموعه انتخابی تصادفی از نقاط تولید شده قبلی، ایجاد می گردد. روشی که بسیار مورد استفاده قرار می گیرد CRC2 است. در هر تکرار، از یک نمونه یک Simplex تولید می گردد و نقطه آزمایشی جدید به عنوان بازتاب یک نقطه در مرکزثقل سایر نقاط در این Simplex تولید می شود. اگر بدترین نقطه در مجموعه تولید شده اولیه ، بدتر از نقطه جدید است، با آن جایگزین می شود. ایده الگوریتم های CRS بعدها به صورت CRS4 و CRS5 گسترش پیدا کرد. در CRS4 اگر بهترین نقطه جدید یافت شود، یک جستجوی اضافه در اطراف آن توسط نقاط نمونه برداری شده از توزیع بتا به عنوان جایزه انجام می شود. این روش بسیار کارامد گزارش شده است.
• استراتژی های تکاملی و الگوریتمهای ژنتیک. خانواده الگوریتم های تکاملی برپایه ایده مدلسازی فرایند جستجوی تکاملی طبیعت قرار دارند گرچه این مدلها ساده سازی خام واقعیت بیولوژیکی است. الگوریتم های تکاملی، تغییراتی از جستجوی تصادفی هستند و اصطلاحات ژنتیک و زیست شناسی را به کار می برند. به طور مثال، برای هر نمونه تصادفی در هر تکرار، جفت افراد والد (نقاط) که بر پایه میزان شایستگی انتخاب می شوند (مقدار تابع)، مجددا ترکیب شده و فرزند جدیدی تولید می کنند . بهترین آنها برای نسل بعد انتخاب می شود. همچنین می تواند جهش یابد یعنی به طور تصادفی موقعیت خود را درفضا تغییر دهد . ایده این عمل آن است که والدین مناسب احتمالا فرزندان مناسب تری تولید می کنند. تولید نقطه تصادفی معادل جهش است و گام برداری به سوی کمینه بعد از آزمایش موفق به عنوان انتخاب درنظر گرفته می شود.
از لحاظ سابقه الگوریتم های تکاملی سه دسته هستند: استراتژی های تکاملی (ES) ، برنامه نویسی تکاملی (EP) و الگوریتم های ژنتیک (GA). آنها از لحاظ نوع عملگرهای جهش، ترکیب مجدد و انتخاب تفاوت عمده دارند. در GA کدگذاری باینری مولفه ها وجود دارد پس یک متغیر l بیتی برای نمایش کد صحیح مولفه xi به کار می رود که مقداری بین 0 تا دارد که می تواند به بازه صحیح [ai,bi] نگاشت شود. رشته باینری سراسری به طول nl به نام کروموزوم برای هر نقطه با اتصال کد همه مولفه ها ایجاد می شود. عملگر جهش، یک بیت را که به طور تصادفی در رشته G انتخاب شده با مکمل کردن تغییر می دهد. عملگر ترکیب (ادغام )، دو والد( نقطه) S و T را براساس قوانینی انتخاب کرده ، عدد را بین 1 و nl انتخاب کرده و سپس یا نقطه جدید s’ را می سازد یا نقاط جدید S’ و T’ را با نگهداشتن بیتهای سمت چپ مقادیر مولفه از والد و بیتهای سمت راست والد دیگر ، ایجاد می کند. در استراتژی های تکاملی جهش مولفه ها با توجه به تغییرات متناظر توزیع نرمال n بعدی مشخصی انجام می شود و نسخه های متعددی از ترکیب تعریف می گردد.
• شروع چندگانه و خوشه بندی. ایده اصلی روشهای چندآغازه ، چندین بار اعمال رویه جستجو و سپس انتخاب ارزیابی بهینه ساز سراسری است. یکی از نسخه های معمول آن براساس خوشه بندی است یعنی تولید گروههایی از نقاط جداگانه که امیدواریم با نواحی جذب شروع بالقوه متناظر باشند. منطقه جذب کمینه محلی x* ، مجموعه نقاطی از X است که با شروع از آنها، رویه جستجوی محلی P به x* همگرا می شود.
در روش پوشش خوشه بندی تطبیقی (ACCO) در مرحله اول از خوشه بندی و سپس از جستجوی تصادفی سراسری به جای جستجوی محلی استفاده می شود.
مراحل :
1. خوشه بندی
2. پوشش زیردامنه های کوچک شونده
3. تطبییق
4. تصادفی سازی تناوبی
ACCOL: ترکیب ACCO با چندین جستجوی محلی
ACD : ترکیب ACCO و سرازیری های Simplex رو به پایین
مرجع:
Genetic and other global optimization algorithms - comparison and use in calibration
problems
Proc. 3rd Inte. Conference on Hydroinformatics, Copenhagen, Denmark, 1998. Balkema Publishers. pp.1021-102
برچسب:
نویسنده: نگار نوری