Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2009 | Buch

Evolutionary Dynamics of Extremal Optimization Kapitel lesen Erstes Kapitel lesen

Learning and Intelligent Optimization

Third International Conference, LION 3, Trento, Italy, January 14-18, 2009. Selected Papers

herausgegeben von: Thomas Stützle

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

LION 3, the Third International Conference on Learning and Intelligent Op- mizatioN, was held during January 14–18 in Trento, Italy. The LION series of conferences provides a platform for researchers who are interested in the int- section of e?cient optimization techniques and learning. It is aimed at exploring the boundaries and uncharted territories between machine learning, arti?cial intelligence, mathematical programming and algorithms for hard optimization problems. The considerable interest in the topics covered by LION was re?ected by the overwhelming number of 86 submissions, which almost doubled the 48 subm- sions received for LION’s second edition in December 2007. As in the ?rst two editions, the submissions to LION 3 could be in three formats: (a) original novel and unpublished work for publication in the post-conference proceedings, (b) extended abstracts of work-in-progressor a position statement, and (c) recently submitted or published journal articles for oral presentations. The 86 subm- sions received include 72, ten, and four articles for categories (a), (b), and (c), respectively.

Inhaltsverzeichnis

Frontmatter

Evolutionary Dynamics of Extremal Optimization

Evolutionary Dynamics of Extremal Optimization
Abstract
Dynamic features of the recently introduced extremal optimization heuristic are analyzed. Numerical studies of this evolutionary search heuristic show that it performs optimally at a transition between a jammed and an diffusive state. Using a simple, annealed model, some of the key features of extremal optimization are explained. In particular, it is verified that the dynamics of local search possesses a generic critical point under the variation of its sole parameter, separating phases of too greedy (non-ergodic, jammed) and too random (ergodic, diffusive) exploration. Analytic comparison with other local search methods, such as a fixed temperature Metropolis algorithm, within this model suggests that the existence of the critical point is the essential distinction leading to the optimal performance of the extremal optimization heuristic.
Stefan Boettcher
A Variable Neighborhood Descent Search Algorithm for Delay-Constrained Least-Cost Multicast Routing
Abstract
The rapid evolution of real-time multimedia applications requires Quality of Service (QoS) based multicast routing in underlying computer networks. The constrained Steiner Tree, as the underpinning mathematical structure, is a well-known NP-complete problem. In this paper we investigate a variable neighborhood descent (VND) search, a variant of variable neighborhood search, for the delay-constrained least-cost (DCLC) multicast routing problem. The neighborhood structures designed in the VND approaches are based on the idea of path replacement in trees. They are simple, yet effective operators, enabling a flexible search over the solution space of this complex problem with multiple constraints. A large number of simulations demonstrate that our algorithm is highly efficient in solving the DCLC multicast routing problem in terms of the tree cost and execution time. To our knowledge, this is the first study of VND algorithm on the DCLC multicast routing problem. It outperforms other existing algorithms over a range of problem instances.
Rong Qu, Ying Xu, Graham Kendall
Expeditive Extensions of Evolutionary Bayesian Probabilistic Neural Networks
Abstract
Probabilistic Neural Networks (PNNs) constitute a promising methodology for classification and prediction tasks. Their performance depends heavily on several factors, such as their spread parameters, kernels, and prior probabilities. Recently, Evolutionary Bayesian PNNs were proposed to address this problem by incorporating Bayesian models for estimation of spread parameters, as well as Particle Swarm Optimization (PSO) as a means to select prior probabilities. We further extend this class of models by introducing new features, such as the Epanechnikov kernels as an alternative to the Gaussian ones, and PSO for parameter configuration of the Bayesian model. Experimental results of five extended models on widely used benchmark problems suggest that the proposed approaches are significantly faster than the established ones, while exhibiting competitive classification accuracy.
Vasileios L. Georgiou, Sonia Malefaki, Konstantinos E. Parsopoulos, Philipos D. Alevizos, Michael N. Vrahatis
New Bounds on the Clique Number of Graphs Based on Spectral Hypergraph Theory
Abstract
This work introduces new bounds on the clique number of graphs derived from a result due to Sós and Straus, which generalizes the Motzkin-Straus Theorem to a specific class of hypergraphs. In particular, we generalize and improve the spectral bounds introduced by Wilf in 1967 and 1986 establishing an interesting link between the clique number and the emerging spectral hypergraph theory field. In order to compute the bounds we face the problem of extracting the leading H-eigenpair of supersymmetric tensors, which is still uncovered in the literature. To this end, we provide two approaches to serve the purpose. Finally, we present some preliminary experimental results.
Samuel Rota Bulò, Marcello Pelillo
Beam-ACO Based on Stochastic Sampling: A Case Study on the TSP with Time Windows
Abstract
Beam-ACO algorithms are hybrid methods that combine the metaheuristic ant colony optimization with beam search. They heavily rely on accurate and computationally inexpensive bounding information for choosing between different partial solutions during the solution construction process. In this work we present the use of stochastic sampling as a useful alternative to bounding information in cases were computing accurate bounding information is too expensive. As a case study we choose the well-known travelling salesman problem with time windows. Our results clearly demonstrate that Beam-ACO, even when bounding information is replaced by stochastic sampling, may have important advantages over standard ACO algorithms.
Manuel López-Ibáñez, Christian Blum
Flexible Stochastic Local Search for Haplotype Inference
Abstract
Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony of the entropy minimization criteria) and to solve it using off-the-shelf combinatorial optimization techniques.
In this paper, we present and discuss an approach based on local search metaheuristics. A flexible solver is designed to tackle the Haplotype Inference under the criterion of choice, that could be defined by the user. We test our approach by solving instances from common Haplotype Inference benchmarks both under the hypothesis of pure parsimony and entropy minimization. Results show that the approach achieves a good trade-off between solution quality and execution time and compares favorably with the state of the art.
Luca Di Gaspero, Andrea Roli
A Knowledge Discovery Approach to Understanding Relationships between Scheduling Problem Structure and Heuristic Performance
Abstract
Using a knowledge discovery approach, we seek insights into the relationships between problem structure and the effectiveness of scheduling heuristics. A large collection of 75,000 instances of the single machine early/tardy scheduling problem is generated, characterized by six features, and used to explore the performance of two common scheduling heuristics. The best heuristic is selected using rules from a decision tree with accuracy exceeding 97%. A self-organizing map is used to visualize the feature space and generate insights into heuristic performance. This paper argues for such a knowledge discovery approach to be applied to other optimization problems, to contribute to automation of algorithm selection as well as insightful algorithm design.
Kate A. Smith-Miles, Ross J. W. James, John W. Giffin, Yiqing Tu
Fitness Landscape Analysis for the Resource Constrained Project Scheduling Problem
Abstract
The fitness landscape of the resource constrained project scheduling problem is investigated by examining the search space position type distribution and the correlation between the quality of a solution and its distance to an optimal solution. The suitability of the landscape for search with evolutionary computation and local search methods is discussed.
Jens Czogalla, Andreas Fink
An ACO-Based Reactive Framework for Ant Colony Optimization: First Experiments on Constraint Satisfaction Problems
Abstract
We introduce two reactive frameworks for dynamically adapting some parameters of an Ant Colony Optimization (ACO) algorithm. Both reactive frameworks use ACO to adapt parameters: pheromone trails are associated with parameter values; these pheromone trails represent the learnt desirability of using parameter values and are used to dynamically set parameters in a probabilistic way. The two frameworks differ in the granularity of parameter learning. We experimentally evaluate these two frameworks on an ACO algorithm for solving constraint satisfaction problems.
Madjid Khichane, Patrick Albert, Christine Solnon
Selection of Heuristics for the Job-Shop Scheduling Problem Based on the Prediction of Gaps in Machines
Abstract
We present a general methodology to model the behavior of heuristics for the Job-Shop Scheduling (JSS) that address the problem by solving conflicts between different operations on the same machine. Our models estimate the gaps between consecutive operations on a machine given measures that characteristics the JSS instance and those operations. These models can be used for a better understanding of the behavior of the heuristics as well as to estimate the performance of the methods. We tested it using two well know heuristics: Shortest Processing Time and Longest Processing Time, that were tested on a large number of random JSS instances. Our results show that it is possible to predict the value of the gaps between consecutive operations from on the job, on random instances. However, the prediction the relative performance of the two heuristics based on those estimates is not successful. Concerning the main goal of this work, we show that the models provide interesting information about the behavior of the heuristics.
Pedro Abreu, Carlos Soares, Jorge M. S. Valente
Position-Guided Tabu Search Algorithm for the Graph Coloring Problem
Abstract
A very undesirable behavior of any heuristic algorithm is to be stuck in some specific parts of the search space, in particular in the basins of attraction of the local optima. While there are many well-studied methods to help the search process escape a basin of attraction, it seems more difficult to prevent it from looping between a limited number of basins of attraction. We introduce a Position Guided Tabu Search (PGTS) heuristic that, besides avoiding local optima, also avoids re-visiting candidate solutions in previously visited regions. A learning process, based on a metric of the search space, guides the Tabu Search toward yet unexplored regions. The results of PGTS for the graph coloring problem are competitive. It significantly improves the results of the basic Tabu Search for almost all tested difficult instances from the DIMACS Challenge Benchmark and it matches most of the best results from the literature.
Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz
Corridor Selection and Fine Tuning for the Corridor Method
Abstract
In this paper we present a novel hybrid algorithm, in which ideas from the genetic algorithm and the GRASP metaheuristic are cooperatively used and intertwined to dynamically adjust a key parameter of the corridor method, i.e., the corridor width, during the search process. In addition, a fine-tuning technique for the corridor method is then presented. The response surface methodology is employed in order to determine a good set of parameter values given a specific problem input size. The effectiveness of both the algorithm and the validation of the fine tuning technique are illustrated on a specific problem selected from the domain of container terminal logistics, known as the blocks relocation problem, where one wants to retrieve a set of blocks from a bay in a specified order, while minimizing the overall number of movements and relocations. Computational results on 160 benchmark instances attest the quality of the algorithm and validate the fine tuning process.
Marco Caserta, Stefan Voß
Dynamic Multi-Armed Bandits and Extreme Value-Based Rewards for Adaptive Operator Selection in Evolutionary Algorithms
Abstract
The performance of many efficient algorithms critically depends on the tuning of their parameters, which on turn depends on the problem at hand. For example, the performance of Evolutionary Algorithms critically depends on the judicious setting of the operator rates. The Adaptive Operator Selection (AOS) heuristic that is proposed here rewards each operator based on the extreme value of the fitness improvement lately incurred by this operator, and uses a Multi-Armed Bandit (MAB) selection process based on those rewards to choose which operator to apply next. This Extreme-based Multi-Armed Bandit approach is experimentally validated against the Average-based MAB method, and is shown to outperform previously published methods, whether using a classical Average-based rewarding technique or the same Extreme-based mechanism. The validation test suite includes the easy One-Max problem and a family of hard problems known as “Long k-paths”.
Álvaro Fialho, Luis Da Costa, Marc Schoenauer, Michèle Sebag
Comparison of Coarsening Schemes for Multilevel Graph Partitioning
Abstract
Graph partitioning is a well-known optimization problem of great interest in theoretical and applied studies. Since the 1990s, many multilevel schemes have been introduced as a practical tool to solve this problem. A multilevel algorithm may be viewed as a process of graph topology learning at different scales in order to generate a better approximation for any approximation method incorporated at the uncoarsening stage in the framework. In this work we compare two multilevel frameworks based on the geometric and the algebraic multigrid schemes for the partitioning problem.
Cédric Chevalier, Ilya Safro
Cooperative Strategies and Reactive Search: A Hybrid Model Proposal
Abstract
Cooperative strategies and reactive search are very promising techniques for solving hard optimization problems, since they reduce human intervention required to set up a method when the resolution of an unknown instance is needed. However, as far as we know, a hybrid between both techniques has not yet been proposed in the literature. In this work, we show how reactive search principles can be incorporated into a simple rule-driven centralised cooperative strategy. The proposed method has been tested on the Uncapacitated Single Allocation p-Hub Median Problem, obtaining promising results.
Antonio D. Masegosa, Franco Mascia, David Pelta, Mauro Brunato
Study of the Influence of the Local Search Method in Memetic Algorithms for Large Scale Continuous Optimization Problems
Abstract
Memetic algorithms arise as very effective algorithms to obtain reliable and high accurate solutions for complex continuous optimization problems. Nowadays, high-dimensional optimization problems are an interesting field of research. Its high dimension introduces new problems for the optimization process, making recommendable to test the behavior of optimization algorithms to large-scale problems. In memetic algorithms, the local search method is responsible of exploring the neighborhood of the current solutions; therefore, the dimensionality has a direct influence over this component. The aim of this paper is to study this influence. We design different memetic algorithms that only differ in the local search method applied, and they are compared using two sets of continuous benchmark functions: a standard one and a specific set with large-scale problems. The results show that high dimensionality reduces the differences among the different local search methods.
Daniel Molina, Manuel Lozano, Francisco Herrera

