# A Modification of the PBIL Algorithm Inspired by the CMA-ES Algorithm in Discrete Knapsack Problem
## 1 Introduction  
Evolutionary algorithms (EAs) are a valuable tool for solving many multidimensional and NP-hard [1] practical problems, mainly because they outperform traditional methods, whose high space complexity often disqualifies them from being used to solve complex problems. EAs are a large and diverse family of algorithms that find solutions to problems in continuous and discrete domains. Among the prominent classes of EAs, the Estimation of Distribution Algorithms (EDAs) [2] can be listed, in which the probabilistic model mechanism realizes the evolution mechanism.  
One of the more straightforward and well-known EDAs initially used to solve discrete problems is the Population-Based Incremental Learning (PBIL) algorithm, first proposed by [PERSON] in [3]. This algorithm owes its simplicity to the fact that the probability distribution of the subsequent bits in the chromosome is independent, so both the point generation and the learning process can be performed separately for each variable. For these reasons, PBIL is popular and various modifications of the algorithm have been developed, introducing, among others, the probability vector multiplication [4, 5], elite strategy [6] and non-parametric approach [7].  
A different approach than EDAs in the EAs family is evolutionary strategies (ES). Their leading representative is the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) algorithm proposed in [8]. Initially, CMA-ES was invented to find solutions to continuous domain problems, but later, modifications dedicated to discrete problems were developed [9]. Whereas CMA-ES, such as EDAs, uses a probability distribution to describe the population--a multivariate normal distribution--, they differ in other aspects. The key among them is how the parameters are updated--in EDAs, learning considers a set ofpoints, while CMA-ES considers a set of steps [10]. CMA-ES outperforms the EDA family of algorithms in many problems [10].  
In this paper, we propose a modification of the PBIL algorithm, which, inspired by CMA-ES, introduces information about correlations between variables into the probability distribution model. In some actual applications, taking the correlations between decision variables into account can bring real benefits, e.g., a faster algorithm convergence. For instance, one can imagine a given problem with two global optima with significantly different realizations. By adding a covariance matrix, the algorithm can detect such a situation and distinguish between these solutions. Knapsack problems with a varying item parameter correlation [11] were chosen to compare the modified and standard PBIL algorithms. The selected test case is a well-known NP-hard optimization problem commonly applied to compare algorithms solving discrete tasks.  
The rest of the paper is organized as follows: In Section 2, we detail investigated PBILs, including our proposed modification. Next, in Section 3, we present the test environment consisting of knapsack problems. Then, in Section 4, results and a discussion are provided. Finally, Section 5 gives out a summary of the research findings.