توسعه و حل یک مدل دو هدفه جهت تکمیل توأم موجودی چند کالا با محدودیت فضای انبار

مقدمه

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

ü     تأثیرات متقابل به علت محدودیتها

ü     تأثیرات متقابل در هزینه های سفارش دهی

ü     تأثیرات متقابل در قیمتهای خرید

ü     تأثیرات متقابل در محدودیتهای تولید

در عمل مدلهای موجودی مختلفی وجود دارد که با چندین محصول در ارتباطند، هدف این مدلها، اغلب مینیمم کردن هزینه کل بوده در حالیکه تقاضا نیز برآورده شود. هزینه کل، معمولاً از دو جزء تشکیل می شود:

الف ) هزینه راه اندازی یا سفارش دهی[1]

این هزینه، برای محصولاتی که ساخته می شوند در واقع هزینه آماده سازی ماشین آلات و تجهیزات، قبل از تولید است و برای محصولاتی که به یک تأمین کننده سفارش داده می شوند شامل هزینه آماده سازی و دریافت سفارش و نیز هزینه حمل و نقل است.

ب ) هزینه نگهداری[2]

این هزینه، همان هزینه نگهداری موجودی است که شامل هزینه درگیر در موجودی، مالیات، بیمه و نظایر آن می باشد.

مهمترین مسأله در مسائل چند محصولی عبارت است از تصمیم گیری روی مقادیر بهینه محصولات مختلف در یکی از حالات زیر: (گویال [3]، 1974)

1- هنگامی که چندین کالا به یک تأمین کننده سفارش داده می شوند.

2- هنگامی که چندین محصول از تجهیزات حمل و نقل مشترک استفاده می کنند.

3- هنگامی که یک محصول بعد از تولید انبوه یا دسته ای در مقادیر مختلف بسته بندی شود.

هزینه ترتیب دادن یک سفارش از یک تأمین کننده برای تعدادی محصول متفاوت از دو جزء زیر تشکیل می شود:

الف ) یک هزینه کلی سفارش دهی [4]که از تعداد محصولات مختلف در یک سفارش مستقل است.

ب ) یک هزینه جزئی سفارش دهی[5] که به تعداد محصولات مختلف در یک سفارش بستگی دارد.

مسأله فوق به «مسأله تکمیل همزمان موجودی[6] »یا JRP معروف است. به علت وجود هزینه کلی سفارش دهی، بکارگیری سفارش دهی گروهی ممکن است منجر به صرفه جویی معنی داری در هزینه ها شود. این صرفه جویی بطور قابل توجهی وقتی تقاضای بین اقلام بطور نزدیکی به‌هم مرتبط هستند، افزایش می یابد (تسا و هوانگ [7]، 2009). بعلاوه صرفه جویی حاصل از محل سفارش دهی گروهی هر چه هزینه کلی سفارش دهی بزرگتر باشد، معنی دارتر است.

استراتژیهای حل JRP می تواند به دو نوع تقسیم شود:

1- استراتژی گروهبندی مستقیم[8] (DGS)

2-استراتژی گروهبندی غیرمستقیم [9] (IGS)

