— (293)

پایان نامه
مقطع کارشناسی ارشد
رشته: مهندسی صنایع – گرایش سیستم‌های اقتصادی اجتماعی
عنوان: مساله مکان‌یابی تک‌وسیلهای با فاصله متعامد در حضور سه مانع خطی احتمالیاستاد راهنما: دکتر نظام‌الدین مهدوی‌امیری
استاد مشاور: مهندس صابر شیری‌پور
دانشجو: 2099945438785سارا رجائی
20999454191004000020000زمستان 1393
تشکر و قدردانیکیفیت این پایاننامه و مقالات حاصل از آن، مرهون قدرت تمرکز و دقت تحسین برانگیز استاد گرانقدر جناب آقای دکتر نظامالدین مهدویامیری است. امیدوارم با وجود کاستیهایی که داشتهام، توانسته باشم موجبات رضایت ایشان را فراهم آورم.
همچنین، از جناب آقای مهندس صابر شیریپور که در تدوین این پایاننامه همراه من بودهاند، صمیمانه تشکر میکنم.
به علاوه، مراتب قدردانی و سپاسگزاری خود را به اطلاع همه اساتید و دوستانم در دانشگاه علوم و فنون مازندران میرسانم، که سخاوتمندانه تلاش کردند من را با ابعاد مختلف رشته مهندسی صنایع آشنا سازند. تعداد این عزیزان آنقدر زیاد است که در این مختصر امکان ذکر نامشان نیست، اما یادشان همواره در ذهن من خواهد ماند.
تقدیم به
دستان پرمهر پدرم، و نگاه مهربان مادرم،
که رضایتشان آرزوی قلبی من است.
چکیدهدر بسیاری از مسایل مکان‌یابی ضروریست که محدودیت‌های دنیای واقعی در نظر گرفته شوند. نواحی با مانع نمونه‌ای از این محدودیت‌ها هستند. در این نواحی، علاوه بر جایگذاری تسهیلات، حرکت نیز ممنوع است. در این پایاننامه، مساله مکان‌یابی تک‌وسیله‌ای را در حضور سه مانع خطی که در مسیرهای افقی بهطور یکنواخت توزیع شده‌اند، در نظر می‌گیریم. یک مدل برنامه‌ریزی غیرخطی ارایه میکنیم که مجموع کل فواصل متعامد با مانع انتظاری تسهیل جدید از تسهیلات موجود را کمینه می‌کند. همچنین، به منظور حل مسایل توسعه یافته، دو الگوریتم جستجوی الگو و ژنتیک ارایه و نتایج بدست آمده از آنها را مقایسه میکنیم. نتایج محاسباتی نشان میدهند که الگوریتم جستجوی الگو نسبت به الگوریتم ژنتیک، در زمانی کمتر به جواب مطلوبتری دست مییابد.
کلمات کلیدی: مکان‌یابی تک‌وسیله‌ای ، مانع احتمالی خطی، مساله میانه متعامد.
فهرست مطالبعنوانصفحه
TOC \o “1-4” \h \z \u فهرست جدولها PAGEREF _Toc399934970 \h خ‌فهرست شکل‌ها PAGEREF _Toc399934971 \h د‌فصل اول: کلیات پژوهش و ساختار پایاننامه PAGEREF _Toc399934972 \h 11 – 1 مقدمه PAGEREF _Toc399934973 \h 21 – 2 ساختار پایان‌نامه PAGEREF _Toc399934974 \h 5فصل دوم: مروری بر ادبیات موضوع مسایل مکانیابی با مانع PAGEREF _Toc399934975 \h 62 – 1 مقدمه PAGEREF _Toc399934976 \h 72 – 2 مسایل مکان یابی با مانع PAGEREF _Toc399934977 \h 8فصل سوم: زمینههای علمی پژوهش PAGEREF _Toc399934978 \h 143 – 1 مقدمه PAGEREF _Toc399934979 \h 163 – 2 دسته بندی مسایل مکان‌یابی PAGEREF _Toc399934980 \h 183 – 3 فواصل در مسایل برنامه‌ریزی تسهیلات PAGEREF _Toc399934981 \h 203 – 3 – 1 فاصله متعامد یا منهتن PAGEREF _Toc399934982 \h 203 – 3 – 2 فاصله خط‌مستقیم یا اقلیدسی PAGEREF _Toc399934983 \h 213 – 3 – 3 فاصله مجذور خط‌مستقیم یا اقلیدسی PAGEREF _Toc399934984 \h 223 – 3- 4 فاصله چبی‌شف PAGEREF _Toc399934985 \h 233 – 3 – 5 کوتاه‌ترین مسیر PAGEREF _Toc399934986 \h 233 – 4 الگوریتم‌های جستجوی مستقیم PAGEREF _Toc399934987 \h 243 – 4 – 1 الگوریتم جستجوی الگو PAGEREF _Toc399934988 \h 243 – 4 – 1 – 1 الگوریتم جستجوی الگوی هوک و جیوز PAGEREF _Toc399934989 \h 273 – 4 – 2 الگوریتم ژنتیک PAGEREF _Toc399934990 \h 333 – 4 – 2 – 1 مفاهیم کلیدی الگوریتم ژنتیک PAGEREF _Toc399934991 \h 34فصل چهارم: ارایه مدل ریاضی و الگوریتمهای پیشنهادی PAGEREF _Toc399934992 \h 434-1 مقدمه PAGEREF _Toc399934993 \h 444 – 2 ساختار مساله PAGEREF _Toc399934994 \h 454 – 2 – 1 محاسبه فاصله انتظاری PAGEREF _Toc399934995 \h 484 – 2 – 1 – 1 پدیداری PAGEREF _Toc399934996 \h 504 – 2 – 1 – 2 اختلاف ناحیههای X و Xi PAGEREF _Toc399934997 \h 514 – 2 – 1 – 3 محاسبه فاصله افقی مورد انتظار در حالت Ri=2 PAGEREF _Toc399934998 \h 534 – 2 – 1 – 4 محاسبه فاصله افقی مورد انتظار در حالت Ri=3 PAGEREF _Toc399934999 \h 614 – 2 – 2 مدل ریاضی مساله PAGEREF _Toc399935000 \h 944 – 3 کران‌های بالا و پایین مساله مکان‌یابی با مانع PAGEREF _Toc399935001 \h 984 – 3 – 1 کران‌های پایین مساله PAGEREF _Toc399935002 \h 984 – 3 – 2 کران‌های بالای مساله PAGEREF _Toc399935003 \h 994 – 4 الگوریتم حل مساله PAGEREF _Toc399935004 \h 1004 – 4 – 1 الگوریتم جستجوی الگوی هوک و جیوز PAGEREF _Toc399935005 \h 1014 – 4 – 1 – 1 شروع PAGEREF _Toc399935006 \h 1014 – 4 – 1 – 2 جستجوی اکتشافی PAGEREF _Toc399935007 \h 1024 – 4 – 1 – 3 معیار توقف PAGEREF _Toc399935008 \h 1024 – 4 – 2 الگوریتم ژنتیک PAGEREF _Toc399935009 \h 1024 – 4 – 2 – 1 نمایش کروموزوم PAGEREF _Toc399935010 \h 1034 – 4 – 2 – 2 شروع PAGEREF _Toc399935011 \h 1034 – 4 – 2 – 3 ارزیابی PAGEREF _Toc399935012 \h 1034 – 4 – 2 – 4 انتخاب PAGEREF _Toc399935013 \h 1054 – 4 – 2 – 5 نخبه گرایی PAGEREF _Toc399935014 \h 1054 – 4 – 2 – 6 عملگر تقاطع PAGEREF _Toc399935015 \h 1054 – 4 – 2 – 7 عملگر جهش PAGEREF _Toc399935016 \h 1054 – 4 – 2 – 8 معیار توقف PAGEREF _Toc399935017 \h 1064 – 4 – 3 مثال PAGEREF _Toc399935018 \h 1064 – 4 – 4 نتایج محاسباتی PAGEREF _Toc399935019 \h 108فصل پنجم: نتیجهگیری و پیشنهادهایی برای پژوهشهای آتی PAGEREF _Toc399935020 \h 1125 – 1 نتیجه‌گیری PAGEREF _Toc399935021 \h 1135 – 2 پیشنهادهایی برای پژوهشهای آتی PAGEREF _Toc399935022 \h 113فهرست مراجع PAGEREF _Toc399935023 \h 115فهرست مراجع فارسی PAGEREF _Toc399935024 \h 116فهرست مراجع لاتین PAGEREF _Toc399935025 \h 117
فهرست جدولها
TOC \h \z \t “فهرست جداول,1” جدول 4-1 تنظیمات الگوریتم PS PAGEREF _Toc399933609 \h 102جدول 4-2 مختصات تسهیلات موجود در مثال PAGEREF _Toc399933610 \h 107جدول 4-3 اطلاعات جواب برای مثال PAGEREF _Toc399933611 \h 107جدول 4-4 خلاصه‌ای از نتایج محاسباتی برای مسایل با اندازه کوچک110
جدول 4-5 خلاصه‌ای از نتایج محاسباتی برای مسایل با اندازه متوسط و بزرگ111

