Distribution Endpoint Estimation Assessment for the use in Metaheuristic Optimization Procedure

Jan Holesovky

doi:10.13164/mendel.2018.1.093

Jan Holesovky

DOI: https://doi.org/10.13164/mendel.2018.1.093

Keywords: metaheuristic optimization, endpoind estimation, extreme value, random search, bootstrap, order statistics

Abstract

Metaheuristic algorithms are often applied to numerous optimization problems, involving large-scale and mixed-integer instances, specifically. In this contribution we discuss some refinements from the extreme value theory to the lately proposed modification of partition-based random search. The partition-based approach performs iterative random sampling at given feasible subspaces in order to exclude the less favourable regions. The quality of particular regions is evaluated according to the promising index of a region. From statistical perspective, determining the promising index is equivalent to the endpoint estimation of a probability distribution induced by the objective function at the sampling subspace. In the following paper, we give a short review of the recent endpoint estimators derived on the basis of extreme value theory, and compare them by simulations. We discuss also the difficulties in their application and suitability of the estimators for various optimization instances.

References

de Haan, L., Ferreira, A.: Extreme Value Theory: An Introduction. Springer, New-York (2006).

Deme, E.H., Gardes, L., Girard, S.: On the estimation of the second order parameter for heavy-tailed distribution. REVSTAT 11(3), 277–299 (2013).

Dorigo, M., Blum, C.: Ant colony optimization: A survey. Theoretical Computer Science 344(2-3), 243–278 (2005).

Draisma, G., de Haan, L., Peng, L., Pereira, T.T.: A Bootstrap-based Method to Achieve Optimality in Estimatingthe Extreme-value Index. Extremes 2(4), 367–404 (1999).

Ferreira, A., de Haan, L., Peng, L.: On optimising the estimation of high quantiles of a probability distribution. Statistics 37(5), 401–434 (2003).

Fraga Alves, I., Neves, C.: Estimation of the finite right endpoint in the Gumbel domain. Statistica Sinica 24, 1811–1835 (2014).

Fraga Alves, M.I., Gomes, M.I., de Haan, L.: A new class of semi-parametric estimators of the second order parameter. Portugaliae Mathematica 60(1), 193–213 (2003).

Fraga Alves, I., Neves, C., Ros´ario, P.: A general estimator for the right endpoint with an application to supercentenarian women’s records. Extremes 20, 199–237 (2017).

Gomes, M.I., Oliveira, O.: The bootstrap Methodology in Statistics of Extremes - Choice of the Optimal Sample Fraction. Extremes 4(4), 331–358 (2001).

Gao, S., Shi, L., Zhang, Z.: A peak-over-threshold search method for global optimization. Automatica 89, 83–91 (2018).

Holesovsk´y, J., Fusek, M., Blachut, V., Michalek, J.: Comparison of precipitation extremes estimation using parametric and nonparametric methods. Hydrological Sciences Journal 61(3), 2376–2386 (2016).

Northrop, P.J., Coleman, C.L.: Improved threshold diaostic plots for extreme value analyses. Extremes 17, 289–303 (2014).

Roupec, J., Popela, P., Hrabec, D., Novotny, J., Olstad, A., Haugen, K.: Hybrid algorithm for network design problem with uncertainty demands. Lecture Notes in Engineering and Computer Science 1, 554–559 (2013).

Scarrott, C., MacDonald, A.A.: A review of extreme value threshold estimation and uncertainty quantification. REVSTAT 10(1), 33–60 (2012).

S¨uveges, M., Davison, A.C.: Model misspecification in peaks over threshold analysis. Annals of Applied Statistics 4(1), 203–221 (2010).

Talbi, E.-G.: Metaheuristics: From Design to Implementation. Wiley, Hoboken (2009).

Zhou, C.: Existence and consistency of the maximum likelihood estimator for the extreme value index. Journal of Multivariate Analysis 100, 794–815 (2009).