ساختار جواب (کروموزوم) مبین یک نقطه از فضای شدنی مساله است، بطوریکه نحوه نمایش آن درهر رویکرد فراابتکاری حایز اهمیت می باشد. ساختار جواب (کروموزوم) در الگوریتم پیشنهادی برای مدل ارائه شده از چهار بخش تشکیل شده است که به ترتیب به صورت زیر می­باشد :
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
بخش اول بیانگر تعداد تقاضای تولید شده از هر قطعه در هر دوره می­باشد که به صورت یک بردار سطری Part × ۱ بیان می­گردد و حداقل سفارش در هر دوره در آن رعایت گردیده است.
مثال :Demand = [ 116 100 200 ]
بخش دوم بیانگر قیمت هر قطعه در هر دوره می­باشد که به صورت یک بردار سطری Part × ۱ بیان می­گردد. در صورتی که تقاضای قطعه­ای برابر صفر باشد، قیمت آن صفر منظور می­ شود.
مثال :Price = [9.0417 4.6052 4.1232 ]
بخش سوم یک ماتریس دو بعدی Machine * Cell می­باشد که بعد اول آن برابر با تعداد ماشین ها و بعد دوم برابر با تعداد سلول­ها می­باشد. هر درایه این ماتریس عددی است که تعداد ماشین نوع m در سلول k را نشان می­دهد. برای مثال machine_cell(1,2) = 2نشان می­دهد که تعداد دو ماشین از نوع ۱ در سلول ۲ وجود دارد.
بخش چهارم یک ماتریس سه بعدی m × k × p می­باشد که بعد اول آن تعداد ماشین­ها ، بعد دوم تعداد عملیات هر قطعه و بعد سوم آن قطعه مورد نظر را نمایش می­دهد. هر درایه غیر صفر این ماتریس سه بعدی شماره سلولی را نشان می­دهد که عملیات مورد نظر از قطعه فعلی در آن سلول انجام می­ شود.
مثال :
این ماتریس ترتیب پردازش برای قطعه دوم را نشان می­دهد که در آن عملیات اول از قطعه ۲ روی ماشین اول(سطر اول) و در سلول اول انجام می­ شود. عملیات دوم از قطعه ۲ روی ماشین سوم(سطر سوم) و در سلول دوم انجام می­ شود و بالاخره عملیات سوم از قطعه ۲ روی ماشین دوم(سطر دوم) و در سلول اول انجام می­ شود.
ماتریس­های ذکر شده در بالا مربوط به یک دوره می­باشد. بنابراین در هر جواب (کروموزوم) T مجموعه از این ماتریس­ها وجود دارد که T تعداد دوره­ها می­باشد.

۲-۲-۸-۴: انتخاب جواب اولیه

در این مسئله جواب اولیه به صورت تصادفی تولید می­ شود. با توجه به ساختار مسئله، جواب­های بعدی در الگوریتم ارائه شده در این بخش در هر تکرار با انجام جهش روی بخش­های مختلف جواب تولید می­ شود.

۳-۲-۸-۴: انتخاب دمای اولیه

تعیین دمای اولیه یکی از مسایل اساسی در شبیه سازی تبرید می­باشد. دمای اولیه باید بگونه­ای تعیین گردد که در آن کاهش تابع انرژی محسوس بوده و از محاسبات اضافی اجتناب گردد. اگر دمای اولیه خیلی پایین باشد، شبیه­سازی تبرید خیلی سریع به جواب­های نامطلوب همگرا خواهد شد (همگرایی زودرس). از طرف دیگر اگر دما خیلی بالا باشد، شبیه­سازی تبریددچار واگرایی شده و قادر به ارضای معیارهای خروج از الگوریتم نخواهد بود. تعیین این پارامتر هم­چنان یک فرایند ابتکاری و تجربی می­باشد.
برطبق مفاهیم اولیه شبیه­سازی تبرید، احتمال پذیرش جواب های غیربهبود دهنده در تکرارهای اولیه بالا است و سپس این احتمال به تدریج کاهش می­یابد. تعیین دمای اولیه و دمای پایانی در این الگوریتم با توجه به مقادیر ورودی و مقادیر تابع هدف انجام شده است.

