| |
|
|
|
|
EvoCOP abstracts
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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&
- 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.
- 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.
|
