Properties of symmetric fitness functions

ABSTRACT

The properties of symmetric fitness functions are investigated. We show that a well-known encoding scheme inducing symmetric functions has the non-synonymous property and the search spaces obtained from symmetric functions have the zero-correlation structures. The Walsh analysis reveals the properties of symmetric functions related to additive separability, problem difficulty measures and so on. Our results support the claim of other researchers that the search spaces with symmetry induce relatively difficult problems. The results also present some limitations of existing problem difficulty measures for symmetric fitness functions.

REFERENCES

• 1: Larry J. Eshelman , J. David Schaffer, Crossover's Niche, Proceedings of the 5th International Conference on Genetic Algorithms, p.9-14, June 01, 1993
• 2: Clarissa Van Hoyweghen , David E. Goldberg , Bart Naudts, From Twomax To The Ising Model: Easy And Hard Symmetrical Problems, Proceedings of the Genetic and Evolutionary Computation Conference, p.626-633, July 09-13, 2002
• 3: Richard A. Watson , Greg Hornby , Jordan B. Pollack, Modeling Building-Block Interdependency, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.97-108, September 27-30, 1998
• 4: Clarissa Van Hoyweghen , Bart Naudts , David E. Goldberg, Spin-flip symmetry and synchronization, Evolutionary Computation, v.10 n.4, p.317-344, December 2002 [doi>10.1162/106365602760972749]
• 5: Emanuel Falkenauer, Genetic Algorithms and Grouping Problems, John Wiley & Sons, Inc., New York, NY, 1998
• 6: S. H. Kim, Y. H. Kim, and B. R. Moon. A hybrid genetic algorithm for the max cut problem. In Genetic and Evolutionary Computation Conference, pages 416--423, 2001.
• 7: G. Laszewski. Intelligent structural operators for the k-way graph partitioning problem. In Fourth International Conference on Genetic Algorithms, pages 45--52, 1991.
• 8: Thang Nguyen Bui , Byung Ro Moon, Genetic Algorithm and Graph Partitioning, IEEE Transactions on Computers, v.45 n.7, p.841-855, July 1996 [doi>10.1109/12.508322]
• 9: S. J. Kang and B. R. Moon. A hybrid genetic algorithm for multiway graph paritioning. In Genetic and Evolutionary Computation Conference, pages 159--166, 2000.
• 10: S. Fischer and I. Wegener. The ising model on the ring: Mutation versus recombination. In Genetic and Evolutionary Computation Conference, pages 1113--1124, 2004.
• 11: C. Van Hoyweghen and B. Naudts. Symmetry in the search space. In Congress on Evolutionary Computation, pages 1072--1079, 2000.
• 12: C. Van Hoyweghen, D. E. Goldberg, and B. Naudts. Building block superiority, multimodality and synchronization problems. In Genetic and Evolutionary Computation Conference, pages 694--701, 2001.
• 13: H. Mühlenbein. Parallel genetic algorithms in combinatorial optimization. In Computer Science and Operations Research: New Developments in Their Interfaces, pages 441--453, 1992.
• 14: Raphaël Dorne , Jin-Kao Hao, A New Genetic Local Search Algorithm for Graph Coloring, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.745-754, September 27-30, 1998
• 15: Sung-Soon Choi , Byung Ro Moon, Isomorphism, Normalization, And A Genetic Algorithm For Sorting Network Optimization, Proceedings of the Genetic and Evolutionary Computation Conference, p.327-334, July 09-13, 2002
• 16: J. H. Kim, S. S. Choi, and B. R. Moon. Neural network normalization for genetic search. In Genetic and Evolutionary Computation Conference, pages 398--399, 2004.
• 17: M. Dietzfelbinger, B. Naudts, C. Van Hoyweghen, and I. Wegener. The analysis of a recombinative hill-climber on H-IFF. IEEE Trans. on Evolutionary Computation, 7(5):417--423, 2003.
• 18: Franz Rothlauf , David E. Goldberg, Redundant representations in evolutionary computation, Evolutionary Computation, v.11 n.4, p.381-415, Winter 2003 [doi>10.1162/106365603322519288]
• 19: E. D. Weinberger. Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics, 63:325--336, 1990.
• 20: P. F. Stadler. Landscapes and their correlation functions. Journal of Mathematical Chemistry, 20:1--45, 1996.
• 21: Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 1995
• 22: K. D. Boese, A. B. Kahng, and S. Muddu. A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 16:101--113, 1994.
• 23: Peter Merz , Bernd Freisleben, Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning, Evolutionary Computation, v.8 n.1, p.61-91, March 2000 [doi>10.1162/106365600568103]
• 24: P. Merz and B. Freisleben. Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. on Evolutionary Computation, 4(4):337--352, 2000.
• 25: J. L. Walsh. A closed set of orthogonal functions. American Journal of Mathematics, 55:5--24, 1923.
• 26: R. B. Heckendorn and D. Whitley. Predicting epistasis directly from mathematical models. Evolutionary Computation, 7(1):69--101, 1999.
• 27: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 28: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 29: C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425--440, 1991.
• 30: C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 31: Y. Davidor. Epistasis variance: A viewpoint on ga-hardness. In Foundations of Genetic Algorithms, volume 1, pages 23--35. Morgan Kaufmann, 1991.
• 32: C. Reeves and C. Wright. An experimental design perspective on genetic algorithms. In Foundations of Genetic Algorithms, volume 3, pages 7--22. Morgan Kaufmann, 1995.
• 33: S. Rochet, M. Slimane, and G. Venturini. Epistasis for real encoding in genetic algorithms. In IEEE Australian New Zealand Conference on Intelligent Information Systems. IEEE Press, 1996.
• 34: B. Naudts, D. Suys, and A. Verschoren. Epistasis as a basic concept in formal landscape analysis. In Seventh International Conference on Genetic Algorithms, pages 65--72. Morgan Kaufmann, 1997.
• 35: M. Manela and J. A. Campbell. Harmonic analysis, epistasis and genetic algorithms. In Parallel Problem Solving from Nature, pages 57--64, 1992.
• 36: Sophie Rochet , Gilles Venturini , M. Slimane , E. M. El Kharoubi, A Critical and Empirical Study of Epistasis Measures for Predicting GA Performances: A Summary, Selected Papers from the Third European Conference on Artificial Evolution, p.275-286, October 01, 1997
• 37: Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, Inc., New York, NY, 1987

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory

Keywords:
Walsh analysis, encoding scheme, problem difficulty measures, search space analysis, symmetric fitness functions