Problem is not specifically for sorting, but the more general case. I just used sorting as an example.
It may be that it is impossible to formulate general purpose fitness functions for problems that are not numerical in nature, unless using detailed knowledge of the specific problem.
Jeferytitan had some interesting suggestions I can build on. That is, it is easier to define penalties on behavior.