Article

New usage of Sammon's mapping for genetic visualization

Authors:

Byung-Ro MoonAuthors Info & Claims

GECCO'03: Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartI

Pages 1136 - 1147

Published: 12 July 2003 Publication History

Abstract

It is a hard problem to understand the fitness landscape of a problem as well as the evolution of genetic algorithms. For the purpose, we adopt Sammon's mapping for the investigation. We demonstrate its usefulness by applying it to the graph partitioning problem which is a well-known NP-hard problem. Also, through the investigation of schema traces, we explain the genetic process and the reordering effect in the genetic algorithm.

References

[1]

K. D. Boese, A. B. Kahng, and S. Muddu. A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 15:101-113, 1994.

Digital Library

[2]

T. N. Bui and B. R. Moon. Hyperplane synthesis for genetic algorithms. In Fifth International Conference on Genetic Algorithms, pages 102-109, July 1993.

Digital Library

[3]

T. N. Bui and B. R. Moon. Genetic algorithm and graph partitioning. IEEE Trans. on Computers, 45(7):841-855, 1996.

Digital Library

[4]

T. D. Collins. Genotypic-space mapping: Population visualization for genetic algorithms. The Knowledge Media Institute, The Open University, Milton Keynes, UK, Technical Report KMI-TR-39, 30th September 1996.

[5]

D. De Ridder and R.P.W. Duin. Sammon's mapping using neural networks: a comparison. Pattern Recognition Letters, 18(11-13):1307-1316, 1997.

Digital Library

[6]

R. Dybowski, T.D. Collins, and P. Weller. Visualization of binary string convergence by Sammon mapping. In Fifth Annual Conference on Evolutionary Programming, pages 377-383, 1996.

[7]

W. Dzwinel. How to make Sammon mapping useful for multidimensional data structures analysis. Pattern Recognition, 27(7):949-959, 1994.

[8]

M. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.

Digital Library

[9]

E. Hart and P. Ross. GAVEL - a new tool for genetic algorithm visualization. IEEE Transactions on Evolutionary Computation, 5(4):335-348, 2001.

Digital Library

[10]

J. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.

Digital Library

[11]

T. Jones and S. Forrest. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In Sixth International Conference on Genetic Algorithms, pages 184-192, 1995.

Digital Library

[12]

B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, 49:291-307, Feb. 1970.

[13]

M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, pages 245-254, Cambridge, MA, 1992. MIT Press.

[14]

E. Pekalska, D. De Ridder, R.P.W. Duin, and M.A. Kraaijveld. A new method of generalizing Sammon mapping with application to algorithm speed-up. In Fifth Annual Conference of the Advanced School for Computing and Imaging, pages 221- 228, 1999.

[15]

H. Pohlheim. Visualization of evolutionary algorithms - set of standard techniques and multidimensional visualization. In Genetic and Evolutionary Computation Conference, pages 533-540, 1999.

[16]

J. W. Sammon, Jr. A non-linear mapping for data structure analysis. IEEE Transactions on Computers, 18:401-409, 1969.

Digital Library

[17]

E. D. Weinberger. Fourier and Taylor series on fitness landscapes. Biological Cybernetics, 65:321-330, 1991.

Digital Library

[18]

D. Whitley and J. Kauth. GENITOR: A different genetic algorithm. In Rocky Mountain Conference on Artificial Intelligence, pages 118-130, 1988.

Cited By

Veerapen NOchoa G(2018)Visualising the global structure of search landscapesGenetic Programming and Evolvable Machines10.1007/s10710-018-9328-119:3(317-349)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10710-018-9328-1
Kim YLee KYoon YRothlauf F(2009)Visualizing the search process of particle swarm optimizationProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569909(49-56)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569909
Harman M(2007)The Current State and Future of Search Based Software Engineering2007 Future of Software Engineering10.1109/FOSE.2007.29(342-357)Online publication date: 23-May-2007
https://dl.acm.org/doi/10.1109/FOSE.2007.29
Show More Cited By

New usage of Sammon's mapping for genetic visualization

Recommendations

Introducing probabilistic adaptive mapping developmental genetic programming with redundant mappings
Abstract
Developmental Genetic Programming (DGP) algorithms have explicitly required the search space for a problem to be divided into genotypes and corresponding phenotypes. The two search spaces are often connected with a genotype-phenotype mapping (GPM) ...
Complex energy landscape mapping by histogram assisted genetic algorithm
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

A histogram assisted adjustment of fitness distribution in standard genetic algorithm is introduced and tested on four benchmark functions of complex landscapes, with remarkable improvement in performance, such as the substantial enhancement in the ...
New Hardware Engine for Genetic Algorithms
ICGEC '11: Proceedings of the 2011 Fifth International Conference on Genetic and Evolutionary Computing

Genetic algorithm is a soft computing method that works on set of solutions. These solutions are called chromosome and the best one is the absolute solution of the problem. Unfortunately, most of the genetic algorithms are implemented in software and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

GECCO'03: Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartI

July 2003

1251 pages

ISBN:3540406026

Editor:
Erick Cantú-Paz
Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 July 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Veerapen NOchoa G(2018)Visualising the global structure of search landscapesGenetic Programming and Evolvable Machines10.1007/s10710-018-9328-119:3(317-349)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10710-018-9328-1
Kim YLee KYoon YRothlauf F(2009)Visualizing the search process of particle swarm optimizationProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569909(49-56)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569909
Harman M(2007)The Current State and Future of Search Based Software Engineering2007 Future of Software Engineering10.1109/FOSE.2007.29(342-357)Online publication date: 23-May-2007
https://dl.acm.org/doi/10.1109/FOSE.2007.29
Harman M(2006)Search based software engineeringProceedings of the 6th international conference on Computational Science - Volume Part IV10.1007/11758549_100(740-747)Online publication date: 28-May-2006
https://dl.acm.org/doi/10.1007/11758549_100
Kim YMoon BO'Reilly U(2005)New topologies for genetic search spaceProceedings of the 7th annual conference on Genetic and evolutionary computation10.1145/1068009.1068232(1393-1399)Online publication date: 25-Jun-2005
https://dl.acm.org/doi/10.1145/1068009.1068232

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents