برای جستجو در بین هزاران پایان نامه در موضوعات مختلف     

      و دانلود متن کامل آنها با فرمت ورد اینجا کلیک کنید     

 
دانلود پایان نامه
قابل قبول بودن یک کروموزوم به این مفهوم است که آیا دیکدینگ این کروموزوم در ناحیه قابل قبول که جزئی از فضای جواب مساله است قرار دارد یا خیر؟
غیرقابل قبول بودن یک کروموزوم ناشی از طبیعت مسائل بهینه سازی با محدودیت می باشد. معمولاً در مسائل بهینه سازی فضای قابل قبول بوسیله یک سیستم معادلات یا نامعادلات تشکیل می شود. درمتعددی به منظور جلوگیری از ایجاد چنین مواردی روش های جریمه ای کروموزوم های غیرقابل قبول پیشنهاد شده است. در مسائل بهینه سازی با محدودیت عموماً جواب در فضای جواب در مرز بین فضای قابل قبول و فضای غیرقابل قبول قرار دارد. در نتیجه روش های جریمه ای الگوریتم ژنتیک را مجبور می کنند که از هر دو طرف به سمت جواب حرکت کند.
مرز بین فضای قابل قبول و فضای غیرقابل قبول قرار دارد. در نتیجه روش های جریمه ای الگوریتم ژنتیک را مجبور می کنند که از هر دو طرف به سمت جواب حرکت کند. قانونی بودن یک کروموزوم به این مفهوم است که آیا این کروموزوم دراثر دیکدینگ به یک جواب منجرخواهد شد یا خیر ؟ یعنی در فضای جواب قرار خواهد گرفت یا خیر؟غیر قانونی بودن یک کروموزوم ناشی از طبیعت روش های کدینگ می باشد. چون یک کروموزوم غیرقانونی قادر نیست به یک جواب تبدیل شود، در نتیجه ارزیابی چنین کروموزومی غیر ممکن است و بنابراین روش های جریمه ای در اینجا عملی نیستند. در چنین مواردی معمولاً از روش های تعمیری به منظور تبدیل کروموزم های غیر قانونی به کرومزوم های قانونی استفاده می کنند.
شکل 3- 6: رابطه بین کروموزوم ها و جواب ها
مساله سوم، بحث یکسانی رابطه است. روابط بین کروموزوم ها و جواب ها معمولاً به یکی از سه صورت زیر است:
رابطه یک به یک
رابطه یک به n
رابطه n به یک
شکل 3-7 این سه نوع رابطه را نشان می دهد. از این سه نوع رابطه، رابطه یک به یک بهترین نوع رابطه و رابطه n به یک بدترین نوع آن است.
شکل 3- 7: انواع روابط بین کروموزوم ها و جواب ها
کروموزوم
رشته یا دنباله ای از بیت ها که به عنوان شکل کد شده یک جواب ممکن(مناسب یا نامناسب) از مساله مورد نظر می باشد، را کروموزوم می گویند. در حقیقت بیت های یک کروموزوم، نقش ژن ها رادر طبیعت عضوی انتخاب می شود. هر بیت، متغیری گسسته است که از یک مجموعه Q عضوی انتخاب می شود چنانچه از کدگذاری باینری استفاده شود، هر بیت یکی از دو مقدار ٠ یا ١ را می پذیرد.
شکل 3- 8: نمایش یک کروموزوم n بیتی
جمعیت
مجموعه ای از کروموزوم ها را جمعیت گویند. یکی از ویژگی های ژنتیک این است که به جای تمرکز برروی یک نقطه از فضای جستجو یا یک کروموزوم، بر روی جمعیتی از کروموزوم ها کار می کند. بدین ترتیب در هر مرحله، الگوریتم دارای جمعیتی از کروموزوم ها بوده که خواص مورد نظر را بیشتر از جمعیت مرحله قبل دارا می باشد. هر جمعیت یا یک نسل از کروموزوم ها، دارای یک اندازه می باشد که به اندازه جمعیت معروف است. اندازه جمعیت معرف تعداد کروموزوم های موجود درجمعیت یا یک نسل است. اگر تعداد کروموزوم ها خیلی کم باشد، امکان شکل گیری عملیات جابجایی توسط الگوریتم ژنتیک بسیار کم خواهد بود و تنها قسمت کمی از فضای جستجو مورد کاوش قرار خواهد گرفت. از طرف دیگر، اگر تعداد کروموزوم ها خیلی زیاد باشد، الگوریتم بسیار کند خواهد شد. بر اساس تحقیقات، جمعیت های با اندازه مناسب حدود ٢٠ تا ٣٠ کروموزوم دارند. البته گاهی اوقات جمعیت با اندازه ۵٠ تا ١٠٠ بهترین جواب ها را داده اند. بعضی تحقیقات نیز نشان می دهد که اندازه جمعیت باید بر اساس نوع مساله و کدینگ آن تعریف شود و افزایش بیشتر آن بی فایده خواهد بود و هرگز به حل سریعتر مساله کمک نمی کند.
مقدار برازندگی
مناسب بودن یا نبودن جواب، با معیاری که از تابع هدف بدست می آید، سنجیده می شود. هر چه که یک جواب مناسب تر باشد، مقدار برازندگی بزرگتری دارد. برای آنکه شانس بقای چنین جوابی بیشتر شود، احتمال بقای آن، متناسب با مقدار برازندگی آن در نظر گرفته می شود. بنابراین کروموزمی که برازنده ترین است با احتمال بیشتری در تولید فرزندان شرکت می کند و دنباله های بیشتری از آن به وجود می آید. به عنوان مثال چنانچه هدف بیشینه کردن یک تابع باشد، مقدار برازندگی، یک تابع صعودی از تابع هدف در نظر گرفته می شود و اگر هدف یافتن مقدار کمینه یک تابع باشد، عدد برازندگی، یک تابع نزولی از آن قرار داده می شود. معمولاً در مواردی که امکان دارد، تابع برازندگی را در فاصله [١ و 0] نرمالیزه می کنند.
عملگر تقاطعی
این عملگر بر روی یک جفت از کروموزوم ها عمل می کند و می تواند به صورت تک نقطه ای، چند نقطه ای و یکنواخت باشد . عملگر تقاطعی تک نقطه ای، دو کروموزوم را به طور تصادفی از یک نقطه شکسته و بخش های شکسته دو کروموزوم را جابجا می کند. بدین ترتیب دو کروموزوم جدید بدست می آید. به کروموزوم های اولیه، کروموزوم های”والد“ و به کروموزوم های حاصل شده از عمل جابجایی وعمل جهش، کروموزوم”فرزند“می گویند.
عملگر تقاطعی با احتمال PC بر روی کروموزوم های والد عمل می کند. بدین معنی که با احتمال PC عمل تقاطع انجام می گیرد. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقًا مشابه والدین خواهند بود(البته این مطلب بدین معنی نیست که نسل جدید همان نسل قبلی است). در صورتی که عمل تقاطع صورت بگیرد، فرزندان از قسمت های مختلف کروموزوم های والد ساخته می شوند. اگر احتمال تقاطع ١ باشد، تمامی فرزندان از طریق عمل تقاطعی ایجاد می شوند. عملیات تقاطع با این هدف انجام می شود که کروموزوم های جدید در بردارنده قسمت های مناسب و خوب کروموزوم های قبلی خواهند بود و شاید این کروموزوم های جدید عملکرد بهتری داشته باشند اما بهتر است همیشه بهترین کروموزوم های نسل قبلی بدون هیچ تغییری به نسل جدید منتقل شوند.
معمولاً اگر کروموزوم از کدگذاری چند متغیر به وجود آمده باشد، بهتر است که نقطه جابجایی، محل اتصال متغیرها انتخاب شود. در شکل 3-9 کروموزوم ها از شکل کد شده متغیرهای x و y و z وw ساخته شده اند. محل اتصال متغیرها می تواند به عنوان نقطه تقاطع استفاده شود. به طور مثال در شکل 3-9 ، محل اتصال متغیرهای x و y به عنوان نقطه تقاطع انتخاب شده است.
شکل 3- 9: تقاطع در کرموزوم هایی که از شکل کد شده چهار متغیر به وجود آمده اند.
تفاوت عملگر چندنقطه ای در مقایسه با عملگر تقاطعی تک نقطه ای در این است که نقطه شکست دو کروموزوم، بیش از یکی است و تقاطع در بخش های شکسته شده دو کروموزوم به صورت یک در میان انجام می گیرد. معادله ی زیر مثالی از عمل تقاطع دو نقطه ای را نشان می دهند.
دسته بندی : علمی