الگوریتم ژنتیک

دانلود پایان نامه

خواهند بود. برای توضیح بیشتر باید به این نکته اشاره کرد که چالش ها و راه حل هایی که در این خصوص وجود دارد برای صنایع مختلف، متفاوت بوده و در اینجا به چالش هایی که بعضی از صنایع کلیدی با آن مواجه هستند اشاره می گردد.
سازمان ها و شرکت هایی که از تکنولوژی پیشرفته استفاده می کنند، از لحاظ انعطاف پذیری زنجیره های تأمین خود پیشرو بوده و به طور مؤثر عمل کرده اند و دلیل آن نیز طول عمر کوتاه محصولات تولیدی آنان است که این امر انعطاف پذیری و پاسخگو بودن آنها را الزامی می سازد. در پایان عمر کوتاه یک محصول، ارزش این محصول به شدت کاهش می یابد و بنابراین به منظور حصول اطمینان از سودآوری آن، باید ارتباط تنگاتنگ و دقیقی از وضعیت عرضه و تقاضا و همچنین پاسخگویی عالی به مشتری و ارتباطات مؤثر در سراسر زنجیره تأمین وجود داشته باشد.
برون سپاری۳۱ اغلب در بخش صنایع تکنولوژی پیشرفته استفاده می گردد و زنجیره تأمین سازمان های این بخش که از تولید کنندگان قراردادی و سازمان هایی که عملیات لجستیکی و پشتیبانی را به عنوان نفر ثالث برای آن تولید کنندگان انجام می دهند، تشکیل شده است. بنابراین در این زنجیره عرضه که شبکه تنیده از ارائه کنندگان خدمات مختلف است، باید اطلاعات به هنگام در خصوص وضعیت عرضه و تقاضا به آنها داده شود. در این حالت عمل حیاتی برای سازمان حفظ مسئولیت عملیات کنترل در شبکه است، در حالی که عمده کارهای اجرایی را به پیمانکاران بیرون از سازمان محول کرده است. این روش موجب می گردد که سازمان به هنگام ضرورت، ارائه کنندگان خدمات را بدون اینکه خللی در شبکه زنجیره بوجود آید، تغییر دهد.
ایجاد جریان اطلاعات در سراسر شبکه تأمین به منظور ایجاد بینش در خصوص محصول و اجزای آن برای تمامی ارائه کنندگان خدمات و همچنین به منظور فراهم آوردن اطلاعات به هنگام برای مشتریان در خصوص وضعیت سفارشات آنان، امری ضروری است.
سازمان ها می توانند بر مبنای زمان واقعی و در آن واحد، به محض ورود سفارش ها از طریق اینترنت آنها را دریافت کرده و اطلاعات را به تمامی اعضای شبکه زنجیره تأمین ارائه کنند و همزمان در خصوص تأمین تقاضای واقعی مشتری فعالیت نمایند. علاوه بر این تأمین کنندگان خدمات با استفاده از این فرصت می توانند برنامه های آتی خود را پیش بینی کنند، به طوری که آنان می توانند به طور شایسته ای به برنامه ریزی ظرفیت خود بپردازند.
اطلاعـات دقیق در خصوص سـطح موجودی و ظرفیت ، برای مشتریان ایـن امکان را فراهم می سازد که در مورد تاریخ واقعی تحویل آگاهی یابند. سازمان های موفق و پیشرو به منظور ایجاد تعادل بین عرضه و تقاضا از قیمت گذاری پویا استفاده می کنند و فروش از طریق اینترنت این فرایند را تسهیل می سازد.
قیمت ها بر اساس سطح موجودی، ظرفیت تولید و باقیمانده عمر محصول مورد تعدیـل قرار می گیرد و مشتریان قادر خواهند بود قیمت ها را در زمان واقعی مقایسه کرده، از طریق اینترنت سفارش داده و از تاریخ دقیق تحویل محصول آگاهی یابند. برای مثال در صنعت خودروسازی یکی از عمده ترین چالش ها، تولید محصول مورد نیاز مشتری در یک چارچوب زمانی کوتاه است که بدین وسیله از افزایش سطح میزان موجودی محصولی که مورد درخواست مشتری نیست، جلوگیری گردد.
مسائل مشترک موجود در زنجیره عرضه در این صنعت شامل زمان های تأخیر طولانی و میزان سطح موجودی بالاست و حل این مسائل نیازمند یک زنجیره تأمین انعطاف پذیر است. برخلاف مدل فشاری۳۲ ، این صنعت باید به سمت مدل کششی۳۳ که تولید بر اساس تقاضای واقعی مشتری است حرکت کند و این مدل نیازمند یک زنجیره منعطف و مرتبط با یکدیگر است که در آن ارتباطات مناسب در سراسر اجزای عرضه کنندگان و تأمین کنندگان خدمات برقرار باشد. یک مدل کششی تقاضا ، قیمت گذاری پویا را تسهیل می سازد و درآمد از طریق قیمت های تعدیل شده که مبتنی بر تقاضای واقعی و ظرفیت قابل دسترس است می تواند بیشینه گردد ، یعنی خودروهای تولیدی در عرضه های با حجم کم ، بالاتر قیمت گذاری شده در مواقعی که ظرفیت عرضه بالاست پایین تر قیمت گذاری می گردند.
یک مدل کششی مبتنی بر قیمت گذاری پویا که از طریق یک زنجیره عرضه پاسخگو پشتیبانی می گردد ، می تواند منجر به کاهش زمان تأخیر گردیده و سطح بالای موجودی کالا را که در زنجیره تأمین وجود دارد ، حذف کند. یک زنجیره عرضه مؤثر می تواند تأثیر مستقیم بر روی قیمت سهام یک سازمان نیز داشته باشد.
با توجه به ساختار خطی موجود در زنجیره تأمین اغلب صنایع ، مشکلات موجود این ساختار عبارتند از :
تجمع خطاهای پیش بینی تقاضا در اثر تکرار عملیات پیش بینی در طول زنجیره تأمین توسط اعضا
عدم اطلاع از ظرفیت تأمین کنندگان
وجود زمان های تأمین۳۴ طولانی برای سفارش به عنوان انگیزه ای برای انباشتن ذخیره های اطمینان
هزینه های بالای سفارش دهی و حمل و نقل به عنوان انگیزه ای برای انباشت ذخیره های اطمینان
عدم اطلاع از تقاضاهای کاذب ایجاد شده بوسیله اعمال سیاست های تخفیف
تعدد نقاط تصمیم گیری در طول زنجیره تأمین
عدم اطلاع از الگوی واقعی تقاضای بازار مصرف

۲-۱۰- مسئله طراحی شبکه زنجیره تأمین۳۵
شبکه زنجیره تأمین امـکان ایجاد یـک بستر مؤثر و کارا برای مدیریت زنجیره تأمین را فراهم می کند. این شبکه مجموعه ای از تسهیلاتی است که در شکل گیری زنجیره تأمین نقش دارند. در این شبکه مجوعه ای از تأمین کنندگان مواد اولیه، کارخانه
های تولید محصولات، مراکز توزیع محصولات و مشتریان حضور دارند که هدف شبکه کمینه کردن کل هزینه های ایجاد چنین شبکه ای است، به گونه ای که به تقاضای مشتریان پاسخ داده شود. هزینه های موجود در شبکه به دو صورت می باشند که نوع اول شامل هزینه های ایجاد و احداث کارخانه ها و مراکز توزیع می باشد و نوع دوم شامل هزینه های خرید، تولید، توزیع و حمل و نقل کالا در هر مرحله از شبکه زنجیره تأمین است[۱۳].
در شکل زیر نمایی از یک شبکه زنجیره تأمین سه مرحله ای تک محصوله نمایش داده شده است :

شکل ۲-۱ شبکه زنجیره تأمین سه مرحله ای تک محصوله[۱۴]
Suppliers تأمین کنندگان مواد اولیه هستند که دارای ظرفیت مشخصی هستند و تعداد آنها نیز مشخص است. Plants کارخانه های تولید محصولات هستند که حداکثر تعداد قابل ایجاد برای آنها مشخص است و در مسئله یافتن اینکه کدام کارخانه ها بایستی ایجاد شوند تا به تقاضای مراکز توزیع با کمترین هزینه بتوانند پاسخ دهند، حائز اهمیت است. DC36 ها مراکز توزیع هستند که همانند کارخانه ها دارای محدودیت ایجاد هستند و باید در مسئله تعیین شوند و Customers مشتریان ما هستند که تقاضایشان غیرقطعی(فازی) است و تمامی محصولات خود را فقط از یک مرکز توزیع دریافت می کنند. شبکه ، نشان دهنده ی گره های S برای تأمین کنندگان مواد اولیه ، K بـرای کارخانه ها، J برای مراکز توزیع و I برای مشتریان است. کمان ها در شبکه نشان دهنده ارتباط بین گره ها می باشد و مسیر حمل و نقلی محصولات را مشخص می کنند.
مسائل MSCN Design از نوع مسائل Mixed-integer programming problems می باشند که در مقیـاس بزرگ قابـل حـل با الگوریتم هـای مشخص نیست و جـزو مسائل NP-Hard دسته بندی می گردد. از این رو برای حل این نوع از مسائل ، از الگوریتم های ابتـکاری و فرا ابتکاری استفاده می شود. یکی از روش های فرا ابتکاری موثر برای حل این نوع از مسائل، الگوریتم ژنتیک می باشد که به خوبی بارها برای این نوع مسائل پیاده سازی شده و نتایج خوبی حاصل شده است.
۲-۱۱- مروری بر الگوریتم ژنتیک
۲-۱۱-۱- مقدمه
الگوریتم ژنتیک۳۷ یکی از اعضای خانواده مدل های محاسباتی الهام گرفته شده از روند تکامل است. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیه آن از علم ژنتیک اقتباس گردیده است و با تقلید از فرایند های مشاهده شده در تکامل طبیعی ابداع شده است و به طور مؤثری از معرفت قدیمی موجود در یک جمعیت استفاده می کند تا حل های جدید و بهبود یافته را ایجاد کند.
در اواسط قرن بیستم برخی از دانشمندان علم کامپیوتر کار بر روی سیستم های تکاملی را به امید آنکه بتوان از آن به عنوان مکانیسمی برای حل مسائل بهینه سازی استفاده نمود، آغاز نمودند. GA اولین بار توسط جان هالند۳۸ و دانشجویان او در دانشگاه میشیگان ابداع شد و توسعه یافت. هدف اصلی این تیم خلق یک الگوریتم جدید نبود بلکه آنها به دنبال تشخیص دقیق نحوه وقوع تطابق در طبیعت و توسـعه راهی برای استفاده از رونـد انطباق طبیعی در سیستم های کامپیوتـری بودند. فعالیت های هالنـد در ایـن زمینه یک چارچوب کـلی بـرای الگوریتم هـای ژنتیک در جهت پیشرفت های آتی فراهم آورد[۲۱].
۲-۱۱-۲- مکانیسم الگوریتم ژنتیک
الگوریتم ژنتیک به عنوان یک الگوریتم محاسباتی بهینه سازی با در نظر گرفتن مجموعه ای از نقاط فضای جواب در هر تکرار محاسباتی، به نحو مؤثری نواحی مختلف فضای جواب را جستجو می کند. در مکانیسم جستجو گرچه مقدار تابع هدف تمام فضای جواب محاسبه نمی شود ولی مقدار محاسبه شده تابع هدف بـرای هر نقطه، در متوسط گیری آماری تابع هدف بـرای هر نقطه، در متوسط گیری آماری تابع هدف در کلیه زیر فضاهایی که آن نقطه بدان ها وابسته بوده، دخالت داده می شود و این زیر فضاها به طور موازی از نظر تابع هدف متوسط گیری آماری می شوند. این مکانیسم را توازی ضمنی۳۹ می گویند. این روند باعث می شود که جستجوی فضا به نواحی از آن که متوسط آماری تابع هدف در آنها زیاد بوده و امکان وجود نقطه بهینه مطلق در آنها بیشتر است، سوق پیدا کند. چون در این روش برخلاف روش های تک مسیری، فضای جواب به طور همه جانبه جستجو می شود، امکان کمتری برای همگرایی به یک نقطه بهینه محلی وجود خواهد داشت. امتیاز دیگر این الگوریتم آن است که هیچ محدودیتی برای تابع بهینه شونده، مثل مشتق پذیری یا پیوستگی لازم ندارد و در روند جستجوی خود، تنها به تعیین مقدار تابع هدف در نقاط مختلف نیاز دارد و هیچ اطلاعات کمکی دیگری مثل مشتق تابع را استفاده نمی کند. لـذا می توان در مسائل مختلف اعـم از خطی ، غیر خطی، پیوسته یا گسسته از آن استفاده نمود.
در هر تکرار هر یک از رشته های موجود در جمعیت رشته ها، رمزگشایی شده و مقدار تابع هدف برای آن بدست می آید. بر اساس مقادیر بدست آمده تابع هدف در جمعیت رشته ها، به هر رشته یک عدد برازندگی نسبت داده می شود. این عدد برازندگی احتمال انتخاب را برای هر رشته تعیین خواهد کرد. بر اساس این احتمال انتخاب، مجموعه ای از رشته ها انتخاب شده و با اعمال عملگرهای ژنتیکی روی آنها رشته های جدید جایگزین رشته هایی از جمعیت اولیه می شوند تا تعداد جمعیت رشته ها در تکرار های محاسباتی مختلف ثابت باشد.
مکانیسم های تصادفی که روی انتخاب و حذف رشته ها عمل می کنند به گونه ای هستند که رشته هایی که عدد برازندگی بیشتری دارند، احتمال بیشتری برای ترکیب و تولید رشته های جدید داشته و در مرحله جایگزینی نسبت به دیگر رشته ها مقاوم تر هستند. بدین لحاظ جمعیت دنباله ها
در یک رقابت بر اساس تابع هدف در طی نسل های مختلف، کامل شده و متوسط مقدار تابع هدف در جمعیت رشته ها افزایش می یابد.
به طور کلی در این الگوریتم ضمن آن که در هر تکرار محاسباتی، توسط عملگرهای ژنتیکی نقاطی جدید از فضای جواب مورد جستجو قرار می گیرند توسط مکانیسم انتخاب، روند جستجو نواحی ای از فضا را که متوسط آماری تابع هدف در آنها بیشتر است را کنکاش می کند. بر اساس این سیکل اجرایی در هر تکرار محاسباتی، سه عملگر اصلی روی رشته ها عمل می کند. این سه عملگر عبارتند از دو عملگر ژنتیکی و عملگر انتخاب تصادفی[۱].
گلدبرگ۴۰ الگوریتم ژنتیکی هالند را با عنوان الگوریتم ژنتیکی ساده۴۱ معرفی می کند[۲۲].

