Fundamenta Informaticae - Volume 35, issue 1-4

Authors: Eiben, A.E. | Michalewicz, Zbigniew

Article Type: Other

DOI: 10.3233/FI-1998-35123415

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. v-vii, 1998

Authors: Fogel, David B.

Article Type: Research Article

Abstract: All of science relies on past experimentation and hypotheses. Unfortunately, the science of evolutionary computation is hampered by a general lack of awareness of many early efforts in the field. This paper offers a review of one such contribution from 1967 which employed self-adaptation, co-evolution, and assessed the utility of recombination in various settings. The conclusions, reconfirmed in recent literature, indicate that recombination (uniform or one-point crossover) is best applied in non-epistatic settings. Theoretical analysis supported the experimental findings and now raises questions concerning common applications of schema theory to describe the behavior of evolutionary algorithms.

Keywords: evolutionary algorithms, history of evolutionary computation

DOI: 10.3233/FI-1998-35123401

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 1-16, 1998

Authors: Esquivel, Susana C. | Leiva, Héctor Ariel | Gallardt, Raúl H.

Article Type: Research Article

Abstract: The selection operator is one of the main operators in evolutionary algorithms. It interacts with other operators (e.g., crossover, mutation) in a complex way. Consequently, the effects of selection should be considered also together with these operators. This paper provides an overview of several presently used selection operators and discusses a new selection operator specifically devised to assist MCPC, an exploitation-oriented multiple crossover per couple approach, to overcome premature convergence. Some experimental results are also provided.

Keywords: selection methods, interaction of operators, couple selection

DOI: 10.3233/FI-1998-35123402

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 17-33, 1998

Authors: Eiben, A.E. | Schippers, C.A.

Article Type: Research Article

Abstract: Exploration and exploitation are the two cornerstones of problem solving by search. The common opinion about evolutionary algorithms is that they explore the search space by the (genetic) search operators, while exploitation is done by selection. This opinion is, however, questionable. In this paper we give a survey of different operators, review existing viewpoints on exploration and exploitation, and point out some discrepancies between and problems with current views.

DOI: 10.3233/FI-1998-35123403

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 35-50, 1998

Authors: Bäck, Thomas

Article Type: Research Article

Abstract: The principle of self-adaptation in evolutionary algorithms is an important mechanism for controlling the strategy parameters of such algorithms by evolving parameter values in analogy with the usual evolution of object variables. To facilitate evolution of strategy parameters, they are incorporated into the representation of individuals and are subject to the evolutionary variation operators in a similar way as the object variables. This survey paper provides an overview of the existing techniques for the self-adaptation of strategy parameters related to mutation and recombination operators, indicating that the principle works under a variety of conditions regarding the search space of the …underlying optimization problem and the method used for the variation of strategy parameters. Although a number of open questions remain, self-adaptation is identified as a generally applicable, robust and efficient method for parameter control in evolutionary algorithms. Show more

DOI: 10.3233/FI-1998-35123404

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 51-66, 1998

Authors: Rudolph, Günter

Article Type: Research Article

Abstract: The theory of evolutionary computation has been enhanced rapidly during the last decade. This survey is the attempt to summarize the results regarding the limit and finite time behavior of evolutionary algorithms with finite search spaces and discrete time scale. Results on evolutionary algorithms beyond finite space and discrete time are also presented but with reduced elaboration.

Keywords: evolutionary algorithms, limit behavior, finite time behavior

DOI: 10.3233/FI-1998-35123405

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 67-89, 1998

Authors: Murthy, C.A. | Bhandari, Dinabandhu | Pal, Sankar K.

Article Type: Research Article

Abstract: In this article, the concept of e-optimal stopping time of a genetic algorithm with elitist model (EGA) has been introduced. The probability of performing mutation plays an important role in the computation of the ε-optimal stopping times. Two approaches, namely, pessimistic and optimistic have been considered here to find out the ε-optimal stopping time. It has been found that the total number of strings to be searched in the optimistic approach to obtain ε-optimal string is less than the number of all possible strings for sufficiently large string length. This observation validates the use of genetic algorithms in solving complex …optimization problems. Show more

DOI: 10.3233/FI-1998-35123406

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 91-111, 1998

Authors: Khouja, Moutaz | Michalewicz, Zbigniew | Vijayaragavan, Poorani

Article Type: Research Article

Abstract: The economic lot and delivery scheduling problem (ELDSP) involves a supply chain consisting of a supplier and an assembly facility, where direct shipments are made from one to the other. The supplier produces multiple components on a single machine or a production line. The assembly facility uses these components at a constant rate. The supplier incurs a sequence-independent setup cost and setup time each time the production line is changed over from one component to another. On the other hand, setup costs and times for the assembly facility are negligible. There is also a fixed charge for each delivery. The …problem is to find a “just-in-time” schedule in which one production run of each component and a subsequent delivery of these components to the assembly facility occur in each cycle. The objective is to find the best sequence and cycle duration that minimizes the average cost per unit time of transportation, inventory at both the supplier and the assembly facility, and setup costs at the supplier. In this paper we investigate the usefulness of an evolutionary algorithm for solving this economic lot and delivery scheduling problem. Show more