در استراتژی DGS، محصولات به تعدادی گروه از قبل مشخص شده، تقسیم می شوند و محصولات داخل هر گروه، با یک زمان سیکل مشترک سفارش داده می شوند. در استراتژی IGS، سفارش دهی در فواصل زمانی منظم انجام می شود که معمولاً به آن زمان سیکل پایه گفته می شود. هر محصول، ضریب عدد صحیحی از زمان سیکل پایه را داراست و در سیکلهای سفارشی که مضرب صحیح از این ضریب است سفارش داده می شود. گروهها در استراتژی IGS، بصورت غیر مستقیم، با محصولاتی که دارای یک ضریب صحیح یکسان هستند، تشکیل می شود. آرکین[10] و همکاران(1989)، ثابت کردند که مسأله JRP، یک مسأله با پیچیدگی سخت [11] است، بنابراین الگوریتمی که در یک زمان چند جمله ای بتواند مسأله JRP مخصوصاً با ابعاد بزرگ را حل کند وجود ندارد و لذا در مقالات بسیاری، با استفاده از الگوریتم­های فراابتکاری، روش­های حل تقریبی برای مسأله توسعه داده شده است. برای اولین بارگویال(1974) با محاسبه یک حد بالا و پایین روی زمان سیکل پایه یک الگوریتم محاسباتی، برای مشخص کردن کلیه می نیمم های محلی و در نتیجه می نیمم کل ارائه داد. بنابراین رویکرد گویال منجر به یافتن جواب بهینه برای مسأله JRP می شد ولی ممکن بود از لحاظ محاسباتی برای مسائل بزرگ به جواب نرسد. سیلور[12] (1976) یک الگوریتم کارا برای حل JRP، ارائه داد که در سال 1979 توسط گویال بهبود داده شده، سپس توسط کسپی و روزنبلات[13] (1983) توسعه بیشتری یافت. این الگوریتم شاید معروفترین روش هیوریستیک در حل JRP بوده و به نام الگوریتم RAND معروف است . این الگوریتم بر اساس محاسبه m مقدار مساوی برای زمان سیکل پایه از طریق حد پائین و بالای آن یعنی روی فاصله، T_max] [T_min و سپس بکارگیری الگوریتم سیلور جهت بهبود الگوریتم برای هر مقدار از زمان سیکل پایه می باشد.

 

بررسی تحقیقات انجام شده

تحقیقاتی که تا کنون روی مسأله JRP انجام شده است را می توان به دو دسته کلی زیر تقسیم کرد:

ü       ارائه روشهای مختلف جهت حل مدل JRP کلاسیک

ü    توسعه مدلهای جدید از روی مسأله JRP کلاسیک و ارائه روشهای مختلف جهت حل آنها که در این مورد عمدتاً موارد زیر در تحقیقات گذشته به چشم می خورد:

الف- توسعه « مدل تکمیل موجودی توأم چند کالا در حالت احتمالی[14] » یا SJRP که در آن تقاضای محصولات به صورت احتمالی در نظر گرفته می شودو هدف مینیمم کردن هزینه مورد انتظار در هر واحد زمان می باشد.

ب- توسعه« مدل تکمیل موجودی توأم چند کالا در حالت پویا[15] » یا DJRP که در آن تقاضای قطعی است ولی نسبت به زمان یکنواخت نیست و هدف عبارتست از مینیمم کردن هزینه کل در افق برنامه ریزی که شامل چند پریود می باشد.

ج- توسعه یکی از مدلهای JRP یا SJRPیاDJRP با در نظر گرفتن شرایط خاص بعنوان مثال:

ü       در نظر گرفتن زیر مجموعه ای از پریودهای زمانی گسسته جهت تکمیل موجودی

ü       در نظر گرفتن تخفیف های مقداری کلی

ü       در نظر گرفتن قیمت هر واحدمحصولات به صورت کاهشی یا افزایشی نسبت به زمان

ü       بکارگیری JRP بعنوان یک زیر مسأله در سایر مسائل

ü       در نظر گرفتن وابستگی هزینه های سفارش دهی به ترکیب موجود در کالاهایی که سفارش داده می شوند.

ü       در نظر گرفتن محدودیتهایی در مدل نظیر ظرفیتهای انبار و حمل و نقل و بودجه

ü       در نظر گرفتن تقاضای نا معین مشتری و همچنین تخمین های نا دقیق واحد هزینه نگهداری

در زمینه توسعه مدل JRP کلاسیک در شرایط خاص که تحقیق حاضر نیز به آن متعلق است، موارد زیر از ادبیات موضوع قابل استخراج می باشد، کلین و ونچورا[16] (1995) ، جهت ایجاد یک سیاست سفارش دهی ساده تر برای پیاده سازی در صنعت مدلی را ارائه دادند که در آن زمانهای تکمیل موجودی تنها به ابتدای پریودهای زمانی گسسته محدود شد. مون و چا[17](2005)، دو الگوریتم برای حل JRP، وقتی تأمین کننده تخفیف های مقداری کلی پیشنهاد می کند، توسعه دادند. نویسندگان دو قضیه اثبات کردند که سپس در توسعه دو الگوریتم برای پیدا کردن جواب بکار بردند. خوجا و همکاران[18] (2005) فرض کردند که هزینه هر واحد محصولات در یک افق زمانی محدود و متناسب با یک آهنگ پیوسته نسبت به زمان کاهشی یا افزایشی است و یک الگوریتم برای حل JRP، ارائه دادند. سیاجادی[19] و همکاران (2005)، مدلی را فرموله کرد که در آنها JRP بعنوان یک زیر مسأله بکار رفت، آنها مدل بهینه سازی تصمیمات موجودی یک فروشنده که بطور همزمان چندین قطعه را برای تولید محصول نهایی بکار می برد، را توسعه دادند. چان[20] و همکاران(2006)، یک رویکرد حل برای برنامه ریزی تحویل از یک تأمین کننده به چندین خریدار توسعه دادند که خریداران JRP را برای تکمیل موجودی خود از تأمین کننده بکار می برندو در ادامه مسأله برنامه ریزی تحویل تحت 4 هدف مختلف فرموله شد. هوک[21] (2006)، یک مدل توسعه یافته از JRP برای در برگرفتن موارد عملی با در نظر گرفتن ظرفیتهای انبار و حمل ونقل و محدودیت بودجه ارائه داده است و یک رویکرد ساده برای محاسبه حد پایین مناسب برای سیکل مشترک پایه ارائه داد. السن[22] (2008)، حالتی از مسأله JRP را در نظر گرفت که در آن هزینه های جزئی سفارش دهی به یکدیگر وابسته اند. وابستگی خطی هزینه های جزیی سفارش دهی در JRP، هنگامی رخ می دهد که هزینه وارد کردن یک آیتم در یک سفارش به اینکه کدامیک از کارهای دیگر در سفارش هستند، بستگی دارد وی در ادامه، یک الگوریتم تکاملی [23] (EA) برای حل چنین مسأله ای ارائه داد. در مقاله ای که وانگ[24] و همکاران (2008) ارائه دادند به مطالعه ای از مسأله JRP، تحت تقاضاهای نا معین مشتری و تخمین نا دقیق واحد هزینه نگهداری پرداختند. سو[25] (2009)، مسأله JRP را برای مدلسازی تصمیمات موجودی برای یک کارخانه مرکزی و شعبه های آن در یک سیستم تولید بهنگام بکار گرفت. لی[26] (2004) یک مدل JRP وقتی چندین خریدار وجود دارند مدلسازی کرده و با توسعه ای از الگوریتم RAND آنرا حل نمود. اکثر مدلهای موجودی چندین مفهوم هزینه ای و نیز احتیاجات سطح سرویس دهی به مشتری را در داخل یک تابع هدف تکی جایگزین می کنند، سپس تصمیمات بهینه در مورد اینکه چقدر سفارش داده شود و کی سفارش داده شود، توسط روشهای سنتی بهینه سازی آغاز می شود، در حالیکه موارد زیادی در مسائل مربوط به سیستم های واقعی کنترل موجودی وجود دارد که تصمیم گیرندگان مایل به بهینه سازی بیش از یک هدف که بعضاً ممکن است با یکدیگر در تضاد نیز باشند هستند. در مورد مسأله JRP، تا کنون به حالتی که بیش از یک هدف در مدل در نظر گرفته شده و در نتیحه بر کارایی کاربردی و عملی آن بیفزاید، پرداخته نشده است. در مقاله حاضر به مدلسازی مسأله JRP با در نظر گرفتن دو هدف پرداخته شده است و از طرفی جهت کاربردی تر شدن مدل، محدودیت فضای انبار نیز که در عمل اکثر سیستمهای کنترل موجودی با آن مواجه هستند نیز به مدل اضافه شده است. هدف دیگر مقاله حاضر، ارائه یک رویکردی کارا برای حل مسأله پیشنهادی است که به این منظور به توسعه الگوریتم ژنتیک چند هدفه که کارایی خوبی برای بهینه سازی مسائل چند هدفه از خود نشان داده است پرداخته و نتایج حاصل نشان داده شده است. روش انجام تحقیق حاضر، روش اسنادی و مطالعات کتابخانه ای یا مراجعه به منابع در دسترس در خصوص موضوعات مرتبط با موضوع تحقیق می باشد. همچنین استفاده از نرم افزارهای محاسباتی و برنامه نویسی پیچیده و بهره گیری از امکانات کامپیوترمنا سب در اجرای مدل توسعه داده شده ضروری خواهد بود. در ادامه مطالب ارائه شده در مقاله حاضر در 5 بخش ارائه می شود. در قسمت سوم به معرفی مدل پیشنهادی می پردازیم. به معرفی الگوریتم ژنتیک چند هدفه در بخش چهارم پرداخته می شود. توسعه الگوریتم ژنتیک چند هدفه برای حل مدل پیشنهادی در قسمت پنجم انجام می شود. در قسمت ششم نتایج حاصل از حل مسأله با روش پیشنهادی ارائه می شود و در قسمت هفتم نیز به جمع بندی، نتیجه گیری و ارائه پیشنهاد برای ادامه تحقیق در مورد این موضوع می پردازیم.

 

معرفی مدل دو هدفه تکمیل توأم موجودی چند کالا با وجود محدودیت فضا

در این قسمت به معرفی فرضیات، پارامترها و متغیرهای تصمیم در مدل پیشنهادی پرداخته و سپس مدل نهایی ارائه می شود.

 

فرضیات

فرضیات مدل، شبیه فرضیات در مدل JRP کلاسیک می باشد که آن هم شبیه فرضیات مدل «مقدار سفارش اقتصادی[27]» یا همان EOQاست که این فرضیات عبارتند از:

1-      وجود تقاضای قطعی و یکنواخت

2-      عدم وجود تخفیف

3-      خطی بودن هزینه نگهداری

4-      عدم مجاز بودن کمبود

علاوه بر آن فرضیات زیر نیز اضافه می شوند:

5-      استفاده از استراتژی IGS

6-      محدودیت فضای انبار

 

پارامترهای مدل

n: تعداد محصولات

i: اندیس محصولات n , ... , i = 1

D_i: تقاضای سالیانه محصول i ام

h_i: هزینه نگهداری سالیانه برای محصول i ام

S: هزینه کلی سفارش دهی در هر بار سفارش

s_i: هزینه جزئی سفارش دهی که در صورت سفارش محصول iام سفارش داده شود پرداخت می شود

c_i: هزینه خرید یک واحد محصول i ام

V: ماکزیمم فضای انبار

v_i: فضای لازم برای انبار کردن یک واحد کالای i‌ام

 

متغیرهای تصمیم

Q_i: میزان سفارش محصول i ام (واحد کالا)

T: زمان بین دو سفارش متوالی یا زمان سیکل پایه

T_i: فاصله زمانی بین دو سفارش متوالی محصول i ام

k_i: ضریب عدد صحیح سفارش دهی محصول i ام

متغیرهای تصمیم ا صلی عبارتند از Tو k_i، بطوریکه مطابق روابط 1و2 متغیرهای Q_iو T_i از روی آنها قابل بدست آوردن هستند.

(1)

 

 (2)

 

 

توابع هدف

الف) هزینه کل سفارش دهی [28] (TCS) و نگهداری موجودی[29] (TCH) در واحد زمان (f1 )

