در شکل ۳-۳ روند کلی استفاده از ابزار­های استفاده شده در الگوریتم ژنتیک، برای دست

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

یافتن به جواب بهینه یک مسئله نشان داده شده است. این روند را می­توان به صورت خلاصه شده زیر بیان کرد. شروع فرایند با یک جمعیت اولیه(مجموعه ­ای از جواب­ها) که به صورت رندم حدس زده می­ شود و جامعه اولیه را شکل می­دهد شروع می­ شود، سپس تابع هدف به ازای افراد جامعه مورد ارزیابی و برازش قرار می­گیرد و به ازای جواب­های مختلف تابع هدف، ارزش­های مختلفی بر افراد گذاشته می­ شود (برازش) . سپس با بهره گرفتن از ارزش گذاری انجام شده افراد بهتر جامعه برای تولید مثل انتخاب می­شوند (انتخاب). سپس بین افرادی که در مرحله انتخاب، تأیید شده ­اند تولید مثل اتفاق می­افتد تا نسل بعدی جواب­ها ایجاد شوند (جفت گیری). از آن­جایی که فرایند طی شده توسط الگوریتم ژنتیک یک فرایند تصادفی می­باشد ممکن است که هیچ کدام از فرزندان به جواب­های صحیح نزدیک نشوند، به همین خاطر روی مجموعه ­ای از افراد به صورت رندم تغییراتی انجام می­ شود که جهش نامیده می­ شود. در مرحله بعد جواب­های به دست آمده، توسط معیار­های ایست مورد بررسی قرار می­گیرند، اگر این معیارها را برآورده کردند، الگوریتم متوقف می­ شود و اگر برآورده نکردند مجددا الگوریتم تکرار می­ شود.
شکل شماره۳-۳: روند حل مسئله به وسیله الگوریتم ژنتیک]۲۹[
۳-۳-۱-۳ روش گرادیان مزدوج
همان طور که گفته شد در روش­های بهینه سازی محلی هم چون روش گرادیان مزدوج]۱۶[ و روش سیمپلکس، هرگاه نقطه شروع خوبی برای الگوریتم­های محلی در نظر گرفته شود، همگرایی به سمت نقطه بهینه مطلق محقق می­ شود. در اینجا همان گونه که ذکر شد این نقطه شروع مناسب توسط الگوریتم ژنتیک به دست می ­آید. اساس کار در روش معکوس الاستیسیته مینیمم کردن تابع هدف تعریف شده است. برای مینیمم کردن تابع هدف به مسیر جست وجوی(x) p^k و طول گام بهینه ^kβ نیاز است. به طوری که شبیه سازی مورد نظر برای این مسئله خاص بیشتر مربوط به نحوه پیدا کردن این دو پارامتر است. با بهره گرفتن از رابطه تکرارپذیر زیر می­توان مقادیر مینیمم کننده تابع هدف را یافت.
۳-۲
که در k=1,…..,iTer_CGM ضریب تکرار و iTer_CGM ماکزیمم تکرار الگوریتم CGM است. همچنین
۳-۳
بر طبق نسخه پولاک -ریبیر ضریب مزدوج ϒ^k ، از رابطه زیر به دست می ­آید:
۳-۴
که ϒ^۰ برابر صفر و همچنین در شروع مجدد، یعنی در مواردی که الگوریتم در N مرحله پایان نمی­پذیرد،­ دوباره مقدار صفر را به خود می­گیرد.
۳-۳-۱-۳-۱ گرادیان تابع هدف
محاسبه گرادیان تابع هدف می ­تواند به روش­های مختلفی انجام گیرد. روش مستقیم محاسبه گرادیان، مشتق گیری معمولی است که برای مسائل معکوس تخمین هندسه به واسطه زیاد بودن تعداد مجهولات منجر به افزایش حجم محاسبات و کاهش سرعت همگرایی می­ شود. همچنین فرمولاسیون صریحی برای الاستیسیته در روش المان مرزی برای معالات الحاقی ارائه نشده است. بنابراین برای محاسبه گرادیان از روش تفاضلات متناهی^[۵۰] استفاده شده است. با این تفاوت که به واسطه گستره زیاد متغیر­ها، گام تفاضل به صورت دینامیکی و متناسب با متغیر مربوطه تغییر می­ کند.
۳-۵
در رابطه فوق گرادیان جا به ­جایی iام نسبت به پارامتر jام است.
۳-۳-۱-۳-۲ طول گام بهینه
در محاسبه طول گام بهینه می­توان تابع هدف را در تکرار k+1 ام به صورت زیر نوشت:
۳- ۶
با بسط دادن جا به ­جایی و با بهره گرفتن از چند جمله ای درجه اول تیلور رابطه ۳-۷ محاسبه می­ شود.
۳-۷
که از حل مسئله مستقیم بر اساس متغیر­های تخمینی به دست می ­آید. بر اساس این رابطه می­توان را بر حسب مینیمم کرد. با این کار مقدار زیر برای گام بهینه به دست می آید.
۳-۸
های مورد نیاز برای محاسبه طول گام را می­توان به ازای از حل مستقیم برنامه به دست آورد.
۳-۳-۱-۴ روش سیمپلکس
در این روش از یک شکل هندسی با قاعده برای انتخاب نقاط رئوس سیمپلکس جهت محاسبه f(x) استفاده می­گردد. در حالتی که مسئله دو بعدی در نظر گرفته شود، یک مثلث متساوی الاضلاع شکل هندسی سیمپلکس را تشکیل می­دهد و در حالتی که مسئله سه بعدی در نظر گرفته شود، این شکل به یک چهار وجهی با قاعده تبدیل می­ شود. با افزایش تعداد متغیرها، تعداد رئوس افزایش پیدا می­ کند. ابتدا برای یک مسئله دو بعدی به توضیح این روش پرداخته می­ شود و سپس تعمیم آن در حالت n بعدی ارائه می­گردد ]۳۲[.
در حالت فرض مسئله به صورت دو بعدی، برای تعیین هر امتداد جست و جو ابتدا f(x) در سه رأس مثلث محاسبه می­گردد و سپس امتداد جست و جو از مرکز مثلث عبور کرده و از رأس مربوط به بزرگترین مقدارf(x) محاسبه شده، از سه رأس دور می شود. شکل زیر این فرایند را نشان می­دهد.
شکل شماره ۳-۴: فرایند انعکاس
پس از آن که مطابق شکل ۳-۴ یک مثلث متساوی الاضلاع دیگر ساخته شد، رأس به دست آمده به عنوان نقطه جدید انتخاب و f(x) در آن نقطه محاسبه می­گردد (به این فرایند انعکاس گفته می­ شود^[۵۱]). به این ترتیب یک امتداد جست و جوی جدید به دست می ­آید. این عمل آن قدر ادامه پیدا می­ کند تا سیمپلکس، نقطه بهینه را در میان گیرد. در این هنگام ادامه روند فوق نمی­تواند منجر به نزدیکی بیشتر به نقطه بهینه گردد. بنابراین اندازه سیمپلکس باید کاهش پیدا کند. در این حالت اضلاع آخرین سیمپلکس بر دو نیم تقسیم شده تا مجددا نقطه بهینه خارج از سیمپلکس قرار گیرد و روند فوق ادامه پیدا می­ کند.
در صورت وجود n متغیر، ۱+n رأس به مختصات در نظر گرفته شده و f(x) در آن رئوسمحاسبه می­گردد. اگر مربوط به بزرگترین مقدار تابع هدف باشد، در مرحله اول انعکاس نسبت به وجه مقابل محاسبه شده و نامیده می­ شود. می­توان انتظار داشت که تابع هدف مربوط به آن دارای کمترین مقدار باشد. بنابراین نقطه را حذف و جایگزین آن می شود. به این ترتیب یک سیمپلکس جدید بنا می­ شود. در ادامه رابطه­ای برای محاسبه از روی ارائه گردیده است که به شرح زیر می­باشد.
۳-۹
در این رابطه
۳-۱۰
و مرکز هندسی همه نقاط به استثنای می­باشد.
۳-۱۱
α ضریب انعکاس و برابر است با:
۳-۱۲
چنان چه رأس مربوط به کمترین مقدار تابع هدف باشد یعنی
۳-۱۳
در صورتی که باشد به طور کلی انتظار می­رود که با حرکت بیشتر در امتداد ، تا نقطه ای مانند ، بتوان مقدار تابع هدف را کاهش داد. این فرایند را گسترش^[۵۲] می­نامند.
شکل شماره۳-۵: گسترش
مقدار از رابطه زیر محاسبه می­ شود.
۳-۱۴
که در آن λ ضریب گسترش نام دارد و به صورت زیر تعریف می­ شود.
۳-۱۵ در صورتی که باشد، را جایگزین نموده و عمل انعکاس مجدداً آغاز می­ شود. اگر فرایند انعکاس به نقطه­ای مانند منتهی شد که برای آن به ازای همه مقادیر i به استثنای ، و ، در این صورت جایگزین می­ شود. این فرایند را انقباض سیمپلکس می­نامند و به صورت زیر بیان می­گردد.
شکل شماره۳-۶ : فرایند انقباض
۳-۱۶
در این رابطه ضریب انقباض است و به صورت زیر تعریف می­ شود:
۳-۱۷
در صورتی که باشد، از رابطه ۴-۱۴ بدون آنکه تغییری در مقدار قبلی ایجاد شود استفاده می­ شود.
چنانچه فرایند انقباض منجر به ایجاد نقطه گردد بطوریکه برای آن شرط برقرار باشد، نقطه جایگزین نقطه می­ شود و چنانچه باشد، فرایند انقباض به شکست می­انجامد و در این حالت جایگزین می­ شود و عمل انعکاس از سر گرفته می­ شود. به این فرایند شکستن می­گویند.
شکل شماره ۳-۷ : فرایند شکستن
به طور ساده­تر می­توان چنین بیان کرد که این روش بهینه سازی به سه بخش تقسیم شده است:
پیدا کردن بزرگترین مقدار تابع هدف و انعکاس حول مرکز سطح سایر نقاط و ادامه این مسیر تا آنجا که به پیدا کردن مناسب­ترین متغیر می­رسد و امکان ادامه فرایند وجود ندارد.(Reflection & Expansion)
انجام فرایند انقباض یا کوچک کردن تا آنجا که ممکن است.(Contraction)
شکستن اضلاع سیمپلکس هنگامی که دیگر با انقباض نمی­ توان به سمت نقطه بهینه حرکت کرد.(Shrinkage)
۳-۴ شبیه سازی مسئله معکوس الاستیسیته