فهرست شکل‌ها TOC \h \z \t “فهرست شکل‌ها,1” شکل 3-1 مسیرهای متعامد مختلف با طول یکسان بین X و Xi PAGEREF _Toc399933142 \h 21شکل 3-2 فاصله اقلیدسی در صفحه PAGEREF _Toc399933143 \h 22شکل 3-3 ساختار الگوریتم‌های جستجوی الگو PAGEREF _Toc399933144 \h 27شکل 4-1 فضای مساله PAGEREF _Toc399933145 \h 46شکل 4-2 چند مثال برای شیوه محاسبه d1BX,Xi PAGEREF _Toc399933146 \h 48شکل 4-3 عوامل موثر بر E[d1Bx,xi] PAGEREF _Toc399933147 \h 50شکل 4-4 افراز فضای شدنی مساله به چهار ناحیه PAGEREF _Toc399933148 \h 51شکل 4-5 یک مثال از (xs1,xs2)∈ψ1 برای x≤xi PAGEREF _Toc399933149 \h 55شکل 4-6 یک مثال از (xs1,xs2)∈ψ1 برای x>xi PAGEREF _Toc399933150 \h 56شکل 4-7 دو مثال از (xs1,xs2)∈ψ2 PAGEREF _Toc399933151 \h 57شکل 4-8 دو مثال از (xs1,xs2)∈ψ3 PAGEREF _Toc399933152 \h 58شکل 4-9 یک مثال از (xs1,xs2)∈ψ4 PAGEREF _Toc399933153 \h 60شکل 4-10 یک مثال از xs1,xs2∈ψ5 PAGEREF _Toc399933154 \h 60شکل 4-11 دو مثال از xs1,xs2,xs3∈ψ6 PAGEREF _Toc399933155 \h 63شکل 4-12 دو مثال از xs1,xs2,xs3∈ψ7 برای x>xi PAGEREF _Toc399933156 \h 64شکل4-13 دو مثال از xs1,xs2,xs3∈ψ7 برای x≤xi PAGEREF _Toc399933157 \h 65شکل 4-14 دو مثال از xs1,xs2,xs3∈ψ8 برای x>xi PAGEREF _Toc399933158 \h 66شکل 4-15 دو مثال از xs1,xs2,xs3∈ψ8 برای x≤xi PAGEREF _Toc399933159 \h 67شکل 4-16 دو مثال از xs1,xs2,xs3∈ψ9 برای x>xi PAGEREF _Toc399933160 \h 68شکل 4-17 دو مثال از xs1,xs2,xs3∈ψ9 x≤xi PAGEREF _Toc399933161 \h 69شکل 4-18 دو مثال از xs1,xs2,xs3∈ψ10 PAGEREF _Toc399933162 \h 71شکل 4-19 دو مثال از xs1,xs2,xs3∈ψ13 PAGEREF _Toc399933163 \h 72شکل 4-20 دو مثال از xs1,xs2,xs3∈ψ14 PAGEREF _Toc399933164 \h 73شکل 4-21 دو مثال از xs1,xs2,xs3∈ψ15 PAGEREF _Toc399933165 \h 74شکل 4-22 دو مثال از xs1,xs2,xs3∈ψ16 PAGEREF _Toc399933166 \h 75شکل 4-23 دو مثال از xs1,xs2,xs3∈ψ17 PAGEREF _Toc399933167 \h 76شکل 4-24 دو مثال از xs1,xs2,xs3∈ψ18 PAGEREF _Toc399933168 \h 77شکل 4-25 دو مثال از xs1,xs2,xs3∈ψ19 PAGEREF _Toc399933169 \h 78شکل 4-26 دو مثال از xs1,xs2,xs3∈ψ20 PAGEREF _Toc399933170 \h 79شکل 4-27 دو مثال از xs1,xs2,xs3∈ψ21 PAGEREF _Toc399933171 \h 80شکل 4-28 یک مثال از xs1,xs2,xs3∈ψ22 PAGEREF _Toc399933172 \h 82شکل 4-29 یک مثال از xs1,xs2,xs3∈ψ23 PAGEREF _Toc399933173 \h 85شکل 4-30 یک مثال از xs1,xs2,xs3∈ψ24 PAGEREF _Toc399933174 \h 87شکل 4-31 یک مثال از xs1,xs2,xs3∈ψ25 PAGEREF _Toc399933175 \h 89شکل 4-32 یک مثال از xs1,xs2,xs3∈ψ26 PAGEREF _Toc399933176 \h 91شکل 4-33 یک مثال از xs1,xs2,xs3∈ψ27 PAGEREF _Toc399933177 \h 92شکل 4-35 مفروضات برای مثال و جواب بهینه‌ی آن PAGEREF _Toc399933179 \h 107شکل 4-36 تابع هدف برای مثال PAGEREF _Toc399933180 \h 108
فصل اول199136045339004000020000کلیات پژوهش و ساختار پایان‌نامه
1 – 1 مقدمهدر مدیریت، اقتصاد، برنامه‌ریزی تولید، طراحی سیستم‌های صنعتی و غیره، به جوانب مختلفی برمی‌خوریم که مستلزم تصمیمات مکان‌یابی هستند. علاوه بر کاربردهای عملی این نظریه در اتخاذ تصمیمات بهینه، نظریه مکان‌یابی بخش جذاب و چالش برانگیزی از ریاضیات، با مجموعه‌ای رو به فزونی از مسایل است که الزاما خاستگاهی در دنیای واقعی ندارند. CITATION Kla02 \l 1033 [1]واژه مکان‌یابی بر مدلسازی و حل مسایلی اشاره دارد که به دنبال یافتن بهترین مکان برای استقرار مراکز و تسهیلات هستند. به عبارت دیگر، مکان‌یابی عبارتست از انتخاب جایی برای تسهیلات جدید، بهطوریکه هزینه تولید و توزیع کالا و خدمات کمینه شود.
سال 1909 را اغلب سال تولد نظریه مکان‌یابی می‌دانند. آلفرد وبر یکی از نظریهپردازهایی بود که در آن سال به ارایه نظریهای در زمینه مکان‌یابی و کمینه سازی هزینه‌ها پرداختCITATION Gor01 \l 1033 [2]. هزینه هایی که او در نظر گرفته بود، عمدتاً از نوع هزینه‌های حمل‌ونقل بودند.
بعدها طیف گسترده‌ای از انواع مسایل مکان‌یابی متناسب با اهداف پژوهش و با توجه به شرایط متفاوت موجود در فضای مساله مطرح شدند. چند نوع از مسایلی که در ادبیات مکان‌یابی پیوسته مطرح شدند عبارتند از مساله میانه، مساله مرکز و مساله مرکز- میانه.
در مساله میانه، هدف قرار دادن یک تسهیل جدید در صفحه است بهطوریکه مجموع کل هزینه انتقال بین تسهیل جدید و تسهیلات موجود کمینه شود.
از طرفی تقریبا در همه‌ی موقعیت‌های دنیای واقعی با انواع محدودیت‌ها و الزامها مواجه هستیم. در مدلسازی مکان‌یابی محدودیت‌ها میتوانند نواحی ممنوعه باشند، یعنی نواحی‌ای که قراردادن تسهیلات در آن‌ها ممنوع، اما حمل و نقل در آن‌ها آزاد است. پارک‌ها و سایر مناطق حفاظت شده، یا نواحی‌ای که ویژگی های جغرافیاییشان، مانند شیب تند، ساخت تسهیلات مطلوب را در آنها ناممکن می‌کند، مثال هایی از نواحی ممنوعه هستند.
همچنین اغلب نواحی‌ای وجود دارند که نه تنها قراردادن تسهیل جدید در آنها ممنوع است، بلکه حرکت در آنها هم مستلزم هزینه بیشتری است، مانند دریاچه‌هایی که با قایق می‌توان از آنها عبور کرد. این نواحی را نواحی متراکم گویند.
علاوه بر این، در بسیاری مناطق حرکت نیز کاملا ممنوع یا ناممکن است. این مناطق را مانع می‌نامیم. مناطق نظامی، کوهستان‌ها، دریاچه‌ها، رودخانه‌های بزرگ، بزرگراه‌ها، یا در مقیاسی کوچکتر، مناطقی که در سطح یک کارخانه با ماشین‌های حجیم و نقاله‌های حمل مواد اشغال شده‌اند، نمونه‌هایی از موانع هستند. بدون در نظر گرفتن این موانع، نمی‌توان ادعا کرد که مدلسازی واقع بینانه‌ای انجام شده است.
مطلب قابل توجه دیگر اینست که مکان قرارگیری موانع میتواند بهصورت تصادفی باشد مانند یک واگن حمل مواد که در هر لحظه ممکن است در هرجایی از مسیرش در فضای کارخانه قرار گرفته باشد. تصادف‌ها یا ساخت‌و‌ساز و تعمیرات برنامه‌ریزی نشده خیابان‌های یک شهر که باعث انحراف و تاخیر در شبکه حمل‌و‌نقل می‌شوند، نمونه‌های دیگری از موانع احتمالی هستند. این حالت در سایر زمینه‌های پژوهشی، از جمله دانش روباتیک، مورد توجه است، زیرا در طراحی روبات‌ها لازم است به قابلیت آنها در اجتناب از تصادف با موانعی که احتمال می‌رود در مسیرشان قرار داشته باشند، اندیشیده شود.
ما در این پایاننامه مفهوم موانع احتمالی در نظریه مکان‌یابی توجه میکنیم ، و به مدلسازی ریاضی مساله‌ای می‌پردازیم که در آن سه مانع خطی احتمالی که مسیر حرکتشان بهصورت افقی است، در صفحه موجودند. در مساله‌ی مورد بررسی، مفروضات زیر در نظر گرفته شده‌اند:
در مساله مکان‌یابی میانه مورد بررسی ظرفیت تسهیل جدید برای خدمت‌دهی به تسهیلات موجود نامحدود است.
در مدلسازی این مساله از متر متعامد برای تعیین فواصل استفاده می‌شود.
مساله برای کل افق برنامه‌ریزی در ابتدای دوره، سیاست‌گذاری می‌کند، یعنی مساله مکان‌یابی ایستا است.
هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزنی نامنفی است.
سه مانع با طول محدود در صفحه موجودند که از عرض آنها نسبت به طولشان صرف نظر شده است و بهصورت خط راست مدلسازی می‌شوند.
موانع بر روی مسیرهای افقی با مختص y معین قرار دارند.
مکان شروع موانع از توزیع یکنواخت با پارامترهای معین پیروی می‌کنند.
تسهیلات موجود در مسیر موانع مستقر نیستند.
تسهیل جدید نمیتواند در مسیر موانع قرار گیرد.
تنها تسهیل جدید با تسهیلات موجود در تعامل است.
1 – 2 ساختار پایان‌نامهدر ادامه، در فصل 2 ادبیات موضوع مسایل با مانع را بررسی میکنیم. در فصل 3، زمینه‌های علمی پژوهش تشریح میشوند. در فصل 4، به تشریح مساله و مدل پیشنهادی میپردازیم و در ادامه دو الگوریتم جستجوی الگو و ژنتیک برای حل مسایل مورد بررسی معرفی میکنیم. سپس، به مقایسه نتایج حاصل از آنها میپردازیم. سرانجام، پیشنهادهایی برای پژوهش‌های آتی به همراه نتیجه گیری در فصل 5 ارایه میشوند.
فصل دوممروری بر ادبیات موضوع مسایل مکان‌ی214376053619404000020000ابی با مانع
2 – 1 مقدمهمکان‌یابی تک‌وسیله‌ای (تک‌تسهیلی) پیوسته در سطح، حوزه‌ گسترده‌ای از کاربرد مدلسازی ریاضی در دنیای واقعی است. در این مسایل مکان بهینه‌ی یک تسهیل جدید (تسهیل عرضه) به منظور سرویس‌دهی به مجموعه‌ای از تسهیلات موجود (تسهیلات متقاضی)، با توجه به تقاضاهایشان، مشخص می‌شود.
مساله میانه، مساله مرکز و مساله مرکز – میانه چند حالت از مسایل مکان‌یابی هستند که در ادبیات موضوع مورد توجه بوده‌اند. در مساله میانه کلاسیک (که غالبا مساله وبر، مساله فرما – اشنایدر- وبر و مساله کمترین مربعات نیز نامیده میشود) در پی یافتن مکان تسهیل جدید هستیم بهطوریکه مجموعه فواصل وزن‌دهی شده با تسهیلات موجود کمینه شود. برای اطلاعات بیشتر در این زمینه، به فراهانی و حکمت‌فر CITATION Far09 \l 1033 [3]و کلامروس CITATION Kla02 \l 1033 [1] مراجعه کنید. در گونه‌ای از مسایل میانه، با محدودیت در قرارگیری یا حرکت مواجه هستیم. در ادبیات موضوع معمولا سه دسته از این مسایل مطالعه شده‌اند. دسته اول نواحی ممنوعه نامیده می‌شوند که تسهیلات نمیتوانند در این نواحی قرار گیرند، اما حرکت در میان آنها بلامانع و بدون جریمه است (مانند مناطق و پارک‌های حفاظت شده یا مناطقی که مشخصه‌های جغرافیایی از قبیل شیب تند زمین از ایجاد تسهیل مورد نظر ممانعت می‌کند). برای مطالعه بر روی مسایل مکان‌یابی میانه و مرکز در نواحی ممنوعه به هاماخر و نیکل CITATION Ham951 \l 1033 [4] مراجعه کنید.
دسته دوم بهعنوان نواحی متراکم شناخته می‌شوند. در این نواحی، قرارگیری یک تسهیل ممنوع و حرکت از میان آنها با جریمه همراه است (مانند دریاچه‌ای که با قایق بتوان از دو طرف آن عبور و مرور کرد). برای نمونه، مسایل مکان‌یابی با نواحی متراکم، با سرعت و هزینه‌های سفر مختلف، در بوت و کاوالیر CITATION But94 \l 1033 [5]بحث و بررسی شده‌اند.
دسته سوم نواحی‌ای هستند که تسهیل جدید نه میتواند آنجا استقرار یابد و نه میتواند از میان آن عبور کند. این نواحی، نواحی با مانع نامیده می‌شوند. دریاچه‌ها، کوهستان‌ها، مناطق نظامی، رودخانه‌ها، بزرگ‌راه‌ها، و در مقیاس کوچکتر نوار نقاله‌ها و ماشین آلات موجود در سطح کارخانهها نمونه‌هایی از این نواحی هستند.
2 – 2 مسایل مکان یابی با مانعاگر چه مسایل مکان‌یابی با مانع در مقایسه با مسایل مکان‌یابی کلاسیک خیلی عملی‌تر و نزدیک‌تر به دنیای واقعی هستند، اما به علت پیچیدگی محاسباتی‌ای که این نوع مسایل دارند، تنها در چند دهه اخیر در ادبیات موضوع مشاهده شده‌اند.
مدلسازی مکان‌یابی با مانع، برای اولین بار توسط کاتز و کوپر CITATION Kat81 \l 1033 [6]معرفی شد. پژوهشگران یک مساله وبر صفحه‌ای را با فواصل اقلیدسی و یک مانع دایره‌ای در نظر گرفتند. آنها نشان دادند که چنین مسایلی تابع هدفی نامحدب دارند و در ادامه برای حل آن یک روش ابتکاری مبتنی بر کمینه‌سازی متوالی نامقید پیشنهاد دادند. سپس، کلامروس CITATION Kla04 \l 1065 [7] برخی از خواص جبری این مساله را بررسی کرد. نویسنده ناحیه شدنی را به تعدادی سلول‌های محدب با تابع هدف محدب تجزیه کرد، بدین صورت که اگر N تعداد تسهیلات موجود باشد، تعداد این سلول‌های محدب تابعی دوجمله‌ای (یعنی برابر ON2) است. با توجه به اینکه با افزایش N، ساخت این سلول‌های محدب سنگین و پرهزینه میشود، بایشوف و کلامروس CITATION Bis07 \l 1033 [8]با پیشنهاد روشی مبتنی بر الگوریتم ژنتیک (GA) براین مشکل فایق شدند. در ادامه، بایشوف و همکاران CITATION Bis09 \l 1033 [9]از این روش برای مساله مکان‌یابی– تخصیص تسهیلات در حضور موانع چندوجهی و فاصله اقلیدسی استفاده کردند. نویسندگان دو روش ابتکاری را که هریک از روش‌ها از دو جواب اولیه استفاده می‌کرد، معرفی کردند، و سپس براساس نتیجه محاسباتی به بررسی روش‌های ابتکاری پیشنهادی پرداختند.
آنجا و پارلر CITATION Ane94 \l 1033 [10]و بوت و کاوالیر CITATION But96 \l 1033 [11]برای مسایل میانه در سطح و در حضور موانع چندوجهی، روش‌هایی ابتکاری توسعه دادند. آنجا و پارلر CITATION Ane94 \l 1033 [10]برمبنای مفهوم پدیداری و با بهکارگیری الگوریتم کوتاه‌ترین مسیر دایسترا برای مساله مکان‌یابی در حضور موانع چندوجهی (نه لزوما محدب) تحت شرایطی که تابع فاصله از نوع اقلیدسی باشد، به کمک الگوریتم فراابتکاری شبیه سازی تبرید (SA)، یک جواب بهینه تقریبی بدست آوردند. بوت و کاوالیر CITATION But96 \l 1033 [11]حالت خاص مساله آنجا و پارلر CITATION Ane94 \l 1033 [10]را که در آن موانع چندوجهی محدب بودند در نظر گرفتند. نویسندگان با استفاده از گراف پدیداری و با پیشنهاد یک روش ابتکاری مساله وبر مقید را به مساله نامقید وبر در هر تکرار از الگوریتم تبدیل کردند. سپس، براساس یک شرط توقف ، الگوریتم منجر به جواب بهینه موضعی شد. در ادامه، کلامروس CITATION Kla01 \l 1033 [12]با یک رویکرد تجزیه‌سازی متفاوت و کاراتر، مساله اصلی نامحدب را به تعدادی زیرمساله محدب متناهی تبدیل کرد، و سپس یک روش حل دقیق و یک روش ابتکاری مبتنی بر این رویکرد تجزیه‌سازی توسعه داد.
مک گاروی و کاوالیر CITATION McG03 \l 1033 [13]از روش اصلاح شده «مربع بزرگ مربع کوچک (BSSS)» برای مساله مکان‌یابی میانه در حضور موانع چندوجهی و فواصل اقلیدسی بهره بردند. روش BSSS یک الگوریتم هندسی شاخه‌و‌کران است که توسط هانسن و همکاران CITATION Han \l 1033 [14]پیشنهاد شد. این روش ابتدا برای حل مساله مکان‌یابی تسهیلات ناخوشایند پیشنهاد شد. این الگوریتم برای مسایل مکان‌یابی پیوسته به این صورت طراحی شد که از طریق گسسته‌سازی یک سطح یا صفحه پیوسته، ناحیه شدنی را به تعدادی زیرمنطقه مربعی شکل تقسیم کرد.
فریث و همکاران CITATION Fri05 \l 1033 [15]یک مساله مکان‌یابی مرکز را در حضور موانع چندوجهی همراه با تابع فاصله اقلیدسی در نظر گرفتند. نویسندگان با استفاده از رویکرد انتشار امواج رادیویی دایره‌ای، کوتاه‌ترین فاصله بین نقاط را تعیین کردند، و سپس یک آزمایش تجربی را بررسی کردند و یک شبیه‌سازی کامپیوتری برای فواصل اقلیدسی و متعامد ارایه دادند.
در حالت خاص، از فاصله منهتن (متعامد) نتایج گسسته سازی توسط لارسون و صدیق CITATION Lar83 \l 1033 [16]برای مساله وبر با شکلهای دلخواه برای موانع بررسی شد. نویسندگان با ایجاد ساختار شبکه‌ای (شبکه موزاییکی) از گره یال و با تعیین مجموعه متناهی غالب و با بهکارگیری مساله p- میانه مشخص کردند که این شبکه حاوی دستکم یک جوال بهینه است.
این مساله زمینه‌ای برای توسعه و پژوهشها مشابه شد. باتا و همکاران CITATION Bat89 \l 1033 [17]دو مساله مکان‌یابی سطح با فاصله متعامد را هم برای نواحی ممنوعه و هم موانع با شکلهای دلخواه در نظر گرفتند. نویسندگان ابتدا یک مساله p- میانه و سپس یک مساله صف احتمالی میانه را در حضور موانع با شکلهای دلخواه بررسی کردند.
گسسته‌سازی مشابه با لارسون و صدیق CITATION Lar83 \l 1033 [16]توسط هاماخر و کلامروس CITATION Ham00 \l 1033 [18]برای مساله وبر با موانع و فواصل بلوکی انجام گرفت. کارایی محاسباتی روشهای یاد شده توسط دیرینگ و سگراس CITATION Dea02 \l 1033 [19] CITATION Dea021 \l 1033 [20] بهطور قابل ملاحظه‌ای بهبود داده شد. نویسندگان نشان دادند که یک مجموعه غالب کاهش یافته برای این مساله کافی و مناسب است. دیرینگ و همکاران CITATION Dea022 \l 1033 [21]نیز الگوریتمی مبتنی بر یک مجموعه متناهی نامزد بهنام مجموعه غالب برای مساله مرکز با فواصل متعامد پیشنهاد کردند. این نتایج سپس توسط دیرینگ و همکاران CITATION Dea05 \l 1033 [22]برای فواصل با نرم بلوکی توسعه یافتند.
دسته‌ای دیگر از پژوهشها در ادامه مطالعات لارسون و صدیق CITATION Lar83 \l 1033 [16]و باتا و همکاران CITATION Bat89 \l 1033 [17]توسط ساواس و همکاران CITATION Sav02 \l 1033 [23]آغاز شد. نویسندگان مدلی برای قرارگیری تسهیلات با اندازه متناهی توسعه دادند. وانگ و همکاران CITATION Wan02 \l 1065 [24] مساله مکان‌یابی تک‌تسهیلی را در جانمایی کف یک فروشگاه با فواصل متعامد مطالعه کردند. در این مقاله، با توجه به تعداد ورودی و خروجی تسهیلات تقاضای مستطیلی شکل با مکان ثابت، کمترین هزینه مسافت کل از تسهیل عرضه که به تسهیلات سرویس دهد، بدست آمد. تعمیمی از کار ساواس و همکاران CITATION Sav02 \l 1065 [23] توسط کلاچنکاتی و همکاران CITATION Kel07 \l 1065 [25] انجام شد. نویسندگان استقرار یک تسهیل با اندازه محدود در چیدمان را در نظر گرفتند بهطوریکه تسهیل جدید و بخش‌های موجود، مستطیلی شکل و فواصل از نوع نرم l1 بودند. آنها بهعلت اینکه تسهیل جدید بنابر برخی محدودیت‌ها نمیتواند در مکان بهینه استقرار یابد، از خطوط کانتور به منظور یافتن مکان مناسب جایگزین برای بخش جدید استفاده کردند.
ناندیکوندا و همکاران CITATION Nan03 \l 1065 [26] مساله مکان‌یابی مرکز را در حضور موانع با شکلهای دلخواه و فواصل منهتن بررسی کردند. نویسندگان تکنیک تجزیه‌سازی ناحیه شدنی به سلول‌ها را که توسط لارسون و صدیق CITATION Lar83 \l 1065 [16] مطرح شده بود، برای این مساله توسعه دادند. تعمیمی از مطالعه ناندیکوندا و همکاران CITATION Nan03 \l 1065 [26] توسط سرکار و همکاران CITATION Sar07 \l 1065 [27] که مکان‌یابی یک‌تسهیلی را با اندازه محدود و شکل دلخواه در حضور موانع با شکلهای دلخواه و تابع هدف مرکز و تابع فاصله متعامد در نظر گرفتند، انجام شد. همچنین نویسندگان برخلاف ساواس و همکاران CITATION Sav02 \l 1065 [23] به جای مساله میانه، مساله مرکز را درنظر گرفتند. همچنین، آنها تنها رابطه میان تسهیل جدید و تسهیلات موجود را در نظر گرفتند.
در ادبیات موضوع مسایل وبر، علاوه بر موانع چندوجهی و دایره‌ای، یک مانع خطی همراه با تعدادی گذرگاه توسط کلامروس CITATION Kla011 \l 1033 [28]برای هر نوع فاصله دلخواه معرفی شد. در ادامه، کلامروس و ویچک CITATION Kla021 \l 1033 [29] این مدل را برای مساله دوهدفی میانه بررسی کردند.
موانع احتمالی بهطور طبیعی در برخی موارد در دنیای واقعی اتفاق می‌افتند. موانع ممکن است دارای موجودیت تصادفی، مکان تصادفی، یا اندازه تصادفی باشند. برای مثال، در چیدمان تسهیلات، واگن‌هایی را که می‌توان از عرض آنها نسبت به طولشان صرف‌نظر کرد، و بر روی ریل برای حمل داخل کارخانه بهطور مداوم در حرکتند و برای جریان مواد داخل کارخانه تداخل ایجاد می‌کنند، نمونههایی از این موانع خطی با مکان احتمالی هستند. برای مثالی دیگر، چند سکوی نفتی را در نظر بگیرید که قرار است حمل مواد در میان آنها انجام گیرد، اما یک کشتی در میان این سکوها بین دو بارانداز همواره در حرکت است. کانبولات و وسولوسکیCITATION Mus09 \l 1033 [30] برای اولین بار بهطور رسمی بر روی موانع احتمالی بحث کردند. نویسندگان مساله میانه مکان‌یابی یک‌تسهیل را در حضور یک مانع خطی با مکان احتمالی و فواصل متعامد در نظر گرفتند. آنها فرض کردند که نقطه شروع مانع خطی احتمالی دارای توزیعی یکنواخت در یک بعد است، و سپس با محاسبه فاصله مورد انتظار بین دو تسهیل، الگوریتمی برای حل مدل ارایه کردند. در ادامه، شیری‌پور و همکارانCITATION Placeholder1 \l 1033 [31] به مدلسازی ریاضی مساله مکان‌یابی چندتسهیلی در حضور یک مانع خطی احتمالی پرداختند.

