الگوریتم ژنتیک یا Genetic Algorithm چیست ؟
الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است. این روش در سال 1970 توسط John Holland معرفی گردید. روشهایی که بر مبنای تکامل جانوران تدوین شده اند، الگوریتمهای تکاملی یا همان Evolutionary Algorithms نیز خوانده می‌شوند.
یک GA برای حل یک مسئله، مجموعه بسیار بزرگی از راه حل‌های ممکن را تولید می‌کند. هر یک از این راه حل‌ها با استفاده از یک “تابع تناسب” مورد ارزیابی قرار می‌گیرند. آن‌گاه تعدادی از بهترین راه حل‌ها باعث تولید راه حل‌های جدیدی می‌شوند که این کار باعث تکامل راه حل‌ها می‌گردد. بدین ترتیب، فضای جستجو در جهتی تکامل پیدا می‌کند که به راه حل مطلوب برسد. در صورت انتخاب صحیح پارامترها، این روش می‌تواند بسیار موثر عمل نماید.
ویژگیهای الگوریتم های ژنتیک :
– الگوریتمهای ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند می‌تواند به‌کار گرفته شود.
– همچنین در مسایلی با فضای فرضیه پیچیده که تاثیر اجزای آن در فرضیه کلی ناشناخته باشند میتوان از GA برای جستجو استفاده نمود.
– برای discrete optimization بسیار مورد استفاده قرار میگیرد.
– الگوریتمهای ژنتیک را میتوان به‌راحتی به‌صورت موازی اجرا نمود. از این رو میتوان رایانه‌های ارزان قیمت‌تری را به‌صورت موازی مورد استفاده قرار داد.
– امکان به تله افتادن این الگوریتم در کمینه محلی کمتر از سایر روش‌هاست.
– از لحاظ محاسباتی پرهزینه هستند.
– تضمینی برای رسیدن به جواب بهینه وجود ندارند.
کاربردهای الگوریتم ژنتیک :
کاربرد الگوریتمهای ژنتیک بسیار زیاد می‌باشد و میتوان گفت در اکثر علوم مورد استفاده قرار میگیرد. اما اگر بخواهیم آنها را طبقه بندی کنیم خواهیم داشت :
– optimization
– automatic programming
– machine learning
– economics
– operations research
– ecology
– studies of evolution and learning, and social systems
نحوه پیاده سازی الگوریتم ژنتیک :
روش متداول پیاده‌سازی الگوریتم ژنتیک به این ترتیب است که مجموعه ای از فرضیه‌ها که population نامیده می‌شود تولید و به‌طور متناوب با فرضیه‌های جدیدی جایگزین می‌گردد. در هر بار تکرار، تمامی فرضیه‌ها با استفاده از یک تابع تناسب یا Fitness مورد ارزیابی قرار داده می‌شوند. آن‌گاه تعدادی از بهترین فرضیه‌ها با استفاده از یک تابع احتمال انتخاب شده و جمعیت جدید را تشکیل می‌دهند. تعدادی از این فرضیه‌های انتخاب شده به‌همان صورت مورد استفاده واقع شده و مابقی با استفاده از اپراتورهای ژنتیکی نظیر Crossover و Mutation برای تولید فرزندان به‌کار می‌روند.
یک الگوریتم GA دارای پارامترهای زیر است:
Fitness, Fitness_threshold, p, r, m
Fitness: تابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت می‌دهد.
Fitness_threshold: مقدار آستانه که شرط پایان را معین می‌کند.
p: تعداد فرضیه‌هایی که باید در جمعیت در نظر گرفته شوند.
r: درصدی از جمعیت که درهرمرحله، توسط الگوریتمcrossover جایگزین می‌شوند.
m: نرخ mutation
بهینه‌سازی چینش حروف فارسی بر روی صفحه کلید با استفاده از الگوریتم ژنتیک :
به‌دست آوردن چینش بهینه حروف فارسی بر روی صفحه کلید در درازمدت برای کسانی که با تایپ کردن متون فارسی درگیر هستند، بسیار مفید خواهد بود. یک الگوریتم تکاملی می‌تواند با توجه به یک تابع تناسب که میزان راحت تایپ کردن متون فارسی را برای یک چینش ارائه می‌دهد, در فضای چینش های حروف فارسی بر روی صفحه کلید، جستجو کرده و چینش بهینه را به‌دست آورد.
در این مساله هندسه صفحه‌کلید ثابت است و ما می‌خواهیم که تعداد 33 نشانه که متشکل از 32 حرف الفبای فارسی بعلاوه حرف همزه “ء” است را بر روی سه ردیف صفحه‌کلید که به‌ترتیب دارای 12، 11و 10 کلید هستند، قرار دهیم. هدف این مساله به‌دست آوردن چینشی از این نشانه ها بر روی این کلید‌ها است, به طوری که این چینش طوری باشد که کاربر هنگام استفاده از صفحه کلید برای تایپ حروف فارسی، احساس راحتی بیشتری نسبت به کار با بقیه چینش‌ها داشته باشد.
برای حل مساله از یک الگوریتم ژنتیک استفاده شده است. تابع تناسب موجود در این الگوریتم ژنتیک، میزان راحتی یا سختی استفاده از یک چینش را محاسبه می‌کند. در هر نسل، عملگرهای ژنتیکی بر روی جمعیت موجود که چینش‌های مختلفی از حروف فارسی بر روی صفحه کلید هستند، اعمال می‌شوند و جامعه به سمتی سوق داده می‌شود که مقدار تابع تناسب به ازای اعضای آن به کمینه مقدار خود برسند. میزان تناسب هر عضو از جامعه که در واقع یک چینش حروف فارسی بر روی صفحه کلید است، با اعمال تابع تناسب بر متنی که از مطالب چند سایت خبری فارسی زبان تهیه شده است، به دست می آید.
شما میتوانید مطالب بیشتری را با جستجو در فضای وب و همچنین رفتن به این لینک در این رابطه مطالعه نمایید. همچنین میتوانید پاورپوینت مفصلی را در این باره از این لینک دانلود نمایید.
