دانلود کد متلب الگوریتم ژنتیک

الگوریتم ژنتیک

الگوریتم ژنتیک (GA) یک روش برای حل مسائل بهینه سازی محدود و نامحدود بر اساس یک فرآیند انتخاب طبیعی است که تقلید تکامل بیولوژیکی می باشد.

پنج فاز و مرحله برای الگوریتم ژنتیک در نظر گرفته می‌شود:

1.     جمعیت اولیه
2.     عملگر سازگاری
3.     انتخاب
4.     ترکیب
5.     جهش

جمعیت اولیه (Initial population)

این فرایند با مجموعه‌ای از نمونه های اولیه و راه حل‌ها آغاز می‌شود که آن‌ها را جمعیت (population) می‌نامیم هر نمونه از این جمعیت یک راه حل برای مشکلی است که ما می‌خواهیم آن را حل کنیم. در مورد جمعیت در الگوریتم ژنتیک باید چند نکته را در نظر داشت:

تنوع بین جمعیت باید حفظ شود و از همگرایی زودرس جواب‌ها به یک جواب واحد خودداری شود (این کار توسط عمل‌گر‌های جهش صورت می‌گیرد)

اندازه جمعیت نباید از یک میزانی فراتر برود چراکه این کار سبب کندی عملکرد الگوریتم ژنتیک می‌شود همچنین اندازه جمعیت نباید آنقدر کوچک باشد که نتوان دو والد موثر را از بین  این جمعیت انتخاب کرد بنابراین یک اندازه بهینه برای جمعیت نیاز است که برای تعیین این اندازه نیاز به سعی و خطا دارد.

هر نمونه این جمعیت به وسیله‌ی مجموعه‌ای از پارامترها توصیف و طبقه بندی می‌شود که ما به هر یک از این پارامترها ژن (Genes) می‌گوییم.

این ژن‌ها به هم می‌پیوندند و تولید یک رشته به نام کروموزوم (Chromosome) می‌کنند که تمام ویژگی‌های راه حل ما را ارائه می‌دهد.

در الگوریتم ژنتیک ژن‌های هر راه حل به وسیله یک حرف الفبایی ارائه می‌شوند که این رشته‌ها معمولا به صورت صحیح یا اعشاری بیان می‌شوند که مهم‌ترین آن‌ها ارائه با سیستم  دودویی (binary) است.

عملگر سازگاری (Fitness function)

عملگر سازگاری مشخص می‌کند که هر نمونه این جامعه به چه میزان قابلیت سازگاری با محیط را دارد (توانایی هر نمونه برای رقابت با دیگر نمونه ها)، ما با این کار به هر یک از نمونه ها امتیازی را اختصاص می‌دهیم و احتمال اینکه یک نمونه از جامعه برای ادامه نسل انتخاب شود به این امتیاز که بر اساس سازگاری به  آن اختصاص داده می‌شود بستگی دارد. عملگر سازگاری باید دو ویژگی مهم را که در ادامه به آن‌ها اشاره می‌شود، داشته باشد:

این عملگر باید به اندازه کافی برای انجام محاسبات سریع باشد.

همچنین باید بتواند به صورت کمی میزان سازگاری راه حل‌های اولیه و همچنین راه حل‌های به وجود آمده از ترکیب دو راه حل والد را به داشته باشد.

انتخاب (Selection)

انتخاب فرآیند گزینش والد‌های مناسبی است که بتوانند با هم ترکیب شوند و نسل‌های بعدی را به وجود آورد. در این مرحله ما بهترین و سازگارترین نمونه جامعه را انتخاب می‌کنیم و به آن‌ها اجازه می‌دهیم که ژن‌های خود را به نسل بعد انتقال دهند. دو جفت نمونه از این جمعیت  برحسب بیش‌ترین سازگاری انتخاب می‌شوند که ما آن‌ها را والد می‌نامیم. افراد با بالاترین سازگاری شانس بیش‌تری برای انتخاب شدن و ادامه نسل دارند.

ترکیب (Crossover)

ترکیب مهم‌ترین و اساسی‌ترین فاز و مرحله الگوریتم ژنتیک است. هر کدام از این جفت والدها با هم ترکیب می‌شوند و نمونه جدید به وجود می‌آورند نقطه بازترکیب به صورت تصادفی در داخل ژن‌ها انتخاب می‌شود. نمونه های جدید با انتقال جابه‌جایی ژن‌های والد و انتقال یک ژن از والد اول به والد دوم و برعکس به وجود می‌آیند. این جابجایی از ابتدای ژن‌ها تا نقطه بازترکیب به صورت متناظر صورت می‌گیرد و فرزندان جدید به جمعیت اضافه می‌شوند.

جهش (Mutation)

پس از شکل گیری نمونه های جدید بعضی از ژن‌های آن‌ها دچار جهش می‌شوند که احتمال تصادفی بودن این جهش کم است. هدف اصلی جهش نگه داشتن تنوع و تمایز میان جمعیت و جلوگیری از همگرا شدن زودهنگام جمعیت به یک نوع خاص است.

خاتمه الگوریتم

الگوریتم زمانی خاتمه می‌یابد که جمعیت به یک نمونه و یک راه حل خاص همگرا شده باشد. یعنی در واقع نمونه های جدید تفاوت چشم‌گیری با نمونه های اولیه خود نداشته باشند. در این صورت می‌توان گفت که الگوریتم ژنتیک مجموعه‌ای از راه حل‌ها را برای مشکل ما فراهم آورده است.

هر جمعیت یک اندازه معین و خاصی دارد و زمانی که نسل جدید شکل می‌گیرد آن‌هایی که کم‌ترین سازگاری را دارند از بی می‌روند و فضایی را برای نمونه های جدید به وجود می‌آورند.

این توالی مراحل و فازها تکرار می‌شود تا نمونه هایی را به وجود بیاورد که از نسل قبل خود بهتر و سازگارتر باشند.الگوریتم ژنتیک
الگوریتم ژنتیک (GA) یک روش برای حل مسائل بهینه سازی محدود و نامحدود بر اساس یک فرآیند انتخاب طبیعی است که تقلید تکامل بیولوژیکی می‌باشد.

برای دانلود کد متلب کلیک کنید