— (643)

دانشکده علوم ریاضی
گروه ریاضی کاربردی
( تحقیق در عملیات )
عنوان:
مدلسازی مسئله تخصیص سهم به تامینکننده با هزینه سفارش وابسته
از:
مهری علی پور
استاد راهنما:
دکتر مهری باقریان
اسفند 1393
تقدیم به …
وجود مهربان ترین هایم، خانواده عزیزم
که در لحظه لحظه زندگی، گرمی کلامشان سرمایه جاودانی زندگیم است.
بلندای وجودشان استوارتقدیر و تشکر…سپاس خداوندگار حکیم را که با لطف بیکران خود، آدمی را زیور عقل آراست.
از استاد عزیز و بزرگوارم سرکار خانم دکتر مهری باقریان که باحسن خلق و درایت زحمت راهنمایی این رساله را به عهده گرفتند و از آقایان دکتر مازیار صلاحی و دکتر محمد کیانپور که زحمت داوری این رساله را متقبل شدهاند کمال تشکر و قدردانی را دارم.
از همسر عزیزم که عاشقانه تشویقم کرد و گلهای زندگیم، علیرضا ومحمدرضا که مرا همراهی کردند سپاسگزارم.
از مادر و خواهر همسرم به پاس مهربانیهای بیدریغشان و پدر و مادر عزیزم سپاسگزارم و در پایان تشکر میکنم از تمامی دوستانی که مرا در این امر یاری نمودهاند، از خداوندگار هستی برایشان سلامتی و عاقبتی خیر را آرزومندم.
مهری علیپور
فهرست مطالبعنوان صفحه
TOC \o “1-3” \h \z \u فهرست مطالبت
فهرست شکلهاج
فهرست جدولهاچ
چکیدهح
مقدمه : PAGEREF _Toc417745858 \h 1فصل اول PAGEREF _Toc417745859 \h 3مسئله تخصیص سهم به تامینکننده PAGEREF _Toc417745860 \h 41-1 جریان مواد PAGEREF _Toc417745861 \h 51-2 : انواع سیستمها6
1-3 : مسائل تصمیمگیری PAGEREF _Toc417745863 \h 61-4 : معیارهای تصمیمگیری PAGEREF _Toc417745864 \h 61-5 : مخارج سیستمهای انبار PAGEREF _Toc417745865 \h 71-6 مدلسازی سیستمهای تصادفی تکدورهای PAGEREF _Toc417745866 \h 81-7 مدل مسئله تخصیص سهم به تامینکننده PAGEREF _Toc417745867 \h 91-7-1 نشانهها و نمادها……………………… PAGEREF _Toc417745868 \h 91-7-2 مدل پیشنهادی مسئله PAGEREF _Toc417745869 \h 101-7-3 روش حل مدل پیشنهادی PAGEREF _Toc417745870 \h 12فصل دوم PAGEREF _Toc417745871 \h 14متاهیوریستیک PAGEREF _Toc417745872 \h 152-1 الگوریتم ژنتیک (GA) PAGEREF _Toc417745873 \h 152-1-1 مزایای الگوریتم ژنتیک PAGEREF _Toc417745874 \h 162-1-2 طرح کلی از GA پیشنهادی PAGEREF _Toc417745875 \h 172-2 روش شبیه سازی تبریدSA PAGEREF _Toc417745876 \h 282-2-1: مقایسه با پدیدههای فیزیکی PAGEREF _Toc417745877 \h 282-2-2- روش کار الگوریتم شبیه سازی تبرید PAGEREF _Toc417745878 \h 292-2-3 : همگرایی الگوریتم انجماد تدریجی PAGEREF _Toc417745879 \h 312-2-4 طرح کلی از SA پیشنهادی PAGEREF _Toc417745880 \h 322-2-5 : اجزای الگوریتم شبیه سازی تبرید PAGEREF _Toc417745881 \h 332-2-6  انتخاب پارامترهای برنامه انجماد PAGEREF _Toc417745882 \h 35فصل سوم PAGEREF _Toc417745883 \h 393-1 ارائهی مثالهای عددی PAGEREF _Toc417745884 \h 403-2 نحوه کدگذاری با توجه به نمادهای مدل پیشنهادی PAGEREF _Toc417745885 \h 433-3 نتایج حاصل از حل مثالها PAGEREF _Toc417745886 \h 463-4 الگوریتم ژنتیک در متلب PAGEREF _Toc417745887 \h 493-5 الگوریتم شبیه سازی تبرید در متلب PAGEREF _Toc417745888 \h 503-6 مقایسه الگوریتم ژنتیک و تبرید تدریجی PAGEREF _Toc417745889 \h 513-6-1 آزمون تی نمونه های مستقل PAGEREF _Toc417745890 \h 523-7 نتیجهگیری کلی PAGEREF _Toc417745891 \h 533-8 پیشنهادهای ادامهی کار PAGEREF _Toc417745892 \h 54پیوستها PAGEREF _Toc417745894 \h 55پیوست 1 PAGEREF _Toc417745895 \h 56پیوست 2 PAGEREF _Toc417745896 \h 57واژهنامه انگلیسی به فارسی PAGEREF _Toc417745897 \h 58فهرست مراجع PAGEREF _Toc417745893 \h 62فهرست شکلها TOC \h \z \c “شکل” شکل 1-1: منحنی قیمت _ مقدار12
شکل 2-1: روند کلی الگوریتم ژنتیک PAGEREF _Toc411862420 \h 18شکل 2-2: نمونه ای از انتخاب در چرخ رولت25
شکل 3-1: نحوه فعال کردن GA ………………………………………………………………………………………………..49
شکل 3-2: پنجره GA ……………………………………………………………… …………………………………………..50
شکل 3-3: پنجره SA ……………………………………………………………………… …………………………………..51

فهرست جدولهاجدول صفحه
TOC \h \z \c “جدول” جدول 2-1: تشکیل کروموزم21
جدول2-2: مثالی از تبدیل کد گذاری22
جدول 2-3: محاسبه تابع بهینه23
جدول 2-4: محاسبه درصد برازندگی23
جدول2-5: تشکیل چرخ رولت25
جدول 2-6: عمل پیوند26
جدول 2-7: مقایسه بین یک مساله و الگوریتم بهینهسازی با یک سیستم فیزیکی………………………………………………………………………….29
جدول 3-1: مقادیرqij و tij در مثال 140
جدول 3-2: مقادیرxijmax وxijmin در مثال 141
جدول 3-3: aij و bij در مثال 141
جدول 3-4: aij و bij در مثال 242
جدول 3-5: مقادیرxijmax وxijmin در مثال 242
جدول 3-6: مقادیرqij در مثال 342
جدول 3-7: مقادیر tij در مثال 443
جدول3-8: جوابهای ایده ال از یک مجموعه 5 تایی مثال عددی46
جدول3-9: ادغام مقادیر اهداف تابع z برای هر مثال47
جدول3-10: بهینه (نزدیک بهینه) تابع هدف z4, z3,z2,z1 مطابق z در مثال 248
جدول 3-11:مقادیرxij بدست آمده از GA در مثال248
جدول3-12:مقادیرxij بدست آمده از SA درمثال 248

چکیدهمدلسازی مسالهی تخصیص سهم به تامینکننده با هزینهی سفارش وابسته
مهری علیپور
یکی از موضوعات جالب توجه در مدیریت زنجیره تامین، مدیریت عرضه است که بهطورکلی مربوط به فعالیتهای مربوط به تامینکنندگان ازقبیل توانمند سازی، ارزیابی مشارکت و … است. هدف اصلی از ارزیابی تامینکنندگان کالا، تعیین سهمیه مطلوب اختصاص داده شده بههر تامینکننده کالا در هنگام سفارش دادن خریداران میباشد.
در این پایاننامه یک مدل چندهدفه پیشنهاد میشود که در آن هزینههای خرید، واحدهای مرجوع شده و تاخیر در تحویل واحدها به حداقل و نمره کل بهدست آمده از فرایند ارزیابی تامینکننده کالا به حداکثر برسد. فرض میکنیم که خریدار، محصولات متعددی از تعدادی تامینکننده از پیش تعیین شده تهیه میکند. تقاضای خرید، تصادفی با توزیع احتمال پواسون برحسب قیمت هر نوع محصول میباشد. همچنین فرض اصلی ایناست که قیمتهای تامینکننده کالا بهصورت خطی وابسته به اندازه سفارش هر محصول است. از آنجا که تقاضا تصادفی است، خریدار ممکن است علاوه بر هزینهی خرید منظم، متحمل هزینههای نگهداری و کمبودکالا نیز بشود.
ما بهکمک روش معروف متریکL-1 برای حل مساله ارزیابی تامینکننده کالا از دو الگوریتم ابتکاری GA وSA استفاده میکنیم.
کلمات کلیدی : ارزیابی تامینکننده کالا ، اختصاص سهمیه ، تقاضای تصادفی ، قیمت وابسته به تقاضا.

