Abstract
Evolutionary design of 3D structures – either static structures, or equipped with some sort of a control system – is one of the hardest optimization tasks. One of the reasons are rugged fitness landscapes resulting from complex and non-obvious genetic representations of such structures and their genetic operators. This paper investigates global convexity of fitness landscapes in optimization tasks of maximizing velocity and height of both active and passive structures. For this purpose, a new dissimilarity measure for 3D active and passive structures represented as undirected graphs is introduced. The proposed measure is general and flexible – any vertex properties can be easily incorporated as dissimilarity components. The new measure was compared against the previously introduced measure in terms of triangle inequality satisfiability, changes in raw measure values and the computational cost. The comparison revealed improvements for triangle inequality and raw values at the expense of increased computational complexity. The investigation of global convexity of the fitness landscape, involving the fitness–distance correlation analysis, revealed negative correlation between the dissimilarity of the structures and their fitness for most of the investigated cases.
The second author was supported by the Faculty of Computing, Poznan University of Technology, through the funds provided by the Ministry of Science and Higher Education.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Hornby, G.S., Globus, A., Linden, D.S., Lohn, J.D.: Automated antenna design with evolutionary algorithms. In: AIAA Space, pp. 19–21 (2006)
Funes, P., Pollack, J.: Evolutionary body building: adaptive physical designs for robots. Artif. Life 4(4), 337–357 (1998)
Byrne, J., et al.: Combining Structural Analysis and Multi-Objective Criteria for Evolutionary Architectural Design. In: Chio, C., et al. (eds.) EvoApplications 2011. LNCS, vol. 6625, pp. 204–213. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20520-0_21
Kicinger, R., Arciszewski, T., DeJong, K.: Evolutionary design of steel structures in tall buildings. J. Comput. Civil Eng. 19(3), 223–238 (2005)
Lipson, H., Pollack, J.B.: Automatic design and manufacture of robotic lifeforms. Nature 406(6799), 974–978 (2000)
Nolfi, S., Floreano, D.: Evolutionary Robotics: The Biology, Intelligence, and Technology of self-Organizing Machines. MIT Press, Cambridge (2000)
Corucci, F.: Evolutionary developmental soft robotics: towards adaptive and intelligent soft machines following nature’s approach to design. In: Laschi C., Rossiter J., Iida F., Cianchetti M., Margheri L. (eds) Soft Robotics: Trends, Applications and Challenges. Biosystems & Biorobotics, vol 17, pp. 111–116. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-46460-2_14
Sims, K.: Evolving 3D morphology and behavior by competition. Artif. Life 1(4), 353–372 (1994)
Komosinski, M., Ulatowski, S.: Framsticks: Creating and Understanding Complexity of Life, 2nd edn. pp. 107–148. Springer, New York (2009). http://www.springer.com/978-1-84882-284-9. Chapter 5
Komosinski, M.: Applications of a similarity measure in the analysis of populations of 3D agents. J. Comput. Sci. 21, 407–418 (2017)
Bentley, P.J.: An introduction to evolutionary design by computers. In: Bentley, P.J. (ed.) Evolutionary Design by Computers, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco (1999)
Hornby, G.S., Pollack, J.B.: Generative representations for evolutionary design automation. Brandeis University (2003)
Smith, T., Husbands, P., O’Shea, M.: Fitness landscapes and evolvability. Evol. Comput. 10(1), 1–34 (2002)
He, J., Reeves, C., Witt, C., Yao, X.: A note on problem difficulty measures in black-box optimization: classification, realizations and predictability. Evol. Comput. 15(4), 435–443 (2007)
Boese, K.D.: Cost versus distance in the traveling salesman problem. UCLA Computer Science Department (1995)
Pitzer, E., Affenzeller, M.: A comprehensive survey on fitness landscape analysis. In: Fodor J., Klempous R., Suárez Araujo C.P. (eds) Recent Advances in Intelligent Engineering Systems, vol. 378, pp. 161–191. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-23229-9_8
Jones, T., Forrest, S.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 184–192. Morgan Kaufmann Publishers Inc., San Francisco (1995)
Freisleben, B., Merz, P.: New genetic local search operators for the traveling salesman problem. Parallel Problem Solving from Nature - PPSN IV, pp. 890–899 (1996)
Freisleben, B., Merz, P.: A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 616–621. IEEE (1996)
Jaszkiewicz, A., Kominek, P.: Genetic local search with distance preserving recombination operator for a vehicle routing problem. Eur. J. Oper. Res. 151(2), 352–364 (2003)
Jaszkiewicz, A., Kominek, P., Kubiak, M.: Adaptation of the genetic local search algorithm to a car sequencing problem. In: 7th National Conference on Evolutionary Algorithms and Global Optimization, Kazimierz Dolny, Poland, pp. 67–74 (2004)
Kubiak, M.: Systematic construction of recombination operators for the vehicle routing problem. Found. Comput. Decis. Sci. 29(3) (2004)
Cyr, C.M., Kimia, B.B.: 3D object recognition using shape similiarity-based aspect graph. In: Proceedings Eighth IEEE International Conference on Computer Vision, ICCV 2001, vol. 1, pp. 254–261 (2001)
Barthel, D., Hirst, J.D., Błażewicz, J., Burke, E.K., Krasnogor, N.: ProCKSI: a decision support system for protein (structure) comparison, knowledge, similarity and information. BMC Bioinform. 8(1), 416 (2007)
Bero, S.A., Muda, A.K., Choo, Y.H., Muda, N.A., Pratama, S.F.: Similarity measure for molecular structure: a brief review. J. Phys. Conf. Ser. 892(1), 012015 (2017). http://stacks.iop.org/1742-6596/892/i=1/a=012015
Komosinski, M., Kubiak, M.: Quantitative measure of structural and geometric similarity of 3D morphologies. Complexity 16(6), 40–52 (2011)
Komosinski, M., Ulatowski, S.: Framsticks web site (2019). http://www.framsticks.com
Komosinski, M., Ulatowski, S.: Framsticks SDK (Software Development Kit). http://www.framsticks.com/sdk
Cox, T.F., Cox, M.A.A.: Multidimensional Scaling. Chapman and Hall/CRC, New York (2000)
Kuhn, H.W.: The hungarian method for the assignment problem. Nav. Res. Logist. Q. 2(1–2), 83–97 (1955)
Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Komosinski, M., Mensfelt, A. (2019). A Flexible Dissimilarity Measure for Active and Passive 3D Structures and Its Application in the Fitness–Distance Analysis. In: Kaufmann, P., Castillo, P. (eds) Applications of Evolutionary Computation. EvoApplications 2019. Lecture Notes in Computer Science(), vol 11454. Springer, Cham. https://doi.org/10.1007/978-3-030-16692-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-16692-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-16691-5
Online ISBN: 978-3-030-16692-2
eBook Packages: Computer ScienceComputer Science (R0)