تحقیق درمورد الگوریتم ژنتیک و مفاهیم اولیه

اصل انتخاب طبیعی: موجوداتی که شانس تطبیق بیشتری با طبیعت دارند بقای بهتری دارند، یعنی طبیعت شانس نابرابر برای بقا به موجودات می‌دهد.
با توجه به این مطالب شکل کلی تئوری داروین را می‌توان به صورت شکل زیر مدل کرد.
شکل8-3: مدل تئوری داروین
شکل8-3: مدل تئوری داروین
جمعیت اولیه
عملگرهای تصادفی
جمعیت جدید
انتخاب طبیعی
جمعیتی بهتر
ملاک برای مقایسه
به طور خلاصه الگوریتم ژنتیک را می‌توان به صورت زیر از فرآیند تطابق طبیعی استنتاج کرد:
همانطور که خصوصیات ارثی موجودات زنده بوسیله ژن‌ها بر روی کروموزوم‌ها، رمزگذاری شده‌اند هر یک از پاسخهای ممکن را نیز می‌توان بوسیله رشته‌های عددی در سیستم دودوئی رمزگذاری کرد و جمعیتی از رشته‌های عددی فوق را به عنوان نامزدهای حل مساله در نظر گرفت.
در سیستم‌های طبیعی، عدم قابلیت بقا و سازش ژن، سبب تغییر کثرت نسبی ژن‌ها به نفع دیگر ژن‌ها و بالعکس قابلیت بقا و سازش ژن مذکور، کثرت نسبی ژن‌ها را به نفع همین ژن تغییر می‌دهد. از طریق کثرت نسبی ژن‌ها، انتخاب طبیعی سبب تجمع تنوعات مفید می‌گردد. مشابه با این وضعیت، قابلیت بقای هر رشته جمعیت، توسط میزان انطباق آن رشته با شرایط مساله سنجیده می‌شود. در الگوریتم ژنتیک، مساله و شرایط آن به مثابه محیط در نظریه تکاملی انواع است. اطلاعات و شرایط مساله در تابعی به نام تابع ارزیابی گنجانیده و با تخصیص هر یک از رشته‌های جمعیت به عنوان متغیر تابع ارزیابی، عددی بدست می‌آید که نشان دهنده درصد سازش (بقا) آن رشته با شرایط مساله (محیط) است. بالا بودن مقدار تابع ارزیابی (عدد برازندگی) به ازای هر رشته جمعیت، نشان دهنده شانس بیشتر جهت حضور آن رشته در جمعیت بعدی و پایین بودن آن، نشان احتمال بالای عدم حضور رشته مربوط در جمعیت بعدی است. در نتیجه در جمعیت بعدی، رشته‌های با عدد برازندگی بالاتر بیش از یک بار تکرار شده، رشته‌های با عدد برازندگی پایین، از جمعیت حذف می‌شوند.
یکی از عواملی که پدیدآورنده تحول در موجودات و بوجودآورنده افراد متفاوت یک‌گونه است، عمل تقاطع است. در عمل تقاطع طبیعی کروموزوم‌های همتا با یکدیگر جفت شده، ژنهایی بین آن دو مبادله می‌شود. مشابه با آن برای ایجاد تنوع در رشته‌های عددی و تبادل اطلاعات رشته‌ها با یکدیگر عمل تقاطع به صورت زیر روی رشته‌ها انجام می‌گیرد:
ابتدا رشته‌های جمعیت دو به دو با یکدیگر جفت می‌شوند و سپس از یک نقطه که بصورت تصادفی انتخاب می‌شود به دو تکه تقسیم شده، نیم تکه‌ها بین دو رشته تعویض می‌شوند.
یکی دیگر از عوامل تحول‌زا در موجودات، جهش می‌باشد. جهش پیدایش هرگونه تغییر در ترتیب استقرار بازها، حذف یا اضافه‌شدن یک نوکلئوتید در طول زنجیره DNA و یا جانشین شدن بازی به جای باز دیگر در زنجیره DNA می‌باشد. مشابه این فرآیند، عمل جهش روی رشته‌های عددی بدین صورت واقع می‌شود که ابتدا یک عدد تصادفی بین 1 تا L (طول رشته) انتخاب می‌شود. این عدد را K می‌نامیم. سپس در رشته مورد نظر K امین عنصر را مشخص نموده، در صورت صفر بودن به یک تبدیل می‌کنیم و بالعکس.
در مدل ریاضی روش ژنتیک، هر کدام از عملگرهای ژنتیک شبیه‌سازی می‌شوند و ترکیب آنها فرآیند طبیعی انتخاب اصلح را مشخص می‌نماید. در این روش یک نمونه از تمامی متغیرهای تصمیم‌گیری که مؤثر بر تابع هدف می‌باشند به عنوان یک عضو تلقی می‌گردد که تعدادی از این نمونه‌ها، مجموعه‌ای از اعضا را تشکیل می‌دهند و به عنوان جمعیت نمونه در فضای متغیرها نامیده می‌شود. سپس با اجرای عملگرهای ژنتیک بر روی اعضا و جمعیت اولیه، نسل جدیدی که شایستگی بالاتری دارد تولید می‌گردد. بدین ترتیب پس از تکرار چندین نسل، شایسته‌ترین نسل که همان پاسخ بهینه مساله می‌باشد تولید خواهد شد. با شبیه‌سازی ریاضی عملگرهای ژنتیک در طی یک جستجوی همه جانبه و با تکامل تدریجی بر روی یک جمعیت از جواب‌ها در طی دنباله‌ای از نسل‌ها، در پی یافتن متکامل‌ترین نمونه است که بهبهترین وجه تابع هدف را بهینه و محدودیت‌ها را تامین نماید. الگوریتم ژنتیک فضای جواب را جستجو می‌کند، تا رشته دارای بالاترین میزان تطبیق را از میان رشته‌های کاراکتری ممکن بیابد.
5- واژگان الگوریتم ژنتیک:
از آنجا که الگوریتم ژنتیک از هر دو علم کامپیوتر و ژنتیک طبیعی نشات گرفته است واژه‌های مورد استفاده‌‌اش مخلوطی است از واژه‌های طبیعی و مصنوعی. مفاهیم اولیه که در فهم الگوریتم ژنتیک بسیار حیاتی هستند عبارتند از:
کروموزوم: اساس الگوریتم ژنتیک تبدیل هر مجموعه جواب به یک کدینگ است. این کد را اصطلاحاً کروموزوم گویند. به کروموزوم، فرد، رشته و ساختار نیز گفته شده‌است. همچنین می‌توان آنها را ژنو تایپ نیز نامید.
فنو تایپ: هر کروموزوم متناظر با یک مجموعه جواب از مساله است. مجموعه متناظر با هر کروموزوم را یک فنو تایپ می‌گویند.
ژن: عناصر تشکیل دهنده یک کروموزوم که معمولا اعداد هستند را ژن می‌گویند. ژنها را ترکیب، نشان و رمزگشا نیز نامیده‌اند.
این نوشته در علمی ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.