ب ) هزینه کل سرمایه درگیر در موجودی (f2 )

 

 مدل پیشنهادی

(3)

 

 (4)

 

 (5)

 

 

 

 

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

بهینه سازی مسائل چند هدفه

یک دسته از سخت ترین و در عین حال پرکاربردترین مدلها در مسائل بهینه سازی، مسائل چند هدفه هستند. در یک مسأله بهینه سازی چند هدفه، معمولاً یک جواب بهینه منحصر به فرد وجود دارد ولی در مسائل بهینه سازی چند هدفه، توابع هدف ممکن است با یکدیگر در تعارض باشند، بنابراین پیدا کردن یک جواب بهینه بطوریکه بصورت همزمان کلیه اهداف را بهینه کند معمولاًامکان پذیر نیست. یکی از روشهای حل اینگونه مسائل ادغام کردن اهداف مختلف در یک تابع هدف است. در چنین مواردی جواب بهینه با استفاده از متدهایی نظیر تابع مطلوبیت و یا مجموع وزین توابع هدف بدست می آید، و لیکن در این روشها نیز انتخاب اوزان مناسب برای توابع هدف و یا انتخاب یک تابع مطلوبیت مناسب یک چالش محسوب می شود. از جمله روشهای دیگر حل مسائل چند هدفه، روشهایی هستند که هدفشان بدست آوردن جوابهای بهینه پارتویی و یا زیر مجموعه ای کارا ازآن می باشد. مجموعه جوابهای پارتویی[30] شامل جوابهایی می شود که توسط هیچ جواب دیگری ازمجموعه جوابهای امکان پذیر مسأله چیره[31] نمی شوند. یک جواب چیره ناپذیر جوابی است که بهبود در یک تابع هدف آن منجر به بدتر شدن حداقل یک تابع هدف دیگر می شود. با استفاده از چنین روشهایی وارائه مجموعه جوابهای چیره ناپذیر، این فرد تصمیم گیرنده است که با توجه به تبادل[32] بین اهداف به انتخاب جواب مطلوب خود می پردازد. (کناک[33] و همکاران، 2006)

 

