منابع و ماخذ پایان نامه الگوریتم ژنتیک، شبکه های عصبی مصنوعی، شبکه های عصبی

دانلود پایان نامه ارشد

پیش از آن لازم است مروری بر روش های بهینه سازی متداول و پرکاربرد در حل مسئله مکان یابی چاه ها داشته باشیم.

2-2- مروری بر روش های بهینه سازی
2-2-1- الگوریتم ژنتیک
الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است. این الگوریتم در سال 1970 توسط John Holland معرفی گردید. این روش به نام الگوریتم تکاملی25 نیز خوانده می شود. الگوریتم ژنتیک، روش بهینه سازی الهام گرفته از طبیعت جاندار است که می توان در طبقه بندی ها، از آن به عنوان یک روش عددی، جستجوی مستقیم و تصادفی یاد کرد. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیه آن از علم ژنتیک اقتباس گردیده است و با تقلید از تعدادی از فرآیند های مشاهده شده در تکامل طبیعی، اختراع شده است و به طور موثری از معرفت قدیمی موجود در یک جمعیت استفاده می کند تاحل های جدید و بهبود یافته را ایجاد کند. اساس این الگوریتم را می توان قانون تکامل داروین “بقا بهترین” دانست که می گوید موجودات ضعیف تر از بین می روند و موجودات قوی تر باقی می مانند. یکی از مهمترین ویژگی های الگوریتم ژنتیک کاربرد آن در مسائلی با فضای جستجوی بزرگ و درجه پیچیدگی بالا می باشد. این الگوریتم در مسائل متنوعی نظیر بهینه سازی، شناسایی و کنترل سیستم، آموزش شبکه های عصبی مصنوعی و سیستم های مبتنی بر تصمیم و قاعده به کار می رود.
یکی از ویژگی های این الگوریتم که آن را از سایر روش ها متمایز می سازد این است که الگوریتم ژنتیک در هر تکرار چند نقطه از فضای جستجو را در نظر می گیرد، بنابراین شانس اینکه به یک ماکزیمم محلی همگرا شود کاهش می یابد. به عبارت دیگر این روش، با ترکیب کردن تصادفی بهترین پایه های هر نسل، توانایی تشخیص روند حرکت به سمت پاسخ های بهینه را دارد. بر خلاف آن، در بیشتر روش های جستجوی مرسوم نظیر روش گرادیان، قاعده تصمیم حاکم به این صورت عمل می کند که از یک نقطه به نقطه دیگر حرکت می کند. این روش ها در فضای جستجو دارای چند بیشینه، ممکن است به یک ماکزیمم محلی همگرا شوند. در مجموع امکان به تله افتادن الگوریتم ژنتیک در مینیمم محلی کمتر از سایر روش هاست. اما این روش از لحاظ محاسباتی پر هزینه می باشد و تضمینی برای رسیدن به جواب بهینه وجود ندارد.
الگوریتم ژنتیک کار خود را با ایجاد یک جمعیت اولیه از پاسخ های ممکن شروع می کند. جواب های پیشنهادی به صورت پارامتری بیان و متغییر های توصیف کننده هر یک از ان ها در کنار یکدیگر قرار داده می شوند و “کروموزومی” را تشکیل می دهند که نشان دهنده آن پاسخ در فرآیند های ارزیابی الگوریتم ژنتیک می باشد. مرحله بعد ارزیابی میزان تابع برازندگی26 برای هر یک از متغییرها و تخصیص احتمالات انتخاب به گونه ای می باشد که شانس انتخاب کروموزوم های با توابع برازندگی بهتر در مقایسه با کروموزوم هایی که تابع برازندگی نامناسب تری دارند بیشتر باشد. کروموزوم های با توابع برازندگی بهتر به عنوان والد27 انتخاب می شوند و برای ترکیب مجدد با یکدیگر جفت می شوند. اپراتوری که وظیفه ترکیب کروموزوم های والد را بر عهده دارد، اطلاعات والدها را با یکدیگر ترکیب می کند و باعث به وجود آوردن کروموزم های فرزند28 می شود که نسل بعد را شکل می دهند. بدین ترتیب یک مجموعه جدید از بردارهای جواب از روی بهترین جواب های مرحله قبل ساخته می شود. بنابراین به طور کلی هر نسل نسبت به نسل قبل از خصوصیات بهتری خواهد داشت. تکامل کروموزوم ها در طی نسل ها باعث حرکت به سمت پاسخ های بهینه می شود.
هرچند کروموزوم هایی که تابع برازندگی بهتری دارند برای انتقال به نسل بعد از شانس بهتری برخوردارند، شانس انتخاب شدن به عنوان والد برای سایر کروموزوم ها هم وجود دارد. از طرف دیگر فرزندانی که در هر نسل ایجاد می شوند لزوماً دارای خصوصیات بهتر نسبت به والدین خود نخواهند داشت. این موضوع باعث شکل گیری مکانیزمی می شود که قابلیت حفظ تنوع در میان جمعیت نسل را داشته باشد و به الگوریتم ژنتیک این امکان را می دهد که بهتر بتواند از دام پاسخ های بهینه محلی رهایی یابد.
در الگوریتم ژنتیک معمولا کروموزوم ها (یا همان اعضای یک جمعیت) به صورت رشته ای از بیت ها نمایش داده می شود تا اعمال اپراتور های ژنتیکی بر روی آن ساده تر باشد.
فضای فنوتیپ29: به مقادیر واقعی متغیر ها گفته می شود.
فضای ژنوتیپ30: به مقادیر انکد شده یا کروموزوم ها گفته می شود که توسط الگوریتم ژنتیک مورد استفاده قرار می گیرد.
باید راهی برای تبدیل این دو نحوه نمایش به یکدیگر بدست اورده شود. در شکل 2-1 این دو فضای متغیرها نمایش داده شده است.

