Changing the cuckoo optimization algorithm for use in dynamic environments

Dissertation for Master's Degree

Computer Engineering, Artificial Intelligence.

Abstract

Dynamic environments are environments that have the ability to change over time. These changes can happen in different ways, including changes in parameters, objective functions or constraints of the problem. In this regard, a wide field of different sciences, such as management, economics, computer, mathematics, etc., have faced these changes, which are presented both in theory and practically in the real world. For this reason, solving problems related to dynamic environments, which are known as solving dynamic optimization problems, have been discussed since the past few decades until today. The most important challenge in solving such problems is related to how to adapt to the new changed environment. Therefore, the need to track and follow a new optimal point (points) in the problem space is felt. To deal with this challenge, researchers decided to use evolutionary algorithms that are inspired by evolutionary processes and add a series of special mechanisms. Another challenge that these problems face is to find the optimum(s) as accurately as possible, for which algorithms with high convergence speed and high local search ability should be used as much as possible. The cuckoo optimization algorithm is one of the evolutionary algorithms that has shown high convergence speed and local search ability in static environments. On the other hand, the dynamics of this algorithm has not been investigated yet. Therefore, the aim of this research is to develop and present a new version of this algorithm. To realize this issue, first, changes were made in the main structure of the standard algorithm and by using a self-adjustment mechanism in the radius of cuckoo eggs, efforts were made to increase the speed of convergence and local search ability. Then, in order to track the optimal(s) after the environmental changes, a multi-hand algorithm, free batch creation mechanism and monopoly mechanism are used. Also, in order to face the challenges related to the loss of diversity and invalid memory in the converged groups, the cuckoos of each group are distributed and evaluated in a radius (which is determined based on the length of the moving step of the peaks) around the best cuckoo of that group. In non-convergent categories, only the merit of the position of the cuckoos in that category is recalculated. The deactivation mechanism is one of the other mechanisms proposed to increase the efficiency of the algorithm in dynamic environments. Finally, based on the obtained results, the proposed algorithm has shown better performance compared to most algorithms. Keywords: dynamic optimization problems, evolutionary algorithms and cuckoo optimization algorithm. Chapter 1: Introduction. Accordingly, this process can cover a wide range of scientific fields in different branches such as mathematics, statistics, computer science, management science, etc. and even everyday issues. Therefore, dealing with optimization issues is of particular importance and is considered as one of the main research procedures for researchers.

In the issues raised in the field of optimization, there are different classifications depending on the application field. One of these classifications is determined based on the changeability or non-changeability of the surrounding environment. In this way, if the environment shows no changes in itself, the related problems are raised under the title of static optimization problems, and in case of environmental changes, it faces dynamic optimization problems. In the first type of problems, the main goal is to find or estimate the optimal point (points) as best as possible. This is despite the fact that in second-type problems, not only the main goal must be satisfied in a static state, but also the optimal point (points) must be followed as quickly as possible. This comes from the fact that in dynamic environments, due to environmental variability, it is possible to change the optimal point (points) to another area of ??the search space. Therefore, such problems face more challenges than the static state. Therefore, researchers decided to use algorithms that can adapt to changing environmental conditions. In this way, their attention was directed towards evolutionary algorithms.Because these algorithms are inspired by natural evolution and natural evolution is also a continuous process of adapting to the environment.

In the researches carried out so far, three main methods have been used in evolutionary algorithms to solve dynamic optimization problems: (1) creating diversity, (2) using memory and (3) multi-population approach. Due to the possibility of making changes in a space where no member is present or the possibility of convergence of members in that area, the approach of creating diversity is used. In order to achieve this, in algorithms such as the genetic algorithm, random immigrants and sometimes a self-adjustment mechanism have been used in the movement rate of immigrants entering the population. In the algorithms of ant colony and artificial bee colony, cellular automaton and in one example artificial safety algorithm based on learning automaton have been used. Also, the researchers tried to adapt the genetic algorithm to environments that are exposed to small changes by using memory and using the best members of the population. In other examples of algorithms such as particle aggregate optimization algorithm[1], artificial fish group algorithm[2] and firefly algorithm[3], a multi-population approach is used, in which several populations in the search space are used to create a balance between exploration[4] and extraction[5] of the optimal point(s) and tracking them as best as possible.

In this thesis, one of the newest evolutionary algorithms, the cuckoo optimization algorithm[6], is used to solve problems. Dynamic optimization is provided. As its name suggests, this algorithm is inspired by the way of life of birds known as cuckoos. The problem here is that the cuckoo algorithm has been used to solve static optimization problems and has reported good results. However, in order to use this algorithm in solving dynamic optimization problems, a series of mechanisms are added for optimal tracking during changes and establishing a kind of balance in exploration and extraction operations. Next, in the second chapter, the general description of the problem, assumptions and optimization goals in dynamic environments are discussed, and in the third chapter, for a better understanding of the issue, the concepts of foundations and tools used to solve the relevant problems are presented. In the fourth chapter, examples of past solutions in the field of dynamic optimization problems are studied, and in the fifth chapter, the proposed solution of this research, evaluation results and tests are given. Finally, in the sixth chapter, general conclusions and future solutions will be presented.

Chapter Two: Problem Description

In this chapter, the recognition of dynamic environments and, accordingly, dynamic optimization problems as the main problem of this research, the changes applied in the problem space that is used as a default in this thesis, and the desired goal to solve such problems will be discussed.

2-1 Dynamic environments and dynamic optimization problems

Dynamic environments, which are known as dynamic problems [7] or time-dependent problems [8], are environments that can witness continuous or discrete changes in themselves over time. These changes can happen in a wide area. Among them, the number, dimensions, range of environmental parameters or other characteristics can be changed. Another thing that may happen is changing the value of parameters according to time. Finally, in all the changes made, the environment faces a change in the global and local optimal point or points. The issues that are defined in this area give objectivity to these environments both in the laboratory and in the real world. Among them are dynamic optimization problems [9] in which the value of the fitness function changes regularly. More precisely, in the mathematical definition, we will have such problems [1]:

(2-1)

where the search space, time, the merit function that assigns numerical values ??to each possible solution ( ) in time and the sum of feasible solutions in time.

2-2 continuous and discontinuous changes

in terms of changes created at a point (points) optimality of the objective function, the environment can witness two types of continuous or discontinuous changes [2]. If the objective function is considered static, then we have changes by applying: where the displacement vector controls the optimal movement path [10]. Therefore, if the function is optimal, then it will be optimal in time.