الگوریتمی برای تقریب جواب بهینه سراسری مسائل بهینه‌سازی بر اساس تکنیک خوشه‌بندی در داده‌کاوی
محورهای موضوعی : تحقیق در عملیاتMohammad Alinejadmofrad 1 * , Mahtab Haddadpour 2 , Mohammad Dehghan Nayyeri 3
1 - گروه ریاضی، دانشکده علوم پايه، دانشگاه بجنورد، بجنورد، ايران
2 - گروه ریاضی، دانشکده علوم پايه، دانشگاه بجنورد، بجنورد، ايران
3 - گروه ریاضی، دانشکده علوم پايه، دانشگاه بجنورد، بجنورد، ايران
کلید واژه: Data mining, Clustering&lrm, , &lrm, Global optimization, &lrm, Reduced search space, Global optimal solution&lrm,
چکیده مقاله :
در برخی از مسائل بهینه‌سازی، یافتن جواب بهینه سراسری اهمیت فراوان دارد. اگر فضای جستجوی مسئله را بتوان به‌طور مداوم به‌گونه‌ای کوچک کرد که به احتمال زیاد شامل جواب بهینه سراسری باشد آنگاه می‌توان تقریب مناسبی برای جواب بهینه مسئله به دست آورد. در این مقاله برای کاهش فضای جستجو از تکنیک خوشه‌بندی در داده‌کاوی استفاده می‌شود. با استفاده تکراری از این تکنیک به همراه طرح یکنواخت از نوع نقاط مشبکه‌ای خوب برای تولید توزیع مناسبی از نقاط روی مرزها و درون فضای شدنی در هر تکرار، الگوریتمی تصادفی پیشنهاد می‌شود که قادر است تقریب مناسبی از جواب بهینه سراسری را بیابد. مقایسه نتایج حاصل از این الگوریتم با الگوریتم ژنتیک برای سه مسئله بهینه‌سازی نامقید غیرخطی نشان می‌دهد که الگوریتم پیشنهادی می‌تواند تقریب‌ها را با تعداد تکرار و زمان محاسباتی کمتری به دست دهد؛ همچنین اگر جواب بهینه سراسری روی مرزها واقع شده باشد، سرعت همگرایی آن در قیاس با الگوریتم ژنتیک به‌طور قابل توجهی بیشتر است.
Finding the global optimal solution is very important in some optimization problems. If the search space of the problem can be iteratively reduced in such a way that it most probably includes the global optimal solution, then a suitable approximation for the optimal solution of the problem can be obtained. In this article, the clustering technique of data mining is used to reduce the search space. By iteratively using this technique together with the uniform design of the good lattice points type to produce a suitable distribution of points on the boundaries and within the feasible region in each iteration, a stochastic algorithm is proposed that is able to find a suitable approximation of the global optimal solution. The comparison of the results of this algorithm with the genetic algorithm for three nonlinear unconstrained optimization problems shows that the proposed algorithm can obtain those approximations with a lower number of iterations and computational time; Furthermore, when the global optimal solution is located on the boundaries, the convergence speed, compared to the genetic algorithm, is significantly higher.
[1] R. Horst, and P. M. Pardalos. Handbook of Global Optimization. Springer (1995)
[2] A. Zhigljavsky, A. Zilinskas. Stochastic global optimization. Springer (2008)
[3] R. Horst, H. Tuy. Global Optimization (Deterministic Approaches). Springer (1996)
[4] A. Torn, A. Zilinskas. Global optimization. Springer (1989)
[5] M. Haddadpour, M. Alinejadmofrad, M. Dehghan Nayyeri. Reducing search space in optimization problems with data mining techniques. Towards Mathematical Sciences 2 (1): 110-121 (2022). Doi: 10.22067/tmsj.2022.42824
[6] T. Y. Chen, J. H. Huang. An efficient and practical approach to obtain a better optimum solution for structural optimization. Engineering Optimization 45 (8): 1005–26 (2013)
[7] T. Y. Chen, J. H. Huang. Application of data mining in a global optimization algorithm. Advances in Engineering Software 66: 24–33 (2013)
[8] J. Han, M. Kamber, J. Pei. Data Mining: Concepts and Techniques, 3rd ed.. Morgan Kaufmann (2011)
[9] K. T. Fang, Y. Wang. Number-Theoretic Methods in Statistics. Chapman and Hall. London (1994)
[10] K. T. Fang, Y. Wang, P. M. Bentler. Some applications of number-theoretic methods in statistics. Statistical Science 9 (3): 416–28 (1994)
[11] K. T. Fang, D. K. J. Lin. Uniform Experimental Designs and Their Application in Industry. Vol. 22. Handbook of Statistics. Elsevier Science (2003)
[12] W. Hopkins. Uniform Space-Filling Designs and Their Applications in Designed Experiments. M.Sc. thesis, Department of Mathematical Sciences. Montana State University (2018)
[13] J. Nocedal, and S. Wright. Numerical Optimization, 2nd.ed.. Springer (2006)
[14] Z. Tu, Y. Lu. A robust stochastic genetic algorithm (StGA) for global numerical optimization. IEEE Transactions on Evolutionary Computation 8 (5): 456–70 (2004)