شکل 2-1: نمایش متغیرها در دو فضای ژنوتیپ و فنوتیپ
2-2-1-1- عملگرهای الگوریتم ژنتیک
الگوریتم ژنتیک استاندارد که الگوریتم ژنتیک دودویی31 هم نامیده می شود، برای ایجاد یک نسل جدید، از اپراتور های زیر استفاده می کند.
رمز گذاری32
این مرحله شاید مشکل ترین مرحله حل مساله به روش الگوریتم ژنتیک باشد. الگوریتم ژنتیک به جای این که بر روی پارامترها یا متغیرهای مساله کار کند، با شکل کد شده آن ها سروکار دارد. یکی از روش های کد کردن، کد کردن دودویی می باشد که در آن هدف تبدیل جواب مساله به رشته ای از اعداد باینری است.
ارزیابی33
تابع برازندگی هر رشته را با یک مقدار عددی ارزیابی می کند که کیفیت آن را مشخص می نماید. هر چه کیفیت رشته جواب بالاتر باشد، مقدار برازندگی جواب بیشتر است و احتمال مشارکت برای تولید نسل بعدی نیز افزایش خواهد یافت.
عملگر تولید مجدد یا انتخاب34
در مرحله انتخاب، یک جفت از کروموزوم ها برگزیده می شوند تا با هم ترکیب شوند. عملگر انتخاب رابط بین دو نسل است و بعضی از اعضای نسل کنونی را به نسل آینده منتقل می کند. بعد از انتخاب، عملگر های ژنتیکی روی دو عضو برگزیده اعمال می شوند. معیار در انتخاب اعضا ارزش تطابق آن ها می باشد اما روند انتخاب حالتی تصادفی دارد.
شاید انتخاب مستقیم و ترتیبی به این شکل که بهترین اعضا دو به دو انتخاب شوند در نگاه اول روش مناسبی به نظر برسد اما باید به نکته ای توجه داشت. در الگوریتم ژنتیک ما با ژن ها روبه رو هستیم. یک عنصر با تطابق پایین اگرچه در نسل خودش عضو مناسبی نمی باشد اما ممکن است شامل ژن هایی خوب باشد و اگر شانس انتخاب شدنش صفر باشد، این ژن های خوب نمی توانند به نسل های بعد منتقل شوند. پس روش انتخاب باید به گونه ای باشد که به این عضو نیز شانس انتخاب شدن بدهد. راه حل مناسب، طراحی روش انتخاب به گونه ای است که احتمال انتخاب شدن اعضای با تطابق بالاتر بیشتر باشد. روش های متدوال انتخاب عبارتند از: انتخاب چرخ رولت، انتخاب بولتزمن، نخبه سالاری و انتخاب رقابتی.

