Optimization method based on the synthesis of clonal selection and annealing simulation algorithms

Abstract

Context. The problem of increasing the efficiency of optimization methods by synthesizing metaheuristics is considered. The object of the research is the process of finding a solution to optimization problems. Objective. The goal of the work is to increase the efficiency of searching for a quasi-optimal solution at the expense of a metaheuristic method based on the synthesis of clonal selection and annealing simulation algorithms. Method. The proposed optimization method improves the clonal selection algorithm by dynamically changing based on the annealing simulation algorithm of the mutation step, the mutation probability, the number of potential solutions to be replaced. This reduces the risk of hitting the local optimum through extensive exploration of the search space at the initial iterations and guarantees convergence due to the focus of the search at the final iterations. The proposed optimization method makes it possible to find a conditional minimum through a dynamic penalty function, the value of which increases with increasing iteration number. The proposed optimization method admits non-binary potential solutions in the mutation operator by using the standard normal distribution instead of the uniform distribution. Results. The proposed optimization method was programmatically implemented using the CUDA parallel processing technology and studied for the problem of finding the conditional minimum of a function, the optimal separation problem of a discrete set, the traveling salesman problem, the backpack problem on their corresponding problem-oriented databases. The results obtained allowed to investigate the dependence of the parameter values on the probability of mutation. Conclusions. The conducted experiments have confirmed the performance of the proposed method and allow us to recommend it for use in practice in solving optimization problems. Prospects for further research are to create intelligent parallel and distributed computer systems for general and special purposes, which use the proposed method for problems of numerical and combinatorial optimization, machine learning and pattern recognition, forecast.

Актуальність. Розглянута задача підвищення ефективності методів оптимізації шляхом синтезу метаевристик. Об’єктом дослідження є процес пошуку рішення оптимізаційних задач. Метою роботи є підвищення ефективності пошуку квазіоптимального рішення за рахунок метаевристичного методу на основі синтезу алгоритмів клонального відбору та імітації відпалу. Метод. Запропонований метод оптимізації удосконалює алгоритм клонального відбору за рахунок динамічної зміни на основі алгоритму імітації відпалу кроку мутації, ймовірності мутації, кількості замінних потенційних рішень. Це зменшує ризик потрапляння в локальний оптимум завдяки широкому дослідженню простору пошуку на початкових ітераціях й гарантує збіжність через спрямованість пошуку на заключних ітераціях. Запропонований метод оптимізації дозволяє знаходити умовний мінімум за рахунок динамічної штрафної функції, значення якої зростає зі збільшенням номера ітерації. Запропонований метод оптимізації допускає небінарні потенційні рішення в операторі мутації завдяки використанню стандартного нормального розподілу замість рівномірного розподілу. Результати. Запропонований метод оптимізації був програмно реалізований за допомогою технології паралельної обробки інформації CUDA і досліджений для задачі знаходження умовного мінімуму функції, задачі оптимального розбиття дискретної множини, задачі комівояжера, задачі про рюкзак на відповідних їм проблемно-орієнтованих базах даних. Отримані результати дозволили досліджувати залежність значень параметрів на ймовірність мутації. Висновки. Проведені експерименти підтвердили працездатність запропонованого методу та дозволяють рекомендувати його для використання на практиці при вирішенні задач оптимізації. Перспективи подальших досліджень полягають у створенні інтелектуальних паралельних й розподілених комп’ютерних систем загального і спеціального призначення, які використовують запропонований метод для задач чисельної та комбінаторної оптимізації, машинного навчання й розпізнавання образів, прогнозу.