research-article

Automated shape composition based on cell biology and distributed genetic programming

Authors:

Manolya Eyiyurekli,

David E. BreenAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1179 - 1186

https://doi.org/10.1145/1389095.1389329

Published: 12 July 2008 Publication History

Abstract

Motivated by the ability of living cells to form specific shapes and structures, we present a computational approach using distributed genetic programming to discover cell-cell interaction rules for automated shape composition. The key concept is to evolve local rules that direct virtual cells to produce a self-organizing behavior that leads to the formation of a macroscopic, user-de.ned shape. The interactions of the virtual cells, called Morphogenic Primitives (MPs), are based on chemotaxis-driven aggregation behaviors exhibited by actual living cells. Cells emit a chemical into their environment. Each cell responds to the stimulus by moving in the direction of the gradient of the cumulative chemical field detected at its surface. MPs, though, do not attempt to completely mimic the behavior of real cells. The chemical fields are explicitly defined as mathematical functions and are not necessarily physically accurate. The functions are derived via a distributed genetic programming process. A fitness measure, based on the shape that emerges from the chemical-field-driven aggregation, determines which functions will be passed along to later generations. This paper describes the cell interactions of MPs and a distributed genetic programming method to discover the chemical fields needed to produce macroscopic shapes from simple aggregating primitives.

References

[1]

L. Bai, M. Eyiyurekli, and D.E. Breen. Self-organizing primitives for automated shape composition. In Proc. IEEE International Conference on Shape Modeling & Applications, 2008.

[2]

P.J. Bentley and D.W. Corne, editors. Creative Evolutionary Systems. Morgan Kaufman, San Francisco, CA, 2002.

Digital Library

[3]

E. Bonabeau, M. Dorigo, and G. Theraulaz. Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, 1999.

Digital Library

[4]

E. Bonabeau, S. Guerin, D. Snyers, P. Kuntz, and G. Theraulaz. Three-dimensional architectures grown by simple stigmergic agents. Biosystems, 56(1):13--32, 2000.

[5]

C. Brown. UNIX Distributed Programming. Prentice Hall, New York, 1994.

Digital Library

[6]

J.A. Davies. Mechanisms of Morphogenesis. Elsevier, Amsterdam, 2005.

[7]

P. Eggenberger. Evolving morphologies of simulated 3D organisms based on differential gene expression. In Proc. 4th European Conference on Artificial Life, pages 205--213, 1997.

[8]

A.E. Eiben and J.E. Smith. Introduction to Evolutionary Computing. Springer, 2003.

Digital Library

[9]

E. Eisenbach et al. Chemotaxis. Imperial College Press, London, 2004.

[10]

M. Eyiyurekli. A Computational Model of Chemotaxis-based Cell Aggregation. Master's thesis, Drexel University, 2006.

[11]

M. Eyiyurekli, P. Lelkes, and D. Breen. A computational system for investigating chemotaxis-based cell aggregation. In Proc. European Conference on Artificial Life, pages 1034--1049, 2007.

Digital Library

[12]

M. Eyiyurekli, P. Lelkes, and D. Breen. Simulation of chemotaxis-based sorting of heterotypic cell populations. In Proc. IEEE / NIH BISTI Life Science Systems & Applications Workshop, pages 47--50, 2007.

[13]

K.W. Fleischer. A Multiple-Mechanism Developmental Model for Defining Self-Organizing Geometric Structures. PhD thesis, California Institute of Technology, 1995.

Digital Library

[14]

K.W. Fleischer and A.H. Barr. A simulation testbed for the study of multicellular development: The multiple mechanisms of morphogenesis. In Artificial Life III, pages 389--408. 1994.

[15]

K.W. Fleischer, D.H. Laidlaw, B.L. Currin, and A.H. Barr. Cellular texture generation. In Proc. SIGGRAPH, pages 239--248, 1995.

Digital Library

[16]

C. Gagné and M. Parizeau. Genericity in evolutionary computation software tools: Principles and case-study. International Journal on Artificial Intelligence Tools, 15(2):173--194, 2006.

[17]

S.F. Gilbert. Developmental Biology. Sinauer Associates, Inc., Sunderland, MA, 8th edition, 2006.

[18]

P.E. Hotz. Combining developmental processes and their physics in an artificial evolutionary system to evolve shapes. In Kumar S. and P.J. Bentley, editors, On Growth, Form and Computers, pages 302--318. Academic Press, 2003.

[19]

H. Juille and J.B. Pollack. Parallel genetic programming and fine-grained SIMD architecture. In Working Notes for the AAAI Symposium on Genetic Programming, pages 31--37. AAAI, 1995.

[20]

J. Klein and L. Spector. Unwitting distributed genetic programming via asynchronous JavaScript and XML. In Proc. 9th Annual Conference on Genetic and Evolutionary Computation, pages 1628--1635, 2007.

Digital Library

[21]

J.R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.

Digital Library

[22]

J.R. Koza and D. Andre. Parallel Genetic Programming on a Network of Transputers. Dept. of Computer Science, Stanford University, 1995.

[23]

C.H. Messom and G Walker. Evolving cooperative robotic behaviour using distributed genetic programming. In Proc. 7th Int. Conference on Control, Automation, Robotics and Vision, volume 1, 2002.

[24]