انتخاب چرخ رولت
انتخاب چرخ رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب ترین انتخاب های تصادفی بوده که ایده آن احتمال انتخاب می باشد.احتمال انتخا متناظر با هر کروموزوم بر اساس برازندگی آن محاسبه شده است که اگر f_k مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
P_k=f_k/(∑_(i=1)^n▒f_i ) (2.1)
حال کروموزوم ها را بر اساس P_k مرتب کرده و q_k که همان مقادیر تجمعی P_k می باشد به صورت زیر به دست می آید.
q_k=∑_i^k▒P_i (2.2)
چرخ رولت به این صورت عمل می کند که برای انتخاب هر کروموزوم یک عدد تصادفی بین صفر و یک تولید کرده و عدد مذکور در هر بازه ای که قرار گرفت، کروموزوم متناظر با آن انتخاب می شود.

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

انخاب رقابتی
این روش تعدادی از اعضای جمعیت را به تصادف انتخاب می کند و سپس اگر شرطی خاص برقرار باشد، بهترین یا تعدادی از بهترین های آن ها را به عنوان والد بر می گزیند. اگر شرط برقرار نشود، بدترین عضو یا تعدادی از بدترین ها در تشکیل جمعیت آینده به عنوان والد در نظر گرفته می شوند.
شکل استاندارد این روش، رقابت دوتایی یا باینری است که به شکل زیر می باشد:
2 عضو به تصادف انتخاب می شود.
مقدار r به تصادف بین 0 و 1 انتخاب می شود.
پارامتر 0 اگر k≤r عضو برتر و اگر k≥r عضو بدتر بین این دو عضو به عنوان والد انتخاب می شود.
دو عضو انتخاب شده برای رقابت به جمعیت باز می گردند و می توانند دوباره در رقابت شرکت کنند.
روش انتخاب رقابتی می تواند به صورت n تایی نیز انجام شود.

اپراتور تقاطع35
این اپراتور با استفاده از دو رشته والد دو رشته فرزند به وجود می آورد. برای این کار به طور تصادفی قسمتی از بیت های والدین در بیت های فرزندان کپی می شود. انتخاب بیت هایی که باید از هر یک از والدین کپی شوند به روش های مختلفی انجام می شود.
تقاطع تک نقطه ای36
تقاطع دو نقطه ای37
تقاطع یکنواخت38
در زیر نحوه روش تقاطع تک نقطه ای بیان می شود و روند بقیه روش های تقاطع در شکل 2-2، 2-3 و 2-4 مشخص شده است.
یک نقطه تصادفی در طول رشته انتخاب می شود.
والدین در این نقطه دو قسمت می شوند.
هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر به وجود می آید.

شکل 2-2: تقاطع تک نقطه ای

شکل 2-3: تقاطع دو نقطه ای

شکل 2-4: تقاطع یکنواخت
تقاطع خاصیت جستجوگرانه و یا Explorative دارد و می تواند با انجام جهش های بزرگ به محل هایی در بین والدین رفته و نواحی جدیدی را کشف نماید.
اپراتور جهش39
این اپراتور برای به وجود آوردن فرزند، فقط از یک والد استفاده می کند. این کار با انجام تغییرات کوچکی در رشته اولیه به وقوع می پیوندد. بدین صورت که با استفاده از یک توزیع یکنواخت یک بیت به صورت تصادفی انتخاب می شود و مقدار آن معکوس می شود. معمولا اپراتور جهش بعد از تقاطع اعمال می شود.

شکل 2-5: اپراتور جهش

جهش خاصیت گسترشی و یا Exploitive دارد و می تواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد.

رمز گشایی40
در این مرحله بعد از اینکه الگوریتم بهترین جواب را برای مساله ارائه کرد لازم است عکس عمل رمزگذاری روی جواب ها اعمال شود تا بتوان نسخه واقعی جواب را به وضوح یافت.
2-2-1-2- پارامترهای الگوریتم ژنتیک
به طور معمول الگوریتم ژنتیک دارای پارامترهای زیر است:
تابع برازندگی برای ارزیابی هر یک از کروموزم ها
مقدار آستانه41 که شرط پایان را معین می کند.
تعداد جمعیت42 (n)
درصدی از جمعیت که در هر مرحله توسط اپراتور تقاطع43 جایگزین می شود. (r)
نرخ جهش (m)
مراحل ایجاد یک جمعیت جدید به صورت زیر می باشد:
انتخاب : تعداد (1-r)n عضو از میان جمعیت کنونی، p، انتخاب و به جمعیت جدید p_s اضافه می شود. احتمال انتخاب یک عضو از میان جمعیت p با توجه به میزان تابع برازندگی برای هر عضو از جمعیت به صورت زیر محاسبه می شود:
P_i=f_i/(∑_(j=1)^n▒f_j )
که f_i مقدار تابع برازندگی عضو i ام جمعیت می باشد.
تقاطع : با استفاده از احتمال بدست امده توسط رابطه فوق، تعداد rn/2 زوج عضو از میان جمعیت p انتخاب می شود و با استفاده از اپراتور تقاطع دو فرزند از آن ها ایجاد می شود. سپس فرزاندان به جمعیت p_s اضافه می شود.
جهش : این اپراتور بر روی یک عضو از یک کروموزوم با احتمال یکنواخت که نرخ جهش (m) نامیده می شود، اثر می گذارد و باعث معکوس شدن آن می شود. به این معنی که 1 را به 0 و 0 را به 1 تبدیل می کند.
اعضای جمعیت p_s ، جمعیت جدیدی را تشکیل می دهد.

