A novel technique for optimization over the canonical signed-digit number space using genetic algorithms

In a previous paper, a novel approach was presented for the restoration of “corrupted” canonical signed-digit (CSD) numbers to their correct format after the application of crossover and mutation operations in genetic algorithms. This paper is concerned with the development of a new technique for the crossover and mutation of CSD numbers which avoids the corruption of the resulting offspring numbers altogether. This is accomplished by encoding the CSD numbers in terms of an “elasticity” factor representing the number of zero digits between each pair of non-zero neighboring digits. The resulting encoding leads to marked improvements in efficiency in terms of storage requirements in the course of optimization, particularly for larger CSD number wordlengths. Furthermore, it gives rise to important flexibility in practical optimization situations by making it possible to place a constraint on the maximum number of non-zero digits in the resulting offspring CSD numbers. In addition, it preserves, as much as possible, the value and the bit-pattern of these offspring CSD numbers, with the bit-pattern becoming crucial when one considers sub-expression sharing. An application example is given to illustrate the resulting technique