ابعاد (Dimension) مسئله و فضای حالت در الگوریتم‌های بهینه‌سازی

دانشمندان و مهندسانِ تحقیقاتی، معمولاً سعی دارند تا با زبانی مشترک با یکدیگر صحبت کنند. آن‌ها در تلاشند تا با توافق بر سر یک سری کلیدواژه‌های واحد، بتوانند معنای نوشته‌ها و تحقیقات خود را به دیگران بفهمانند. هوش‌مصنوعی و زیرشاخه‌ی آن یعنی بهینه‌سازیِ هوشمند نیز از این قاعده مستثنی نیست. یکی از واژه‌ها و تعاریف اولیه و پایه‌ای که دانشمندان علوم کامپیوتر در حوزه‌ی هوش مصنوعی بر سر آن به توافق رسیده‌اند، واژه‌ی ابعاد (Dimensions) مسئله است. در واقع این واژه را می‌توان پایه‌ی اصلی برای بسیاری از مقالات و الگوریتم‌های بهینه‌سازی دانست. در این درس می‌خواهیم به بررسیِ این واژه و نحوه‌ی مقابله‌ی الگوریتم‌های بهینه‌سازی با این رویکرد را بررسی کنیم.

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

اجازه بدهید با یک مثال بحث را ادامه دهیم. فرض کنید یک اتومبیل مسابقه‌ای بدون سرنشین دارید و آن را از راه دور کنترل می‌کنید. در جلوی شما ۵ پیچِ تنظیم وجود دارد که ۳ تای آن‌ها اصلی است. دستگاهی کنترلی مانند شکل زیر:

پیچ اول (از سمت راست)، دور موتور را تنظیم می‌کند، پیچ دوم زاویه‌ی چرخ‌ها را تنظیم می‌کند، پیچ سوم زاویه‌ی بادگیر عقب را تنظیم می‌کند، پیچ چهارم میزان باز بودن دریچه‌ی احتراق سوخت را کم و زیاد می‌کند و بلاخره پیچ پنجم ارتقاع اتومبیل را نسبت به سطح زمین تنظیم می‌کند. مسابقه را شروع می‌کنید و بایستی با تنظیم درست این پیچ‌ها، در هر لحظه، حداکثرِ سرعت را به دست بیاورید. پس در این‌جا می‌خواهیم سرعت را حداکثر کنیم. در واقع خروجیِ تابع برازش (Fitness Function) در این‌جا میزان سرعت است. خروجیِ تابعِ برازش در واقع همان چیزی است که الگوریتم می‌خواهد آن را بهینه کند (یک نوع شاخص که میزان خوب یا بد بودن عملکرد را نشان می‌دهد – مثلاً در این‌جا سرعت شاخص است)

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

در واقع با کم و زیاد کردن پیچ‌های بالا، سعی دارید تا سرعت را بیشینه (Maximum) کنید. ولی هر کدام از پیچ‌ها بر روی یکدیگر تاثیر می‌گذارند و بایستی به نسبتی این سه پیچ تنظیم شوند تا سرعت بیشینه شود. حتماً می‌دانید که پیدا کردن سرعت بیشینه با توجه به حالت‌های مختلفِ این سه پیچ کمی دشوار و زمان‌گیر است. این‌جاست که الگوریتم‌های بهینه‌سازی فراابتکاری وارد می‌شوند و می‌توانند قدرت خود را در پیدا کردن یک حالت بهینه (مثلاً بیشترین سرعت یا چیزی نزدیک به آن) نشان دهند. در واقع این الگوریتم‌ها به جای این‌که تمامی حالات را امتحان کنند، با استفاده از تکنیک‌های مختلف، می‌توانند با جستجو در بخش‌هایی از فضای حالت، یک مقدار مناسب بهینه را در زمان کم پیدا کنند.

برای آن بتوانیم بهتر درک کنیم که فضای حالت چیست، همان مثالِ بالا (برای سه پیچ در مسابقه‌ی اتومبیل کنترلی) را در نظر می‌گیریم. شکل زیر را مشاهده کنید:

این شکل فضای حالت برای سه پیچ کنترل اتومبیل است. یادتان هست که ما سه پیچِ تنظیم داشتیم. حالا هر کدام از پیچ‌ها به یک بُعد نگاشت می‌کنیم. در واقع چون سه پیچ (پیچ‌های اصلی) داریم، فضای حالت، سه بُعدی شده است. در شکل بالا محیط رنگی همان مقدار خروجی تابع برازش (Fitness Function Output) است. هر چقدر که این صفحه قرمز‌تر شود به این معنی است که سرعت اتومبیل بالاتر رفته و بهینه‌تر شده است و هر چقدر صفحه آبی‌تر شود، یعنی سرعت اتومبیل کمتر شده و از بهینگی فاصله گرفته‌ایم. فرض کنید پیچِ اول، بر روی مقدار ۰/۴ تنظیم شود. پیچِ دوم بر روی مقدار ۱/۱ تنظیم شده و بلاخره پیچ سوم بر روی مقدار ۱/۰۰۹ قرار داشته باشد. نقطه‌ای که در شکل زیر مشخص است:

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

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

به مثال برگردیم. تا این‌جا ما با ۳ پیچ بازی می‌کردیم. یعنی فضای حالت ۳ بُعدی بود. حالا اگر هر ۵ پیچ را مورد استفاده قرار دهیم چه می‌شود؟ طبیعتاً فضای حالت ۵ بُعدی شده و سخت‌تر می‌شود. با توجه به این‌که نمی‌توان فضاهای حالت در بیشتر از ۳ بُعد را رسم کرد، سعی کنید در ذهن خود فضای حالت ۵ بُعدی را تصور کنید. متوجه می‌شوید که هر چقدر فضای حالت دارای ابعاد بیشتری باشد، جستجو پیچیده‌تر و سخت‌تر خواهد شد و نیاز ما به الگوریتم‌های فراابتکاری یا روش‌های دیگر بیشتر می‌شود.