همچنان که در زیست‌شناسی، موضوعی به نام تکامل وجود دارد، در هوش مصنوعی هم الگوریتم‌های تکامل‌یابنده‌ای وجود دارند که وظایف تعریف‌شده توسط کاربر را انجام میدهند. به این برنامه‌ها با الهام از روند تکامل بیولوژیک، برنامه توارثی یا ژنتیکی genetic program گفته می‌شود.
شخصی به نام راجر السینگ Roger Alsing، در اوقات فراغت تعطیلات آخر هفته پیش، دست به کار جالبی زد. او تصمیم گرفت الگوریتمی بنویسد که با استفاده از رسم مداوم چند ضلعی‌ها و مقایسه آن با یک تصویر داده، به تدریج شکلی بیافریند که متشکل از چندضلعی‌های زیاد باشد.
او این کار را در ۳ ساعت انجام داد و برای تست، از تصویر تابلوی مشهور مونالیزا استفاده کرد. او در توضیحاتش «ادعا می‌کند» که الگوریتم او، در رده برنامه‌های توارثی تقسیم‌بندی می‌شود.
برای تست برنامه می‌توانید به این صفحه بروید. شما باید در این صفحه لینک عکسی را بدهید که ابعاد آن ۲۰۰ در ۲۰۰ پیکسل و همچنین ۱۶ رنگی باشد.
مشاهده مراحل تکامل تصویر از یک عکس ساده به عکس داده شده، بسیار جالب است. البته باید صبوری زیادی داشته باشید. من برای تست لوگوی فایرفاکس را به این برنامه معرفی کردم و تا لحظه ارسال این پست، چنین تصویری را دارم:
گرچه حتی خود آقای السینگ عقیده دارد که برنامه‌اش کاربردی ندارد، اما تصور می‌کنم که تست برنامه خالی از لطف نباشد.
توضیحات بیشتر را در اینجا و اینجا بخوانید.
پی‌نوشت: اگر توضیحات دقیقی در مورد ترمینولوژی برنامه‌های توارثی یا این الگوریتم دارید، دریغ نکنید.
پی‌نوشت ۲: توضیحات خوب کمانگیر را در اینجا بخوانید.
سلام.
در الگوریتم ژنتیک، چند حالت اولیه در نظر می‌گیریم(که طبیعتاً هیچ‌کدام جواب نهایی نیستند.)
برای مسئله تابعی تعریف می‌کنیم به نام تابع ارزیابی، که وظیفه‌اش محاسبه‌ی مقداری است،که از روی آن مقدار می‌شود نزدیکی و دوری حالت فعلی، با جواب نهایی را تعیین کرد.
مقدار تابع ارزیابی را برای آن چند حالت اولیه محاسبه می‌کنیم و دورترین‌ها را حذف، و نزدیک‌ترین‌ها به جواب را دوبل و بلکه سوبل می‌کنیم! حالا، حالت‌ها را دوتا دوتا دسته‌بندی می‌کنیم و به شکل تصادفی، یک قسمت از یک حالت را، با قسمت مشابه حالت هم‌دسته‌ای‌اش جابه‌جا می‌کنیم. مثلاً اگر دو دنباله‌ی ۸ رقمی داشته‌باشیم و به شکل تصادفی قرار شود که از رقم پنجم به بعد را جابه‌جا کنیم، پنج رقم اول دنباله‌ها را با هم عوض می‌کنیم. با احتمال کوچکی، هر کدام از این حالت‌های جدیداً به‌دست آمده، می‌توانند دچار جهش هم بشوند که منظور این است که بعضی از قسمت‌هایشان تغییر کند، درست مثل جهش ژنتیکی.
دوباره تابع ارزیابی را محاسبه می‌کنیم و روز از نو، روزی از نو!
سلام دکتر. مطلب جالبی بود. ممنون.
تا جایی که من میدونم رسم تمامی تصاویر در کامپیوتر که به وسیله کارت گرافیک انجام میشه, از مثلث های کوچک و به تعداد بسیار بالا تشکیل شده و ما حاصل کار را به صورت یک شکل منسجم میبینیم.
در ابتدا این کار به وسیله مربع انجام میشد ولی با درک این مسئله که با سه ضلعی ها تصاویر دقیق تر و شفاف تری در اختیار داریم, تمامی شتاب دهنده های گرافی به سمت استفاده از مثلث روی آوردند.
در این تکنیک اشکال با کمترین شکست در لبه های تصویر, شکل شفاف و واضح و کاملا Smooth ای را ارائه میدهند.
این آقا هم قطعا از همین موضوع استفاده کرده و به جای استفاده از میلیارد ها مثلث کوچک قصد داره با تعدادی از اون ها در محیط واقعی به نوعی شبیه سازی انجام بده.
موفق باشید.
http://www.thelightnights.wordpress.com
این پست رو خوندم یاد یه بازی افتادم تو بچگی دکتر که اول می رفتیم بیرون بعد مثلا یه چیزی رو تغییر می دادن تو اتاق و ما می یومدیم تو و دنبالش می گشتیم! فکر کنم این نسل جدید بازی های اینطوری باشه
یه حسی به بچگیم داد این پست … این رو گفتم تا باهم شریک بشیم
دیدن عملی اینکه الگوریتم ژنتیک کاملا بر مبنای نظریه تکامل برای مسائل بهینه سازی با استفاده از تنها دو جواب تصادفی جواب نهایی بسیار خوبی میدهد، برای من خیلی جالب بود. وقتی برای اولین بار بطور عملی میدیدم که در هر قدم، جواب حاصل به جواب بهینه نزدیک و نزدیکتر میشه. اون موقع من کاملا بطور تئوریک با منطقش آشنا بودم و کاملا منطقی بود اما دیدن کارکردش توی یک مساله بهینه سازی پیچیده واقعا زیبا بود. این الگوریتم ژنتیک خیلی ایده جالبی است.
why genetic algorithms is translated to Tavarosi?
یک نکته نچندان مهم، الگوریتم پیاده شده در این پست، یک gradient descent است. و به همین دلیل سرعت پایینی دارد. در صورتی که گاهی اوقات حالت های بد (حالت هابیی که شباهت کمتری دارند) را به عنوان حالت بعدی قبول کند می شود Monte Carlo . و اگر یک جمعت را نگه دارد می شود GP
ممنون دکتر من امتحان کردم ولی سیستمم خیلی سنگین شد دلیل چیه؟