Studies in Computational Intelligence 521 Hiram Ponce-Espinosa Pedro Ponce-Cruz Arturo Molina Artificial Organic Networks Artificial Intelligence Based on Carbon Networks Studies in Computational Intelligence Volume 521 Series Editor J. Kacprzyk, Polish Academy of Sciences, Warsaw, Poland e-mail: [email protected] For furthervolumes: http://www.springer.com/series/7092 About the Series The series ‘‘Studies in Computational Intelligence’’ (SCI) publishes new devel- opmentsandadvancesinthevariousareasofcomputationalintelligence–quickly andwithahighquality.Theintentistocoverthetheory,applications,anddesign methods of computational intelligence, as embedded in the fields of engineering, computer science, physics and life sciences, as well as the methodologies behind them. The series contains monographs, lecture notes and edited volumes in computational intelligence spanning the areas of neural networks, connectionist systems, genetic algorithms, evolutionary computation, artificial intelligence, cellular automata, self-organizing systems, soft computing, fuzzy systems, and hybrid intelligent systems. Of particualr value to both the contributors and the readership are the short publication timeframe and the world-wide distribution, which enable both wide and rapid dissemination of research output. Special offer: For all clients with a print standing order we offer free access to the electronic volumes of the Series published in the current year. Indexed by DBLP, Ulrichs, SCOPUS, MathSciNet, Current Mathematical Publications, Mathematical Reviews, Zentralblatt Math: MetaPress and Springerlink. Hiram Ponce-Espinosa • Pedro Ponce-Cruz Arturo Molina • Artificial Organic Networks Artificial Intelligence Based on Carbon Networks 123 Hiram Ponce-Espinosa Pedro Ponce-Cruz ArturoMolina InstitutoTecnológico de Estudios Superiores deMonterrey Campus Ciudadde México Tlalpan Distrito Federal Mexico ISSN 1860-949X ISSN 1860-9503 (electronic) ISBN 978-3-319-02471-4 ISBN 978-3-319-02472-1 (eBook) DOI 10.1007/978-3-319-02472-1 SpringerChamHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2013950734 (cid:2)SpringerInternationalPublishingSwitzerland2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To Omar who makes me believe in the unbelievable To my parents and grandfather —Hiram Ponce-Espinosa To Norma, Pedro and Jamie who are always very close to my heart —Pedro Ponce-Cruz To my lovely family: Silvia, Julio and Monserrat —Arturo Molina Preface This book was written for undergraduate and graduate students as well as researchersandscientistsinterestedinartificialintelligencetechniques.Infact,the intention of this book is to introduce and fully describe the artificial organic networkstechnique,anovelmachinelearningmethodinspiredonchemicalcarbon networks. In addition, an organic network-based algorithm named artificial hydrocarbon networks is presented to show the advantages and the scope of the technique. On one hand, the book is complemented with several examples through chaptersandthedescriptionofreal-worldapplicationsusingartificialhydrocarbon networks. On the other hand, the text is accompanied with an artificial organic networkstoolkitimplementedonLabVIEWTMallowingahands-on experienceto readers. Theorganizationofthebookisasfollows:Chapter 1introducesanoverviewof machinelearningandthemodelingproblemwhileChap. 2describeskeyconcepts oforganicchemistryinordertounderstandthetechnique,Chaps. 3and4describe the artificial organic networks technique and the artificial hydrocarbon networks algorithm. Then, Chap. 5 offers some improvements to the basic artificial hydro- carbon networks algorithm. Finally, Chaps. 6 and 7 provide experimental results and discuss how to implement the algorithm in real-world applications like audio filtering, control systems and facial recognition. Finally, we would like to express our gratitude to all those who provided supportandrevieweddetailsoverandover,thosewhoreadandofferedcomments allowed us to quote their remarks, and those who assisted us in the editing, proofreadinganddesigningstages.AspecialacknowledgementtotheTecnologico de Monterrey. Mexico City, Mexico, August 2013 Hiram Ponce-Espinosa Pedro Ponce-Cruz Arturo Molina vii Contents 1 Introduction to Modeling Problems . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 The Modeling Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Review of Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Learning Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Classification Algorithms. . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Nature-Inspired Computing. . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Metaheuristic Algorithms. . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.3 Biologically Inspired Algorithms . . . . . . . . . . . . . . . . . 9 1.3.4 Chemically Inspired Algorithms . . . . . . . . . . . . . . . . . . 14 1.4 Comparison of Algorithms for Modeling Problems . . . . . . . . . . 17 1.4.1 Complexity and Stability in Modeling Problems. . . . . . . 17 1.4.2 Artificial Organic Networks and Modeling Problems. . . . 20 1.5 Motivation of Artificial Organic Networks. . . . . . . . . . . . . . . . 24 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2 Chemical Organic Compounds. . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.1 The Importance of Organic Chemistry. . . . . . . . . . . . . . . . . . . 32 2.2 Basic Concepts of Organic Compounds . . . . . . . . . . . . . . . . . . 33 2.2.1 Structural Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.2 Chemical Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3 Covalent Bonding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3.1 Characterization of Covalent Bonds . . . . . . . . . . . . . . . 40 2.4 Energy in Organic Compounds. . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.1 Energy Level Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.2 Measures of Energy . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5 Classification of Organic Compounds . . . . . . . . . . . . . . . . . . . 45 2.5.1 Hydrocarbons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.5.2 Alcohols, Ethers, and Thiols. . . . . . . . . . . . . . . . . . . . . 46 2.5.3 Amines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.5.4 Aldehydes, Ketones, and Carboxylic Acids . . . . . . . . . . 47 2.5.5 Polymers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.5.6 Carbohydrates, Lipids, Amino Acids, and Proteins . . . . . 48 2.5.7 Nucleic Acids. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 ix x Contents 2.6 Organic Compounds as Inspiration . . . . . . . . . . . . . . . . . . . . . 49 2.6.1 Motivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.6.2 Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 Artificial Organic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1 Overview of Artificial Organic Networks. . . . . . . . . . . . . . . . . 53 3.1.1 The Metaphor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Artificial Organic Compounds. . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.1 Components. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.2 Interactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3 Networks of Artificial Organic Compounds . . . . . . . . . . . . . . . 66 3.3.1 The Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.3.2 The Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.3.3 Mixtures of Compounds. . . . . . . . . . . . . . . . . . . . . . . . 66 3.4 The Technique of Artificial Organic Networks . . . . . . . . . . . . . 67 3.4.1 Levels of Energy in Components . . . . . . . . . . . . . . . . . 67 3.4.2 Formal Definition of Artificial Organic Networks. . . . . . 68 3.4.3 Model of Artificial Organic Networks. . . . . . . . . . . . . . 69 3.5 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.5.1 The Search Topological Parameters Problem . . . . . . . . . 70 3.5.2 The Build Topological Structure Problem . . . . . . . . . . . 71 3.5.3 Artificial Organic Networks-Based Algorithms. . . . . . . . 72 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4 Artificial Hydrocarbon Networks . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1 Introduction to Artificial Hydrocarbon Networks. . . . . . . . . . . . 73 4.1.1 Chemical Inspiration. . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1.2 Objectives and Scope . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2 Basics of Artificial Hydrocarbon Networks. . . . . . . . . . . . . . . . 75 4.2.1 Components. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.2 Interactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.3 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.2.4 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . 101 4.3 Metrics of Artificial Hydrocarbon Networks. . . . . . . . . . . . . . . 102 4.3.1 Computational Complexity. . . . . . . . . . . . . . . . . . . . . . 102 4.3.2 Stability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.4 Artificial Hydrocarbon Networks Practical Features. . . . . . . . . . 108 4.4.1 Partial Knowledge Representation. . . . . . . . . . . . . . . . . 108 4.4.2 Practical Issues in Partial Knowledge Extraction. . . . . . . 110 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Contents xi 5 Enhancements of Artificial Hydrocarbon Networks. . . . . . . . . . . . 113 5.1 Optimization of the Number of Molecules . . . . . . . . . . . . . . . . 113 5.1.1 The Hess’ Law. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.1.2 Boiling and Melting Points in Hydrocarbons . . . . . . . . . 114 5.1.3 Enthalpy in Artificial Hydrocarbon Networks. . . . . . . . . 115 5.2 Extension to the Multidimensional Case. . . . . . . . . . . . . . . . . . 119 5.2.1 Components and Interactions . . . . . . . . . . . . . . . . . . . . 120 5.2.2 Multidimensional AHN-Algorithm . . . . . . . . . . . . . . . . 124 5.3 Recursive Networks Using Aromatic Compounds . . . . . . . . . . . 127 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6 Notes on Modeling Problems Using Artificial Hydrocarbon Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.1 Approximation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.1.1 Approximation of Univariate Functions. . . . . . . . . . . . . 132 6.1.2 Approximation of Multivariate Functions. . . . . . . . . . . . 137 6.2 Clustering Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.2.1 Linear Classifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.2.2 Nonlinear Classifiers. . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.3 Guidelines for Real-World Applications. . . . . . . . . . . . . . . . . . 149 6.3.1 Inheritance of Information . . . . . . . . . . . . . . . . . . . . . . 150 6.3.2 Catalog Based on Artificial Compounds . . . . . . . . . . . . 152 6.3.3 Using Metadata. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 7 Applications of Artificial Hydrocarbon Networks . . . . . . . . . . . . . 155 7.1 Filtering Process in Audio Signals. . . . . . . . . . . . . . . . . . . . . . 155 7.1.1 Background and Problem Statement . . . . . . . . . . . . . . . 156 7.1.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 7.1.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . 159 7.2 Position Control of DC Motor Using AHN-Fuzzy Inference Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 7.2.1 Background and Problem Statement . . . . . . . . . . . . . . . 166 7.2.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 7.2.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . 177 7.3 Facial Recognition Based on Signal Identification Using AHNs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 7.3.1 Background and Problem Statement . . . . . . . . . . . . . . . 183 7.3.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.3.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . 187 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189