# A Modification of the PBIL Algorithm Inspired by the CMA-ES Algorithm in Discrete Knapsack Problem
## 2 PBIL Algorithm  
In algorithms from the family of EDAs, each population is represented by a probability distribution. In the case of PBIL [3], this is a vector consisting of the probabilities of obtaining a value of one at each position in the chromosome (1). \[\mathbf{p}^{t}=[p_{1}^{t},p_{2}^{t},\ldots,p_{n}^{t}] \tag{1}\]  
In each iteration, a population of M individuals was generated based on the probability distribution using the _sample_. The solutions were, then, evaluated according to the adopted objective function, and the N best solutions were selected (_select_). Based on the obtained \(O^{t}\) subset, a vector of probabilities was updated in the _update_ function. The algorithm ran in a loop until the assumed stopping condition was not met. The code is presented in Algorithm 1. ```
1:\(initialize(\mathbf{p}^{0})\)
2:\(t\gets 0\)
3:while\(\mathit{lstop}\)do
4:\(P^{t}\leftarrow\mathit{sample}(\mathbf{p}^{t},M)\)
5:\(O^{t}\leftarrow\mathit{select}(P^{t},N)\)
6:\(\mathbf{p}^{t+1}\leftarrow update(O^{t},\mathbf{p}^{t},a)\)
7:\(\mathit{mutate}(\mathbf{p}^{t+1})\)
8:\(t\gets t+1\)
9:endwhile
```  
**Algorithm 1** PBIL  
The method of updating the probability vector was described in Formula (2), where \(a\) is a learning rate and \(\mathbf{x}\) is a binary vector representing a single solution to the problem. In each iteration of the algorithm, the vector is modified according to the frequency of ones on each gene in the set of \(N\) best solutions. \[\mathbf{p}^{t+1}=(1-a)\cdot\mathbf{p}^{t}+a\cdot\frac{1}{N}\sum_{\mathbf{x} \in O^{t}}\mathbf{x} \tag{2}\]  
The stop condition could be customized for the problem under study. Typically, a maximum number of iterations (\(max_{iter}\)) is specified. Additionally, the algorithm is assumed to stop when the probability vector stabilizes, i.e., if all vector elements are in a fixed neighbourhood of zero or unity (\(\epsilon\)). _Proposed Modifications_  
The algorithm introduced in [3] assumes the independence of the individual genes in the chromosome. Inspired by the CMA-ES algorithm described in [8], a Covariance Matrix Adaptation Population-Based Incremental Learning (CMA-PBIL) algorithm that attempts to account for correlations between variables was proposed. In the CMA-PBIL algorithm, the probability distribution of population was described by two parameters: the covariance matrix (\(\mathbf{C}^{t}\)) and the probability vector (\(\mathbf{p}^{t}\)). The CMA-PBIL pseudocode is presented in Algorithm 2. The steps of the modified algorithm correspond to its original version. The changes only relate to how the points are generated and how the probability distribution parameters are updated. ```
1:\(initialize(\mathbf{p}^{0},\mathbf{C}^{0})\)
2:\(t\gets 0\)
3:while\(\mathit{lstop}\)do
4:\(P^{t}\gets sample(\mathbf{p}^{t},\mathbf{C}^{t},M)\)
5:\(O^{t}\leftarrow select(P^{t},N)\)
6:\((\mathbf{p}^{t+1},\mathbf{C}^{t+1})\gets update(O^{t},\mathbf{p}^{t}, \mathbf{C}^{t},a)\)
7:\(t\gets t+1\)
8:endwhile
```  
**Algorithm 2** CMA-PBIL  
The procedure for updating the covariance matrix is outlined in Formula (3). It employs the same learning factor \(a\) as during the modification of the vector \(\mathbf{p}^{t}\). The coefficient \(a\) was squared as the variance was the second central moment. \[\mathbf{C}^{t+1}=(1-a^{2})\cdot\mathbf{C}^{t}+a^{2}\cdot\mathbf{C}^{t} \tag{3}\]  
The matrix \(\mathbf{C}^{t}\) was computed at each iteration according to Formula (4), where the vector \(\mathbf{s}^{t}\) consists of the frequencies of ones on each bit in the set \(O^{t}\). \[\mathbf{C}^{t}(i,j)=\frac{1}{N}\sum_{\mathbf{x}\in O^{t}}(x_{i}-s_{i}^{t})(x_{ j}-s_{j}^{t}) \tag{4}\]  
The method of updating the vector \(\mathbf{p}^{t}\) did not change. **3. Experiments**  
As a test case, multiple variants of knapsacks problems were chosen. The task aimed to select from a set of \(n\) items a subset that maximizes the overall value of the knapsack within the capacity limit (\(Capacity\)). Each item \(i\) was described by two parameters--weight (\(weight_{i}\)) and value (\(value_{i}\)).