EuroGP2001 18-20 April 2001
Lake Como (Milan), Italy
home | post conference information | papers | EvoWorkshops | committees   


 

EvoWorkshops
2001

EvoCOP
EvoFLIGHT
EvoIASP
EvoLEARN
EvoSTIM



     

EvoCOP abstracts

  1. T. Gaube, F. Rothlauf:
    The Link and Node Biased Encoding Revisited: Bias and Adjustment of Parameters

    When using genetic and evolutionary algorithms (GEAs) for the optimal communication spanning tree problem, the design of a suitable tree network encoding is crucial for finding good solutions. The link and node biased (LNB) encoding represents the structure of a tree network using a weighted vector and allows the GEA to distinguish between the importance of the nodes and links in the network. This paper investigates whether the encoding is unbiased in the sense that all trees are equally represented, and how the parameters of the encoding influence the bias. If the optimal solution is underrepresented in the population, a reduction in the GEA performance is unavoidable. The investigation reveals that the commonly used simpler version of the encoding is biased towards star networks, and that the initial population is dominated by only a few individuals. The more costly link-and-node-biased encoding uses not only a node-specific bias, but also a link-specific bias. Similarly to the node-biased encoding, the link-and-node-biased encoding is also biased towards star networks, especially when using a low weighting for the link-specific bias. The results show that by increasing the link-specific bias, that the overall bias of the encoding is reduced. If researchers want to use the LNB encoding, and they are interested in having an unbiased representation, they should use higher values for the weight of the link-specific bias. Nevertheless, they should also be aware of the limitations of the LNB encoding when using it for encoding tree problems. The encoding could be a good choice for the optimal communication spanning tree problem as the optimal solutions tend to be more star-like. However, for general tree problems the encoding should be used carefully.

  2. Y. Li:
    An Effective Implementation of a Direct Spanning Tree Representation in GAs

    This paper presents an effective implementation based on predecessor vectors of a genetic algorithm using a direct tree representation. The main operations associated with crossovers and mutations can be achieved in O(d) time, where d is the length of a path. Our approach can avoid usual drawbacks of the fixed linear representations, and provide a framework facilitating the incorporation of problem-specific knowledge into initialization and operators for constrained minimum spanning tree problems.

  3. I. Ljubic, G. R. Raidl:
    An Evolutionary Algorithm with Stochastic Hill-Climbing for the Edge-Biconnectivity Augmentation Problem

    Augmenting an existing network with additional links to achieve higher robustness and survivability plays an important role in network design. We consider the problem of augmenting a network with links of minimum total cost in order to make it edge-biconnected, i.e. the failure of a single link will never disconnect any two nodes. A new evolutionary algorithm is proposed that works directly on the set of additional links of a candidate solution. Problem-specific initialization, recombination, and mutation operators use a stochastic hill-climbing procedure. With low computational effort, only locally optimal, feasible candidate solutions are produced. Experimental results are significantly better than those of a previous genetic algorithm concerning final solutions' qualities and especially execution times.

  4. P. Chardaire, G. P. McKeown, J. A. Maki:
    Application of GRASP to the Multiconstraint Knapsack Problem

    A number of approaches based on GRASP are presented for the Multiconstraint Knapsack Problem. GRASP combines greedy construction of feasible solutions with local search. Results from applying our algorithms to standard test problems are presented and compared with results obtained by Chu and Beasley.

  5. J. Levenhagen, A. Bortfeldt, H. Gehring:
    Path Tracing in Genetic Algorithms Applied to the Multiconstrained Knapsack Problem

    This contribution investigates the usefulness of F. Glover's path tracing concept within a Genetic Algorithm context for the solution of the multiconstrained knapsack problem (MKP). A state of the art GA is therefore extended by a path tracing component and the Chu/Beasley MKP benchmark problems are used for numerical tests.

  6. J. Gottlieb:
    On the Feasibility Problem of Penalty-Based Evolutionary Algorithms for Knapsack Problems

    Constrained optimization problems can be tackled by evolutionary algorithms using penalty functions to guide the search towards feasibility. The core of such approaches is the design of adequate penalty functions. All authors, who designed penalties for knapsack problems, recognized the feasibility problem, i.e. the final population contains unfeasible solutions only. In contrast to previous work, this paper explains the origin of the feasibility problem. Using the concept of fitness segments, a computationally easy analysis of the fitness landscape is suggested. We investigate the effects of the initialization routine, and derive guidelines that ensure resolving the feasibility problem. A new penalty function is proposed that reliably leads to a final population containing feasible solutions, independently of the initialization method employed.

  7. R. Cordone, F. Maffioli:
    Coloured Ant System and Local Search to Design Local Telecommunication Networks

    This work combines local search with a variant of the Ant System recently proposed for partitioning problems with cardinality constraints. The Coloured Ant System replaces the classical concept of trail with p trails of different ``colours'', representing the assignment of an element to one of the classes in the partition. We apply the method with promising results to the design of local telecommunication networks. The combination of the Coloured Ant System with local search yields much better results than the two approaches alone.

  8. K. Doerner, R. F. Hartl, M. Reimann:
    Cooperative Ant Colonies for Optimizing Resource Allocation in Transportation

    In this paper we propose an ACO approach, where two colonies of ants aim to optimize total costs in a transportation network. This main objective consists of two sub goals, namely fleet size minimization and minimization of the vehicle movement costs, which are conflicting for some regions of the solution space. Thus, our two ant colonies optimize one of these sub-goals each and communicate information concerning solution quality. Our results show the potential of the proposed method.

  9. V. Maniezzo, A.Carbonaro, M.Golfarelli, S.Rizzi:
    An ANTS Algorithm for Optimizing the Materialization of Fragmented Views in Data Warehouses: Preliminary Results

    The materialization of fragmented views in data warehouses has the objective of improving the system response time for a given workload. It represents a combinatorial optimization problem arising in the logical design of data warehouses which has so far received little attention from the optimization community. This paper describes the application of a metaheuristic approach, namely the ANTS approach, to this problem. In particular, we propose an integer programming formulation of the problem, derive an efficient lower bound and embed it in an ANTS algorithm. Preliminary computational results, obtained on the well-known TPC-D benchmark, are presented.

  10. I. Meents:
    A Genetic Algorithm for the Group-Technology Problem

    The design and production planning of cellular manufacturing systems requires the decomposition of a company's manufacturing assets into cells. The set of machines has to be partitioned into machine-groups and the products have to be partitioned into part-families. Finding the machine-groups and their corresponding part-families leads to the combinatorial problem of simultaneously partitioning those two sets with respect to technological requirements represented by the part-machine incidence matrix. This article presents a new solution approach based on a grouping genetic algorithm enhanced by a heuristic motivated by cluster analysis methods.

  11. S. Gregori, R. Rossi, G. Torelli, V. Liberali:
    Generation of Optimal Unit Distance Codes for Rotary Encoders through Simulated Evolution

    An evolutionary algorithm is used to generate unit distance codes for absolute rotary encoders. The target is to obtain a code suitable for disk size reduction, or for resolution increase, thus overcoming the limitations of conventional Gray codes. Obtained results show that simulated evolution can produce codes suitable for this purpose.

  12. J. Poland, K. Knödler, A. Zell:
    On the Efficient Construction of Rectangular Grids from Given Data Points

    Many combinatorial optimization problems provide their data in an input space with a given dimension. Genetic algorithms for those problems can benefit by using this natural dimension for the encoding of the individuals rather than a traditional one-dimensional bit string. This is true in particular if each data point of the problem corresponds to a bit or a group of bits of the chromosome. We develop different methods for constructing a rectangular grid of near-optimal dimension for given data points, providing a natural encoding of the individuals. Our algorithms are tested with some large TSP instances.

  13. D. A. Fotakis, S. D. Likothanassis, S. K. Stefanakos:
    An Evolutionary Annealing Approach to Graph Coloring

    This paper presents a new heuristic algorithm for the graph coloring problem based on a combination of genetic algorithms and simulated annealing. Our algorithm exploits a novel crossover operator for graph coloring. Moreover, we investigate various ways in which simulated annealing can be used to enhance the performance of an evolutionary algorithm. Experiments performed on various collections of instances have justified the potential of this approach. We also discuss some possible enhancements and directions for further research.

  14. G. Filho, L. Lorena:
    A Constructive Evolutionary Approach to School Timetabling

    This work presents a constructive approach to the process of fixing a sequence of meetings between teachers and students in a prefixed period of time, satisfying a set of constraints of various types, known as school timetabling problem. The problem is modeled as a bi-objective problem used as a basis to construct feasible assignments of teachers to classes on specified timeslots. A new representation for the timetabling problem is presented. Pairs of teachers and classes are used to form conflict-free clusters for each timeslot. Teacher preferences and the process of avoiding undesirable waiting times between classes are explicitly considered as additional objectives. Computational results over real test problems are presented.

  15. B. Weinberg, V. Bachelet, E.-G. Talbi:
    A Co-Evolutionist Meta-Heuristic for the Assignment of the Frequencies in Cellular Networks

    This paper presents a new approach, the COSEARCH approach, for solving the Problem of Assigning Frequencies (FAP) on antennas of a cellular telecommunication network. The COSEARCH approach is a co-evolutionist method in which complementary meta-heuristics, such as genetic algorithm (GA) or tabu search (TS), cooperate in parallel via an adaptive memory (AM). We introduce an original encoding and two new cross-over operators suited to FAP. COSEARCH for the FAP is compared with other studies and its efficiency is revealed on both medium and large instances.

  16. D.-R. Din, S.-S. Tseng:
    A Simulated Annealing Algorithm for Extended Cell Assignment Problem in a Wireless ATM Network

    In this paper, we investigate the extended cell assignment problem which optimally assigns new adding and splitting cells in PCS (Personal Communication Service) to switches in a wireless ATM (Asynchronous Transfer Mode) network. Given cells in a PCS and switches on an ATM network (whose locations are fixed and known), we would like to do the assignment in an attempt to minimize a cost criterion. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-hard. A simulated annealing algorithm are proposed to solve this problem. The simulated annealing algorithm, ESA (enhanced simulated annealing), generates constraint-satisfy configurations, and uses three configuration perturbation schemes to change current configuration to a new one. Experimental results indicate that ESA algorithm has good performances.

  17. P. A. Borisovsky, A. V. Eremeev:
    On Performance Estimates for Two Evolutionary Algorithms

    In this paper we consider the upper and lower bounds on probability to generate the solutions of sufficient quality using evolutionary strategies of two kinds: the (1+1)-ES and the (1,lambda)-ES. The results are obtained in terms of monotone bounds on transition probabilities of the mutation operator. Particular attention is given to the computational complexity of mutation procedure for NP-hard combinatorial optimization problems.

  18. R. Lehn, P. Kuntz:
    A Contribution to the Study of the Fitness Landscape for a Graph Drawing Problem

    These past few years genetic algorithms and stochastic hill-climbing have received a growing interest for different graph drawing problems. This paper deals with the layered drawing of directed graphs which is known to be an NP-complete problem for the arc-crossing minimization criterium. Before setting out a (n+1)th comparison between meta-heuristics, we here prefer to study the characteristics of the arc-crossings landscape for three local transformations (greedy switching, barycenter, median) adapted from the Sugiyama heuristic and we propose a descriptive analysis of the landscape for two graph families. First, all the possible layouts of 2021 small graphs are generated and the optima (number, type, height, attracting sets) are precisely defined. Then, a second family of 305 larger graphs (up to 90 vertices) is examined with one thousand hill-climbers. This study highlights the diversity of the encountered configurations and gives leads for the choice of efficient heuristics.

  19. M. Pelillo:
    Evolutionary Game Dynamics in Combinatorial Optimization: An Overview

    Replicator equations are a class of dynamical systems developed and studied in the context of evolutionary game theory, a discipline pioneered by J. Maynard Smith which aims to model the evolution of animal behavior using the principles and tools of noncooperative game theory. Because of their dynamical properties, they have been recently applied with significant success to a number of combinatorial optimization problems. It is the purpose of this article to provide a summary and an up-to-date bibliography of these applications.

  20. R. Baraglia, J. I. Hidalgo, R. Perego:
    A Parallel Hybrid Heuristic for the TSP

    In this paper we investigate the design of a coarse-grained parallel implementation of Cga-LK, a hybrid heuristic for the Traveling Salesman Problem (TSP). Cga-LK exploits a compact genetic algorithm in order to generate high-quality tours which are then refined by means of an efficient implementation of the Lin-Kernighan local search heuristic. The results of several experiments conducted on a cluster of workstations with different TSP instances show the efficacy of the parallelism exploitation.

  21. E. K. Burke, P. I. Cowling, R. Keuthen:
    Effective Local and Guided Variable Neighbourhood Search Methods for the Asymmetric Traveling Salesman Problem

    In this paper we present effective new local and variable neighbourhood search heuristics for the asymmetric Travelling Salesman Problem. Our local search approach, HyperOpt, is inspired by a heuristic developed for a sequencing problem arising in the manufacture of printed circuit boards. In our approach we embed an exact algorithm into a local search heuristic in order to exhaustively search promising regions of the solution space. We propose a hybrid of HyperOpt and 3-opt which allows us to benefit from the advantages of both approaches and gain better tours overall. Using this hybrid within the Variable Neighbourhood Search (VNS) metaheuristic framework, as suggested by Hansen and Mladenovi;, allows us to overcome local optima and create tours of very high quality. We introduce the notion of a ``guided shake'' within VNS and show that this yields a heuristic which is more effective than the random shakes proposed by Hansen and Mladenovi&

  22. M. Guntsch, M. Middendorf:
    Pheromone Modification Strategies for Ant Algorithms applied to Dynamic TSP

    We investigate strategies for pheromone modification of ant algorithms in reaction to the insertion/deletion of a city of Traveling Salesperson Problem (TSP) instances. Three strategies for pheromone diversification through equalization of the pheromone values on the edges are proposed and compared. One strategy acts globally without consideration of the position of the inserted/deleted city. The other strategies perform pheromone modification only in the neighborhood of the inserted/deleted city, where neighborhood is defined differently for the two strategies. We furthermore evaluate different parameter settings for each of the strategies.

  23. S. Esquivel, C. Gatica, R. Gallard:
    Conventional and Multirecombinative Evolutionary Algorithms for the Parallel Task Scheduling Problem

    The present work deals with the problem of allocating a number of non identical tasks in a parallel system. The model assumes that the system consists of a number of identical processors and that only one task may be executed on a processor at a time. All schedules and tasks are nonpreemptive. Graham's well-known list scheduling algorithm (LSA) is contrasted with different evolutionary algorithms (EAs), which differ on the representations and the recombinative approach used. Regarding representation, direct and indirect representation of schedules are used. Concerning recombination, the conventional single crossover per couple (SCPC) and a multiple crossover per couple (MCPC) are used. Outstanding behaviour of evolutionary algorithms when contrasted against LSA was detected. Results are shown and discussed.

Web site designed and maintained by Chris Osborne at EvoNet.