MALIOB Workshop Papers

Neural Network Pairwise Interaction Fields for Protein Model Quality Assessment
Abstract
We present a new knowledge-based Model Quality Assessment Program (MQAP) at the residue level which evaluates single protein structure models. We use a tree representation of the C α trace to train a novel Neural Network Pairwise Interaction Field (NN-PIF) to predict the global quality of a model. We also attempt to extract local quality from global quality. The model allows fast evaluation of multiple different structure models for a single sequence. In our tests on a large set of structures, our model outperforms most other methods based on different and more complex protein structure representations in both local and global quality prediction. The method is available upon request from the authors. Method-specific rankers may also built by the authors upon request.
Alberto J. M. Martin, Alessandro Vullo, Gianluca Pollastri
A Graph-Based Semi-supervised Algorithm for Protein Function Prediction from Interaction Maps
Abstract
Protein function prediction represents a fundamental challenge in bioinformatics. The increasing availability of proteomics network data has enabled the development of several approaches that exploit the information encoded in networks in order to infer protein function. In this paper we introduce a new algorithm based on the concept of topological overlap between nodes of the graph, which addresses the problem of the classification of partially labeled protein interaction networks. The proposed approach is tested on the yeast interaction map and compared with two current state-of-the-art algorithms. Cross-validation experiments provide evidence that the proposed method represents a competitive alternative in a wide range of experimental conditions and also that, in many cases, it provides enhanced predictive accuracy.
Valerio Freschi
Substitution Matrices and Mutual Information Approaches to Modeling Evolution
Abstract
Substitution matrices are at the heart of Bioinformatics: sequence alignment, database search, phylogenetic inference, protein family classification are all based on BLOSUM, PAM, JTT, mtREV24 and other matrices. These matrices provide means of computing models of evolution and assessing the statistical relationships amongst sequences. This paper reports two results; first we show how Bayesian and grid settings can be used to derive novel specific substitution matrices for fish and insects and we discuss their performances with respect to standard amino acid replacement matrices. Then we discuss a novel application of these matrices: a refinement of the mutual information formula applied to amino acid alignments by incorporating a substitution matrix into the calculation of the mutual information. We show that different substitution matrices provide qualitatively different mutual information results and that the new algorithm allows the derivation of better estimates of the similarity along a sequence alignment. We thus express an interesting procedure: generating ad hoc substitution matrices from a collection of sequences and combining the substitution matrices and mutual information for the detection of sequence patterns.
Stephan Kitchovitch, Yuedong Song, Richard van der Wath, Pietro Liò
Backmatter
Metadaten
Titel
Learning and Intelligent Optimization
herausgegeben von
Thomas Stützle
Copyright-Jahr
2009
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-11169-3
Print ISBN
978-3-642-11168-6
DOI
https://doi.org/10.1007/978-3-642-11169-3

Premium Partner

    Bildnachweise