دانلود تحقیق کاربرد الگوریتم ژنتیک ترکیبی برای زمان بندی تولید کارگاهی

زمان بندی برای تولید کارگاهی (job shop) از دو زمینه مدیریت محصول و بهره وری گروهی خیلی مهم است.
هر چند که این امر کاملا متفاوت است با بدست آوردن یک جواب بهینه با متدهای بهینه یابی مرسوم، زیرا مسئله مورد نظر دارای محاسبات خیلی پیچیده می باشد.(مسئله فوق از نوع NP-Hardاست.)
اثبات شده است که الگوریتم ژنتیک (GA) برای تنوع وضعیت هایی که شامل زمان بندی و توالی می باشند(S.S) موثر می باشد.
در این مقاله یک نوع الگوریتم ژنتیکی ابتکاری هایبرید برای مسئله n/m/G/Cmax پیشنهاد شده است ، هایبرید به این خاطر که قوانین زمان بندی از قبیل SPT و MWKR با الگوریتم ژنتیک ادغام شده اند، همچنین از تکنیک جستجوی محلی (NST ) به عنوان رویه ای کمکی جهت بهبود حل عملکردی کمک گرفته ایم.
کارایی و اثر بخشی این الگوریتم جدید به وسیله مقایسه با برخی متدهای معروف دیگر از قبیل الگوریتم های NST (تکنیک جستجوی محلی)، SA (تبرید شبیه سازی شده) و ژنتیک ، به اثبات رسیده است.






1.

مقدمه
زمان بندی برای تولید کارگاهی یک موضوع مهم در مدیریت تولید است، که توجه آن برروی معین کردن سفارش ترخیص و زمان های مجموعه پدیده ها بر روی ماشین های مربوطه،با در نظر گرفتن محدودیت های مربوطه معطوف شده است، که مجموعه n پدیده بایستی توسط m ماشین پروسه شوند، که عملیات iام بایستی برروی ماشین jام با زمان فرآیند معینی tij انجام شود.

همچنین هر ماشین تنها یک پدیده را در یک زمان می تواند پروسه نماید و یک فعالیت نمی تواند مانع انجام کار شود.
هدف مسئله این است که Cmax (دوره ساخت) مینیمم شود.
این مسئله از نوع NP-Hard است(Garey.Johnson & Sethi 1976) که از متدهای موجود الگوریتم ژنتیک بالاترین کارایی را از خود نشان داده اند.
2.الگوریتم ژنتیک
1-2- مقدمه
در میان روش های بهینه سازی الهام گرفته از طبیعت جاندار، الگوریتم ژنتیک (GA) که بر اساس اصول تکامل طبیعی پایه ریزی شده،از تکامل یافته ترین ها به شمار می آید.
الگوریتم ژنتیک یک روش بهینه سازی غیر کلاسیک و جستجوی مستقیم است که فقط با خود تابع و نه مشتقات آن سرو کار داردو بر اساس مکانیزم بقای اصلح و علم ژنتیک طبیعی ،الهام گرفته از نظریه تکامل داروین بنا شده است.

در این روش جستجو از چندین نقطه در فضای حل و بطور همزمان اغاز می شود و با جستجوی نقطه به نقطه فضای متغیرهای تابع هدف بررسی شده و نهایتا نقطه ای که بیشترین و یا کمترین مطلق است، به عنوان نقطه بهینه مطرح می شود.این الگوریتم ابتدا توسط جان هلند، همکاران و دانشجویانش در دانشگاه میشیگان ایالات متحده در سال 1962 بیان شد و بنام الگوریتم ژنتیک شهرت یافت.وی بیان کرد که الگوریتم ژنتیک در طول دورهای محاسباتی مختلف با شناسایی واحدهای ساختاری خوب و الحاق آنها به یکدیگر ، به نواحی با متوسط برازندگی بیشتر، همگرا می شود.
آنها از تحقیقاتشان دو هدف اصلی زیر را دنبال می کردند:
1- ارائه شرح دقیق و خلاصه ای از عملکرد قابل قبول از سیستم های طبیعی.
2- طراحی نرم افزارهای سیستم های ساختگی که ساز و کارهای اصلی سیستم را در بر داشته باشد.
مهمترین کاربرد الگوریتم های ژنتیک برای بهینه سازی می باشد.

