حقیقی، کدگذاری، همگرایی، دودویی، پروسه، CAPP

، جابجایی تک نقطه ای (Single Point) است. در جابجایی تک نقطه ای، ابتدا جفت کروموزوم والد (رشته دودویی) در نقطه مناسبی در طول رشته بریده شده و سپس قسمت های بعد از نقطه برش، با هم عوض می شوند. بدین ترتیب دو کروموزوم جدید به دست می آید که هرکدام از آن ها ژن هایی را از کروموزوم های والد به ارث می برند.
برای جابجایی چندنقطه ای m موقعیت جابجا شدن، ، که نقطه جابجایی و l طول کروموزوم می باشد، را به صورت تصادفی و بدون تکرار انتخاب می کنیم. سپس جهت ایجاد فرزندی جدید بیت های بین نقاط مشخص شده در والدین با هم عوض می شوند.
به هر بیت از رشته کروموزوم ها یک آلل (Allele) گفته می شود. بخش بین اولین آلل تا اولین نقطه قطع، بین والدین جابجا نمی شود. این عملیات در شکل نشان داده شده است. فلسفه انجام جابجایی در چند نقطه و البته حالت های مختلف دیگر عملگر جابجایی این است که، قسمت هایی از کروموزوم که بیان کننده سهم به سزائی در عملکرد بهتر یک عضو خاص هستند ممکن است در زیر رشته های همسایه یافت نشوند.
به نظر می رسد نحوه عملکرد عملگر جابجایی در چند نقطه (Multipoint Crossover) نسبت به روش همگرایی به مقادیر بالاتر برازندگی به پیشرفت و توسعه جستجو در فضای داده های مربوطه بیشتر کمک می کند، لذا جستجو در دامنه جواب قوی تر می شود.
یانگ عملگر جابجایی چند نقطه را مورد بررسی قرار داده و ثابت کرد که عملگر جابجایی دو نقطه بهتر از تک نقطه بوده و همچنین اضافه کردن نقاط جابجایی بیشتر، عملکرد الگوریتم ژنتیک را کاهش می دهد.
عملگرهای جابجایی یک نقطه ای و چندنقطه ای در جایی اثر می کنند که کروموزوم دقیقاً در آن نقاط فقط می تواند جدا شود، اما عملگر جابجایی یکنواخت پتانسیل جابجاشوندگی را به تمام نقاط یک کروموزوم به صورت یکنواخت نسبت می دهد. به این معنی که احتمال جابجا شدن کروموزوم در هر نقطه برابر خواهد بود. یک الگوی بیان کننده عمل جابجایی (به همان طولی که کروموزوم ها دارند) به صورت تصادفی ایجاد می شود و مقدار تعیین شده در هر بیت از این نمونه نشان می دهد که کدام یک از والدین به عنوان مرجع مقداردهی برای آن بیت از فرزند خواهد بود. تعداد نقاط برش ثابت نیست ولی به طور متوسط برابر است.
دو کروموزوم اولیه (والدین) و الگوی عملگر جابجایی و فرزندان حاصل را در نظر بگیرید.