فصل سوم229616052666904000020000زمینه‌های علمی پژوهش
3 – 1 مقدمهبرنامه‌ریزی تسهیلات یکی از مضامین اصلی فعالیت‌های مهندسی صنایع است و سالهاست که مهندسین صنایع به کار در این زمینه اشتغال دارند. کار آنها در واقع به طراحی نحوه استقرار اجزای فیزیکی فعالیت‌ها به طور عام، و فعالیت‌های صنعتی بهطور خاص مربوط میشود.
هدف کلی در هر مطالعه به منظور طرح‌ریزی ، تعیین ورودی‌های مورد نظر و طراحی صحیح استقرار اجزای فیزیکی است، به نحوی که ورودی‌ها با کارایی مطلوب از تسهیلات بگذرند و با انجام فرایندهای لازم به خروجی‌های موردنظر تبدیل شوند. CITATION فرق88 \l 1065 [32]بهعنوان برخی از اهداف اصلی برنامه‌ریزی تسهیلات می‌توان به موارد زیر اشاره کرد:
آسان‌سازی فرایند تولید،
کم کردن حجم انتقال مواد (به کمینه سازی جا به جایی‌ها و حمل‌و‌نقل‌ها)،
فراهم کردن ایمنی و رفاه برای کارکنان،
بالا بردن سرعت گردش مواد در جریان ساخت،
کوتاه کردن زمان کل تولید،
پایین آوردن حجم سرمایه‌گذاری بر روی ماشین آلات،
بیشترین استفاده از منابع موجود مانند نیروی انسانی، زمین، و تجهیزات.
به‌طور‌کلی، برنامه‌ریزی تسهیلات تعیین می‌کند که چگونه دارایی‌های ثابت مربوط به یک فعالیت بهترین پشتیبانی برای اهداف آن فعالیت فراهم کند.
مطالعه برنامه‌ریزی تسهیلات موارد زیر را در بر میگیرد:
مکان‌یابی (جایابی): به معنی یافتن محل با مشخصه‌های لازم برای پشتیبانی اهداف،
طراحی تسهیلات: به معنی جانمایی، طراحی سیستم انتقال و ساختار برای رسیدن به اهداف. CITATION نیک91 \l 1065 [33]مکان یابی از نظر اقتصادی نقش مهمی را در میزان سرمایه‌گذاری اولیه برای تاسیس واحد صنعتی، و همچنین در قیمت تمام شده کالا ایفا می‌کند و امکانات رشد و پیشرفت صنایع را فراهم می‌آورد. CITATION فرق88 \l 1065 [32] مطالعات مکان یابی‌از سال 1885 توسط لانهارت آغاز شد و وبر یافته‌های او را تکمیل کرد و گسترش داد.
به طور کلی، جایابی به معنی پیدا کردن محلی برای تسهیلات جدید است به گونه‌ای که
دسترسی به منابع ورودی به سیستم (مانند مواد اولیه) به راحتی صورت گیرد،
مشکلی برای محیط اطراف (رعایت مقررات، ایمنی، و …) ایجاد نشود،
دسترسی به منابع مصرف کننده به راحتی صورت گیرد،
حمل‌و‌نقل در صورت امکان کم و ارتباط امکان‌پذیر باشد،
پارامترهای هزینه حذف یا کم اثر شوند،
نیازهای تسهیلات در صورت امکان در محیط برآورده شوند. CITATION نیک91 \l 1065 [33]مراکز صنعتی و کارخآنجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و بخش‌های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و غیره، با مسایل مکان‌یابی گوناگونی در بخش‌های دولتی و خصوصی، اعم از صنعتی و غیرصنعتی، مواجه می‌شوند. در بخش دولتی، تعیین مراکز خدماتی نظیر ایستگاه‌های پلیس‌راه، اورژانس، بیمارستان‌ها، ایستگاه‌های آتش‌نشانی و غیره نیاز به اتخاذ چنین تصمیماتی دارد. لذا تصمیم‌گیری در مورد مکان‌یابی تسهیلات عمدتا از تصمیم‌گیری‌های بلندمدت و استراتژیک شرکت‌های بزرگ خصوصی و دولتی است و هزینه‌های بالای مربوط به جایابی و استقرار و راه‌اندازی تسهیلات، پروژه‌های مکان‌یابی را به سرمایه‌گذاری‌های بلند مدت تبدیل کرده است. لذا موفقیت یا شکست مراکز تسهیلاتی در هر یک از بخش‌های دولتی و خصوصی، بستگی کامل به مکان‌های انتخابی برای آنها دارد. بدین ترتیب، اهمیت مساله مکان‌یابی و استقرار تسهیلات و ضرورت پرداختن بدان بر همگان روشن است. CITATION بشی88 \l 1065 [34]3 – 2 دسته بندی مسایل مکان‌یابی CITATION نیک91 \l 1065 [33]بهطور کلی مسایل مکان‌یابی از نظر تعداد وسایلی که باید جایابی شوند، به دو دسته تقسیم می‌شوند:
مکان‌یابی یک‌وسیله (انفرادی، تکی): چند وسیله موجودند و مدنظر است که یک وسیله جدید بین وسایل موجود جایابی شود.
مکان‌یابی چندوسیله (مرکب): یک یا تعدادی وسایل موجود است و مدنظر است که چند وسیله جدید در میان وسایل موجود جایابی شوند.
از نظر محل نامزد برای نصب ماشین، استقرار کارخانه و …، مسایل جایابی به دو دسته تقسیم می‌شوند:
جایابی گسسته: محل‌هایی که وسیله یا وسایل جدید میتوانند قرار گیرند، محدود و مشخص باشند.
جایابی پیوسته: بی‌نهایت محل نامزد وجود داشته باشند.
از نظر تسهیلات موجود، مسایل مکان‌یابی به دو دسته تقسیم می‌شوند:
وسیله‌ای از قبل موجود نباشد.
وسایلی از قبل وجود داشته باشند.
از نظر ارتباط بین وسایل جدید با وسایل موجود، دستهبندی زیر را داریم:
بین وسیله جدید با وسایل موجود ارتباط وجود ندارد (جریانی رد و بدل نمی‌شود).
بین وسیله جدید با وسایل موجود ارتباط وجود دارد.
طبقه‌بندی مسایل مکان‌یابی از حیث تعداد پارامترهای موثر نیز به دو دسته صورت میگیرد:
تک‌پارامتری (مثلا مسافت طی شده).
چند پارامتری.
روشهای حل برای مسایل مکان‌یابی بدین قرارند:
روش‌های کمّی و محاسباتی.
روش‌های کیفی.
مسایل جایابی کمّی از حیث تابع هدف به سه نوع زیر دستهبندی میشوند:
تعیین مکان برای وسیله یا وسایل جدید بهطوریکه مجموع کل هزینه‌ها کمینه شود (MiniSum) (کمینه سازی هزینه کل).
تعیین مکان برای وسیله یا وسایل جدید بهطوریکه بیشترین فاصله تا وسایل موجود را کمینه شود (MiniMax) (کمینه سازی بیشینه هزینه).
سایر موارد.
طبقه‌بندی مسایل مکان‌یابی از نظر نوع تسهیلات بدین قرار است:
نقطه‌ای: وسایل جدید نقطه فرض می‌شوند. مثلا یافتن محل آبخوری در دانشگاه (چون خیلی کوچک است).
ناحیه‌ای: وسایل جدید ناحیه فرض می‌شوند. مثلا یافتن محل استادیوم در داخل دانشگاه (چون خیلی بزرگ است).
از نظر نوع مسافت بین ماشین‌آلات جدید و موجود:
در هر مساله مکان‌یابی می‌توان فواصل بین نقاط را به طرق مختلفی در نظر گرفت. انتخاب نوع فاصله در یک مساله مکان‌یابی به نوع مساله و محدوده مورد بررسی بستگی دارد. نوع فاصله انتخابی یکی از تصمیم گیری‌های مهم در مسایل مکان‌یابی است و در تابع هدف موثر است. برخی از انواع فواصل عبارتند از متعامد، خط مستقیم یا اقلیدسی، مجذورفاصله اقلیدسی، چبی‌شف، و کوتاه‌ترین مسیر.
3 – 3 فواصل در مسایل برنامه‌ریزی تسهیلاتاگر مختصات تسهیل جدید بهصورت X=x,y و مختصات وسایل موجود بهصورت Xi=xi,yi در صفحه دو بعدی باشند، آنگاه 5 نوع فاصله زیر را میتوان تعریف کرد.
3 – 3 – 1 فاصله متعامد یا منهتن
در بیشتر مسایل مکان‌یابی ماشین، فاصله در مجموعه‌ای از راه‌رو‌هایی پیموده می‌شود که در الگویی مستطیلی و موازی با دیوارهای ساختمان هستند. در چنین وضعیتی، فاصلهی متناسب بهصورت متعامد مستطیلی، کلان‌شهری، یا منتهتن است (این فاصله گاهی اوقات خطی شکسته، پله‌ای، و راهرویی نیز نامیده می‌شود). فاصله متعامد بین X و Xi را بهصورت زیر تعریف می‌کنیم:
d1X,Xi=x-xi+y-yi(3-1)
فاصله متعامد برای تحلیل‌های آن دسته از مسایل مکان‌یابی شهری‌ مناسب است که در آنها سفر در امتداد مجموعه محدبی از خیابان‌ها اتفاق می‌افتد. بعلاوه، تعدادی از ادارات مجموعه‌ای از راه‌روها و تالارهای متعامد را برای حرکت پرسنل بهکار می‌برند. شکل 3-1 چند مسیر متعامد مختلف بین X و Xi را نشان می‌دهد که طول یکسان دارند.