الگوریتمهای تکاملی چند هدفه[34]

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

در یک الگوریتم تکاملی چند هدفه که یک توسعه از الگوریتم تکاملی است به دو سؤال اساسی بایستی پاسخ داده شود:

1- مکانیزم انتخاب کروموزومها به نحوی که جوابهای چیره ناپذیر شانس بیشتری برای انتخاب و ایجاد نسل بعد را داشته باشند.

2- مکانیزم ایجاد تنوع در جوابهای تولید شده به نحوی که حتی المقدور کل فضای جواب جستجو شده و تا حد امکان کل مجموعه جوابهای پارتویی ارزیابی شود.

الگوریتمهای تکاملی با توجه به مکانیسمی که برای پاسخ به هر یک از دو پرسش فوق انتخاب می‌کنند، متعلق به یکی از سه دسته زیرهستند:

1- توابع ادغامی[35] که مجموع وزین توابع هدف را بعنوان یک تابع هدف کلی در نظر می گیرند.

2- روشهای مبتنی بر جمعیت [36]، به عنوان یک مثال کلاسیک از این دسته VEGA[37] را می توان نام برد.

3- روشهای مبتنی بر جوابهای پارتویی[38]، یک مثال کلاسیک از این دسته MOGA[39] است.

 

 الگوریتم ژنتیک چند هدفه (MOGA)

