On coevolutionary genetic algorithms

 The use of evolutionary computing techniques in coevolutionary/multi-agent systems is becoming increasingly popular. This paper presents simple models of the genetic algorithm in such systems, with the aim of examining the effects of different types of interdependence between individuals. Using the model it is shown that, for a fixed amount of interdependence between coevolving individuals, the existence of partner gene variance and the level at which fitness is applied can have significant effects, as does the evaluation partnering strategy used.     

A coevolutionary approach to adapt the genotype-phenotype map in genetic algorithms

This article introduces a coevolutionary approach to genetic algorithms (GAs) for exploring not only within a part of the solution space defined by the genotype-pheno-type map, but also the map itself. In canonical GAs with a fixed map, how large an area of the solution space can be covered by possible genomes, and consequently how better solutions can be found by a GA, rely on how well the geotype-phenotype map in designed, but it is difficult for designers of the algorithms to design the map without a priori knowledge of the solution space. In the proposed algorithm, the genotype-phenotype map is improved adaptively during the search process for solution candidates. It is applied to 3-bit deceptive problems such as of typical combinatorial optimazation problems. These are well known because their difficulty for GAs can be controlled by the genotype-phenotype map, and this shows a fairly good performance compared with a conventional GA. This work was presented in part at the Sixth International Symposium on Artificial Life and Robotics, Tokyo, January 15–17, 2001.     

A review of the current applications of genetic algorithms in assembly line balancing

Most of the problems involving the design and plan of manufacturing systems are combinatorial and NP-hard. A well-known manufacturing optimization problem is the assembly line balancing problem (ALBP). Due to the complexity of the problem, in recent years, a growing number of researchers have employed genetic algorithms. In this article, a survey has been conducted from the recent published literature on assembly line balancing including genetic algorithms. In particular, we have summarized the main specifications of the problems studied, the genetic algorithms suggested and the objective functions used in evaluating the performance of the genetic algorithms. Moreover, future research directions have been identified and are suggested.     

Traffic-aware stress testing of distributed real-time systems based on UML models using genetic algorithms

This paper presents a model-driven, stress test methodology aimed at increasing chances of discovering faults related to network traffic in distributed real-time systems (DRTS). The technique uses the UML 2.0 model of the distributed system under test, augmented with timing information, and is based on an analysis of the control flow in sequence diagrams. It yields stress test requirements that are made of specific control flow paths along with time values indicating when to trigger them. The technique considers different types of arrival patterns (e.g., periodic) for real-time events (common to DRTSs), and generates test requirements which comply with such timing constraints. Though different variants of our stress testing technique already exist (that stress different aspects of a distributed system), they share a large amount of common concepts and we therefore focus here on one variant that is designed to stress test the system at a time instant when data traffic on a network is maximal. Our technique uses genetic algorithms to find test requirements which lead to maximum possible traffic-aware stress in a system under test. Using a real-world DRTS specification, we design and implement a prototype DRTS and describe, for that particular system, how the stress test cases are derived and executed using our methodology. The stress test results indicate that the technique is significantly more effective at detecting network traffic-related faults when compared to test cases based on an operational profile.     

Leveraging saving-based algorithms by master-slave genetic algorithms

Saving-based algorithms are commonly used as inner mechanisms of efficient heuristic construction procedures. We present a general mechanism for enhancing the effectiveness of such heuristics based on a two-level genetic algorithm. The higher-level algorithm searches in the space of possible merge lists which are then used by the lower-level saving-based algorithm to build the solution. We describe the general framework and we illustrate its application to three hard combinatorial problems. Experimental results on three hard combinatorial optimization problems show that the approach is very effective and it enables considerable enhancement of the performance of saving-based algorithms.     

A multiagent-based complex systems approach for dynamic negotiation mechanism in virtual enterprise

Nowadays a sophisticated match-making mechanism is necessary for appropriate collaborations in virtual enterprise (VE). Virtual market based match-making operation enables effective partner search in terms of products allocation by distributing the scheduled resources according to the market prices, which define common scale of value across the various products. We formulate the VE match-making model as discrete resource allocation problem, and propose a complex market-oriented programming framework based on the economics of complex systems. Three types of heterogeneous agents are defined in the complex virtual market. It is described that their interactions with micro behaviour emerge a macro order of the virtual market, and the clearing price dynamism can be analysed in economic terms. The applicability of the framework into resource allocation problem for VE is also discussed.     

Order acceptance using genetic algorithms

This paper uses a genetic algorithm to solve the order-acceptance problem with tardiness penalties. We compare the performance of a myopic heuristic and a genetic algorithm, both of which do job acceptance and sequencing, using an upper bound based on an assignment relaxation. We conduct a pilot study, in which we determine the best settings for diversity operators (clone removal, mutation, immigration, population size) in connection with different types of local search. Using a probabilistic local search provides results that are almost as good as exhaustive local search, with much shorter processing times. Our main computational study shows that the genetic algorithm always dominates the myopic heuristic in terms of objective function, at the cost of increased processing time. We expect that our results will provide insights for the future application of genetic algorithms to scheduling problems.     

