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

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

ابت شده، θ_2 به گونه ای پیدا می شود که S(θ_2) حداقل شود. این روند تا آخرین پارامتر یعنی θ_p ادامه می یابد به نحوی که به بردار ▁θ_b برسیم. از این نقطه مجدداً الگوریتم فوق تکرار می شود. در شکل 2-14 نحوه جستجوی این الگوریتم در یک فضای جستجوی دو بعدی نمایش داده شده است.

شکل 2-14: نحوه جستجوی الگوریتم HJ در فضای جستجوی دو بعدی [10]
الگوریتم HJ دارای دو نوع حرکت برای رفتن به سمت پاسخ بهینه می باشد: حرکت اکتشافی50 و حرکت الگویی51 . در شکل بالا حرکت اکتشافی با پیکان با رنگ سیاه و حرکت الگویی با رنگ قرمز نشان داده شده است. حرکت اکتشافی در واقع تخمینی از مشتق52 را ارائه می دهد. همان طور که در شکل 2-14 نشان داده شده است الگوریتم از یک نقطه دلخواه (دایره با رنگ قرمز) شروع می شود و در یک جهت، حرکت اکتشافی انجام می دهد و تابع هزینه ارزیابی می شود. اگر الگوریتم بتواند به نقطه ای با تابع هدف مطلوب تر برسد، سپس حرکت اکتشافی در جهت دیگر فضای مسئله زده می شود. اگر دو حرکت اکتشافی، موفقیت آمیز باشد سپس یک حرکت الگویی انجام می شود. اگر حرکت الگویی منجر به پاسخ مطلوب تر نشد مجدداً از همان نقطه حرکت اکتشافی تکرار می شود. برای اطلاعات بیشتر در مورد الگوریتم HJ به مراجع [11و12] مراجعه شود.
در زیر خلاصه گام به گام این روش آورده شده است:
یک تخمین اولیه برای بردار θ در نظر گرفته و آن را θ_a می نامیم.
در جهت محور θ_1 انقدر حرکت می کنیم تا s(θ) حداقل شود. سپس مقدار θ_1 را ثابت کرده و به مرحله بعد می رویم.
در جهت محور θ_2 انقدر حرکت می کنیم تا s(θ) حداقل شود. سپس مقدار θ_2 را ثابت کرده و به مرحله بعد می رویم.
گام 2 و 3 را برای یک مسئله بهینه سازی p بعدی، تا p بعد و حرکت در جهت محور θ_p ادامه می دهیم.
نقطه حاصا از بهینه سازی در جهت تک تک محورها را θ_b می نامیم.
در جهت بردار θ_b-θ_a حرکت می کنیم تا بردار θ ́_b بدست آید.
در صورتی که s(θ ́_b) کمتر از s(θ_b) باشد، θ ́_b را با θ_b عوض می کنیم.
الگوریتم را از مرحله 2 به بعد آنقدر تکرار می کنیم تا در یک نقطه همگرا شود.

