الگوریتم ژنتیک چیست و چه کاربرد هایی دارد؟

الگوریتم ژنتیک یا GA یک الگوریتم بهینه سازی و فراابتکاری می باشد، از این جهت که یک ابزار و الگوریتم ، برای حل مسئله های بهینه سازی می باشد. این الگوریتم اولین بار توسط جان هلند (Jan Holand) در سال 1970 میلادی یعنی سال 1349 شمسی معرفی شد و در دهه 60 و 70 میلادی با تلاش وی و شاگردانش در دانشگاه میشیگان آمریکا توسعه پیدا کرد.

جان هلند با تکیه بر نظریه تکامل وراثتی ، نظریه انتخاب طبیعی و نحوه انتقال خصوصیات از والدین به فرزندان ،در انسان، و فرموله کردن این رفتارها ، به یک الگوریتم برای حل مسئله رسید که نام آن را GeneticAlgorithm  گذاشت. در سال 1992 مقاله ای توسط دی جانگ، با عنوان “الگوریتم وراثتی بهینه ساز تابع نیست ” ارائه شد. که بیان میکرد که این  الگوریتم فقط یک بهینه ساز برا حل توابع ریاضی نیست بلکه توانایی بسیاری برای حل مسائل مختلف دنیای واقعی دارد.

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

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

الگوریتم ژنتیک، تعدادی راه حل اولیه برای مسئله مورد نظر بصورت تصادفی می سازد ، که به هر راه حل به اصطلاح کروموزوم گفته میشود و به مجموعه همه کروموزوم ها یا راه حل ها اصطلاحا جمعیت گفته میشود. بعد از اینکه یک جمعیت بصورت تصادفی ساخته شد، الگوریتم ژنتیک میزان خوب بودن هر یک از کروموزوم های جمعیت را بررسی میکند( با تابع شایستگی ) سپس سعی میکند طی سه مرحله بنام های "انتخاب" ، "ترکیب" و "جهش" راه حل ها را بهبود دهد و راه حل های جدیدی را تولید کند.

در این الگوریتم از یک سری مفاهیم استفاده میشوند که عبارتند از :

• ژن (Gene)
• کروموزوم (Chromosome )
• آلل (Allele)
• جمعیت (Population)
• تابع شایستگی یا تابع برازش (Fitness Function)
• تولید مثل یا Reproduction   
• عملگر انتخاب یا Selection
• عملگر ترکیب یا Crossover
• عملگر جهش یا Mutation
• همگرایی یا Convergence

الگوریتم ژنتیک در متلب به چه صورت است و چه کاربرد هایی دارد؟

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

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

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

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

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

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

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

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

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

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

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

انتخاب (Selection)

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

ترکیب (Crossover)

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

جهش (Mutation)

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

جمع بندی

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

نویسنده مقاله: سمانه خان بیگی کارشناس دپارتمان مهندسی پزشکی موسسه پارس پژوهان