Machine-component grouping using genetic algorithms

One major problem in cellular manufacturing is the grouping of component parts with similar processing requirements into part families, and machines into manufacturing cells to facilitate the manufacturing of specific part families assigned to them. The objective is to minimize the total inter-cell and intra-cell movements of parts during the manufacturing process. In this paper, a mathematical model is presented to describe the characteristics of such a problem. An approach based on the concept of genetic algorithms is developed to determine the optimal machine-component groupings. Illustrative examples are used to demonstrate the efficiency of the proposed approach. Indeed, the results obtained show that the proposed genetic approach is a simple and efficient means for solving the machine-component grouping problem.     

Comparison of methods for developing dynamic reduced models for design optimization

In this paper we compare three methods for forming reduced models to speed up genetic-algorithm-based optimization. The methods work by forming functional approximations of the fitness function which are used to speed up the GA optimization by making the genetic operators more informed. Empirical results in several engineering design domains are presented.This research was funded in part by a sub-contract from the Rutgers-based Self Adaptive Software project supported by the Advanced Research Projects Agency of the Department of Defense and by NASA under grant NAG2-1234.     

An investigation of genetic algorithms for the optimization of multi-objective fisheries bioeconomic models

The use of genetic algorithms (GA) for optimization problems offers an alternative approach to the traditional solution methods. GA follow the concept of solution evolution, by stochastically developing generations of solution populations using a given fitness statistic, for example the achievement function in goal programs. They are particularly applicable to problems which are large, non-linear and possibly discrete in nature, features that traditionally add to the degree of complexity of solution. Owing to the probabilistic development of populations, GA do not distinguish solutions, e.g. local optima from other solutions, and therefore cannot guarantee optimality even though a global optimum may be reached. In this paper, a non-linear goal program of the North Sea demersal fisheries is used to develop a genetic algorithm for optimization. Comparisons between the GA approach and traditional solution methods are made, in order to measure the relative effectiveness. General observations of the use of GA in multi-objective fisheries bioeconomic models, and other similar models, are discussed.     

Efficient solutions for Mastermind using genetic algorithms

We present a new genetic algorithm for playing the game of Mastermind. The algorithm requires low run-times and results in a low expected number of guesses. Its performance is comparable to that of other meta-heuristics for the standard setting with four positions and six colors, while it outperforms the existing algorithms when more colors and positions are examined. The central idea underlying the algorithm is the creation of a large set of eligible guesses collected throughout the different generations of the genetic algorithm, the quality of each of which is subsequently determined based on a comparison with a selection of elements of the set.     

Evolving complex group behaviors using genetic programming with fitness switching

Genetic programming provides a useful tool for emergent computation and artificial life research. However, conventional genetic programming is not efficient enough to solve realistic multiagent tasks consisting of several emergent behaviors that need to be coordinated in the proper sequence. In this paper, we describe a novel method, called fitness switching, for evolving composite cooperative behaviors in multiple robotic agents using genetic programming. The method maintains a pool of basis fitness functions which are switched from simpler ones to more complex ones. The performance is demonstrated and evaluated in the context of a table transport problem. Experimental results show that the fitness switching method is an effective mechanism for evolving collective behaviors which can not be solved by simple genetic programming.     

区间适应值交互式遗传算法神经网络代理模型

为了解决交互式遗传算法的用户疲劳问题,提出区间适应值交互式遗传算法神经网络代理模型．首先,对用户已评价个体的基因型及其适应值进行采样以训练神经网络,使其逼近区间适应值的上下限;然后,利用神经网络代理模型,评价后续的部分进化个体,并不断更新训练数据和代理模型,以保证逼近精度;最后,对算法性能进行了定量分析,并将其应用于服装进化设计系统．分析结果表明,所提算法在减轻用户疲劳的前提下,具有更多找到满意解的机会．     

Design of coordination strategies in multiagent systems via genetic fuzzy systems

This paper suggests an evolutionary approach to design coordination strategies for multiagent systems. Emphasis is given to auction protocols since they are of utmost importance in many real world applications such as power markets. Power markets are one of the most relevant instances of multiagent systems and finding a profitable bidding strategy is a key issue to preserve system functioning and improve social welfare. Bidding strategies are modeled as fuzzy rule-based systems due to their modeling power, transparency, and ability to naturally handle imprecision in input data, an essential ingredient to a multiagent system act efficiently in practice. Specific genetic operators are suggested in this paper. Evolution of bidding strategies uncovers unknown and unexpected agent behaviors and allows a richer analysis of auction mechanisms and their role as a coordination protocol. Simulation experiments with a typical power market using actual thermal plants data show that the evolutionary, genetic-based design approach evolves strategies that enhance agents profitability when compared with the marginal cost-based strategies commonly adopted     