شکل 3-1 مسیرهای متعامد مختلف با طول یکسان بین X و Xi3 – 3 – 2 خط‌مستقیم یا فاصله اقلیدسیفاصله اقلیدسی بین X و Xi بهصورت زیر تعریف می‌شود:
d2X,Xi=x-xi2+y-yi2(3-2)
فاصله اقلیدسی برای برخی از مسایل مکان‌یابی شبکه، شامل نقاله و سفر هوایی بهکار می‌رود. برخی از مسایل سیم‌کشی الکتریکی و مسایل لوله‌کشی نیز فاصله اقلیدسی را بهکار میگیرند. شکل 3-2 مسیر حاصل از فاصله اقلیدسی را بین X و Xi با خط تیره مشخص می‌سازد.

شکل 3-2 فاصله اقلیدسی در صفحه3 – 3 – 3 مجذور فاصله اقلیدسیدر برخی مسایل مکان‌یابی تسهیلات هزینه تابع درجه اول فاصله نیست. بهعنوان مثال، انتظار می‌رود که هزینه مربوط به عکس‌العمل یک ماشین آتش‌نشانی با فاصله غیرخطی باشد. فرض کنید که هزینه با مربع فاصله اقلیدسی بین X و Xi متناسب باشد. فاصله اقلیدسی بین X و Xi بهصورت زیر تعریف می‌شود:
dESX,Xi=x-xi2+y-yi2(3-3)
این نوع فاصله میتواند در مسایل خدمات اورژانس و آتش‌نشانی کاربرد داشته باشد.
3 – 3- 4 فاصله چبی‌شففاصله چبی‌شف بین دو نقطه X و Xi با علامت tX,Xi نمایش داده می‌شود و بهصورت زیر تعریف می‌شود:
tX,Xi=maxx-xi,y-yi(3-4)
در حالیکه فاصله متعامد برابر مجموع فواصل افقی و عمودی دو نقطه است، فاصله چبی‌شف برابر با بیشترین فواصل افقی و عمودی دو نقطه است.
از جمله کاربردهای این فاصله اینست که حرکت مواد در کارخانه به کمک جرثقیل‌های مجهز به دو موتور انجام می‌شود که یک موتور سبب حرکت در جهت حرکت محور xها و دیگری سبب حرکت در جهت محور yها است. همچنین، این فاصله در مسایل انتخاب سفارش نیز کاربرد دارد.
3 – 3 – 5 کوتاه‌ترین مسیردر مسایل مکان‌یابی روی شبکه، از آنجائیکه معمولا بیش از یک مسیر بین هر دو گره وجود دارند، از روش کوتاه‌ترین مسیر برای تعیین فاصله بین دو گروه استفاده میشود.
3 – 4 الگوریتم‌های جستجوی مستقیمعنوان جستجوی مستقیم که توسط هوک و جیوز CITATION Hoo61 \l 1033 [35]در سال 1961 ابداع شد، برای روش‌های بهینه‌سازی‌ای بهکار میرود که بدون محاسبه یا تخمین مشتق به حل مساله
minxf(x)(3-5)
که در آن، f: Rn⟶R و x∈Rn، میپردازند.
در این روش‌ها، جستجو تنها با استفاده از مقدار تابع هدف هدایت می‌شود. الگوریتمهای بهینه‌سازی زیر نمونه‌هایی از الگوریتم‌های جستجوی مستقیم هستند: CITATION Tor95 \l 1033 [36]الگوریتم‌های جستجوی الگو،
الگوریتم‌های ژنتیک،
روش سیمپلکس نلدرمید CITATION Nel65 \l 1033 [37]،
روش‌های جستجوی تصادفی.
3 – 4 – 1 الگوریتم جستجوی الگوروش‌های جستجوی الگو صورت کلی روش‌های بهینهسازی را دارند. اکنون، قدمهای اساسی را مشاهده میکنیم. CITATION Tor95 \l 1065 [36]الگوریتم کلی جستجوی الگو
جواب اولیه x0 و طول گام اولیه ∆0 را مشخص کن.
برای k=0,1,2,…، انجام ده:
گام 1. همگرایی را بررسی کن و در صورت تشخیص توقف کن.
گام 2. f(xk) را محاسبه کن.
گام 3. جستجوی اکتشافی را برمبنای (∆k,Pk) انجام بده و جهت بهبود sk را معین کن.
گام 4. اگر fxk>f(xk+sk) آنگاه قرار بده: xk+1=xk+sk،
در غیر اینصورت قرار بده: xk+1=xk.
گام 5. (∆k,Pk) را به‌روز‌رسانی کن.
در الگوریتم‌های جستجوی الگو، با توجه به نوع روش جستجو، مقدار تابع هدف در نقاطی حول بهترین جواب بدست آمده در هر تکرار محاسبه می‌شود. چنانچه جوابی بهتر از بهترین جواب موجود در میان این مجموعه جواب‌ها وجود داشته باشد، مسیر حرکت مدل بهینه‌سازی از نقطه موجود به سمت نقطه‌ای ساخته میشود که از مطلوبیت بیشتری از نظر تابع هدف برخوردار است. در این حالت، شبکه‌ی جواب‌های مورد آزمون گسترش مییابد و فضای گسترده‌تری جستجو می‌شود. اما اگر جواب بهتری در میان مجموعه جواب‌های آزمون شده پیدا نشود، آنگاه شبکه مورد آزمون فشرده میشود و مجموعه جواب‌های دیگری که نزدیک‌تر به جواب موجود باشند، آزمون می‌شوند.
یک نمودار گردشی کلی برای الگوریتم‌های جستجوی الگو را می‌توان در شکل 3-3 مشاهده کرد.

