In this section we describe how EvoSAP can be improved by incorporating an adaptive diversification mechanism based on TABU search. Observe that at each generation EvoSAP produces a local optimum. Suppose the Flip Heuristic directs the search towards similar (that is having small Hamming distance) local optima having equal fitness function values. Then we can try to escape from these local optima by prohibiting the flipping of some genes and by adapting the probability of mutation of the genes that are allowed to be modified.
To this aim, we use the following technique based on TABU search. A table is considered which is dynamically filled with chromosomes having best fitness. If the best fitness increases then the table is emptied. When the table is full, the chromosomes are compared gene-wise. Those genes which do not have the same value in all the chromosomes are labeled as `frozen'. Formally, the table can be represented by a (k,n) matrix T, where k is the number of chromosomes the table can contain, and n is the number of variables of the considered SAT problem. The entry T(i,j) contains the value of the j-th gene in the i-th chromosome of T. Let frozen be an array of length n whose entry j is 0 if the j-th gene is not frozen, and it is 1 otherwise. Initially all genes are not frozen.
When the table is filled, we consider the quantities , for every . If val(j) is 0 or k then we set frozen(j) to 1 (the j-th gene becomes frozen). We denote by n_frozen the number of frozen genes. The size k of the table T is a parameter. After computational testing, we decided to set k to 10. When the fitness of the best chromosome increases, the table is emptied and all genes are unfrozen, that is, frozen(j) is set to 0 for every j, and n_frozen is set to 0.
We use the information contained in T for adapting the search strategy during the execution as follows. Each time T is full, the mutation rate is recomputed, the flipping of frozen genes is prohibited, and possibly the execution is restarted from a new random search point. Let us describe how these three actions are performed. The mutation rate is set to 1/2 * n_frozen/n, thus 0 <= mut_prob <= 0.5 . Frozen genes are not allowed to be flipped neither by the mutation operator nor by the Flip Heuristic.
The rationale behind these two actions is the following. If table T becomes full it means that the search strategy has found for k times best chromosomes with equal fitness. A gene which is not frozen has the same value in all these chromosomes. This indicates that the search directs often to local optima containing the values of the not frozen genes. Therefore in the next iteration we allow to flip only not frozen genes in order to reach search points far enough from the attraction basin of those local optima. The mutation rate is chosen in such a way that the lower the number of not frozen genes is, the higher the probability will be to flip them. The term 1/2 is used to keep the mutation rate smaller or equal than 0.5.
Finally the information in the table T is used for possibly restarting the search. The chromosomes in T are grouped into equivalence classes, each class containing equal chromosomes. If the number of equivalent classes is very small, that is less or equal than two, it means that the last k best chromosomes found so far are of just one or two forms, indicating that the search is strongly biased towards those chromosomes. Then it seems worth to re-start the search from a new randomly generated chromosome.
The overall Adaptive evolutionary algorithm for the SAtisfiability Problem, called ASAP, is summarized in pseudo-code below. Adaptive mutation is the mutation operator which allows to mutate only not frozen genes. Analogously, the adaptive Flip Heuristic allows only the flipping of non-frozen genes.
The mutation rate is initially equal to 0.5. The termination condition in ASAP is equal to the one of EvoSAP, that is, either the optimum is found or the maximum number of chromosomes have been generated.
PROCEDURE ASAP randomly generate chromosome C; apply Flip Heuristic to C; WHILE (not termination condition) DO BEGIN C0=C; apply adaptive mutation to C; apply adaptive Flip Heuristic to C; UPDATE_TABLE; END END
PROCEDURE UPDATE_TABLE BEGIN unfreeze all genes; IF (fitness C0 > fitness C) /* discard C */ C=C0; ELSE IF (fitness C > fitness C0) BEGIN empty table T; add C to table T; END ELSE /* fitness C0 = fitness C */ BEGIN add C to table T; IF (table T full) BEGIN compute frozen genes; adapt mutation rate; count classes; IF (number of classes <= 2) RESTART; empty table T; END END END