광역 최적화를 위한 통계적 중첩분할 방법

Abstract

Nested partitions (NP) method is a new type of random search method for global optimization problems. The method has good characteristics such as the convergence to the global optimum and the finite time behavior. Thus, the method has been exploited in many areas such as production planning, data mining and logistics. Even though the efficacy of NP method has been proven from a number of research, only a few studies suggested the enhanced version of NP method. In this dissertation, a new type of NP method, called statistical nested partitions (SNP) method, is proposed. Using the information of confidence interval, SNP greatly reduced the computational effort when sampling the points. The confidence interval could be a normal distribution of the mean value or a Weibull distribution of the minimum value of the samples. Experimental results show that SNP outperforms other heuristics and significantly reduces the computational time comparing to the original NP method. Application to the Travelling Salesman Problem also shows that SNP method is effective in discrete cases. Ordered Nested partitions (ONP) method is another enhanced version of NP method. It can handle multi-dimensional problems, which are hard to solve by the original NP method. By fixing the value of the elements one by one, ONP can solve multi-dimensional problems efficiently.