نحوه عملکرد الگوریتم ژنتیک در شکل 2-6 نشان داده شده است. هنگام استفاده از الگوریتم ژنتیک در مسئله مکان یابی چاه های نفت، مکان هر چاه که توسط دو تایی مرتب (i,j) توصیف می شود، جواب های ممکن مسئله هستند که اجتماع آن ها جمعیت را تشکیل می دهد. هر مکان ممکن چاه به عنوان ورودی سیستم در نظر گرفته می شود و تابع برازندگی خروجی می باشد و سپس جمعیت طبق الگوریتم ژنتیک بهبود داده می شود تا به بهترین مکان دست یافت [7].

شکل 2-6: فلوچارت الگوریتم ژنتیک
2-2-2- الگوریتم 44PSO
الگوریتم بهینه سازی ذرات یک الگوریتم بهینه سازی فرا اکتشافی می باشد که از حرکت گروهی پرندگان و دیگر حیواناتی که به شکل گروهی زندگی می کنند الگو گرفته است. الگوریتم PSO مشابه الگوریتم ژنتیک یک روش بر مبنای جمعیت است. پاسخ مسئله در روش PSO ذرات هستند که مجموعه ذرات در هر تکرار ازدحام45 نامیده می شود. موقعیت هر ذره بر اساس میزان تابع هدف آن و موقعیت نسبی بقیه ذرات تنظیم می شود. این الگوریتم اولین بار توسط James Kennedy , Russell Eberhart در سال 1995 در مقاله [8] ارائه شد.
PSO بر اساس حرکت و هوش ذرات کار می کند و مفهوم تعامل اجتماعی را برای حل مسائل بهینه سازی به کار می گیرد. ذرات (پاسخ های مسئله) در فضای جستجو حرکت می کنند و هر ذره در حال جستجو برای نقطه بهینه می باشد. هر ذره در هر مرحله، موقعیتی را که بهترین نتیجه را در آن داشته به خاطر می سپارد (بهترین موقعیت فردی هر ذره). به علاوه ذرات در گروه ذرات با هم همیاری می کنند. ذرات اطلاعاتی، درباره موقعیتی که در آن هستند با هم تبادل می کنند. این روش، یک روش مرتبه صفر است و نیازی به عملیات سنگین ریاضی مثل گرادیان ندارد. همچنین بار محاسباتی قابل قبولی دارد و همگرایی آن نسبتاً سریع است.
حرکت هر ذره در این الگوریتم به سه عامل بستگی دارد:
موقعیت فعلی ذره
بهترین موقعیتی که تاکنون ذره داشته است. (P_best)
بهترین موقعیتی که کل مجموعه ذرات تاکنون داشته اند. (G_best)

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

شکل 2-7: انتخاب جمعیت اولیه از اعضا [6]
پس از آن مقدار تابع به ازای هر عضو جمعیت ارزیابی می شود.

شکل 2-8: ارزیابی تابع هدف [6]
اگر موقعیت ذره از بهترین موقعیت قبلی آن بهتر شد، به روز رسانی می شود.
بهترین موقعیت ذرات با در نظر گرفتن بهترین موقعیت های قبل انتخاب می شود.

شکل 2-9: انتخاب بهترین موقعیت ذرات [6]
سرعت ذرات به کمک رابطه زیر به روز رسانی می شود:

v_i^(k+1)=C_0 v_i^k+C_1 r_1 (P_(〖best〗_i )-x_i^k )+C_2 r_2 (G_(〖best〗_i )-x_i^k ) (2.3)

