Convergence of the evolutionary algorithms for optimal solution with binary choice relations

Authors

  • V. F. Irodov Dr. Sc. (Tech.), Prof., Ukraine
  • Yu. V. Khatskevych Cand. Sc. (Tech.), Ass. Prof., Ukraine

Keywords:

evolutionary algorithms, binary choice relation, conditions of convergence, R - optimal solution

Abstract

Abstract. Purpose. To solve problems of mathematical programming, we previously developed one approach to construct algorithms for evolutionary random search. These algorithms in subsequent works were extended to solving generalized mathematical programming problems in which binary relations of choice are used. The convergence of evolutionary algorithms to optimal solutions when using objective functions from the Euclidean space is proved analytically in our papers. The convergence of the search for optimal solutions in the solution of problems of generalized mathematical programming is confirmed by numerous experiments on different problems. Conditions for the convergence of evolutionary algorithms for generalized mathematical programming problems are presented earlier. In this paper we prove the convergence of evolutionary algorithms for finding optimal solutions with binary choice relations. Methodology. The solution of optimization problems with the binary relation of nonstrict choice was analyzed. To investigate the convergence of evolutionary search, algorithms were studied whose main functions are the function of generating solutions and the function of the choice of solutions. As a selection function, the preference function is a binary choice relation. Findings. The article formulated conditions that ensure convergence of algorithms of evolutionary search. Among them: the condition of non-strict choice for a binary choice relation, the condition for the existence of upper-section binary relations of the choice of a non-zero measure, the condition of non-zero probability of new solutions falling into an arbitrary upper section of the choice relation. Originality. Sufficient conditions are formulated that ensure the convergence of the sequences of selected solutions to the RS - optimal solution with probability 1 under general conditions for the ratio of choice. The formulated conditions leave significant opportunities for constructing specific evolutionary random search algorithms. Practical value. The conditions of convergence of evolutionary algorithms allow us to construct effective algorithms for solving generalized mathematical programming problems: with continuous, discrete or mixed variables, in the presence of constraints in the form of equalities or inequalities.

Author Biographies

V. F. Irodov, Dr. Sc. (Tech.), Prof.

Department of System Analysis and Modeling in Heat and Gas Supply, State Higher Education Establishment “Pridneprovsk State Academy of Civil Engineering and Architecture”, Chernishevskogo str., 24-A, Dnipro 49600, Ukraine, phon. +38 (056) 756-34-06

Yu. V. Khatskevych, Cand. Sc. (Tech.), Ass. Prof.

Department of Power Supply System, State Higher Educational Establishment “National Mining University”, D. Yavornytskogo prospect, 19, Dnipro, Ukraine, phon. +380952251010

References

Bukatova I.L. Evolyutsionnoye modelirovaniye i ego prilozheniya [Evolutionary modeling and its applications]. Moskva, Nauka Publ., 1979, 232 p. (in Russian).

Ivakhnenko A.G., Zaychenko Yu.P. and Dimitrov V.D. Prinyatiye resheniy na osnove samoorganizatsii [Decision-making based on self-organization]. Moskva, Sovetskoye radio Publ., 1976. 280 p. (in Russian).

Ivakhnenko A.G. Sistemy evristicheskoy samoorganizatsii v tekhnicheskoy kibernetike [Systems of heuristic selforganization in technical cybernetics]. Kyiv, Tekhnika Publ., 1971. 392 p. (in Russian).

Rastrigin L.A. Statisticheskiye metody poiska [Statistical methods of search]. Moskva, Nauka Publ., 1968, 376 p. (in Russian).

Stratan F.I. and Irodov V.F Evoliutsionnye algoritmy poiska optimalnykh resheniy [Evolutionary algorithms search for optimal solutions]. Metody optimizatsii pri proektirovanii sistem teplogazosnabzheniya – Methods of optimizing for design of heating systems, 1984, pp. 16–30. (in Russian).

Fogel L. and Uolsh A. Iskusstvennyy intellekt i evolyutsionnoye modelirovaniye [Artificial intelligence and evolutionary modeling]. Moskva, Mir Publ., 1969, 228 p. (in Russian).

Yudin D.B. Vychislitelnyye metody teorii prinyatiya resheniy [Computational methods of decision theory]. Moskva, Nauka Publ., 1989, 320 p. (in Russian).

Irodov V.F. and Maksimenkov V.P. Application of an evolutionary program for solving the traveling-salesman problem. Sov. Autom. Control, 1981, pp. 7–10. (in English).

Irodov V.F. On the construction and convergence of evolutionary algorithms of random search. Soviet J. Automat. Informat. Sci, 1987, pp. 34–43. (in English).

Irodov V.F. Self-organization methods for analysis of nonlinear systems with binary choice relations. Soviet J. Journal Systems Analysis Modeling Simulation. Newark, NJ, USA, 1995, issue 18-19, pp. 203–206. (in English).

Published

2017-04-27

Issue

Section

Energy, ecology, computer technology in construction