در روش های معمولی و متعارف بهینه سازی (برنامه ریزی خطی و غیر خطی،معادله لاگرانژ و...) توابع هدف باید حتما پیوسته و مشتق پذیر باشند،در حالی که در روش الگوریتم ژنتیک نیازی به تابع پیوسته و مشتق پذیرنیست.بر اساس روش کار الگوریتم ژنتیک یک نمونه از تمامی متغیرهای تصمیم گیری که موثر بر تابع عملکرد می باشند بعنوان یک عضو تلقی می گردند که تعدادی از این نمونه ها ، مجموعه ای از اعضا را تشکیل می دهند.در این روش مجموعه ای از جمعیت متغیرها در روند جستجو به کار می روند بدین ترتیب همزمان با ایجاد بیشتر برای متغیر های شایسته تر ، احتمال یافتن نقطه بهینه مطلق یا سراسری افزایش می یابد، این ویژگی بخصوص برای توابعی با تغییرات ناگهانی و دارای چندین نقطه بهینه موضعی ،مناسب می باشد.
2-2- مفاهیم اولیه در الگوریتم ژنتیک
قبل از ارائه الگوریتم لازم است مفاهیم اولیه این روش و اجزاء تشکیل دهنده آن بررسی شوند که بترتیب به شرح آنها پرداخته شده است:
- کد کردن : GA به جای اینکه برروی پارامترها یا متغیرهای مسئله کارکند، با شکل کد شده آنها به طور مناسب سروکار دارد.

درGA جوابها در قالب رشته ای از ژنها که کروموزوم نامیده می شوند ،نمود پیدا می کند.