در مکانیسم انتخاب در MOGA رتبه هر کروموزوم در جمعیت برابر است با تعداد جوابهایی که آنرا چیره می کنند. کل جوابهایی که چیره ناپذیرند دارای رتبه برابر هستند و در نتیجه شانس برابری برای انتخاب در تکرار بعد و تولید جمعیت جدید را دارند. MOGA به منظور ایجاد پراکندگی لازم در فضای جواب از رویکرد اشتراک برازندگی[40] برای بدست آوردن جوابهایی که بطور یکنواخت در مجموعه جوابهای پارتو توزیع شده اند، استفاده می کند. در این تکنیک جوابهایی که در مناطقی قرار دارند که چگالی جوابهای یکسان در آنها زیاد است، برازندگیشان کاهش می یابد.

برای توسعه هر الگوریتم ژنتیک اجزاء اصلی و مهم الگوریتم بایستی به دقت تعریف شوند که در ادامه به معرفی آنها می پردازیم:

 

 

حدود متغیرهای تصمیم

همانطور که قبلاً نیز اشاره شد در استراتژی IGS که ما نیز از آن استفاده می کنیم متغیرهای تصمیم عبارتند از، زمان سیکل پایه(T) و ضرایب عدد صحیح مربوط به هر کالا(k_i,s). حد بالا و پایین مقادیر T را بصورت زیر در نظر می گیریم (خوجا و همکاران، 2000):

