پایان نامه با کلید واژه های انتخاب رشته، پژوهشگران

تا در نهایت بهترین طرح ممکن حاصل گردد. این روش نه تنها پایدار است بلکه نیازی به گرادیان تابع هدف ندارد. این الگوریتم بر اساس انتخاب اتفاق‍ی مشابه آنچه در طب‍یعت است بنا شده و به سرعت از اطلاعات بدست آمده برای رس‍یدن به نتایج بهتر درس گرفته و استفاده م‍یکند.
اکثر روشهای به‍ینهیاب‍ی به نحوه تغ‍ی‍یرات یا مشتق تابع هدف ن‍یاز دارند که عموما ًبه روشهای تحل‍یل‍ی یا عددی محاسبه م‍یشوند. در مقابل الگوریتم ژنتیک نیازی به مشتق تابع هدف ندارد و م‍یتواند مسائل ناپ‍یوسته را مانند مسائل پ‍یوسته به‍ینهیاب‍ی نماید. همچن‍ین الگوریتم ژنتیک ازیک سری عملگرهای اتفاق‍ی بهره م‍یگ‍یرد. از آنجا که این عملگرها در هر مرحله بر روی مجموعه کروموزومهای انتخاب شده و ب‍ین آنها انجام م‍یشود لذا از اطلاعات بدست آمده در مراحل قبل استفاده م‍یشود. به هم‍ین جهت نباید با روش جستجوی اتفاق‍ی که در آن ه‍یچگاه از نقاط بدستآمده در مرحله قبل استفاده نم‍یشود اشتباه گردد.
3-3-2-?ساختار الگوریتم ژنتیک
روش الگوریتم ژنتیک به منظور بهرهگیری از انتخاب تکامل طبیعی طرح شده است. در هر تکرار که یک نسل نامیده میشود جمعیتی از طرحهای مورد آزمون ارزیابی میگردند تا برای شرکت در تولید طرحهای جدید با همدیگر رقابت کنند. هر طرح توسط یک رشته نمایش داده میشود که مجموعهای از مقادیر طراحی است. به طور معمول رشتهها از ارقام در مبنای دو ساخته میشوند. یک رشته با کروموزومی که دارای ژنهای گوناگونی است بیان خواهد شد. هر ژن متناظر با یک متغیر طراحی است. رشتهها برای پدر و مادر شدن و تولید فرزندان به نسبت صلاحیت خود انتخاب میشوند. پس از انتخاب رشتههای ژنتیکی با استفاده از عملگر پیوند ترکیب جدیدی از آنها پیدا میشود به طوری که طرحهای جدید بخشهایی از دو طرح پیشین را دارا هستند. یک عملگر جهش میتواند بخشهایی از رشتههای جدید را اصلاح نماید به گونهای که ممکن است شامل ترکیبهای تازهای شوند که در والدین موجود نبوده است.
در این روش محاسباتی از ویژگیهای گرادیان تابع هدف به منظور هدایت فرایند بهرهگرفته نمیشود. موثر بودن این فرایند در رسیدن به پاسخ بهینه به نحوه ارتباط بین بخشهای یک رشته ژنتیکی و طرحی که با این رشته نمایش داده میشود وابسته است. زیرا رشتهها به احتمال قوی در نسلهای بعد حتی اگر رشتهها توسط عملگرهای پیوند و جهش شکسته شوند باقی خواهد ماند. زیرا رشتههای با صلاحیت پایین در نسلهای پیاپی نابود نمیشوند و برای تشکیل زیر رشتهها با صلاحیت بالاتر با یکدیگر ترکیب میشوند. این فرایند در نسلهای زیادی تکرار میشود تا بهترین طرح پیدا گردد.
از دیدگاه نظری و تجربی ثابت شده است که روش الگوریتم ژنتیک یک جستجوی توانا و قدرتمند در فضاهای پیچیده فراهم میآورد. از آنجا که معتبر بودن این فرایند در حل مسائلی که احتیاج به جستجوی موثر و کارامد دارند ثابت شده است کاربرد آن در زمینههای مختلف گسترش یافته است. دلیل استفاده فراوان از این روش در زمینههای متفاوت این است که از یک سو به لحاظ محاسباتی ساده بوده و از سوی دیگر در مراحل جستجو بسیار قدرتمند میباشد. علاوه بر این از نظر مبانی و اصول به فرضیات محدود کننده نظیر پیوستگی و یا وجود داشتن مشتقات تابع محدود نمیباشد.
3-3-3-?اجزای الگوریتم ژنتیک
اجزای الگوریتم ژنتیک شامل متغیرهای طراحی و تابع صلاحیت میباشد که در ذیل به تفصیل شرح داده میشود [148]:
3-3-3-1- متغیرهای طراحی
تعیین مجموعه متغیرهای مساله به عنوان یک رشته با طول معین اولین گام روشهای ژنتیک میباشد. این مرحله از اهمیت ویژهای برخوردار است. زیرا متغیرهای رمزگذاری شده را به متغیرهای واقعی آن مربوط مینماید. انواع مختلفی از نمایش متغیرها وجود دارند. در این روش هر متغیر طراحی به صورت ارقام دودویی و طول ثابت رمزگذاری میشود. هر متغیر طراحی به وسیله یک زیر رشته با طول بیت نشان داده میشود. مقدار به نوع متغیر و محدودیتهای جانبی مربوطه بستگی دارد. برای تشکیل یک کروموزوم که نماینده یک نقطه از فضای طراحی میباشد کلیه زیر رشتههای متغیر طراحی به صورت سر به دم یکدیگر وصل و متصل میشوند. طول کروموزوم از رابطه زیر بدست میآید:
(3-4)
در رابطه فوق تعداد متغیرهای طراحی وطول زیر رشته مربوط به متغیر طراحی iام مساله است. متغیرهای طراحی نسبت به نوع متغیر به دو گونه متغیرهای گسسته و پیوسته تقسیم گشتهاند که در ادامه به نحوه بکار بردن هر کدام پرداخته میشود. موارد مهم در مورد متغیرهای طراحی رمزگذاری و رمزگشایی آنها میباشد که در ادامه به شرح آنها میپردازیم:
3-3-3-1-1- متغیرهای طراحی گسسته
رمزگذاری: طول زیر رشتهبستگی به تعداد مقادیر مستقل طراحی دارد و به صورت زیر است:
(3-5)
که در این رابطه تعداد مقادیر مستقل مربوط به متغیر iام می باشد. به عنوان نمونه چنانچه 16 مقدار مستقل طراحی وجود داشته باشدخواهد بود. اگر تعداد مقادیر گسسته با مقداریکی نباشد میتوان از روش پخش اضافه که در آن هر مقدار گسسته ممکن است بیشتر ازیک نمایش دودویی داشته باشد استفاده نمود.
رمزگشایی: مقادیر فیزیکی متغیرهای طراحی توسط یک فرایند دو مرحلهای به دست میآیند که به تبدیل نمودن رابطههای بین اعداد دهدهی بدون علامت و مقدارهای مجزا بنا شده است.
مرحله اول: زیر رشته با ارقام دودویی طبق رابطه تبدیل به عدد دهدهی بدون علامت میشود.
مرحله دوم: مقدار فیزیکی متغیر طراحی توسط یک تناظر یک به یک ازI به مجموعه مقادیر مجزا تعیین میشود.
(3-6)
در اینجا m کمترین مقداری است که نامساوی ()را برقرار نماید و مقدار آن برابر با طول رشته متغیرiام خواهد بود. مقدار iامین سلول زیر رشته است و مقدارش صفر و یا یک میباشد.
3-3-3-1-2- متغیرهای طراحی پیوسته
رمزگذاری: چنانچهدقت مورد نیاز در متغیرهای طراحی پیوسته باشد حداقل طول زیر رشته بایستی برابر مقدار زیر باشد:
(3-7)
در این رابطه به ترتیب کرانههای بالا و پایین متغیرهای پیوستهمیباشد. برای نمونه اگر ووباشد آنگاه خواهد بود.
رمزگشایی: ابتدا زیر رشته با ارقام در مبنای دو به یک عدد دهدهی بدون علامت I تبدیل میگردد. سپس مقدار فیزیکی X طبق رابطه زیر محاسبه میگردد:
(3-8)
برای نمونه چنانچه وباشد آنگاه مقدار X برابر با 16.867خواهد بود.
3-3-3-2- تابع صلاحیت
تابع صلاحیت از تبدیل مناسب تابع هدف بدست میآید و کیفیت هر رشته را با استفاده ازیک مقدار عددی ارزیابی میکند. هرچه کیفیت رشته بهتر باشد مقدار صلاحیت آن بیشتر خواهد بود و احتمال اینکه برای تولید نسل بعدی نیز شرکت کند افزایش خواهد یافت. به عبارت دیگر صلاحیت کارایی تولید مثل جانداران را بر اساس اصل بقای نسل ارائه شده توسط داروین بیان میکند. در واقع صلاحیت نوعی معیار در اندازهگیری کیفیت بوده که بایستی حداکثر گردد. به بیان بهتر میتوان گفت که رشتههای با مقدار صلاحیت بالاتر احتمال بیشتری برای انتخاب شدن به عنوان پدر و مادر برای تولید نسل بعدی خواهند داشت. چون احتمال انتخاب شدن هر فرد عددی مثبت میباشد و متناسب با میزان صلاحیت او میباشد لذا بایستی تابع صلاحیت مقدار مثبتی داشته باشد. بر این اساس تابع صلاحیت از رابطه زیر بدست میآید:
(3-9)
در این رابطه مقدار بیشینه تابع هدف اصلاح شده و مقدار تابع هدف اصلاح شده طرح iام میباشد که از منفی شدن تابع صلاحیت Fجلوگیری میکند.
3-3-3-2-1- درجهبندی تابع صلاحیت
در روشهای ژنتیک با جمعیت کم وجود داشتن تعادل در تعداد تکثیر از اهمیت ویژهای برخوردار است. در آغاز فرایند جستجو بطور معمول تعدادی از طرحهای با صلاحیت بالا در جمعیتی از رشتههای با صلاحیت متوسط بوجود میآید. چنانچه قانون انتخاب طبیعی بکار رود رشتههای با صلاحیت بالا برای تکثیر شدن و تولید جمعیت جدید از احتمال بیشتری برخوردار هستند. این مساله سبب تسلط زود هنگام رشتههای با صلاحیت بالا میشود و در فرایند جستجو ممکن است در نسلهای بعدی صلاحیت متوسط جمعیت به بهترین صلاحیت نزدیک شود. در این حالت رشتههای متوسط و رشتههای بهتر به تعداد مساوی تکثیر میگردند و باقی ماندن رشتههای بهتر در بهبود بخشیدن به فرایند جستجو یک روند تصادفی خواهد بود. در این موارد صلاحیت درجه بندی شده میتواند موثر باشد زیرا که صلاحیت درجهبندی شده سبب میشود تا هر رشته برای تکثیر از یک شانس مجدد برخوردار باشد. بدین ترتیب تعداد تکثیرهای اختصاص داده شده به هر رشته متعادل میگردد. چندین روش توسط پژوهشگران برای درجه بندی صلاحیت پیشنهاد شده است که از بین آنها میتوان درجهبندی خطی و درجهبندی توانی را نام برد.
الف- درجه بندی خطی
برای نخستین بار گلدبرگ الگوی درجهبندی خطی را پیشنهاد کرد. چنانچه صلاحیت واقعی را باو صلاحیت درجهبندی شده را با نمایش داده شود، درجهبندی خطی بصورت رابطه زیر بیان خواهد شد:
(3-10)
در رابطه پارامترهای ثابتی هستند که ممکن است به روشهای متفاوتی انتخاب گردند. به هر حال با هر روش و شیوهای که این دو ثابت انتخاب و برگزیده شوند بهتر است که صلاحیت میانگین درجه بندی شده برابر صلاحیت میانگین حقیقی و واقعی باشد. زیرا باعث میشود که هر عضو با صلاحیت متوسط از جمعیت تنها در تولید یک رشته جدید از نسل بعدی شرکت داشته باشد.
برای محدود کردن تعداد فرزندانی که باعث حداکثر شدن صلاحیت واقعی جمعیت خواهند شد از رابطه دیگری برای بدست آوردن این صلاحیت حداکثر و درجه بندی شده استفاده میشود که بصورت زیر میباشد:
(3-11)
در این رابطه تعداد تکثیرهای مطلوب مورد انتظار برای بهترین رشته از جمعیت میباشد. برای نمونه در جمعیتهای بین 50 تا 500 عدد مقدار بین 2/1 تا 2 رضایت بخش است و هنگامی که فرایند جستجو به جواب بهینه نزدیک میشود مقدار صلاحیت واقعی را بطور عمده طبق شکل3-1 افزایش میدهد.
شکل3-1- درجه بندی خطی در شرایط عادی [148]
از طرف دیگر ممکن است در مرحلهای از فرایند جستجو پس از گذشت نسلهای زیادی وضعیت پیچیدهای رخ دهد. این وضعیت در شکل 3-2 نشان داده شده است.
بدین صورت که چند تا از رشتههای با صلاحیت واقعی بسیار و نزدیک به هم با فاصلهای بیشتر از تفاوت بین حداکثر و میانگین صلاحیت جمعیت نسبت به صلاحیت واقعی متوسط جمعیت قرار میگیرند. چنانچه در این حالت از درجهبندی خطی استفاده شود برای بعضی از رشتهها صلاحیت درجهبندی شده منفی بدست خواهد آمد و این سبب گسیختگی فرایند جستجو میگردد.
شکل3-2- درجه بندی خطی در شرایط ویژه[148]
چندین روش برای حل این مساله وجود دارد که همانند حالت قبل بایستی صلاحیت میانگین واقعی را برابر صلاحیت میانگین درجهبندی شده قرار داد. برای تعیین رابطه جهت بدست آوردن مقادیر بایستی برای حداقل مقدار صلاحیت واقعی یعنی حداقل مقدار صلاحیت درجهبندی شده ()در نظر گرفت.
ب‌- درجه بندی توانی
در فرایند جستجوی ژنتیکی هرگاه بیشتر اعضای جمعیت از صلاحیت بالایی برخوردار باشند تصمیمگیری و انتخاب اعضا برای تکثیر مشکل خواهد بود. در این حالت با استفاده از درجهبندی توانی اختلاف بین مقدار صلاحیت افراد افزایش خواهد یافت. رابطه زیر نوعی درجهبندی توانی است.
(3-12)
در رابطه صلاحیت محاسبه شده و

مطلب مرتبط با این موضوع :  پایان نامه با کلید واژه هایآسیب، روشهای، الگوریتم

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