A b s t r a c tModeling a supplier quota allocation problem with price-dependent ordering
Mehri Alipour
One of the interesting subjects in supply chain management is supply management, which generally relates to the activities regarding suppliers such as empowerment, evalution and so on. A major objective of supplier evaluation involves buyers determining the optimal quota allocated to each supplier when placing an order.
In this thesis, we propose a multi-objective model in which purchasing cost, rejected units, and late delivered units are minimized, while the obtained total score from the supplier evaluation process is maximized. We assume that the buyer obtains multiple products from a number of predetermined suppliers. The buyer faces a stochastic demand with a probability of Poisson distribution regarding each product type. A major assumption is that the supplier prices are linearly dependent on the order size of each product. Since demand is stochastic, the buyer may incur holding and stock out costs in addition to the regular purchasing cost. We use the well-known L-1 metric method to solve the supplier evaluation problem by utilizing two meta-heuristic algorithms (SA and GA) to solve the corresponding mathematical problems.
Keywords: Supplier selection, Quota allocation, Stochastic demand, Price-dependent demand.
مقدمه :
در دهه گذشته، مدیران به اهمیت نقش زنجیره تأمین SCM در ارزشآفرینی شرکتها پیبردهاند. اسمیچی لوی و همکاران (2004) SCM را بهعنوان مجموعهای از روشهای مورد استفاده برای ادغام موثر تامینکنندگان، انبارها و فروشگاهها تعریف میکند بهطوریکه برای بهحداقل رساندن سیستم گستردهی هزینهها، کالا در مقادیر مناسب تولید شود و به مکان مناسب برده و در زمان مناسب توزیع شود، در حالیکه خدمات مورد نیاز در سطح رضایت بخش باشد [3]. فعالیت خرید بهعنوان یک قابلیت رقابتی یکی از مهمترین فعالیتهای زنجیره تامین است. با توجه به نقش تعیینکنندهی تامینکنندگان در کیفیت محصول نهایی و نهایتا رضایت مشتری، سازمانها عملکرد تامینکنندگان خود را بهصورت دورهای ارزیابی مینمایند. از آنجا که ادبیات در انتخاب تامینکننده کالا گسترده است ما مسئلهی اختصاص سهمیه تامینکننده را روی مواردی که در تکنیکهای مدلهای تصمیمگیری چندهدفه MODM استفاده میشود مختص میکنیم. درحال حاضر تحقیقات در این زمینه به بخشهای زیر تقسیم میشود:
– مدلهای برنامهریزی ریاضی فقط با یک تابع هدف: با توجه به مدلهای با یک تابع هدف، قدسیپور و ا برایان(2001) یک مدل برنامهریزی غیرخطی عدد صحیح مختلط را بهمنظور حل مسئلهی چندهدفه منابع برای بهحداقل رساندن هزینه کل خرید سالانه فرموله کردند [4].
-مدلهای برنامهریزی ریاضی با دو تابع هدف، مینیمم کردن هزینه و ماکزیمم کردن سود: ونتورا و مندوزا (2008) یک روش دو مرحلهای برای مسئله انتخاب تامینکننده کالا و تخصیص مقدار سفارش بهطور همزمان ارائه کردند. چه و وانگ (2008) یک الگوریتم پایه ژنتیک و مفاخری و همکاران(2011)، برنامهریزی پویا چندهدفهیدو مرحلهای برای آن پیشنهاد کردند و جعفری و همکاران (2011) یک مدل عدد صحیح مختلط دو هدفه برای مینیمم کردن مجموع هزینهها و ماکزیمم کردن بازده کل ارائه کردند [5-8].
– مدلهای با حداقل سه تابع هدف، بهحداقل رساندن هزینه، اقلام تاخیری و واحدهای مرجوع شده: کارپاک و همکاران(2001) یک مدل برنامهریزی هدف برای مسئله ارزیابی و انتخاب تامینکنندگان با سه هدف شامل هزینه،کیفیت و توانایی تحویل پیشنهاد کردند. فضلالهپور و همکاران (2011)، رضایی و داوودی(2011)، سیفبرقی و اسفندیاری (2011) نیز از جمله کسانی هستند که در این مورد پژوهش کردند [9-12].
– مدلهای فازی که با ابهام و عدم دقت در داده های ورودی مانند تقاضا و ظرفیت مواجه میشوند: عمید و همکاران (2006) و کومار و همکاران (2006) مدلهای برنامهریزی چندهدفه فازی ارائه کردند [13و14].
– مدلهایی با انواع مختلف تخفیفهای تامینکنندگان، با توجه به پیچیدگی مسئله از الگوریتم ابتکاری برای حل آن استفاده شدهاست: معقول و رزمی(2009)، محمد ابراهیم (2009) و کمالی و همکاران (2011) در این زمینه تحقیق کردند [15-17].
– مدلهای با عدم قطعیت تقاضا، ظرفیت و غیره: لی و زابینسکی(2011) و ژانگ و ژانگ (2011) یک مسئله انتخاب تامینکننده کالا، تکمحصول، تکهدفه و مسئله خرید تحت تقاضای تصادفی را بیان کردند. هدف به حداقل رساندن انتخاب، خرید، نگهداری و هزینههای کمبود برای انتخاب تامینکنندگان و تخصیص مقدار سفارش می باشد [18و19].
در این پایان نامه فرض میکنیم، خریداری که محصولات مختلف را از تعدادی تامینکنندهی از پیش تعیین شده فراهم میکند، با تقاضای تصادفی و توزیع احتمال پواسون مواجه است. از آنجا که تقاضا تصادفی است خریدار با هزینههای کمبود و نگهداری کالا، علاوه بر هزینه خرید بهطور معمول، مواجه میشود. همچنین فرض کردهایم که قصد خریدار جایگذاری مینیمم مقدار سفارش برای هر تامینکننده است. نیاز چنین فرضی ایناست که خریدار مایل به حفظ همکاری مستمر با تامینکنندگان انتخابشده باشد. لذا قیمت ارائه شده برای هر تامینکننده کالا بهصورت خطی وابسته به اندازه سفارش هر محصول است.کاستا و الیویرا (2001) استراتژیهای تکاملی مانند الگوریتم ژنتیک (GA) و شببیه سازی تبرید (SA) را بهعنوان بهترین الگوریتم برای حل مسائل برنامهریزی صحیح غیرخطی NIPمعرفی کردند[20]. در فصل اول با معیارهای تصمیمگیری و نمادها و فرمولبندی مسئله آشنا میشویم. در فصل دو به بررسی الگوریتمهای راهحل پرداخته و در فصل سه بهمنظور بررسی مدل و ارزیابی عملکرد روشهای پیشنهاد شده، مثالهایی ارائه و نتایج حاصل از حل آنها مقایسه میشود.

فصل اولمفاهیم اولیه
معیارهای تصمیم گیری، نمادها و ارائهی مدل