۴-۲-۸-۴: مکانیزم ایجاد جواب همسایه

برای پیمایش در فضای شدنی، نیاز به تولید پاسخ شدنی دیگری با تغییر پاسخ فعلی وجود دارد، که به آن جواب همسایه اطلاق می­ شود. بعد از آن باید شدنی بودن پاسخ مورد بررسی قرار گیرد. اگر پاسخ بدست آمده شدنی نباشد، آن را حذف و یا اصلاح کرده و پاسخ دیگری تولید می­ شود. در الگوریتم فعلی جهش­های نوع دوم، سوم وچهارم می­توانند جواب نشدنی تولید نمایند که در جهش­های نوع دوم و سوم قابلیت اصلاح نیز وجود دارد. جهش­های نوع دوم وسوم هر دو روی بخش سوم کروموزوم انجام می­گیرند. نحوه تولید یک جواب شدنی جدید با بهره گرفتن از جواب فعلی به صورت زیر است:
نخست یکی از دوره­ها جهت انجام جهش انتخاب می­گردد. در هر جواب شدنی پنج نوع جهش متفاوت می ­تواند انجام گیرد. این چهار نوع جهش عبارتند از:
تغییر در تعداد قطعات تولید شده : در هر دوره می­توان میزان تولید هر یک از قطعات را افزایش یا کاهش داد مشروط بر اینکه حداقل سفارش رعایت شده و جواب شدنی باشد. برای این کار ابتدا یکی از قطعات را انتخاب کرده و با توجه به حداقل میزان سفارش مورد نیاز و حداکثر ظرفیت ماشینی که قطعه مورد نظر روی آن پردازش می­ شود، بازه تغییر تولید را معین می­کنیم. واضح است که با اتخاذ روش فوق پاسخ همسایه ایجاد شده همواره شدنی خواهد بود. باید توجه داشته باشیم که با تغییر میزان تولید قیمت قطعه در دوره مورد نظر خودبه­خود تغییر می­یابد.
تغییر مکان ماشین­ها در سلول­ها: این کار به دو روش متفاوت انجام می­گیرد، بدین معنا که می­توان یک ماشین را از یک سلول به سلول دیگر منتقل نموده و یا جای دو ماشین را در دو سلول متفاوت با هم عوض نمود. در صورتی که پاسخ به دست آمده پس از اصلاحات لازم روی ماتریس پردازش شدنی نباشد، حذف شده و تلاش می­کنیم که تغییر را در یک سلول متفاوت و روی ماشین­های دیگر اعمال نماییم. جهت جلوگیری از ایجاد حلقه بی­نهایت این کار تنها با دفعات محدود انجام می­گیرد.
تغییر در تعداد ماشین­ها: در هر دوره می­توان تعداد ماشین­های پردازش­کننده را افزایش یا کاهش داد. افزایش ماشین­ها تاثیری در بهبود پاسخ ندارد و تنها برای افزایش حق انتخاب در جهش­های دیگر صورت می­گیرد. حذف یک ماشین تنها در صورتی قابل پذیرش است که پاسخ به دست آمده شدنی باشد. پس از حذف یک ماشین تلاش می­کنیم که عمل اصلاحی را انجام داده و هر عملیات انجام یافته روی آن را به ماشین­های دیگر اختصاص دهیم. در صورتی که باز هم پاسخ شدنی به دست نیاید، جواب مذکور حذف شده و عملیات حذف روی ماشین­های دیگر انجام می­گیرد.
تغییر مکان پردازش یک عملیات: آخرین نوع جهش مربوط به ماتریس­های پردازش می­باشد .برای این کار یک عملیات از یک قطعه خاص انتخاب شده و به ماشینی دیگر در همان سلول و یا روی سلول دیگر انتقال می­یابد. بدیهی است که عملیات انتقال تنها در صورتی انجام می­ شود که ماشین مقصد ظرفیت کافی داشته باشد. اگر چنین ماشینی موجود نباشد، جواب فعلی حذف شده و یک عملیات از یک قطعه دیگر را جهت انجام فرایند جهش انتخاب می­کنیم.

۵-۲-۸-۴: مکانیزم کاهش دما

