Metaheuristic Computation with MATLAB®

Erik Cuevas, Alma Rodriguez

• Publisher: Chapman and Hall/CRC
• Year: 2020
• ISBN:
  9781000096538
• Edition: 1
• Topic: Informatique
• Subtopic: Ingénierie de l'informatique

Metaheuristic algorithms are considered as generic optimization tools that can solve very complex problems characterized by having very large search spaces. Metaheuristic methods reduce the effective size of the search space through the use of effective search strategies.

Book Features:

• Provides a unified view of the most popular metaheuristic methods currently in use

• 
  
  

• Includes the necessary concepts to enable readers to implement and modify already known metaheuristic methods to solve problems

• 
  
  

• Covers design aspects and implementation in MATLAB ®

• 
  
  

• Contains numerous examples of problems and solutions that demonstrate the power of these methods of optimization

• 
  
  

The material has been written from a teaching perspective and, for this reason, this book is primarily intended for undergraduate and postgraduate students of artificial intelligence, metaheuristic methods, and/or evolutionary computation. The objective is to bridge the gap between metaheuristic techniques and complex optimization problems that profit from the convenient properties of metaheuristic approaches. Therefore, engineer practitioners who are not familiar with metaheuristic computation will appreciate that the techniques discussed are beyond simple theoretical tools, since they have been adapted to solve significant problems that commonly arise in such areas.

CHAPTER 1

Introduction and Main Concepts

OBJECTIVE

The objective of this chapter is to introduce the main concepts that involve an optimization process. In this way, once the optimization problem is generically formulated, the methods used for its solution are then classified. Considering that the book focuses on the study of metaheuristic techniques, traditional gradient-based algorithms will be only marginally treated. Another important objective of this chapter is to explain the main characteristics of evolutionary algorithms, introducing the dilemma of exploration and exploitation. Furthermore, acceptance and probabilistic selection are also analyzed. These are the two main operations used in most metaheuristic methods. Finally, three of the first evolutionary methods which have been considered as the basis for the creation of new algorithms have been exposed. The idea with this treatment is to introduce the concepts of metaheuristic methods, through implementing techniques that are easy to understand.

1.1 Introduction

Optimization has become an essential part of all disciplines. One reason for this consideration is the motivation to produce products or quality services at competitive prices. In general, optimization is the process of finding the “best solution” to a problem among a big set of possible solutions (Baldick, 2006).

An optimization problem can be formulated as a process in which it is desired to find the optimum value $x\ast$ that minimizes or maximizes an objective function $f(x)$. Such that

$$\begin{array}{cc}\text{Minimize/Maximize}& f\text{(}\mathbf{\text{x}}\text{)},\mathbf{\text{x}}=(x_1,\dots ,x_d)\in {ℝ}^d\\ \text{Subject}\text{to:}& \mathbf{\text{x}}\in \mathbf{\text{X}},\end{array}(1.1)$$

where x represents the vector of decision variables, while d specifies its dimension. X symbolizes the set of candidate solutions, also known as the solution search space. In many occasions, the bounds of the search space are located by the lower $\left(l_i\right)$ or upper $\left(u_i\right)$ limits of each decision variables such that $\mathbf{\text{X}}=\left\{\mathbf{\text{x}}\in {ℝ}^d|l_i\le x_i\le u_i,i=1,\dots ,d\right\}$.

Sometimes it is necessary to minimize $f(\mathbf{\text{x}})$, but in other scenarios it is necessary to maximize. These two types of problems are easily converted from one to another through the following relationship:

$$\begin{array}{l}\underset{\mathbf{\text{x}}\ast }{\min }f(\mathbf{\text{x}})\iff \underset{\mathbf{\text{x}}\ast }{\max }[-1\cdot f(\mathbf{\text{x}})]\\ \underset{\mathbf{\text{x}}\ast }{\max }f(\mathbf{\text{x}})\iff \underset{\mathbf{\text{x}}\ast }{\min }[-1\cdot f(\mathbf{\text{x}})]\end{array}(1.2)$$

To clarify these concepts, the following minimization problem is presented as an example:

$$\begin{array}{cc}\text{Minimize}& f(x)=x^4+5x^3+4x^2-4x+1\\ \text{Subject}\text{to:}& x\in [-4,1]\end{array}(1.3)$$

In this formulation, the minimization of a function with a single decision variable (d = 1) is presented. The search space X for this problem is integrated by the interval from −4 to 1. Under these circumstances, the idea is to find the value of x for ...