R. Poli, University of Birmingham, and Cognitive Science Research Centre. Parallel Distributed Genetic Programming. University of Birmingham, Cognitive Science Research Centre, 1996.

[25]

P.B.B. Rao and RC Hansdah. Extended Distributed Genetic Algorithm for Channel Routing. In Proc. 5th IEEE Symposium on Parallel and Distributed Processing, pages 726--733, 1993.

Digital Library

[26]

K. Sims. Artificial evolution for computer graphics. In Proc. SIGGRAPH, pages 319--328, 1991.

Digital Library

[27]

K. Sims. Interactive evolution of equations for procedural models. The Visual Computer, 9(8):466--476, 1993.

[28]

K. Sims. Evolving virtual creatures. In Proc. SIGGRAPH, pages 15--22, 1994.

Digital Library

[29]

G. Theraulaz and E. Bonabeau. Coordination in distributed building. Nature, 269:686--688, 1995.

[30]

G. Theraulaz and E. Bonabeau. Modeling the collective building of complex architectures in social insects with lattice swarms. Journal of Theoretical Biology, 177:381--400, 1995.

[31]

G. Theraulaz and E. Bonabeau. A brief history of stigmergy. Artificial Life, 5:97--116, 1999.

Digital Library

[32]

M. Tomassini. Parallel and distributed evolutionary algorithms: A review. In Evolutionary Algorithms in Engineering and Computer Science, pages 113--133. John Wiley & Sons, Chichester, 1999.

[33]

M. Tomassini, F. Fernández, L. Vanneschi, and L. Bucher. An MPI-Based Tool for Distributed Genetic Programming. In Proc. IEEE Int. Conference on Cluster Computing, pages 209--216, 2000.

[34]

M. Tomassini, L. Vanneschi, F. Fernandez, and G. Galeano. Experimental investigation of three distributed genetic programming models. In Proc. Parallel Problem Solving from Nature-PPSN VII, volume 2439, pages 641--650. Springer, 2002.

Digital Library

[35]

T. Weise and K. Geihs. DGPF-an adaptable framework for distributed multi-objective search algorithms applied to the genetic programming of sensor networks. In Proc. 2nd Int. Conference on Bioinspired Optimization Methods and their Application, pages 157--166, 2006.

Cited By

Alt CMayer H(2013)Evolution of a digital organism playing Go2013 IEEE Conference on Evolving and Adaptive Intelligent Systems (EAIS)10.1109/EAIS.2013.6604115(130-137)Online publication date: Apr-2013
https://doi.org/10.1109/EAIS.2013.6604115
Sayama HMoore J(2012)Morphologies of self-organizing swarms in 3D swarm chemistryProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330245(577-584)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330245
Bai LBreen D(2012)Chemotaxis-Inspired Cellular Primitives for Self-Organizing Shape FormationMorphogenetic Engineering10.1007/978-3-642-33902-8_9(209-237)Online publication date: 13-Dec-2012
https://doi.org/10.1007/978-3-642-33902-8_9
Show More Cited By

Index Terms

Automated shape composition based on cell biology and distributed genetic programming
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Chemotaxis-based sorting of self-organizing heterotypic agents
SAC '10: Proceedings of the 2010 ACM Symposium on Applied Computing

Cell sorting is a fundamental phenomenon in morphogenesis, which is the process that leads to shape formation in living organisms. The sorting of heterotypic cell populations is produced by a variety of inter-cellular actions, e.g. differential ...
Self-organized sorting of heterotypic agents via a chemotaxis paradigm

Cell sorting is a fundamental phenomenon in morphogenesis, a process that leads to shape formation in living organisms. The sorting of heterotypic cell populations is produced by a variety of inter-cellular actions, e.g. differential chemotactic ...
Cell-based computer models in developmental biology

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
192
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alt CMayer H(2013)Evolution of a digital organism playing Go2013 IEEE Conference on Evolving and Adaptive Intelligent Systems (EAIS)10.1109/EAIS.2013.6604115(130-137)Online publication date: Apr-2013
https://doi.org/10.1109/EAIS.2013.6604115
Sayama HMoore J(2012)Morphologies of self-organizing swarms in 3D swarm chemistryProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330245(577-584)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330245
Bai LBreen D(2012)Chemotaxis-Inspired Cellular Primitives for Self-Organizing Shape FormationMorphogenetic Engineering10.1007/978-3-642-33902-8_9(209-237)Online publication date: 13-Dec-2012
https://doi.org/10.1007/978-3-642-33902-8_9
Wang SMa JLiu JCheung DSong IChu WHu XLin J(2009)Learning to rank using evolutionary computationProceedings of the 18th ACM conference on Information and knowledge management10.1145/1645953.1646254(1879-1882)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1645953.1646254
Linge Bai Eyiyurekli MBreen D(2008)Self-organizing primitives for automated shape composition2008 IEEE International Conference on Shape Modeling and Applications10.1109/SMI.2008.4547962(147-154)Online publication date: Jun-2008
https://doi.org/10.1109/SMI.2008.4547962
Bai LEyiyurekli MBreen D(2008)An Emergent System for Self-Aligning and Self-Organizing Shape PrimitivesProceedings of the 2008 Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems10.1109/SASO.2008.54(445-454)Online publication date: 20-Oct-2008
https://dl.acm.org/doi/10.1109/SASO.2008.54

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten