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

همه کارها در لحظه صفر در دسترس نیستند.
ماشینها در تمام زمانها در دسترس هستند.
حداقل دو ماشین در کارگاه وجود دارد که غیرمرتبط هستند.
بین کارها زمان آمادهسازی وجود دارد.
3-2-1-2. پارامتر ها و متغیر های مساله
j : اندیس کار
i: اندیس ماشین
k: اندیس موقیعت روی ماشین
l: اندیس واحد کار
P_ij: زمان پردازش کار jام روی ماشین iام
C_j: زمان تکمیل کار j
C_ikjl: زمان تکمیل واحد lام از کار j که در موقیعت kام روی ماشین i قرار دارد
S_ij’j: زمان آمادهسازی بین کارها
R_j: زمان در دسترس قرار گرفتن کار j
L_j: زمان دیرکرد کار j
D_j: موعد تحویل
n_j: تعداد زیرکارهای هر کار
M: مقداری بزرگ
C_max: بزرگترین زمان تکمیل
l_max: بزرگترین زمان دیرکرد
X_ikjl: اگر lاُمین واحد از کار j روی موقعیت kاُم ماشین i باشد “یک” است و در غیر اینصورت “صفر” است.
3-2-1-3. توابع هدف
برای این مساله از دو هدف استفاده شده است. هدف اول که از نظر اولویت نیز در رتبه بالاتری قرار دارد حداقلسازی بزرگترین زمان تکمیل است. هدف دوم مربوط به دیرکرد و در ارتباط با موعد تحویل است. این هدف با حداقلسازی بیشترین زمان دیرکرد مشخص میشود. اهداف در زیر مشخص شده اند.
min⁡〖z_1 〗=C_max
min z_2=L_max
3-2-1-4. محدودیتهای مساله
محدودیت (1): این محدودیت مشخص میکند که هر واحد از هر کار تنها در یک موقیعت از هر ماشین میتواند پردازش شود.

∑_i▒∑_k▒〖x_ikjl=1〗 ∀ j،l1
محدودیت (2): در این محدودیت داریم هر موقیعت از هر ماشین تنها به یک واحد از یک کار میتواند تخصیص یابد.

∑_j▒∑_l▒〖x_ikjl≤1〗 ∀ i،k2
محدودیت (3): این محدودیت بیان میکند مجموع واحدهای کارها که در موقیعتهای مختلف قرار میگیرند برابر کل تعداد واحدها است.

∑_i▒∑_l▒〖∑_k▒〖x_ikjl=n_j 〗 〗 ∀ j3
محدودیت (4): این محدودیت واحدهای کوچکتر را به ازای هر کار ملزم میدارد که در موقیعتهای کوچکتر قرار گیرند تا توالی بین واحدهای کار رعایت گردد.

x_ikjl-∑_(i^’)▒∑_(k^’)▒x_(i^’ k^’ j(l-1)) >0 ∀ i، j،l≥2،k،k^'<k4 محدودیت (5): زمان پردازش هر جزء از کار از تقسیم کل زمان پردازش هر کار بروی تعداد واحدهای آن کار بدست میآید.

p_ijl=p_ij/n_j ∀ i،j5
محدودیت (6): زمان تکمیل lاُمین واحد از کار j باید بزرگتر از زمان تکمیل واحد قبلی آن باشد.
c_ikjl≥c_(i^’ k^’ j(l-1))+p_ijl+s_(ij^’ j)-[(2-x_(i^’ k^’ j(l-1))-x_ikjl )×M]∀ i،i^’،j،j^’،k،k^’، l≥26
محدودیت (7): زمان تکمیل واحدهایی که در موقیعتهای پایینتر هر ماشین هستند باید کوچکتر از زمان تکمیل واحدهایی باشد که در موقیعتهای بالاتر قرار دارند.

c_ikjl≥c_(i〖k^’ j〗^’ l^’ )+p_ijl+s_(ij^’ j)-[(2-x_ikjl-x_(i〖k^’ j〗^’ l^’ ) )×M]∀ i،j،j^’، l〖،l〗^’،k≥2،k^'<k7
محدودیت (8): زمان تکمیل اولین واحد از هر کار از مجموع زمان دردسترس قرار گرفتن کار و زمان پردازش واحد آن کار بدست می آید.

