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

الگوریتم های ژنتیک (به انگلیسی: Genetic algorithm) تکنیک جستجو در علم رایانه برای یافتن راه حل تقریبی برای بهینه سازی مدل، ریاضی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک های زیست شناسی فرگشتی مانند وراثت، جهش زیست شناسی و اصول انتخابی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می شود. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند. در مدل سازی الگوریتم ژنتیک یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود دارای ورودی هایی می باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه حل ها تبدیل می شود سپس راه حل ها به عنوان کاندیداها توسط تابع برازش یا تابع برازندگی (Fitness Function) مورد ارزیابی قرار می گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می یابد. به طور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش های آن به صورت فرایندهای تصادفی انتخاب می شوند که این الگوریتم ها از بخش های تابع برازش، نمایش، انتخاب و تغییر تشکیل می شوند.

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

الگوریتم ژنتیک (GA)، یک الگوریتم جستجوی ابتکاری انطباق پذیر است که بر مبنای ایده های تکاملی انتخاب طبیعی و ژنتیک طراحی شده است. به این ترتیب این الگوریتم نمایانگر استفاده ی هوشمند از یک الگوریتم جستجوی تصادفی برای حل مسائل بهینه سازی می باشد. اگرچه الگوریتم های ژنتیک از پدیده هایی تصادفی استفاده می کنند اما خودشان به هیچ وجه تصادفی نیستند بلکه، آن ها از اطلاعات تاریخی موجود برای هدایت عملیات جستجو به منطقه ای با عملکرد بهتر در فضای جستجو استفاده می کنند. روش های اصلی الگوریتم ژنتیک به گونه ای طراحی شده اند تا بتوانند فرآیند های ضروری برای تکامل در سیستم های طبیعی را شبیه سازی کنند. از جمله مهمترین این فرآیند ها، آن هایی هستند که از قوانینی که اولین بار توسط چارلز داروین و با نام “بقای اصلح”(Survival Of The Fittest) مطرح شد، پیروی می کنند. علت این امر آن است که در طبیعت، رقابت میان موجودات زنده برای دستیابی به منابع کمیاب منجر به غلبه اصلح ترین موجودات بر موجودات ضعیف تر می شود.

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

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

روش های نمایش

قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنوم ها به زبان کامپیوتر باید به کار رود. یکی از روش های معمول کد کردن به صورت رشته های باینری است: رشته های ۰ و ۱. یک راه حل مشابه دیگر کد کردن راه حل ها در آرایه ای از اعداد صحیح یا اعداد اعشاری است. سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است. خاصیت هر سه روش این است که آن ها تعریف سازنده ای را که تغییرات تصادفی در آن ها ایجاد می کنند را آسان می کنند: ۰ را به ۱ و برعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک به صفر یا برعکس. یک روش دیگر که توسط John Koza توسعه یافت، برنامه نویسی ژنتیک است؛ که برنامه ها را به عنوان شاخه های داده در ساختار درخت نشان می دهد. در این روش تغییرات تصادفی می توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

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

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

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

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه سازی های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم های او به نسل بعدی منتقل می شوند. هر ژن در این کروموزوم ها نماینده یک خصوصیت است. به عنوان مثال ژن ۱ می تواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی دهد. در واقع به صورت هم زمان دو اتفاق برای کروموزوم ها می افتد. اتفاق اول جهش (Mutation) است. «جهش» به این صورت است که بعضی ژن ها به صورت کاملاً تصادفی تغییر می کنند. البته تعداد این گونه ژن ها بسیار کم می باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است؛ مثلاً ژن رنگ چشم می تواند به صورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه ای بوده اند. علاوه بر «جهش» اتفاق دیگری که می افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به «جهش» رخ می دهد چسبیدن دو کروموزوم از طول به یکدیگر و تبادل برخی قطعات بین دو کروموزوم است. این مسئله با نام Crossover شناخته می شود. این همان چیزیست که باعث می شود تا فرزندان ترکیب ژن های متفاوتی را (نسبت به والدین خود) به فرزندان خود انتقال دهند.

روش های انتخاب الگوریتم ژنتیک

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

• انتخاب Elitist

مناسب ترین عضو هر اجتماع انتخاب می شود.

• انتخاب Roulette

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

• انتخاب Scaling

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

• انتخاب Tournament

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

بعضی از روش های دیگر عبارتند از:

1. Hierarchical Selection
2. Steady-State Selection
3. Rank Selection

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

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است: اول روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. به شکل سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسه ها.نمایش داده می شود.دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می شود. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می باشد. این روش,بر مبنای نظریه تکامل تدریجی و ایده های بنیادین داروین پایه گذاری شده است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می شود مجموعه ای از پارامترهای هدف بصورت اتفاقی تولید می شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد. بصورت متداول سه معیار به عنوان معیار توقف شمرده می شود: ۱. زمان اجرای الگوریتم ۲. تعداد نسلهایی که ایجاد می شوند ۳. همگرایی معیار خطا

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

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