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

V. F. Irodov, Yu. V. Khatskevych

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.

Keywords


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

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


GOST Style Citations


1. Букатова И. Л. Эволюционное моделирование и его приложения / И. Л. Букатова.- М.: Наука, 1979.- 232 с.

2. Ивахненко А. Г. Принятие решений на основе самоорганизации / А. Г. Ивахненко, Ю. П. Зайченко, В. Д. Димитров. – М.: Сов. радио, 1976. – 280 с.

3. Ивахненко А. Г. Системы эвристической самоорганизации в технической кибернетике / А. Г. Ивахненко. – К.: Техника, 1971. – 392 с.

4. Растригин Л. А. Статистические методы поиска / Л. А. Растригин.- М.: Наука, 1968.- 376 с.

5. Стратан Ф. И. Эволюционные алгоритмы поиска оптимальных решений / Ф. И. Стратан, В. Ф. Иродов // Методы оптимизации при проектировании систем теплогазоснабжения. – Кишинев: Штиинца, 1984. – С. 16–30.

6. Фогель Л. Искусственный интеллект и эволюционное моделирование / Л. Фогель, А. Уолш.- М.: Мир, 1969.- 228 с.

7. Юдин Д. Б. Вычислительные методы теории принятия решений / Д. Б. Юдин.- М.: Наука, 1989.- 320 с.

8. Irodov V.F. Application of an evolutionary program for solving the traveling-salesman problem / V.F.Irodov, V.P. Maksimenkov // Sov. Autom. Control.- 1981.- 14, No 4.- рр. 7-10.

9.  Irodov V.F. On the construction and convergence of evolutionary algorithms of random search/ V.F.Irodov // Soviet J. Automat. Informat. Sci.- 1987.- 20, No4.- рр. 34-43.

10. Irodov V. Self-organization methods for analysis of nonlinear systems with binary choice relations / V. Irodov // Journal Systems Analysis Modeling Simulation. - Newark, NJ, USA Inc: Gordon and Breach Science Publishers, 1995.- Vol. 1819, 1995. – рр. 203 – 206.
 
Стаття рекомендована до публікації д-ром.техн.наук, проф. А. С. Беліковим (Україна);  д-ром.техн.наук, проф. С. З. Поліщуком (Україна)
 Стаття надійшла в редколегію 29.03.2017



Refbacks

  • There are currently no refbacks.