مسئله تخصیص سهم به تامینکنندهبرای آشنایی بیشتر با اهمیت مسئله تخصیص سهم به تامینکننده، ابتدا به ذکر چند تعریف میپردازیم.
زنجیره تامین: تمام فعالیت‌هاى مرتبط با جریان و تبدیل کالاها از مرحله ماده خام (استخراج) تا تحویل کالاى نهایى به مصرفکننده نهایى و نیز جریان‌هاى اطلاعاتى مرتبط با آنها را شامل مى‌شود.
مدیریت زنجیره تامین: یکپارچه سازى فعالیت‌هاى زنجیره تامین و نیز جریان‌هاى اطلاعاتى مرتبط با آن، از طریق بهبود و هماهنگ سازى فعالیت‌ها در زنجیره تامین از جمله موجودی و ترابری، تولید و عرضه محصول، براى دستیابى به مزیت رقابتى قابل اتکا و دائمی می باشد، تا بهترین ترکیب ممکن از پاسخدهی و کارایی برای بازاری که آن را تغذیه می کند بهدست آید.
تامینکننده: تامینکننده کسی است که بخشی از کالاها یا خدمات موردنیاز یک سازمان را درجهت تولید محصول یا ارائه خدمت به مشتری تامین میکند.
برای پیادهسازی مدیریت زنجیرهی تامین موانعی وجود دارد که عبارتند از:
تعدد مراکز تصمیمگیرى
عدم اطمینان زنجیره تامین از پیشبینی تقاضا
عدم اطمینان زنجیره تامین از زمانهای تحویل
عدم هماهنگی یک بخش شرکت با دیگر بخشها
تغییرات نامنظم در سفارشات
که اهمیت تعیین و تخصیص سهم به تامینکننده را بیشتر میکند.
تغییرات بسیار سریعی که در سرتاسر بازارهای جهانی اتفاق میافتد، به طور اساسی روشی را که مدیران به محیطشان مینگریستند، تغییر داده است. یکی از حوزههایی که مدیران توجه خود را بیشتر به آن معطوف کردهاند، مدیریت منبعیابی و خرید است.
سازمان باید اطمینان یابد که خرید انجام شده با الزامات و نیازمندیهای خرید انطباق دارد. نوع و گسترهی کنترل اعمال شده بر تامین کننده و اقلام/مواد و تجهیزات خریداری شده بر مراحل بعدی پدیدآوری محصول یا بر محصول نهایی بستگی دارد. سازمان باید تامینکنندگان را بر پایه توانایی آنان در تامین اقلام/مواد و تجهیزات/خدمات بر طبق الزامات سازمان ارزیابی و انتخاب کند. معیارهای انتخاب، ارزیابی و ارزیابی مجدد باید تعیین گردد.
در دهه اخیر، مدیریت خرید، در زنجیره تأمین چالشی برای عمدهی شرکتها بوده است و دستیابی به یک سطح رقابتی جهانی در زمینه تأمین، به یک نیاز اساسی تبدیل شده است. در بیشتر صنایع هزینه مواد خام (و قطعات(، هزینه اصلی محصول نهایی را تشکیل میدهند. بنابراین، دپارتمان خرید میتواند نقش کلیدی در کارایی و اثربخشی یک سازمان ایفا کند، زیرا میتواند اثر مستقیمی روی کاهش هزینه، سودآوری و انعطاف پذیری شرکت داشته باشد. بدون تردید، مهمترین و حساسترین مرحله در فرآیند خرید هر سازمان، ارزیابی و انتخاب تأمینکنندگان بهمنظور اختصاص سهم مناسب است. اهمیت انتخاب تأمینکننده از این حقیقت ناشی میشود که آنها تأمین منابع را تعهد میکنند، درحالیکه به طور همزمان بر فعالیتهایی، از قبیل مدیریت موجودی، برنامهریزی و کنترل تولید، الزامات جریان وجوه نقد و کیفیت محصول نیز اثر میگذارند.
در این بخش برای آشنایی با مسئله و مدل مربوط به آن، به مقدماتی در ارتباط با سیستمهای مختلف و معیارهای تصمیمگیری در آنها ، برگرفته از منبع [1] پرداخته میشود.
1-1 جریان موادموسسههای تولیدی، مواد اولیه و قطعاتی را تهیه و تا زمان نیاز انبار میکنند. تهیه و مدیریت انبار اقلام مربوطه را “تدارک” مینامیم. این عمل(تدارک)، مواد ورودی بخش تولید را تامین میکند. بخش “تولید” با پردازشهای لازم روی مواد اولیه و قطعات، تولیدات خود را تامین میکند. کالای تکمیل شده ممکن است در کنار مرکز تولید یا انبارهای محلی نگهداری شود. در هر حال کنترل کمیت آنها بخشی از وظایف”توزیع” است.
سه مشخصه جریان مواد مورد توجه مدیریت تولید قرار میگیرد:
کیفیت
کمیت زمانی
مخارج
منظور ازکیفیت، میزان انطباق خصوصیات تولید بر خصوصیات تعیین شده قبلی میباشد. منظور ازکمیت زمانی، حجم مواد پردازش شده در هر دوره زمانی و منظور از مخارج، بهای کلیه منابع و امکانات بهکار گرفته برای تولید کالا میباشد.
1-2 : انواع سیستمهابه طور کلی چهار نوع سیستم جریان مواد را میتوان برشمرد:
سیستم تولید پیوسته که انواع محدودی کالای مشابه در حجم زیاد و بطور دائم تولید میکند.
سیستم تولید منقطع که حجم زیادی از یک نوع کالا تولید و سپس تولید کالای دیگری شروع میشود.
سیستم پروژهای که یک یا چند نوع کالا اغلب فقط برای یک مرتبه تولید میکند.
سیستم انبار محض که پردازشی روی مواد صورت نمیگیرد و فقط کالایی تهیه و به متقاضیان تحویل میشود.
ازآنجا که مسئله اختصاص سهم به تامین کننده به سیستمهای انبار مربوط میباشد به تشریح معیارهای تصمیمگیری مربوط به سیستمهای انبار میپردازیم.
1-3 : مسائل تصمیمگیریتصمیماتی که برای اداره سیستمهای تولیدی و انبار گرفته میشود، عموما دو نوع میباشند: نوع اول آنهایی که از روی قاعده و بهمنظور تنظیم جریان مواد صورت میگیرد، نوع دوم آنهایی که گهگاه به منظور اعمال سیاستها و ظرفیتها است.
در سیستمهای انبار محض تصمیمات اساسی عبارتند از:
چه اقلام یا کالایی را انبار نمود؟
چه موقع سفارش تهیه کالا داد؟
چقدر سفارش داد؟
به چه کسی سفارش داد؟
جهت بهعمل آوردن این تصمیمات بهطورمنطقی، سیستم مدیریت باید شامل یک روال پیش بینی تقاضا و یک سیاست سفارش باشد تا با توجه به سطح موجودی و حجم تقاضا مقدار سفارش را تعیین نماید.
1-4 : معیارهای تصمیمگیریاهدافی که در کلیه تصمیمگیریهای مربوط به جریان مواد مورد توجه میباشند متنوع بوده و ممکن است در سیستمهای مشابه، متفاوت یا بالعکس در سیستمهای متفاوت، مشابه باشند. بههرحال بعضی از این اهداف عبارتند از:
کسب حداکثر درآمد
کاهش هزینه تدارک، تولید و توزیع
ارائهی سرویس خوب و جلب رضایت مشتری
کاهش میزان سرمایهگذاری در انبارها
پایین نگهداشتن حجم سرمایهگذاری روی وسایل تولید
در ساخت مدلها سعی میشود کارایی ها بر اساس یک واحد پولی اندازهگیری شوند. همچنین در این مدلها عوامل اقتصادی زیر بر حسب تناسب مورد توجه قرار می گیرند:
درآمدهای حاصل از فروش
مخارج تولید، تهیه و توزیع
زیانهای ناشی از کمبودات
مخارج سرمایهگذاری در انبارها
هزینههای تغییر نرخ تولید
هزینههای تغییر سطح نیروی کار
هزینههای تغییر امکانات.
1-5 : مخارج سیستمهای انبارمنظور از انبار، تجمع (یا ذخیره سازی) اشیایی است که بعدا برای ارضای نیازها و تقاضاهایی مصرف خواهند گردید. موجودی انبار عبارتست از حجم یا تعداد واحدهای کالایی که در انبار و در دسترس موجود است. وقتیکه موجودی انبار صفر است، گوییم حالت کمبود پیش آمده است. هر تقاضایی که در این مدت به انبار برسد قابل پرداخت نبوده و به عنوان کمبود در نظر گرفته میشود. چنانچه قرار باشد اینگونه تقاضاها بعدا وقتی مجددا کالایی به انبار رسید، اجابت شود، آنها را پستحویل یا تعویق تقاضا مینامند. در حالت دیگر اینگونه تقاضاها از دست میروند. بدین معنی که یا متقاضی نیازش را از جای دیگر برطرف میکند یا کالای دیگری بهجای کالای تقاضا شده انتخاب میکند. موقعیکه سفارش تهیه کالا برای ورود به انبار انجام شود ممکن است مدتی طول بکشد تا کالای سفارش داده شده عملا وارد انبار گردد این فاصله زمانی را مدت تاخیر یا تحویل گویند.
اداره یک سیستم انبار نیاز به داشتن یک روش تدارک کالا است. این روش باید مشخص کند که، چه موقع باید سفارش یا عمل تهیه کالا انجام شود و چه مقدار تهیه شود. بدیهی است که مقدار ورود کالا به انبار بر سطح موجودی و حجم کمبود اثر مستقیم دارد. لذا به منظور ارزیابی سیاستهای مختلف و بهکار بستن آنها لازم است مخارج اداره یک سیستم انبار را شناخت.
اقلام اصلی مخارج در سیستمهای انبار عبارتند از:
مخارج تدارک کالا
نگهداری کالا
کمبودها
مخارج اداره سیستم.
مخارج تدارک شامل دو بخش است: یک بخش مخارجی که مستقل از حجم کالای تدارک دیده شده میباشد، این مخارج ممکن است از قبیل پردازش و انجام مقدمات سفارش، ترخیص، حسابداری و غیره باشد. بخش دیگر شامل مخارج مربوط به حجم کالای تدارک دیده شده همانند بهای کالا، مخارج حملونقل و غیره میباشد. گاهی به بخش اول مخارج تدارک کالا (یا مخارج ثابت تدارک) و به بخش دوم مخارج متغیر سفارش گفته میشود. مخارج نگهداری کالا در انبار شامل مالیاتها، صدمات، فسادها و مخارج فضای انبار (مانند سیستمهای تهویه، نگهبان و غیره) و مخارج حاصل از رکود سرمایه در انبار میباشد. زمانی که سیستم موقتا فاقد موجودی بوده و تقاضایی برسد، زیان حاصل، متناسب با سرنوشت تقاضا، متفاوت خواهد بود. در حالتیکه تحویل کالا تا ورود محموله بعدی به تاخیر بیافتد، مخارج ممکن است شامل حمل یا جابجایی ویژه، متوقف شدن بسیاری فرایندهای تولیدی دیگر که به این کالا وابستهاند و حتی صدمات سنگین و حیاتی (مانند کمبود مهمات در سیستمهای نظامی یا کمبود دارو در سیستمهای پزشکی) باشد و در حالتیکه کالای دیگری جایگزین کالای مورد تقاضا شود، اگر کالای جایگزین از کیفیت پایینتری برخوردار باشد باعث عدمرضایت و کاهش اطمینان متقاضی خواهد شد و چنانچه از کیفیت بالاتر و در نتیجه بهای بیشتری برخوردار باشد مسلما برای سیستم زیان آور است و در حالتیکه متقاضی درخواست خود را لغو کند، زیان حاصل برابر سودی است که از دست میرود. لذا فرض میکنیم به ازای هر یک واحد کالای کمبود، زیان ثابتی برابر π ریال وارد میگردد.
1-6 مدلسازی سیستمهای تصادفی تکدورهای
در سیستمهای تکدورهای، کالا (کالاها) برای برآورد تقاضا در یک دوره تدارک دیده میشوند و کالایی که در انتهای دورهی برنامهریزی باقی میماند، در این دوره دیگر مصرف نداشته و لذا یا باید با هزینهای برای دوره بعد نگهداری شود یا بهدلیل هزینهی نگهداری یا فاسد شدن یا تکمیل نیاز متقاضیان و غیره ازبین برده شوند. بدین لحاظ در اینگونه سیستمها برنامهریزی فقط شامل یکدوره خواهد گردید. خصوصیت دیگری که در این سیستمها وجود دارد ایناست که بهدلیل کوتاهی دوره یا طولانی بودن زمان دریافت مواد یا قطعات اولیه یا زمان تولید، تدارک مواد یا قطعات اولیه در طول دوره میسر نبوده یا مفید نمیباشد. لذا هر اندازه که لازم است باید قبل از شروع دوره، دریافت یا سفارش شده باشد.
حجم تقاضا در طول دوره که با x نمایش داده میشود تصادفی و دارای تابع احتمالfx است.xij را سایز سفارش محصول j اختصاص یافته به تامینکننده i مینامیم. چنانچه سطح انبار در ابتدای دوره، بعد از تدارک کالا را باjixij نشان دهیم، آنگاه مسئله بهصورت یافتن مقداری از xijکه هزینه کلی سیستم را بهحداقل برساند، در میآید.
با توجه به اینکه افق کار سیستم تنها شامل یک دوره بوده و در صورت کمبود، تقاضای وارده لغو میگردد، فرض میکنیم مخارج کمبود، π واحد برای هر واحد کالای کمبود باشد. کالاهایی که در انتهای دوره در انبار باقی میمانند، بسته به نوع آنها و خصوصیات سیستم، یا باید با صرف هزینهای از انبار خارج گردند یا با بهای کمتری به فروش رسانیده شوند.
در مورد مخارج نگهداری در این سیستمها دو حالت را میتوان در نظر گرفت. حالت اول ایناست که در صورت کوتاه بودن طول دوره، این مخارج تنها شامل کالاهایی که در انتهای دوره باقی ماندهاند، باشد. در حالت دوم مخارج نگهداری طبق روش معمول تاکنون به زمان نگهداری آنها نیز بستگی داشته باشد. در اینجا حالت اول را بکار برده و سرجمع مخارج نگهداری و تخلیه کالا از انبار و هر مقدار سودی که از فروش یا مصرف کالای مازاد حاصل میشود باh نشان میدهیم در واقع h مجموع هزینههای نگهداری و خارج ساختن کالا از انبار منهای بهای کسب شده از فروش آنها در صورت وجود است، لذا ممکن است h (هزینه نگهداری) صفر باشد.
1-7 مدل مسئله تخصیص سهم به تامینکنندهدر این پایاننامه بهکمک نمادها و اهداف ذکر شده برگرفته از منبع [21] ، یک مدل چندهدفه فرض میکنیم که در آن هزینههای خرید، واحدهای مرجوع شده و تاخیر در تحویل واحدها مینیمم شود، درحالیکه نمره کل بهدست آمده از فرایند ارزیابی تامینکننده کالا به حداکثر برسد.
1-7-1 نشانهها و نمادهاi: فهرست تامین کنندگان
j: فهرست محصولات
Pij: قیمت محصول jارائه شده توسط تامینکننده i که به مقدار سفارش بستگی دارد
Wi : نمره ارزیابی تامینکننده i که توسط کمپانی خریدار ارائه میشود
qij: درصد اقلام مرجوع شده که جنس j توسط تامینکننده i مرجوع شده
tij : درصد اقلام دیر تحویل شده از محصول j توسط تامینکننده i
Qj: ماکزیمال درصد قابل قبول از اقلام مرجوع شده از محصول j
Tj: ماکزیمال درصد قابل قبول از اقلامی که دیر تحویل میشوند از محصول j
t: افق (دوره) برنامهریزی
Dj: متغیر تصادفی تقاضا از محصول j درافق برنامهریزی
f (Dj): تابع توزیع احتمال Djhj : هزینه نگهداری به ازای هر واحد از محصول j که در انتهای افق برنامهریزی باقی میماند
πj : هزینه جریمه به ازای هر واحد تقاضای از دست رفته از محصول j
λj : نرخ تقاضای محصول j
xijmin : مینیمال مقدار از محصول j که باید به تامینکننده i ارائه شود
xijmax : ماکزیمال مقدار از محصول j که باید به تامینکننده i ارائه شود
xij : تعداد سفارش محصول j اختصاص یافته به تامینکننده i
1-7-2 مدل پیشنهادی مسئلهبا توجه به مطالبی که در ارتباط با سیستمهای مختلف و معیارهای تصمیم در آنها ارائه شد، مدل پیشنهادی ما چهار تابع هدف متفاوت دارد:
بهحداقل رساندن هزینه عملیاتی کل شامل هزینههای خرید، نگهداری در انبار و کمبودکالا.
بهحداقل رساندن کل واحدهای مرجوع شده.
بهحداقل رساندن کل واحدهایی که با تاخیر تحویل داده میشوند.
حداکثر کردن نمرات ارزیابی کل.
توابع هدف بیان شده میتواند بهجای روابط (1-1) تا (1-4) قرار گیرد.
MinZ1=ijPijxij +jhjDj=0ixij(ixij-Dj)f Dj+jπjDj=iXij∞(Dj-ixij) f(Dj) (1-1)
Min Z2 = ijqijxij (2-1)
Min Z3 =jitijxij (3-1)
MaxZ4=jiWixij (4-1) subject to:
ijqijxij≤ Qjixij ∀j (5-1)
ijtijxij≤ Tjjxij ∀j (6-1)
xijmin≤xij≤xijmax ∀j,i (7-1)
تابع هدف (1-1)
معادله (1-1) شامل سه قسمت است. قسمت اولijpijxij اشاره دارد به هزینه خرید کل، که مجموع قیمت هر محصول، ضربدر اندازه سفارش از هر محصول تخصیص داده شده به هر تامین کننده میباشد. قسمت دوم hjDj=0ixij(ixij-Dj)f Dj اشاره دارد به هزینهی کل نگهداری هر محصول j که در آن hj هزینه نگهداری هر واحد کالا وDj=0ixij(ixij-Dj)f Dj باقیماندهی مورد انتظار در انتهای افق برنامهریزی است که تا زمانیکه ixij ≤ Dj ، غیرصفر است (Dj متغیر تصادفی تقاضای محصول j درافق برنامه ریزی است). قسمت سوم πjDj=ixij∞(Dj-ixij) f (Dj) به هزینه کل کمبود کالا اشاره دارد، که πj هزینهی کمبود هر واحد کالا وDj=iXij∞(Dj-ixij) مقدار کالایی است که با کمبود مواجه شده است.
متغیر تصادفی تقاضای محصول j دارای توزیع پواسون در نظر گرفته میشود. لذا فرض بر آن است که تقاضای محصولات مختلف مستقل است. با توجه به نمادهای فوق f (Dj) میتواند توسط رابطه (1-8) بهدست آید
f (Dj) = e-λjt (λjt)DjDj! . (8-1)
رابطه بین قیمت هر محصول پیشنهاد شده توسط هر تامینکننده، pij و مقدار سفارش مربوط به آن، xij را بهصورت رابطه (1-9)، خطی فرض میکنیم که پارامترهای aij و bij نشاندهنده عرض از مبدا و شیب منحنی قیمت- مقدار میباشد. (مانند شکل 1-1):
pij=aij-bijxij . (9-1)
208520716198400
شکل 1-1: منحنی قیمت-مقدار
تابع هدف (1-2)
شامل فرایندهایی است که درگیر بازگشت یا دریافت محصولات مرجوع شده به هر دلیل می باشند. فرایند مذکور میتواند قابل تعمیم به فرایندهای پشتیبانی از مشتریان پس از تحویل نیز باشد. بهصورت جزئیتر فرایند برگشت شامل موارد بازگرداندن مواد اولیه (به تامین کننده) و دریافت رسید محصول برگشتی (از مشتری) شامل کالای معیوب، مازاد و منقضی میباشد.
محدودیتها
محدودیت (1-5) تضمین میکند که تعداد کل واحدهای مرجوع شده از هر محصول کمتر از حداکثر سطح مجاز است. محدودیت (1-6 ) نشاندهنده آناست که تعداد کل اقلام دیرتحویلشده از هر محصول پایینتر از حداکثر سطح مجاز متناظر است. محدودیت (1-7) تضمین میکند که مقدار سفارش محصول j اختصاص یافته به تامینکننده i بین مقدار مینیمم و ماکزیمم متناظر قرار میگیرد.

1-7-3 روش حل مدل پیشنهادیبرای حل این مساله تصمیمگیری چند هدفه از روش متریک Lp، جواب ایدهآل مدل را بهدست آورده (جواب ایدهآل با توجه به هر تابع هدف از مدل اصلی با توجه به محدودیتهای (1-5) تا (1-7) بهدست میآید) و سپس با ترکیب آنها به یک تابع هدف که در (1-10) آمده است، سعی میشود نزدیکترین نقطه از فضای جواب به نقطهی ایدهآل یافت شود. توابع متفاوتی برای اندازهگیری فاصله در روش Lp تعریف میشود. ما از تعریف زیر استفاده میکنیم.
Lp=j=1kbjfjx-fjxj*fjxj*p1pکه برای p=1 و k=4 رابطهی (1-10) بهدست میآید
z =b1z1-z1*z1* +b2z2-z2*z2* +b3z3-z3*z3* +b4z4*-z4z4*.(10-1)
در معادله (1-10)، b1 تا b4 وزنهای مهمی هستند که با توجه به اهداف تصمیمگیرنده انتخاب میشوند. با توجه به غیرخطی بودن z1 ، z نیز غیرخطی و شامل متغیرهای صحیح است. بنابراین یک مساله برنامهریزی صحیح غیرخطی NIP خواهیم داشت، که با روشهای متاهیوریستیک GA (الگوریتم ژنتیک) و SA (شبیه سازی گرم وسپس سرد کردن) آنرا حل میکنیم.

فصل دوماستفاده از الگوریتم ژنتیک و الگوریتم شبیهسازی تبرید برای حل مدل پیشنهادی

متاهیوریستیکمحاسبه جواب بهینه برای اکثر مسائل بهینهسازی که در خیلی از زمینههای کاربردی و عملی مشاهده میگردند،کاری دشوار و سخت است. درعمل، معمولا به جوابهای “خوب” که از الگوریتمهای هیوریستیک یا متاهیوریستیک (فراابتکاری) بهدست میآید، اکتفا میگردد. روشهای فراابتکاری جوابهای “قابل قبول” در زمان معقول را برای مسائل پیچیده و سخت در زمینههای مهندسی و علوم ارائه مینمایند.
چه موقع از متاهیوریستیکها استفاده میشود؟
پیچیدگی یک مساله، زمان حل، ساختار دادههای ورودی و اندازه مساله شاخصهایی برای بررسی سختی یک مساله بهحساب میآید. استفاده از متاهیوریستیکها برای حل مسائل ساده، کاری بیهوده است. اگر یک مساله قابل تجزیه به مسائل کلاسیک یا مسالهای که حل شده است، باشد، میتوان با مراجعه به پیشینه تحقیق، الگوریتم مناسبی برای آن پیدا کرد. دسته ای از مسائلی که متا هیوریستیکها برای حل آن مناسب میباشند، بهصورت زیر طبقهبندی میشود:
یک مساله ساده (طبقه p) با ابعاد خیلی بزرگ. در این مورد، الگوریتمهای چندجمله ای دقیق برای حل مساله وجود دارند، ولی بهدلیل ابعاد بزرگ، خیلی پر هزینه می باشند.
برای حل برخی مسائل از ردهی انپی-سخت استفاده میشوند.
قادر به بهینه سازی مسائل با توابع هدف یا محدودیتهای زمانبر میباشند.
2-1 الگوریتم ژنتیک (GA)استفاده از GA بهعنوان یک عضو از خانوادهی الگوریتمهای تکاملی یک راهحل مسائل NIP است که بیشتر اوقات با یک رشته اعداد دودویی یا حقیقی به نام کروموزم نشان داده میشود. هرکروموزم دارای یک مقدار تناسب است که معمولا به مقدار تابع هدف جواب مربوط است. در ابتدا در این الگوریتم یک جمعیت از جواب بهطور تصادفی تولید میشود، پس از آن برای تولید جوابهای جدید بهنام فرزندان تعدادی جواب با توجه به اعمال قانون تولید مثل انتخاب میشوند. جفتگیری از والدین با استفاده از اپراتورهایGA بهنام تقاطع و جهش انجام میشود تا زمانیکه قانون توقف صدق کند (برای مثال گذشت تعداد معینی از تکرارها).
2-1-1 مزایای الگوریتم ژنتیکذاتا موازی است، یعنی جمعیتی از نقاط بهجای یک نقطه مورد جستجو قرارمیگیرد.
با متغیرهای پیوسته و گسسته کار میکند.
نیاز به محاسبه مشتق تابع ندارد چون برای پیدا کردن جهت جستجو انتخاب تصادفی انجام میدهد.
قادر به بهینه سازی مسائل با متغیرهای زیاد است.
با متغیرهای کدشده کار میکند وکدبندی سرعت همگرایی الگوریتم را افزایش میدهد.
این الگوریتم از قوانین انتقال احتمالی بهجای قوانین انتقال قطعی استفاده میکند بدین معنا که حرکت آن در هر نقطه از الگوریتم کاملا احتمالی بوده و براساس قطعیت صورت نمیگیرد. این امر از مزایای مهم این روش بوده و از افتادن در کمینه محلی جلوگیری میکند. البته میزان احتمال بهگونهای است که احتمال حرکت به سوی هدف مساله بیشتر از احتمال حرکت به سمت مخالف جواب میباشد.
برای حل برخی مسائل از ردهی انپی-سخت نیز استفاده میشود.
قبل از دادن یک طرح کلی پیشنهاد اکتشافی مبتنی بر GA برخی از نمادهای اضافی را معرفی میکنیم.
ppsz: سایز جمعیت جواب که در طول اجرای الگوریتم ثابت است.
maxit: تعداد تکرار از پیش تعیین شده.
Pc: نرخ تقاطع (باکدام احتمال یک کروموزم ازهر نسل برای انجام تقاطع انتخاب شده است).
Pm: نرخ جهش (باکدام احتمال یک بیت از یک رشته جواب (یا یک ژن ازیک کروموزم) به منظور جهش انتخاب شده است).
ftfn: مقدار تابع تناسب که فرض شده است با مقدار تابع هدف برابر باشد.
2-1-2 طرح کلی از GA پیشنهادی
مرحله 1: مقداردهی اولیه ppszو maxit و Pc و Pmو ftfn
مرحله 2: تولید تصادفی جمعیت اولیه با توجه به ارزش ppsz
مرحله 3: تکرار تا زمانیکه maxit
مرحله 3-1: استفاده ازعملگر تولید مثل، انتخاب مجموعهای از جوابهای واجد شرایط با استفاده از قوانین چرخرولت و ساخت جمعیت جدید.
مرحله3-2 : انتخاب کروموزمهای والدین از جمعیت جدید بااحتمالPc
مرحله3-3: تقاطع (پیوند)
الف: شکل دادن جفتهای والدین، در میان کروموزمهای والدین
ب : بهکاربردن عملگر تقاطع تکنقطه ای برای تولید کروموزمهای فرزند از دو کروموزم والدین اولیه
پ: جایگزینی هر کروموزم والدین اولیه در جمعیت با کروموزمهای فرزند
مرحله 3-4 : بهکاربردن عملگر جهش در جمعیت با احتمال Pm
مرحله 3-5: محاسبه ftfn برای هر کروموزم و ذخیره بهترین مقدار در bv(best value) ، اگر از قبلی بهتر باشد.
مرحله 4: چاپ bv
در شکل (2-1) روند کلی الگوریتم ژنتیک نمایش دادهشده است.

شکل 2-1: روند کلی الگوریتم ژنتیکدر ادامه گامبهگام با این روند آشنا میشویم.
2-1-2-1 تعیین تابع تناسب
یکی از مزایای روش الگوریتم ژنتیک ایناست که فقط با مقدار تابع سرو کار دارد و نیازی به دانستن رابطه بین متغیرها و تابع نیست لذا برای انتخاب تابع نیازی به دانستن معادله دقیق آن نداریم و فقط اگر روشی بیابیم که بهوسیله وارد کردن متغیرهای مساله مقدار عددی تابع را بتوانیم پیدا کنیم کفایت میکند.
مثلا اگر بتوانیم بهوسیله روشی از روشهای ترسیمی در مورد مسالهای خاص به ازای متغیرهای مختلف مقدار تابع را پیدا کنیم یا اینکه اگر نرم افزاری برای تحلیل یک مساله مهندسی وجود دارد که متغیرها را از ما میگیرد و جواب را به ما میدهد میتوانیم بدون دانستن اتفاقاتی که در طی آن به جواب میرسیم، فقط با دانستن مقدار آن به ازای متغیرهای ورودی مقدار بهین تابع را بهوسیله الگوریتم ژنتیک بهدست آوریم.
اگر تابع هدف ما دارای قیود طراحی بود که معمولا هم چنین است میتوانیم به وسیله تابع جریمه، مجموعه قیود مساوی و نامساوی را به یک رابطه تبدیل کنیم و به بهینه کردن رابطه مورد نظر بپردازیم. برای مثال اگر برای مسالهای سه قید نامساوی و یک قید مساوی مانند زیر داشته باشیم:
16×12+16×12≤1×1≥0x2≥05×1+3×2=8میتوان آنرا به صورت استاندارد زیر نوشت :
g1x=16×12+16×12-1≤0g2x=-x1≤0g3x=-x2≤0g4x=5×1+3×2-8=0بردار V را بهصورت زیر تعریف میکنیم:
V= max [0,g1x, g2x, g3x, abs(g4x)]
و تابع جریمه را بهصورت زیر تعریف میکنیم:
φ=f0+RVکه در آن φ تابع هدف نامقید بوده و R ضریب جریمه است که انتخاب آن به عهده طراح میباشد و بردار V ماکزیمم نقض قید توسط متغیرها میباشد و از این پس تابع φکه تابع پنالتی ما میباشد به عنوان تابع هزینه بهینه میگردد.
2-1-2-2 تعیین طول کروموزوم
کروموزوم یک رشته از 0 و 1 است که مقدار n متغیر تابع هدف ما را دربردارد. مثلا اگر طول هر متغیر را α بیت در نظر بگیریم طول کل کروموزوم برابر است با: L=n*α (به هر بیت از کروموزوم یک ژن گویند).
میتوان برای تعیین α از رابطه زیر استفاده کرد: α=[logb-a*10m+1] که m دقت متغیرها بر حسب تعداد رقم اعشار و a حد پایین وb حد بالای متغیرها در مبنای 10 میباشد.
در جاهایی که لازم است برای اعداد منفی باید یک بیت به علامت آنها اختصاص داد و در مورد اعداد اعشاری باید ابتدا آنها را با ضرب در یک عدد به عدد صحیح تبدیل کرده و سپس به باینری تبدیل کرد.
2-1-2-3 تولید جمعیت اولیه
پس از تعین طول کروموزوم باید آنرا به طور اتفاقی از 0 و 1 پرکنیم. اینکار بهوسیله دستور زیر انجام میشود:
L= round (rand)
با توجه به اینکه تعداد ترکیبهای جایگیری 0 و 1 برای کروموزوم به طول L برابر است با لذا بهتر است تعداد کروموزومهای یک جمعیت را، از تعداد ترکیبهای نشستن صفر و یکها در یک کروموزوم بیشتر نگیریم، چرا که در بعضی از کروموزومها به ناچار تکرار میگردند.
مقدار بهینه تعداد کروموزومها در یک جمعیت بهطور تقریبی از رابطه npop=1.65*20.21 L بهدست میآید که در آن L، طول رشته است.
فرض کنید برای یک تابع دومتغیره5 کروموزوم با تعداد 10ژن در هرکدام انتخاب کردهایم. مانند جدول (2-1)

جدول 2-1: تشکیل کروموزمx2x1کروموزم ش 1 0 0 1 1 1 0 0 1 0 1
ادامه جدول 2-1: تشکیل کروموزم
x2x1کروموزم ش2 0 1 1 1 1 0 0 1 1 1
کروموزم ش3 0 0 1 0 1 0 0 1 1 0
کروموزم ش4 1 1 0 1 0 1 1 0 0 0
کروموزم ش5 0 1 0 1 0 1 1 0 1 0
در جدول (2-1)، 5 بیت اول هر کروموزوم، مربوط به مقدار باینری x1 و 5 بیت دوم هر کروموزوم مربوط به مقدار باینریx2 میباشد.
2-2-2-4 تبدیل کروموزمها به اعدادی در بازهی دامنهی همان متغیرهااگر محدوده متغیرx1 برابر است با: ≤ b x1 ≥ a باید 0 و 1 های کروموزوم را به اعدادی در بازهی مورد نظر تبدیل کنیم. فرض کنید یک تکه ژنی از کروموزومی به طول L را که متعلق بهx1 است میخواهیم به بازه a≤x1≤b تبدیل کنیم. اگر ∝=5. کوچکترین عددی که با 5 ژن در مبنای 2 میتوان ساخت بهصورت زیر است:
0 0 0 0 0

کوچکترین عدد از بردن یک تکه کروموزوم ژنی به مبنای 10 برابر است با:
u=0*20+0*21+0*22+…+0*2∝-1=01 1 1 1 1
بزرگترین عددی که در 5 ژن از یک کروموزوم میتوان داشت برابر است با:
و با بردن بزرگترین کروموزوم ∝ژنی به مبنای 10 داریم:
u=1*20+1*21+1*22+…+1*2∝-1=2∝-1تمامی جایگشتهای 0 و 1 در یک بایت ∝ بیتی میتوانند اعدادی بین 0 تا 2∝-1 در مبنای 10 تولید کند. در حالیکه مجموعه x1 ما اعدادی در بازه a تا b میخواهد. تبدیل این دو مجموعه بهوسیله نگاشت انجام میشود. نگاشت خطی که بازهها را بههم تبدیل می کند. (u یک عدد در مبنای 10 است).
0,2∝-1r=c1+c2ua,bu=0 , r=a →c1=au=2l-1 , r=b →c2=b-a2∝-1⇒r=a+b-a2∝-1*uبههمین ترتیب میتوانیم برای x2با دامنه مختص به خودش نگاشتی بنویسیم و اعداد باینری هر متغیر را به مقداری در مبنای 10 در بازه مجاز همان متغیر تبدیل کنیم.
جدول2-2: مثالی از تبدیل کد گذاریمتغیر x1 متغیر x2
کروموزم ش 1 0 1 1 0 0 1 1 1 0 1
مقداردرمبنای 10 6 23
2-1-2-5 بهدست آوردن مقدار تابع تناسب
مقدار متغیرها را در تابع هدف قرار داده و مقدار تابع را به ازای هر بردار x=[x1, x2,…, xn] بهدست میآوریم بدین ترتیب برای مجموعه 5 کروموزومی و تابع هدف زیر داریم:
fx=x12+x22+3x1x2جدول2-3: محاسبه تابع بهینهکروموزم ها متغیر x1به صورت باینری متغیر x2 به صورت باینری x1x2f(x)کروموزمش1 0 0 1 1 1 0 0 1 0 1 28 20 2864
کروموزم ش2 0 1 1 1 1 0 0 1 1 1 30 28 4204
کروموزم ش 3 1 0 1 0 1 0 0 1 1 0 21 12 1341
کروموزم ش 4 1 1 0 1 0 1 1 0 0 0 11 3 229
کروموزم ش 5 0 1 0 1 0 1 1 0 1 1 10 27 1639
2-1-2-6 محاسبه درصد برازندگی
درصد برازندگی هر کروموزوم را حساب میکنیم مثلا برای یک تابع دو متغیره درصد برازندگی برابر است با:
100* (جمع تمام برازندگیها / مقدار تابع به ازای )
که برای مجموعه 6 کروموزمی بالا و fx=x12+x22+3x1x2 به صورت جدول (2-4) درمیآید:
جدول2-4: محاسبه درصد برازندگیکروموزم ها متغیر x1 به صورت باینری متغیر x2به صورت باینری f(x)درصد برازندگی
کروموزم ش 1 0 0 1 1 1 0 0 1 0 1 2864 28%
کروموزم ش 2 0 1 1 1 1 0 0 1 1 1 4204 1/41%
ادامه جدول 2-4
کروموزم ها متغیر x1 به صورت باینری متغیر x2به صورت باینری f(x)درصد برازندگی
کروموزم ش 3 1 0 1 0 1 0 0 1 1 0 1341 1/13%
کروموزم ش 4 1 1 0 1 0 1 1 0 0 0 229 2/2%
کروموزم ش 5 0 1 0 1 0 1 1 0 1 1 1639 16%
جمع: 10227 100%

2-1-2-7 تعیین تعداد کروموزوم شرکت کننده در عمل پیوند
تا اینجا، جمعیت اولیه تولید و درصد برازندگی هر کروموزوم محاسبه گردید. حال باید تعدادی از این کروموزومها در عمل پیوند شرکت کنند برای تعیین تعداد کروموزومها از فرمول زیر استفاده میکنیم:
Nc=2*round(p0*cp2)که در آن p0، تعداد جمعیت اولیه، cp، ضریب پیوند که معمولا حدود 0.6 میباشد وNc تعداد کروموزومهایی از جمعیت اولیه است که در عمل پیوند شرکت میکنند.
2-1-2-8 انتخاب کروموزومهایی که در عمل پیوند شرکت میکنند
برای اینکه نسل بعدی از نسل قبلی بهتر باشد باید کروموزومهایی با درصد برازندگی بیشتر، شانس بیشتری برای شرکت در عمل پیوند داشته باشند. لذا برای تعیین اینکه چه کروموزومهایی در عمل پیوند شرکت میکنند مکانیزمی به نام چرخرولت انتخاب میکنیم که متناسب با درصد برازندگی هر کروموزوم، آن را در عمل پیوند شرکت میدهد. این مکانیزم به اینصورت است که درصد برازندگی هر کروموزوم را روی دایرهای به صورت قطاعی مشخص میکند. در مثال ما که 5 کروموزوم داریم باید 5 قطاع به اندازههای مختلف داشته باشیم.
جدول 2-5: تشکیل چرخ رولت
کروموزم ها درصدبرازندگی
کروموزم ش1 28%
کروموزم ش2 1/41%
کروموزم ش3 1/13%
کروموزم ش4 2/2%
کروموزم ش5 16%
-104140279400

حال فرض کنید چرخ را به گردش در آورده و نقطهای را به عنوان شاخص در نظر میگیریم. پس از توقف چرخ، قطاعی که در مقابل شاخص قرار گرفت نشاندهنده کروموزومی است که باید در عمل پیوند شرکت کند. این کار را Nc بار انجام میدهیم تا به تعداد کافی کروموزوم برای پیوند بهدست آوریم. ملاحظه میکنیم که در این مکانیزم کروموزومهای با درصد برازندگی بالاتر شانس بیشتری برای انتخاب شدن دارند . که در شکل 2-2 نشان داده شدهاست.
30346654953000-11220454953000
↑مربوط به کروموزم بادرصد برازندگی 41.1%
شکل 2-2: نمونه ای از انتخاب در چرخ رولت2-1-2-8-الف: انتخاب به روش چرخ رولت
در این روش هر رشته، قطاعی از چرخرولت با شعاع 2π*fiftot از مرکز چرخ را به خود اختصاص میدهد.
انتخاب چرخرولت، خطای نمونه برداری زیادی تولید میکند. از اینجهت که تعداد نهایی فرزندان تخصیص داده شده به یک رشته با میزان مورد نظر خیلی تفاوت دارد. تعداد فرزندان زمانی به میزان مورد نظر میرسد که اندازه جمعیت خیلی زیاد باشد. در مسائل کاربردی از چرخ استفاده نمیشود بلکه مقدار fifi را به هر رشته تخصیص میدهند و با تولید یک عدد تصادفی در بازه (0,fi) رشته را انتخاب میکنند.
2-1-2-9 تقاطع(پیوند):
عمل ترکیب دو کروموزوم (والدین) و بهدست آوردن دو کروموزوم جدید (فرزندان) را پیوند مینامند. برای انجام عمل پیوند روی دو کروموزوم L ژنی ابتدا باید نقطه پیوند را مشخص کنیم. این کار با فراخوانی عددی تصادفی بین 1 و L-1 صورت میپذیرد.
round ((L*rand) +1)
سپس ژنهای دو کروموزوم را از نقطه پیوند با هم عوض میکنیم. عمل پیوندی که در فوق انجام شد تقاطع تکنقطهای نام دارد. بهعنوان مثال برای دو کروموزوم 10 ژنی با نقطه پیوند 4 داریم:
جدول 2-6: عمل پیوندکروموزم ش1 1 1 1 1 1 1 1 1 1 1
کروموزم ش2 0 0 0 0 0 0 0 0 0 0
287464518986500اگر پیوند را از نقطه 4 آغاز کنیم داریم
کروموزم جدید ش 1 0 0 0 0 1 1 1 1 1 1
کروموزم جدید ش2 1 1 1 1 0 0 0 0 0 0
2-1-2-10جهشجهش یکی از پدیدههای علم ژنتیک است که بهندرت در برخی از کروموزومها رخ میدهد و در طی آن فرزندان خصوصیاتی پیدا میکنند که متعلق به هیچ یک از والدین نمیباشد.
نقش جهش در الگوریتم ژنتیک بازگرداندن مواد ژنتیکی گمشده و یا پیدا نشده داخل جمعیت است. تا از همگرایی زودرس الگوریتم به جوابهای بهینه محلی جلوگیری شود. در جهش یکسری از ژنها را بهطور تصادفی برگزیده، صفرها را به یک و یکها را به صفر تبدیل میکنیم. یکی از روشهای جهش بدین صورت است که ابتدا با توجه به یک عدد کوچکتر از یک، به نام احتمال جهش، برای هر ژن از جمعیت، یک عدد تصادفی فراخوانی میشود. اگر این عدد تصادفی از احتمال جهش کوچکتر بود، در آن ژن جهش رخ میدهد.
چون عمل جهش در طبیعت بهندرت رخ میدهد لذا در الگوریتم ژنتیک هم با احتمال بسیار کم(کمتر از 0.05) عمل جهش را انجام میدهیم. همانطور که گفته شد مزیت عملگر جهش ایناست که توان دسترسی به همه فضای جستجو را به ما میدهد.
در صورتی که کاراکترها اعداد پیوسته باشند جهش را میتوان بهصورت نمو تصادفی مثبت یا منفی حول مقدار قبلی کاراکتر انجام داد. این نوع جهش را جهش خزنده مینامند.
2-1-2-11 حفظ بهترین کروموزومها
تا اینجا تولید جمعیت جدید خاتمه مییابد. اکنون برای آنکه بهترین کروموزوم نسل قبل را از دست ندهیم آنرا بهطور دستی در جای بدترین کروموزوم نسل جدید قرار میدهیم.
رهیافت دیگری برای حفظ بهترین کروموزوم ایناست که جمعیت جدید و جمعیت قبلی را با هم در آمیخته و سپس آنها را بر حسب برازندگیشان از بزرگ به کوچک طبقه بندی میکنیم. سپس ppsz (برابر با تعداد جمعیت اولیه) کروموزوم اول جمعیت که از همه برازندگیشان بیشتر است بهعنوان جمعیت جدید برمیگزینیم.
در این روش جمعیت با میانگین برازندگی بالاتری تشکیل میگردد و بهجای انتقال بهترین کروموزوم و حذف بدترین کروموزوم دستهای از بهترین کروموزومها جای دستهای از بدترین کروموزومها را میگیرند. با این عمل همگرایی به سمت عدد بهینه در اجرای الگوریتم سریعتر و زمان اجرای برنامه تا یافتن جواب مناسب کاهش مییابد.
2-1-2-12 تکرار تا زمان توقف
حال جمعیت جدیدی تولید شده است که میانگین برازندگی آن از نسل قبلی بهتر است. با این جمعیت، مجددا مراحل قبل را از گام چهارم تا یازدهم تکرار کرده و این اعمال را آنقدر انجام میدهیم تا به مقدار بهین دست پیدا کنیم.
2-2 روش شبیه سازی تبریدSA
مقایسه ساختار پیچیده پیکربندی فضای جواب مسائل بهینه سازی سخت، با بعضی از پدیدههای فیزیکی توسط کرک پاتریک و همکارانش در انجمن IBM ، منجر به ارائهی پیشنهاد یک روش جدید تکراری (تکنیک انجماد تدریجی (شبیه سازی تبرید)) که توانایی خروج از بهینه محلی را داشت، گردید. همچنین اثر مشابهی در همان زمان توسط کرنی در سال 1985 منتشر گردید. آنها از الگوریتم انجماد تدریجی (SA) برای افراز بندی گرافها استفاده نمودند. SA بهدلیل سادگی و همچنین کارایی بالا در حل مسائل بهینه سازی ترکیبی، جایگاه ویژهای در بین تکنیکهای جستجو و هیوریستیکها در دهه 1980 بهدست آورد. این تکنیک بعدها به حوزه مسائل بهینهسازی پیوسته نیز توسعه داده شد.
2-2-1: مقایسه با پدیدههای فیزیکیدر طبیعت فرایند تغییر شکل منظم را بهصورت خودبهخود، زمانیکه دمای یک سیستم بهتدریج کاهش مییابد، میتوان دید. آرایش مولکولی یک جسم داغ که در ابتدا ساختاری غیر منظم داشته و دارای فاصله زیادی از همدیگر است، زمانیکه دمای آن بهآرامی کاهش پیدا میکند، به یک ساختار منظم و نزدیک به هم تغییر شکل پیدا میکند.
به دو صورت میتوان جسم را سرد کرد. در حالت اول، جسم بهسرعت سرد میگردد که در اینحالت میزان آنتروپی (یا فاصله بین مولکولها) از همدیگر کاهش مییابد ولی بهمقدار حداقلی، نخواهد رسید. در حالت دوم، جسم بهآرامی سرد میشود و مولکولها این فرصت را پیدا میکنند که کلیه فضاهای خالی را پر کرده و آرایش منظمتری را ایجاد نمایند. در این حالت میزان آنتروپی به حداقل خود خواهد رسید.
بهمنظور تولید یک ساختار کریستالی، ابتدا جسم به اندازه کافی دما داده میشود و سپس آن جسم به آرامی سرد میگردد. در طول فرایند کاهش دما، پس از هر مرحله کاهش، مدتی جسم در آن دما باقی میماند. این مرحله به آرامی ادامه پیدا میکند تا جسم به پایینترین دما رسانده شود که منجر به ایجاد یک حالت کریستالی در جسم خواهد شد. در صورتیکه در مرحلهای کاهش دما بهتندی، صورت گیرد، حالت غیر بلوری ایجاد خواهد شد.
الگوریتم شبیه سازی تبرید که انجماد تدریجی نیز نامیده میشود، از پدیده انجماد فیزیکی فوق الگو گرفته شده است. در این الگوریتم شبیه به پدیده آنیلینگ، از یک پارامتر دما برای کنترل الگوریتم در طول بهبود جواب مساله استفاده میگردد. جدول زیر مقایسهای بین یک سیستم فیزیکی با مسائل و الگوریتم های بهینه سازی را نمایش میدهد.
جدول 2-7: مقایسه بین یک مساله و الگوریتم بهینه سازی با یک سیستم فیزیکی
سیستم فیزیکی مساله و الگوریتم بهینه سازی
وضعیت سیستم جواب
موقعیتهای مولکولی متغیرهای تصمیم
انرژی تابع هدف
وضعیت پایدار جواب بهینه سراسری
وضعیت نیمه پایدار بهینه محلی
سرد کردن سریع جستجوی محلی
دما پارامتر کنترل
آنیلینگ با دقت شبیه سازی تبرید
2-2-2- روش کار الگوریتم شبیه سازی تبریدفرض کنید فضای جواب s یک مجموعه متناهی از تمام جوابها و f مقدار تابع هدف، برای هر یک از عناصر باشد. هدف، پیدا کردن یک جواب یا حالتی مانند iєs است بهطوریکه f(i) روی s کمینه باشد. تبرید شبیه سازی شده، شکلی از روشهای سنتی کاهشی برای بهینه سازی محلی یا جستجوی همسایگی است. الگوریتم کاهش با یک جواب اولیه شروع میکند و از بین همسایگیهای این جواب، آن را که جواب حاضر را بهبود دهد انتخاب میکند و این همسایگی جدید بهجای جواب اولیه قرار میگیرد. این فرآیند ادامه مییابد تا اینکه دیگر هیچ یک از همسایگیهای جواب جاری نتواند مقدار تابع هدف را بهبود بخشد. در این حالت جواب جاری یک بهینه محلی است.
یکی از راههایی که میتوان برای بهبود این روش استفاده کرد این است که الگوریتم را چندین  بار با جوابهای اولیه مختلف اجرا کنیم و در نهایت بهینه محلی را انتخاب کنیم. شبیه سازی تبرید  بهجای استفاده ازاین استراتژی، سعی میکند در یک بهینه محلی قرار نگیرد و بنابراین برای این کار، بعضی اوقات جوابهایی که مقدار تابع هدف را افزایش داده میپذیرد. قبول یا رد این جواب به دنباله ای از اعداد تصادفی وابسته به یک کنترل احتمالی بستگی دارد. بهعلاوه اجتناب از جواب بهینه محلی، به برنامه آنیلینگ (گرم کردن و سپس به تدریج سرد کردن)، انتخاب دمای اولیه، تعداد تکرارهای لازم در هر دما و مقدار کاهش دما در هر مرحله بستگی دارد که درادامه به آنها اشاره خواهد شد.
در واقع این الگوریتم بر مبنای دو قاعده از فیزیک آماری عمل میکند:
قاعده اول بر این اساس است که وقتی تعادل ترمودینامیکی به یک دمای مشخص رسید، احتمال یک سیستم فیزیکی برای داشتن یک سطح انرژی E، با فاکتور بالتزمن، e-EkB T که در آن kB  توزیع بالتزمن در دمای مربوطه می باشد، متناسب است. بر اساس این قاعده احتمال پذیرش جوابها در دماهای مختلف متفاوت بوده و متناسب با تابع معرفی شده میباشد.
قاعده دوم نحوه رسیدن به تعادل ترمودینامیکی در یک دمای مشخص را بیان میکند. بر اساس آن، در یک دمای مشخص، با استفاده از الگوریتم متروپلیس تکامل یک سیستم فیزیکی در رسیدن به تعادل ترمودینامیکی در دمای مشخص شبیه سازی میگردد. بر اساس این قاعده، برای یک جواب یا پیکرهبندی مشخص یک سری محدود از حرکت یا تغییرات ابتدایی در نظر گرفته میشود. اگر یک تغییر شکل منجر به کاهش تابع هدف یا انرژی گردد، آن تغییر شکل پذیرفته میشود و درصورتیکه این تغییر شکل منجر به افزایش تابع هدف یا انرژی به اندازه E∆ گردد، تغییر شکل با احتمال e-∆ ET پذیرفته میشود. این پذیرش از طریق تولید یک عدد تصادفی با توزیع یکنواخت در فاصله بین ۰و۱ و مقایسه آن با تابع تعریف شده انجام میگردد. در صورتی که مقدار عدد بهدست آمده کوچکتر از تابع تعریف شده باشد، تغییر شکل پذیرفته میشود. هر جواب از روی جواب پذیرفته شده قبلی خود تولید میگردد و با تکرار تولید جوابها و پذیرش آنها با استفاده از قاعده متروپلیس، یک توالی از جوابها بهوجود میآید که زنجیره مارکف را بهوجود آوردهاند. پایان یافتن این زنجیره با طول محدود و کافی را میتوان به رسیدن یک سیستم فیزیکی به تعادل ترمودینامیکی در یک دمای مشخص تشبیه کرد.
قاعده متروپلیس بهصورت زیر عمل میکند: در دمای بالا و مراحل اولیهی الگوریتم، مقدار e-E T نزدیک به یک بوده و درنتیجه، اکثر حرکتها (تغییر شکلها) پذیرفته میشود و الگوریتم، رفتاری شبیه به یک جستجوی تصادفی را خواهد داشت. در دماهای پایین و اواخر الگوریتم، مقدار e-E T به صفر نزدیک شده و اکثر جوابهای بدتر ردشده و تنها جوابهای خوب پذیرفته میشوند. شانس جابهجایی یک جواب خوب با یک جواب بدتر، خروج الگوریتم از جواب بهینهی محلی را تضمین میکند و از طرفدیگر، کاهش احتمال پذیرش جواب بدتر با کاهش دما، موجب تضمین همگرایی SA است.
معمولا الگوریتم های بهبود دهنده، که با یک جواب اولیه شروع شده و در طی مراحلی بهبود داده میشوند، ممکن است بعد از چند تکرار در نقطه بهینه محلی قرار بگیرند، که گاهی اوقات نیز از ناحیه جواب نهایی خیلی دور است. فرق الگوریتم انجمادتدریجی با الگوریتم های بهینهسازی محلی در ایناست، که در الگوریتم بهینهسازی محلی، یک جواب در همسایگی جواب قبلی ایجاد میشود، اگر تابع هدف بهواسطه جواب جدید بهترشود، جواب جدید قبول شده و در غیراینصورت جواب جدید رد میگردد. این عمل ممکن است منجر به قرارگرفتن در نقطه بهینه محلی شده و دیگر نتواند از آن خارج شود. درحالیکه در روش تبرید شبیه سازی شده، از توقف در ناحیه بهینه محلی اجتناب کرده و بهطور گذرا از آن رد میشود. این حالت با پذیرفتن احتمالی جوابهای بد انجام میشود، تا از نقطه بهینه محلی خارج شود. این احتمال برابر است با ( e-∆fT ) که T میزان درجه حرارت و ∆f میزان تغییر در تابع هدف میباشد. اگراین احتمال از یک عدد تصادفی یکنواخت بین [ 0 ,1] ، بیشتر باشد، جواب نامناسب هم پذیرفته میشود.

2-2-3 : همگرایی الگوریتم انجماد تدریجیبسیاری از محققین همگرایی الگوریتم شبیه سازی تبرید را بررسی نمودهاند و بعضی از آنها بهدنبال ارائهی یک مدل کلی برای تحلیل روشهای تصادفی در یافتن بهینه سراسری از مسائل بهینهسازی بودهاند. دستاوردهای اصلی آنها عبارتند از: در شرایط اطمینان، احتمالا الگوریتم شبیهسازی تبرید به سمت بهینه سراسری همگرا خواهد بود و بهعبارت دیگر، الگوریتم شبیه سازی تبرید، امکان رسیدن به نقطهای نزدیک به بهینه سراسری را خواهد داشت. این نتیجه، بهنوبهی خود، از اهمیت بهسزایی برخوردار بود. زیرا این نتیجه، موجب تمایز این الگوریتم نسبت به سایر الگوریتمهای مشابه که هنوز همگرایی آنها تضمین نشده بود، میگشت.
قبل از دادن یک طرح کلی پیشنهاد اکتشافی مبتنی بر SA برخی از نمادهای اضافی را معرفی میکنیم.
maxit: تعداد تکرارها تا زمان توقف الگوریتم
ilit: حداکثر تعداد تکرارها در هر دما
α: نرخ خنک کننده یا کاهش دما
–p0: دمای اولیه
ffv: مقدار تابع تناسب
2-2-4 طرح کلی از SA پیشنهادی
مرحله 1: تولید تصادفی جمعیت اولیه از جوابها با اندازه از پیش تعیین شده ومحاسبه ffv برای هریک و بهترین مقدار آنرا ffv0 مینامیم و قرار میدهیم solution=ffv0 و bv(best value)=ffv0
مرحله 2: تعیین پارامترهای اولیه
2-1: مقداردهی اولیه پارامترهای تبرید تدریجی ilit, maxit, α, –p02-2: مقداردهی شمارشگر تکرار iter=0
مرحله 3: برنامه تبرید تدریجی
3-1: مقدار دهی اولیه حلقه داخلی il=0
3-2: رسیدن به تعادل در هر دما، اجرای حلقه داخلی تا زمانیکه شرایط 3-2-5 صدق کند
3-2-1: il=il+1
3-2-2: ایجاد یک جواب مجاور که در شرایط مدل صدق کند. محاسبه ffv مربوطه و نامگذاری آن بهعنوان ffvil3-2-3: ε=ffvil-ffvil-13-2-4: اگرε≥0
جواب جدید را قبول کن و ffvil solution= و bv=ffvil درغیر اینصورت اگر (random(0,1)≤exp⁡(-ε–piter))
جواب جدید را قبول کن و ffvil solution=
در غیر اینصورت جواب جدید را ردکن و solution=ffvil-1
3-2-5: اگر (il>=ilit)
حلقه داخلی را خاتمه بده و برو به مرحله 3-3
در غیراینصورت حلقه داخلی را ادامه بده و برو به مرحله 3-2
3-3: –piter+1= –piter*α3-4: iter=iter+1
3-5: اگر iter<=maxit
برو به مرحله 3
درغیر اینصورت برو به مرحله 4
مرحله4:bv و solution را چاپ و توقف کن.
2-2-5 : اجزای الگوریتم شبیه سازی تبرید به منظور آشنایی بیشتر با الگوریتم SA مطابق آنچه در مرجع [2] آمده است، برخی نمادهای استفاده شده در این قسمت را بیان میکنیم. f(x) مقدار تابع هدف بهازای x بوده و xc یک جواب جاری در هر مرحله می باشد. V (xc) مجموعهای است که برای نشان دادن همسایههای xc بهکار میرود.p یک عدد تصادفی است که در زمان برخورد با جواب بدتر بهمنظور بررسی پذیرش یا عدم پذیرش آن جواب بهکار میرود.
در قدم اول الگوریتم یک جواب اولیه ایجاد و مقدار تابع هدف آنرا محاسبه میکند. دراین قدم جواب اولیه بهعنوان جواب جاری xcو بهترین جوابx* نیز درنظر گرفته میشود. البته این دو جواب در طول الگوریتم تغییر خواهند یافت. همچنین مقدار تابع هدف جواب اولیه بهعنوان مقدار تابع هدف جواب جاری f(xC) و بهترین جواب f(x*) نیز در نظر گرفته میشود. در این قدم دمای اولیه T0 بهعنوان دمای جاری Tcدر نظر گرفته میشود.
در قدم دوم در هر دما یک زنجیره مارکف ایجاد میگردد (زنجیره مارکف یک سیستم ریاضی است که در آن انتقال از یک حالت به حالت دیگر صورت می‌گیرد). در این مرحله جستجوی همسایگی تا زمانیکه زنجیره مارکف به انتها برسد انجام میگردد. بدین منظور برای هر جواب جاری یک جواب همسایه xc’ در همسایگی آن پیدا شده و مقدارتابع هدف آن f(xc’ ) محاسبه میگردد. درصورتیکه همسایه جدید، مقدار تابع هدف جاری را بهبود بدهد یا برابر آن باشد (f(xc’ )≤f(xC)) جواب همسایه بهعنوان جواب جاری پذیرفته میشود. (الگوریتم از یک نقطه به نقطه دیگر حرکت میکند) و جواب جدید بهعنوان جواب جاری پذیرفته میشود.(xc’→xc و ( f(xc’)→f(xc). درغیر اینصورت اگر جواب همسایه منجر به بدتر شدن تابع هدف جاری گردد ( fxc’ >fxc) همسایه، با تابع احتمال e-∆fTc ارزیابی میگردد. در این تابع مقدار اختلاف انرژی از طریق ∆f= fxc’-fxc محاسبه میگردد. برای اینمنظور مقدار تصادفیp∈U(0,1) تولید و سپس با تابع احتمال مقایسه میگردد. در صورتیکه مقدار p از تابع احتمال کمتر باشد جواب همسایه بهعنوان جواب جاری پذیرفته میشود. علاوه بر بهنگام سازی جواب جاری بهترین جواب نیز در این قدم بهنگام میگردد. بدین منظور بعداز یافتن هر جواب جدید که منجر به بهبود جواب جاری گردد آن جواب، با بهترین جواب مقایسه میگردد. اگر از بهترین جوابی که تا بهحال پیدا شده بهتر باشد(f(xc’ )≤f(x*)) جایگزین جواب بهتر میگردد. ( fxc’→fx*و xc’→x* ) این قدم ادامه می یابد تا زمانیکه زنجیره مارکف به انتها برسد یا بهعبارت دیگر تعداد مشخصی از جستجوها انجام شده باشد. معمولا برای این زنجیره یک طول معین مشخص شده و زمانیکه تعداد جستجو (شامل تمامی نقاط پذیرفته و رد شده) به طول مشخص شده برسد زنجیره پایان می یابد. در طول زنجیره دما ثابت میماند.
در قدم سوم، بعد از اتمام یک زنجیره، کاهش دما اتفاق خواهد افتاد. معمولا برای کاهش دما از یک ضریب ثابت α (1 >α>0) استفاده میگردد. رابطه کاهش دما در این حالت بصورتT * α = T تعریف میگردد.
در قدم چهارم، شرط توقف الگوریتم بررسی میگردد. در صورتیکه شرط توقف برآورده شود، الگوریتم متوقف و در غیر اینصورت به قدم دوم برمیگردد. شرط توقفهای مختلفی میتوان تعریف کرد. یک شرط توقف رایج، رسیدن دمای الگوریتم به یک دمای انتهایی ( دمای انجماد ، Tf) میباشد که بهصورت ( ≤ Tf T) تعریف میگردد.
2-2-6  انتخاب پارامترهای برنامه انجمادبرای بهکار بردن شبیهسازی تبرید جهت یک مساله خاص تعداد زیادی تصمیم باید گرفته شود. این تصمیمها را میتوان به دو گروه تقسیمبندی کرد، گروه اول تصمیمهای کلی که مرتبط با پارامترهای خود الگوریتم آنیل هستند که شامل عواملی از قبیل دمای اولیه، قاعده کاهش دما، زنجیره مارکف و قاعده توقف میباشد. گروه دوم تصمیم های مربوط به یک مساله خاص شامل انتخاب فضای جواب موجه، ساختار همسایگی و شکل تابع هزینه میباشد. هر دو گروه تصمیمها باید با دقت گرفته شوند و ثابت شده که موثر بر سرعت الگوریتم و کیفیت جوابهای بهدست آمده هستند.
2-2-6-1: دمای اولیه
تعیین دمای اولیه T0 تاثیر زیادی در انتخاب کردن و یا انتخاب نکردن جابجاییها دارد و تاکنون روش دقیقی برای آن بهوجود نیامده است و معمولا برای هر مساله با مقادیر مختلف برای آن، الگوریتم شبیهسازی تبرید را اجرا میکنند. اگر T0 (دمای اولیه) خیلی بزرگ باشد آنگاه e-∆ ET نزدیک ۱ میشود و در نتیجه هر جابهجایی که تابع هدف را بهبود ندهد، نیز پذیرفته میشود. در واقع بالا بودن بیش از حد دمای اولیه، باعث اتلاف وقت در ابتدای الگوریتم میشود، زیرا احتمال پذیرش جوابهای با سطح انرژی بالاتر زیاد میشود که الگوریتم بهطور دائم بهصورت تصادفی از یک جواب به جواب دیگر میجهد. این عمل در حالت حدی، جواب ما را شبیه به جستجو به صورت کاملاً تصادفی میکند. حال اگر T0 مقدار کوچکی داشته باشد، آنگاه انتخاب یا پذیرش جوابهای خیلی بد کاهش مییابد. در واقع پایین بودن بیش از حد دمای اولیه، باعث توقف در جوابهای محلی میشود، زیرا در ابتدای الگوریتم، اجازهی جستجو را از خود میگیریم و بهعبارت دیگر با اینکار احتمال پذیرش جواب با سطح انرژی بالا کمتر میشود و در نتیجه سرعت الگوریتم، بسیار کاهش مییابد. بنابراین برای جلوگیری از این مشکلات، دمای اولیه T0 را نسبتا بزرگ انتخاب میکنیم و بعد از هر تکرار، آن را کاهش میدهیم. همچنین پایین بودن بیش از حد دمای نهایی، باعث اتلاف وقت در انتهای الگوریتم میشود. در واقع در انتهای الگوریتم، از یک دمای خاص کمتر، دیگر جوابهای جدید پیشرفت چندانی در پایین آوردن سطح انرژی نمیکنند.
سه استراتژی مهم در هنگام تنظیم این پارامتر وجود دارد:
1-پذیرش کلیه جوابها: در این حالت مقدار دمای اولیه به اندازهای بزرگ در نظر گرفته میشود که کلیهی جوابها در طول فاز اولیهای از الگوریتم پذیرفته میشود.



قیمت: 10000 تومان

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

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

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