به این دلیل انتخاب نوع کدگذاری و طول رشته کروموزوم اهمیت ویژه ای می یابد.ژنها می توانند به صورت اعداد در مبنای باینری (0, 1)، اعداد در مبنای دهدهی (9,...,2,1( ، حروف انگلیسی یا هر نماد دیگر بیان شوند.
- رشته : یک رشته دنباله ای از بیت ها ست که به عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مسئله مورد نظر می باشد.در حقیقت بیت های یک رشته نقش ژنها در طبیعت را بازی می کنند.هر بیت متغیر گسسته ای است که از یک مجموعه Q عضوی انتخاب می شود.چنانچه از کدگذاری باینری استفاده شود ، هر بیت یکی از دو مقدار 0و1 را می پذیرد بنابراین در این حالت Q=2 می باشد.
- جمعیت : مجموعه ای از رشته ها را جمعیت می گویند.یکی از ویژگی های جمعیت این است که به جای تمرکز روی یک نقطه از فضای جستجو یا یک رشته ،بر روی جمعیتی از رشته ها کار می کند.بنابراین در هر مرحله الگوریتم دارای جمعیتی از رشته ها بوده که خواص مورد نظر را از جمعیت مرحله قبل دارا می باشد.
به هنگام استفاده از GA به عنوان یک روش بهینه سازی، باید در خصوص تعیین اندازه جمعیت تصمیم گرفته شود.از جمله مهمترین عواملی که در این کار موثر هستند می توان به شیوه نمایش فضای جواب ، نوع مسئله ای که باید حل گردد و عملگرهای به کار رفته اشاره نمود.اما آنچه بهترین جواب را می دهد تجربه و آزمایش است.اندازه جمعیت تاثیر فراوانی در عملکرد و راندمان الگوریتم های ژنتیک دارد.اگر تعداد جمعیت خیلی کم باشد این الگوریتم ها با راندمان بسیار پائین عمل خواهند کرد ، زیرا نمونه های مورد نیاز به قدر کافی برای نمایش اکثریت فضاهای جستجو وجود ندارد.
کار کردن با جمعیت های زیاد اگرچه ارائه دهنده فضاهای جستجوی زیادتری می باشد و GA می تواند جستجوی آگاهانه تری را ارائه دهد ، ولی این تعداد زیاد جمعیت باعث می گردد که یک همگرایی زود هنگام به سمت نقاط بهینه محلی بدست می آید.

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

1-2-2- مقدار برازندگی
یکی از مراحل GA ارزیابی جوابهای بدست آمده در هر مرحله است.

در واقع ارزش جوابهای بدست آمده در هر مرحله تعیین می شود.مناسب بودن یا نبودن جواب با معیاری که از تابع هدف بدست می آید ، سنجیده می شود.هر چه که یک جواب مناسب تر باشد ، مقدار برازندگی بیشتری دارد که با استفاده از محدوده دانش مسئله به کار برده شده محاسبه می شود.برای آنکه شانس بقای چنین جوابی بیشتر شود احتمال بقای آن متناسب با مقدار برازندگی آن در نظر گرفته می شود.بنابراین رشته ای که برازنده تر است با احتمال بیشتری در تولید فرزندان شرکت می کند و دنباله های بیشتری را بوجود می آورد.

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

با ارزشترین جوابها درهرمرحله ، مانند قویترین موجودات در یک جمعیت می باشند.در تکثیر، رشته های با میزان تطبیق کم ، از جمعیت حذف می شوند و رشته های با میزان تطبیق زیاد، تاثیر بیشتری در تولید جمعیت بعدی خواهند داشت.

معمولا در مواردی که امکان دارد، تابع برازندگی را در فاصله (0,1) نرمالیزه می کند.

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

مثلا در ترکیب یک نقطه ای اگرهررشته بصورت دنباله ای از صفرویک (باینری) و به طول L کد بندی شده باشد یک عدد تصادفی K€(1,L) با توزیع احتمال یکنواخت تولید می شود، سپس درهردو رشته باینری مورد نظر که هر یک L عنصر دارند،Kمین عنصر را مشخص کرده و عناصر واقع در سمت راست K مین عنصر درهردو عدد باینری با یکدیگر جابجا شوند.

تعداد نقاط تعویض بیشتر از یک نقطه، معادل آن است که عمل ترکیب فوق در چند مرحله انجام می شود.

3-2-2- عملگر جهش رشته های که تحت عمل ترکیب قرار گرفته اند با احتمال P عملگر جهش برروی آنها اعمال می شود.

جهش روی یک کاراکتر بصورت تغییر تصادفی آن به یکی از کاراکترهای موجود در مجموعه الفبای کاراکترها انجام می شود.

مثلا اگر رشته ها بصورت اعداد باینری بطولL کدبندی شده باشند یک عدد تصادفی K€(1,L) با توزیع یکنواخت تولید می شود سپس در عدد باینری مورد نظر که L عنصر دارد Kمین عنصر را مشخص کرده و در صورت صفر بودن به یک ودر صورت یک بودن به صفر تبدیل می شود.

4-2-2- فرآیند انتخاب پس از اعمال عملگرهای GA مجموعه ای از رشته ها برای دور محاسباتی بعد با تعدادی برابر جمعیت اولیه تعیین می شوند.

این مجموعه تشکیل شده از کلیه رشته های فرزند ( حاصل از عملگرهای ترکیب و جهش) و تعدادی از رشته های مرحله قبل می باشد.انتخاب این تعداد از رشته های اولیه بطور تصادفی از بین رشته های عدد برازندگی بالاتر انجام می شود ، این مرحله را تکثیر می گویند.

گلدبرگ روش چرخ گردان را برای تکثیر ارائه داد.

دراین روش یک چرخ که سطح آن متناسب با برازندگی هر رشته تقسیم بندی شده است ، در مقابل یک نشانه می چرخد تا بالاخره متوقف شود و یکی از سطوح در مقابل نشانه قرار گیرد.

به این ترتیب یک رشته انتخاب می شود ، اگر برازندگی رشته زیاد باشد شانس آن برای انتخاب شدن بیشتر است و برعکس.

بنابراین با تکرار به دفعات مناسب می توان رشته های لازم برای اعمال عملگرهای ژنتیک را انتخاب نمود (تکثیر یا تکرار).

این نوع انتخاب (تکثیر) بر اسا س ارزیابی میزان برازندگی یک رشته نسبت به بقیه رشته ها و استفاده ازعنصر تصادف است.

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

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

هر رشته در واقع شامل همه متغیرهای کد شده ای است که در مسئله مورد نظر وجود دارد.

نحوه نمایش در واقع نوعی نگاشت از فضای جستجو به فضای رشته هایی به طول L که با مجموعه الفبایی کاراکتری ساخته شده اند، n می باشد.

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

بدیهی است که رشته هایی که عدد برازندگی بیشتری دارند به تعداد بیشتری انتخاب می شوند.

تعیین پارامترها و متغیرها پارامترهای GA عبارتند از : الف- میزان جمعیت و ماکزیمم تعداد تکرار(تعداد نسلها) ب- احتمال عملگرهای ترکیب و جهش 4- مشخص کردن شرط پایان تکرار و نحوه انتخاب خروجی الگوریتم شرط خاتمه الگورتم را می توان تعداد مشخص تکرار یا رسیدن به مقدار معینی از برازندگی قرار دارد و بهترین رشته از آخرین نسل را می توان به عنوان خروجی در نظر گرفت.

شکل 3 نمودار گردشی اجرای الگوریتم ژنتیک را نشان می دهد.

3-الگوریتم ژنتیک ترکیبی ابتکاری برای زمانبندی Job shop زمان بندی انجام شده بایستی دارای خصوصیات زیر باشد.(siman,1982) با محدودیت های تکنولوژیکی سازگار باشد.

نسبت به معیارهای عملکردی بهینه باشد.

جواب یک مسئله job shop را می توان به صورت زیر نمایش داد.

Job M1: o11 o12 … o1n M2: o21 o22 … o2n … … … Mm: om1 om2 … omn که{ J1 ,J2 ,….

Jn }єomn و Mi ماشین iام و Jj پدیده شماره j می باشد.

تعداد کل زمان بندی های ممکن (هم قابل قبول و هم غیر قابل قبول (n!)m می باشد که به عنوان مثال اگر n,m برابر با 10 باشند تعداد کل حالتهای ممکن فوق العاده زیاد است در نتیجه برای حل آن به روشهای ابتکاری از جمله ژنتیک روی می آوریم.

به منظور کارایی بیشتر الگوریتم ژنتیک ارائه برخی روشها جهت محدود کردن فضای جواب لازم می باشد.

برخی آزمایشات عددی نشان می دهد که اولین پدیده بر روی هر ماشین (i=1,2,….,m) oi1 معمولا نقش مهمی را در مشخص نمودن عملکرد جواب ایفا می کند.

لذا ما اولین پدیده بر روی هر ماشین را بر اساس GA برنامه ریزی نمودیم و بقیه فعالیت ها را به جهت مقایسه بر اساس متدهای دیگری از قبیل NST,MWKR,SPT زمان بندی نمودیم.

مطابق با قاعده MWKR پدیده ای که دارای بیشترین زمان فرایند است ابتدا پروسه می شود در حالی که بر مبنای قاعده SPT پدیده ای که دارای کمترین زمان فرایند است ابتدا پروسه می شود، که با استفاده قوانین یاد شده تعداد حالت های ممکن برای جواب مسئله به nm کاهش می یابد.

رویهNST امکان جستجوی بیشتر را برای یافتن جواب بهتر برای ما فراهم می آورد.

که به طور اختصار مراحل الگوریتم ژنتیک ترکیبی را می توان به صورت زیر خلاصه کرد.

Begin K:=0; Initialize p(k); I*p(k) is the population of the Kth generation */ Calculate the fitness value (Cmax) of each individual in p(k); While (the termination criterion is not met) do Begin K=k+1; {for each schedule in p(k-1).generate the corresponding chromosome composed of the first operation on each machine, all of which constitute the set P׳(k-1);} Generate P’(k) from P’(k-1) by reproduction : Perform crossover on P’(k): perform mutation on P’(k) with different mutation rates according of the diversity of the population ;} {generate the succeeding operations on each machine with a heuristic rule (e.g.

SPT or MWKR) to construct the total schedule, all of which constitute the set P(k);} Calculate the fitness value of each individual in P(k);} End Choose the best individual as a seed, and start the NST procedure; End 4- نتایج محاسباتی: ما مسائلی را در ابعاد مختلف با الگوریتمهای متعدد بررسی نموده ایم که در جدول 1 لیست شده اند، و در جدول 2 نیز اثر بهبود دو روشGA-SPT-NST و GA-MWKR-NST را در دو وضعیت بهترین مقدار و مقدار میانگین با روش های SA وGA مقایسه نموده ایم.

همانطور که از جدول 1و2 مشخص است تقریبا در تمامی موارد می بینیم که نتیجه GA-MWKR-NST بر سایر رویکردها مقدم است.

همچنین سرعت همگرایی الگوریتم های GA-SPT-NST و GA-MWKR-NST نسبت به GA بسیار سریعتر می باشد به گونه ای که در حدود 20% تا 40% صرفه جویی در زمان محاسبات با استفاده از این دو روش نسبت به روش GA داریم.

پس بنابراین الگوریتم ژنتیک ترکیبی در حل مسائل با حجم زیاد، مزایای بیشتری را نسبت به الگوریتم ژنتیک عادی دارد به خصوص زمانی که الگوریتم ژنتیک را با قاعده MWKR ترکیب می کنیم میزان کارایی این روش نسبت به روشهای مطرح شده در بالا بسیار بهتر می باشد.

قابل ذکر است که در بخش عملیات ما الگوریتم خود را با زبان فرترن کد نموده و سپس مسئله در سه سطح 10*10 ، 15*15 و 20*20 مبتنی بر الگوریتمهای ترکیبی حل شده که متوسط زمان مورد نیاز برای هر کدام از مسائل به ترتیب برابر با 15، 30 و 60 دقیقه بوده ضمن اینکه تعداد مراحل 2000 سیر تکاملی جهت رسیدن به جواب مذکور انجام شده است.

منابع: http://ietehranshomal.persianblog.com الگوریتم های ژنتیک و کاربردهای آن ترجمه و تالیف : مهندس مهدی علیرضا