خط مهندسی
مجله ی آنلاین مهندسی

الگوریتم ژنتیک قدرت بخش هوش مصنوعی برای رسیدن به دنیایی هیجان انگیز

2 12,835

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

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

واقعیت در پس الگوریتم های ژنتیک

بهتر است که ابتدای بحث را با نقل قولی از چارلز داروین آغاز کنیم:

“نه قوی ترین گونه و نه باهوش ترین آنها زنده می مانند بلکه گونه ای به حیات خود ادامه می دهد که با تغییرات سازگار شود.”

شاید این سوال پیش آید که این گفته داروین چه ارتباطی با الگوریتم ژنتیک خواهد داشت؟ در پاسخ باید بگوییم که مفهوم کلی الگوریتم ژنتیک بر پایه این جمله داروین بنا شده است.

جهت درک بهتر این موضوع، بیایید که نگاهی به یک مثال ساده بیندازیم:

تصور کنید که شما رهبری یک کشور را بر عهده دارید و به برای اینکه شهر خود را از اتفاقات بد مصون دارید، سیاستی به شرح زیر را پیاده سازی می کنید:

شما افراد خوب را انتخاب می کنید و از آنها می خواهید که با تولید مثل، نسل خود را گسترش دهند. در ادامه نسل این افراد ادامه پیدا می کند.

حال شما جمعیتی از افراد خوب در کشور خود دارید.

اگرچه این مثال در واقعیت امکان پذیر نیست اما به درک بهتر موضوع کمک می کند. بنابراین ما ورودی (یعنی جمعیت) را به گونه ای تغییر دادیم که بازده بهتری بگیریم (یعنی یک کشور بهتر).

در ادامه به ارزیابی مفاهیم دقیق تر و ارتباط آنها با یکدیگر خواهیم پرداخت.

 

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

 

مفاهیم بیولوژیکی

 

همه ما با این جمله از دوران تحصیل خود آشنا هستیم “سلول ها واحدهای ساختمان اصلی همه موجودات زنده هستند.”

همانطور که میدانید که در هر سلول، مجموعه ای از کروموزم های یکسان وجود دارد و کروموزوم ها نیز اساسا رشته های DNA هستند. به طور کلی این کروموزوم ها در مفهوم “باینری” به صورت رشته های ۰ و ۱ نمایش داده می شوند.

کروموزوم ها نیز متشکل از ژن هایی هستند که به نام بلوک DNA شناخته می شوند، جایی که هر ژن یک ویژگی خاص مانند رنگ مو یا رنگ چشم را رمزگذاری می کند. حال که با مفهوم الگوریتم ژنتیک از دیدگاه زیست شناسی آشنا شدیم، نوبت آن است که بدانیم مفهوم الگوریتم ژنتیک چیست؟

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

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

  1. اول از همه ما جمعیت اولیه خود را از هموطنان خود انتخاب کردیم.
  2. در ادامه نیز تابعی جهت طبقه بندی فرد خوب یا بد ارائه دادیم و افراد خوب را برای جفت گیری انتخاب کردیم و بدین ترتیب رشته های کروموزومی آنها تکثیر پیدا کرد.
  3. در نهایت افراد دارای کروموزوم های خوب جایگزین افراد بد از جمعیت اولیه شدند و این روند تکرار شد.

عملکرد الگوریتم ژنتیک نیز اساسا به این صورت است و در واقع سعی دارد که تا حدودی انسان را به تکامل سوق دهد.

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

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

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

این الگوریتم شامل مراحل مختلفی می شود که در هر یک از این مراحل اتفاق به خصوصی رخ می دهد و بدین ترتیب ادامه چرخه امکان پذیر می‌شود.

۱- ارزش دهی آغازی

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

ما به خوبی می دانیم که کروموزوم ها رشته هایی مطابق با اصل “باینری” هستند که در این مسئله عدد ۱ به معنی آن است که آیتم مورد نظر وجود دارد و ۰ به معنای آن است که آیتم مورد نظر از دست رفته است.

۲- تابع برازندگی

تابع برازندگی، عملکردی است که از طریق آن “مقدار برازندگی” هر یک از اعضای تشکیل دهنده جمعیت اولیه تعیین می شود. پس از اینکه مقدار برازندگی اعضا مشخص شد، جواب های کاندید انتخاب می شود.

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

در الگوریتم‌های ژنتیک، برازندگی به عنوان معیاری شناخته می‌شود که به تشخیص داده‌های خوب یا بد می‌پردازد یا احتمال تکثیر داده‌های موجود در جمعیت را نشان می‌دهد.

 

۳- انتخاب

در این مرحله از الگوریتم ژنتیک، نوبت آن است که کروموزوم هایی که قصد تکثیر رشته های آنها را داریم، انتخاب کنیم. تصور کلی افراد در این مرحله آن است که ما باید کروموزم های برازنده را انتخاب کنیم و اجازه دهیم که این رشته های DNA تکثیر پیدا کنند.

اما این عملکرد اشتباه است، اما به چه دلیل؟ اتخاذ چنین رویکردی منجر به آن خواهد شد که در چند نسل آینده، کروموزوم ها شباهت بیشتری نسبت به یکدیگر پیدا کنند و بدین ترتیب تنوع به طور چشمگیری کاهش پیدا خواهد کرد.

