Smart-appliance ensembles consist of intelligent devices that interact with each other and that are supposed to support their users in an autonomous, non-invasive way. Since both the number and the composition of the participating devices may spontaneously change at any time without any notice, traditional approaches, such as rule-based systems and evolutionary algorithms, are not appropriate mechanisms for their self-organization. Therefore, this chapter describes a new evolutionary framework, called appliancesgo- evolution platform (AGE-P) that accounts for the inherent system dynamics by distributing all data structures and all operations across all participating devices. This chapter illustrates the behavior of this framework by presenting several results obtained from simulations as well as real-world case studies.
TopIntroduction
Evolutionary algorithms of various sorts solve technical problems by utilizing some selected concepts from natural evolution (Back et al., 1997; Fogel, 1995; Goldberg, 1989; Rechenberg, 1994; Schwefel, 1995). They describe a technical (optimization) problem as a set of n problem-specific parameters xi, also called genes. The set of genes is called a genome and is tightly embedded into an object, called an individual. Typically, an evolutionary algorithm applies its random variation operators, such as mutation and recombination, to an individual’s genes. As a consequence, these random variations change the individual’s fitness values. A subsequent selection process exploits these fitness variations in order to gain some progress. It should be obvious that both the fitness evaluation and the selection process consider the genomes as atomic entities. In summary, the notion of an individual as the container of its genome is a very fundamental concept in all evolutionary algorithms.
The concepts described above are quite generic by their very nature. The pertinent literature on evolutionary algorithms presents a huge number of successful applications that can be found in areas as diverse as machine learning, combinatorial problems, VLSI design, breast cancer detection, evolutionary robotics, and numerical optimization in general. However, in its canonical form, the concept of an individual is not suitable for all types of applications. For example, when evolving structures, such as the topology of a neural network, the number n of parameters xi is generally not known in advance. Rather, the number n of parameters itself is the result of the actual evolutionary process. As a relief, previous research has developed the concept of variable-length genomes (Lee & Antonsson, 2000; Ramsey et al., 1998; Schiffmann et al., 1993). This option allows an individual to grow and shrink its genome, and thus to adapt to changing demands. But still, with its genome, an individual constitutes a solid, atomic, and monolithic entity, which is fundamental to all evolutionary algorithms.
Even with the concept of variable-length genomes, evolutionary algorithms cannot be directly utilized in all application domains. Section 2 briefly describes an example of smart-appliance ensembles (Aarts, 2004; Saha & Mukherjee, 2003; Weiser, 1993). The term “smart-appliance ensemble” refers to everyday-life devices that are equipped with some computational resources and that are supposed to self-organize according to the users’ needs. The following properties are closely linked to smart-appliance ensembles: (1) they are dynamic by their very nature in that devices may join or leave the ensemble at any time without notice; (2) the physical properties of every device are known only to itself and not to the rest of the system; and (3) a smart-appliance ensemble should not induce any user-based modeling and/or administration; rather, devices might be freely added and be freely removed, which also includes device failures.
The discussion presented above suggests that the conventional usage of individuals and genes does not match the dynamic and model-free nature of smart-appliance ensembles. Therefore, Section 3 proposes a new evolutionary framework, called the appliances-go-evolution platform (AGE-P). A key feature of AGE-P is that it physically distributes the genome as well as the variation operators across all the appliances. This way, the genome grows and shrinks as devices come and go, and thus is naturally adapting to an ensemble’s dynamics. It should be mentioned, that the idea of distributed evolution is not new. For a good overview, the interested reader is referred to the literature (Alba & Tomassini, 2002; Cahon et al., 2004). In order to gain performance, these methods work on several subpopulations simultaneously, but nonetheless handle genomes in the form of assembled individuals. In contrast, AGE-P abolishes the concept of assembled individuals, not to gain performance, but to ensure consistency.