برنامه ريزي غيرخطي پيچيده با استفاده از يك الگوريتم فراابتكاري و حل عدی آن
محورهای موضوعی : مدیریت دانش
علی اصغر توفیق
1
منیره السادات محمودی
2
(دانشگاه صنعتی امیرکبیر)
کلید واژه: مسئله حداقل سازي حجم بيضي الگوريتم آنيلينگ شبيه سازي شده,
چکیده مقاله :
از آنجايي كه الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند، در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد. به علاوه الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. يکي از مسائل برنامه ريزي غير خطي، مسئله ي حداقل سازي حجم بيضي اي به مرکز O که مجموعه اي متناهي از نقاط فضا را پوشش مي دهد، مي باشد. اين مسئله تنها در فضاي دو بعدي و آن هم با راه حل هاي ابتکاري به سختي قابل حل است. اما در سه بعد و بالاتر به علت افزايش بي رويه ي حجم محاسبات، حل صريح اين مسئله بسيار سخت و دشوار مي شود. در حل اين مسئله از الگوريتم SA استفاده شده و مسئله ي موردنظر در دو حالت فضاي دو بعدي و سه بعدي حل شده و در فضاي n بعدي نيز قابل تعميم است.
Since exact algorithms are able to find the optimal solution exactly, they are not effective for solving the complicated and difficult optimization problem and the time of problem solving is increased exponentially; moreover approximate algorithms are able to find the approximate solution (which is very near to the optimal solution) for very complicated and difficult optimization problem in a short period of time. One of the well-known nonlinear programming problems is finding minimum volume ellipsoid covering a finite set of points problem. This problem is solvable for two dimensional space, however heuristic methods are even used to solve it in two dimensional space are very difficult. It would be difficult to achieve the exact solution for three dimensions or more because of huge volume of calculation. In this paper, SA algorithm is used and the problem is solved in two and three dimensions; in addition it can be used for n dimensions as well.