A tight single-change covering design (TSCCD) is an ordered set of ordered sets of integers, or in other words, a sequence of “blocks”. The size and complexity of a TSCCD are determined by two parameters: v, the total number of unique integers, or “symbols”, and k, the number of symbols in each block. A valid TSCCD consists of a sequence of blocks which satisfies three properties. First, each successive block must have all symbols in common with the preceding block except for any single symbol which must differ. This is the “single-change” element. Second, all unique pairs of v symbols must be represented, or “covered”, by the constituent symbols’ appearance together in at least one block. Finally, for each single changed symbol from one block to the next, all pairs formed by the new symbol’s introduction to the block must not be formed in any preceding block. This is the “tight” element of the problem. TSCCDs are deceptively complex constructions, and they are not easy to generate in non-trivial sizes.
CS448 was a high level evolutionary algorithms course. Students were given a choice of several problems to attack throughout the semester with whatever EA design seemed appropriate. I chose to try to generate TSCCDs, following up a previous student’s work. That student didn’t succeed in generating a complete (20,5) design, and neither did I. TSCCDs have an immensely complex solution space, an absolute minefield of suboptima.
There’s too much to say here, so I’ll just defer to my paper. Help yourself to the EA code and collapser code.