Keywords: heuristic search, evolutionary algorithms, scheduling, economic lot scheduling and delivery

DOI: 10.3233/FI-1998-35123407

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 113-123, 1998

Authors: Sebag, Michèle | Schoenauer, Marc | Peyral, Mathieu

Article Type: Research Article

Abstract: A new evolution scheme is presented, memorizing the extreme (best and worst) past individuals through distributions over the binary search space. These distributions are used to bias the mutation operator in a (μ + λ) Evolution Strategy, guiding the generation of newborn offspring: different mimetic strategies are defined, combining either attraction, indifference or repulsion with respect to the two distributions. These distributions are then updated from the best and the worse individuals in the current population. Experiments on large size binary problems allow one to delineate the niche of each of these mimetic strategies.

DOI: 10.3233/FI-1998-35123408

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 125-162, 1998

Authors: Giordana, A. | Lo Bello, G.

Article Type: Research Article

Abstract: Genetic Algorithms have been proposed by many authors for Machine Learning tasks. In fact, they are appealing for several different reasons, such as the flexibility, the great exploration power, and the possibility of exploiting parallel processing. Nevertheless, it is still controversial whether the genetic approach can really provide effective solutions to learning tasks, in comparison to other algorithms based on classical search strategies. In this paper we try to clarify this point and we overview the work done with respect to the task of learning classification programs from examples. The state of the art emerging from our analysis suggests that …the genetic approach can be a valuable alternative to classical approaches, even if further investigation is necessary in order to come to a final conclusion. Show more

Keywords: Machine learning, Concept learning, Genetic Algorithms

DOI: 10.3233/FI-1998-35123409

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 163-177, 1998

Authors: Angeline, Peter J.

Article Type: Research Article

Abstract: Genetic programming (Koza 1992) is a method of inducing behaviors represented as executable programs. The generality of the approach has spawned a proliferation of work in the evolution of executable structures that is unmatched in the history of the subject. This paper describes the standard approach to genetic programming, as denned in Koza (1992), and then presents the significant studies that preceded its inception as well as the diversification of techniques evolving executable structures that is currently underway in the field.

DOI: 10.3233/FI-1998-35123410

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 179-195, 1998

Authors: Boryczka, Mariusz

Article Type: Research Article

Abstract: We describe the ant systems and the application of the generative policies improving the performance of the ant systems in the context of the Travelling Salesman Problem. The generative policies are derived from the studies carried out in Germany and USA in the sixties. We study the leader (superman) and élite strategies, which have been chosen because of their analogy to the world of real ants. First, we describe three ant algorithms and we introduce a formal description of the ant system. Then we discuss the reflection of the evolutionary computing in the ant systems.

Keywords: ant systems, Travelling Salesman Problem, NP-complete problems, generative policies

DOI: 10.3233/FI-1998-35123411

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 197-209, 1998

Authors: Seredyński, Franciszek

Article Type: Research Article

Abstract: The paper overviews existing models and new tendencies observed in the current literature concerning parallel and distributed evolutionary computation. Sources of parallelism, ways of exploring it and forms of a distributed control of execution of parallel evolutionary algorithms are discussed. Some taxonomy of parallel and distributed computation is proposed. The most known or promising computational schemes are overviewed.

Keywords: evolutionary computation models, distributed algorithms, parallel algorithms, sources of parallelism, taxonomy

DOI: 10.3233/FI-1998-35123412

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 211-230, 1998

Authors: Deaton, Russell | Garzon, Max | Rose, John | Franceschetti, D.R. | Stevens, S.E.

Article Type: Research Article

Abstract: DNA computing holds out the promise of important and significant connections between computers and living systems, as well as promising massively parallel computations. Before these promises are fulfilled, however, important challenges related to errors and practicality have to be addressed. On the other hand, new directions toward a synthesis of molecular evolution and DNA computing might circumvent the problems that have hindered development, so far.

DOI: 10.3233/FI-1998-35123413

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 231-245, 1998

Authors: De Jong, Kenneth

Article Type: Research Article

Abstract: Although more than 30 years old, the field of evolutionary computation has experienced a significant growth of interest and activity in the past few years. This has resulted in fresh perspectives and a flurry of new results in both theory and applications. This paper will attempt to summarize the current state of the field and suggest promising new directions.

Keywords: Evolutionary Computation, Evolutionary Algorithms, Genetic Algorithms

DOI: 10.3233/FI-1998-35123414

Citation: Fundamenta Informaticae, vol. 35, no. 1-4, pp. 247-259, 1998