正弦余弦算法 | Baeldung中文网

1. Introduction

In this tutorial, we take a look at a very recent algorithm: the sine-cosine algorithm or SCA.

It is an optimization procedure that belongs to the family of population-based metaheuristic techniques. Within these, it belongs to the math-based algorithms.

2. Sine-Cosine Algorithm

The SCA algorithm was proposed by Seyedali Mirjalili in 2016. It is a population-based metaheuristic algorithm applied to optimization problems.

As is common to algorithms belonging to the same family, the optimization process consists of the movement of the individuals of the population within the search space, which represent approximations to the problem.

For this purpose, SCA uses trigonometric sine and cosine functions. At each step of the calculation, it updates the solutions according to the following equations:

$[X_{ij}^{(t+1)}=X_{ij}^{(t)}+r_{1}\sin(r_{2})\left|r_{3}P_{ij}^{(t)}-X_{ij}^{(t)}\right|]$

$[X_{ij}^{(t+1)}=X_{ij}^{(t)}+r_{1}\cos(r_{2})\left|r_{3}P_{ij}^{(t)}-X_{ij}^{(t)}\right|]$

Generally, the above equations are combined as follows:

$[X_{ij}^{(t+1)}=\left\{ \begin{array}{ll} X_{ij}^{(t)}+r_{1}\cos(r_{2})\left|r_{3}P_{ij}^{(t)}-X_{ij}^{(t)}\right|, & r_{4}\geq0.5\\ X_{ij}^{(t)}+r_{1}\sin(r_{2})\left|r_{3}P_{ij}^{(t)}-X_{ij}^{(t)}\right|, & r_{4}<0.5 \end{array}\right.]$

where $X_ {ij} ^ {(t)}$ represents the current individual at iteration , $P_ {ij} ^ {(t)}$ shows the best individual’s position at iteration , and $r_ {1}, r_ {2}, r_ {3}, r_ {4}$ are random parameters.

SCA uses the latter parameters to avoid entrapment in suboptimal solutions and to balance the exploration and exploitation processes:

$r_ {1}$ conditions the shift in updating a solution, towards the best solution () or outwards it (). $r_ {1}$ decreases linearly from a certain constant value to zero:

$[r_{1}=a-t\frac{a}{T_{\max}}]$

where is a constant, is the current iteration, and $T _ {\ max}$ represents the maximum iterations allowed. The above equation allows for the balance between exploration and exploitation.

$r_ {2}$ has values in the range $[0: 2 \pi]$ and determines how big the movement of a solution is towards or outwards of the destination.
$r_ {3}$ has values in the range and is used to assign a weight to the destination, reinforcing or inhibiting the impact of the destination point on the updating process of the other solutions.
$r_ {4}$ , with values in the range , is a switch between the sine and cosine functions.

3. SCA in Practice

SCA begins the optimization procedures with a set of initial random solutions. The best solution achieved becomes the destination point (target), which is used to update the other solutions. SCA refreshes the ranges of sine and cosine functions to maintain the exploitation of the search space as the iteration number increments. The SCA stops the optimization procedures when the iteration number reaches the maximum number of iterations.

The following figure illustrates the entire process:

SCA

3.1. An Example: Features Selection

Belazzoug et al. used SCA to select features for text categorization.

The goal of the problem is to find the optimal subset of features. Each solution consists of a fixed size vector where each dimension encodes a value for each feature in the range [0: 1] . A feature with a value greater than or equal to 0.5 implies its selection.

The evaluation of each solution (features subset) takes into account both the accuracy of the classification and the size of the selected subset. This is an example of multi-objective optimization, where the objectives are the minimization of the classification error and the subset size:

$[f=\alpha E+(1-\alpha)\frac{n_{i}}{n_{T}}]$

where:

$\alpha \in [0: 1]$ represents the relative importance of the error rate with respect to the number of features;
is the error in the classification;
$n_ {i}$ is the number of features of the current solution for dimension ;
$n_ {T}$ is the total number of features.

This objective function allows the evaluation of each individual in the general procedure we have given in the figure above.

Of course, we have to calculate a value for the classification error. In the context of Belazzoug’s work, this value is obtained through the Information Gain (Mutual Information), which measures the number of bits of information obtained for category prediction by knowing the presence or the absence of a term in a document.

3.2. A Numerical Calculation

In this section, we’ll make a numerical example of optimization with SCA. Let’s try to find the minimum of a real two-variable function, the Six-Hump Camel Function, often used as a test:

$[f(x_{1},x_{2})=\left(\frac{x_{1}^{4}}{3}-2.1x_{1}^{2}+4\right)x_{1}^{2}+\left(4x_{2}^{2}-4\right)x_{2}^{2}+x_{1}x_{2}]$

$[\left\{ x_{1},x_{2}\right\} \in[-5:5]]$

Six Hump Camel function

The function has a minimum for:

$[f(x_{1},x_{2})=-1.0316\left\{ \begin{array}{ll} x_{1}=0.0898, & x_{2}=-0.7126\\ x_{1}=-0.0898, & x_{2}=0.712 \end{array}\right.]$

Using Dr. Pereira’s code, the optimization process, starting from a random population, is as follows:

Iteration

x_1

x_2

f(x_1,x_2)

0.14352534

-0.54935549

-0.84019004

100

-0.08822356

0.70538939

-1.0312019

200

-0.08822356

0.70538939

-1.0312019

300

-0.0996268

0.71069016

-1.0312051

400

-0.09105287

0.7089342

-1.03150536

500

-0.09105287

0.7089342

-1.03150536

600

-0.08818936

0.71163966

-1.03161103

700

-0.08818936

0.71163966

-1.03161103

800

-0.08818936

0.71163966

-1.03161103

900

-0.09038102

0.71235722

-1.03162643

1000

-0.09038102

0.71235722

-1.03162643

4. Exploration vs. Exploitation

As happens to all optimization algorithms in general, and to metaheuristic algorithms in particular, the goodness of the SCA solutions depends on an optimal balance between exploration and exploitation. To explain how this balancing, we will start from the following figure, which represents two functions dependent on sine and cosine in the interval $[0: 2 \pi]$ for the independent variable, with values of the functions within the range [-2: 2] :

sincos

The variable represents the set of independent variables that define the search space.

As we can see, the range of variability in the domain is much greater for the values of the functions located in the upper and lower part of the curves, compared to the central section. This fact allows us to state the following heuristic rule:

For values of the sine and cosine functions in the intervals, and we have a predominance of the exploratory process since the SCA tests many different points in the problem space.
For values of the sine and cosine functions in the range , there is a predominance of the exploiting phase.

5. Why Does SCA Work?

The reasons for the efficiency of the SCA algorithm are different, some common to other metaheuristic techniques:

SCA works with a population of solutions, which benefit from parallel exploration phenomena
It investigates several regions of the solution space simultaneously for values of the sine and cosine functions outside the range
During the exploiting process, with sine and cosine values in the range , SCA investigates several promising solutions simultaneously
The adaptive values of the parameters allow transferring the promising strategies and regions between the exploratory and exploitative processes
The best solution at a certain point in the calculation is saved in a variable and becomes the target of the problem, and therefore is never lost during the optimization phase
The optimization process is convergent

6. Conclusion

In this tutorial, we have briefly analyzed the sine-cosine algorithm. This is an optimization procedure that has original characteristics with respect to other conventional algorithms belonging to the family of metaheuristic techniques.

We have left out many interesting features, including the variants of the algorithm that arose from the original proposal by Seyedali Mirjalili. The analysis of these variants is outside the scope of this tutorial, but we invite the reader to explore them.

Persistence

REST

Security

1. Introduction

2. Sine-Cosine Algorithm

3. SCA in Practice

3.1. An Example: Features Selection

3.2. A Numerical Calculation

4. Exploration vs. Exploitation

5. Why Does SCA Work?

6. Conclusion