# The Color Mix Problem
## 3 Hybrid Genetic Algorithm for the Solution of the Color Mix Problem
### Crossover Procedure
``` // pseudocode of the greedy offspring creation sub-procedure // input: \(B\), \(n\), \(m\), \(m_{1}\), \(p\), this_\(c\), common_elements, #_of_points, \(c_{1}\), \(c_{2}\), \(c_{3}\) // output: \(p\), common_elements, \(c_{1}\), \(c_{2}\), \(c_{3}\) begin if(common_elements \(\
eq\) #_of_points) minimum_contribution \(\leftarrow\)\(\infty\); \(j\gets 0\); do if(element \(p(j)\) is not yet selected) if(this_c(\(p(j))<minimum_contribution) minimum_contribution \(\leftarrow\) this_c(\(p(j)\))); \(k\gets j\) endif; \(j\gets j+1\) while(\(j\
eq\) #_of_points); if(minimum_contribution \(\
eq\)\(\infty\)) if(#_of_points \(=\)\(m_{1}\)) \(i\gets 0\); do \(c_{1}(i)\gets c_{1}(i)+2\times b_{i,p(k)}\); \(c_{2}(i)\gets c_{2}(i)+b_{i,p(k)}\); \(c_{3}(i)\gets c_{3}(i)+b_{i,p(k)}\); \(i\gets i+1\) while(\(i\
eq n\)); elseif(#_of_points \(=\)\(m\)) \(i\gets 0\); do \(c_{1}(i)\gets c_{1}(i)+b_{i,p(k)}\); \(c_{2}(i)\gets c_{2}(i)+2\times b_{i,p(k)}\); \(c_{3}(i)\gets c_{3}(i)-b_{i,p(k)}\); \(i\gets i+1\) while(\(i\
eq n\)); endif; \(p(common\_elements)\gets p(k)\); common_elements \(\leftarrow\) common_elements \(+1\) endif endif end. ```
**Algorithm 4** Greedy_Offspring_Creation

### Offspring Improvement

#### 3.4.1 Hierarchical Iterated Tabu Search Algorithm

Every produced offspring is subject to improvement by the hierarchical iterated tabu search procedure which can also be seen as a multi-level tabu search [17] procedure, where the basic idea is the cyclic (multiple) reuse of the tabu search algorithm. The \(k\)-levelhierarchical iterated tabu search algorithm is consisting of three main ingredients: (1) call of the \(k-1\)-level hierarchical iterated tabu search procedure; (2) selection (acceptance) of the solution for perturbation, i.e., mutation; (3) perturbation of the selected solution. The perturbed solution serves as an input for the autonomous (self-contained) TS procedure. The TS algorithm gives back an optimized solution, and so on. The solution acceptance rule is very simple: we always accept the recently found improved solution. The overall iterative process is continued until a given total number of iterations have been accomplished (see Algorithm 4). The time complexity of HITS is proportional to



#### 3.4.2 Tabu Search Algorithm

The 0-level HITS algorithm (the ITS algorithm) uses a self-contained (\"kernel\") tabu search (TS) procedure (a more detailed discussion of the principles of TS algorithms can be found in [18]). It is this procedure that is wholly responsible for the improvement of a given solution. At the same time, this procedure is in the role of the intensification of the search process, while the perturbation process rather serves as the search diversification mechanism. Briefly speaking, the TS procedure analyses the neighbourhood of the incumbent solution and accepts the non-tabu (non-prohibited) move that most improves the objective function. In order to avoid cycling search trajectories, the return to recently visited solutions is forbidden for some time period. The tabu list (list of prohibitions), \(T\), is operationalized as a matrix of size \(n\times n\). In this case, the entry \(t_{ij}\) memorizes the sum of the current iteration number and the tabu tenure, \(h\). The value of \(h\) depends on the problem size, \(n\) (we have chosen \(h=0.5n\)). It should be noted that the tabu status is disregarded at accident moments with a very small probability \(\alpha\) (\(\alpha<0.1\)). This strategy enables to increase the number of non-prohibited solutions and not to confine the search directions too much. The tabu status is also ignored if an aspiration criterion is satisfied, i.e., the currently attained solution appears better than the best obtained solution. Moreover, our TS algorithm utilizes an additional memory known as a secondary memory, \(SM\). The goal of this memory is to archive high-quality solutions, which although are evaluated as quite good, but are not elected.