استراتژی های تکاملی
آموزشآموزش‌های پایه‌ای هوش مصنوعیآموزش‌های پیشرفته هوش مصنوعیاصول هوش مصنوعیبینایی ماشینپایتون و ابزارهای یادگیری عمیق

راهنمای استراتژی‌های تکاملی

    0
    در مقاله حاضر، می‌خواهیم چگونگی کارکرد استراتژی‌های تکاملی evolution strategies (ES) را به کمک چند نمونه بصری توضیح دهیم. در این مقاله چگونگی به‌کارگیری الگوریتم‌ها برای انجام کارهای مختلف را شرح خواهیم داد.
    مقدمه
    مدل‌های شبکه عصبی از انعطاف‌پذیری بالایی برخوردارند. اگر بتوانیم مجموعه مناسبی از پارامترهای مدل را پیدا کنیم، امکان استفاده از شبکه‌های عصبی برای حل بسیاری از مسائل چالش‌برانگیز وجود خواهد داشت.
    یادگیری عمیق موفقیتِ خود را تا حد زیادی مرهونِ استفاده از الگوریتم پس‌انتشار (Back-propagation) است که می‌تواند گرادیان تابع هدف را نسبت به هر یک از پارامترهای مدل به شکل کارآمدی محاسبه کند. به کمک این گرادیان‌ها می‌توانیم فضای پارامتر را به شکلی کارآمد جستجو کنیم تا به راه حل مناسبی برای انجام کارهای سخت، توسط شبکه‌های عصبی دست پیدا کنیم.
    با این حال، مسائل بسیاری هم وجود دارند که برای حل آن‌ها نمی‌توان از الگوریتم پس‌انتشار استفاده کرد. برای مثال، در مسائل یادگیری تقویتی reinforcement learning  می‌توان یک شبکه عصبی را آموزش داد به طوری که بتواند یک توالی از حرکت‌ها را برای انجام برخی از وظایف در یک محیط تشکیل دهد. اما تخمین گرادیان سیگنال‌های پاداش با توجه به حالت عامل در آینده جهت تعیین حرکت کنونی کار ساده‌ای نیست، به ویژه زمانی که پاداش ناشی از حرکت کنونی در آینده تعیین می‌شود. حتی در صورتی که قادر به محاسبه گرادیان‌های دقیق باشیم، مسئلۀ گیر افتادن در بهینه محلی  local optimum  کماکان وجود دارد.

    استراتژی های تکاملی

    گیرافتادن در بهینه محلی

    در RL یک بخش کامل برای مطالعه مسئله تخصیص اعتبار  credit-assignment در نظر گرفته شده و پیشرفت قابل توجهی در سال‌های اخیر در این حوزه به دست آمده است. با این حال، همچنان کار دشواری است؛ به ویژه وقتی که سیگنال‌های پاداش پراکنده باشند.
    در دنیای حقیقی، پاداش‌ها می‌توانند پراکنده و نویزدار باشند. گاهی اوقات فقط یک پاداش داریم. بسته به کارفرمایی که داریم، شاید دانستن این که چرا پاداش اینقدر کم است، سخت باشد. بنابراین، در مسائلی از این دست به جای اینکه به تخمین بی‌معنی گرادیان آینده تکیه کنیم و سیاست‌های خود را پیرامون آن بچینیم، می‌توانیم استفاده از روش‌های بهینه‌سازی جعبه سیاه (Black Box) مثل الگوریتم‌های ژنتیک یا استراتژی‌های تکاملی را در دستور کارمان قرار دهیم.
    در همین راستا، «Open AI» مقاله‌ای با عنوان «استراتژی‌های تکاملی، یک روش جایگزین مقیاس‌پذیر برای یادگیری تقویتی» منتشر کرد که نشان می‌داد استراتژی‌های تکاملی علی‌رغم اینکه کارآیی کمتری به لحاظ داده‌ای از RL دارند، اما از مزایای بسیاری برخوردارند.
    کنار گذاشتنِ محاسبات گرادیان، فرصتی به این نوع الگوریتم‌ها می‌دهد تا به شکل موثرتری تکامل یابند. به راحتی می‌توان محاسابات مربوط به یک الگوریتم ES را بر روی هزاران ماشین جهت دستیابی به پردازش موازی به اشتراک گذاشت. همچنین در این مقاله نشان داده شده که با اجرا کردن متعدد این الگوریتم‌ها از ابتدا، می‌توان به سیاست‌های متنوع‌تری در مقایسه با سیاست‌های کشف شده توسط RL دست یافت.
    اشاره به این نکته ضروری است که حتی در مسئلۀ شناسایی مدل یادگیری ماشین، مثل طراحی معماری شبکه عصبی، نمی‌توان گرادیان را به‌طور مستقیم محاسبه کرد. اگرچه می‌توان از RL، استراتژی تکاملی، الگوریتم ژنتیک و… برای جستجو در فضای معماری مدل استفاده کرد، اما در مقاله حاضر تمرکز روی استفاده از این الگوریتم‌ها برای جستجوی پارامترهای مدلِ از پیش‌تعریف شده معطوف شده است.

    استراتژی تکاملی چیست؟

    تابع Rastrigin تعداد زیادی بهینه محلی دارد

    نمودارهای زیر توابع دوبعدی Schaffer(شکل سمت چپ) و Rastrigin(شکل سمت راست) را نشان می‌دهند. دو مسئله ساده که برای آزمایش الگوریتم‌های بهینه‌سازی جعبه سیاه پیوسته مورد استفاده قرار می‌گیرند. بخش‌های روشن‌تر نمودار مقادیر بیشتر توابع F(x, y)  را نشان می‌دهند.

    استراتژی تکاملی
    همان‌طور که در این نمودار مشاهده می‌کنید، بهینه‌های محلی زیادی در این تابع وجود دارد. ما باید یک مجموعه پارامتر مدل
    (x,y) پیدا کنیم؛ طوری که (F(x, y بیشترین نزدیکی را به حداکثر سراسری  global maximum  داشته باشد. اگرچه تعاریف متعددی از استراتژی‌های تکاملی ارائه شده است، اما می‌توان استراتژی تکاملی را به عنوان الگوریتمی تعریف کرد که مجموعه‌ای از راه‌حل‌های احتمالی را در اختیار کاربر قرار می‌‌دهد تا بتواند مسئله‌ای را ارزیابی کند.
    فرایند ارزیابی بر پایه تابع هدف است که راه حل معینی را می‌گیرد و یک مقدار برازش ارائه می‌کند. بر اساس نتایج برازشِ راه‌حل‌های موجود، الگوریتم به تولید نسل بعدیِ راه‌حل‌های نامزد خواهد پرداخت. انتظار می‌رود نتایج بهتری در مقایسه با نسل فعلی حاصل شود.
    فرایند تکراری زمانی متوقف می‌شود که کاربر به بهترین راه‌حل ممکن دست پیدا کند. با توجه به یک الگوریتم استراتژی تکاملی موسوم به EvolutionStrategy، می‌توان به شیوه زیر اقدام کرد:

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

    استراتژی تکاملی ساده

    در یکی از ساده‌ترین استراتژی‌های تکاملی، مجموعه راه‌حل‌ها از توزیع نرمال نمونه‌گیری می‌شوند؛ با میانگینμ و انحراف معیار ثابت σ. در مسئله دوبعدی داریم: μ=(μ​x​​,μ​y​​) و σ=(σ​x​​,σ​y​​). در ابتدا، μ بوسیله مرکز فضای مسئله مقداردهی می‌شود. پس از اینکه نتایج برازش مورد ارزیابی قرار گرفت، باید μ را به بهترین راه‌حل در جمعیت جواب‌ها مقداردهی شود. نسل بعدی راه‌حل‌ها باید بر اساس میانگین جدید نمونه‌گیری شوند. این نحوه عملکرد الگوریتم در ۲۰ نسل است که در دو مسئله فوق به کار گرفته شده است.

    استراتژی تکاملیاستراتژی تکاملی

     

     

     

     

     

     

     

     

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

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

    الگوریتم ژنتیک  genetic algorithm  یکی از قدیمی‌ترین الگوریتم‌های بهینه‌سازی شمرده می‌شود که انواع مختلفی دارد و هر کدام از آن‌ها در سطح متفاوتی پیچیده هستند، اما در این مقاله ساده‌ترین نسخه معرفی می‌شود.

    این ایده ساده را در نظر بگیرید: تنها ۱۰ درصد از بهترین راه‌حل‌ها را در نسل فعلی نگه دارید و بگذارید بقیه جمعیت از بین بروند. در نسل بعدی، برای نمونه‌گیریِ راه‌حل جدید، باید دو راه‌حل را به صورت تصادفی از بازماندگان نسل قبلی انتخاب کنید و با ادغام مجدد پارامترهایشان به ایجاد یک راه‌حل جدید برسید. در این فرایندِ نوترکیب (crossover)، از روش پرتاب سکه برای تعیین هر پارامتر از والدها استفاده می‌شود. در تابع دو بعدی مثال قبل، هر یک از جواب‌های جدید ممکن است x یا y را به احتمال ۵۰ درصد از هر یک از والدین به ارث ببرند. پس از این فرایند نوترکیب نویز گاوسی Gaussian noise با انحراف معیار ثابت، به هر راه‌حل جدید اضافه می‌شود.
    الگوریتم ژنتیک سادهالگوریتم ژنتیک ساده

     

     

     

     

     

     

     

     

    شکل فوق چگونگی کارکرد الگوریتم ژنتیک ساده را نشان می‌دهد. نقاط سبز اعضای جمعیت منتخب از نسل قبلی را نشان می‌دهند. نقاط آبی فرزندانی هستند که مجموعه راه‌حل‌های احتمالی را ایجاد می‌کنند. نقطه قرمز هم نشانگرِ بهترین راه‌حل است.
    الگوریتم‌های ژنتیک با شناسایی مجموعه متنوعی از راه‌حل‌های احتمالی به منظور تکثیر نسل بعدی نقش مهمی در تنوع ایفا می‌کنند. با این حال، با گذشت زمان اکثر راه‌حل‌ها در جمعیت منتخبِ بازمانده به سمت بهینه محلی همگرا می‌شوند.
    نسخه‌های پیچیده‌تری از الگوریتم‌های ژنتیک هم وجود دارند که از جمله آن‌ها می‌توان به CoSyNe، ESP و NEAT اشاره کرد. در این الگوریتم‌ها، راه‌حل‌های مشابه در جمعیت، با گونه‌های مختلف خوشه‌بندی می‌شوند تا از تنوع و گوناگونی در طی زمان اطمینان حاصل شود.

    استراتژی تکاملی سازگاری ماتریس کوواریانس(CMA-ES)

    یکی از معایب الگوریتم‌های ژنتیک ساده و استراتژی تکاملی ساده این است که پارامتر نویز، انحراف معیار ثابتی دارد. گاهی اوقات می‌خواهیم کاوش بیشتری انجام داده و انحراف معیار فضای جستجویمان را افزایش دهیم. گاهی اوقات هم به سطحی کافی از اطمینان رسیده‌ایم و می‌دانیم که جواب بهینه نزدیک است. بنابراین فقط باید به تنظیم دقیق جواب بپردازیم. ما می‌خواهیم فرایند جستجو به شکل زیر انجام شود:

    استراتژی تکاملیاستراتژی تکاملی

     

     

     

     

     

     

     

     

     

    این همان چیزی است که به دنبالش بودیم. فضای جستجویِ نشان داده شده در شکل فوق با استراتژی تکاملیِ «CMA-ES» ساخته شده است. «CMA-ES» الگوریتمی است که می‌تواند نتایج هر نسل را ثبت کند و به شکلی مناسب به افزایش یا کاهش فضای جستجو در نسل بعدی بپردازد.
    این الگوریتم نه تنها خود را برای میانگین μ و پارامترهای سیگما را سازگار می‌کند، بلکه می‌تواند ماتریس کوواریانس کامل فضای پارامتر را محاسبه کند. در هر نسل، «CMA-ES» پارامترهای یک توزیع نرمال چندمتغیره  multi-variate normal distribution  را برای نمونه‌گیری از راه‌حل‌ها فراهم می‌کند. بنابراین، این الگوریتم از کجا می‌داند که فضای جستجو را چگونه افزایش یا کاهش دهد؟
    قبل از بحث درباره روش کارکرد آن، بگذارید چگونگی تخمین ماتریس کوواریانس را با هم مرور کنیم، چرا که برای درک روش «CMA-ES» در بخش‌های بعدی اهمیت زیادی دارد. اگر بخواهیم ماتریس کوواریانس کل جمعیت نمونه‌گیری شده را تخمین بزنیم، می‌توانیم از مجموعه معادلات زیر استفاده کنیم.
    از این معادله‌ها می‌توان برای محاسبه تخمین درست نمایی بیشینه از یک ماتریس کوواریانس نیز استفاده کرد. در ابتدا باید میانگین هر کدام از xi و yi را محاسبه کرد.استراتژی تکاملی

    عبارات ماتریس کوواریانس ۲×۲ به صورت زیر خواهد بود:

    استراتژی تکاملی

    البته این مقادیر میانگین تخمین زده شده ux​​ و uy​​ و عبارات کوواریانس σ​x ، σ​y، σ​xy فقط برآوردی از ماتریس کوواریانس حقیقی هستند و لزوماً برای ما فایده‌ای ندارند. «CMA-ES» فرمول محاسبه کوواریانسِ بالا را به شیوه‌ای شفاف اصلاح می‌کند تا آن را با مسئله بهینه‌سازی سازگار کند.

    چگونگی انجام گام به گام این فرایند را توضیح می‌دهیم. در ابتدا، «CMA-ES» روی Nbest عدد از بهترین راه‌حل‌ها در نسل فعلی تمرکز می‌کند. برای سهولت کار، بگذارید فرض کنیم Nbest برابر با ۲۵ درصد از تعداد راه‌حل‌ها باشد. پس از مرتبط‌سازی راه‌حل‌ها  پس از مرتبط‌سازی راه‌حل‌ها بر اساس میزان ارزیابی‌شان، میانگین میانگین u(g+1) نسل بعدی (g+1) براساس ۲۵ درصد از بهترین جواب‌های نسل فعلی مورد محاسبه قرار می‌گیرد. بنابراین فرایند مذکور به صورت زیر انجام می‌شود:استراتژی تکاملی

    در گام بعدی، فقط از ۲۵ درصد راه‌حل برتر برای تخمین ماتریس کوواریانس C(g+1) نسل بعدی استفاده می‌شود، اما u(g+1) نسل فعلی هم به جای پارامترهای به‌روزرسانی شده u(g+1) که قبلاً محاسبه کرده بودیم، مورد استفاده قرار می‌گیرد:
    استراتژی تکاملی
    با برخورداری از مجموعه σ​x ، σ​y،  uy ،ux و σ​xy پارامترها برای نسل بعدی (g+1)، امکان نمونه‌گیری از نسل بعدیِ راه‌حل‌های احتمالی فراهم میشود.
    در زیر، مجموعه‌ای از اَشکال را آورده‌ایم که چگونگیِ استفاده از نتایج نسل فعلی (g) را برای تولید راه‌حل در نسل بعدی(g+1) نشان می‌دهد:
    استراتژی تکاملی

    ۱. امتیاز برازش هر راه‌حل احتمالی در نسل (g) را محاسبه کنید.
    ۲. آن ۲۵ درصد راه‌حل برتر در جمعیت نسل (g) را جدا کنید (به رنگ بنفش).
    ۳. با استفاده از بهترین راه‌حل‌ها و میانگین u(g) نسل فعلی (نقطه سبز)، ماتریس کوواریانس C(g+1) نسل بعدی را محاسبه کنید.
    ۴. مجموعه جدیدی از راه‌حل‌های احتمالی را با استفاده از میانگین به‌روزرسانی شده u(g+1) و ماتریس کوواریانس C(g+1) نمونه‌گیری کنید.
    بیایید یک بار دیگر جزئیات این مسئله را در کل فرایندِ جستجو بررسی کنیم:

    استراتژی تکاملیاستراتژی تکاملی

     

     

     

     

     

     

     

     

     

    از آنجایی که «CMA-ES» می‌تواند میانگین و ماتریس کوواریانس را با استفاده از اطلاعات حاصل از بهترین راه‌حل‌ها تنظیم و هماهنگ کند، وقتی که راه‌حل‌ها فاصله زیادی با هم داشته باشند، می‌تواند شبکه وسیع‌تری را در بر گیرد؛ یا حتی وقتی بهترین راه‌حل‌ها فاصله نزدیکی با هم دارند، فضای جستجو را تنگ‌تر کند.
    در این مقاله سعی شده الگوریتم «CMA-ES» را تا حد زیادی ساده‌سازی کنیم. این الگوریتم یکی از متداول‌ترین و مشهورترین الگوریتم‌های بهینه‌سازی به حساب می‌آید که محققان زیادی آن را برای انجام کارهای تحقیقاتی خود انتخاب می‌کنند. تنها عیب الگوریتم «CMA-ES» این است که اگر تعداد پارامترهای مدل خیلی زیاد باشد، عملکردش دچار اختلال می‌شود. وقتی فضای جستجو کمتر از ده هزار پارامتر باشد، به نظر الگوریتم «CMA-ES» انتخاب مناسبی است؛ در صورتی که ما به اندازه کافی صبور باشیم.

    استراتژی‌های تکاملی عصبی


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

    یکی از نقاط ضعف الگوریتم‎های بررسی شده تا به اینجا، این است که اکثر راه‌حل‌ها را کنار می‌گذارند و فقط بهترین راه‌حل‌ها را نگه می‌دارند. راه‌حل‌های ضعیف حاوی اطلاعاتی درباره مواردی هستند که نباید آن‌ها را انجام داد. از این نوع اطلاعات می‌توان به شکل بهتری برای برآورد نسل بعدی استفاده کرد.
    در مقاله ای که سال ۱۹۹۲ میلادی منتشر شد، ویلیام از روشی برای تخمین گرادیان پاداش‌های مورد انتظار در رابطه با پارامترهای مدل یک شبکه عصبی سخن گفته بود.
    در این مقاله، استفاده از «REINFORCE» در بخش ششم مقاله به عنوان استراتژی تکاملی پیشنهاد شد. مورد ویژۀ «REINFORCE-ES» در بخش‌های بعدی مقاله هم مورد بحث و بررسی قرار گرفت. در این روش می‌خواهیم از کلیه اطلاعاتِ مربوط به هر یک از اعضای جمعیت (خوب یا بد) استفاده کنیم تا سیگنال گرادیان را تخمین بزنیم؛ سیگنالی که می‌تواند کل جمعیت را به جهت بهتری در نسل بعدی هدایت کند.
    از آنجا که تخمینِ گرادیان در دستور کار ما قرار دارد، می‌توانیم از این گرادیان در قانون به‌روزرسانی استاندارد گرادیان کاهشی تصادفی(SGD)  Stochastic Gradient Descent (SGD) برای یادگیری عمیق استفاده کنیم. امکان استفاده از این گرادیان تخمینی با «Momentum SGD»، «RMSProp» یا «Adam» نیز وجود دارد. هدف این است که امتیاز مورد انتظارِ برازش در راه‌حل‌های نمونه‌گیری شده افزایش پیدا کند. اگر نتیجه به اندازه کافی خوب باشد، در این صورت بهترینِ عضوِ جمعیت حتی عملکرد بهتری از خود بر جای خواهد گذاشت. بنابراین، بهینه‌سازی در این مورد روش معقولی است. افزایش امتیاز مورد انتظارِ برازش در راه‌حل نمونه‌گیری شده به این کار شبیه است که امتیاز برازش کل جمعیت را افزایش دهیم.
    اگر z یک بردار راه‌حل باشد که از تابع توزیع احتمال π(z,θ) نمونه‌گیری شده است، می‌توان مقدار مورد انتظار تابع هدف F را به ترتیب زیر تعریف کرد:استراتژی تکاملی

    که در آن θ پارامترهای تابع توزیع احتمال هستند. برای مثال، اگر π را یک توزیع نرمال در نظر بگیریم، در این صورت θعبارت است از μو σ. در مسائل دو بعدی ساده که پیش ازاین مطرح کردیم، هر z یک بردار دوبعدی (x, y) است.
    مقاله «NES» مشتق خوبی از گرادیان J(θ) نسبت به θ ارائه می‌کند. استفاده از روش log-likelihood مانند آنچه که در الگوریتم REINFORCE ارائه شده، به ما اجازه می‌دهد که گرادیان J(θ) را به صورت زیر محاسبه کنیم:استراتژی تکاملی

    در اندازه جمعیت N، که راه‌حل‌های zN  ….. z۳ ،z۲  ، z۱  را در اختیار داریم، می‌توانیم این گرادیان را بصورت زیر تخمین بزنیم:
    استراتژی تکاملی

    با این گرادیان، می‌توان از پارامتر میزان یادگیری α استفاده کرد و شروع به بهینه‌سازی پارامترهای θدر π کرد؛ به طوری که راه‌حل‌های نمونه‌گیری شده به امتیاز بالایی در تابع هدف F می‌رسند. با استفاده از SGD (یا Adam) هم می‌توان θ را برای نسل بعدی به‌روزرسانی کرد:

    استراتژی تکاملی

     

     

    سپس مجموعه جدیدی از راه‌حل‌های نامزد z را از این pdf به‌روزرسانی شده نمونه‌گیری کرده و تا جایی ادامه دهیم که راه‌حل رضایت‌بخش بدست آید. در بخش ۶ از مقاله «REINFORCE»، ویلیامز فرمول‌های فرم بسته ​∇θ​​ logπ(zi,θ) برای مورد ویژه ای که در آن π(z, θ) یک توزیع نرمال چند متغیره فاکتورشده است، را مورد محاسبه قرار داده است.
    در این مورد خاص θ عبارت است از بردارهای μو σ. بنابراین، هر عنصر راه‌حل را می‌توان از توزیع نرمال تک‌متغیری Zj ~  N(uj , σj )  نمونه‌گیری کرد. فرمول‌های فرم بستۀ مربوط به ∇θ​​ logπ(zi,θ) برای هر عنصر از بردار θدر هر راه‌حل در جمعیت جواب‌ها به صورت زیر محاسبه می‌شود:استراتژی تکاملی

    برای شفافیت در کار می‌توان از شاخص j برای شمارش در فضای پارامتر استفاده کرد و نباید این را با اندیس ii اشتباه گرفت که برای شمارش اعضای نمونه‌گیری شده در جمعیت به کار برده می‌شود. در مسائل دوبعدی، شرایط زیر حاکم است:

    Z۱ =  x ,  z۲ = y , μ۱ = μx ، μ۲ = μy، σ۱= σx، σ۲ = σy

    این دو فرمول را می‌توان در فرمول گرادیان تقریبی جایگذاری کرد تا قوانین به‌روزرسانیِ صریح μو σ بدست آید. در مقاله‌هایی که در بخش‌های قبلی اشاره شد، قوانین به‌روزرسانی صریح‌تری بدست آمد و ترفندهای دیگری هم معرفی شد، مثل نمونه‌گیری متضاد در PEPG که روش ما هم مبتنی بر آن است.در مقاله «NES»، استفاده از معکوسِ ماتریس اطلاعات Fisher در قانون به‌روزرسانیِ گرادیان مد نظر قرار گرفت. اما مفهوم کلی اساساً با سایر الگوریتم‌های استراتژی تکاملی یکسان است. یعنی میانگین و انحراف معیار توزیع نرمال چندمتغیری در هر نسل جدید به‌روزرسانی می‌شود و مجموعه جدیدی از راه‌حل‌ها با توزیع به‌روزرسانی شده انتخاب می‌شوند. در زیر تصویری از این الگوریتم به نمایش درآمده است. فرمول‌های توضیح داده شده در بخش‌های قبلی هم در اینجا به کار برده شده است:

    استراتژی تکاملی

    استراتژی تکاملی

     

     

     

     

     

     

     

     

    همان طور که می‌بینید این الگوریتم می‌تواند به‌صورت پویا σ را برای جستجو یا تنظیم فضای راه‌حل تغییر دهد. برخلاف CMA-ES، هیچ ساختار همبستگی در روش انجامِ ما وجود ندارد؛ بنابراین، توجهِ ما فقط روی نمونه‌های افقی یا عمودی است. هرچند در صورت نیاز می‌توانیم قوانین به‌روزرسانی را برای کل ماتریس کوواریانس به کار ببریم.
    این الگوریتم از دید ما الگوریتم خوب و کارآمدی است؛ زیرا σ می‌تواند وفق پیدا کند، بنابراین فضای جستجوی ما می‌تواند در طول زمان توسعه یابد یا محدود شود. چون پارامتر همبستگی در این روش استفاده نمی‌شود، بازده الگوریتم برابر است با O(N). پس اگر عملکرد CMA-ES به مشکل بخورد، می‌توان از PEPG استفاده کرد. معمولاً زمانی از PEPG استفاده می‌کنیم که تعداد پارامترهای مدل از چند هزار تخطی کرده باشد.

    استراتژی تکاملی Open AI

    در مقاله «OpenAI»، از یک استراتژی تکاملی که مورد خاصی از الگوریتم «REINFORCE-ES» است، استفاده می‌شود. این الگوریتم در بخش‌های قبلی توضیح داده شد. در عمل σ ثابت در نظر گرفته شده است، و فقط پارامتر u در هر نسل بروز رسانی می‌شود. در شکل زیر، چگونگی کارکرد این استراتژی نشان داده‌ شده است بطوری که پارامتر σ ثابت می‌باشد..
    این مقاله علاوه بر ساده‌سازی مراحل کار، قانون به‌روزرسانی را هم اصلاح کرده است که می‌تواند برای پردازش موازی در ماشین‌های مختلف استفاده شود. بر اساس قانون به‌روزرسانیِ آن‌ها، طیف وسیعی از اعداد تصادفی با استفاده از یک مقدار ثابت از پیش محاسبه شده‌اند.
    با انجام این کار، هر عامل می‌تواند پارامترهای عوامل دیگر را در طول زمان تکثیر کند، و هر عامل تنها نیاز دارد یک عدد که همان نتیجه تابع ارزیابی نهایی است را با سایر عامل‌ها به اشتراک بگذارد. این کار زمانی اهمیت پیدا می‌کند که بخواهیم استراتژی‌های تکاملی را برای هزاران یا میلیون‌ها عامل که در ماشین‌های مختلف واقع شده‌اند، به کار ببریم. از آنجا که شاید مقدور نباشد در هر به‌روزسانی نسل، کل بردار راه‌حل را یک میلیون بار منتقل کنیم، بهتر است فقط به انتقال نتایج برازش نهایی بسنده کنیم. محققان در مقاله خود نشان داده‌اند که با استفاده از ۱۴۴۰ عامل در Amazon EC2 می‌توانند مسئله راه رفتن Mujoco Humanoid را تقریباً در ده دقیقه حل کنند.
    از نظر ما، قانون به‌روزرسانی موازی باید در الگوریتم اصلی به خوبی عمل کند چرا که امکان به‌کارگیری σ نیز وجود دارد؛ اما شاید در عمل بخواهیم در آزمایش‌های محاسبات موازی بزرگ‌مقیاس، تعداد را کاهش دهیم. در این مقاله مهم، بسیاری دیگر از جنبه‌های کاربردی استراتژی تکاملی در کارهای RL-style مورد بحث و بررسی قرار گرفته است.

    شکل دهی برازش

    اکثر الگوریتم‌هایی که در بخش‌های قبلیِ این مقاله اشاره شد، معمولاً با روشی موسوم به «شکل‌دهی برازش» یا «Fitness Shaping» ترکیب می‌شوند؛ مثل شکل‌دهی برازش رتبه‌محور  based-ranked fitness shaping method  که در این بخش معرفی خواهد شد. «شکل‌دهی برازش» این فرصت را به ما می‌دهد تا از دخالت داده‌های دورافتاده  outlier  در جمعیت جلوگیری کنیم و محاسبه گرادیان تقریبی بدون هیچ مشکل خاصی پیش رود:

    استراتژی تکاملی

    اگر در جمعیت، F(z^m)F(zm) خیلی بزرگتر از F(zi) باشد، در این صورت شاید گرادیان تحت تاثیر داده‌های دورافتاده قرار گیرد و احتمالِ گیر افتادنِ الگوریتم در بهینه محلی افزایش پیدا کند. برای رهایی از این مشکل می‌توانیم از یک تبدیل رتبه بر روی برازش‌ها استفاده کنیم. در این روش به جای استفاده از تابع برازش اصلی، نتایج را مرتب می‌کنیم سپس از یک تابع برازش افزوده شده که متناسب است با رتبه راه‌حل‌ها در جمعیت جواب، استفاده می‌کنیم. در شکل زیر مقایسه‌ای میان مجموعه اصلی برازش و برازش مرتب شده نشان داده شده است. استراتژی تکاملی

    همانطور که در شکل فوق قابل مشاهده است، جمعیت جواب ها دارای ۱۰۱ جواب است. در این حالت ابتدا هر یک از جواب‌ها بوسیله تابع برازش اصلی ارزیابی می‌شود، سپس جواب‌ها بر اساس برازش‌شان مرتب می‌شوند. در این مرحله مقدار برازش افزوده شده -۰.۵ به بدترین جواب، -۰.۴۹ به دومین بدترین، …، ۰.۴۹ به دومین بهترین و ۰.۵ به بهترین جواب اختصاص داده می‌شود.
    این مجموعه برازش‌های افزوده شده بجای برازش‌های حاصل از تابع ارزیابی واقعی، برای محاسبۀ به‌روزرسانیِ گرادیان استفاده خواهد شد. این روش تا حد زیادی به به‌کارگیری روش نرمال‌سازیِ باخ  Batch Normalization  در نتایج شباهت دارد. روش‌های جایگزینی برای شکل‌دهی برازش وجود دارد، اما همه آن‌ها اساساً در پایان به نتایج مشابهی می‌رسند. اگر تابع هدف برای یک شبکه سیاست داده شده، غیر قطعی  non-deterministic  باشد، شکل‌دهی برازش می‌تواند در کارهای RL خیلی مفید باشد، چرا که در این نوع محیط‌ها شاهد ایجاد تصادفیِ نقشه‌ها هستیم و مخالفان، سیاست‌های تصادفی در پیش می‌گیرند. این روش کارآیی چندانی در بهینه‌سازیِ توابع جبری قطعی که رفتار خوبی دارند، ندارد. استفاده از این روش می‌تواند زمان لازم برای رسیدن به راه‌حل مناسب را نیز افزایش دهد.

    MNIST

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

    از آنجا که همه الگوریتم‌های ML باید در MNIST مورد آزمایش قرار گیرند، سعی کردیم الگوریتم‌های گوناگون استراتژی تکاملی که در این مقاله توضیح داده شد را برای یافتن وزن های یک convnet دو لایه کوچک جهت دسته بندی عکس، بکار ببریم و بررسی کنیم. عملکرد این روش‌ها در مقایسه با SGD چگونه است. «convnet» حدود یازده هزار پارامتر دارد. بنابراین می‌توانیم از الگوریتم CMA-ES استفاده کنیم. کدها و آزمایش‌ها در این بخش قابل دسترس هستند.
    نتایج روش‌های گوناگونِ استراتژی تکاملی در بخش زیر بیان شده‌اند که در آنها اندازه جمعیت جواب‌ها ۱۰۱ مورد است و تعداد تکرارها نیز ۳۰۰ دوره در نظر گرفته شده است. آن دسته از پارامترهای مدل را زیر نظر داریم که بهترین عملکرد را در پایان هر دوره بر روی کل مجموعه آموزشی دارند و ارزیابی این مدل بر روی داده‌های آزمایش پس از اتمام ۳۰۰ تکرار انجام می‌گیرد. جالب است که گاهی دقت مجموعه آزمایش در مدل‌هایی که امتیاز پایینی دارند، بالاتر از مجموعه آموزشی است.

    استراتژی تکاملی

    استراتژی تکاملی

    نمی‌توان این نتایج را به طیف گسترده تعمیم داد، چرا که نباید به یک دوره عملیات اکتفا کرد و به طور متوسط نیاز به انجام ۵ تا ۱۰ عملیات است. نتایجی که بر پایه یک دوره عملیات باشند، نشان می‌دهند که الگوریتم «CMA-ES» بهترین عملکرد را بر روی MNIST دارد، اما عملکرد الگوریتم PEPG نیز چندان تفاوتی با آن ندارد. هر دوی این الگوریتم‌ها حدود ۹۸ درصد از دقت آزمایش را کسب کرده‌اند؛ یعنی یک درصد کمتر از مبنای «SGD/ADAM». شاید قابلیت تغییر پویایِ ماتریس کوواریانس و پارامترهای انحراف معیار در هر نسل باعث شده تا وزن‌ها را بهتر از نسخۀ ساده‌تر «OpenAI» تنظیم کنند.

    خودتان امتحان کنید

    احتمالاً همه الگوریتم‌هایی که در مقاله حاضر معرفی شدند، به صورت منبع آزاد در دسترس باشند. «نیکولاس هنسن» نویسنده «CMA-ES» یک پیاده‌سازی مبتنی بر numpy را برای CMA-ES ارائه داده است. با استفاده از پیاده سازی ایشان، الگوریتم های دیگری مانند الگوریتم ژنتیک ساده، PEPG و OpenAI’s را پیاده‌سازی نمودم و در در یک فایل پایتون کوچک به نام es.py قرار دادم. با این روش من می‌توانم تنها با تغییر یک خط کد، به راحتی الگوریتم های ES را با یکدیگر مقایسه کنم:

    می‌توانید به فایل «es.py» در «GitHub» و نمونه‌های نوت‌بوک «IPython» نگاه کنید. در نوت‌بوک «IPython»، که با es.py همراه است، من نشان دادم که چگونه میتوان از ES جهت حل تابع Rastrigin با بیش از ۱۰۰ بعد که دارای نقاط بهینه محلی بیشتری است، استفاده شود. توجه شود که مسئله ۱۰۰ بعدی بسیار پیچیده‌تر از مسئله دو بعدی است که در مثال‌های این مقاله آورده شد. در شکل زیر مقایسه عملکرد الگوریتم‌های ES بر روی مسئله ۱۰۰ بعدی Rastrigin آورده شده است.

    استراتژی تکاملی

    در مسئله ۱۰۰ بعدی «Rastrigin» هیچ یک از ابزارهای بهینه‌ساز به راه‌حل بهینه سراسری نرسیده‌اند، اگرچه الگوریتم «CMA-ES» عملکرد خوبی داشته است.
    PEPG در جایگاه دوم قرار گرفت و OpenAI-ES و الگوریتم ژنتیک در جایگاه‌های بعدی قرار گرفتند. باید به تدریج σ را در OpenAI-ES کاهش می‌دادیم تا عملکرد خوبی در این کار داشته باشد:استراتژی تکاملی

    دانشگاه علوم پزشکی و پژوهشگاه ICT در حوزه‌ی هوش مصنوعی تفاهم‌نامه امضا کردند

    مقاله قبلی

    پژوهشگاه ارتباطات صاحب مرکز هوش مصنوعی شد

    مقاله بعدی

    شما همچنین ممکن است دوست داشته باشید

    بیشتر در آموزش

    نظرات

    پاسخ دهید

    نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *