Catálogo de publicaciones - libros

In this paper we introduce a new fuzzy evaluation function for examination timetabling. We describe how we employed fuzzy reasoning to evaluate the quality of a constructed timetable by considering two criteria: the average penalty per student and the highest penalty imposed on any of the students. A fuzzy system was created based on a series of easy to understand rules to combine the two criteria. A significant problem encountered was how to determine the lower and upper bounds of the decision criteria for any given problem instance, in order to allow the fuzzy system to be fixed and, hence, applicable to new problems without alteration. In this work, two different methods for determining boundary settings are proposed. Experimental results are presented and the implications analysed. These results demonstrate that fuzzy reasoning can be successfully applied to evaluate the quality of timetable solutions in which multiple decision criteria are involved.

An important application for population search methods (such as particle swarm optimization and the several varieties of synthetic evolution) is the engineering problem of configuring individual agents to yield useful emergent behavior. While the biological antecedents of population-based search operate in real time, most engineered versions run off-line. For some applications, it is desirable to evolve agents as they are running in the system that they support. We describe two instances of such systems that we have developed and highlight lessons learned.

This chapter describes how genetic programming was used as an invention machine to automatically synthesize a complete design for an aspherical optical lens system (a type of lens system that is especially difficult to design and that offers advantages in terms of cost, weight, size, and performance over traditional spherical systems). The genetically evolved aspherical lens system duplicated the functionality of a recently patented aspherical system. The automatic synthesis was open-ended — that is, the process did not start from a pre-existing good design and did not pre-specify the number of lenses, which lenses (if any) should be spherical or aspherical, the topological arrangement of the lenses, the numerical parameters of the lenses, or the non-numerical parameters of the lenses. The genetically evolved design is an instance of human-competitive results produced by genetic programming in the field of optical design.

We used Linear Genetic Programming (LGP) to study the extent to which automated learning techniques may be used to improve Unexploded Ordinance (UXO) discrimination from Protem-47 and Geonics EM61 non-invasive electromagnetic sensors. We conclude that: (1) Even after geophysicists have analyzed the EM61 signals and ranked anomalies in order of the likelihood that each comprises UXO, our LGP tool was able to substantially improve the discrimination of UXO from scrap—preexisting techniques require digging 62% more holes to locate all UXO on a range than do LGP derived models; (2) LGP can improve discrimination even though trained on a very small number of examples of UXO; and (3) LGP can improve UXO discrimination on data sets that contain a high-level of noise and little preprocessing.

One of the challenges in engineering design is adapting a set of created designs to a change in requirements. Previously we presented two four-arm, symmetric, evolved antennas for NASA’s Space Technology 5 mission. However, the mission’s orbital vehicle was changed, putting it into a much lower earth orbit, changing the specifications for the mission. With minimal changes to our evolutionary system, mostly in the fitness function, we were able to evolve antennas for the new mission requirements and, within one month of this change, two new antennas were designed and prototyped. Both antennas were tested and both had acceptable performance compared with the new specifications. This rapid response shows that evolutionary design processes are able to accommodate new requirements quickly and with minimal human effort.

This chapter gives an overview, based on the experience from the Dow Chemical Company, of the importance of variable selection to build robust models from industrial datasets. A quick review of variable selection schemes based on linear techniques is given. A relatively simple fitness inheritance scheme is proposed to do nonlinear sensitivity analysis that is especially effective when combined with Pareto GP. The method is applied to two industrial datasets with good results.

We demonstrate a functional style recursion implementation to evolve recursive programs. This approach re-expresses a recursive program using a non-recursive application of a higher-order function. It divides a program recursion pattern into two parts: the recursion code and the application of the code. With the higher-order functions handling recursion code application, GP effort becomes focused on the generation of recursion code. We employed this method to evolve two recursive programs: a C library function, and programs that produce the Fibonacci sequence. In both cases, the program space defined by higher-order functions are much easier for GP to search and to find a solution. We have learned about higher-order function selection and fitness assignment through this study. The next step will be to test the approach on applications with open-ended solutions, such as evolutionary design.

Geographical distribution is widely held to be a major determinant of evolutionary dynamics. Correspondingly, genetic programming theorists and practitioners have long developed, used, and studied systems in which populations are structured in quasi-geographical ways. Here we show that a remarkably simple version of this idea produces surprisingly dramatic improvements in problem-solving performance on a suite of test problems. The scheme is trivial to implement, in some cases involving little more than the addition of a modulus operation in the population access function, and yet it provides significant benefits on all of our test problems (ten symbolic regression problems and a quantum computing problem). We recommend the broader adoption of this form of “trivial geography” in genetic programming systems.

Backward chaining evolutionary algorithms (BC-EA) offer the prospect of run-time efficiency savings by reducing the number of fitness evaluations without significantly changing the course of genetic algorithm or genetic programming runs. “Tournament selection, iterated coupon-collection problem, and backward-chaining evolutionary algorithm,” Poli, , 2005 describes how BC-EA does this by avoiding the generation and evaluation of individuals which never appear in selection tournaments. It suggests the largest savings occur in very large populations, short runs, small tournament sizes and shows actual savings in fixed-length binary GAS. Here, we provide a generational GP implementation, including mutation and two offspring crossover of BC-EA and empirically investigate its efficiency in terms of both fitness evaluations and effectiveness.

This chapter examines the notion of co-evolving grammars with a population of individuals. This idea has great promise because it is possible to dynamically reshape the solution space while evolving individuals. We compare such a system with a more standard system with fixed grammars and demonstrate that, on a selection of benchmark problems, the standard approach appears to be better. Several different context free grammars, including one inspired by Koza’s GPPS system are examined, and a number of surprising results appear, which indicate that several representative GP benchmark problems are best tackled by a standard GP approach.