شکل 3-3 یک ساختار کلی برای الگوریتم‌های جستجوی الگودر الگوریتم‌های جستجوی الگو، مانند هر روش بهینه‌سازی دیگر، شرط‌های مختلفی میتواند بهعنوان معیار توقف استفاده شود. برخی شرطها میتوانند کمترین اندازه شبکه، بیشترین تعداد تکرارها، یا موارد دیگر باشند. همچنین، برقراری یک یا تعدادی از این شرطها میتواند بهعنوان معیار توقف الگوریتم تعریف شود.
3 – 4 – 1 – 1 الگوریتم جستجوی الگوی هوک و جیوزCITATION Chi12 \l 1033 [38]این روش بهینه‌سازی که در سال 1961 توسط هوک و جیوز ارایه شد، شامل دو نوع حرکت است:
جستجوی اکتشافی: جستجوی اکتشافی یک جستجوی موضعی است که به دنبال یک جهت بهبود برای حرکت است.
حرکت الگو: حرکت الگو جستجوی گسترده‌تری برای بهبود مشخص شده توسط جستجوی اکتشافی است. تا جاییکه بهبود ادامه داشته باشد، این حرکت فضای گسترده‌تری را کاوش می‌کند.
پیش از اینکه الگوریتم جستجوی الگوی هوک و جیوز را بهصورت کامل ارایه دهیم، به بررسی این دو نوع حرکت می‌پردازیم.
3 – 4 – 1 – 1 – 1 جستجوی اکتشافی
موضوع اصلی پیدا کردن یک جهت بهبود است (نه لزوما تندترین جهت بهبود که همان گرادیان یا منفی گرادیان است). اینکار با منحرف شدن از نقطه موجود به مقدار ناچیز در جهت‌های مثبت و منفی محورهای مختصات، و سنجش بهبود یا عدم بهبود مقدار تابع هدف در آن نقاط، انجام میگیرد.
ابتدا اندازه انحرافی را که در هر بعد داریم با تنظیم بردار انحراف P0=∆x1,∆x2,∆x3,…,∆xn مشخص می‌کنیم. الزامی نیست که اندازه انحراف در همه‌ی جهات یکسان باشد، اما عموما همه آنها نسبتا کوچک هستند.
حال با داشتن جواب اولیه‌ی x(0) و مقدار متناظر تابع هدفش، fx(0)، می‌توانیم یک جستجوی اکتشافی اطراف آن داشته باشیم. اینکار را در الگوریتم زیر شرح می‌دهیم:
الگوریتم جستجوی اکتشافی
x(1)⟵x(0) (یعنی مقدار x(0) را در x(1) کپی کن) و قرار ده fbest⟵fx(0).
برای j=1,2, …, n، انجام ده:
گام 1. x(1)⟵x1(1),x2(1),x3(1), …,xj1+∆xj, …,xn(1)، یعنی متغیر jام را به اندازه مقدار انحراف متناظرش در جهت مثبت تصحیح کن.
اگر fx(1) بهتر از fbest است، آنگاه قرار ده fbest⟵fx(1) و گام 2 را برای این متغیر انجام نده.
گام 2. x(1)⟵x1(1),x2(1),x3(1), …,xj1-2∆xj, …,xn(1)، یعنی متغیر jام را به اندازه دو برابر مقدار انحراف متناظرش در جهت منفی تصحیح کن.
اگر fx(1) بهتر از fbest است، آنگاه قرار ده fbest⟵fx(1).
اگر fx(1) بهتر از fbest نیست، آنگاه قرار ده:
x(1)⟵x1(1),x2(1),x3(1), …,xj1+∆xj, …,xn(1).
لازم است به چند نکته در خصوص الگوریتم جستجوی اکتشافی توجه کنیم.
اگر برای یک متغیر، انحراف در جهت مثبت موفقیت‌آمیز باشد (مقدار بهتری برای تابع هدف تولید کند)، آنگاه انحراف در جهت منفی برای آن متغیر بررسی نمی‌شود.
انحراف در جهت منفی صرفا در صورتی برای یک متغیر بررسی می‌شود که انحراف در جهت مثبت برای آن متغیر با شکست مواجه شده باشد (مقدار تابع هدف برای نقاط آزمون بهتر نشود، یعنی یا مساوی نقطه موجود باشد یا بدتر از آن).
این امکان وجود دارد که هم انحراف در جهت مثبت و هم انحراف در جهت منفی برای یک متغیر با شکست مواجه شود، که در اینصورت مقدار آن متغیر تغییر نمیکند.
این الگوریتم همه n2 ترکیب ممکن برای انحراف در جهتهای مثبت و منفی متغیرها را بررسی نمی‌کند. در بدترین حالت، وقتی انحراف در جهت مثبت برای همه متغیرها ناموفق باشد، n2 ترکیب از انحرافات بررسی می‌شوند. و در بهترین حالت، وقتی همه انحراف به سمت بالاها موفقیت‌آمیز باشند، تنها n انحراف مورد آزمون قرار می‌گیرد.
اگر دستکم یکی از انحرافهای آزمون شده به بهبود تابع هدف منجر شود، آنگاه جستجوی اکتشافی موفقیت‌آمیز است و جهت بهبود با برداری که ابتدای آن x(0) و انتهای آن خروجی جستجوی اکتشافی، یعنی x(1)، است مشخص می‌شود. حال، میتوانیم این جهت بهبود را در حرکت الگو بهکار گیریم. اما اگر همه انحرافات برای بهبود تابع هدف با شکست مواجه شوند، آنگاه جستجوی اکتشافی ناکام می‌ماند. بعدا خواهیم دید که در این حالت چه اقدامی صورت می‌دهیم.
3 – 4 – 1 – 1 – 2 حرکت الگو
همه‌ی چیزی که حرکت الگو به آن نیاز دارد، دو نقطه است: نقطه موجود x(0) و نقطه متمایز x(1) که از مقدار تابع هدف بهتری برخوردار است. این یک جهت بهبود برای حرکت در اختیار حرکت الگو قرار می‌دهد.
نقطه جدید x(2) با حرکت از x(0) در جهت x(1) بهصورت زیر تولید می‌شود:
x(2)=x(0)+ax(1)-x(0)(3-6)
بهطوریکه a ضریب شتاب است و طول بردار جهت بهبود، یعنی بردارx(1)-x(0)، را بزرگتر می‌کند. یک انتخاب متداول، 2 a= است، که در این حالت x(2) بهصورت زیر محاسبه می‌شود.
x(2)=2x(1)-x(0)(3-7)
3 – 4 – 1 – 1 – 3 الگوریتم جستجوی الگوی هوک و جیوز
این الگوریتم علاوه بر تابع هدف به چهار ورودی نیاز دارد:
یک نقطه شروع x(0)،
مقدار ضریب شتاب a،
بردار انحراف اولیه P0،
بردار تاب انحراف T=t1,t2,t3, …,tn. همانطور که خواهیم دید، این بردار کوچکترین انحراف ممکن برای هر متغیر را در اختیار قرار میدهد، و از آن بهعنوان معیار توقف الگوریتم استفاده می‌شود.
الگوریتم دارای سه بخش اصلی به صورت زیر است:
مقداردهی اولیه،
روال شروع/ شروع مجدد،
روال حرکت الگو.
الگوریتم جستجوی الگوی هوک و جیوز
مقداردهی اولیه:
نقطه شروع، x(0)، ضریب شتاب، a ، بردار انحراف، P0، و بردار تاب انحراف، T ، را انتخاب کن.
بردار انحراف موجود را بهصورت P⟵P0 مقداردهی اولیه کن.
روال شروع/ شروع مجدد:
با یک جستجوی اکتشافی اطراف x(0) نقطه بهبود x(1) را که مقدار تابع هدف بهتری دارد، پیدا کن.
اگر جستجوی اکتشافی ناکام ماند (یعنی x(1) مقدار تابع هدف بهتری نسبت به x(0) نداشت) آنگاه:
همه انحرافات را با 12 مقدار کنونی‌شان جایگزین کن، یعنی قرار ده P⟵P2.
اگر دستکم یکی از درایه‌های P کوچکتر از تاب انحراف متناظرش در T شد، آنگاه x(0) را بهعنوان جواب گزارش کن، در غیر اینصورت روال “شروع/ شروع مجدد” را فرا بخوان.
در غیر اینصورت (x(1) دارای مقدار تابع بهتری نسبت به x(0) است، و بنابراین یک جهت بهبود داریم):
بردار انحراف را به حالت اولیه‌اش برگردان و قرار ده P⟵P0.
حرکت الگو را انجام ده.
حرکت الگو:
نقطه آزمایشی x(2) را با حرکت از x(0) به سمت x(1) بدست آور.
x(2) نهایی را با جستجوی اکتشافی اطراف نقطه آزمایشی x(2) بدست آور.
اگر fx(2) بدتر از fx(1) است، آنگاه:
قرار‌ده: x(0)⟵x(1) (x(1) بهترین نقطه‌ای است که تاکنون بدست آمده است).
روال شروع/ شروع مجدد را فرابخوان.
در غیر اینصورت (fx(2) بهتر یا مساوی با fx(1) است):
قرارده: x(0)⟵x(1) و x(1)⟵x(2).
حرکت الگو را انجام ده.
توجه کنید که حرکات الگو مادام که موفقیت آمیز باشند تکرار می‌شوند، و معمولا بلندتر و بلندتر می‌شوند. اما هنگامی که حرکت الگو نقطه‌ای تولید کند که مقدار تابع هدفش از بهترین مقدار تابع هدف موجود بدتر باشد (یعنی fx(2) بدتر از fx(1))، آنگاه حرکت الگو خاتمه می‌یابد و الگوریتم به جستجوی اکتشافی اطراف بهترین نقطه موجود می‌پردازد.
همچنین، توجه کنید که یک حرکت الگو ابتدا نقطه آزمایشی x(2) را بدست می‌آورد، و سپس آن را نهایی می‌کند. این به حرکت الگوریتم به سمت جواب بهینه کمک می‌کند.
در نهایت، به معیار توقف الگوریتم توجه کنید: یک جستجوی اکتشافی در اطراف بهترین جواب موجود، به ازای همه‌ی انحرافات ناکام می‌ماند. حتی به‌ازای کوچکترین تاب انحراف که توسط T مشخص شده است. این بدان معنی است که الگوریتم نمیتواند از بهترین جواب موجود یک جهت برای بهبود پیدا کند، و بنابراین همین جواب، جواب بهینه است.
3 – 4 – 2 الگوریتم ژنتیکالگوریتم‌های ژنتیک روشهای نسبتا جدیدی هستند که از آنها برای حل مسایل مختلف استفاده میشود. دو ویژگی اصلی در این روشها، یکی الهام‌گیری از پدیده‌های طبیعی خلقت، و دیگری قابلیت پردازش موازی است. الگوریتم‌های ژنتیک با الهام از فرایند تکامل طبیعی و به عنوان یک روش جستجوی هوشمند در حل مسایل بهینه‌سازی کاربرد گسترده‌ای یافته‌اند. الگوریتم ژنتیک برگرفته از الگوریتم تکاملی است که اولین بار توسط جان هالند CITATION Hol75 \l 1033 [39]در دانشگاه میشیگان پیشنهاد شد و استراتژی‌ها و برنامه‌ریزی‌های تکاملی که توسط رکشنبرگ، شوِفل، فوگوگل و کوزا ایجاد شدند، از جمله روش‌های محاسبه تکاملی هستند.
روش‌های بهینه‌سازی الهام گرفته از طبیعت با روش‌های متعارف بهینه‌سازی تفاوت مهمی دارند. در روش‌های متعارف هر جواب نامزد جدید در صورتی به عنوان جواب جدید انتخاب میشود که مقدار تابع هدف را بهبود ببخشد، ولی در الگوریتم‌های الهام گرفته از طبیعت به همه نامزدهای جدید شانس انتخاب داده می‌شود. الگوریتم‌های ژنتیک تکنیک‌هایی از نوع جستجوی تصادفی را در بر دارند که بر اساس انتخاب طبیعی و نسل شناسی طبیعی کار می‌کنند. یک الگوریتم ژنتیک مستقل از دامنه مساله است و به سرعت فضای جستجو را برای نقاطی با تابع صلاحیت بهتر جستجو می‌کند.
3 – 4 – 2 – 1 مفاهیم کلیدی الگوریتم ژنتیکبا نگاهی به آنچه که تاکنون مطرح شده مشخص است که در تبیین الگوریتم ژنتیک مباحث کلیدی زیر باید بررسی شوند. در ادامه، این مباحث بررسی میشوند:
تعریف یک سیستم کدبندی،
ایجاد جمعیت اولیه،
تعریف عملیات ژنتیک،
تابع پردازش،
استراتژی برخورد با محدویت.
3 – 4 – 2 – 1 – 2 کدبندی
اولین گام در بهکارگیری و پیاده‌سازی یک الگوریتم ژنتیک نمایش جواب‌های مساله بهصورت یک کروموزوم است. در حقیقت، این عمل یک مفهوم کلیدی در الگوریتم‌های ژنتیک است که با استفاده از عمل کدبندی می‌توان الگوریتم را به زبان برنامه نویسی تبدیل کرد.
3 – 4 – 2 – 1 – 3 ایجاد جمعیت اولیه
اولین مرحله پس از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بهکار می‌رود، ایجاد یک جمعیت اولیه از کروموزوم‌هاست. در این مرحله، جواب اولیه معمولا بهصورت تصادفی تولید می‌شود. البته، در بعضی موارد با توجه به نوع مساله و برای بالا بردن سرعت همگرایی الگوریتم، از روش‌های ابتکاری نیز استفاده میشود.
3 – 4 – 2 – 1 – 4 عملگرهای الگوریتم ژنتیک
عملیات ژنتیک فرایند انتقال موروثی ژن‌ها را برای ایجاد اولاد جدید در هر نسل تقلید می‌کنند. یک بخش مهم در الگوریتم ژنتیک ایجاد کروموزوم‌های جدید موسوم به اولاد از طریق بعضی کروموزوم‌های قدیم موسوم به والدین است. این فرایند مهم توسط عملیات ژنتیک صورت می‌گیرد. بهطور کلی، این عملیات توسط دو عملگر عمده انجام می‌شود، عملگر جهش و عملگر تقاطع. اما عملگرها عملا برحسب نوع مساله تعریف میشوند و کاملا به توانایی حل تحلیل‌گر وابسته و تجربی هستند. کارایی این عملگرها در رسیدن به جواب بهینه در مسایل مختلف متفاوت است. بعضی از عملگرها تنها یک کروموزوم را در نظر میگیرند و بر اساس اطلاعات، آن کروموزوم جدید را ایجاد می‌کنند. اما بعضی دیگر بر روی چند کروموزوم و حتی همه کروموزوم‌های جمعیت موجود، عملیات را انجام می‌دهند.
3 – 4 – 2 – 1 – 4 – 1 عملگرهای جهش
اینها عملگرهایی هستند که یک یا چند ژن از یک کروموزوم را انتخاب و مقادیر آنها را تغییر می‌دهند. در این عملگرها یک یا چند محل از یک رشته از نویسهها با طول خاص در نظر گرفته میشود و مقادیر کاراکترها در آن محل ها تغییر می‌یابند. مواردی که در این کار مهم هستند عبارتند از:
تعداد محل‌هایی که قرار است تغییر یابند،
نحوه انتخاب محل‌ها،
نحوه عملیات تغییر.
با مشخص شدن این موارد یک عملگر خاص ایجاد می‌شود که به آن عملگر جهش گفته می‌شود. در این نوع عملگرها از اطلاعات یک جواب استفاده و جواب دیگری ایجاد می‌شود. این تغییر ممکن است کم یا زیاد باشد که به همان میزان از اطلاعات زیاد یا کم استفاده می‌شود. به عبارت دیگر، هر چه تغییرات زیاد‌تر باشد، جواب بدست آمده تصادفی‌تر خواهد بود، و این تصادفی بودن برای ورود مواد ژنتیکی جدید به داخل جمعیت مفید است.
وقتی که جمعیت به سمت جواب خاصی همگرا شود، احتمال جهش باید زیاد شود تا از این عمل جلوگیری کند و برعکس، وقتی جمعیت دارای جواب‌های ناهمسان است، باید احتمال جهش کم شود.
3 – 4 – 2 – 1 – 4 – 2 عملگرهای تقاطع
اینها عملگرهایی هستند که یک یا چند نقطه از دیا چند جواب را انتخاب و مقادیر آنها را تعویض می‌کنند. این عملگرها یک جواب را در نظر میگیرد و محل‌هایی از جواب را با جواب‌های دیگر معاوضه میکند و جواب‌های جدید را می‌سازد. به این نوع عملگرها عملگرهای تقاطع گفته می‌شود. عملگر تقاطع در یک لحظه بر روی دو کروموزوم اعمال میشود و دو نوزاد به وسیله ترکیب ساختار دو کروموزوم ایجاد می‌شوند. یک مفهوم مهم که در ارتباط با این عملگر مطرح است، نرخ تقاطع است.
3 – 4 – 2 – 1 – 4 – 3 مکانیزم نمونه‌گیری
مکانیزم نمونه‌گیری به چگونگی انتخاب کروموزوم‌ها از فضای نمونه‌گیری مربوط می‌شود و یکی از رویکردهای آن نمونه‌گیری تصادفی است. دو نمونه گیری تصادفی که اکثرا از آنها استفاده می‌شود، عبارتند از: انتخاب چرخ رولت و انتخاب کلی تصادفی. انتخاب چرخ رولت که اولین بار توسط هالند پیشنهاد شد، یکی از مناسب‌ترین انتخاب‌های تصادفی است و ایده آن احتمال انتخاب است. احتمال انتخاب متناظر با هر کروموزوم بر اساس برازندگی آن محاسبه می‌شود به طوری که اگر fk مقدار برازندگی کروموزوم kام باشد، آنگاه احتمال بقای متناظر با آن کروموزوم عبارتست از:
pk=fki=0nfi(3-8)
بهطوریکه n اندازه جمعیت هر نسل است. حال، کروموزوم‌ها را بر اساس pk مرتب میکنند و qk را که همان مقادیر تجمعی pk است بهصورت زیر بدست می‌آورند:
qk=j=0kpj(3-9)
در روش انتخاب چرخ رولت به این صورت عمل می‌شود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین صفر و یک تولید میشود و سپس این عدد در هر بازه‌ای که قرار داشته باشد، کروموزوم متناظر با آن انتخاب می‌شود. البته، روش پیاده سازی چرخ رولت بدین صورت است که یک دایره در نظر گرفته میشود و آن را به تعداد کروموزوم‌ها طوری تقسیم می‌کنند که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال، چرخ را چرخانند و هر جا که چرخ متوقف شود، به شاخص چرخ نگاه میکنند و کروموزوم مربوط به آن بخش را انتخاب می‌کنند.
3 – 4 – 2 – 1 – 5 تابع برازش
همانطور که دیدیم، در فرایند انتخاب بارها از عبارت کروموزوم مناسب‌تر صحبت کردیم. بدیهی است که برای تشخیص کروموزوم مناسب‌تر باید یک شاخص برای ارزیابی کروموزوم‌ها موجود باشد.
در مورد مسایل بهینه‌سازی توابع معمولا این شاخص همان مقدار تابع هدف مساله است، یعنی هر کروموزوم تبدیل به جوابی متناظر میشود و در تابع هدف قرار می‌گیرد. آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد، کروموزوم متناسب با آن جواب مناسب‌تر خواهد بود. اما در مورد بعضی مسایل پیچیده‌تر ، باید یک تابع برازش مناسب تعریف کرد.
3 – 4 – 2 – 1 – 6 استراتژی برخورد با محدودیتها
نکته دیگری که در الگوریتم ژنتیک وجود دارد، چگونگی برخورد با محدودیتهای مساله است زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم های ناموجه می‌شوند. چند تکنیک معمولا برای مواجهه با محدودیت وجود دارند که در ادامه به برخی از آنها اشاره می‌کنیم.
3 – 4 – 2 – 1 – 6 – 1 استراتژی اصلاح عملگرها
یک روش برای جلوگیری از تولید کروموزوم غیر موجه اینست که عملگر ژنتیکی طوری تعریف شود که پس از عمل بر روی کروموزوم‌ها، کروموزوم تولید شده نیز موجه باشد. در این حالت، مشکلاتی وجود دارند، مثلا پیدا کردن عملگری که دارای این شرایط باشد بسیار دشوار و از مساله‌ای به مساله دیگر متفاوت است.
3 – 4 – 2 – 1 – 6 – 2 استراتژی ردی
در این روش پس از تولید هر کروموزوم آن را از نظر موجه بودن آزمون میکنند و در صورت ناموجه بودن آنرا حذف می‌کنند. این روش بسیار ساده و کارا است.
3 – 4 – 2 – 1 – 6 – 3 استراتژی اصلاح
در این روش به جای اینکه کروموزوم غیر موجه حذف شود آنرا به یک کروموزوم موجه تبدیل می‌کنند. این روش نیز مانند روش اول به مساله وابسته است و یافتن فرایند اصلاح گاهی بسیار پیچیده است.
3 – 4 – 2 – 1 – 6 – 4 استراتژی جریمه‌ای
در این روش برخلاف سه روش پیشین که از ورود جواب‌های ناموجه جلوگیری می‌کنند، جواب‌های ناموجه با احتمال کم امکان حضور می‌یابند. سه روش بالا این اشکال را دارند که به هیچ نقطه‌ای بیرون از فضای موجه توجه نمی‌کنند، اما در بعضی مسایل بهینه‌سازی جواب‌های ناموجه درصد زیادی از جمعیت را اشغال می‌کنند. در چنین شرایطی، اگر جستجو تنها در ناحیه موجه انجام گیرد، شاید یافتن جواب موجه خیلی وقت‌گیر و مشکل باشد. استراتژی جریمه‌ای از متداول‌ترین تکنیک‌های مورد استفاده برای پذیرش جواب‌های ناموجه است که در آن ابتدا محدودیت‌های مساله در نظر گرفته نمی‌شوند، و سپس برای هر تخلف از محدودیت‌ها یک جریمهای اختصاص می‌یابد و این مقدار جریمه در تابع هدف قرار می‌گیرد.
3 – 4 – 2 – 2 ساختار کلی الگوریتم ژنتیک
ساختار کلی یک الگوریتم ژنتیک را میتوان بهصورت زیر در نظر گرفت.
ابتدا پیش از هر چیز باید مکانیسمی برای تبدیل هر جواب مساله به یک کروموزوم تعریف کرد. پس از آن، یک مجموعه از کروموزوم‌ها که در حقیقت مجموعه‌ای از جواب‌های مساله هستند، به عنوان یک جمعیت آغازین تهیه می‌شوند. این مجموعه که اندازه آن دلخواه است و توسط کاربر تعریف می‌شود، اغلب به صورتی تصادفی ایجاد می‌شود.
پس از این مرحله، باید با بهکارگیری عملیات ژنتیک اقدام به ایجاد کروموزوم‌های جدید موسوم به نوزاد کرد. این عملیات به دو گونه عمده تقاطع و جهش تقسیم‌بندی می‌شوند. همچنین، برای گزینش کروموزوم‌هایی که باید نقش والدین را بازی کنند، دو مفهوم نرخ تقاطع و نرخ جهش کاربرد فراوان دارند که این دو نیز پیش از شروع الگوریتم توسط کاربر تعیین می‌شوند.
پس از تولید یک سری کروموزوم جدید یا اولاد باید با استفاده از عمل تکامل اقدام به انتخاب برازنده‌ترین کروموزوم‌ها کرد. این عمل که در فرایند انتخاب نمود می‌یابد، گلچین کردن کروموزوم‌های برازنده در میان والدین و اولاد است بهطوریکه تعداد کروموزوم‌های منتخب برابر با اندازه جمعیت اولیه باشد. فرایند انتخاب مبتنی بر مقدار برازندگی هر رشته است. در حقیقت، فرایند ارزیابی محتمل‌ترین بحث در فرایند انتخاب است.
تا بدین مرحله یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم پس از تولید چند نسل به تدریج به سمت جواب بهینه همگرا می‌شود. شرط توقف مساله نیز انجام تعداد معینی از تکرار هاست که پیش از آغاز الگوریتم توسط کاربر تعیین می‌شود.
ساختار کلی یک الگوریتم ژنتیک را میتوان به صورت زیر بیان کرد.
روند الگوریتم ژنتیک
گام 1. قرار ده: t=0.
گام 2. جمعیت اولیه، p(t)، را تولید کن.
گام 3. ارزیابی p(t) جهت محاسبه مقادیر برازش.
گام 4. تا زمانیکه شرط خاتمه محقق نشده است، انجام بده:
P(t) را بر اساس مقادیر برازش انتخاب کن، سپس p(t) را به منظور محاسبه c(t) ترکیب کن.
c(t) را ارزیابی کن.
P(t+1) را از p(t) و c(t) بساز.
قرار ده: t=t+1.
گام 5. پایان.
فصل چهارم192468550457104000020000یک مدل ریاضی و الگوریتم‌های پیشنهادی
4-1 مقدمهدر مسایل مکان‌یابی معمولا از نمادگذاری Pos1/Pos2/Pos3/Pos4/Pos5 برای طبقه‌بندی مسایل استفاده می‌شود. این نماد‌گذاری توسط هاماخر و نیکل CITATION Ham95 \l 1065 [40] معرفی شد. در این طرح طبقه‌بندی، Pos1 تعداد (یا شکل) تسهیلات جدید را مشخص می‌سازد. وقتی که می‌خواهیم N≥1 تسهیل جدید را در صفحه جایگذاری کنیم، Pos1 یک عدد صحیح مثبت N قرار داده می‌شود.
در Pos2 فضای تصمیم مساله نشان داده می‌شود. بهعنوان مثال، Rn برای مسایل n بعدی پیوسته، P (یا R2) برای مسایل بهروی سطح، و G برای مسایل مکان یابی در شبکه استفاده می‌شوند.
در این مدل طبقه‌بندی، Pos3 به ویژگی‌های خاص مساله مکان‌یابی مفروض اختصاص می‌یابد. برای نمونه، این مکان میتواند برای تاکید بهروی نواحی ممنوعه موجود در فضای مساله بهکار گرفته شود. برای اینکار، از نماد R در این مکان استفاده می‌شود یا با استفاده از نماد B در محل Pos3 می‌توان حضور موانع در فضای مساله را نشان داد.
در مدل‌های پیوسته، Pos4 شامل اطلاعاتی راجع به تابع فاصله است. بهعنوان مثال، d1 نشان دهنده فاصله متعامد، d2 نشان دهنده فاصله اقلیدسی، و dB نشان‌دهنده حالتی است که تابع فاصله با مانع توسط یک معیار مفروض d محاسبه می‌شود.
در طبقه‌بندی ارایه شده، Pos5 نشان دهنده تابع هدف مساله است. برای نمونه، اگر یک مساله وبر یا میانه مدنظر باشد، آنگاه از نماد Σ در این محل استفاده می‌شود. مسایل مرکز با نماد max، و مسایل وبر ترتیبی با Σord نشان داده می‌شوند. همچنین تابع هدف محدب کلی با نماد fconvex نمایش داده می‌شود.
اگر در هر یک از این مکانها فرض خاصی مدنظر قرار نگیرد، آن مکان را با نماد گلوله () نشان می‌دهند.
براساس مدل طبقه‌بندی تشریح شده، کار ما از نوع 1/R2/B/d1/Σ است.
4 – 2 ساختار مسالهقصد داریم یک تسهیل جدید را در صفحه‌ای شامل m تسهیل موجود و سه مانع افقی احتمالی طوری جایگذاری کنیم که مجموع فواصل با مانع تسهیل جدید از تسهیلات موجود، کمینه باشد. در ادامه، به تشریح دقیق ساختار مساله می‌پردازیم.
صفحه‌ای شامل m تسهیل نقطه‌ای Xixi,yi، i=1,…, m، را در نظر بگیرید. سه مانع خطی افقی به طول L که با Bk، k=1,2,3، نشان داده شدهاند و دارای مختص y ثابت به ترتیب برابر با b1، b2، و b3 هستند نیز در صفحه موجودند، بهطوریکه b1<b2<b3. نقطه شروع هر مانع، Xsk، k=1,2,3، یک متغیر تصادفی یکنواخت با تابع چگالی احتمال زیر است:
f(xsk)=1u2-u1,0, u1≤xsk≤u2سایرموارد ,k=1,2,3,(4-1)
که در آن، u1≤minxixi=1,…,m-3L و u2≥maxxixi=1,…,m+2L .
محل سه مانع مستقل از یکدیگر هستند، یعنی متغیرهای تصادفی Xs1، Xs2 و Xs3 مستقلند، و در نتیجه برای هر 1≤i,j≤3، داریم:
f(xsi,xsj)=1u2-u12,0, u1≤xsi,xsj≤u2سایرموارد(4-2)
و
f(xs1,xs2,xs3)=1u2-u13,0, u1≤xs1,xs2,xs3≤u2سایرموارد(4-3)
فضای شدنی مساله بهصورت زیر است:
F⊆R×R-b1,b2,b3,(4-4)
یعنی هیچ تسهیلی (موجود یا جدید) نمیتواند بر روی مسیر موانع قرار گیرد. اما حرکت صرفا در آن قسمتی از مسیر ممنوع است که مانع قرار گرفته است. بنابراین، حرکت در فضای R2\k=13Bk آزاد است.
با این توصیف، میتوان گفت که مساله مکان‌یابی با مانع احتمالی، یک مساله‌ی ترکیبیِ با مانع و ممنوعه است. به منظور تجسم بهتر فضای مساله، شکل 4-1 را مشاهده کنید.

