مزایا و برتریهای الگوریتم ژنتیک
قابلیت‌های روش ژنتیک را می‌توان ماحصل امتیازات ویژه این روش دانست. برخی از امتیازات این روش به صورت زیر هستند ]۳۶[:
۱- امتیاز اول جستجوی چند جانبه و کار بر روی جمعیتی از متغیرها در آن واحد است. الگوریتم ژنتیک در یک جمعیت از جواب‌ها و با مجموعه‌ای از آنها شروع به جستجو می‌کند نه با یک جواب. بدین ترتیب به جای یافتن نقطه مناسب، محدوده‌های مناسب در فضای متغیرها شناسایی ‌شده و با انتخاب والدین متناسب با شایستگی آنها از تمامی فضای متغیرها یک جستجوی هوشمند و مؤثر برنامه‌ریزی می‌گردد که امکان یافتن نقطه بهینه کلی را افزایش می‌دهد. به عبارت دیگر الگوریتم ژنتیک تحت تاثیر جواب بهینه موضعی قرار نمی‌گیرد.
در اغلب روش‌های بهینه‌سازی، جستجو از یک نقطه شروع و با یک الگوریتم خاص به نقطه دیگر هدایت می‌شود. این روش ممکن است به پاسخ موضعی منجر گردد و از یافتن پاسخ بهینه کلی بازماند. در روش ژنتیک همواره مجموعه‌ای از جمعیت متغیرها در روند جستجو به کار می‌روند، بدین ترتیب همزمان با ایجاد شانس بیشتر برای متغیرهای شایسته‌تر برای بقا و تولید مثل، جستجوی سایر مناطق فضای متغیرها با شایستگی کمتر نیز، نادیده گرفته نمی‌شود، لذا احتمال یافتن نقطه بهینه کلی افزایش می‌یابد، این ویژگی بخصوص برای توابع با تغییرات ناگهانی و دارای چندین نقطه بهینه موضعی مناسب می‌باشد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۲- امتیاز دوم صرفا استفاده از مقدار تابع هدف برای جستجو است. بنابراین نیازی به اطلاعات جانبی دیگر مانند مشتق تابع ندارد. به همین دلیل به راحتی می‌توان از این روش در بهینه‌سازی توابع منفصل و یا توابع دارای تغییرات ناگهانی و چندین نقطه بهینه موضعی استفاده کرد.
۳- امتیاز سوم استفاده از قواعد احتمالی به جای قواعد قطعی است. در بسیاری از روش‌های بهینه‌سازی، با بهره گرفتن از یک قانون معین از یک نقطه خاص در فضای جستجو به نقاط دیگر می‌رویم. این گونه روش‌های نقطه به نقطه از این جهت خطرناک هستند که در فضاهای جستجوی چند بهینه، احتمال قرار گرفتن در بهینه موضعی وجود دارد. در مقایسه با این روش‌ها، الگوریتم ژنتیک به طور همزمان با مجموعه‌ای از نقاط کار می‌کند و به طور موازی از ماکزیمم‌های مختلف فراتر رفته و بنابراین احتمال رسیدن به یک جواب اشتباه کاهش می‌یابد. البته استفاده الگوریتم ژنتیک از قواعد احتمالی به معنای یک جستجوی صرفا تصادفی نیست، بلکه این الگوریتم از انتخاب تصادفی به عنوان ابزاری برای هدایت عمل جستجو در مناطقی از فضا استفاده می‌کند.
۴- امتیاز چهارم کلی بودن الگوریتم و مستقل بودن اجزای آن است. الگوریتم ژنتیک به خاطر طبیعت تکاملی، جواب‌ها را بدون توجه به طرز کار ویژه مساله، جستجو می‌کند و می‌تواند با هر نوع تابع هدف و محدودیت (خطی و غیر خطی) در هر فضای جستجو (گسسته، پیوسته یا مرکب) کار کند به عبارت دیگر این الگوریتم از انعطاف پذیری بالایی برخوردار است.
امتیاز پنجم این است که بدون توجه به دامنه یک مساله خاص، الگوریتم ژنتیک جستجوی خود را به کمک عملیات فوق العاده ساده‌ای انجام داده و بسیار ساده و قابل درک است. در عمل، الگوریتم ژنتیک به طور حیرت آوری در جستجوی فضاهای پیچیده کاملا غیرخطی و چندبعدی به صورتی سریع و موثر عمل می‌کند.
امتیاز ششم این است که در این روش محاسبات به طور دقیق انجام شده و هیچگونه تقریبی نظیر خطی‌سازی تابع هدف، گردکردن نتایج و تغییر متغیرهای گسسته به پیوسته و بالعکس وجود ندارد.
استفاده کننده ممکن است قضاوت­های بیشتری روی انتخاب ساختار نمایش و تابع صلاحیت، انتخاب اندازه جمعیت، تعداد نسل­ها، پارامترهایی که احتمال عملیات مختلف را کنترل می‌کنند، شرط پایانی و روش‌های به دست آوردن جواب انجام دهد. تمام این انتخاب­ها ممکن است بر روی اینکه به چه اندازه الگوریتم ژنتیک در مورد یک مساله خوب اجرا می‌شود، تاثیر داشته باشد. به هر حال نکته اصلی این است که الگوریتم ژنتیک روشی مستقل از دامنه مساله است و به سرعت فضای جستجو را برای نقاطی با تابع صلاحیت بهتر، جستجو می‌کند.
معایب الگوریتم ژنتیک
روش ژنتیک نیز مانند هر روش دیگر، علی‌رغم توانایی­های قابل توجه دارای محدودیت­هایی نیز می‌باشد. یکی از محدودیت­هایی که برای این روش ذکر شده این است که روش‌های کلاسیک اگرچه در تمامی انواع مسایل قابل استفاده نمی‌باشند، اما در مورد مسایل خاص از نظر دقت نتایج، بهتر از روش ژنتیک عمل می‌کند. گرچه روش ژنتیک قادر است با سرعت مناسب پاسخ­های قابل قبول ارائه نماید، اما نمی‌تواند یافتن نقطه بهینه کلی را تضمین نماید. ولی برای بسیاری از مسایل کاربردی مهندسی که روش‌های کلاسیک جوابگو نمی‌باشند، روش ژنتیک برتری دارد.
تضمین نکردن جواب بهینه توسط الگوریتم ژنتیک توسط محققین مختلف بررسی شده و نشان داده شده است که اولا احتمال یافتن نقطه بهینه کلی توسط روش ژنتیک بالا است (در یک نمونه پیچیده حدود ۷۰ درصد بوده است)، ثانیا در موارد بسیاری نیز نزدیکترین نقطه بهینه موضعی به نقطه بهینه کلی یافت شده است.
گذری بر ژنتیک طبیعی:
در طبیعت فرایند تکامل هنگامی ایجاد می‌شود که چهار شرط زیر برقرار باشد:
یک موجود توانایی تکثیر خود را داشته باشد.
یک جمعیت از چنین موجوداتی که قابلیت تولید خود را دارند، وجود داشته باشد.
تنوع در بین این موجودات وجود داشته باشد.
انواع این موجودات توسط بعضی از قابلیت­ها، در زندگی محیط اطرافشان از هم مجزا شوند.
در طبیعت تنوع موجودات در اختلافی است که در کروموزوم­های آنها وجود دارد و این تفاوت در ساختار و رفتار افراد یک جمعیت باعث قدرت بقای متفاوت می‌شود. چرا که تنوع ساختار و رفتار به نوبه خود بر روی نرخ زاد و ولد اثر می‌گذارد. موجوداتی که توانایی بیشتری را در انجام فعالیت‌ها در محیط دارند (برای مثال موجودات متکامل)، دارای نرخ زاد و ولد بالاتری هستند و طبعا موجوداتی که برازندگی یا تطابق^[۱۰۶] کمتری با محیط دارند، دارای نرخ پایین­تری از زاد و ولد هستند. بنابراین با گذشت زمان تعداد نفراتی که رفتار و ساختار مناسب‌تری دارند افزایش می‌یابد و جمعیت رو به بهبودی و تکامل می‌رود.
بر اساس این مفهوم از تکثیر بقای طبیعی و تکثیر بقای احسن که به وسیله چارلز داروین (۱۸۵۹)، بیان شده است، بعد از چند دوره زمانی و گذشت چند نسل، کل جمعیت تمایل دارد موجوداتی را بیشتر در خود داشته باشد که با تغییر کروموزوم‌هایشان، ساختار و رفتار آنها قادر به انجام بهتر کارها در محیط و تولید مثل بهتر می‌شود. بنابراین در طی زمان، ساختار افراد جامعه به علت بقای طبیعی تغییر می‌کند. هنگامی که این تفاوت­های قابل اندازه‌گیری در ساختار افراد که ناشی از تطابق با محیط اطراف است دیده شود می‌گوییم که جمعیت تکامل یافته است. در این فرایند، ساختار توسط تطبیق مشخصات افراد جامعه با محیط ایجاد می‌شود.
هنگامی که جمعیتی از موجودات داریم، وجود تفاوت‌ها در آنها به طور غیرمستقیم در نرخ تکثیر آنها تاثیر می‌گذارد که این امر غیر قابل اجتناب است. بنابراین در عمل، وجود شرط اول از چهار شرط بالا، شرط اساسی برای شروع فرایند تکامل است.
جان هالند ]۴۴[، قالبی کلی برای تمام سیستم‌های قابل تطبیق ایجاد کرد و نشان داد چگونه می‌توان فرایند تکامل را برای سیستم‌های مصنوعی بکار برد. به طور کلی هر مساله قابل تطبیق می‌تواند در قالب واژه‌های ژنتیک فرمول‌بندی شود. اگر فرمول‌بندی این گونه مسایل بر اساس واژه‌های ژنتیک باشد، می‌توانیم آنها را بوسیله الگوریتم‌های ژنتیک حل کنیم.
الگوریتم ژنتیک، الگوریتمی ریاضی است که با بهره گرفتن از الگوهای عملیاتی داروینی در مورد تکثیر بقای احسن و بر اساس فرایند طبیعی ژنتیک، مجموعه‌ای (جمعیتی) از اشیا منفرد ریاضی (معمولا رشته‌های کارکتری با طول ثابت به عنوان رشته کروموزوم‌ها) با میزان تطبیق خاصی را به جمعیت جدیدی (برای مثال نسل بعد) تبدیل می‌کند.
الگوریتم ژنتیک در واقع تلاشی برای شبیه‌سازی برخی از خصوصیت‌های تکامل و تغییرات روی کروموزوم است که همواره در طبیعت صورت می‌گیرد. به عبارت دیگر این­ها الگوریتم‌های شدیدا موازی هستند که سعی می‌کنند با وراثت و جهش طی نسل‌های متوالی عملکرد مورد نظری را در افراد یک جمعیت ایجاد کنند. این کار از طریق ایجاد یک جمعیت اولیه و فراهم آوردن شرایط تکامل در نسل‌های بعدی صورت می‌گیرد.
اولین تئوری مربوط به تکامل در یک جمعیت توسط لامارک مطرح شد. طبق این تئوری صفات اکتسابی موجودات زنده به نسل بعد منتقل می‌شود. بنابر این اگر موجودات بخواهند با طبیعت خود تطبیق پیدا کنند این کار عملی خواهد بود. با توجه به تئوری داروین که قبلا به آن اشاره شد می‌توان به نکات زیر رسید:
وراثت: موجود زنده شبیه خود را می‌سازد و یا تولید مثل می‌کند. از لحاظ ریاضی یعنی تجربه‌های قبلی حفظ می‌شوند.
علل تصادف: در این همانندسازی یکسری تصادف‌ها و خطاهایی رخ می‌دهد و به لحاظ ریاضی اطلاعات به سیستم یا دستگاه تزریق می‌شود.
اصل انتخاب طبیعی: موجوداتی که شانس تطبیق بیشتری با طبیعت دارند بقای بهتری دارند، یعنی طبیعت شانس نابرابر برای بقا به موجودات می‌دهد.
با توجه به این مطالب شکل کلی تئوری داروین را می‌توان به صورت شکل زیر مدل کرد.
شکل۸-۳: مدل تئوری داروین
جمعیت اولیه
عملگرهای تصادفی
جمعیت جدید
انتخاب طبیعی
جمعیتی بهتر
ملاک برای مقایسه
به طور خلاصه الگوریتم ژنتیک را می‌توان به صورت زیر از فرایند تطابق طبیعی استنتاج کرد:
همانطور که خصوصیات ارثی موجودات زنده بوسیله ژن‌ها بر روی کروموزوم‌ها، رمزگذاری شده‌اند هر یک از پاسخ­های ممکن را نیز می‌توان بوسیله رشته‌های عددی در سیستم دودوئی رمزگذاری کرد و جمعیتی از رشته‌های عددی فوق را به عنوان نامزدهای حل مساله در نظر گرفت.
در سیستم‌های طبیعی، عدم قابلیت بقا و سازش ژن، سبب تغییر کثرت نسبی ژن‌ها به نفع دیگر ژن‌ها و بالعکس قابلیت بقا و سازش ژن مذکور، کثرت نسبی ژن‌ها را به نفع همین ژن تغییر می‌دهد. از طریق کثرت نسبی ژن‌ها، انتخاب طبیعی سبب تجمع تنوعات مفید می‌گردد. مشابه با این وضعیت، قابلیت بقای هر رشته جمعیت، توسط میزان انطباق آن رشته با شرایط مساله سنجیده می‌شود. در الگوریتم ژنتیک، مساله و شرایط آن به مثابه محیط در نظریه تکاملی انواع است. اطلاعات و شرایط مساله در تابعی به نام تابع ارزیابی گنجانیده و با تخصیص هر یک از رشته‌های جمعیت به عنوان متغیر تابع ارزیابی، عددی بدست می‌آید که نشان دهنده درصد سازش (بقا) آن رشته با شرایط مساله (محیط) است. بالا بودن مقدار تابع ارزیابی (عدد برازندگی) به ازای هر رشته جمعیت، نشان دهنده شانس بیشتر جهت حضور آن رشته در جمعیت بعدی و پایین بودن آن، نشان احتمال بالای عدم حضور رشته مربوط در جمعیت بعدی است. در نتیجه در جمعیت بعدی، رشته‌های با عدد برازندگی بالاتر بیش از یک بار تکرار شده، رشته‌های با عدد برازندگی پایین، از جمعیت حذف می‌شوند.
یکی از عواملی که پدیدآورنده تحول در موجودات و بوجودآورنده افراد متفاوت یک‌گونه است، عمل تقاطع است. در عمل تقاطع طبیعی کروموزوم‌های همتا با یکدیگر جفت شده، ژن­هایی بین آن دو مبادله می‌شود. مشابه با آن برای ایجاد تنوع در رشته‌های عددی و تبادل اطلاعات رشته‌ها با یکدیگر عمل تقاطع به صورت زیر روی رشته‌ها انجام می‌گیرد:
ابتدا رشته‌های جمعیت دو به دو با یکدیگر جفت می‌شوند و سپس از یک نقطه که بصورت تصادفی انتخاب می‌شود به دو تکه تقسیم شده، نیم تکه‌ها بین دو رشته تعویض می‌شوند.
یکی دیگر از عوامل تحول‌زا در موجودات، جهش می‌باشد. جهش پیدایش هرگونه تغییر در ترتیب استقرار بازها، حذف یا اضافه‌شدن یک نوکلئوتید در طول زنجیره DNA و یا جانشین شدن بازی به جای باز دیگر در زنجیره DNA می‌باشد. مشابه این فرایند، عمل جهش روی رشته‌های عددی بدین صورت واقع می‌شود که ابتدا یک عدد تصادفی بین ۱ تا L (طول رشته) انتخاب می‌شود. این عدد را K می‌نامیم. سپس در رشته مورد نظر K امین عنصر را مشخص نموده، در صورت صفر بودن به یک تبدیل می‌کنیم و بالعکس.
در مدل ریاضی روش ژنتیک، هر کدام از عملگرهای ژنتیک شبیه‌سازی می‌شوند و ترکیب آنها فرایند طبیعی انتخاب اصلح را مشخص می کند. در این روش یک نمونه از تمامی متغیرهای تصمیم‌گیری که مؤثر بر تابع هدف می‌باشند به عنوان یک عضو تلقی می‌گردد که تعدادی از این نمونه‌ها، مجموعه‌ای از اعضا را تشکیل می‌دهند و به عنوان جمعیت نمونه در فضای متغیرها نامیده می‌شود. سپس با اجرای عملگرهای ژنتیک بر روی اعضا و جمعیت اولیه، نسل جدیدی که شایستگی بالاتری دارد تولید می‌گردد. بدین ترتیب پس از تکرار چندین نسل، شایسته‌ترین نسل که همان پاسخ بهینه مساله می‌باشد تولید خواهد شد. با شبیه‌سازی ریاضی عملگرهای ژنتیک در طی یک جستجوی همه جانبه و با تکامل تدریجی بر روی یک جمعیت از جواب‌ها در طی دنباله‌ای از نسل‌ها، در پی یافتن متکامل‌ترین نمونه است که به­بهترین وجه تابع هدف را بهینه و محدودیت‌ها را تامین نماید. الگوریتم ژنتیک فضای جواب را جستجو می‌کند، تا رشته دارای بالاترین میزان تطبیق را از میان رشته‌های کاراکتری ممکن بیابد.
۵- واژگان الگوریتم ژنتیک:
از آنجا که الگوریتم ژنتیک از هر دو علم کامپیوتر و ژنتیک طبیعی نشات گرفته است واژه‌های مورد استفاده‌‌اش مخلوطی است از واژه‌های طبیعی و مصنوعی. مفاهیم اولیه که در فهم الگوریتم ژنتیک بسیار حیاتی هستند عبارتند از:
کروموزوم: اساس الگوریتم ژنتیک تبدیل هر مجموعه جواب به یک کدینگ است. این کد را اصطلاحاً کروموزوم گویند. به کروموزوم، فرد^[۱۰۷]، رشته^[۱۰۸] و ساختار^[۱۰۹] نیز گفته شده‌است. همچنین می‌توان آنها را ژنو تایپ^[۱۱۰] نیز نامید.
فنو تایپ^[۱۱۱]: هر کروموزوم متناظر با یک مجموعه جواب از مساله است. مجموعه متناظر با هر کروموزوم را یک فنو تایپ می‌گویند.
ژن: عناصر تشکیل دهنده یک کروموزوم که معمولا اعداد هستند را ژن می‌گویند. ژن­ها را ترکیب^[۱۱۲]، نشان^[۱۱۳] و رمزگشا^[۱۱۴] نیز نامیده‌اند.
مکان: محل قرار گرفتن ژن در کروموزوم را یک مکان می‌گویند.