c_ikj(l=1) ≥p_(ij(l=1))+R_j-[(1-x_(ikj(l=1)) )×M]∀ i، j ،k8
محدودیت (9): زمان تکمیل فقط برای حالتی محاسبه میگردد که واحدی از کار در موقعیتی از ماشین قرار گرفته باشد.

c_ikjl≤x_ikjl×M∀ i ،j، l،k9
محدودیت (10) : زمان تکمیل هر کار بزرگتر از زمان تکمیل هر جزء آن است.

c_j≥c_ikjl∀ i ،j، l،k10
محدودیت (11) و (12) : حداکثر زمان تکمیل و حداکثر دیرکرد و نحوه محاسبه آن را نشان میدهد.
L_max≥(c_j-D_j )∀ j11C_max≥c_j∀ j12
3-2-1-5. مدل مساله

توابع هدفmin z_1=C_maxmin z_2=L_maxمحدودیت ها∑_i▒∑_k▒〖x_ikjl=1〗 ∀ j،l1∑_j▒∑_l▒〖x_ikjl≤1〗 ∀ i،k2∑_i▒∑_l▒〖∑_k▒〖x_ikjl=n_j 〗 〗 ∀ j3x_ikjl-∑_(i^’)▒∑_(k^’)▒x_(i^’ k^’ j(l-1)) >0 ∀ i، j،l≥2،k،k^'<k4p_ijl=p_ij/n_j ∀ i،j5c_ikjl≥c_(i^’ k^’ j(l-1))+p_ijl+s_(ij^’ j)-[(2-x_(i^’ k^’ j(l-1))-x_ikjl )×M]∀ i،i^’،j،j^’،k،k^’، l≥26c_ikjl≥c_(i〖k^’ j〗^’ l^’ )+p_ijl+s_(ij^’ j)-[(2-x_ikjl-x_(i〖k^’ j〗^’ l^’ ) )×M]∀ i،j،j^’، l〖،l〗^’،k≥2،k^'<k7c_ikj(l=1) ≥p_(ij(l=1))+R_j-[(1-x_(ikj(l=1)) )×M]∀ i، j ،k8c_ikjl≤x_ikjl×M∀ i ،j، l،k9c_j≥c_ikjl∀ i ،j، l،k10L_max≥(c_j-D_j )∀ j11C_max≥c_j∀ j12متغیر هاx_ikjl ∈ {0،1}

3-2-1-6. اعتبارسنجی مدل
برای اطمینان از قابل اطمینان بودن جوابهای خروجی مدل از یک مثال با دو ماشین، 4 کار، که هر کار دارای دو واحد کاری میباشد استفاده کردهایم. هر ماشین 8 موقیعت کار ( با این فرض که تمام کارها بروی یک ماشین صورت گیرد، موقیعت ماشین ایجاد میکنیم پس 8 موقیعت بروی هر ماشین خواهیم داشت). اطلاعات مساله در زیر نشان داده شده است و همچنین نتیجه گانت چارتی حاصل از خروجی مدل ریاضی در ادامه آورده شده است.

4321شماره کارهااطلاعات مساله14321ماشنزمان های پردازش3224221ماشینزمان های آماده سازی1221ماشینتعداد واحدهای کار24200زمان در دسترس قرار گرفتن کارها6522موعد تحویل کارها پس کدنویسی و اجرای مساله در نرم افزار GAMS و روی یک لپتاپ با مشخصات Intel®Core i7 2.00GHz 8.00GB RAM &و با سیستم عامل ویندوز 7، 64 بیتی اجرا شده است. جواب زیر حاصل شده است که نمای شماتیک آن در زیر آمده است. مدل با ابعاد بزرگتر نیز مورد برازش قرار گرفته است که نتایج آن در پیوست ارائه شده است.