به همین دلیل است که ما از ” انتخاب مبتنی بر چرخ رولت” استفاده می کنیم. در این روش معیار انتخاب یک رشته از کروموزوم، در تناسب با برازندگی آن رشته ارزیابی می شود.

اما چرخ رولت به چه معناست؟

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

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

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

۴- ترکیب یا آمیزش

حال که به کروموزم های برازنده انتخاب شدند، نوبت آن است که رشته ها یا کروموزم های مناسب تری تولید شوند اما ترکیب کروموزوم ها به چه صورت رخ خواهد داد؟

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

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

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

تعریف کروموزم مادر و فرزند

کروموزوم هایی که در عمل ترکیب شرکت می کنند را کروموزوم های “مادر” و کروموزوم هایی که در پایان این مرحله تولید می شوند را کروموزوم ” فرزند” می نامند. انتخاب کروموزوم های مادر خوب، منجر به تولید کروموزوم های فرزند بهتر می شود، با این حال هیچ تضمینی در این زمینه وجود ندارد.

توابع مختلف آمیزش

اما آیا جای نگرانی در رابطه با این مسئله وجود دارد؟ در پاسخ باید بگوییم که خیر. کروموزوم های خوب تولید شده در اثر ترکیب، انتخاب می شوند و در نسل های بعدی تکثیر خواهند شد و کروموزوم های نامناسب نیز در اثر تکثیر کمتر به مرور ناپدید می شوند.

توابع مختلفی جهت ترکیب یا آمیزش کروموزوم های وجود دارد که ۲ مورد از مهم ترین آنها شامل موارد زیر هستند:

  • عملگر یک نقطه ای
  • عملگر دو نقطه ای

بهتر است که نگاهی به این دو عملگر داشته باشیم و بدین ترتیب به درک بهتری از نحوه آمیزش یا ترکیب دست پیدا کنیم.

 

عملگر یک نقطه ای

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

در این روش دو کروموزم والد، دو فرزند با ژن های متفاوت نسبت به همدیگر و والدین خواهیم داشت. این نوع عملگر بیشتر برای کروموزوم هایی با طول زنجیر کوتاه کاربرد دارد.

عملگر دو نقطه ای

عملگر دو نقطه ای شباهت بسیاری به عملگر تک نقطه ای دارد، با این تفاوت که در عملگر دو نقطه ای؛ دو”محل ترکیب” خواهیم داشت. بنابراین در این نوع عملگر، ژن های قرار گرفته در قسمت میانی بین دو محل ترکیب، با یکدیگر جابجا خواهند شد.

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

۵- جهش

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

بنابراین چنین پدیده ای تحت عنوان “جهش” شناخته می شود که به صورت تصادفی در کروموزوم ها رخ می دهد و در نتیجه منجر به ایجاد تنوع در جمعیت می شود.

اما در اینجا نکته مهمی وجود دارد، رشته های کروموزومی جهش یافته مجددا تحت تاثیر عملگر برازندگی قرار خواهند گرفت و چنانچه از برازندگی مورد نظر برخوردار باشند، در جمعیت گسترش بیشتری پیدا خواهند کرد.

جهش در الگوریتم ژنتیک

اما شاید این سوال پیش آید که برازندگی کروموزوم های جدید چگونه تعیین می شود؟

اساسا تعیین برازندگی یک کروموزوم براساس معیارهای مختلفی تعیین می شود که در ادامه ۳ مورد از مهم ترین آنها را مطرح خواهیم کرد:

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

 

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

حال که به درک مناسبی از الگوریتم ژنتیک دست پیدا کردید، نوبت آن است که به برخی از کاربردهای آن در علم داده بپردازیم.

انتخاب یک ویژگی

در هنگام انتخاب یک ویژگی به خصوص در زمینه دیتا (داده) چگونه عمل می کنید؟ به طور کلی افراد ابتدا نگاهی به اهمیت ویژگی های و برخی مدل ها خواهند داشت و خصوصیاتی که از اهمیت بیشتری برخوردار هستند را انتخاب خواهند کرد.

به نظر شما آیا روش بهتری برای مقابله با این شرایط وجود دارد؟ در واقع پیشرفته ترین نوع الگوریتم جهت انتخاب یک ویژگی به خصوص، الگوریتم ژنتیک است.

جهت انتخاب یک ویژگی، تنها کافی است که از اعداد ۰ و ۱ استفاده کنیم و در نهایت تابع برازندگی را تعیین خواهیم کرد. تعیین تابع برازندگی از اهمیت بالایی برخوردار است و هر چه این تابع دقیق تر انتخاب شود، مجموعه کروموزوم تولیدی ما مناسب تر خواهد بود.

اجرای برنامه TPOT

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

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

برنامه های کاربردی در دنیای واقعی

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

۱.مهندسی طراحی

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

۲.مسیریابی و حمل و نقل

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

۳. رباتیک

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

نتیجه گیری

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

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

 

 

2 نظرات
  1. محمد می گوید

    ممنون از ارائه مطلبتون،خیلی خلاصه و خوب جمع بندی شده .
    و اجازه می خواستم که این مطالبتون رو به همین نحو در کلاس ارائه کنم .
    با تشکر

  2. زهرا می گوید

    عالی گفتید عالی…….

نظر شما درباره این مطلب

آدرس ایمیل شما منتشر نخواهد شد.