r_1 و r_2 تابع Rand، مولد عدد تصادفی در بازه [0,1] می باشد. C_1 و C_2 ثابت های اثر نامیده می شوند.
ترم اول جمله سمت راست مربوط به جابه جایی فعلی ذره و جمله دوم نشانگر اثر حافظه ذره و در نهایت جمله سوم اثر گروه ذرات می باشد.

شکل 2-10: به روز رسانی سرعت ذرات [6]

در ادامه مقدار P_(〖best〗_i ) مساوی مقدار اولیه هر ذره قرار داده می شود و G_(〖best〗_i ) که کمترین مقدار در میان همه P_(〖best〗_i ) ها می باشد، محاسبه می شود. سپس سرعت جدید ذرات از رابطه (2.3) محاسبه می شود. موقیت جدید ذرات از رابطه زیر بدست می آید:
〖x_i^(k+1)=x_i^k+v〗_i^(k+1) (2.4)

این مراحل تکرار می شود تا نقطه بهینه حاصل شود. شکل 2-11 زیر نحوه محاسبه سرعت و چگونگی به روز کردن موقعیت ذره x_i در فضای جستجوی دو بعدی در الگوریتم PSO را نشان می دهد.

شکل 2-11: چگونگی به روز کردن موقعیت ذره x_i در فضای جستجوی دو بعدی
در شکل 2-12 فلوچارت کلی الگوریتم PSO آمده است.

شکل 2-12: فلوچارت الگوریتم PSO
2-2-3- الگوریتم Polytope
روش polytope یک روش از دسته روش های معروف به تپه نوردی46 می باشد و از جمله الگوریتم های بهینه سازی است که نیازی به محاسبه مشتق ندارند. این الگوریتم اولین بار توسط Nelder و Mead در سال 1965 معرفی شد [9]. این روش همان الگوریتم Hill-Climbing است که نیازی به اطلاعات مربوط به مشتق پارامترها را ندارد و گاهی اوقات با نام الگوریتم Simplex هم شناخته می شود.
این روش در یک فضای n- بعدی با n+1 نقطه، کار خود را آغاز می کند. در هر مرحله متغیر های تصمیم گیری، x_1,x_2,…,x_(n+1) به گونه ای مرتب می شوند که مقدار تابع هدف آن ها به ترتیب صعودی به نزولی قرار بگیرد یعنی:
f_1≥f_2≥…≥f_(n+1) (2.5)
ابتدا یک نقطه آزمایشی در یک گام بازتاب47 ایجاد می شود:
x_r=c+α(c-x_(n+1) ) (2.6)
که α (α>0) ثابت انعکاس و c مرکز n+1 نقطه می باشد و از رابطه زیر بدست می آید:
c=1/n ∑_(i=1)^n▒x_i (2.7)
در ادامه مقدار تابع هدف به ازای نقطه جدید x_r ، یعنی f_r محاسبه می شود. گام بعد با توجه به مقدار f_r به یکی از صورت های زیر خواهد بود:
اگر f_1≥f_r≥f_n باشد، نقطه x_(n+1) که در واقع بدترین نقطه می باشد، در تکرار بعد با نقطه x_r جایگزین می گردد.
اگر f_r≥f_1 باشد، آنگاه نقطه x_r بهترین نقطه در جمعیت است. در این صورت فرض بر این می شود که انعکاس، در جهت نقطه بهینه است. بنابراین یک گام گسترش48 انجام می شود:
x_e=c+β(x_r-c) (2.8)
سپس مقدار تابع هدف در نقطه x_e ، یعنی f_e محاسبه می شود. لازم به ذکر است که β ضریب گسترش است و مقدار آن بزرگتر از یک می باشد. در این مرحله نیز دو حالت ممکن است رخ بدهد:
اگر f_e≥f_r باشد، آنگاه گسترش موفقیت آمیز بوده است و x_e جایگزین x_(n+1) می شود.
اگر f_e≤f_r باشد، آنگاه گسترش موفقیت آمیز نبوده است و x_r جایگزین x_(n+1) می شود.
اگر f_n≥f_r باشد، الگوریم بزرگ است و باید منقبض شود.
اگر f_r≥f_(n+1) باشد، آنگاه:
x_c=c+γ(x_(n+1)-c) (2.9)
اگر f_rx_c=c+γ(x_r-c) (2.10)
که γ مقداری بین 0 و 1 می باشد و ضریب انقباض نام دارد. سپس مقدار تابع هدف در نقطه x_c ، یعنی f_c محاسبه می شود و اگر این مقدار هم از f_r و هم از f_(n+1) بزرگتر باشد، x_c جایگزین x_(n+1) می شود، در غیر صورت یک مرحله انقباض دیگر انجام می شود. در شکل 2-13 زیر ساختار الگوریتم ploytope در یک فضای جستجوی دو بعدی نشان داده شده است.

