# Universal Approach to Solution of Optimization Problems by Symbolic Regression
## 5 Computational Experiments
### Case 2. Knapsack Problem  
Consider a classic NP-hard knapsack problem. We need to choose, among a number of objects, some set of objects that satisfy certain criteria. Vector of small variations consists of two elements: 1--index of element in the set of objects; 2--a new value.  
Suppose that the capacity of knapsack is \(C\). The set of objects with some weights is  
\[X=(x_{1},\ldots,x_{K}),\ \ x^{-}\leqslant x_{i}\leqslant x^{+},\ \ \ i=\overline{1,K}, \tag{82}\]  
where \(x^{-}\) and \(x^{+}\) are low and upper values of objects, \(K\) is a number of objects.  
Each possible solution is  
\[\mathbf{y}=[y_{1}\ldots y_{K}],\ \ \ y_{i}\in\{0,1\},\ \ \ i=\overline{1,K}. \tag{83}\]  
It is necessary to find a vector \(\mathbf{y}\) to minimize the following quality criterion  
\[F(\mathbf{y})=|C^{*}-\sum_{i=1}^{K}y_{i}x_{i}|\rightarrow\min, \tag{84}\]  
so that the weight of objects would be as close to the capacity of knapsack as possible.  
Consider the following example. We have a \(K=100\) objects that have real values (suppose weights, kg) from 0 to 10. The capacity of the knapsack is 100 kg. We need to choose the objects so that their total weight is close to the capacity. In general case there are different types of constraints,on weight, volume, costs, etc.  
To solve this problem, we applied VarGA. The parameters of algorithm are given in Table 1.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Value** \\ \hline Number of solutions in generation & 1024 \\ Number of generations & 128 \\ Number of crossovers & 128 \\ Depth of variation & 8 \\ Number of generations between epochs & 8 \\ Probability of mutation & 0.75 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Parameters of VarGA for the knapsack problem.  
Figure 5: Trajectories of mobile robot from eight initial states.  
The set of objects is  
\[\begin{array}{rcl}\mathbf{X}&=&\{x_{1}=1.198973,x_{2}=8.195864,x_{3}=0.149163,x_{ 4}=0.600499,\\ &x_{5}=1.868563,x_{6}=1.134450,x_{7}=2.940746,x_{8}=3.005569,\\ &x_{9}=0.235667,x_{10}=6.92442,x_{11}=9.862742,x_{12}=9.013933,\\ &x_{13}=1.685997,x_{14}=4.716708,x_{15}=1.805467,x_{16}=3.955157,\\ &x_{17}=3.605431,x_{18}=3.456106,x_{19}=4.063158,x_{20}=8.704509,\\ &x_{21}=1.290323,x_{22}=7.570359,x_{23}=0.605452,x_{24}=5.840240,\\ &x_{25}=7.466071,x_{26}=7.852390,x_{27}=0.020214,x_{28}=4.903944,\\ &x_{29}=7.782723,x_{30}=8.912633,x_{31}=8.311701,x_{32}=4.629041,\\ &x_{33}=9.999174,x_{34}=0.188699,x_{35}=2.837382,x_{36}=6.866526,\\ &x_{37}=3.853656,x_{38}=9.422472,x_{39}=7.059892,x_{40}=5.666469,\\ &x_{41}=7.686985,x_{42}=6.470105,x_{43}=3.892209,x_{44}=0.501044,\\ &x_{45}=3.471120,x_{46}=3.024267,x_{47}=1.730138,x_{48}=8.358248,\\ &x_{49}=0.700096,x_{50}=8.905066,x_{51}=6.966928,x_{52}=3.520369,\\ &x_{53}=3.283775,x_{54}=9.267853,x_{55}=0.620899,x_{56}=7.016356,\\ &x_{557}=9.203328,x_{58}=4.219690,x_{59}=1.891819,x_{60}=3.921507,\\ &x_{61}=4.049162,x_{62}=5.061787,x_{63}=9.480431,x_{54}=6.256851,\\ &x_{65}=0.661214,x_{66}=5.630264,x_{67}=9.411684,x_{68}=5.275044,\\ &x_{69}=4.325184,x_{70}=1.710065,x_{71}=2.823965,x_{72}=1.055504,\\ &x_{73}=8.029722,x_{74}=5.355668,x_{75}=1.084831,x_{76}=9.075759,\\ &x_{77}=6.102632,x_{78}=8.207962,x_{79}=1.945653,x_{80}=0.996382,\\ &x_{81}=7.408127,x_{82}=5.727311,x_{83}=2.674080,x_{84}=4.547363,\\ &x_{85}=7.281093,x_{86}=6.022923,x_{87}=3.066631,x_{88}=5.206564,\\ &x_{89}=2.919562,x_{90}=500339,x_{91}=0.182961,x_{92}=7.070480,\\ &x_{93}=9.648925,x_{94}=8.176261,x_{95}=6.963208,x_{96}=3.829286,\\ &x_{97}=3.794559,x_{98}=6.652624,x_{99}=4.438315,x_{100}=0.459797\}.\end{array} \tag{85}\]  
As a result, we obtained the following solution  
\[\begin{array}{rcl}y_{i}&=&1,\\ i&=&1,4,5,6,11,14,15,16,21,23,27,28,29,31,32,\\ &&43,44,46,47,48,51,59,65,69,78,90,91,92.\end{array} \tag{86}\]  
The objective function for this solution is \(F(\mathbf{y})=0.00125\),  
\[\sum_{i=1}^{100}y_{i}x_{i}=99.998749. \tag{87}\]