Applying genetic algorithms to zone design

Genetic algorithms (GA) have been found to provide global near optimal solutions in a wide range of complex problems. In this paper genetic algorithms have been used to deal with the complex problem of zone design. The zone design problem comprises a large number of geographical tasks, from which electoral districting is probably the most well known. The electoral districting problem is described and formalized mathematically. Different problem encodings, suited to GA optimization, are presented, together with different objective functions. A practical real world example is given and tests performed in order to evaluate the effectiveness of the GA approach.     

Optimization of fuzzy partitions for inductive reasoning using genetic algorithms

Fuzzy Inductive Reasoning (FIR) is a data-driven methodology that uses fuzzy and pattern recognition techniques to infer system models and to predict their future behavior. It is well known that variations on fuzzy partitions have a direct effect on the performance of the fuzzy-rule-based systems. The FIR methodology is not an exception. The performance of the model identification and prediction processes of FIR is highly influenced by the discretization parameters of the system variables, i.e. the number of classes of each variable and the membership functions that define its semantics. In this work, we design two new genetic fuzzy systems (GFSs) that improve this modeling and simulation technique. The main goal of the GFSs is to learn the fuzzification parameters of the FIR methodology. The new approaches are applied to two real modeling problems, the human central nervous system and an electrical distribution problem.     

Dynamic vehicle routing using genetic algorithms

Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic Vehicle Routing Problem (DVRP), new customer orders appear over time, and new routes must be reconfigured while executing the current solution. Montemanni et al. [1] considered a DVRP as an extension to the standard vehicle routing problem (VRP) by decomposing a DVRP as a sequence of static VRPs, and then solving them with an ant colony system (ACS) algorithm. This paper presents a genetic algorithm (GA) methodology for providing solutions for the DVRP model employed in [1]. The effectiveness of the proposed GA is evaluated using a set of benchmarks found in the literature. Compared with a tabu search approach implemented herein and the aforementioned ACS, the proposed GA methodology performs better in minimizing travel costs. Franklin T. Hanshar is currently a M.Sc. student in the Department of Computing and Information Science at the University of Guelph, Ontario, Canada. He received a B.Sc. degree in Computer Science from Brock University in 2005. His research interests include uncertain reasoning, optimization and evolutionary computation. Beatrice Ombuki-Berman is currently an Associate Professor in the Department of Computer Science at Brock University, Ontario, Canada. She obtained a PhD and ME in Information Engineering from University of The Ryukyus, Okinawa, Japan in 2001 and 1998, respectively. She received a B.Sc. in Mathematics and Computer Science from Jomo Kenyatta University, Nairobi, Kenya. Her primary research interest is evolutionary computation and applied optimization. Other research interests include neural networks, machine learning and ant colony optimization.     

Natural language tagging with genetic algorithms

This work analyzes the relative advantages of different metaheuristic approaches to the well-known natural language processing problem of part-of-speech tagging. This consists of assigning to each word of a text its disambiguated part-of-speech according to the context in which the word is used. We have applied a classic genetic algorithm (GA), a CHC algorithm, and a simulated annealing (SA). Different ways of encoding the solutions to the problem (integer and binary) have been studied, as well as the impact of using parallelism for each of the considered methods. We have performed experiments on different linguistic corpora and compared the results obtained against other popular approaches plus a classic dynamic programming algorithm. Our results claim for the high performances achieved by the parallel algorithms compared to the sequential ones, and state the singular advantages for every technique. Our algorithms and some of its components can be used to represent a new set of state-of-the-art procedures for complex tagging scenarios.     

Motion fairing using genetic algorithms

In this paper, we solve the motion smoothing problem using genetic algorithms. Smooth motion generation is essential in the computer animation and virtual reality area. The motion of a rigid body in general consists of translation and orientation. The former is described by a space curve in three-dimensional Euclidean space while the latter is represented by a curve in the unit quaternion space. By adopting the geometric approach, the smoothness of both translation data and orientation data is measured from the strain energy perspective and a nonlinear optimization problem is formulated that aims to minimize the weighted sum of the strain-energy and the sum of the squared errors. A hybrid algorithm that combines genetic algorithms and local search schemes is deployed to solve this optimization problem and the experiments show that both smoothness and shape preservation of the resulting motion can be achieved by the proposed algorithm.     

Adaptive reconfiguration of data networks using genetic algorithms

Genetic algorithms are applied to an important, but little investigated, network design problem, that of reconfiguring the topology and link capacities of an operational network to adapt to changes in its operating conditions. These conditions include: which nodes and links are unavailable; the traffic patterns; and the quality of service (QoS) requirements and priorities of different users and applications. Dynamic reconfiguration is possible in networks that contain links whose endpoints can be easily changed, such as satellite channels, terrestrial wireless connections, and certain types of optical connections. We report preliminary results that demonstrate the feasibility of performing genetic search quickly enough for online adaptation.