## 6 Experimental Results
### Improvement with the Greedy Steepest Descent Algorithm  
In this subsection, the improvement of the quality of the solutions that occurs with the additional step of the greedy steepest descent algorithm, is examined. In Table 4, the average distance (%) from the  
\begin{table}
\begin{tabular}{l c c c c} \hline
**Dataset** & \(\mathbf{pop}=\mathbf{256}\) & \(\mathbf{pop}=\mathbf{2048}\) & \(\mathbf{pop}=\mathbf{8192}\) & \(\mathbf{pop}=\mathbf{16},\mathbf{384}\) \\ \hline car-s-91 & 4.37 & 4.54 & 21.97 & 23.96 \\ hec-s-92 & 3.26 & 4.73 & 25.372 & 26.17 \\ lse-f-91 & 3.09 & 4.32 & 22.54 & 23.25 \\ pur-s-93 & 4.34 & 4.31 & 22.11 & 21.37 \\ \hline \end{tabular}
\end{table}
Table 2: Total speedup for the examination-threaded approach.  
\begin{table}
\begin{tabular}{l c c c c} \hline
**Dataset** & **Full Conflict Matrix (ms)** & **CSR Conflict Matrix (ms)** & **Speedup** & **Conflict Density** \\ \hline car-s-91 & 20.80 & 3.97 & 5.24 & 0.13 \\ hec-s-92 & 0.12 & 0.09 & 1.29 & 0.42 \\ lse-f-91 & 5.52 & 0.41 & 13.44 & 0.06 \\ pur-s-93 & 377.09 & 11.50 & 32.78 & 0.03 \\ \hline \end{tabular}
\end{table}
Table 3: GPU evaluation execution time and speedup between the full conflict matrix and the compressed sparse row format implementation.  
best reported solutions in the literature, for all of the datasets with the genetic algorithm, is illustrated. In Table 5, the respective values for the hybrid evolutionary algorithm are given. The results are from five runs for three population sizes with different seeds and a small number of initial solutions. The only dataset with no initial solutions was _pur-s-93_. The mutation probability was 0.8% and the crossover probability 30%. The distance from the best solution with the steepest descent algorithm is smaller for all of the datasets. In the next Tables when the algorithm failed to provide a feasible solution with the selected parameters it is denoted using INF which stands for infeasible.  
\begin{table}
\begin{tabular}{l r r r} \hline \hline
**Dataset** & \(\mathbf{pop=256}\) & \(\mathbf{pop=2048}\) & \(\mathbf{pop=16,384}\) \\ \hline car-f-92 & 89.68 & 89.41 & 58.46 \\ car-s-91 & 110.67 & 110.67 & 80.40 \\ ear-f-83 & 74.85 & 64.78 & 56.94 \\ hec-s-92 & 91.06 & 80.73 & 74.10 \\ kfu-s-93 & 91.80 & 58.66 & 38.87 \\ lse-f-91 & 113.42 & 70.32 & 59.98 \\ pur-s-93 & INF & INF & INF \\ rye-s-93 & 153.7 & 149.91 & 94.54 \\ sta-f-83 & 19.43 & 19.43 & 19.23 \\ tre-s-92 & 57.04 & 48.06 & 42.17 \\ uta-s-92 & 81.56 & 81.56 & 65.40 \\ ute-s-92 & 35.83 & 25.88 & 19.85 \\ yor-f-83 & 41.41 & 37.12 & 30.41 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Average distance (%) from the best reported solution in the bibliography with the genetic algorithm.  
\begin{table}
\begin{tabular}{l r r r} \hline \hline
**Dataset** & \(\mathbf{pop=256}\) & \(\mathbf{pop=2048}\) & \(\mathbf{pop=16,384}\) \\ \hline car-f-92 & 42.21 & 29.40 & 26.77 \\ car-s-91 & 44.84 & 30.27 & 24.95 \\ ear-f-83 & 43.16 & 33.77 & 28.88 \\ hec-s-92 & 30.87 & 27.02 & 20.78 \\ kfu-s-93 & 24.17 & 16.15 & 12.53 \\ lse-f-91 & 43.20 & 29.03 & 27.43 \\ pur-s-93 & 263.7 & 153.23 & 126.06 \\ rye-s-93 & 54.01 & 36.38 & 33.36 \\ sta-f-83 & 16.83 & 16.69 & 16.64 \\ tre-s-92 & 22.88 & 19.42 & 13.85 \\ uta-s-92 & 43.95 & 30.13 & 25.57 \\ ute-s-92 & 7.52 & 5.43 & 4.53 \\ yor-f-83 & 17.64 & 13.40 & 11.31 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Average distance (%) from the best reported solution in the bibliography with the hybrid evolutionary algorithm.