تحقیق مقاله بهینه سازی جهانی

بهینه سازی جهانی

بهینه سازی جهانی یک شاخه از ریاضیات کاربردی و آنالیز های عددی می باشد که با بهینه سازی یک تابع یا یک سری از توابع در برخی حوزه ها سر وکار دارد.

کاربرد های بهینه سازی جهانی

مثال های ساده از کاربردهای بهینه سازی جهانی عبارتند از:

پیش بین ساختار پروتئین (به حداقل رساندن انرزی /تابع انرزی آزاد)

مسئله فروشنده دوره گرد طرح مداری (به حداقل رساندن طول مسیر )

مهندسی شیمی (آنالیط انرزی آزاد گیبس)

شناسایی امنیتی ،مهندسی امنیت (ساختارها ی مکانیکی ،ساختمان ها )

بدترین آنالیز مورد

مسائل ریاضیاتی (تخمین کپلر)

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

لیوان های فشرده

دیدگاه ها

قطعی گرایانه

موفق ترین آن عبارت است از :

روش های شاخه ومرز

روش های برپایه هندسه جبری واقعی

اتفاقی ، ترمودینامیک

تعداد زیادی الگوریتم بر پایه Monte-Carlo وجود دارد :

باز پخت شبیهع سازی شده

نمونه سازی مستقیم Monte-Carlo

مسیر سازی اتفاقی

بازپخت متوازن

به حداقل رسانی به همراه Monte Carlo

روش های متناوب

ابتکاری وفوق ابتکاری

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

الگوریتم های تکاملی

الگوریتم های بهینه سازی بر پایه  اجتماعی

الگوریتم های ممتیک ،اتصال دهنده استراتزی های جستجوی عمومی و جهانی

سیر تکاملی افتراقی

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

تاریخچه

سیر تکاملی افتراقی حاصل تلاش های کنس چرایس برای حل مسئله سازگاری چند جمله ای چبیسشو  است که به توسط استورن تحمیل شده بود .یک شکافت وقتی او با نظریه استفاده از تفاوتهای برداری برای آشفتن

اجماع برداری استفاده کرده ،روبرو شده است.از زمان  این نظریه نطفه ای یک بحث زنده بین کنث و رینر و اندیشناکی های بی پایان وشبیه سازی های کامپیوتری در هر دو بخش ،بسیاری اصلاحات  قابل توجه را باعث شد که آنرا وسیله ای چند بعدی و قوی ساخت که امروزه می باشد.بازپخت های زنتیکی ،توسعه یافته توسط پرایس ،ابتدای راه الگوریتم های آن بود.اولین مقاله راجع به بازپخت زنتیکی در اکتبر 1994 توسط مجله وکتر داب به چاپ رسید.و یک الگوریتم ترکیبی بر پایه جمعی بود که معیار بازپختی را از راه آستانه که توسط علکرد میانگین اجتماع رانده می شود ،درک می کند .خیل یزود بعد از این پیشرفت ،پرایس با استورن تماس گرفت که در حل مسئله سازگاری چند جمله ای چبیچو توسط بازپخت زنتیکی علا قه مند بود.بعد از تعدادی آزمایشات پرایس الگوریتم را با استفاده از از نقطه شناور به جای رمزگذاری رشته باریک و عملیات های حسابی برداری  به جای منطقی ها را شناسایی کرد.این قالب های نو بازپخت زنتیکی را از ترکیبی به بهینه گر متناوب تغییر داده بودند.با این روش ،پرایس پروسه جهش های متفاوت را کشف کرد .پرایس .استورن یافتند که ترکیب جهش افتراقی با ترکیبات گسسته ومجموعه جفت با هوش در یک فاکتور بازپختی مورد نیاز نمی باشد.از این رو ،مکانیسم بازپخت در انتها از دور خارج شد و پس الگوریتم به دست آمده دوره تکامل افتراقی را آغاز کرد.برای اولین بار تکامل افتراقی زمان توسط پرایس واستورن در گزارش تکنیکی خود توصیف شد .یک سال بعد ،در می  1996 در اولین مسابقه بین المللی بهینه سازی تکاملی ،که همزمان با کنفرانس بین المللی IEEE در 1996 حول محاسبات تکاملی بود ، سیر تکاملی افتراقی برنده شد.الگوریتم سوم شد.با  آنچه از نتایج حاصل شده بود آن دو مقاله برای مجله دکتر داب نوشتند که در آپریل 1997 به چاپ رسید.همچنین مقاله آنها برای مجله بهینه سازی جهانی در دسامبر 1997 به چاپ رسید.این مقالات به عموم جهان به طور گسترده معرفی شد ومزیت آن را نسبت دیگر ابتکارات مطرح ساخت .نتایج بسیار خوبی در وسعت بالای معیاری نشان داده شد.به علاوه ،پرایس آنرا در دومین مسابقه بین المللی بهینه سازی تکاملی در 1997 شرکت داد.آنجا تکامل افتراقی یک از بهترین الگوریتم های مدعی بود .و در انتها دو سال بعد در 1999 او الگوریتم را در ایجازی با نام "نطریات جدید در بهینه سازی " خلاصه کرد .استورن روی کاربرد های متفاوتی از آن متمرکز شده بود و سایت اینترنتی خود را که شامل رمز های منبع وبسیاری لینک های مفید بود راه انداخت .در 1998 لمپینن سایت اینترنتی اداری رسمی تاریخچه ای را راه اندازی کرد ،که همه اسناد و همچنین لینک ها راجع به موضوع را از سال 1995 تا 2002 جمع آوری کرده بود.

