YPEA: Yarpiz Evolutionary Algorithms

YPEA is a general-purpose MATLAB toolbox for defining and solving optimization problems with Evolutionary Algorithms (EAs) and metaheuristics. Define a problem once, then pass it to different algorithms through the same interface. The source code is on GitHub (opens in a new tab).

Available algorithms

YPEA currently supports these algorithms, listed in alphabetical order. Each name links to the Yarpiz post with a standalone MATLAB implementation of that algorithm.

1. Artificial Bee Colony (ABC)
2. Ant Colony Optimization for Continuous Domains (ACOR)
3. Bees Algorithm (BA)
4. Biogeography-based Optimization (BBO)
5. Covariance Matrix Adaptation Evolution Strategy (CMA-ES)
6. Cultural Algorithm (CA)
7. Differential Evolution (DE)
8. Firefly Algorithm (FA)
9. Genetic Algorithm (GA)
10. Harmony Search (HS)
11. Imperialist Competitive Algorithm (ICA)
12. Invasive Weed Optimization (IWO)
13. Particle Swarm Optimization (PSO)
14. Simulated Annealing (SA)
15. Teaching-Learning-based Optimization (TLBO)

Installation

A MATLAB toolbox package file (*.mltbx) is in the dist folder. Right-click this file inside MATLAB and select Install. This is the recommended way to install YPEA.

Alternatively, the source code is in the src folder. Download it and add the ypea folder to your MATLAB path.

The toolbox has its own documentation, which you can find under Supplemental Software in the MATLAB documentation center. To open it from the command line, type doc ypea.

How YPEA works

To set up and solve a problem with YPEA, follow these steps.

1. Define the optimization problem
   • Create an instance of the optimization problem.
   • Set the problem type (minimization or maximization).
   • Define the search space and decision variables.
   • Define the objective function.
     • Note: for a constrained problem, define the constraints and include them in the final objective function with a method such as penalty functions.
2. Use an optimization algorithm
   • Create an instance of the algorithm class.
   • Set the parameters of the algorithm.
   • Call the solve method of the algorithm and pass the problem object to it.
   • Get the results and visualize them if needed.

A worked example

Problem definition

Suppose we want to find 20 real numbers in the range $[-10, 10]$ that minimize the well-known sphere function:

Its minimum value is 0, at the origin.

We define this problem with these commands in MATLAB:

problem = ypea_problem();

problem.type = 'min';

problem.vars = ypea_var('x', 'real', 'size', 20, 'lower_bound', -10, 'upper_bound', 10);

sphere = ypea_test_function('sphere');

problem.obj_func = @(sol) sphere(sol.x);

Particle Swarm Optimization (PSO)

Now we can use any algorithm in YPEA to solve this problem. Here we use Particle Swarm Optimization (PSO). Create an instance of PSO (ypea_pso) and set its parameters.

pso = ypea_pso();

pso.max_iter = 100;
pso.pop_size = 100;

pso.w = 0.5;
pso.wdamp = 1;
pso.c1 = 1;
pso.c2 = 2;

You can also use Constriction Coefficients for PSO:

phi1 = 2.05;
phi2 = 2.05;
pso.use_constriction_coeffs(phi1, phi2);

Next, call the solve method of PSO:

pso_best_sol = pso.solve(problem);

The best solution found by PSO is available here:

pso_best_sol.solution.x

Differential Evolution (DE)

You can pass the same problem to another algorithm. For example, to use Differential Evolution (DE), create an instance of DE (ypea_de) and set its parameters. Here we use DE/best/2/bin, which means:

• using the best solution ever found as the base vector,
• using two difference vectors for mutation (creating the mutant vector),
• and using binomial crossover (bin) to create the trial vector. Each element of the trial vector comes from the mutant vector with the crossover probability, and from the current solution otherwise. One randomly chosen element always comes from the mutant vector.

de = ypea_de('DE/best/2/bin');

de.max_iter = 1000;
de.pop_size = 20;

de.beta_min = 0.1;
de.beta_max = 0.9;
de.crossover_prob = 0.1;

Call the solve method of DE and pass the problem to it:

de_best_sol = de.solve(problem);

The best solution found by Differential Evolution is available here:

de_best_sol.solution.x

Results of a run

The solve method returns the best solution found. Its solution field holds the decoded decision variables (here solution.x), its position field holds the encoded values, and its obj_value field holds the objective value.

The algorithm object also keeps a record of the run. The properties best_obj_value_history and nfe_history hold the best objective value and the number of function evaluations at the end of each iteration, and run_time holds the total run time. The plot and semilogy methods of the algorithm draw the convergence curve, against the iteration or against the number of function evaluations.

Check the result

Use the Sphere example first: its known minimum is 0 at the origin. When comparing algorithms, keep the objective, bounds, and stopping budget consistent. Iteration counts alone are not comparable when algorithms evaluate different numbers of candidates per iteration, so inspect nfe_history alongside the best objective history. For a constrained model, validate the decoded solution against the original constraints as well as the penalized objective.

Types of decision variables

Dealing with different kinds of decision variables is one of the difficulties of modeling optimization problems. YPEA supports several variable types to make problem definition easier:

• Real variables model real-valued (continuous) variables of any size (scalar, vector, matrix, etc.), with any combination of lower and upper bounds.
  • Sample usage: most real-world mathematical programming and optimization problems.
• Integer variables model integer-valued (discrete) variables of any size (scalar, vector, matrix, etc.), with any combination of lower and upper bounds.
  • Sample usage: Generalized Knapsack Problem.
• Binary variables are a special case of integer variables, with the lower bound set to 0 and the upper bound set to 1.
  • Sample usage: Standard (Binary) Knapsack Problem.
• Permutation variables model permutations of items. One variable can hold more than one permutation (as rows of a matrix).
  • Sample usage: Traveling Salesman Problem (TSP), n-Queens Problem, and Quadratic Assignment Problem (QAP).
• Selection variables model fixed-length selections of items. One variable can hold more than one selection (as rows of a matrix).
  • Sample usage: Feature Selection.
• Partition/Allocation variables partition a list of items into disjoint subsets (also known as allocation and assignment). One variable can hold more than one partitioning (as rows of matrices).
  • Sample usage: Vehicle Routing Problem (VRP) and Hub Location Allocation.
• Fixed Sum variables model real-valued variables that must have a fixed target sum (over the whole matrix, over rows, or over columns).
  • Sample usage: Transportation Problem.

All of these variable types are encoded as real values in the range [0,1]. This common encoding lets the algorithms use the same problem definition. The suitability of an algorithm still depends on the objective, constraints, and evaluation budget.