در این الگوریتم جهت به هنگام سازی دما یا اصطلاحاً زمان­بندی سرمایش از قاعده کلاسیک شبیه سازی تبرید بصورت زیر استفاده شده است. پارامتر مبین نرخ کاهش دما است در بازه [۹۹/۰ ، ۸۵/۰] تعیین می­گردد.
T_r=T_r-1
اگرچه تاکنون قواعد متنوعی در ادبیات موضوع ارائه شده است ولی کارایی قاعده فوق هم­چنان مورد توجه است.

۶-۲-۸-۴: مکانیزم پذیرش جواب­های نامزد شده

یکی دیگر از مولفه­های تعیین کننده کیفیت و سرعت رسیدن به جواب تقریبا بهینه، نحوه پذیرش یا رد جواب­های جدید است. الگوریتم شبیه سازی تبرید با یک جواب شدنی اولیه آغاز شده و طی مکانیزم معینی، یک حل همسایه از فضای جواب انتخاب کرده و هزینه این جواب همسایگی با هزینه­ جواب قبلی مقایسه می­ شود.
هرگاه تابع هدف بهبود یافته باشد، حل جدید نگه داشته شده و به عنوان حل جاری منظور می­ شود، در غیر اینصورت،این همسایگی علی­رغم عدم بهبود هدف،با احتمال مشخصی پذیرفته می­ شود.
این تابع احتمال، حالت خاصی از توزیع احتمالی بولتزمن در علم ترمودینامیک آماری است که بصورت زیر تعریف می­گردد.

۷-۲-۸-۴: معیارهای توقف الگوریتم شبیه­سازی تبرید

با توجه به اینکه الگوریتم­های فوق ابتکاری هیچگونه شناختی نسبت به نقطه ی بهینه سراسری و بطور کلی درجه­ بهینه بودن جواب­ها ندارند، معیاری برای توقف آنها مورد نیاز است. برای توقف الگوریتم شبیه سازی تبرید، از دو معیار بصورت زیر استفاده شده است:
۱- حداکثر تعداد انتقالات دما یا حداکثر تعداد دفعات کاهش دما.
۲- حداکثر تعداد تکرار الگوریتم

۳-۸-۴ : اجزاء و پارامترهای الگوریتم ژنتیک

۱-۳-۸-۴: تعریف کروموزم

برای نمایش کروموزم از۵ ماتریس استفاده نموده­ایم که مقادیر این ماتریس­ها از نوع عدد صحیح هستند دو ماتریس اول (X,Y) ساختار سه بعدی دارند. هر درایه ماتریس X تخصیص عملیات پارت­ها به ماشین­ها را نشان می­دهد. برای مثال اگر =m1 داشته باشیم این عبارت بیان می­ کند که عملیات j ام قطعه i توسط ماشین m1 پردازش می­ شود.
هر درایه ماتریس Y تخصیص عملیات قطعات به سلول­ها را نشان می­دهد برای مثال اگر یعنی عملیات jام قطعه i در سلول c1 پردازش می­ شود.
بنابراین دو ماتریسX,Y تخصیص عملیات قطعات به ماشین­های داخل سلول­ها را نشان می­ دهند.
ماتریس سوم (N) تعداد ماشین­هایی که در هر دوره به سلول­ها تخصیص می­یابد را نشان می­دهد برای مثال اگر =۴ یعنی تعداد ماشین­های نوع دوم در سلول شماره ۳ برابر ۴ می­باشد. هر عضو ماتریس N با توجه به معادله زیر تعیین می­ شود.
ماتریس چهارم(K) تعداد ماشین­هایی را که در هر دوره ( موقع پیکر بندی مجدد) از سلول­ها کم و یا به آنها اضافه می­ شود را نشان می­دهد. عناصر ماتریسKبا توجه به معادله زیر تعیین می­ شود.
ماتریس پنجم(XT ماتریس تولید) مقدار تولید از هر نوع قطعه در یک دوره را نشان می­دهد. هر عضو ماتریسXTابتدا با توجه به معادله زیر تعیین می­ شود سپس با توجه به ظرفیت ماشین­ها تصحیح می­ شود.