شکل 4-1 فضای مسالهمسیر موانع را “ریل” نیز می‌نامند. بنابراین، هر ریل پاره خطی افقی با مشخصه bk است که مانع kام روی آن حرکت می‌کند.
در نظر داریم که تسهیل جدید X(x,y) را طوری در فضای F جایگذاری کنیم که مقدار مورد انتظار مجموع فواصل با مانع وزن‌دهی‌شده انتظاری آن با تسهیلات موجود کمینه شود. متری که به منظور تعیین فواصل استفاده می‌کنیم، متر متعامد است. لذا مساله موردنظر بهصورت زیر فرمولبندی می‌شود:
minX∈Fi=1mwiE[d1BX,Xi],(4-5)
که در آن، wi وزن یا میزان تواتر i- امین تسهیل موجود، B=B1∪B2∪B3، و d1BX,Xi نشان دهنده فاصله متعامد با مانع بین X(x,y) و Xi(xi,yi) است:
d1BX,Xi=infdP| است Xi و X بین شدنی متعامد مسیر یک P.(4-6)
چند مثال از شیوه محاسبه d1BX,Xi در شکل 4-2 آمدهاند. در این شکل، d1BX,Xi برابر با طول خط نقطه‌چین است.
34817053911600(d)
00(d)
34817051873250(b)
00(b)
11671303921125(c)
00(c)
11671301873250(a)
00(a)