(6)

 

(7)

 

حد پایین برای مقادیر(k_i,s) که مسلماً عبارتست از k_i(min) =1 برای بدست آوردن حد بالا هم ابتدا مقادیر T_i(in) از فرمول EOQ بصورت مستقل برای هر کالا بدست می آید و سپس T_min به صورت زیر بدست می آید (خوجا و همکاران، 2000).

(8)

 

(9)

 

بطوریکه در رابطه فوق منظور ازنماد [a] اولین عدد صحیح بزرگتر از a است.

تابع هدف دوم ما بر روی روابط فوق بی تأثیر است ولی محدودیت مدل، T_max را بصورت زیر تغییر می کند:

(10)

 

 

نمایش[41]

یکی از مهمترین مسائل در الگوریتم ژنتیک، نحوه باز نمایی یا کد کردن جوابها می باشد. در مدل پیشنهادی ما، یک کروموزوم یا یک جواب حاوی (n+1) ژن می باشد، بطوریکه n ژن اول که مقادیر عدد صحیح بوده حاوی مقادیر (k_i,s) می باشند و یک ژن آخر حاوی مقدار مربوط به زمان سیکل پایه بوده و متغیری پیوسته می باشد.

 

جمعیت اولیه[42]

جمعیت اولیه بصورت تصادفی ایجاد می شود. برای ایجاد هر عضو جمعیت، ابتدا n عدد تصادفی عدد صحیح بین k_i(min) و k_i(max) تولید می شود و سپس یک عدد تصادفی پیوسته بین T_min و T_max ایجاد می شود. قاعدتاً از بین جوابهای تولید شده جوابهایی قابل قبول هستند که در محدودیت مدل صدق کنند.

 

استراتژی انتخاب[43]

برای انتخاب والدین[44] از میان جمعیت برای ایجاد نسل بعدفرزندان[45] از مکانیسم چرخ رولت[46] استفاده می شود. در این مکانیزم انتخاب کروموزومها احتمالی است، به طوریکه کروموزومهای با تابع برازندگی بیشتر شانس بیشتری برای انتخاب شدن دارند و در واقع احتمال انتخاب i امین کروموزوم با تابع برازندگی f_i، عبارتست از  .

 

تابع برازندگی[47]

میزان برازندگی هر کروموزوم مطابق مراحل زیر ارزیابی می شود:

1- برای هر کروموزوم در هر تکرار، رتبه آن یعنیr(x,t) مطابق رابطه زیر محاسبه می شود:

 

nq(x,t) عبارتست از تعداد جوابهایی که در تکرار t، جواب x را چیره می کنند. و منظور از p_t، تکرار t ام جمعیت می باشد.

2- برای هر جواب بر اساس رتبه بدست آمده یک مقدار برازندگی مطابق رابطه زیر محاسبه می شود:

(12)

 

n_k عبارتست از تعداد جوابهای با رتبه k و لذا  عبارتست از تعداد جوابهای با رتبه r(x,t)

1- برای هر جواب یک شمارنده تشابه یعنی nc(x,t) مطابق رابطه زیر محاسبه می کنیم:

 

(13)

 

_shareσ آستانه تشابه نام دارد و می تواند بین 0 تا 1 تغییر کند.

dz(x,y) فاصله اقلیدسی بین دو جواب x,y در فضای نرمال سازی شده توابع هدف بوده و بین صفر و یک می باشد و مطابق رابطه زیر بدست می آید:

(14)

 

 

1- برای هر جواب  مقداربرازندگی اشتراکی یعنی  مطابق رابطه زیر بدست می آید:

(15)

 

2- مقادیربرازندگی با بکارگیری مقادیر برازندگی اشتراکی به صورت زیر نرمالسازی می شود:

(16)

 

 

 تقاطع[48] و جهش[49]

