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).

Downloads

Published

2017-04-27

Issue

No. 98 (2017)

Section

Energy, ecology, computer technology in construction

License

Редакція  Видання категорично засуджує прояви плагіату в статтях та вживає всіх можливих заходів для його недопущення. Плагіат розглядається як форма порушення авторських прав і наукової етики.

При виявлені у статті більш ніж 25% запозиченого тексту без відповідних посилань та використання лапок, стаття кваліфікується як така, що містить плагіат. У цьому випадку стаття більше не розглядається редакцією, а  автор отримує перше попередження.

Автори, в статтях яких повторно виявлено плагіат, не зможуть публікуватися в усіх журналах Видавництва ДВНЗ «Придніпровська державна академія будівництва та архітектури».

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).