در این مقاله، به معرفی تاریخچه الگوریتم ژنتیک خواهیم پرداخت. الگوریتم ژنتیک یکی از الگوریتم‌های بهینه‌سازی هوشمند در رده الگوریتم‌های فرا ابتکاری از نوع تکاملی می‌باشد. این الگوریتم محبوبیت فوق‌العاده‌ای در بین علاقه مندان و محققان بهینه سازی دارد و در اکثر مقالات علمی در حوزه بهینه سازی بعید است که اسمی از الگوریتم ژنتیک برده نشود. این الگوریتم به عنوان یک روش پایه و استاندارد در حوزه بهینه سازی هوشمند استفاده می‌شود.
مقدمه
برای ارائه یک توضیح کامل درباره تاریخچه الگوریتم ژنتیک (Genetic Algorithm)، می‌توانیم از شروع شکل‌گیری ایده‌ها تا پیشرفت‌های کلیدی در طول زمان صحبت کنیم. در ادامه، به طور جامع و کامل درباره تاریخچه الگوریتم ژنتیک که برای استفاده محتوای آموزشی مناسب باشد صحبت می‌کنیم.
تاریخچه الگوریتم ژنتیک
در حدود سال‌های ۱۸۵۰ گریگور مندل تئوری خویش مبنی بر تعریف ژن‌ها را بنا نهاد. ژن‌ها کدهای اطلاعاتی هستند که در بدن موجودات زنده وجود دارند. هر ژن یک عامل تعیین خصوصیت ویژه‌ای از موجود زنده است. مجموعه کامل ژن‌ها توصیف‌کننده مشخصات و عوارض بدن موجود زنده می‌باشد. این فرضیه تئوری ژنتیک می‌باشد که منشا اولیه در معرفی تاریخچه الگوریتم ژنتیک است.
ژن‌ها به طور عملی توسط ملکولهای پیچیده‌ای به نام DNA و یا کروموزم کد شده‌اند. هر سلول در بدن یک ارگانیسم زنده، یک کپی از همه کرموزم‌های مختلف را در خود دارد. در نتیجه هر سلول یک نمونه کامل اطلاعاتی از کل ارگانیزم را با خود حمل می‌کند. در طول رشد یا تکامل یک ارگانیسم، ملکولهای DNA برای کپی برداری و انتقال اطلاعات از سلول والد یا سلول‌های والدین به سلول‌های جدید استفاده می‌شوند.
چند سال بعد از ارائه تئوری ژنتیک، چارلز داروین در سال ۱۸۵۹، نظریه «منشاء انواع» را منتشر نمود که با نام نظریه داروین معروف شده است. در این تئوری او به شرح و بسط نحوه تکامل موجودات زنده در قالب یک پدیده طبیعی می‌پردازد. تئوری ژنتیک مندل می‌توانست کمک بزرگی به داروین بنماید، ولی متأسفانه داروین از مفاد آن بی‌اطلاع بود. به هر حال، یک مشخصه مهم تئوری، تفوق بیشتر و شانس بقای انواع موجودات زنده قویتر یا سازگارتر با محیط، در طول زندگی و حتی نسل‌های بعدی می‌باشند.
به عبارت ساده، قوی‌بنیه‌ها و سازگارترها زنده می‌مانند و این ویژگی را به فرزندان خود منتقل می‌کنند. داروین به این مسئله، عبارت و اصطلاح «انتخاب طبیعی» اطلاق می‌کند. بدین ترتیب، یک رشد تکاملی سریع از موجوداتی خواهیم داشت که بهتر از والدین و نسل‌های قبل‌ترشان با محیط خودشان تعامل داشته و خو می‌گیرند.
جان هلند ، دانشمند علوم کامپیوتر و روانشناس، مبدع شاخه‌ای از علوم کامپیوتربه نام «سیستم‌های تطبیقی پیچیده» می‌باشد. او در کتاب خود یک سیستم تطبیقی یا وفقی را چنین شرح می‌دهد که سیستم مربوطه به طور یکنواخت و پیوسته خودش را تغییر می‌دهد تا از محیط اطراف خود بهتر استفاده کند. هُلند در خلال توسعه تئوری خود برای سیستم‌های تطبیقی به شرح اپراتورهای ژنتیک برای تغییر حالت سیستم می‌پردازد. گر چه کتاب هُلند، اختصاصاً برای سیستم‌های تطبیقی نگاشته شده‌است ولی یک مشخصه بسیار مهم دارد و آن ابداع و معرفی الگوریتم ژنتیک می‌باشد.
روند تکامل الگوریتم ژنتیک
همانطور که در بخش‌های قبل به تاریخچه الگوریتم ژنتیک اشاره شد می‌توان ۴ دوره یا نسل برای ظهور و استفاده از الگوریتم ژنتیک را به صورت زیر بخش بندی یا تقسیم بندی کرد:
۱- آغاز ایده‌ها — دهه ۱۹۵۰ و ۱۹۶۰
ایده اصلی الگوریتم‌های الهام‌گرفته از طبیعت به سال‌های میانی قرن بیستم بازمی‌گردد. در این دوران، دانشمندانی همچون آلن تورینگ و جان هالند (John Holland) به بررسی امکان شبیه‌سازی فرایندهای طبیعی برای حل مسائل محاسباتی پرداختند. آلن تورینگ در سال ۱۹۵۰ در مقاله معروف خود با عنوان Computing Machinery and Intelligence ایده‌هایی پیرامون ماشین‌های یادگیرنده ارائه کرد که بعداً الهام‌بخش الگوریتم‌های تکاملی شد.
۲- تولد الگوریتم ژنتیک — دهه ۱۹۷۰
پایه‌گذار اصلی الگوریتم ژنتیک را می‌توان جان هالند دانست. او در سال ۱۹۷۵ کتابی با عنوان Adaptation in Natural and Artificial Systems منتشر کرد که در آن، اصول الگوریتم ژنتیک به صورت رسمی مطرح شد. هالند و دانشجویانش در دانشگاه میشیگان با توسعه این ایده‌ها، اولین پیاده‌سازی‌های عملی از الگوریتم ژنتیک را انجام دادند.
۳- توسعه و گسترش — دهه ۱۹۸۰ و ۱۹۹۰
در دهه‌های ۱۹۸۰ و ۱۹۹۰، الگوریتم ژنتیک به عنوان ابزاری قدرتمند برای حل مسائل بهینه‌سازی در حوزه‌های مختلف مانند مهندسی، علوم کامپیوتر، اقتصاد و زیست‌شناسی مورد استفاده قرار گرفت. پژوهشگران شروع به ترکیب الگوریتم ژنتیک با روش‌هایی مانند شبکه‌های عصبی مصنوعی و منطق فازی کردند. الگوریتم‌های ژنتیکی چندهدفه (Multi-objective GAs) و نسخه‌های موازی (Parallel GAs) نیز در این دوره مطرح شدند.
۴- الگوریتم ژنتیک در قرن ۲۱
در قرن بیست و یکم، با پیشرفت رایانه‌ها و رشد علم داده، کاربرد الگوریتم ژنتیک گسترش یافته است. امروزه این الگوریتم‌ها در حوزه‌هایی چون یادگیری ماشین، بهینه‌سازی مسیر، طراحی مهندسی، برنامه‌ریزی تولید و حتی هنرهای دیجیتال کاربرد دارند. این ۴ دوره را می‌توان به عنوان تاریخچه الگوریتم ژنتیک در نظر گرفت.
ژنتیک بیولوژیکی چیست؟
بسیاری از اصطلاحات و ترمینولوژی الگوریتم ژنتیک برخاسته از پدیده‌های بیولوژیکی می‌باشد. فهم بسیاری از این پدیده های دیگر، میتواند کمک بزرگی به فهم، تعمیم یا بهبود الگوریتم‌های موجود ژنتیک نماید. به هر موجودی که قابلیت تکثیر، ترمیم و مرگ دارد، موجود زنده اطلاق می‌کنیم. به مجموعه‌ای از موجودات زنده از یک نژاد خاص در یک اقلیم خاص را جمعیت مینامیم. هر موجود زنده در یک جمعیت، موسوم به فرد می‌باشد.
هر فرد بطور مقتضی با کدهای مدفون در آن، موسوم به کروموزوم‌ها رشد می‌کند و بقاء دارد یا زندگی می‌کند. کروموزوم‌ها معرف مشخصه‌های طبیعی یک فرد هستند. به مجموعه کروموزوم‌های یک فرد، ژنوم یا ژنوتایپ می‌گویند، چون معرفه ذات و نوع فرد هستند. در حالیکه به شیوه رشد یا بقاء، فنو تایپ می‌گویند، چون مفهومی اکتسابی و از جنس پدیده‌شناختی و وقوعی می‌باشد. در تاریخچه الگوریتم ژنتیک نیز همه افراد به دنبال یافتن چنین مفهومی بودند.
هر کروموزوم شامل بیت‌های اطلاعاتی و تکه‌های رقومی هستند. هر کدام از این تکه‌ها موسوم به ژن می‌باشند. در یک بیان تناظری، نسبت مادی ژن به کروموزوم به فرد مثل نسبت معنوی حرف به کلمه به جمله می‌باشد. هر ژن میتواند مقادیری را اختیار کند و هر مقدار ممکن موسوم به یک اَلل می‌باشد. در صورتی که ژن کد باینری باشد، آنگاه دو اَلل بیشتر نداریم، یکی مقدار صفر (۰) و دیگری مقدار (۱) و موقعیت یک ژن در کروموزوم مربوطه معروف به مکان یا موقعیت می‌باشد.
جهت تفهیم و تعمیق اصطلاحات یادشده، یک مجموعه ساده پنج عضوی از پرندگان یک نژاد خاص (مثلاً اُردک ها) را در نظر بگیرید. برای آشنایی بیشتر شما عزیزان و داشتن ارائه‌ای کاربردی در این زمینه می‌توانید از دوره آموزش الگوریتم ژنتیک که در لینک زیر قرار داده شده بهره مند شوید.
روش الگوریتم ژنتیک
در ادامه تاریخچه الگوریتم ژنتیک بایستی روش کلی این الگوریتم در حل یک مسئله را بایستی بدانیم. به صورت کلی الگوریتم ژنتیک روشی برای بهینه سازی با جستجوی وسیع است و کارکرد آن بر اصول انتخاب طبیعی حاکم بر ژنتیک طبیعی استوار است. ایده این الگوریتم از نظریه تکامل داروین الهام گرفته شده است. اگرچه این الگوریتم روشی برای جستجوی تصادفی است، ویژگی‌های خاص آن موجب می‌شود که نتوان آن را یک جستجوی تصادفی ساده قلمداد کرد. این الگوریتم جزو الگوریتم های تکاملی است.
در این الگوریتم اطلاعات تاریخی از چگونگی تکامل، به شکلی کارا استخراج شده و در روند جستجو استفاده می‌شود. الگوریتم ژنتیک روشی قدرتمند بوده و بر روی دسته وسیعی از مسائل به‌خوبی عمل می‌کند. الگوریتم‌های ژنتیک که بر اساس ایده‌ی تکامل بیولوژیکی در طبیعت عمل می‌نمایند، بر روی جمعیتی از راه حل‌های بالقوه یا کروموزوم‌ها که هر یک می‌توانند به‌عنوان پاسخی از مسئله تلقی شوند، با اعمال عملگرهای ژنتیک به جستجوی راه حل نهایی می‌پردازند.
در الگوریتم‌های ژنتیکی، بسیاری از مکانیزم‌هایی که در زیست شناسی وجود دارد، نظیر انتخاب ژن برتر، ترکیب ژن‌ها، جهش ژن‌ها، مهاجرت افراد جمعیت، محلی بودن گونه‌ها و غیره شبیه سازی می‌شوند. در این الگوریتم‌ها، جستجو بر روی مجموعه‌هایی از راه حل‌ها به‌صورت موازی انجام می‌شود، درحالی‌که در روش‌های سنتی جستجو به‌صورت ترتیبی است.
روند کار الگوریتم ژنتیک
در آغاز الگوریتم، تعدادی از افراد به‌عنوان جمعیت اولیه و معمولاً به‌صورت تصادفی ساخته‌شده و معیاری از کیفیت به نام تابع هدف یا برازندگی برای تک تک آن‌ها ارزیابی می‌شود. اگر شرط رسیدن به جواب برقرار نباشد (به جواب بهینه نرسیده باشیم)، نسل بعدی با انتخاب والدین بر اساس میزان برازندگی آن‌ها تولید می‌شود.
در هر نسل، بهترین‌های آن نسل انتخاب می‌شوند و پس از زاد و ولد، مجموعه جدیدی از فرزندان را تولید می‌کنند. کروموزوم‌های موجود در جمعیت بر اساس مقدار برازندگی به‌عنوان والد انتخاب می‌شوند. سپس تولیدمثل، بین جفت کروموزوم‌ها انجام می‌گیرد تا فرزندان ایجاد شوند و فرزندان با احتمالی ثابت دچار جهش می‌شوند. سپس میزان برازندگی فرزندان جدید محاسبه‌شده و جمعیت جدید، از جایگزینی فرزندان با والدین ایجاد می‌شود و جمعیت ایجادشده جدید به‌عنوان نسل بعدی شناخته می‌شود و فرایند تکرار می‌شود.
در این فرایند، افراد مناسب‌تر با احتمال بیشتری در نسل‌های بعد باقی خواهند ماند و این فرایند تا برقرار شدن شرط خاتمه تکرار می‌شود. الگوریتم زمانی پایان خواهد یافت که بهبودی بر روی جواب‌ها صورت نگیرد و یا اینکه تعداد مشخصی نسل تولید شود. مراحل کلی یک الگوریتم ژنتیک میتواند به‌صورت شکل زیر باشد.
معرفی یک الگوریتم ژنتیک ساده
الگوریتم‌های ژنتیک، به‌جای آنکه بر روی پارامترها کار کنند با شکل کد شده آن‌ها سروکار دارند. برای مثال فرض کنید که بیشینه کردن تابع f(x,y)=X^2+Y^2 (با محدودیت‌های x و y اعداد صحیح و x بین ۰ تا ۷ و y بین ۰ تا ۳۱ مدنظر باشد. متداول-ترین روش کدگذاری، کدگذاری باینری است.
ازاین‌رو پارامتر با دنباله مناسبی از اعداد جایگزین می‌شود. هر عدد صحیح از ۰ تا ۳۱ را می‌توان با ۵ بیت و هر عدد صحیح از ۰ تا ۷ را با ۳ بیت می‌توان نمایش داد. برای مثال شکل زیر کدگذاری باینری دو متغیر x= 9 و y=5 را نشان می‌دهد.
بنابراین با هر نقطه از فضای دوبعدی (x,y) دنباله‌ای به‌صورت شکل زیرمتناظر است.
تعریف‌ها
- ژن: مقدار کد شده هر متغیر را ژن گویند. در کدگذاری باینری ژن متناظر با x=9 مطابق شکل عبارت است از: ۰۱۰۰۱.
- کروموزوم: به رشته یا دنباله‌ای از ژن‌ها که به‌عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مسئله موردنظر به کار می‌رود کروموزوم گویند.
- جمعیت: در هر مرحله تکرار از الگوریتم ژنتیکی تعدادی مشخص از کروموزوم‌ها مورد ارزیابی قرار می‌گیرد. به مجموعه این کروموزوم‌ها جمعیت می‌گویند.
- عدد برازندگی: مناسب بودن یا نبودن را با معیاری که باهدف(مورد بهینه‌سازی) رابطه دارد می‌سنجند.
- عملگر جابجایی یا ترکیب: این عملگر برای زوجی از کروموزوم‌ها اعمال می‌شود. نوعی از این عملگر، دو کروموزوم را به‌طور تصادفی از یک نقطه شکسته و بخش‌های شکسته دو کروموزوم را جابه جا می‌کند. نحوه عملکرد این عملگر در شکل زیر نشان داده‌شده است.
- عملگر جهش: این عملگر روی یک دنباله منفرد عمل می‌کند به‌این‌ترتیب که با احتمال کوچکی به نام احتمال جهش هر ژن از کروموزوم‌ها را تغییر می‌دهد. در شکل زیر نحوه تغییر ژن‌های یک کروموزوم براثر عملگر جهش نشان داده‌شده است.
- کروموزوم فرزند: به دنباله‌ای که پس از عمل جابه جایی و عمل جهش به دست می‌آید کروموزوم فرزند می‌گویند.
- جایگذاری: پس‌ازآنکه فرزندان جدید، با استفاده از جمعیت قدیمی ساخته شدند و میزان شایستگی آن‌ها نیز تعیین گردید، می‌بایست یک نسل جدید از میان فرزندان و والدین موجود انتخاب شوند. روش‌های مختلفی برای این انتخاب وجود دارد که تحت عنوان جایگذاری شناخته می‌شود.
- عملگر انتخاب: برای ایجاد افراد نسل جدید، از عملگر انتخاب استفاده می‌شود.
- مرحله تولید: به هر بار تولید یک جمعیت جدید یک مرحله تولید گویند.
کاربردهای الگوریتم ژنتیک
در ادامه مقاله تاریخچه الگوریتم ژنتیک به کاربردهای این الگوریتم می‌پردازیم. الگوریتم ژنتیک در حوزه‌های مختلفی کاربرد دارد، از جمله:
- بهینه‌سازی ترکیبیاتی: حل مسائلی مانند مسئله فروشنده دوره‌گرد (TSP) و زمان‌بندی.
- یادگیری ماشین: تنظیم پارامترهای مدل‌ها و انتخاب ویژگی‌ها.
- طراحی مهندسی: بهینه‌سازی ساختارها و سیستم‌ها.
- اقتصاد و مالی: مدل‌سازی بازارها و استراتژی‌های سرمایه‌گذاری.
- زیست‌شناسی محاسباتی: تحلیل توالی‌های ژنتیکی و مدل‌سازی سیستم‌های زیستی.
مزایا و معایب الگوریتم ژنتیک
مزایا
- قابلیت جستجوی فضای بزرگ و پیچیده.
- عدم نیاز به اطلاعات مشتق‌پذیری تابع هدف.
- توانایی فرار از بهینه‌های محلی.
معایب
- نیاز به تنظیم دقیق پارامترها.
- ممکن است به زمان محاسباتی زیادی نیاز داشته باشد.
- عدم تضمین یافتن بهینه‌ترین راه‌حل.
سخن آخر
در این مقاله آموزشی سعی شد تا یک دیدگاه کلی از تاریخچه الگوریتم ژنتیک برای شما باز شود. واضح است برای مطالعات تکمیلی وقت و زمان بیشتری لازم است. پیشنهاد می‌کنیم حتماً مقاله آموزش جامع الگوریتم ژنتیک را مشاهده کنید در این آموزش نحوه کار الگوریتم ژنتیک بطور کامل تشریح شده است. امیدواریم مطالب فوق برای شما مفید بوده باشد. موفق و پیروز باشید.
