Abstract
This paper proposes a new method for treating the inverse problem for Iterated Functions Systems (IFS) using Genetic Programming. This method is based on two original aspects. On the fractal side, a new representation of the IFS functions, termed Polar Iterated Functions Systems, is designed, shrinking the search space to mostly contractive functions. Moreover, the Polar representation gives direct access to the fixed points of the functions. On the evolutionary side, a new variant of GP, the “Parisian” approach is presented. The paper explains its similarity to the “Michigan” approach of Classifier Systems: each individual of the population only represents a part of the global solution. The solution to the inverse problem for IFS is then built from a set of individuals. A local contribution to the global fitness of an IFS is carefully defined for each one of its member functions and plays a major role in the fitness of each individual. It is argued here that both proposals result in a large improvement in the algorithms. We observe a drastic cut-down on CPU-time, obtaining good results with small populations in few generations.
Similar content being viewed by others
References
M. F. Barnsley, Fractals Everywhere, Academic Press: New York, 1988.
M. Barnsley and S. Demko, "Iterated function system and the global construction of fractals," Proc. R. Soc. A, vol. 399, pp. 243–245, 1985. 360 collet et al.
M. Barnsley, V. Ervin, D. Hardin, and J. Lancaster, "Solution of an inverse problem for fractals and other sets," Proc. Natl. Acad. Sci. USA, vol. 83, 1986.
P. Collet, E. Lutton, F. Raynal, and M. Schoenauer, "Individual GP: an alternative viewpoint for the resolution of complex problems," in Genetic and Evolutionary Computation Conference, W. Banzhaf, J. Dauda, A. Eiben, M. Garzon, V. Honavar, M. Jakiela, and R. Smith (eds.), Morgan Kaufman: San Francisco, 1999, pp. 974–981.
K. A. De Jong, "The analysis of the behavior of a class of genetic adaptive systems," Ph.D. thesis, University of Michigan Press: Ann Arbor, 1975.
F. M. Dekking, Fractal image coding: some mathematical remarks on its limits and its prospects," Fractal Image Encoding and Analysis, in Y. Fisher (ed.), NATO ASI Ser. F: Comput. Syst. Sci. vol. 159, pp. 117–133, Springer-Verlag: Berlin, 1998.
Y. Fisher, Fractal Image Compression: Theory and Application, Springer-Verlag: New York, 1995.
B. Goertzel, H. Miyamoto, and Y. Awata, "Fractal image compression with the genetic algorithm, Complex. Int. vol. 1, pp. 25–28, 1994, http://www.csu.edu.au/ci/vol1/goertzel.html.
D. P. Hardin, "Hyperbolic iterated function systems and applications," Ph.D. Thesis, Georgia Institute of Technology, 1985.
J. H. Holland, "Escaping brittleness: the possibilities of general purpose learning algorithms applied to parallel rule-based systems," in Machine Learning: An Artificial Intelligence Approach, R. Michalski, J. Carbonell, and T. Mitchell (eds.), Morgan Kauffman: San Francisco: 1986, vol. 2, pp. 593–623.
J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press: Ann Arbor, 1975.
J. Hutchinson, "Fractals and self-similarity," Ind. Univ. J. Math. vol. 30, pp. 713–747, 1981.
A. E. Jacquin, "Fractal image coding: a review," Proc. IEEE, vol. 81, no. 10 pp. 1451–1465, 1993.
J. Lévy Véhel, “Analyse et synthése d'objets bi-dimensionnels par des methodes stochastiques,” Ph.D. thesis, Univ. de Paris Sud, Décembre 1988.
J. Lévy Véhel, K. Daoudi, and E. Lutton, "Fractal modeling of speech signals," Fractals, vol. 2, no. 3, pp. 379–382, 1994.
E. Lutton, J. Lévy Véhel, G. Cretin, P. Glevarec, and C. Roll, "Mixed IFS: resolution of the inverse problem using genetic programming," Complex Syst. vol. 9, pp. 375–398, 1995.
G. Mantica and A. Sloan, "Chaotic optimization and the construction of fractals: solution of an inverse problem," Complex Syst. vol. 3, pp. 37–62, 1989.
B. L. Miller and M. J. Shaw, "Genetic algorithms with dynamic niche sharing for multimodal function optimization," IlliGAL Technical Report 95010, 1995.
D. J. Nettleton and R. Garigliano, "Evolutionary algorithms and a fractal inverse problem," Biosystems, vol. 33, pp. 221–231, 1994.
J. Puate and F. Jordan, "Using fractal compression scheme to embed a digital signature in an image," in Video techniques and software for full-service networks, T. Chiueh and A. G. Tescher (eds.), SPIE Proc. vol. 2915, pp. 108–118, 1996.
F. Raynal, E. Lutton, P. Collet, and M. Schoenauer, "Manipulation of non-linear IFS attractors using genetic programming," in Cong. Evol. Comput. 99, P. J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala (eds.), IEEE Press, 1999, pp. 1171–1177.
M. Schoenauer, "Representations for evolutionary optimization and identification in structural mechanics, in Genetic Algorithms in Engineering and Computer Sciences, J. Périaux and G. Winter (eds.), John Wiley: New York, 1995, pp. 443–464.
M. Schoenauer, M. Sebag, F. Jouve, B. Lamy, and H. Mautournam, "Evolutionary identification of macro-mechanical models," in Advances in Genetic Programming II, P. J. Angeline and K. E. Kinnear, Jr. (eds.), MIT Press: Cambridge, MA: 1996, pp. 467–488.
S. F. Smith, "Flexible learning of problem solving heuristics through adaptive search, in Proc. IJCAU83, A. Bundy (ed.), Morgan Kaufmann: San Franscisco, 1983, pp. 422–425.
L. Vences and I. Rudomin, "Genetic algorithms for fractal image and image sequence compression, in Proc. Comput. Visual 1997, Universidad Nacional Autonoma de Mexico, 1997, pp. 35.44, http://sgio2.cem.itesm.mx/rudomin/VISUALPS/lucy.pdf.
E. R. Vrscay, "Fractal geometry and analysis, the Mandelbrot Festschrift, Curacao 1995," in Iterated Function Systems: Theory, Applications and the Inverse Problem, C. J. G. Evertsz, H.-O. Peitgen, and R. F. Voss (eds.), World Scientific, 1996, pp. 405–468.
E. R. Vrscay, "Moment and collage methods for the inverse problem of fractal construction with iterated function systems," in Fractal 90 Conference, Fractals in Fundamental and Applied Sciences, H.-O. Peitgen, J. M. Henriques, and L. F. Penedo (eds.), North Holland, 1991, pp. 271–289.
M. Wall, "GALib: a C++ library of genetic algorithm components," http://lancet.mit.edu/ga/.
S. W. Wilson and D. E. Goldberg, "A critical review of classifier systems," in Proc. 3rd Int. Conf. Genetic Algorithms, J. D. Schaffer (ed.), Morgan Kauffman: San Francisco, 1989, pp. 244–255.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Collet, P., Lutton, E., Raynal, F. et al. Polar IFS+Parisian Genetic Programming=Efficient IFS Inverse Problem Solving. Genetic Programming and Evolvable Machines 1, 339–361 (2000). https://doi.org/10.1023/A:1010065123132
Issue Date:
DOI: https://doi.org/10.1023/A:1010065123132