OptaPlanner یک راهکار سبک و متن‌باز به زبان جاوا برای حل مسائل ارضای محدودیت (CSP) است. با این نرم افزار بهینه سازی ریاضی می‌توان CSP را از طریق روش‌های ابتکاری یا فراابتکاری حل کرد. این موتور بهینه‌سازی قابل یکپارچه‌سازی با بسیاری از بسترهای موجود است. OptaPlanner کمک بزرگی به برنامه‌نویسان Java می‌کند تا بتوانند مسائل بهینه‌سازی ریاضی با ابعاد بالا را به‌طور کارا حل کنند یا برای آنها پاسخ‌های شدنی مناسب بیابند. علاوه‌بر جاوا، انطباق این نرم‌افزار متن‌باز با سایر زبان‌های JVM مثل Kotlin یا Scala نیز وجود دارد.
گستره مسائلی که OptaPlanner می‌تواند در حل آنها کمک کند، به گستره مسائل زمان‌بندی و برنامه‌ریزی مبتنی‌بر مدل‌های مختلف برنامه‌ریزی ریاضی است. مسائل معروفی همچون برش، مسیریابی وسیله نقلیه، برنامه‌ریزی نگهداری و تعمیرات، تخصیص، زمان‌بندی کلاس، بهینه‌سازی ابری، زمان‌بندی کار کارگاهی، بین پکینگ یا بسته‌بندی، بهینه‌سازی مالی، برنامه‌ریزی تخصیص بیمارستانی، برنامه‌ریزی هواپیمایی و … از جمله مسائل تحت پوشش این بسته نرم‌افزاری برای حل مسائل بهینه‌سازی ریاضی هستند. اپتاپلنر برای مسائل بهینه‌سازی NP-Complete و NP-hard مناسب است و براساس ساختار تعریف‌شده در مسائل خود عمل می‌کند. در این راستا، الگوریتم‌های بهینه‌سازی مبتنی‌بر هوش مصنوعی (مثل Tabu Search یا تبرید شبیه‌سازی‌شده) نیز توسط آن به کار گرفته می‌شوند.
دانلود و نصب OptaPlanner
برای نصب اپتاپلنر می‌تواند فایل zip بسته نصبی آن را از اینجا دانلود کنید. سپس اسکریپت متناسب لینوکس / مک یا ویندوز را مطابق زیر اجرا کنید. لازم به ذکر است که OptaPlanner هیچ وابستگی GUI ندارد. همان‌طور که روی دسکتاپ اجرا می‌شود کافی است که آن را روی یک سرور یا Mobile JVM اجرا کنید.
در لینوکس یا مک:
$ cd examples $ ./runExamples.sh
در ویندوز:
$ cd examples $ runExamples.bat
نمای GUI از مثال‌های بهینه‌سازی OptaPlanner
اگر بخواهید مثال‌ها را از طریق یک IDE (IntelliJ، Eclipse یا NetBeans) فراخوانی کنید یا به کمک Maven، Gradle، Ivy، Buildr یا ANT آن را به کار ببندید بهتر است این راهنما را مطالعه کنید.
کار با OptaPlanner
در OptaPlanner، محدودیت‌ها روی اهداف موردنظر تعریف شده و کدهای موجود در آن فراخوانی می‌شوند. بنابراین نیازی نیست که محدودیت‌ها را در قالب روابط ریاضی به‌عنوان ورودی آن تعریف کنید.
حل یک مسأله برنامه‌ریزی با OptaPlanner شامل گام‌های زیر است:
- مسأله برنامه‌ریزی خود را در قالب یک annotation با عنوان
PlanningSolution@مدل‌سازی کنید. مثلا از کلاسNQueensبرای حل مسأله چند وزیر استفاده کنید یا برای حل مسأله زمان‌بندی شیفت‌های کاری، کلاسShiftAssignmentرا فراخوانی کنید. - یک
Solverرا تنظیم کنید. مثلا به تناسب مسأله از روش ابتکاری مثل First Fit یا روش فراابتکاری مثل الگوریتم ژنتیک استفاده کنید. - دیتاست مسأله خود را فراخوانی کنید. مثلا نمونه چهار وزیر در مثال مسأله
NQueensداده‌های شما را در لایه داده ایجاد می‌کند. - با استفاده از
solve(problem)مسأله را حل کرده و بهترین پاسخ را بیابید.
مدل‌سازی یک مسأله برنامه‌ریزی
OptaPlanner دست‌کم به این سه جزء برای تعریف مدل نیاز دارد:
- امتیاز (Score)
- Problem Fact
- Planning Entity
هر PlanningSolution@ یک امتیاز دارد. امتیاز یک راه مشهود برای مقایسه دو پاسخ است. پاسخی که امتیاز بالاتری داشته باشد، بهتر است. بنابراین Solver تلاش می‌کند پاسخی را پیدا کند که در میان همه پاسخ‌های ممکن، بالاترین مقدار Score را داشته باشد. OptaPlanner نمی‌تواند به‌طور خودکار بفهمد که کدام پاسخ برای کسب‌وکار شما بهترین است؛ لذا شما باید تعیین کنید که با داشتن یک نمونه PlanningSolution@ چگونه باید امتیاز را براساس نیازمندی کسب‌وکارتان محاسبه نمود. به‌منظور پیاده‌سازی هر محدودیت کسب‌وکار باید یک «محدودیت امتیاز» را فرموله کنید. تعریف این محدودیت‌ها از طریق روش‌های منعطفی همچون علامت امتیاز (مثبت یا منفی برای بیشینه یا کمینه کردن محدودیت)، وزن امتیاز (هزینه یا درآمد حاصل از محدودیت)، سطح امتیاز (سخت، ساده و … برای اولویت‌بندی کردن محدودیت‌ها) و امتیازبندی پارتو (که به‌ندرت استفاده می‌شود) امکان‌پذیر است.
کلاس problem fact توسط محدودیت‌های امتیاز مورد استفاده قرار می‌گیرد اما در خلال برنامه‌ریزی تغییر می‌کند. مثلا Bed، Room، Shift، Employee، Topic، Period و … همگی problem fact هستند. ویژگی‌ها یا مشخصه‌هایی که در خلال برنامه‌ریزی تغییر می‌یابند متغیرهای برنامه‌ریزی (planning variables) هستند.
کلاس planning entity توسط محدودیت‌های امتیاز مورد استفاده قرار می‌گیرد و در ضمن برنامه‌ریزی تغییر پیدا می‌کند. برای مثال BedDesignation، ShiftAssignment، Exam و … مواردی از planning entity هستند. ویژگی‌ها یا مشخصه‌هایی که در خلال برنامه‌ریزی تغییر می‌یابند متغیرهای برنامه‌ریزی (planning variables) هستند.
برای مدل‌سازی یک مسأله باید این پرسش را از خود بپرسید: کدام کلاس در خلال برنامه‌ریزی تغییر می‌کند؟ کدام کلاس دارای متغیرهایی است که می‌خواهیم توسط Solver تغییر یابند؟ این کلاس، یک planning entity است. اغلب مسائل مدنظر در OptaPlanner فقط یک کلاس planning entity دارند. همچنین، اغلب مسائل فقط یک متغیر برنامه‌ریزی به‌ازای هر کلاس planning entity دارند.
مستندات OptaPlanner
این یادداشت از مجموعه یادداشت‌های بخش فناوری آزمایشگاه تحقیق در عملیات است که نگاهی کلی به موتور بهینه‌سازی OptaPlanner دارد. این موتور حل‌کننده یا Solver برای حل مسائل ارضای محدودیت ـ به‌ویژه در حل مسائل بزرگ خود ـ مبتنی‌بر هوش مصنوعی نیز عمل می‌کند. برای دسترسی به توضیحات و مستندات بیشتر درباره این محصول می‌توانید به مستندات آموزشی آن در وب‌سایت OptaPlanner و یا به GitHub آن مراجعه کنید.