بعد از انتخاب والدین با مکانیزم چرخ رولت و بر اساس  که در رابطه 16 ارائه شد، فرزندان با دو مکانیزم تقاطع و جهش تولید می شوند. متدهای مختلفی برای انجام این دو عملگر وجود دارند. در اینجا از متد نقطه تصادفی جهت عملگر تقاطع استفاده می شود، بطوریکه این عملگر با احتمال p_c عمل می کندو تعدادی کروموزوم تصادفی از دو والد با مکان مشترک را نتخاب می کند و جای آنها را تعویض می کند. بعد از تولید فرزندان با این مکانیزم، عملگر جهش به کار گرفته می شود که در این عملگر هر کروموزوم با احتمال ضعیف برابر p_mتغییر می کند. در هر یک از دو عملگر فوق مقدار هر کروموزوم بین حدود پایین و بالایی که در قسمتهای قبل ارائه شد تغییر می کند و همچنین تنها جوابهایی که در محدودیت مسأله صدق کنند قابل قبول خواهند بود.

 

جایگزینی[50]

بعد از تولید قرزندان، مجدداً از مکانیزم چرخ رولت استفاده می شود وبه تعداد اندازه جمعیت که از قبل تعریف شده است، از فرزندان جدید و نسل قبل به نسل بعد منتقل می شوند.

 

شرط توقف[51]

هر گاه تعداد جوابهای بهینه پارتویی در طی 50 تکرار متوالی تغییر نکند، الگوریتم متوقف خواهد شد.

 

مراحل کلی الگوریتم ژنتیک چند هدفه

قدم 1: با یک جمعیت اولیه تصادفی(p₀) شروع کنید(t=0)

قدم 2: اگر شرط توقف برقرار است متوقف شوید، جواب نهایی عبارت است از p_t

قدم 3: برای هر عضو جمعیت مقدار تابع برازندگی f ⁽²⁾ (x,t) را با استفاده از رابطه 16 محاسبه کنید.

قدم 4: با استفاده از متد چرخ رولت و بر اساس مقادیر f ⁽²⁾ (x,t) والدها را جهت تولید نسل بعد انتخاب کنید.

قدم 5: با استفاده از عملگر تقاطع و جهش فرزندان نسل جدید را تولید کنید.

قدم 6: با استفاده از مکانیزم چرخ رولت از مجموع والدین و فرزندان تولید شده به تعداد اندازه جمعیت کروموزوم انتخاب کنید.

قدم 7: قرار دهید t = t + 1 و به قدم 2 بروید.

 

نتایج حاصل از اجرای مدل

برای بررسی عملکرد الگوریتم پیشنهادی جهت حل مدل، الگوریتم پیشنهادی روی 1600 مسأله که هر یک بصورت تصادفی ایجاد شده اند، تست شده است . هر مسأله دارای 6 پارامتر اصلی است که از مقاله خوجا و همکاران(2000) استخراج شده و در جدول 1 خلاصه شده است، همچنین پارامترهای مورد نیاز الگوریتم نیز در جدول 2 خلاصه شده است. این پارامترها با تکرار الگوریتم به تعداد دفعات زیاد و مطابق با بهترین نتایج حاصل انتخاب شده است.

 

 

 

 

 

 

 

 

جدول1. مقادیر پارامترهای هر مسأله

 

جدول 2. مقادیر پارامترهای الگوریتم

 

برای هر مقدار n و S که با توجه به جدول 1 شامل 16 مقدار می شود، 100 مسأله تصادفی تولید شده که تفاوت آنها در مقادیر D_i و s_iوH_i می باشد، این مسائل با الگوریتم پیشنهادی که توسط نرم افزار ویژوال بیسیک 2007 کد شده، حل گردیده و نتایج حاصل در جدول 3 خلاصه شده است. ستون پنجم این جدول نشان دهنده متوسط تعداد جوابهای بهینه پارتویی است که برای هر ردیف در 100 مسأله تصادفی ایجاد شده، بدست می آید. روند تغییرات این مقادیر در نمودار 1 نشان داده شده است، همانگونه که این نمودار نشان می دهد با افزایش ابعاد مسأله تعداد جوابهای پارتویی نیز افزایش یافته است . در ادامه در هر ردیف این جدول برای هر مسأله تولید شده از بین جوابهای بهینه پارتویی مقدار مینیمم f1 را انتخاب کرده و میانگین آن را روی هر 100 مسأله محاسبه کرده واز مقادیر متناظر f2 آنها نیز میانگین گرفته و این مقادیر را در ستون ششم و هفتم جدول ارائه شده است. همین کار برعکس برای مقادیر می نیمم f2 و مقادیر متناظر f1 نیز انجام شده و نتایج درستون هشتم و نهم جدول ارائه شده است. ستون دهم جدول تفاضل ستونهای 8 و6 و ستون یازدهم تفاضل ستونهای 9و 7 جدول می باشد هر چه مقادیر دو ستون آخر جدول بزرگتر باشد نشان دهنده این است که جوابهای پارتویی دارای پراکندگی بیشتری هستند. این مقادیر در قالب نمودار 2 نمایش داده شده است، همانگونه که ملاحظه می کنید؛ اولاً با افزایش ابعاد مسأله این مقادیر زیادتر شده و در واقع جوابهای پارتویی دارای تنوع بیشتری می شوند و ثانیاً در کل مقادیر مربوط به f1 نسبت به مقادیر f2 از پراکندگی بیشتری برخوردارند.

 

جدول 3. نتایج حاصل اجرای 1600 مسأله تصادفی

 

 

نمودار1. متوسط تعداد جوابهای بهینه پارتویی برای مقادیر مختلف n وS

 

نمودار 2 . میزان پراکندگی جوابهای پارتویی

 

در ادامه نتایج حاصل از اجرای یک مسأله تصادفی ارائه می شود. در این مسأله پارامترها عبارتند از: N=30,S=15, . الگوریتم پیشنهادی طی 457 تکرار این مسأله را حل کرده است . روند تغییرات تعداد جوابهای پارتویی که مسأله طی تکرارهای متوالی الگوریتم به آن دست پیدا کرده در نمودار 3 ارائه شده است . همانگونه که ملاحظه می شود و در شرط توقف الگوریتم نیز ذکر شد در طی 50 تکرارآخر الگوریتم این تعداد بدون تغیر مانده است.

 

 

نمودار 3. روند تغییر تعداد جوابهای بهینه پارتویی در طی تکرارهای الگوریتم

 

جوابهای نهایی این مسأله که شامل 7 جواب بهینه پارتویی می شود در نمودار 4 ارائه شده است. همانگونه که ملاحظه می‌کنید هیچ یک از این جوابها دیگری را مغلوب نمی کند، یا به عبارت ساده تر جوابی که هر دو تابع هدفش از دو تابع هدف سایر جوابها بهتر باشد وجود ندارد و نهایتاً این تصمیم گیرنده است که با توجه به تبادلات بین اهداف یکی از این جوابهای پارتویی را به عنوان جواب رضایت بخش خود انتخاب می کند. لازم به ذکر است که در هر تکرار الگوریتم تعدادی جواب پارتویی بدست می آید که ممکن است لیست جوابهای پارتویی که تا آن تکرار بدست آمده را تغییر دهد. بعنوان نمونه در نمودار 5 جوابهای پارتویی تکرار آخر که شامل 5 جواب می باشد ارائه شده است. روند بهبود f1 و f2 طی تکرارهای متوالی الگوریتم نیزبه ترتیب در نمودارهای 6و7 آمده است، همانگونه که ملاحظه می کنید شیب بهبود در مورد هر دو نمودار در ابتدای الگوریتم تندتر از تکرارهای پایانی است که نشان دهنده عملکرد منطقی الگوریتم پیشنهادی است. لازم به ذکر است که برای حل این مسأله از پارامترهای جدول 2 استفاده شده است، ولی برای حل این مسأله یا هر مسأله دلخواه دیگری میتوان با ترکیبات مختلف پارامترها مسأله را حل کرد تا بهترین ترکیب پارامترها برای هر مسأله بدست آید.

 

 

نمودار 4. جوابهای بهینه پارتویی نهایی

 

 

نمودار 5. جوابهای بهینه پارتویی تکرار آخر الگوریتم

 

 

نمودار 6. روند بهبود f1 در طی تکرارهای الگوریتم

 

نمودار 7. روند بهبود f2 در طی تکرارهای الگوریتم