برنامه‌نویسی ژنتیک

برنامه‌نویسی ژنتیک یک heuristic، ابزار یادگیری ماشینی تکاملی و زیر مجموعه‌ای از رایانش فرگشتی است. در برنامه‌نویسی ژنتیک، هدف ایجاد برنامه‌های قابل اجرا جهت حل مسائل است. در این روش، فضای جستجو مجموعه‌ای از برنامه‌ها است. یک برنامه، یک داده ساختار تلقی می‌شود که می‌تواند مستقیماً توسط رایانه اجرا شود. یا این‌که به یک چنین برنامه‌ای ترجمه(compile) شود یا تفسیر(interpret) شود. در این روش پاسخ‌های مسئله برنامه‌های رایانه‌ای هستند که قادر به اجرای مناسب وظیفهٔ از پیش تعریف‌شده باشند.

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

از مسائل باز در این حوزه می‌توان به موارد زیر اشاره کرد:
 روش‌های به کار رفته در تبدیل برنامه‌ها به کروموزوم مصنوعی و ارزیابی برازش آن در مقایسه با وظیفهٔ از پیش تعریف‌شده.
 جلوگیری از پدیده باد کردن برنامه‌ها
 مباحث نظری برنامه‌نویسی ژنتیک
 ماژولی بودن (به انگلیسی: Modularity)
 تکامل پایان‌بازhttps://alfagroup.csail.mit.edu/sites/default/files/documents/2015%20Genetic%20Programming.%20James%20McDermott%20and%20Una-May%20O%27Reilly.%20Handbook%20of%20Computational%20Intelligence%2C%202015.pdf

 تاریخچه 
می‌توان پیشنهاد آلن تورینگ در دههٔ ۱۹۵۰ را نخستین پیشنهاد ثبت شده برای تکامل برنامه‌ها دانست. هرچند سی سال طول کشید تا ریچارد فورسیت موفقیت تکامل برنامه‌های کوچک را که به شکل درخت ارائه شده بودند، نشان دهد. فورسیت از این روش برای دسته‌بندی شواهد صحنهٔ جرم استفاده کرد.

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

کوزا مطالعات خود را ادامه داد و ۲۰۵ مقاله دربارهٔ «برنامه‌نویسی ژنتیک» که توسط دیوید گولدبرگ نامگذاری شده بود،Goldberg. D.E. (1983), Computer-aided gas pipeline operation using genetic algorithms and rule learning. Dissertation presented to the University of Michigan at Ann Arbor, Michigan, in partial fulfillment of the requirements for Ph.D. منتشر کرد. البته در واقع مجموعهٔ ۴ کتابی او که از سال ۱۹۹۲ همراه ویدئوهای آموزشی منتشر شد، برنامه‌نویسی ژنتیک را بنیان نهاد.

کوزا در سال ۱۹۹۶ کنفرانس سالانهٔ برنامه‌نویسی ژنتیک را راه‌اندازی کرد. در سال ۲۰۰۰ نخستین مجلهٔ اختصاصی آن منتشر شد و سه سال بعد، ریک ریولو کارگاه سالانهٔ برنامه‌نویسی ژنتیک تئوری و عملی را تأسیس کرد.

 تعریف برنامه 
برنامه‌نویسی ژنتیک برنامه‌های رایانه‌ای را که به صورت سنتی با ساختار درختی در حافظه تعریف می‌شوند، تکامل می‌دهد.Nichael L. Cramer "A Representation for the Adaptive Generation of Simple Sequential Programs" . می‌توان درختان را به سادگی در روشی بازگشتی ارزیابی کرد. هر گره درخت یک تابع عملگر دارد و هر گره ترمینال شامل یک عملوند است. به این ترتیب، به سادگی می‌توان عبارات ریاضی را تکامل داد و ارزیابی کرد. برنامه‌نویسی ژنتیک علاقه‌مند به استفاده از برنامه‌هایی است که به صورت طبیعی دارای ساختار درختی باشند. (برای نمونه زبان‌های برنامه‌نویسی تابعی)

ساختارهای بدون درخت نیز پیشنهاد شده‌اند و با موفقیت به اجرا درآمده اند. برای نمونه برنامه‌نویسی ژنتیک خطی برای برنامه‌های دستوری سنتی‌تر مناسب است.Garnett Wilson and Wolfgang Banzhaf. "A Comparison of Cartesian Genetic Programming and Linear Genetic Programming". µGP از گراف چندگانه برای ایجاد برنامه‌هایی که دستور زبان اسمبلی را به‌طور کامل بیان می‌کنند، بهره می‌گیرد. برنامه‌نویسی ژنتیک دکارتی روش دیگری است که به جای ساختار درختی از ساختار گراف استفاده می‌کند.

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

 دسته‌بندی‌ها 
انواع مختلف برنامه‌نویسی ژنتیک را می‌توان به روش‌های مختلف دسته‌بندی کرد.

 بر اساس طرز نمایش برنامه‌ها 
بر اساس روش نمایش برنامه، چند دسته‌بندی مطرح وجود دارد:
 برنامه‌نویسی ژنتیک استاندارد یا درختی: در این روش، یک درخت نحو یا عبارت نمایش دهنده یک برنامه است.
 برنامه‌نویسی ژنتیک بر اساس گراف: یک تعمیم به کل از برنامه‌نویسی ژنتیک درختی، برنامه‌نویسی ژنتیک بر اساس گراف است. شبکه‌های عصبی نیز می‌توانند گونه‌ای از این نوع در نظر گرفته شوند. چند نوع برنامه‌نویسی ژنتیک که در این دسته قرار می‌گیرند شامل برنامه‌نویسی ژنتیک موازی و توزیع‌شدهو هم‌چنین Cartesian GPهستند. علاوه‌بر این دو، Neuro-evolution of augmented topologiesیا به اختصار NEAT نیز یک نوع دیگر است.
 نمایش ماشین حالات متناهی: در این نوع نمایش از گراف‌ها اما به شیوه‌ای دیگر استفاده می‌شود. یک برنامه، یک ماشین حالات متناهی است. یک نمونه که در این دسته‌بندی قرار می‌گیرد برنامه‌سازی تکاملی می‌باشد.
 برنامه‌نویسی ژنتیک نحوی (به انگلیسی: Grammatical GP): در این دسته‌بندی یک نحو مستقل از متن استفاده می‌شود. در رویکرد رایج، جستجو در فضایی انجام می‌شود که توسط یک نحو مستقل از متن غیرقطعی تعریف می‌شود.
 برنامه‌نویسی ژنتیک خطی: در این روش، یک برنامه فهرستی از دستورها است که به صورت پشت سر هم اجرا می‌شوند. معمولاً برای بدست آوردن یک کارکرد به اندازه کافی پیچیده و مناسب، تعدادی ثبات به عنوان حالت یا حافظه تعریف می‌شوند.
 برنامه‌نویسی ژنتیک پشته‌ای: نوعی از برنامه‌نویسی ژنتیک خطی است با این تفاوت که از هیچ ثباتی استفاده نمی‌شود. در عوض یک پشته به عنوان حافظه به کار گرفته می‌شود.
 برنامه‌نویسی ژنتیک سطح پایین: در این روش، برنامه‌ها مستقیم یک زبان سطح پایین هستند. برای مثال بایت‌کد جاوا یا اسمبلی اکس۸۶.

 بر اساس پیکره‌بندی جمعیت 
بر اساس پیکره‌بندی جمعیت، ۳ دستهٔ مطرح وجود دارند:

 یک جمعیت بزرگ. در این روش تمام برنامه‌ها در یک جمعیت بزرگ وجود دارند. ازدواج و بقا بین همهٔ برنامه‌های این جمعیت اتفاق می‌افتد.
 پیکره‌بندی روستا‌یی یا منطقه‌ای(به انگلیسی: Demetic Genetic Programming). در این روش برنامه‌ها در  منطقه‌ها یا روستا‌های متعددی پخش شده‌اند. ازدواج و بقا بین اعضای یک روستا یا deme اتفاق می‌افتد. و مهاجرت‌های اندکی هر چند نسل یک‌بار بین روستا‌ها وجود دارند. میزان هر مهاجرت، فرکانس مهاجرت و مبدا و مقصد هر منطقه از پارامتر‌هایی هستند که باید تعیین شوند. روش رایج برای مبدا و مقصد، فهرست دایره‌ای است. به این صورت که هر منطقه مهاجرانی به منطقهٔ بعد می‌فرستد. و منطقهٔ آخر مهاجران خود را به منطقهٔ اول می‌فرستد.
 پیکره‌بندی سلولی(به انگلیسی Cellular Genetic Programming). در این روش مانند روش منطقه‌ای، جمعیت‌ها در منطقه‌های مختلف، یا به دیگر بیان در سلول‌های مختلف، نیمه ایزوله هستند. اما این منطقه‌ها در یک شبکهٔ معمولا مستطیلی یا مکعبی پخش شده‌اند. و مهاجرت بین همسایه‌ها اتفاق می‌افتد.

 کاربرد 
برنامه‌نویسی ژنتیک با موفقیت به عنوان ابزار برنامه‌نویسی خودکار، ابزار یادگیری ماشین و موتور حل مسألهٔ خودکار به کار رفته است. این روش به ویژه در دامنه‌هایی که شکل دقیق پاسخ شناخته شده نیست یا پاسخ تقریبی قابل پذیرش است، قابل استفاده است. از برنامه‌نویسی ژنتیک برای مسائل دسته‌بندی و همچنین مسائل رگرسیون در یادگیری ماشین استفاده شده است.

 پیوند به بیرون 
 مجموعه‌ای از حدود ۱۷ هزار مقالهٔ برنامه‌نویسی ژنتیک که به صورت رایگان و با دسترسی باز منتشر شده‌اند. می‌توان بر اساس نام نویسنده یا نویسنده‌ها، عنوان و متن مقاله جستجو کرد. http://gpbib.cs.ucl.ac.uk/

 منابع 


رده:الگوریتم‌های ژنتیک
رده:یادگیری ماشین
رده:هوش مصنوعی