ABC A BC C
the program should output the solution ABC
, which is a one-element subset of the set of strings that covers all three characters that occur in the union of the four input strings. A binary representation of the individuals in the population, indicating whether a particular string is present or not in the corresponding candidate solution, is probably the best way to represent this so that a genetic algorithm can be applied.Your program must accept command-line arguments in the following format:
java SetCover <population size> <mutation rate> <number of iterations> <string 1> <string 2> ...
and output the best individual (i.e. set of strings) found in the given number of iterations. The strings must be output on a single line, separated by spaces.
For example, the command-line:
java SetCover 50 0.05 50 ABC ACD D A C
should produce the output
ABC ACD
In this example, the best solution was found, a two-element set with no missing characters, but this may obviously not be the case in general for a fixed number of iterations. You should design your genetic algorithms so that the likelihood of an optimum solution is maximized for a given number of iterations.
Value: 11% of the final grade
Due date: Wednesday, 26 March, midday
No extensions will be granted except for sound, documented, medical reasons.