Methods of Solving the Problem of Construction the Optimum Regression Model as a Discrete Optimization Task. Ivan Melnyk

Abstract. The problem of constructing the optimum regression model consist in selection, based on a proper goal function, a sub-set of independent variables (regressors) to be included to the model. A functional of the model evaluation is proposed as a criterion for selection the optimum model. The task of constructing the optimum regression model is multiextremal and formulated as a task of discrete optimization on a special graph and represents search of the shortest path on the graph. The exact method of solving this task is proposed for searching the shortest path. There are considered two options for the functional of the model assessment. First option, when the functional depends on the model complexity (number of chosen regressors) and the residual of the built regression equation on the whole set of statistical data. Second option, when the functional is defined as a maximal value of the residual sum of squares of the regression model on a part of the set.

The special attention is paid to consideration of the calculation scheme of the heuristic genetic algorithm for the solution this very complex task. The suggested variant of the genetic algorithm belongs to so called "island models".

Keywords. Regression model, discrete optimization, functional of evaluation the model, function of adaptability, shortest path on the graph, genetic algorithm.

References.
1. Holland J. H.: Adaptation in Natural and Artificial Systems. - Ann Arbor: Michigan University Press, 1975.
2. Goldberg D. S.: Genetic algorithms in search, optimization, and machine learning. - Reading, MA: Addison-Wesley, 1989.
3. Melnyk I.M., Stepashko V.S.: On an approach to the optimum regression model selection using the discrete optimization method. - Proceedings of the International Workshop on Inductive Modelling. - Kyiv: IRTC ITS, 2005. - P. 223-229. (In Ukrainian)
4. Ivakhnenko A. G., Stepashko V.S.: Pomekhoustoichivost modelirovania (Noise-immunity of modeling). Kiev: Naukova Dumka, 216 p, 1985. (In Russian),  http://www.gmdh.net/articles/theory/bookNoiseIm.pdf
5. Yermoliev Yu.M., Melnyk I.M. Extremalnye zadachi na grafakh (Extreme tasks on the graphs). - Kiev: Naukova Dumka, 1967. - 159 p. (In Russian)
6. Melnyk I.M. Genetic algorithm for solving the task of an optimum regression model construction as a discrete optimization problem. - Problems of Control and Informatics. - 2008. - no.3. - p.30-43. (In Russian)
7. Whitley W.D., Rana S.B., and Heckendorn R.B. Island model genetic algorithms and linearly separable problems. - Selected Papers from AISB Workshop on Evolutionary Computing. - London: Springer-Verlag, 1997. - p.109-125.