In situ Distributed Genetic Programming: An Online Learning Framework for Resource Constrained Networked Devices

Valencia, Philip (2016). In situ Distributed Genetic Programming: An Online Learning Framework for Resource Constrained Networked Devices PhD Thesis, School of Information Technology and Electrical Engineering, The University of Queensland. doi:10.14264/uql.2016.295

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s4109212_final_thesis.pdf Thesis full text application/pdf 8.55MB 0

Author Valencia, Philip
Thesis Title In situ Distributed Genetic Programming: An Online Learning Framework for Resource Constrained Networked Devices
School, Centre or Institute School of Information Technology and Electrical Engineering
Institution The University of Queensland
DOI 10.14264/uql.2016.295
Publication date 2016-05-20
Thesis type PhD Thesis
Open Access Status DOI
Supervisor Peter Lindsay
Raja Jurdak
Total pages 270
Total colour pages 125
Total black and white pages 145
Language eng
Subjects 0801 Artificial Intelligence and Image Processing
Abstract/Summary This research presents In situ Distributed Genetic Programming (IDGP) as a framework for distributively evolving logic while attempting to maintain acceptable average performance on highly resource-constrained embedded networked devices. The framework is motivated by the proliferation of devices employing microcontrollers with communications capability and the absence of online learning approaches that can evolve programs for them. Swarm robotics, Internet of Things (IoT) devices including smart phones, and arguably the most constrained of the embedded systems, Wireless Sensor Networks (WSN) motes, all possess the capabilities necessary for the distributed evolution of logic - specifically the abilities of sensing, computing, actuation and communications. Genetic programming (GP) is a mechanism that can evolve logic for these devices using their “native” logic representation (i.e. programs) and so technically GP could evolve any behaviour that can be coded on the device. IDGP is designed, implemented, demonstrated and analysed as a framework for evolving logic via genetic programming on highly resource-constrained networked devices in real-world environments while achieving acceptable average performance. Designed with highly resource-constrained devices in mind, IDGP provides a guide for those wishing to implement genetic programming on such systems. Furthermore, an implementation on mote class devices is demonstrated to evolve logic for a time-varying sense-compute-act problem and another problem requiring the evolution of primitive communications. Distributed evolution of logic is also achieved by employing the Island Model architecture, and a comparison of individual and distributed evolution (with the same and slightly different goals) presented. This demonstrates the advantage of leveraging the fact that such devices often reside within networks of devices experiencing similar conditions. Since GP is a population-based metaheuristic which relies on the diversity of the population to achieve learning, many, if not most, programs within the population exhibit poor performance. As such, the average observed performance (pool fitness) of the population using the standard GP learning mechanism is unlikely to be acceptable for online learning scenarios. This is suspected to be the reason why no previous attempts have been made to deploy standard GP as an online learning approach. Nonetheless, the benefits of GP for evolving logic on such devices are compelling and motivated the design of a novel satisficing heuristic called Fitness Importance (FI). FI is population-based heuristic used to bias the evaluation of candidate solutions such that an “acceptable” average fitness (AAF) is achieved while also achieving ongoing, though diminished, learning capacity. This trade off motivated further investigation into whether dynamically adjusting the average performance in response to AAF would be superior to a constant, balanced, performing-learning approach. Dynamic and constant strategies were compared on a simple problem where the AAF target was changed during evolution, revealing that dynamically tracking the AAF target can yield a higher success rate in meeting the AAF. The combination of IDGP and FI offers a novel approach for achieving online learning with GP on highly resource-constrained embedded systems. Furthermore, it simultaneously considers the acceptable average performance of the system which may change during the operational lifetime. This approach could be applied to swarm and cooperative robot systems, WSN motes or IoT devices allowing them to cooperatively learn and adapt their logic locally to meet dynamic performance requirements.
Keyword Genetic Programming
Embedded Systems
Internet of Things
Machine learning
Exploration and exploitation
Online Learning

Document type: Thesis
Collections: UQ Theses (RHD) - Official
UQ Theses (RHD) - Open Access
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Sun, 08 May 2016, 21:33:13 EST by Mr Philip Valencia on behalf of Learning and Research Services (UQ Library)