بخشی از مقاله
چکیده :
زمان بندی برای تولید کارگاهی (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 ارزیابی جوابهای بدست آمده در هر مرحله است. در واقع ارزش جوابهای بدست آمده در هر مرحله تعیین می شود.مناسب بودن یا نبودن جواب با معیاری که از تابع هدف بدست می آید ، سنجیده می شود.هر چه که یک جواب مناسب تر باشد ، مقدار برازندگی بیشتری دارد که با استفاده از
محدوده دانش مسئله به کار برده شده محاسبه می شود.برای آنکه شانس بقای چنین جوابی بیشتر شود احتمال بقای آن متناسب با مقدار برازندگی آن در نظر گرفته می شود.بنابراین رشته ای که برازنده تر است با احتمال بیشتری در تولید فرزندان شرکت می کند و دنباله های بیشتری را بوجود می آورد. با ارزشترین جوابها درهرمرحله ، مانند قویترین موجودات در یک جمعیت می باشند.در تکثیر، رشته های با میزان تطبیق کم ، از جمعیت حذف می شوند و رشته های با میزان تطبیق زیاد، تاثیر بیشتری در تولید جمعیت بعدی خواهند داشت.
معمولا در مواردی که امکان دارد، تابع برازندگی را در فاصله (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 مجموعه ای از رشته ها برای دور محاسباتی بعد با تعدادی برابر جمعیت اولیه تعیین می شوند. این مجموعه تشکیل شده از کلیه رشته های فرزند ( حاصل از عملگرهای ترکیب و جهش) و تعدادی از رشته های مرحله قبل می باشد.انتخاب این تعداد از رشته های اولیه بطور تصادفی از بین رشته های عدد برازندگی بالاتر انجام می شود ، این مرحله را تکثیر می گویند.
گلدبرگ روش چرخ گردان را برای تکثیر ارائه داد. دراین روش یک چرخ که سطح آن متناسب با برازندگی هر رشته تقسیم بندی شده است ، در مقابل یک نشانه می چرخد تا بالاخره متوقف شود و یکی از سطوح در مقابل نشانه قرار گیرد. به این ترتیب یک رشته انتخاب می شود ، اگر برازندگی رشته زیاد باشد شانس آن برای انتخاب شدن بیشتر است و برعکس.
بنابراین با تکرار به دفعات مناسب می توان رشته های لازم برای اعمال عملگرهای ژنتیک را انتخاب نمود (تکثیر یا تکرار). این نوع انتخاب (تکثیر) بر اسا س ارزیابی میزان برازندگی یک رشته نسبت به بقیه رشته ها و استفاده ازعنصر تصادف است.
در شبيه سازي كامپيوتري مي توان برازندگي نسبي تجمعي را به دست آورد و با انتخاب يك عدد تصادفي و تعيين محدوده اي كه اين عدد در آن قرار دارد،رشته مورد نظر را انتخاب كرد.
