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

Abstract

EN: 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.

UK: Мета. Для рішення задач математичного програмування раніше нами був розроблений один підхід побудови алгоритмів еволюційного випадкового пошуку. Ці алгоритми у наступних працях були поширені на рішення задач узагальненого математичного програмування, у яких використовуються бінарні відношення вибору. Збіжність еволюційних алгоритмів к оптимальним рішенням при використанні цільових функцій у евклідовому просторі доказана аналітично у наших працях. Збіжність пошуку оптимальних рішень для задач узагальненого математичного програмування підтверджена значною кількістю експериментів на різних задачах. Умови збіжності еволюційних алгоритмів для задач узагальненого математичного програмування викладені раніше. У цій роботі наведені докази збіжності еволюційних алгоритмів для вирішення задач пошуку оптимальних рішень з бінарними відношеннями вибору. Методика. Розглядалось вирішення задачі оптимізації з бінарними відношеннями нестрогого вибору. Для дослідження збіжності еволюційного пошуку досліджувались алгоритми, які складаються з наступних функцій: функція генерації рішень та функція відбору рішень. У якості функції вибору – функція переваги по бінарному відношенню вибору. Результати. Сформульовані умови, які забезпечують збіжність алгоритмів еволюційного пошуку. Серед них: умова нестрогого вибору для бінарного відношення вибору, умова існування у перетинів бінарного відношення не нульової міри, умова не нульової вірогідності влучення нових рішень у довільний верхній перетин відношення вибору. Наукова новизна. Сформульовані та обґрунтовані умови, які забезпечують збіжність послідовностей відібраних рішень у процесі еволюційного пошуку до RS – оптимального рішення з вірогідністю 1 при достатньо загальних умовах для відношення вибору. Практична значимість. Умови збіжності еволюційних алгоритмів дозволяють будувати ефективні алгоритмі для вирішення задач узагальненого математичного програмування з безперервними, дискретними або змішаними змінними, при наявності обмежень у вигляді рівнянь або нерівностей.

RU: Цель. Для решения задач математического программирования ранее нами был разработан один подход построения алгоритмов эволюционного случайного поиска. Эти алгоритмы в последующих работах были распространены на решение задач обобщенного математического программирования, в которых используются бинарные отношения выбора. Сходимость эволюционных алгоритмов к оптимальным решениям при использовании целевых функций из пространства Эвклида доказана аналитически в наших работах. Сходимость поиска оптимальных решений при решении задач обобщенного математического программирования подтверждена многочисленными экспериментами на разных задачах. Условия сходимости эволюционных алгоритмов для задач обобщенного математического программирования изложены ранее. В данной работе приведено доказательство сходимости эволюционных алгоритмов для задач поиска оптимальных решений с бинарными отношениями выбора. Методика. Анализировалось решение задач оптимизации с бинарным отношением нестрогого выбора. Для исследования сходимости эволюционного поиска исследовались алгоритмы, основными функциями которых являются: функция генерации решений и функция выбора решений. В качестве функции выбора – функция предпочтения по бинарному отношению выбора. Результаты. В статье сформулированы условия, которые обеспечивают сходимость алгоритмов эволюционного поиска. Среди них: условие нестрогого выбора для бинарного отношения выбора, условие существования у верхних сечений бинарного отношения выбора не нулевой меры, условие не нулевой вероятности попадания новых решений в произвольное верхнее сечение отношения выбора. Научная новизна. Сформулированы достаточные условия, которые обеспечивают сходимость последовательностей отбираемых решений к RS – оптимальному решению с вероятностью 1 при общих условиях для отношения выбора. Сформулированные условия оставляют значительные возможности для построения конкретных эволюционных алгоритмов случайного поиска. Практическая значимость. Условия сходимости эволюционных алгоритмов позволяют строить эффективные алгоритмы для решения задач обобщенного математического программирования: с непрерывными, дискретными или смешанными переменными, при наличии ограничений в виде равенств или неравенств.