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

{ ∀(o,o′) ϵ Ni , ∀i , j≠j′ }
3-4- مدل ریاضی


Widget not in any sidebars

S.T

4-4- تشریح مدل
در (1) تابع هدف مدل ارائه شده است که در آن ما به دنبال حداقل کردن زمان تکمیل همه کارها هستیم.
محدودیتهای شماره (2) و (3) به ترتیب تضمین میکنند که هر قطعه تنها به یک سلول میتواند اختصاص یابد و اینکه به هر سلول میبایست حداقل یک قطعه تخصیص پیدا کند.
محدویت شماره (4) باعث میشود قطعه به سلولی اختصاص یابد که اولین عملیات آن توسط یکی از ماشینهای اختصاص یافته با آن سلول پردازش شود.
محدودیت شماره (5) بیان میکند که هر ماشین میبایست فقط به یک سلول نسبت داده شود.
محدودیتهای شماره (6) و (7) مانع از این میشود که تعداد ماشینهای موجود در هر سلول از محدوده حداقل و حداکثر تعداد ماشین مجاز در هر سلول خارج شود.
محدودیت شماره (8) هر ماشین را در یکی از موقعیتهای ممکن در سلول اختصاص یافته به آن ماشین قرار میدهد. به عبارت دیگر استقرار هر ماشین تنها در موقعیتهایی مجاز است که مربوطه به سلول انتخابی برای حضور آن ماشین هستند و نه سلولهای دیگر.
محدودیت شماره (9) از اختصاص بیش از یک ماشین به هر موقعیت از هر سلول ممانعت مینماید.
محدودیت (10) اشاره دارد که هر ماشین باید تنها در یکی از موقعیتهای یک سلول قرار گیرد.
محدودیت شماره (11) زمان جابجایی بین سلولی و درون سلولی را محاسبه میکند.
محدودیت شماره (12) تاکید میکند که عملیاتهای هر قطعه مطابق توالی عملیاتهای مورد نیاز انجام میگیرند.
محدودیتهای (13) و (14) تضمین میکند که هر ماشین در یک لحظه نمیتواند بیش از یک قطعه را پردازش کند.
محدودیت (15) تضمین میکند که زمان تکمیل عملیات o قطعه j بزرگتر مساوی زمان پردازش این عملیات است.
محدودیت (16) زمان تکمیل کار قطعه j را محاسبه میکندو در نهایت محدودیت (17) مشخص میکند که متغیرهای تصمیم ما باینری هستند.
3-2- روش حل با استفاده از الگوریتم ژنتیک
3-2-1- آشنایی با الگوریتم ژنتیک
3-2-1-1- مقدمه
الگوریتم ژنتیک یک روش آماری برای بهینه سازی و جستجو است. الگوریتم ژنتیک جزئی از محاسبات تکاملی است که خود جزئی از هوش مصنوعی میباشد. ویژگیهای خاص این الگوریتم باعث میشود که نتوانیم آن را یک جستجوگر تصادفی ساده قلمداد کنیم. در واقع ایده اولیه این روش از نظریه تکاملی داروین (1859) الهام گرفته شده است و کارکرد آن بر اساس ژنتیک طبیعی استوار میباشد. نظریه تکاملی داروین بدین صورت است که آن دسته از صفات طبیعی که با قوانین طبیعی سازگاری بیشتری دارند، شانس بقاء بیشتری دارند.
ایده محاسبات تکاملی اولین بار در سال ١٩۶٠ توسط رچنبرگ که در زمینه استراتژیهای تکاملی تحقیق میکرد بوجود آمد که نظریه او بعدها توسط دیگر محققان توسعه داده شد. اصول اولیه الگوریتم ژنتیک توسط هلند و همکارانش در دانشگاه میشیگان در سال ١٩۶٢ ارائه شد. آنان در تحقیقات خود به فرایند سازگاری در سیستم های طبیعی توجه نمودند و برای مدل سازی آن در سیستم های مصنوعی که باید دارای توانایی های اصلی سیستم های طبیعی باشند، تلاش نمودند. نتیجه این تلاشها، پیدایش الگوریتم ژنتیک بود. سپس در سال ١٩٧۵، مبانی ریاضی آن در کتابی توسط هلند با نام «تطابق در سیستمهای طبیعی و مصنوعی» منتشر شد. ودر سال 1989 کاربرد آن با انتشار کتابی توسط گلدبرگ تسریع یافت. در سال ١٩٩٢، جان کوزا الگوریتم ژنتیک را به منظور انجام وظایف خاصی در برنامههایش بکار برد. او این روش را برنامه ریزی تکاملی نامید. در برنامه ریزی تکاملی، هدف پیدا کردن الگوریتمی است که بتواند جواب هر صورت مسالهای را پیدا کند. در این روش باید برای الگوریتمها مطلوبیت تعریف کرد تا فهمیده شود که کدام الگوریتم بهتر است.