# A Modification of the PBIL Algorithm Inspired by the CMA-ES Algorithm in Discrete Knapsack Problem
## 2 PBIL Algorithm
The decision of whether the item was included or not in the knapsack was represented by variable \(x_{i}\in\{0,1\}\). The main task is defined in Equation (5), while the limit is defined in Formula (6). \[\operatorname*{arg\,max}_{\mathbf{x}}\sum_{i=1}^{n}x_{i}\cdot value_{i} \tag{5}\]  
\[\sum_{i=1}^{n}x_{i}\cdot weight_{i}\leqslant Capacity \tag{6}\]  
The fitness was evaluated using Formula (7), where \(P\) is the penalty coefficient. The objective function considered both the goals, which was to maximize the values of the items and the constraint. \[f(\mathbf{x})=\left\{ \begin{array}{l}\sum_{i=1}^{n}x_{i}\cdot value_{i}, \quad\text{ if }\quad\sum_{i=1}^{n}x_{i}\cdot weight_{i}\leqslant Capacity\\ \sum_{i=1}^{n}x_{i}\cdot value_{i}-P\cdot(\sum_{i=1}^{n}x_{i}\cdot value_{i}- Capacity),\quad\text{ otherwise}\end{array} \right. \tag{7}\]The problem was investigated on six different knapsack problems generated as proposed in [11; 12]. Problems with different correlation intensities (uncorrelated, moderately correlated, and strongly correlated) and with different capacities were examined. As reported in [11], the higher the correlation, the more challenging the knapsack problem was expected to become. The sets consisted of \(n=100\) items with a maximum weight \(v=10\) and maximum offset \(r=5\). The method by which the weights, values and capacities were generated sequentially for the following test cases is shown in Table 1. The \(\mathcal{U}_{[a,b]}\) represents the continuous uniform distribution within the range of \([a,b]\). The initialization method for vector \(\mathbf{p}\) and matrix \(\mathbf{C}\) was adapted to the test case. Typically, in the PBIL algorithm, the computation starts with a vector \(\mathbf{p}^{0}=[0.5\ldots 0.5]\). For the experiments performed, the elements of the vector \(\mathbf{p}^{0}\) contained values calculated using Formula (8). \[p^{0}=\frac{Capacity}{\sum_{i=1}^{n}weight_{i}} \tag{8}\]  
The initial probability distribution was assumed to be uncorrelated. Therefore, matrix \(\mathbf{C}^{0}\) was a diagonal matrix with the variances computed according to Formula (9) located on the diagonal. \[Var^{0}=p^{0}\cdot(1-p^{0}) \tag{9}\]  
Test Environment  
Since CMA-PBIL requires the generation of binary vectors with a given correlation, it was important to select an algorithm that provided this. There are several types of algorithms for this [13; 14; 15]. One of them was proposed by [PERSON] and is a modification of the Emrich and Piedemont algorithm. An implementation of the algorithm from the MultiOrd package [16] in R was adopted in the experiments. The algorithm uses a correlation matrix instead of a covariance matrix, on which a constraint (10) is imposed, where \(\psi_{i}^{t}\) is described by Formula (11). \[max(-\psi_{i}^{t}\psi_{j}^{t},\frac{-1}{\psi_{i}^{t}\psi_{j}^{t}})\leqslant Cor ^{t}(i,j)\leqslant min(\frac{\psi_{i}^{t}}{\psi_{j}^{t}},\frac{\psi_{j}^{t}}{ \psi_{i}^{t}}) \tag{10}\]  
\[\psi_{i}^{t}=\sqrt{\frac{p^{t}(x_{i})}{(1-p^{t}(x_{i}))}} \tag{11}\]  
In the PBIL algorithm, three parameters could be specified: \(M\)--the number of solutions generated; \(N\)--the number of solutions taken into account when updating the distribution parameters; \(a\)--the learning rate. In addition, the penalty factor \(P\) was introduced for the knapsack problem. \(\epsilon\) and \(max_{iter}\) parameters determined the stop condition of the algorithms. The value of the factor prevented solutions exceeding the knapsack constraint from being selected. Parameter settings are listed in Table 2.