3-2-2.روش های فرا ابتکاری
یک روش ناشیانه برای حل مسائل بهینه‌سازی ترکیبی این است که تمامی جواب‌های امکان‌پذیر در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهایت، بهترین جواب انتخاب گردد. روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منتهی می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن غیرممکن است. با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده است که مشهورترین نمونه آنها، روش سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کرانه برای حل برنامه‌های خطی با متغیرهای صحیح است. برای مسائلی با ابعاد بزرگ، روش سیمپلکس از کارایی بسیار خوبی برخوردار است، ولی روش شاخه و حد کارایی خود را از دست می‌دهد و عملکرد بهتری از شمارش کامل نخواهد داشت. به دلایل فوق، اخیراً تمرکز بیشتری بر روش‌های ابتکاری (Heuristic) یا فرا ابتکاری (Metaheuristic) یا جستجوی تصادفی (Random Method) صورت گرفته است. روش‌های جستجوی ابتکاری، روش‌هایی هستند که می‌توانند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کنند. روش‌های جستجوی ابتکاری عمدتاً بر مبنای روش‌های شمارشی می‌باشند، با این تفاوت که از اطلاعات اضافی برای هدایت جستجو استفاده می‌کنند. این روش‌ها از نظر حوزه کاربرد، کاملاً عمومی هستند و می‌توانند مسائل خیلی پیچیده را حل کنند. عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند.
3-2-2-1. الگوریتم مورچگان
3-2-2-1-1. مقدمه
الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه ها است. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه‌ها دارای نوعی هوشمندی توده‌ای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه‌ها ابتدا به طور تصادفی به این سو و آن سو می‌روند تا غذا بیابند. سپس به لانه بر می‌گردند و ردّی از فرومون38 به جا می‌گذارند. چنین ردهایی پس از باران به رنگ سفید در می‌آیند و قابل رویتاند. مورچه‌های دیگر وقتی این مسیر را می‌یابند، گاه پرسه زدن را رها کرده و آن را دنبال می‌کنند. سپس اگر به غذا برسند به خانه بر می‌گردند و رد دیگری از خود در کنار رد قبل می‌گذارند و به عبارتی مسیر قبل را تقویت می‌کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:
باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه‌های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر (بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر.
اگر فرومون اصلاً تبخیر نمی‌شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.
وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.
لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیه مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر، به مرور همه مورچه‌ها هم مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی است که روی نمودار در حال حرکت اند. مساله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی اند.

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

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

تبخیر شدن فرومون و احتمال تصادف به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینهسازی می‌شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره‌ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره‌ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه‌ها می‌توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.
3-2-2-1-2. مزیتهای ACO
همانطور که گقته شد «تبخیر شدن فرومون» و «احتمال تصادف» به مورچه ها امکان پیدا کردن کوتاهترین مسیر را می دهند. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه سازی می شوند. مثلا در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه ها می توانند پس از مدت کوتاهی مسیر بهینه(کوتاهترین) را بیابند.
3-2-2-1-3. کاربردهای ACO
از کاربردهایACO می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد ، اشاره نمود :
مسیر یابی داخل شهری و بین شهری
مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا
مسیر یابی شبکه های کامپیوتری
3-2-2-1-4. الگوریتم ACO
برای پیاده سازی کلونی مورچه، از مورچه های مصنوعی به عنوان عناصری در بهینه سازی استفاده می شود. البته این عناصر تفاوتهای اساسی با مورچه های واقعی دارند که عبارتند از:
حافظه: برای مورچه های مصنوعی می توان یک حافظه در نظر گرفت که مسیرهای حرکت را در خود نگه می دارند.
موانع ساختگی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جوابهای متنوع.
حیات در محیط گسسته: مورچههای واقعی نمیتوانند جدا از کلونی به حیات خود ادامه دهند.
توجه به کولونی مورچه‌ها و نیز استفاده وسیع ازآن بیشتر ناشی از توجه خاصی بوده که پیشتر، بیولوژیست‌ها به کولونی مورچه‌ها داشته‌اند. چه بسا سیستم‌های دیگر طبیعی نیز باشند که تاکنون مورد مطالعه قرار نگرفته‌اند یا اگرهم مطالعه شده‌اند با دید معطوف به هوشمندی و بهینه‌سازی نبوده است.
   بنابراین می‌توان تصور کرد که در سال‌های آینده روش‌های زیاد دیگری جهت بهینه‌سازی و نیز کنترل هوشمند با استفاده از سیستم‌های طبیعی پیشنهاد شوند . تا به حال به کرات به مزایای این نوع هوشمندی اشاره کرده‌ایم اما اکنون بار دیگر تأکید می‌کنیم که این نوع از هوشمندی علاوه بر تمامی مزایای مهندسی، یک مزیت عمده و اصلی دارد: تمامی این روش‌ها قابلیت تعمق زیستی39 دارند به این معنی که طبیعت آنها را در طی میلیون‌ها سال به عنوان روش بهینه انتخاب کرده است.
3-2-2-2. الگوریتم ژنتیک
3-2-2-2-1. مقدمه
محدوده کاری الگوریتم ژنتیک بسیار وسیع میباشد و هر روز با پیشرفت روز افزون علوم و تکنولوژی استفاده از این روش در بهینهسازی و حل مسائل بسیار گسترش یافته است. الگوریتم ژنتیک یکی از زیر مجموعههای محاسبات تکامل یافته می باشد که رابطه مستقیمی با مبحث هوش مصنوعی دارد در واقع الگوریتم ژنتیک یکی از زیر مجموعههای هوش مصنوعی می باشد. الگوریتم ژنتیک را میتوان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید میکند. الگوریتم ژنتیک برروی یکسری از جوابهای مساله به امید بدست آوردن جوابهای بهتر قانون بقای بهترین را اعمال میکند. درهر نسل به کمک فرآیند انتخابی متناسب با ارزش جوابها و تولید مثل جوابهای انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شدهاند، تقریبهای بهتری از جواب نهایی بدست میآید. این فرایند باعث میشود که نسلهای جدید با شرایط مساله سازگارتر باشد.
الگوریتم ژنتیک (Genetic Algorithm – GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.
الگوریتم ژنتیک که به ‌عنوان یکی از روشهای تصادفی بهینهیابی شناخته شده، توسط جان هالند در سال ۱۹۶۷ ابداع شده ‌است. بعدها این روش با تلاشهای گلدبرگ 1989، مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش، جای مناسبی در میان دیگر روشها دارد. الگوریتمهای ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونه انتزاعی (کروموزومها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی می‌شوند. به طور سنتی راه‌حلها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند. فرضیه با جمعیتی کاملاً تصادفی منحصربفرد آغاز می‌شود و در نسلها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی می‌شود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب می‌شوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح می‌شوند (کسر یا دوباره ترکیب می‌شوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل می‌شود.
3-2-2-2-2. ساختار الگوریتم ژنتیک
کروموزوم40
در الگوریتم‏های ژنتیکی، هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک راه‏حل ممکن برای مسئله مورد نظر است. خود کروموزوم‏ها (راه حل‏ها) از تعداد ثابتی ژن41 (متغیر) تشکیل می‏شوند. برای نمایش کروموزوم‏ها، معمولاً از کدگذاری‏های دودویی (رشته‏های بیتی) استفاده می‏شود.
جمعیت42
مجموعه‏ای از کروموزوم‏ها یک جمعیت را تشکیل می‏دهند. با تاثیر عملگرهای ژنتیکی بر روی هر جمعیت، جمعیت جدیدی با همان تعداد کروموزوم تشکیل می‏شود.
تابع برازندگی43
به منظور حل هر مسئله با استفاده از الگوریتم‏های ژنتیکی، ابتدا باید یک تابع برازندگی برای آن مسئله ابداع شود. برای هر کروموزوم، این تابع عددی غیر منفی را برمی‏گرداند که نشان دهنده شایستگی یا توانایی فردی آن کروموزوم است.
3-2-2-2-3. عملگرهای الگوریتم ژنتیک
در الگوریتم‏های ژنتیکی، در طی مرحله تولید مثل44 ازعملگرهای ژنتیکی استفاده می‏شود. با تاثیر این عملگرها بر روی یک جمعیت، نسل45 بعدی آن جمعیت تولید می‏شود. عملگرهای انتخاب46 ، آمیزش47 و جهش48 معمولاً بیشترین کاربرد را در الگوریتم‏های ژنتیکی دارند.
عملگر انتخاب (Selection)
این عملگر از بین کروموزوم‏های موجود در یک جمعیت، تعدادی کروموزوم را برای تولید مثل انتخاب می‏کند. کروموزوم‏های برازنده‏تر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند.
روش های انتخاب :
انتخاب نخبگان (Elitist Selection)
مناسب‌ترین عضو هر اجتماع انتخاب می‌شود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
نمونه‏برداری به روش چرخ رولت
در این روش، به هر فرد قطعه‏ای از یک چرخ رولت مدور اختصاص داده می‏شود. اندازه این قطعه متناسب با برازندگی آن فرد است. چرخ N بار چرخانده می‏شود که N تعداد افراد در جمعیت است. در هر چرخش، فرد زیر نشانگر چرخ انتخاب می‏شود و در مخزن والدین نسل بعد قرار می‏گیرد. این روش می‏تواند به صورت زیر پیاده‏سازی شود:
نرخ انتظار کل افراد جمعیت را جمع کنید و حاصل آن را T بنامید.
مراحل زیر را N بار تکرار کنید:
یک عدد تصادفی r بین 0 و T انتخاب کنید.
در میان افراد جمعیت بگردید و نرخ‏های انتظار( مقدار شایستگی) آنها را با هم جمع کنید تا این که مجموع بزرگتر یا مساوی r شود. فردی که نرخ انتظارش باعث بیشتر شدن جمع از این حد می‏شود، به عنوان فرد برگزیده انتخاب می‏شود.

انتخاب تورنومنت (Tournament Selection)
یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیر‌گروه برای تولید انتخاب می‌شوند.
عملگر آمیزش (Crossover)
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزومها با یکدیگر تعویض می شوند. این موضوع باعث میشود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. هدف تولید فرزند جدید میباشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب میکنیم
ژن های مابعد آن نقطه از کروموزومها را جابجا میکنیم
تلفیق تک نقطه ای (Single Point Crossover)
اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطهای می گویند. تلفیق بدین صورت انجام میگیرد که حاصل ترکیب کروموزومهای پدر و مادر میباشد. روش تولید مثل نیز بدین صورت است که ابتدا بصورت تصادفی، نقطهای که قرار است تولید مثل از آنجا آغاز گردد، انتخاب میگردد. سپس اعداد بعد از آن به ترتیب از بیتهای کروموزومهای پدر و مادر قرار میگیرد که در شکل زیر نیز نشان داده شده است.

در شکل بالا کروموزومهای 1 و2 در نقش والدین هستند و حاصل تولید مثل آنها در رشتههائی بنام Offspring ذخیره شده است. دقت شود که علامت “|” مربوط به نقطه شروع تولید مثل میباشد و در رشتههای Offspring اعدادی که بعد از نقطه شروع تولید مثل قرار میگیرند مربوط به کروموزومهای مربوط به خود می باشند. بطوریکه اعداد بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کرومکوزوم 1 و اعداد بعد از نقطه شروع تولید مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع تولید مثل مربوط به کروموزوم 2 میباشند
روش ادغام دو نقطه ای(Two-point CrossOver)
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.

تلفیق نقطه ای (Multipoint Crossover)
میتوانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطهای میگویند
.تلفیق جامع (Uniform Crossover)
اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع میگوئیم.

عملگر جهش (Mutation)
پس از اتمام عمل آمیزش، عملگر جهش بر روی کروموزوم‏ها اثر داده می‏شود. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر می‏دهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل می‏کند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار می‏دهد. در شکل (6) چگونگی جهش یافتن پنجمین ژن یک کروموزوم نشان داده شده است.
پس از اتمام عمل جهش، کروموزوم‏های تولید شده به عنوان نسل جدید شناخته شده و برای دور بعد اجرای الگوریتم ارسال می‏شوند.

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

3-2-2-2-5. شرط پایان الگوریتم

دسته بندی : پایان نامه ارشد

پاسخ دهید