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

برنامه‌نویسی ژنتیک یکی از روش‌های هوش مصنوعی است که بر پایه آن، برنامه‌های رایانه‌ای به صورت مجموعه ای از ژن‌ها کدگذاری می‌شوند. سپس این ژن‌ها با استفاده از الگوریتم فرگشتی (که معمولاً الگوریتم ژنتیک است) تغییر داده می‌شوند. این روش یکی از کاربردهای الگوریتم‌های ژنتیک است که در آن، فضای پاسخ شامل برنامه‌های رایانه‌ای است. پاسخ‌های مسئله برنامه‌های رایانه‌ای هستند که قادر به اجرای مناسب وظیفهٔ از پیش تعریف‌شده باشند. روش‌های به کار رفته در تبدیل برنامه‌ها به کروموزوم مصنوعی و ارزیابی برازش آن در مقایسه با وظیفهٔ از پیش تعریف‌شده همچنان موضوع پژوهش هستند.

بخشی از مجموعه
الگوریتم فرگشتی
الگوریتم ژنتیک
برنامه‌نویسی ژنتیک
  • Cartesian genetic programming
  • Linear genetic programming
  • Multi expression programming
  • Schema
  • Eurisko
  • Parity benchmark

تاریخچه

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

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

کوزا مطالعات خود را ادامه داد و ۲۰۵ مقاله دربارهٔ «برنامه‌نویسی ژنتیک» که توسط دیوید گولدبرگ نامگذاری شده بود،[5] منتشر کرد. البته در واقع مجموعهٔ ۴ کتابی او که از سال ۱۹۹۲ همراه ویدئوهای آموزشی منتشر شد،[6][7] برنامه‌نویسی ژنتیک را بنیان نهاد.

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

تعریف برنامه
تابع ارائه شده به صورت ساختار درختی

برنامه‌نویسی ژنتیک برنامه‌های رایانه‌ای را که به صورت سنتی با ساختار درختی در حافظه تعریف می‌شوند، تکامل می‌دهد.[11] می‌توان درختان را به سادگی در روشی بازگشتی ارزیابی کرد. هر گره درخت یک تابع عملگر دارد و هر گره ترمینال شامل یک عملوند است. به این ترتیب، به سادگی می‌توان عبارات ریاضی را تکامل داد و ارزیابی کرد. برنامه‌نویسی ژنتیک علاقه‌مند به استفاده از برنامه‌هایی است که به صورت طبیعی دارای ساختار درختی باشند. (برای نمونه زبان‌های برنامه‌نویسی تابعی)

ساختارهای بدون درخت نیز پیشنهاد شده‌اند و با موفقیت به اجرا درآمده اند. برای نمونه برنامه‌نویسی ژنتیک خطی برای برنامه‌های دستوری سنتی‌تر مناسب است.[12] µGP از گراف چندگانه برای ایجاد برنامه‌هایی که دستور زبان اسمبلی را به‌طور کامل بیان می‌کنند، بهره می‌گیرد.[13] برنامه‌نویسی ژنتیک دکارتی روش دیگری است که به جای ساختار درختی از ساختار گراف استفاده می‌کند.

انتخاب

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

کاربرد

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

منابع
  1. "Computing Machinery and Intelligence". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  2. "BEAGLE A Darwinian Approach to Pattern Recognition". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  3. "A representation for the Adaptive Generation of Simple Sequential Programs". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  4. "Non-Linear Genetic Algorithms for Solving Problems". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  5. 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.
  6. "Genetic Programming: On the Programming of Computers by Means of Natural Selection". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  7. "Genetic Programming:The Movie". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  8. "Genetic Programming 1996: Proceedings of the First Annual Conference". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  9. Banzhaf, Wolfgang (2000-04-01). "Editorial Introduction". Genetic Programming and Evolvable Machines. 1 (1–2): 5–6. doi:10.1023/A:1010026829303. ISSN 1389-2576.
  10. "Genetic Programming Theory and Practice". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  11. Nichael L. Cramer "A Representation for the Adaptive Generation of Simple Sequential Programs" بایگانی‌شده در ۴ دسامبر ۲۰۰۵ توسط Wayback Machine.
  12. Garnett Wilson and Wolfgang Banzhaf. "A Comparison of Cartesian Genetic Programming and Linear Genetic Programming".
  13. Giovanni Squillero. "µGP (MicroGP)".
  14. "A Field Guide to Genetic Programming". www.gp-field-guide.org.uk. Retrieved 2018-05-20.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.