گسترش

همان گونه که مطرح شد " تکامل افتراقی  –یک طرح ساده وموثر سازوارپذیر برای بهینه سازی جهانی در فضای مستمر  می باشد "المان کلیدی برای تشخیص آن از تکنیک های جامعه مدار جهش های افتراقی می باشد .سری ابتدایی ستراتزی ها که جهش های افتراقی را شناسایی کردند توسط استورن وپرایس ارایه شده بودند.اولین تلاش برای هدایت جهش افتراقی توسط پرایس انجام شد ،در جایی که جهش نیمه هدایت شده توسط یک عملیات گزینش قبلی خاص شناسایی شده بود .بعدها ،پرایس استراتزی ها را آنالیز کرد و اشاره کرد که استراتزی ممکن است از جهش افتراقی و تقاطع های هندسی تشکیل شود.در عوض این قضیه اثرات دینامیک متفائتی از جستحو را حاصل می کند.نظریات دستورالعمل ها بی اختیار توسط فان ولامپینن در 2001 کشف شد ،آنها تعویض قطب استراتزی کلاسیک را با یک طرح زمان بندی مثلث جهش انجام دادند ،و در سال 2003 تعویض قطب ها با استراتزی هدایت شده وزن شده در جایی که آنها دو بردار متفاوت را استفاده می کنند .این روش ها تعدادی اصلاحات را انجام داده اند ،اما لازم است که اشاره داشته باشیم ،درصد استفاده از

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

محدودیت ها

برای هندلینگ محدودیت های مرزی دو راه حل می تواند انجام شود :

آغاز سازی  دوباره

اسلوب دوره ای (مکانیسم انتقالی )

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

مدل سازگار با اطلاعات ،بهینه سازی در ریاضیات عددی ،عملیات بهینه سازی مهندسی بسته یا دیگر سیستم ها ،بسته بندی ودیگر مسائل چیدمان هدف ،سازمان دهی دارایی ،مدل های انرزی بالقوه در شیمی و فیزیک محسباتی ،پروسه کنترل ،طرح روبات ودست آموز کردن ،سیستم های معادلات غیر خطی و عدم تساوی ها ،و سازماندهی سیستم ها ی عملکرد با آب فاضلاب می باشد.برای فرمول بندی مسئله بهینه سازی جهانی فرض کنید که تابع هدف f و حدود  g توابع متناوب هستند .حدود جزء باهوش xi و xµ مرتبط با متغیر بردار تصمیم متناهی هستند .و سری محتمل خالی نمی باشد.این فرضیات گارانتی میکند که مدل بهینه سازی جهانی خوب مطرح شده است و از آنجایی که ،توسط تئوری ارزش گستری ،سری راه حل مدل بهینه سازی جهانی غیر خالی است .از وقتی که ما آرزوی یافتن کوچکتیرن اشتباه جهانی را داریم و نه فقط کوچکترین عمومی ومحلی آن ،ما می بایست به صورت جهانی در دو بعد محدوده جستجو کنیم. تعداد بسیار زیادی مسائل بهینه سازی غیر خطی وجود دارد که یک ساختار مدل چندگانه مشابه را پردازش می کند .اگر ما حوزه ر.ش های محلی وعمومی سنتی را را برای حل ایم مسئله استفاده کنیم سپس  به نقطه آغازین جستجو بستگی خواهد داشت.ما معمولا راه حل های سهینه محلی با کیفیت های متفاوت را خواهیم یافت .در شکل بالا می توان به راحتی روش های جستجوی محلی را به دام انداخت تا راه جهانی بهینه را بیابیم .یک جستجوی جهانی لازم میباشد.بسیاری از مهمترین استراتزی های بهینه سازی جهانی در زیر لیست شده اند ،با هم وبا علامات و منابع اضافه شده .بسیاری از برداشت های نرم افزاری جهانی بهینه سازی بر پایه یکی از این دیدگاه می باشد ،ممکن است نظریات را از استراتزی های متفاوت با هم ترکیب کرده باشند.

روش های قطعی عبارتند از:

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

استراتزی های کامل جستجو :اینها بر پایه یک تعیین شماره جامع از کلیه راه حل های ممکن می باشد . اینها برای مسائل ترکیبی همانند مسائل بهینه سازی متناوب با ساختار خوب مثل برنامه نویسی کاوی قابل کاربرد است.

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

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

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