دانلود پایان نامه

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

۳۳ ۲-۶-۵ واژگان الگوریتم ژنتیک
* رشته یا کروموزوم (Chromosome): آرایه ای از اعداد صحیح (کدهای باینری) است که مقادیر عناصر این آرایه با توجه به نوع رشته مشخص می شود. مثلا در رشته باینری این اعداد صفر و یک هستند. این اعداد مشخص کننده متغیر های بهینه سازی مسئله هستند. می توان گفت که هر کروموزوم دو بخش عمده دارد، اولین بخش همان ژن های کروموزوم هستند و دومین بخش میزان تابع برازندگی (Fitness) مرتبط با کروموزوم است. اطلاعات هر نسل توسط کروموزوم ها به نسل بعد منتقل می شود.
* ژن (Gene): بخشی از رشته یا کروموزوم است که خصوصیات ویژه ای را معین می کند. در واقع همان متغیر های بهینه سازی مسئله می باشد.
* نماد معرف: به خصوصیات قابل مشاهده یک جاندار گفته می شود که در مسائل بهینه سازی به بردار حقیقی حاصل از رمز گشایی یک رشته گفته می شود.
* نسل (Generation): یک دوره از زاد و ولد اعضای یک جمعیت را نسل می گویند. به عبارت دیگر هر جایگزینی از جمعیت قدیمی را با جمعیت جدید یک نسل (زاد و ولد) می گویند.
* برازندگی (Fitness): در طبیعت به سازگاری و میزان تطابق یک جاندار با محیط گفته می شود و در بهینه سازی به میزان ارزیابی تابع هدف با مقداری متناظر با آن به ازای یک رشته (جواب) خاص گفته می شود که نشان دهنده میزان مطلوبیت آن رشته (جواب) برای تابع هدف می باشد. بنابراین با استفاده از جزء ارزیابی میزان برازندگی جوابها مورد بررسی قرار می گیرد.
* تقاطع (Crossover): به جابه جایی و مبادله قسمت های مختلف یک رشته گفته می شود. این جابه جایی ها توسط عملگرهای ویژه ای صورت می گیرد که در ادامه توضیح داده خواهد شد.
* جهش (Mutation): به تغییر تصادفی و ناگهانی یکی از عناصر یک رشته (ژن) گفته می شود.
۳۴
۳۵ ۲-۶-۶ مفاهیم کلیدی در الگوریتم ژنتیک
در هنگام استفاده از الگوریتم ژنتیک نکاتی را باید مدنظر قرار داد که می توان از جمله مهمترین آن ها را به صورت زیر برشمرد.
توجه به پارامترهای مسئله مانند:
* نحوه کد کردن کروموزوم ها
* اندازه جمعیت اولیه
* روش های انتخاب و تعداد کروموزومهای انتخاب شده
* نوع عملگرهای ادغام و جهش
* نرخ ادغام و نرخ جهش
* تعداد فرزندان تولیدی در هر بار تولید مثل
* تابع برازندگی و کارایی
* شرط خاتمه
سیستم کدینگ : اولین گام در بکارگیری و پیاده سازی یک الگوریتم ژنتیک نمایش جواب های مساله بصورت یک کروموزوم است در حقیقت این عمل یک مفهوم کلیدی در الگوریتم ژنتیک می باشد . کدینگ را می توان به هر دو نوع رشته ای و غیر رشته ای تقسیم کرد در کدینگ رشته ای هدف تبدیل جواب های مساله به رشته های از اعداد است گاهی این رشته متشکل از صفرها و یک هاست در این صورت رشته دودویی نامیده می شود اگر عناصر رشته از مقادیر دیگری تشکیل شده باشند با رشته غیر دو دویی مواجه می شویم که این نوع کدینگ در مسائل بهینه سازی کاربرد بسیار کمی داشته و تنها در مسائل بسیار خاص استفاده می شود.
در رشته های دو دویی دو رویکرد وجود دارد یا هر عنصر رشته(ژن) با یک قسمت از مجموعه جواب متناظر است و یا چند عنصر رشته با یک قسمت از مجموعه جواب تناظر دارد .
تعداد بیتهایی که برای کد گذاری متغیر استفاده می شود به دقت مورد نظر برای جواب های محدود تغییر پارامتر ها و رابطه بین پارامتر ها وابسته است در هنگام استفاده از کدینگ با سه مفهوم اساسی روبرو هستیم
* قانون مند بودن کروموزم
* موجه بودن کروموزوم
* منحصر به فرد بودن ترسیم
قانون مندی کروزمووم مربوط به زمان بکارگیری اعمال ژنتیک می باشد یعنی گاهی اوقات ممکن است کروموزوم هایی تولید شود که با هیچ عضوی از فضای جواب متناظر نباشد .
موجه بودن کروموزوم مربوط به حالتی است که بعد از رمز گشایی همه محدودیت های مساله را ارضا می کند در غیر این صورت کروموزوم غیر موجه خواهد بود .
جمعیت اولیه : مجموعه ای از کروموزوم ها را جمعیت گویند یکی از ویژگی های الگوریم ژنتیک این است که به جای تمرکز بر روی یک نقطه از فضای جستجو با یک کروموزوم بر روی جمعیتی از کرومزوم کار می کند (فوگرتی ۱۹۸۹و ۱۰۹-۱۰۴)
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار می رود ایجاد یک جمعیت اولیه از کروموزوم هاست در این مرحله جواب اولیه معمولاً بصورت تصادفی تولید می شودالبته در بعضی موارد با توجه به نوع مساله و برای بالا بردن سرعت همگرایی الگوریتم از روش های ابتکاری نیز استفاده گردیده است (کازرلیس و همکارن ۱۹۹۶و۹۲-۸۳) به عنوان نمونه ریوز در حل مساله توالی جریان کارگاه از الگوریتم NEH استفاده نمود و یک کروموزوم خوب تهیه کرد(ریوز ۱۹۹۵و۱۳-۵).
عملگرها : یک بخش مهم در الگوریتم ژنتیک ایجاد کروموزوم های جدید موسوم به فرزند از طریق بعضی کروموزوم های قدیمی موسوم به والدین است این فرایند مهم توسط عملگر های ژنتیک صورت می گیرد به طور کلی این اعمال توسط دو عملگر عمده انجام می شود عملگر جهش و عملگر تقاطع عملاً عملگر ها بر حسب نوع مساله تعریف شده و کاملاً به توانایی تحلیل گر وابسته بوده و تجربی می باشند کارایی این عملگر ها در رسیدن به جواب بهینه در مسائل مختلف متفاوت است .
از مهمترین عملگر های GA میتوان مورد زیر را برشمرد.
* عملگرمعکوس کردن(Inversion)
* عمل حذف کردن((Deletion
* عمل جداسازی(segregation)
* عمل نقل مکان(Migration)
* عمل بخش بندی(Sharing)
* عمل ادغام (Cross over)
* عمل غالب شدن یا تسلط(Dominance)
* عمل کپی کردن((Duplication
معمولا دریک الگوریتم ساده ژنتیک تنها از سه عملگر تولید مثل، ادغام و جهش استفاده می شود.
۱-عملگر تولید مثل(Reproduction or Selection)
براساس نظریه حیات بهترین موارد باید انتخاب شوند تا نسل بعدی بهتری ایجاد نمایند به همین دلیل گاه به عملگر تولید مثل عملگر انتخاب(Selection )نیز گفته می شود.
ممکن است عوامل مختلفی به منظورانتخاب کروموزومهای والدتعریف شود ، امامعمولاازتابع برازندگی(Fitness)برای این منظور استفاده می کنند.هدف این عملگر انتخاب رشته هایی با تابع برازندگی بالا ازجمعیت فعلی و تولید فرزندان جدید ازآن ها وقرار دادن آن ها در یک مکان به نام استخر تولید مثل(Mating Pool)براساس یک فرم احتمالی است.هدف ازانتخاب بهترین والدها دست یافتن به فرزندان بهتراست اما ممکن است که این امر منجربه افتادن در نقاط بهینه محلی شودبنابراین درالگوریتم های ژنتیک درانتخاب کروموزوم های والد عامل تصادفی سازی نیز مورد توجه قرار می گیرد.
۲- عملگرادغام((cross over:
عملگر اصلی جهت تولید کروموزم های جدید در الگوریتم ژنتیک ، عملگر ادغام می باشد این عملگر مشابه همتای خودش در طبیعت افراد جدیدی تولید می نماید ، که از اجزای (ژن های) والدینش تشکیل می گردد.(لارهوینس و آرتس ۱۹۸۷) .
همان طور که توضیح داده شد وظیفه عملگر تولید مثل انتخاب مجموعه ای از بهترین کروموزوم ها به منظور تولید مثل است.برای تولید کروموزوم جدید می توان از عملگر ادغام استفاده نمود. دراین عملگر برای تولیدکروموزوم جدید از ادغام کروموزوم های والد استفاده می شود.روش کاراین عملگر به این شکل است که نقطه ای را درطول رشته انتخاب نموده وسپس مقداردورشته رااز محل انتخابی جابه جا می کند.

شکل ۲-۲ روش ادغام
البته بسته به این که از چه روشی برای کد کردن کروموزوم هااستفاده کرده باشیم روش کار عملگر می تواند متفاوت و حتی گاه بسیار پیچیده باشد. یکی از مواردی که عملکردالگوریتم ژنتیک تاثیر بسیاری دارد تعیین چگونگی انجام عملگر ادغام است. برای مثال فرض کنید که در مرحله تولید مثل دو کروموزوم زیر انتخاب شده اند. محل ادغام نیز برابر محل ۳ دررشته باشد دراین صوت دو رشته جدید به صورت زیر خواهند بود.
Chromosome A: 111|11 A*:11100
Chromosome B: 000|00 B*: 00011
در بعضی از رویکرد های جدید الگوریتم ژنتیک امکان جستجو در طول متغییر نیز ممکن شده است. در رابطه زیر بسته به مقادیر محلعمل ادغام تفاوت کرده و فرزند متفاوتی ایجاد می شود.

انواع روش های ادغام:
روش ادغام تک مکانی: در این روش دو کروموزوم والد از یک نقطه به منظور انجام عمل ادغام دچار شکست می شوند. مثال قبل از این روش است.
روش ادغام دو نقطه ای(Tow point cross over): در این روش دو کروموزوم والد از دو نقطه به منظور انجام عمل ادغام دچار شکست می شوند. به مثال زیر دقت نمایید.
Chromosome A:

دسته‌ها: No category

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