بدن همه موجودات زنده از سلول ها تشکیل شده است و در هر سلولی دسته کروموزوم۴۲ های یکسانی وجود دارد. کروموزوم ها رشته هایی از DNA هستند که در واقع الگویی برای تمام بدن هستند. هر کروموزومی محتوی دسته هایی DNA است که ژن نامیده می شوند و هر ژنی پروتئین خاصی را رمزگذاری می کند. اساسا می توان گفت که هر ژن، ویژگی خاصی (مثلا رنگ چشم) را رمزگذاری می کند. حالت های مختلف یک خصیصه (آبی، قهوه ای) آلل۴۳ نامیده می شود. هر ژنی موقعیت خاص خود را بر روی کروموزوم دارد که این موقعیت لوکاس۴۴ نامیده می شود. مجموعه کاملی از مواد ژنتیکی (همه کروموزوم ها) ژنوم نامیده می شود. دسته خاصی از ژن های موجود در ژنوم، ژنوتیپ نامیده می شود. ژنوتیپ به همراه تغییرات پس از تولد، پایه و اساس فنوتیپ موجود زنده (ارگانیسم) ، ویژگی های فیزیکی و ذهنی از قبیل رنگ چشم و هوش و غیره است.
در تولید مثل، ابتدا ترکیب۴۵ یا ادغام اتفاق می افتد. ژن های والدین برای ایجاد کروموزوم های جدید ترکیب می شوند. سپس جنین تشکیل شده دچار تغییر می شود. جهش به این معناست که عناصر DNA کمی تغییر پیدا کند و این تغییرات اغلب نتیجه نسخه برداری غلط از ژن های والدین است. میزان برازندگی۴۶ موجود زنده (جنین) به واسطه بقای آن اندازه گیری می شود.
در الگوریتم ژنتیک، مجموعه ای از متغیرهای طراحی را توسط رشته هایی با طول ثابت۴۷ یا متغیر۴۸ کدگذاری می کنند که در سیستم های بیولوژیکی آنها را کروموزوم یا فرد۴۹ می نامند.
هر رشته یک نقطه پاسخ در فضای جستجو را نشان می دهد. به ساختمان رشته ها یعنی مجموعه ای از پارامترها که توسط یک کروموزوم خاص نمایش داده می شود ژنوتیپ۵۰ و به مقدار رمزگشایی شده آن فنوتیپ۵۱ می گویند. الگوریتم های

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

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