به منظور متوقف کردن الگوریتم HJ از دو شرط توقف استفاده می شود. شرط توقف اول رسیدن به حداقل گام حرکت و شرط دوم ارزیابی تابع هدف به میزان تعریف شده می باشد. در مسائل بهینه سازی مکان چاه های نفت به دلیل اینکه نوع مسئله گسسته می باشد، حداقل گام حرکت یک انتخاب می شود. زمانی که گام حرکت کوچکتر از یک شود الگوریتم متوقف می شود و همگرایی حاصل می شود.
یکی از مهمترین معایب روش HJ ترتیبی بودن فرآیند بهینه سازی می باشد و نمی توان آن را مشابه الگوریتم های تکاملی به طور موازی اجرا کرد. مشکل دیگر این روش دستیابی به بهینه محلی می باشد و این نتیجه بسیار تاثیر پذیر از شرط اولیه شروع الگوریتم می باشد.
2-2-6- الگوریتم شاخه و کران53
یک مسئله برنامه ریزی اعداد صحیح را در نظر بگیرید. اولین گام در الگوریتم شاخه و کران، حل مسئله بدون در نظر گرفتن محدودیت های صحیح بودن متغییرهاست. اگر پاسخ مسئله صحیح نبود، قیود جدیدی برای برش زدن این پاسخ بهینه غیر صحیح ایجاد می شود. اما در اینجا به جای گسترش مسئله اصلی با اضافه کردن یک قید، دو مسئله مجزا که هر کدام با اضافه کردن یک قید جدید به مجموعه متغیر ها ساخته می شود، ایجاد می شود. برای این منظور یک متغیر مانند x_j، که مقدار آن در پاسخ بهینه به دست آمده است یک عدد غیر صحیح است، انتخاب می شود. فرض کنید x_j=b_j است. پس لز آن دو مسئله جدید با افزودن قیود x_j≤[b_j ] و x_j≥[b_j ]+1 ساخته می شود. باید توجه داشت که پاسخ بهینه غیر صحیح، یک جواب قابل قبول برای هیچ یک از دو مسئله جدید نیست. اما هر پاسخ صحیح مسئله اصلی، یک جواب قابل قبول برای یکی از دو مسئله فوق نیز می باشد. هر یک از دو مسئله جدید مانند قبل بدون در نظر گرفتن قید صحیح بودن حل می شود و همان روال قبل طی می شود. اگر باز هم جواب صحیح حاصل نشد، دو شاخه جدید زده می شود و مسئله ادامه می یابد.
2-3- تاریخچه مسئله مکان یابی بهینه چاه های نفت
بهینه سازی تولید معمولاً به دو دسته مکان یابی بهینه چاه و کنترل بهینه چاه تقسیم می شود. در مسائل مکان یابی، موقعیت چاه ها به طور بهینه به منظور ماکزیمم یا مینیمم کردن یک تابع هدف یافته می شود، در حالی که در مسئله کنترل چاه پارامترهای چاه نظیر نرخ تزریق یا تولید چاه ها یا فشار ته چاهی54 بهینه می شود. تاریخچه مربوط به مسئله مکان یابی چاه ها بسیار گسترده می باشد. انواع روش های مختلف بهینه سازی، تکنیک های ترکیبی، پروکسی ها، روش های متنوع اعمال قیود غیرخطی در این زمینه تاکنون مطرح شده است. در این بخش، مروری بر تاریخچه مسئله مکان یابی بهینه چاه ها خواهیم داشت.
2-3-1- الگوریتم های بهینه سازی
مسئله مکان یابی بهینه چاه ها یک مسئله چند بعدی و تحت قید می باشد. الگوریتم هایی که به این مسئله ها اعمال می شود به دو دسته کلی روش های مبتنی بر گرادیان55 و روش های آزاد از گرادیان56 تقسیم می شود. روش های آزاد از گرادیان دارای استراتژی های متفاوت جهت جستجوی نقطه بهینه هستند. می توان الگوریتم های آزاد از گرادیان را به دو گروه روش های تصادفی، جستجوی جهانی، و روش های قطعی، جستجوی محلی، دسته بندی کرد. روش های تصادفی نظیر الگوریتم ژنتیک و یا (SimA) Simulated Annealing مدل محاسباتی الهام گرفته از طبیعت یا فرایند های فیزیکی می باشد. روش های تصادفی نیازی به محاسبه مشتق ندارند، همچنین این نوع الگوریتم ها دارای مکانیزمی جهت فرار از به دام
افتادن در دام بهینه های محلی می باشد. اما این روش ها نیاز به ارزیابی زیادی از تابع هدف دارند و عملکرد آن ها وابستگی مستقیمی با نحوه تنظیم پارامتر های این الگوریتم ها دارد. در حالی که روش های بهینه سازی قطعی نقطه بهینه محلی را جستجو می کنند و نیاز به ارزیابی کمی از تایع هدف دارند اما مشابه روش های تصادفی برای جستجو نیازی به محاسبه مشتق تابع هدف ندارند.
روش های بهینه سازی بر مبنای گرادیان نیاز به محاسبه گرادیان تابع هدف نسبت به متغیرهای تصمیم گیری دارند. گرادیان تابع هدف می تواند توسط فرآیند مدل کمکی57 (در ادامه بیشتر توضیح داده خواهد شد.) یا به صورت عددی محاسبه شود. روش های مبتنی بر گرادیان با حرکت در جهت جستجوی مناسب باعث بهبود تابع هدف در هر تکرار می شود. اگرچه این الگوریتم از نظر محاسباتی بسیار کارآمد است اما مضنون به دام افتادن در بهینه های محلی می باشد. در بخش آتی، به طور دقیق تر انواع الگوریتم های آزاد از گرادیان و مبتنی بر گرادیان اعمال شده به مسئله مکان یابی چاه ها بررسی خواهد شد.
2-3-2- روش های بهینه سازی آزاد از گرادیان
2-3-2-1- الگوریتم بهینه سازی تصادفی
عام ترین و معروف ترین الگوریتم تصادفی اعمال شده به مسئله مکان یابی چاه ها روش های ژنتیک و SimA می باشد. الگوریتم SimA از خاصیت سرد شدن فلزات برای یافتن پاسخ در مسائل بهینه سازی بهره می گیرد. این الگوریتم با شروع از یک نقطه در فضای جستجو و ارزیابی تابع هدف در این نقطه کار خود را آغاز می کند. نقطه جدید با تغییری کوچک در نقطه قبلی حاصل می شود. سپس تابع هدف در نقطه جدید ارزیابی می شود، اگر مقدار تابع هدف (به طور مثال برای مسئله مینیمم سازی) کمتر از نقطه قبلی باشد نقطه جدید به عنوان نقطه آغازگر بعدی انتخاب می شود. اما اگر این مقدار بیشتر از نقطه قبلی باشد، این نقطه با یک احتمال متناسب با پارامتر “دما” که نشانگر میزان پیشرفت الگوریتم می باشد قابل قبول است. این الگوریتم تا زمانی که دما به مقدار مینیمم از پیش تعیین شده ای برسد ادامه می یابد. در [13]، الگوریتم SimA به منظور ماکزیمم سازی سود حاصل از برداشت وقتی که متغیرهای تصمیم گیری موقعیت چاه های افقی باشد، اعمال شده است. نوع دیگری از الگوریتم بهینه سازی تصادفی اعمال شده به مخزن روش ژنتیک می باشد. در [14، 15]، روش ژنتیک برای مسئله مکان یابی بهینه چاه ها به کار برده شده است. همچنین در [16]، روش ژنتیک برای مکان یابی بهینه چاه های افقی در یک مخزن گازی اعمال شده است. روش ژنتیک برای مسئله مکان یابی با قیود غیرخطی در [17] بررسی شده است. در [18]، الگوریتم ژنتیک پیوسته برای مکان یابی چاه های نفت پیشنهاد شده است و نتایج با الگوریتم ژنتیک استاندارد مقایسه شده است که نشان دهنده پیشرفت قابل توجهی در پاسخ های مسئله بود. الگوریتم تصادفی PSO یکی دیگر از پرکاربردترین روش های بهینه سازی در امر مکان یابی چاه های نفت می باشد. در [19]، الگوریتم استاندارد PSO به عنوان گزینه ای مقدم بر ژنتیک پیشنهاد شده است و نشان داده شده که به طور میانگین PSO نتایج بهتری را نسبت به روش ژنتیک دارد.
یک دسته دیگر از الگوریتم های تکاملی، روش تکاملی وفقی ماتریس کوواریانس58 می باشد، که به مسئله مکان یابی چاه ها با مکان های نامنظم اعمال شده است [20]. اختلاف نتایج این روش با آنچه که از روش ژنتیک باینری بدست آمده است، بسیار مشهود است و این حاکی از عملکرد بهتر این روش می باشد.
پاسخ های بدست آمده از روش ژنتیک یا PSO می تواند با ترکیب این روش ها با الگوریتم های بهینه سازی دیگری نظیر الگوریتم مورچه ها، جستجوی مستقیم هوک- جویز (HJ)، الگوریتم پولیتپ و یا الگوریتم تابو59 ، بهبود یابد. در قسمت های بعد تاریخچه ای از روش های ترکیبی به کاربرده شده در مسئله مکان یابی چاه ها نیز بررسی خواهد شد. به طور کلی روش های ترکیبی پاسخ بهتری را ارائه می دهند، همچنین هزینه های محاسباتی را کاهش می دهند.
2-3-2-2- روش های بهینه سازی قطعی60
این دسته از روش های بهینه سازی از روش های بهینه یاب محلی هستند که کارایی این الگوریتم ها وابسته به انتخاب حدس اولیه برای شروع الگوریتم می باشد. روش های 61GPS، 62HJDS و MADS روش های بهینه سازی از این دسته هستند که مشابهت هایی نیز به یکدیگر دارند. از مزایای روش های GPS و MADS قابلیت موازی کار کردن این الگوریتم ها می باشد. برای اطلاعات بیشتر درباره نحوه پیاده سازی این الگوریتم ها به [21] مراجعه شود. در [11، 12] نشان داده شده است که الگوریتم HJDS از لحاظ تعداد ارزیابی تابع هدف عملکرد بهتری را نسبت به الگوریتم های GPS و MADS در مسئله کنترل چاه دارد، اگرچه مشخص نیست که آیا این نتیجه برای مسئله مکان یابی نیز صادق است یا نه.
2-3-3- روش های بهینه سازی ترکیبی63
روش های هایبرید، در واقع ترکیب دو یا چند روش بهینه سازی می باشد. این کار باعث می شود تا بتوان از ویژگی های مثبت روش های مختلف استفاده نمود. در [22]، الگوریتم هایبرد با ترکیب روش ژنتیک و پولیتوپ برای مسئله مکان یابی مورد بررسی قرار گرفته است. اگرچه روش ژنتیک در یافتن ناحیه بهینه در فضای جستجو قدرتمند می باشد اما در پالایش آن و رسیدن به نقطه بهینه ضعیف و کند است. در این پژوهش الگوریتم پولیتپ برای رفع این مشکل و افزایش سرعت همگرایی مورد استفاده قرار گرفته است. در [14]، با اضافه کردن شبکه عصبی و روش درونیابی Kriging به عنوان پروکسی به منظور کاهش تعداد شبیه سازی ها، کار صورت گرفته در مقاله [22] بهبود یافت. در این مقاله الگوریتم ژنتیک با ال
گوریتم پولیتوپ و روش تخمین Kriging ترکیب شده است. سپس روش بهینه سازی ترکیبی پیشنهادی بر روی یک مخزن همگن 16*16 گرید با نقطه بهینه معلوم، به منظور اطمینان از صحت عملکرد روش پیشنهادی تست شده است. سپس این روش بر یک مخزن بزرگتر اعمال شده است و تاثیر اپراتورهای ژنتیک و روش ترکیبی، برای یافتن مکان بهینه چاه های تولید و تزریق بررسی شده است. پس از اعمال این روش بر روی مخازن نفتی و انجام سناریوهای متفاوت مکان یابی، مشاهده می شود که الگوریتم ژنتیک ترکیب شده قادر به کاهش تعداد شبیه سازی های مورد نیاز نسبت به الگوریتم ژنتیک معمولی می باشد. مثال های متعدد پروکسی ها در مکان یابی بهینه چاه های نفت شامل روش های Kriging، حداقل مربعات و شبکه های عصبی می باشد. پروکسی ها با تخمینی از مدل مخزن و

دیدگاهتان را بنویسید