Joao Paulo Papa edited Introduction.tex  over 8 years ago

Commit id: a224347342bc6d86114ff4daeff3b3fbf7987457

deletions | additions      

       

In this section, we briefly present the theoretical background regarding the meta-heuristic techniques employed in this paper, as well as some basis related to optimization-based problems.   Let ${\cal S}=\{\textbf{x}_1,\textbf{x}_2,\ldots,\textbf{x}_m\}$ be a search space, where each possible solution $\textbf{x}_i\in\Re^n$ is composed of $n$ decision variables, and $x_{ij}$ $x_{i,j}$  stands for the $j^{th}$ decision variable of agent $i$. Additionally, let $f:{\cal S}\rightarrow\Re$ be a function to be minimized/maximized\footnote{For the sake of simplicity, we adopted a minimization problem.}. Roughly speaking, the main idea of any optimization problem is to solve the following equation: \begin{equation}  \label{e.minimization} 

Harmony Search (HS) is a meta-heuristic algorithm inspired in the improvisation process of music players, since they often improvise the pitches of their instruments searching for a perfect state of harmony~\cite{2009}. The main idea is to use a similar process to the one adopted by musicians when creating new songs, where each possible solution is modeled as a harmony (agent), and each musician corresponds to one decision variable.  In the context of HS, our search space ${\cal S}$ is called "Harmony Memory", since it comprises all possible solutions encoded on each agent. Harmony Search algorithm generates at each iteration a new agent $\hat{\textbf{x}}$ $\textbf{x}_{m+1}$  based on memory considerations, pitch adjustments, and randomization (music improvisation). Further, the new agent is evaluated in order to be accepted in the harmony memory: if $\hat{\textbf{x}}$ $\textbf{x}_{m+1}$  is better than the worst harmony, the latter is then replaced by the new agent. Roughly speaking, HS algorithm basically rules the process of creating and evaluating new harmonies until some convergence criterion is met. The memory consideration step concerns with modeling the process of creating songs, in which the musician can use his/her memories of good musical notes to create a new song. This process is modeled by the Harmony Memory Considering Rate ($HMCR$) parameter, which is the probability of choosing one value from the historic values stored in the harmony memory, being $(1-HMCR)$ the probability of randomly choosing one feasible value, as follows:  \begin{eqnarray}  \label{eq:hcmr}  \hat{x}^j \hat{x}_{m+1,j}  & = & \left\{ \begin{array}{ll} x^j_A x_{A,j}  & \mbox{{ with probability HMCR}} \\ \Phi_j & \mbox{{ with probability (1-HMCR),}}  \end{array}\right.  \end{eqnarray}  where $A\sim {\cal U}(1,2,\ldots,m)$, and $\bm{\Phi}=\{\Phi_1,\Phi_2,\ldots,\Phi_m\}$ stands for the set of feasible values for each decision variable.  Further, every component $j$ of the new harmony vector $\hat{\textbf{x}}$ $\textbf{x}_{m+1}$  is examined to determine whether it should be pitch-adjusted or not, being such step controlled by the Pitch Adjusting Rate (PAR) variable, as follows: \section*{Acknowledgments}  The authors are grateful to FAPESP grants \#2013/20387-7 and \#2014/16250-9, as well as CNPq grants \#470571/2013-6 and \#306166/2014-3.