شکل 2-13: الگوریتم Polytope [9]
2-2-4- الگوریتم Simplex
مبنای این روش این است که در یک فضای n بعدی، یک چند ضلعی حداقل حاوی n+1 ضلع خواهد بود. به عنوان مثال در فضای دو بعدی، یک چند ضلعی که حداقل بعد را داشته باشد، مثلث است. در فضای پارامترها مثلثی را به صورت A,B,C در نظر بگیرید و s(θ) که تابع هدف مورد نظر برای بهینه سازی می باشد، را برای هر راس مثلث حساب کنید. هر راس که تابع s(θ) آن بزرگتر باشد، نسبت به سایر اضلاع قرینه می شود. به عنوان مثال اگر s(θ_A) از s(θ_B) و s(θ_C) بزرگتر باشد، نقطه A نسبت به ضلع BC قرینه می شود، تا نقطه D بدست آید. سپس الگوریتم برای نقاط B,C,D تکرار می شود.
بزرگترین مشکل این روش پدیده Cycling می باشد. بدین معنی که الگوریتم بین نقاط A و D تکرار شود. اگر با این پدیده مواجه شویم راهکار زیر توصیه می شود:
اگر s(θ_D )>s(θ_A) در آن صورت نقطه D به مرکز BC، نزدیکتر انتخاب می شود.
اگر s(θ_D )s(θ_A) در آن صورت نقطه D به مرکز BC، دورتر انتخاب می شود.
الگوریتم فوق توسط Nelder و Mead توسعه داده شده است. در زیر خلاصه گام به گام این الگوریتم برای یک مسئله مینیمم سازی در یک فضای دو بعدی آورده شده است:

مراحل الگوریتم Simplex در فضای دو بعدی برای یافتن مینیمم s(θ):
سه نقطه A,B,C با فاصله مساوی انتخاب می شوند.
s(θ_A) ، s(θ_B) و s(θ_C) محاسبه می شوند.
نقطه ای که s آن از سایرین بزرگتر می باشد، انتخاب می شود. (فرض کنید نقطه A انتخاب می شود.)
قرینه نقطه A نسبت به ضلع BC محاسبه می شود و D نامیده می شود.
s(θ_D) محاسبه می شود.
s(θ_B) ، s(θ_C) و s(θ_D) مقایسه شده و بزرگترین s انتخاب می شود.
الگوریتم مجدداً تکرار می شود تا جایی که به یک نقطه مشخص همگرا شود یا تغییرات s بسیار ناچیز باشد.
روش فوق بر مبنای محاسبه مستقیم تابع هزینه در هر نقطه می باشد و به گرادیان آن هیچ نیازی ندارد. پیشنهاد می شود تنها در مواردی که محاسبه گرادیان تابع هزینه بسیار مشکل باشد از روش فوق استفاده شود.
2-2-5- الگوریتم Hook Jeeves
الگوریتم HJ یک روش بهینه سازی بر مبنای جستجوی مستقیم می باشد و بر اساس محاسبه تابع هزینه عمل می کند و به مشتق آن نیازی ندارد. ایده این روش این است که برای جستجوی مقدار بهینه θ در یک فضای p بعدی، در p بعد مستقل به دنبال جواب θ باشد. به عبارت دیگر این الگوریتم از نقطه اولیه ▁θ_a شروع می کند و در یک جهت مشخص حرکت می کند تا θ_1 مینیمم تابع S(θ_1) را بیابد. اگر مقدار S(θ_1) در راستای حرکت افزایش یافت، جهت حرکت عوض می شود و اگر S(θ_1) تغییر چندانی نداشت گام حرکت49 کوچک تر می شود. سپس در راستای پارامتر θ_2 حرکت می کند و با

پایان نامه
Previous Entries منابع و ماخذ پایان نامه مکان یابی، شبیه سازی، تولید نفت Next Entries منابع و ماخذ پایان نامه مکان یابی، الگوریتم ژنتیک، روش های ترکیبی