شکل 4-2 چند مثال از شیوه محاسبه d1BX,Xi4 – 2 – 1 محاسبه فاصله انتظاریاین بخش را که به محاسبه E[d1BX,Xi] از رابطه (4-5) اختصاص داده شده است، با یک لم آغاز می‌کنیم. این لم به بیان یک ویژگی از مسایل مکان‌یابی متعامد در حضور موانع خطی افقی می‌پردازد.
لم 4 – 1. در مسایل از نوع 1/R2/B/d1/Σ، هر گاه موانع بهشکل خطوط افقی باشند، آنگاه تنها فاصله افقی مکان تسهیل بهینه از تسهیلات موجود بهوسیله‌ی مکان موانع متاثر می‌شود.
یعنی برای هر تسهیل موجود Xi=xi,yi، و هر X=(x,y) از F، تنها d1Bx,xi تابعی از محل قرارگیری موانع است. این تابع را با D نمایش می‌دهیم:
d1Bx,xi=D(xs1,xs2,xs3)(4-7)
برای مطالعه برهان لم 4-1، به مرجع CITATION Mus09 \l 1033 [30] مراجعه کنید.
با توجه به ویژگی‌های متر متعامد، و ویژگی بیان شده در لم 4-1، می‌توان تابع هدف مساله (رابطه 4-5) را بهصورت زیر تفکیک کرد:
minX∈Fi=1mwiEd1BX,Xi=minX∈Fi=1mwiE[d1Bx,xi+d1By,yi] =minX∈Fi=1mwiE[d1Bx,xi]+minX∈Fi=1mwiE[d1By,yi] =minxi=1mwiE[d1Bx,xi]+minyi=1mwiy-yi.(4-8)
جواب دلخواه Xx,y∈F و یکی از تسهیلات موجود، Xixi,yi، را در نظر بگیرید. همانطور که در شکل 4-3 می‌بینید، دو عامل زیر بر مقدار مورد انتظار فاصله افقی با مانع X و Xi، یعنی E[d1Bx,xi]، اثر می‌گذارند:
تعداد ریل‌هایی که بین X و Xi قرار گرفته‌اند. بهعنوان مثال، اثر یک ریل بر فاصله دو تسهیل از اثر سه ریل کمتر است.
فاصله افقی X و Xi، یعنی x-xi. بهعنوان مثال، اگر فاصله افقی X و Xi از مجموع طول هر سه مانع بیشتر باشد، آنگاه واضح است که فاصله با مانع و بی‌مانع دو تسهیل با هم برابرند. بهطور کلی، هرچه x-xi کوچکتر باشد، حضور موانع اثر بیشتری بر فاصله مورد انتظار X و Xi می‌گذارد.
36055302977515(c)
00(c)
13766802977515(b)
00(b)
23387051443990(a)
00(a)

