۲۹ شهریور ۱۳۹۹

بسته نرم افزاری Primitives

انیمیشنی که مشاهده می‌کنید، خروجی یک بسته نرم‌افزاری به نام Primitives است که به صورت متن‌باز در گیت‌هاب [+] در دسترس قرار دارد. کد این نرم‌افزار، با استفاده از زبان Go و توسط «مایکل فوگلمن» نوشته شده است.

خروجی این برنامه، می‌تواند به صورت رستری (فرمت PNG و JPG)، برداری (فرمت SVG) و یا انیمیشن (فرمت GIF) باشد. برای ساخت خروجی نیز، می‌توان مشخص کرد که شکل یا عنصر پایه (Primitive) چه باشد؛ خط، دایره، مستطیل، بیضی، مثلث، چندضلعی و حتی ترکیب همه این‌ها.

اما این نرم‌افزار چطور این کار را انجام می‌دهد؟ مسأله ما، یافتن یک نسخه تقریبی از تصویر ورودی است که در آن، از عناصر پایه مشخصی استفاده شده است. در واقع، این یک مسأله بهینه‌سازی است که البته پاسخ زیر-بهینه (sub-optimal) برای آن نیز، کار ما را راه می‌اندازد.

اما برای ساده‌تر کردن حل این مسأله بهینه‌سازی، یک ترفند جالب به کار رفته است. حل مسأله آن طور که هست، خیلی سخت است؛ اما می‌توان آن را تبدیل به یک فرایند بهینه‌سازی دنباله‌ای (Sequential Optimization) کرد. یعنی به جای حل یک مسأله بزرگ و سخت، چند مسأله ریز و متوالی را حل کنیم.

این تکنیک رایجی در حل مسائل بهینه‌سازی است و کاربردهای فراوانی در حوزه‌های مختلف دارد. در مورد این کاربرد خاص، مسأله اصلی به پیدا کردن فقط و فقط یک شکل یا عنصر پایه در هر مرحله، شکسته می‌شود. یعنی در هر مرحله، فقط یک عنصر افزوده می‌شود. البته پاسخ، غالبا زیر-بهینه خواهد بود.

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

در پروژه Primitive از الگوریتم‌های بهینه‌سازی ساده‌ای استفاده شده است و نتایج هم قابل قبولند؛ هم سرعت خوبی دارند و هم کیفیت پاسخ‌ها مطلوب است. در این برنامه نسخه تغییر یافته الگوریتم‌های تپه‌نوردی (Hill Climbing) و شبیه‌سازی تبرید (Simulated Annealing) به کار رفته‌اند.

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

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

۲۳ اردیبهشت ۱۳۹۸

YPEA: الگوریتم‌های تکاملی یارپیز

زمستان سال ۱۳۹۵ بود که پیاده‌سازی یکی از ایده‌های قدیمی‌ام را شروع کردم که سال‌ها ذهنم را به خود مشغول کرده بود. هدفم ایجاد یک ساختار واحد و منسجم، برای مدل‌سازی، تعریف و حل «مسائل بهینه‌سازی» (Optimization Problem) با استفاده از روش‌های «محاسبات تکاملی» (Evolutionary Algorithm) و «فراابتکاری» (Metaheuristic) بود. انگیزه اصلی من برای انجام این کار، طی ارتباطم با دانشجوها شکل گرفت. سال‌ها، با صدها دانشجو به صورت مستقیم در ارتباط بوده‌ام و می‌دانم که یکی از بزرگ‌ترین مشکلات محققین و دانشجویان، به ویژه افرادی که در برنامه‌نویسی چندان توانمند نیستند، تعریف ساختار مسأله و متغیرهای آن است.

۱ بهمن ۱۳۹۷

پاسخ به پرسشی پیرامون الگوریتم ژنتیک و مسائل بهینه‌سازی — پادکست به همراه نسخه متنی

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

۲۸ تیر ۱۳۹۶

نکاتی از بهینه‌سازی مقید

ظاهرا از امروز، ۲۸ تیر ماه ۱۳۹۶، در اتوبان‌های تهران، در محل خروجی اتوبان‌ها، دوربین‌هایی تعبیه می‌شوند تا خروج‌های غیر اصولی را ثبت کنند. با نصب این دوربین‌ها، رانندگانی که بدون برنامه‌ریزی قبلی، طوری تغییر مسیر می‌دهند که مجبورند از جناغی‌های کنار اتوبان رد شوند، مشمول پرداخت جریمه خواهند شد. افرادی که ترافیک‌های سنگین چند ساعته را تجربه کرده‌اند، می‌دانند که اغلب ریشه ترافیک، عدم رانندگی صحیح و تعیین مسیر در زمان مناسب است. هر جا که قرار باشد، تصمیم‌گیری و اقدام از طرف رانندگان باشد، اغلب شاهد کندی سرعت و راه بندان هستیم. راه‌اندازی این دوربین‌ها، احتمالا باعث تصمیم‌گیری مناسب‌تر و به موقع توسط رانندگان خواهد شد.

۲ خرداد ۱۳۹۶

قطره قطره جمع گردد …

تا کنون در نوشته‌های متعددی، بیش از هر چیز دیگری، بر اهمیت کارهای کوچک تأکید کرده‌ام؛ چه خوب و چه بد. معتقدم اگر قرار است بهبودی در چیزی ایجاد شود، بهتر است به تدریج با گام‌های کوچک باشد. چرا که گام‌های بزرگ و آنی، حتی اگر مقدور باشند، امکان شکست و ریسک بالایی دارند.

۲۹ بهمن ۱۳۹۵

برقراری تعادل میان تمرکز و تنوع

بخش مهمی از مسائل کاربردی در حوزه‌های مختلف علمی و فنی، مربوط به حوزه بهینه‌سازی و جستجو است. الگوریتم‌های متنوعی هم برای حل این دسته از مسائل معرفی شده‌اند، که نوع مهمی از آن‌ها، الگوریتم‌های تکاملی هستند که تشکیل دهنده مبحث محاسبات تکاملی در هوش مصنوعی می‌باشند. یکی از اصول کلی که لازمه عملکرد مناسب یک الگوریتم بهینه‌سازی است، ایجاد تعادل بین دو فاکتور مهم است: اکتشاف (Exploration) و استخراج (Exploitation). یک الگوریتم موثر و کارآمد، باید بتواند میان این دو مولفه، تعادل مناسبی را برقرار کند.