در اینجا مشاهده می شود که فرزند اول بدین صورت ایجاد شده است که اگر بیت مربوط در الگوی جابجایی (mask) 1 باشد مقدار آن بیت در برابر با مقدار بیت متناظر در و همچنین اگر بیت مربوط در الگوی جابجایی 0 باشد مقدار آن بیت در برابر با مقدار بیت متناظر در است.
رشته با جابجا کردن و و در نظر گرفتن همین شیوه ایجاد شده است یعنی مقدار 1 در رشته mask به معنی مقدار بیت متناظر در برای همان بیت در است.
مشخصاً عملگر جابجایی یکنواخت همانند عملگر جابجایی چند نقطه ای باعش کاهش خطای همگرایی، ناشی از طول باینری استفاده شده و نوع کد کردن سری پارامترهای داده شده، می شود. این مسأله کمک می کند گه بر خطای همگرایی موجود در حالت جابجایی تک نقطه ای در زیررشته های کوتاه غلبه کنیم بدون آنکه نیاز به دانستن مقادیر بیت های اعضا در کروموزوم های ارائه شده داشته باشیم.
Spears و Dejong نشان داده اند که چگونه جابجایی یکنواخت به وسیله احتمال عوض شدن و جابجا شدن بیت ها پارامتری می شود. این پارامتر فوق العاده می تواند بدون توصیف یک همگرایی مربوط به طول رشته های استفاده شده، در کنترل مقدار تغییریافته در طول ترکیب بندی مجدد استفاده شود، هنگامی که از عملگر جابجایی یکنواخت در مقادیر حقیقی استفاده می شود به آن ترکیب بندی منفصل گفته می شود.
در مقایسه هایی که بین عملگرهای دودویی به هر دو صورت تئوری و تجربی انجام شده و نتایج به دست آمده نشان می دهد که، هیچ یک از این عملگرها نمی تواند به طور مطلق بهترین بوده و اختلاف در سرعت این روش ها هم نمی تواند بیش از %2 باشد.
عملگر جابجایی دیگری که مطرح می شود به اسم Shuffle است. یک نقطه قطع مجزا انتخاب می شود اما قبل از اینکه بیت ها تعویض شوند، در هر دو والد بیت ها به صورت تصادفی جابجا می شوند. بعد از ترکیب بندی مجدد بیت ها در رشته فرزند جایگذاری می شوند. این عملگر نیز خطای همگرایی رشته ها را با جابجایی تصادفی بیت ها در هر جایی که عملگر جابجایی انجام می شود حذف می کند.
عملگر دیگری نیز عمل جابجایی را مقید می کند که همیشه اعضای جدیدی ایجاد کند در هر جایی که ممکن باشد. معمولاً این عملگر بدین صورت عمل می کند که مکان نقاط قطع را محدود می کند به گونه ای که نقاط قطع تنها جایی اتفاق می افتند که مقادیر ژن در دو کروموزوم متفاوت است.
نمونه دوم: جابجایی حقیقی (Real Crossover)
در کدگذاری حقیقی که کروموزوم ها به صورت برداری از اعداد حقیقی می باشند، روش های زیادی برای عملگر جابجایی حقیقی ارائه شده است که اکثر آن ها در دو دسته زیر خلاصه می شوند:
جابجایی عمومی
جابجایی محاسباتی
عملگرهای جابجایی عمومی با توسعه روش های جابجایی دودویی برای کدگذاری حقیقی تهیه می شوند که یک مثال ساده از آن، عملگر جابجایی ساده می باشد که شامل جابجایی تک نقطه، دو نقطه و چندنقطه است که مشابه همان حالت دودویی می باشد با این تفاوت که در اینجا به جای یک بیت دودویی (0و1) ، یک عدد حقیقی در رشته است. با فرض این که و دو کروموزومی باشند که تحت عمل جابجایی قرار می گیرند و نقطه نقطه جابجایی باشد دو کروموزوم جدید که از اعمال عملگر جابجایی ساده حاصل می شود به صورت روابط زیر خواهند بود:

(1-3)

جابجایی محاسباتی براساس مفهوم ترکیب خطی بردارها تهیه شده است. با این فرض که دو فرزند که k=1,2 است بر اساس این عملگر تولید شده باشند، در این صورت تحت شرایط مختلف برای ضرایب و در روابط مذکور، سه نوع مختلف از این عملگر ایجاد می شود:
Near crossover که در آن و هردو اعداد حقیقی هستند.
Affine crossover که در آن=1 + است.
Convex crossover که در آن =1 + بوده و و هر دو حقیقی مثبت هستند.
اسامی Affine , linear و Convex از تئوری مجموعه های محدب وام گرفته شده است. عملگر Convex معمولاً بیشتر از بقیه کاربرد دارد. این عملگرها به طور شماتیکی در شکل 9 نشان داده شده اند.
(1-4)

در عملگر تقاطع چند نقطه ای در این روش تعدادی نقطه روی کروموزوم انتخاب شده و آن را به چند قسمت تقسیم می کند. سپس قسمت های مشابه از کروموزوم ها یکی در میان با هم عوض می شوند. اولین قسمت هر کروموزوم بدون تغییر نگه داشته می شود. در شکل 1-4 این شیوه نشان داده شده است. نقاط شکست کروموزوم ها با نقطه ای بر روی آن ها مشخص شده اند.

شکل 1-4 : تقاطع چند نقطه ای

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

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

(1-5)
بزرگترین مقدار مجاز متغییر و کوچکترین مقدار مجاز آن است. t تعداد نسلهای تولید شده تا آن زمان است. مقداری بین صفر و دارد و از رابطه زیر به دست می آید.
(1-6)
T ماکزیمم تعداد نسلهاست. b هم یک پارامتر بزرگتر از یک است. که مقدار غیر یکنواختی را تعیین می کند. مقدار جهش با افزایش تعدا نسلهای تولید شده کاهش می یابد. انتخاب یکی از دو فرزند جهش یافته در بالا به صورت تصادفی است. در این شیوه باید دقت شود که مقدار متغییر ها از مقادیر مجاز افزایش نیابد و در صورت نیاز به نزدیکترین عدد صحیح گرد شود.
احتمال جهش را می توان ثابت در نظر گرفت یا اینکه آن را متناسب با تعداد نسلهای تولید شده قرار داد مثلا
(1-7)
احتمال جهش در هر نسل، یک مقدار ثابت که ماکزیمم احتمال جهش را مشخص می کند . یک ضریب ثابت است که شدت کاهش احتمال جهش را مشخص می کند این کار باعث می شود در ابتدا جهش با احتمال زیادی انجام شده فضای جستجو گسترش یابد سپس احتمال جهش کاهش یافته و جستجو در قسمتهایی در نتایج یافت شده متمرکز گردد و سرعت همگرایی افزایش یابد.

فصل دوم: کاربردهای الگوریتم ژنتیک در برنامه ریزی فرآیند

2-1-بهینه سازی مسیر فرآیند با استفاده از الگوریتم ژنتیک
2-1-1- توصیف توالی فرآیند
تعیین توالی فرایندهای پشت سر هم برای قطعات منشوری شکل کاری بسیار دشوار و پیچیده است و یک نوع تکنولوژی کلیدی در طراحی فرایند به کمک کامپیوتر به حساب می آید. در روش های قدیمی ماشینیکاری شیوه های کاری(مراحل تولید) زیادی وجود دارد و در هر کدام از این شیوه های کاری مراحل عملی(گامهای هر یک از مراحل تولید) کمی یافت می شود. بنابر این تعیین توالی این شیوه های کار فعالیتی مهم به شمار می آید. اما در ماشین های کنترل عددی جدید این شیوه های کاری کاهش یافته و اما در هر از یک شیوه های کاری چندین مرحله عملی وجود دارد. برخی اوقات بیش از 50 مرحله عملی در یک عملیات ثابت وجود دارد. به همین خاطر مراحل عملی یکی از فاکتورهای مهم در تعیین توالی فعالیتها به حساب می اید . با انجام مقایسه ای بین توالی شیوه های عملی کار و توالی مراحل شیوه های عملی کار می بینیم که مورد دوم سخت تر است و جزیئات بیشتری را شامل می شود. تعیین توالی فرایند های پشت سر هم، پروسه تجزیه و تحلیل روابط و تأثیرات داخلی فاکتورهای بسیار زیاد موجود در دستگاه است که به سختی می توان انها را با روش های ریاضی وار حل کرد. به همین خاطر نمی توان از روش های تحلیلی و شمارشی در تعیین این توالی استفاده کرد.
تعیین توالی فرایند های پشت سر هم در عناصر منشوری شکل در سیستم های CAPP قدیمی به شکل رشته های سلسله ای می باشند. این رشته ها حاوی اشکال هندسی و ایندکس های بهینه سازی می باشد و باید از روش های تکنولوژیکی و تکنیکی در آنها استفاده کرد. بعد از آن توالی پروسه ای آن را بدست می آوریم. در این روش ایجاد مسیر فرایندها با استفاده از توضیحات تکنولوژیکی و در نظر گرفتن منطق تصمیم گیری بسیار مشکل است. به همین دلیل این روش در CAPP کمی در تنگنا قرار می گیرد. عملا توالی فرایندها را می توان پروسه ای دانست که در آن یکسری از رشته ها را مکررا و یک به یک به توده ای تشکیل شده از سلولهای ماشین القا می کنند. در اینجا سلولها با مراحل عملی مطابقت پیدا کرده و واحد پایه و اساس رشته های عملیات را تشکیل می دهند. آخرین توالی که میتواند کاملا تمام رشته ها را در گیرد، مناسب ترین رشته فرایند ها خوانده می شود. بنابر این کل پروسه توالی را میتوان یک پروسه انتخابی طبیعی دانست که در آن تکامل از نسلی به نسل دیگر می رود در حالیکه بهترین ها باقی مانده و بدترین ها حذف می گردند. با استفاده از استراتژی کد گزاری، اپراتورهای تکامل و تابع صحت نیازهای توالی رفع گردید .از این شرایط موجود برای کنترل استراتژی GAها در پروسه تحقیقات به منظور هدایت محاسبه GAها و دست یابی به بهترین نتیجه ای که این شرایط را راضی کند، استفاده گردید.
اطلاعات CAD توسط سیستم CAPP قبل از اینکه مسیر توالی فرآیند تولید مشخص گردد، خوانده می شود. سپس روش ماشینکاری هر ویژگی توسط سیستم CAPP بر طبق نیازها و ویژگی های متفاوت انتخاب می گردد و روش ماشینکاری از طریق رشته هایی عملیات تعیین می گردد. در پایان رشته به سلول های ماشینکاری ویژگی ها شکسته می شود. بعنوان مثال یک حفره P در یک قطعه وجود دارد. اطلاعات CADآن عبارتند از :
قطر5.2±0.01 mm
سختی سطح Ra=1.6
عمق H=4.0 mm
بعد از خواندن اطلاعات سیستم CAPP بر اساس این اطلاعات و قابلیت هر حفره به انتخاب رشته های عملیاتی این حفره می پردازد. این رشته می تواند “دریل+ بزرگ کردن + برقو زدن سخت +