شکل 4-3 عوامل موثر بر E[d1Bx,xi]به منظور کمّی‌سازی دو عامل یاد شده به دو متغیر تصمیم نیاز است که آنها را به ترتیب با Ri و Γi نمایش می‌دهیم. Ri و Γi توابعی روی F×F بهصورتهای زیر هستند:
Ri: F×F⟶0,1,2,3,(4-9)
Γi: F×F⟶R+∪0.(4-10)
متغیرهای تصمیم بالا را به تربیت در بخش‌های 4-2-1-2 و 4-2-2 بررسی می‌کنیم. اما پیش از آن به مفهوم پدیداری می‌پردازیم.
4 – 2 – 1 – 1 پدیدارییکی از مفاهیم اساسی که در بحث فاصله با مانع مطرح می‌شود، مفهوم پدیداری است. اگر برای X و Xi داشته باشیم dpBX,Xi=dpX,Xi، آنگاه گوییم این دو تسهیل p- پدیدار هستند. در غیر اینصورت آنها را p- سایه یا ناپدیدار می‌نامیم.
در خصوص مساله مورد بررسی ما، با توجه به لم 4-1، پدیداری وقتی اتفاق می‌افتد که داشته باشیم:
Ed1Bx,xi=d1x,xi=x-xi(4-11)
4 – 2 – 1 – 2 اختلاف ناحیه X و Xiمسیرهای y=bk، k=1,2,3، فضای شدنی مساله را به چهار ناحیه افراز می‌کنند. این نواحی در شکل 4-4 به تصویر کشیده شده‌اند.

شکل 4-4 افراز فضای شدنی مساله به چهار ناحیههمانطور که گفته شد، قصد داریم متغیر تصمیم Ri: F×F⟶0,1,2,3 را با ضابطه زیر تعریف کنیم:
RiX,Xi=0 i∈J1 i∈J’ 2 i∈J” 3 i∈J”'(4-12)
که در آن مجموعه I={i; 1≤i≤m} بهصورت زیر افراز شده است:
J={i∈I; نیست Xi و X بین ریلی هیچ}J’=i∈I; است موجود Xi و X بین ریل یکJ”={i∈I; هستند موجود Xi و X بین ریل دو}J”’=i∈I; هستند موجود Xi و X بین ریل سه.برای رسیدن به متغیر تصمیم بالا، ابتدا متغیرهای تصمیم r1,r2,r3:F⟶0,1 را تعریف می‌کنیم که موضع X را به ترتیب نسبت به ریل‌های مربوط به B1، B2 و B3 مشخص می کنند:
r1=0,1, y<b1y>b1r2=0,1, y<b2y>b2r3=0,1, y<b3y>b3.(4-13)
به همین صورت، ri1، ri2 و ri3 موضع Xi را نسبت به ریل‌های مربوط به B1، B2 و B3 مشخص می‌کنند:
r1i=0,1, yi<b1yi>b1r2i=0,1, yi<b2yi>b2r3i=0,1, yi<b3yi>b3.(4-14)
حال، rX و rXi مشخص می‌کنند که X و Xi هر یک در چه ناحیه ای واقع شده‌اند:
rX=r11+r21+r3=0, y<b11, b1<y<b22, b2<y<b33, y>b3(4-15)
rXi=r1i1+r2i1+r3i=0, yi<b11, b1<yi<b22, b2<yi<b33, yi>b3.(4-16)
و در نهایت، تعریف می‌کنیم:
Ri=rX-rXi =0, i∈J1, i∈J’ 2,



قیمت: 10000 تومان

متن کامل در سایت homatez.com
NameEmailWebsite

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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *