Graphic summary
  • Show / hide key
  • Information


Scientific and technological production
  •  

1 to 50 of 146 results
  • Premis Arquimedes d'introducció a la recerca científica en l¿area d'Enginyeria i arquitectura

     Mateo Bellido, Sergi; Blum, Christian Clemens
    Award or recognition

    View View Open in new window  Share

  • Swarm Intelligence Techniques for Optimization and Management Tasks inSensor Networks  Open access  awarded activity

     Hernandez Pibernat, Hugo
    Department of Computer Science, Universitat Politècnica de Catalunya
    Theses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    The main contributions of this thesis are located in the domain of wireless sensor netorks. More in detail, we introduce energyaware algorithms and protocols in the context of the following topics: self-synchronized duty-cycling in networks with energy harvesting capabilities, distributed graph coloring and minimum energy broadcasting with realistic antennas. In the following, we review the research conducted in each case. We propose a self-synchronized duty-cycling mechanism for sensor networks. This mechanism is based on the working and resting phases of natural ant colonies, which show self-synchronized activity phases. The main goal of duty-cycling methods is to save energy by efficiently alternating between different states. In the case at hand, we considered two different states: the sleep state, where communications are not possible and energy consumption is low; and the active state, where communication result in a higher energy consumption. In order to test the model, we conducted an extensive experimentation with synchronous simulations on mobile networks and static networks, and also considering asynchronous networks. Later, we extended this work by assuming a broader point of view and including a comprehensive study of the parameters. In addition, thanks to a collaboration with the Technical University of Braunschweig, we were able to test our algorithm in the real sensor network simulator Shawn (http://shawn.sf.net). The second part of this thesis is devoted to the desynchronization of wireless sensor nodes and its application to the distributed graph coloring problem. In particular, our research is inspired by the calling behavior of Japanese tree frogs, whose males use their calls to attract females. Interestingly, as female frogs are only able to correctly localize the male frogs when their calls are not too close in time, groups of males that are located nearby each other desynchronize their calls. Based on a model of this behavior from the literature, we propose a novel algorithm with applications to the field of sensor networks. More in detail, we analyzed the ability of the algorithm to desynchronize neighboring nodes. Furthermore, we considered extensions of the original model, hereby improving its desynchronization capabilities.To illustrate the potential benefits of desynchronized networks, we then focused on distributed graph coloring. Later, we analyzed the algorithm more extensively and show its performance on a larger set of benchmark instances. The classical minimum energy broadcast (MEB) problem in wireless ad hoc networks, which is well-studied in the scientific literature, considers an antenna model that allows the adjustment of the transmission power to any desired real value from zero up to the maximum transmission power level. However, when specifically considering sensor networks, a look at the currently available hardware shows that this antenna model is not very realistic. In this work we re-formulate the MEB problem for an antenna model that is realistic for sensor networks. In this antenna model transmission power levels are chosen from a finite set of possible ones. A further contribution concerns the adaptation of an ant colony optimization algorithm --currently being the state of the art for the classical MEB problem-- to the more realistic problem version, the so-called minimum energy broadcast problem with realistic antennas (MEBRA). The obtained results show that the advantage of ant colony optimization over classical heuristics even grows when the number of possible transmission power levels decreases. Finally we build a distributed version of the algorithm, which also compares quite favorably against centralized heuristics from the literature.

    Las principles contribuciones de esta tesis se encuentran en el domino de las redes de sensores inalámbricas. Más en detalle, introducimos algoritmos y protocolos que intentan minimizar el consumo energético para los siguientes problemas: gestión autosincronizada de encendido y apagado de sensores con capacidad para obtener energía del ambiente, coloreado de grafos distribuido y broadcasting de consumo mínimo en entornos con antenas reales. En primer lugar, proponemos un sistema capaz de autosincronizar los ciclos de encendido y apagado de los nodos de una red de sensores. El mecanismo está basado en las fases de trabajo y reposo de las colonias de hormigas tal y como estas pueden observarse en la naturaleza, es decir, con fases de actividad autosincronizadas. El principal objectivo de este tipo de técnicas es ahorrar energía gracias a alternar estados de forma eficiente. En este caso en concreto, consideramos dos estados diferentes: el estado dormido, en el que los nodos no pueden comunicarse y el consumo energético es bajo; y el estado activo, en el que las comunicaciones propician un consumo energético elevado. Con el objetivo de probar el modelo, se ha llevado a cabo una extensa experimentación que incluye tanto simulaciones síncronas en redes móviles y estáticas, como simulaciones en redes asíncronas. Además, este trabajo se extendió asumiendo un punto de vista más amplio e incluyendo un detallado estudio de los parámetros del algoritmo. Finalmente, gracias a la colaboración con la Technical University of Braunschweig, tuvimos la oportunidad de probar el mecanismo en el simulador realista de redes de sensores, Shawn (http://shawn.sf.net). La segunda parte de esta tesis está dedicada a la desincronización de nodos en redes de sensores y a su aplicación al problema del coloreado de grafos de forma distribuida. En particular, nuestra investigación está inspirada por el canto de las ranas de árbol japonesas, cuyos machos utilizan su canto para atraer a las hembras. Resulta interesante que debido a que las hembras solo son capaces de localizar las ranas macho cuando sus cantos no están demasiado cerca en el tiempo, los grupos de machos que se hallan en una misma región desincronizan sus cantos. Basado en un modelo de este comportamiento que se encuentra en la literatura, proponemos un nuevo algoritmo con aplicaciones al campo de las redes de sensores. Más en detalle, analizamos la habilidad del algoritmo para desincronizar nodos vecinos. Además, consideramos extensiones del modelo original, mejorando su capacidad de desincronización. Para ilustrar los potenciales beneficios de las redes desincronizadas, nos centramos en el problema del coloreado de grafos distribuido que tiene relación con diferentes tareas habituales en redes de sensores. El clásico problema del broadcasting de consumo mínimo en redes ad hoc ha sido bien estudiado en la literatura. El problema considera un modelo de antena que permite transmitir a cualquier potencia elegida (hasta un máximo establecido por el dispositivo). Sin embargo, cuando se trabaja de forma específica con redes de sensores, un vistazo al hardware actualmente disponible muestra que este modelo de antena no es demasiado realista. En este trabajo reformulamos el problema para el modelo de antena más habitual en redes de sensores. En este modelo, los niveles de potencia de transmisión se eligen de un conjunto finito de posibilidades. La siguiente contribución consiste en en la adaptación de un algoritmo de optimización por colonias de hormigas a la versión más realista del problema, también conocida como broadcasting de consumo mínimo con antenas realistas. Los resultados obtenidos muestran que la ventaja de este método sobre heurísticas clásicas incluso crece cuando el número de posibles potencias de transmisión decrece. Además, se ha presentado una versión distribuida del algoritmo, que también se compara de forma bastante favorable contra las heurísticas centralizadas conocidas.

  • Variable neighbourhood search for the variable sized bin packing problem

     Hemmelmayr, Vera C.; Schmid, Verena; Blum, Christian Clemens
    Computers & operations research
    Vol. 39, num. 5, p. 1097-1108
    DOI: 10.1016/j.cor.2011.07.003
    Date of publication: 2012-05
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.

  • Large neighbourhood search algorithms for the founder sequence reconstruction problem

     Roli, Andrea; Benedettini, Stefano; Stützle, Thomas; Blum, Christian Clemens
    Computers & operations research
    Vol. 39, num. 2, p. 213-224
    DOI: 10.1016/j.cor.2011.03.012
    Date of publication: 2012-02
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The reconstruction of founder genetic sequences of a population is a relevant issue in evolutionary biology research. The problem consists in finding a biologically plausible set of genetic sequences (founders), which can be recombined to obtain the genetic sequences of the individuals of a given population. The reconstruction of these sequences can be modelled as a combinatorial optimisation problem in which one has to find a set of genetic sequences such that the individuals of the population under study can be obtained by recombining founder sequences minimising the number of recombinations. This problem is called the founder sequence reconstruction problem. Solving this problem can contribute to research in understanding the origins of specific genotypic traits. In this paper, we present large neighbourhood search algorithms to tackle this problem. The proposed algorithms combine a stochastic local search with a branch-and-bound algorithm devoted to neighbourhood exploration. The developed algorithms are thoroughly evaluated on three different benchmark sets and they establish the new state of the art for realistic problem instances.

  • Iterated greedy algorithms for the maximal covering location problem

     Rodríguez Diaz, Francisco Javier; Blum, Christian Clemens; Lozano, Manuel; García Martínez, Carlos
    Lecture notes in computer science
    Vol. 7245, p. 172-181
    DOI: 10.1007/978-3-642-29124-1_15
    Date of publication: 2012
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The problem of allocating a set of facilities in order to maximise the sum of the demands of the covered clients is known as the maximal covering location problem. In this work we tackle this problem by means of iterated greedy algorithms. These algorithms iteratively refine a solution by partial destruction and reconstruction, using a greedy constructive procedure. Iterated greedy algorithms have been applied successfully to solve a considerable number of problems. With the aim of providing additional results and insights along this line of research, this paper proposes two new iterated greedy algorithms that incorporate two innovative components: a population of solutions optimised in parallel by the iterated greedy algorithm, and an improvement procedure that explores a large neighbourhood by means of an exact solver. The benefits of the proposal in comparison to a recently proposed decomposition heuristic and a standalone exact solver are experimentally shown.

  • Distributed graph coloring: An approach based on the calling behavior of Japanese tree frogs

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Swarm intelligence
    Vol. 6, num. 2, p. 117-150
    DOI: 10.1007/s11721-012-0067-2
    Date of publication: 2012-06
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • An artificial bee colony algorithm for the unrelated parallel machines scheduling problem

     Rodríguez Diaz, Francisco Javier; García Martínez, Carlos; Blum, Christian Clemens; Lozano, Manuel
    Lecture notes in computer science
    Vol. 7492, p. 143-152
    DOI: 10.1007/978-3-642-32964-7_15
    Date of publication: 2012
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • A population-based iterated greedy algorithm for the minimum weight vertex cover problem

     Bouamama, Salim; Blum, Christian Clemens; Boukerram, Abdellah
    Applied soft computing
    Vol. 12, num. 6, p. 1632-1639
    DOI: 10.1016/j.asoc.2012.02.013
    Date of publication: 2012-06
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Wireless and Mobile Networking Conference (WMNC 2011) Best Paper Award

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Award or recognition

    View View Open in new window  Share

  • Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic

     Baumgartner, Lukas; Schmid, Verena; Blum, Christian Clemens
    Lecture notes in computer science
    Vol. 6683, p. 76-90
    DOI: 10.1007/978-3-642-25566-3_6
    Date of publication: 2011
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The two-dimensional bin packing problem (2BP) consists in packing a set of rectangular items into rectangular, equally-sized bins. The problem is NP-hard and has a multitude of real world applications. We consider the case where the items are oriented and guillotine cutting is free. In this paper we first present a review of well-know heuristics for the 2BP and then propose a new ILP model for the problem. Moreover, we develop a multi-start algorithm based on a probabilistic version of the LGFi heuristic from the literature. Results are compared to other well-known heuristics, using data sets provided in the literature. The obtained experimental results show that the proposed algorithm returns excellent solutions. With an average percentage deviation of 1.8% from the best know lower bounds it outperformes the other algorithms by 1.1% − 5.7%. Also for 3 of the 500 instances we tested a new upper bound was found.

  • Minimum energy broadcasting in wireless sensor networks: An ant colony optimization approach for a realistic antenna model

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Applied soft computing
    Vol. 11, num. 8, p. 5684-5694
    DOI: 10.1016/j.asoc.2011.03.023
    Date of publication: 2011-12
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Hybrid metaheuristics in combinatorial optimization: A survey

     Blum, Christian Clemens; Puchinger, Jakob; Raidl, Günther; Roli, Andrea
    Applied soft computing
    Vol. 11, num. 6, p. 4135-4151
    DOI: 10.1016/j.asoc.2011.02.032
    Date of publication: 2011-09
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Research in metaheuristics for combinatorial optimization problems has lately experienced a noteworthy shift towards the hybridization of metaheuristics with other techniques for optimization. At the same time, the focus of research has changed from being rather algorithm-oriented to being more problem-oriented. Nowadays the focus is on solving the problem at hand in the best way possible, rather than promoting a certain metaheuristic. This has led to an enormously fruitful cross-fertilization of different areas of optimization. This cross-fertilization is documented by a multitude of powerful hybrid algorithms that were obtained by combining components from several different optimization techniques. Hereby, hybridization is not restricted to the combination of different metaheuristics but includes, for example, the combination of exact algorithms and metaheuristics. In this work we provide a survey of some of the most important lines of hybridization. The literature review is accompanied by the presentation of illustrative examples.

  • Iterative beam search for simple assembly line balancing with a fixed number of work stations

     Blum, Christian Clemens
    SORT: statistics and operations research transactions
    Vol. 35, num. 2, p. 145-164
    Date of publication: 2011
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Automated reconstruction of dendritic and axonal trees by global optimization with geometric priors

     Türetken, Engin; González, Germán; Blum, Christian Clemens; Fua, Pascal
    Neuroinformatics
    Vol. 9, num. 2-3, p. 279-302
    DOI: 10.1007/s12021-011-9122-1
    Date of publication: 2011
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Foundations of ANTCYCLE: self-synchronized duty-cycling in mobile sensor networks

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    The Computer journal (paper)
    Vol. 54, num. 9, p. 1427-1448
    DOI: 10.1093/comjnl/bxq099
    Date of publication: 2011-09
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Ants are generally believed to follow an intensive work routine. Numerous tales and fables refer to ants as conscientious workers. Nevertheless, biologists have discovered that ants also rest for extended periods of time. This does not only hold for individual ants. Interestingly, ant colonies exhibit synchronized activity phases that result from self-organization. In this work, self-synchronization in ant colonies is taken as the inspiring source for a new mechanism of self-synchronized duty-cycling in mobile sensor networks. Hereby, we assume that sensor nodes are equipped with energy harvesting capabilities such as, for example, solar cells. We show that the proposed self-synchronization mechanism can be made adaptive depending on variable energy resources. The main objective of this paper is to study and explore the swarm intelligence foundations of self-synchronized dutycycling. With this purpose in mind, physical constraints such as packet collisions and packet loss are generally not considered.

  • On solving the assembly line worker assignment and balancing problem via beam search

     Blum, Christian Clemens; Miralles, Cristobal
    Computers & operations research
    Vol. 38, num. 1, p. 328-339
    DOI: 10.1016/j.cor.2010.05.008
    Date of publication: 2011-01
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Guest editorial: Special issue based on the LION 4 conference

     Blum, Christian Clemens; Battiti, Roberto
    Annals of mathematics and artificial intelligence
    Vol. 61, num. 2, p. 47-48
    DOI: 10.1007/s10472-011-9239-9
    Date of publication: 2011
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • FlockOpt: A new swarm optimization algorithm based on collective behavior of starling birds

     Hereford, James; Blum, Christian Clemens
    World Congress on Nature & Biologically Inspired Computing
    p. 17-22
    DOI: 10.1109/NaBIC.2011.6089411
    Presentation's date: 2011
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Ant colony optimization

     Blum, Christian Clemens
    Genetic and Evolutionary Computation Conference
    p. 963-990
    DOI: 10.1145/2001858.2002122
    Presentation's date: 2011
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Implementing a model of Japanese tree frogs' calling behavior in sensor networks: a study of possible improvements

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Genetic and Evolutionary Computation Conference
    p. 615-622
    DOI: /doi.acm.org/10.1145/2001858.2002057
    Presentation's date: 2011
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Distributed graph coloring in wireless ad hoc networks: a light-weight algorithm based on Japanese tree frogs' calling behaviour  awarded activity

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Wireless and Mobile Networking Conference
    p. 1-7
    DOI: 10.1109/WMNC.2011.6097216
    Presentation's date: 2011
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Graph coloring concerns the problem of assigning colors to the nodes of a graph such that adjacent nodes do not share the same color. In this paper we deal with the problem of finding valid colorings of graphs in a distributed manner, while minimizing the number of used colors. This problem is at the heart of several problems arising in wireless ad hoc networks. Examples are TDMA slot assignment, wakeup scheduling, and data collection. The proposed algorithm is inspired by the de-synchronization that can be observed in the calling behaviour of male Japanese tree frogs. Experimental results show that our algorithm is very competitive with current state-of-the-art approaches.

    Wireless and Mobile Networking Conference (WMNC’11) Best Paper Award

  • Theoretical Computer Science Top Cited Article 2005-2010

     Blum, Christian Clemens; Dorigo, Marco
    Award or recognition

     Share

  • A protocol for self-synchronized duty-cycling in sensor nenworks: generic implementation in Wiselib

     Hernandez Pibernat, Hugo; Blesa Aguilera, Maria Jose; Blum, Christian Clemens; Baumgartner, Tobias; Fekete, Sandor P.; Kröller, Alexander
    Date: 2010
    Report

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Adapting a sensor net to the dynamic environment in a wildlife scenario: a case study

     Blesa Aguilera, Maria Jose; Blum, Christian Clemens; De Caro, Angelo; Degener, Bastian; Kempkes, Barbara; Leone, Pierre; Persiano, Giuseppe; Meyer auf der Heide,, Friedhelm; Mylonas, Georgios
    Date: 2010
    Report

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Hybrid algorithms for the variable sized bin packing problem

     Blum, Christian Clemens; Hemmelmayr, Vera C.; Pibernat, Heranandez Hugo; Schmid, Verena
    Lecture notes in computer science
    num. 6373, p. 16-30
    DOI: 10.1007/978-3-642-16054-7_2
    Date of publication: 2010-10
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    This paper deals with the so-called variable sized bin packing problem, which is a generalization of the one-dimensional bin packing problem in which a set of items with given weights have to be packed into a minimum-cost set of bins of variable sizes and costs. First we propose a heuristic and a beam search approach. Both algorithms are strongly based on dynamic programming procedures and lower bounding techniques. Second, we propose a variable neighborhood search approach where some neighborhoods are also based on dynamic programming. The best results are obtained by using the solutions provided by the proposed heuristic as starting solutions for variable neighborhood search. The results show that this algorithm is very competitive with current state-of-the-art approaches.

  • A randomized iterated greedy algorithm for the founder sequence reconstruction problem

     Benedettini, Stefano; Blum, Christian Clemens; Roli, Andrea
    Lecture notes in computer science
    num. 6073, p. 37-51
    DOI: 10.1007/978-3-642-13800-3_4
    Date of publication: 2010-04
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The problem of inferring ancestral genetic information in terms of a set of founders of a given population arises in various biological contexts. In optimization terms, this problem can be formulated as a combinatorial string problem. The main problem of existing techniques, both exact and heuristic, is that their time complexity scales exponentially, which makes them impractical for solving large-scale instances. Basing our work on previous ideas outlined in [1], we developed a randomized iterated greedy algorithm that is able to provide good solutions in a short time span. The experimental evaluation shows that our algorithm is currently the best approximate technique, especially when large problem instances are concerned.

  • Hybrid Metaheuristics

     Blum, Christian Clemens
    Computers & operations research
    Vol. 37, num. 3, p. 430-431
    Date of publication: 2010-03
    Journal article

     Share Reference managers Reference managers Open in new window

  • A hybrid metaheuristic for the longest common subsequence problem

     Lozano, Manuel; Blum, Christian Clemens
    Lecture notes in computer science
    num. 6373, p. 1-15
    DOI: 10.1007/978-3-642-16054-7_1
    Date of publication: 2010-10
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The longest common subsequence problem is a classical string problem. It has applications, for example, in pattern recognition and bioinformatics. This contribution proposes an integrative hybrid metaheuristic for this problem. More specifically, we propose a variable neighborhood search that applies an iterated greedy algorithm in the improvement phase and generates the starting solutions by invoking either beam search or a greedy randomized procedure. The main motivation of this work is the lack of fast neighborhood search methods for the tackled problem. The benefits of the proposal in comparison to the state of the art are experimentally shown.

  • Reconstructing geometrically consistent tree structures from noisy images

     Türetken, Engin; Blum, Christian Clemens; González, Germán; Fua, Pascal
    Lecture notes in computer science
    num. 6361, p. 291-299
    DOI: 10.1007/978-3-642-15705-9_36
    Date of publication: 2010-09
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    We present a novel approach to fully automated reconstruction of tree structures in noisy 2D images. Unlike in earlier approaches, we explicitly handle crossovers and bifurcation points, and impose geometric constraints while optimizing a global cost function. We use manually annotated retinal scans to evaluate our method and demonstrate that it brings about a very substantial improvement.

  • Beam-ACO for the travelling salesman problem with time windows

     López Ibáñez, Manuel; Blum, Christian Clemens
    Computers & operations research
    Vol. 37, num. 9, p. 1570-1583
    DOI: 10.1016/j.cor.2009.11.015
    Date of publication: 2010-09
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • On the use of different types of knowledge in metaheuristics based on constructing solutions

     Mastrolilli, Monaldo; Blum, Christian Clemens
    Engineering applications of artificial intelligence
    Vol. 23, num. 5, p. 650-659
    DOI: 10.1016/j.engappai.2010.01.018
    Date of publication: 2010-08
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • A brief survey on hybrid metaheuristics

     Blum, Christian Clemens; Puchinger, Jakob; Raidl, Günther; Roli, Andrea
    Bioinspired Optimization Methods and their Applications
    p. 3-16
    Presentation's date: 2010-05
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    The combination of components from different algorithms is currently one of most successful trends in optimization. The hybridization of metaheuristics, such as ant colony optimization, evolutionary algorithms, and variable neighborhood search, with techniques from operations research and artificial intelligence plays hereby an important role. The resulting hybrid algorithms are generally labelled hybrid metaheuristics. The rising of this new research field was due to the fact that the focus of research in optimization has shifted form an algorithm-oriented point of view. In this brief survey on hybrid metaheuristics we provide an overview on some of the most interesting and representative developments.

  • Ant colony optimization for broadcasting in sensor networks under a realistic antenna model

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Bioinspired Optimization Methods and their Applications
    p. 153-162
    Presentation's date: 2010-05
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Most, if not all, works from the literature dealing with minimum energy broadcasting in wireless ad-hoc networks such as sensor networks consider antenna models that allow the adjustment of the emission power to any desired real value from zero up to the maximum sensing range. However, looking at the currently available hardware shows that these antenna models are not very realistic. In this work we therefore adapt the currently best available algorithm for minimum energy broadcasting for a more realistic antenna model which only offers few different levels of emission power. The obtained results show that this ant colony optimization algorithm performs well in comparison to a standard heuristic known from the literature.

  • Access to the full text
    Beam-ACO for the longest common subsequence problem  Open access

     Blum, Christian Clemens
    International Conference on Complex Medical Engineering
    p. 1-8
    DOI: 10.1109/CEC.2010.5585928
    Presentation's date: 2010-07
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    The longest common subsequence problem is classical string problem. It has applications, for example, in pattern recognition and bioinformatics. In this work we present a socalled Beam-ACO approach for solving this problem. Beam-ACO algorithms are hybrid techniques that results from a combination of ant colony optimization and beam search, which is an incomplete branch and bound derivative. Our results show that Beam-ACO is able to find new best solutions for 31 out of 60 benchmark instances that we chose for the experimental evaluation of the algorithm.

  • A protocol for self-synchronized duty-cycling in sensor networks: Generic implementation in Wiselib

     Hernandez Pibernat, Hugo; Baumgartner, Tobias; Blesa Aguilera, Maria Jose; Blum, Christian Clemens; Kröller, Alexander; Fekete, Sandor P.
    International Congress on Mobile Ad-hoc and Sensor Networks
    p. 1-11
    Presentation's date: 2010-12
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    In this work we present a protocol for self-synchronized duty-cycling in wireless sensor networks with energy harvesting capabilities. The protocol is implemented in Wiselib, a library of generic algorithms for sensor networks. Simulations are conducted with the sensor network simulator Shawn. They are based on the specifications of real hardware known as iSense sensor nodes. The experimental results show that the proposed mechanism is able to adapt to changing energy availabilities. Moreover, it is shown that the system is very robust against packet loss.

  • ALGORISMIA, BIOINFORMÀTICA, COMPLEXITAT I METODES FORMALS (ALBCOM)

     Orejas Valdes, Fernando; Galceran Oms, Marc; Oliva Valls, Sergi; Godoy Balil, Guillermo; Atserias Peri, Albert; Martinez Parra, Conrado; Pasarella Sanchez, Ana Edelmira; Pino Blanco, Elvira Patricia; Alvarez Faura, Maria Del Carme; Blum, Christian Clemens; Gabarro Valles, Joaquin; Cortadella Fortuny, Jordi; Molinero Albareda, Xavier; Serna Iglesias, Maria Jose; Messeguer Peypoch, Xavier; Roura Ferret, Salvador; Blesa Aguilera, Maria Jose; Valiente Feruglio, Gabriel Alejandro; Duch Brown, Amalia; Carmona Vargas, Jose; Hernandez Pibernat, Hugo; Gel Moreno, Bernat; Gascon Caro, Adrian; Petit Silvestre, Jordi; Diaz Cort, Jose Maria
    Competitive project

     Share

  • Self-synchronized duty-cycling in sensor networks with energy harvesting capabilities: the static network case

     Pibernat, Heranandez Hugo; Blum, Christian Clemens
    Genetic and Evolutionary Computation Conference
    p. 33-40
    Presentation's date: 2009-01-01
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Biological studies have shown that some species of ants rest quite large fractions of their time. Interestingly, not only sin- gle ants show this behaviour, but whole ant colonies exhibit synchronized activity phases resulting from self-organization. Inspired by this behaviour, we previously introduced an adap- tive and self-synchronized duty-cycling mechanism for mo- bile sensor networks with energy harvesting capabilities. In this paper, we focus on the study of this mechanism in the context of static sensor networks, because most sensor net- works deployed in practice are static. We consider various scenarios that result from the combination of different network topologies and sizes. Our results show that our mechanism also works in the case of static sensor networks with energy harvesting capabilities.

  • Un estudio aplicado al problema del viajante del comercio con ventanas de tiempo

     López Ibáñez, Manuel; Blum, Christian Clemens
    Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados
    p. 671-680
    Presentation's date: 2009-01-01
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Los algoritmos Beam-ACO son métodos híbridos que combinan la metaheurística de optimización basada en colonias de hormigas (Ant Colony Optimisation, ACO) con la búsqueda en haz (beam-search). Estos algotitmos dependen en gran medida de una función de estimación precisa y computacionalmente poco costosa que permita elegir entre diferentes soluciones parciales durante el proceso de construcción de soluciones. En este trabajo proponemos usar muestreo estocástico como una alternativa viable a la función de estimación para casos en los que calcular una cota fiable es demasiado costoso. Como caso aplicado, hemos elegido el conocido problema del viajante de comercio con ventanas de tiempo (Traveling Salesman Problem with Time Windows, TSPTW). Nuestros resultados demuestran claramente que Beam-ACO, aún después de reemplazar la función de estimación por el muestreo estocástico, tiene importantes ventajas sobre algoritmos ACO estándar.

  • Ant colony optimization

     Blum, Christian Clemens
    Genetic and Evolutionary Computation Conference
    p. 2825-2852
    Presentation's date: 2009
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    ◮ Origins of ACO: Swarm intelligence ◮ How to transfer the biological inspiration into an algorithm ◮ Example applications of ACO: TSP and Assembly line balancing ◮ Hybridizations of ACO algorithms with more classical techniques

  • Access to the full text
    Self-synchronized duty-cycling for mobile sensor networks with energy harvesting capabilities: A swarm intelligence study  Open access

     Pibernat, Heranandez Hugo; Blum, Christian Clemens; Middendorf, Martin; Ramsch, Kai; Scheidler, Alexander
    IEEE Swarm Intelligence Symposium
    p. 153-159
    DOI: 10.1109/SIS.2009.4937858
    Presentation's date: 2009-01-01
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    When asked if ants rest or if they work untiringly all day long, most people would probably respond that they had no idea. In fact, when watching the bustling life of an ant hill it is hard to imagine that ants take a rest from now and then. However, biologists discovered that ants rest quite a large fraction of their time. Surprisingly, not only single ants show alternate phases of resting and being active, but whole ant colonies exhibit synchronized activity phases that result from self-organization. Inspired by this self-synchronization behaviour of ant colonies, we develop a mechanism for self-synchronized duty-cycling in mobile sensor networks. In addition, we equip sensor nodes with energy harvesting capabilities such as, for example, solar cells. We show that the self-synchronization mechanism can be made adaptive depending on the available energy.

  • Asynchronous simulation of a self-synchronized duty-cycling mechanism for mobile sensor networks

     Pibernat, Heranandez Hugo; Blum, Christian Clemens
    Workshop on Bio-Inspired Algorithms for Distributed Systems
    p. 61-68
    Presentation's date: 2009-01-01
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    In previous work we introduced a self-synchronized duty-cycling mechanism for mobile sensor networks with energy harvesting capabilities, inspired by the self-synchroned sleeping patterns that can be observed in real ant colonies. The focus of our previous study was mainly on swarm intelligence aspects of the proposed system. In contrast, in this paper we propose a more realistic version of the initial system. The proposed changes concern in particular the systems’ asynchronous simulation. Instead of exchanging information at the same time, in our new proposal sensor nodes wake up periodically based on their own internal clock and perform an update of their internal state based on the information received by their neighbors. In addition we use a more realistic mobility model and apply the system to scenarios where weather conditions vary over the area of deployment. The simulation results show that our asynchronous system also permits adaptive duty-cycling, and that the system is able to adapt to changing weather conditions.

  • ACO_R híbrido con múltiples colonias para problemas de optimización continua

     Blum, Christian Clemens; Cardoso, Pedro; Herrera, Francisco
    Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados
    p. 465-472
    Presentation's date: 2009-01-01
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Este trabajo se centra en algoritmos con colonias de hormigas para resolver problemas de optimización continua. En concreto, se propone una extensión de este tipo de algoritmos hacia un método multi-colonia para incrementar la capacidad de exploración del algoritmo. Asimismo, se estudia la introducción de diferentes optimizadores de búsqueda local para mejorar las soluciones generadas por las hormigas artificiales. En este trabajo se presentas los resultados obtenidos por este modelo sobre el conjunto de funciones de prueba desarrolladas por la sesión de optimización continua del CEC’05

  • Solving the KCT Problem: Large-Scale Neighborhood Search and Solution Merging

     Blum, Christian Clemens; Blesa Aguilera, Maria Jose
    Date of publication: 2009
    Book chapter

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Hybridizing Beam-ACO with constraint programming for single machine job scheduling

     Thiruvady, Dhananjay; Blum, Christian Clemens; Meyer, Bernd; Ernst, Andreas T.
    Lecture notes in computer science
    Vol. 5818, p. 30-44
    DOI: 10.1007/978-3-642-04918-7_3
    Date of publication: 2009
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    A recent line of research concerns the integration of ant colony optimization and constraint programming. Hereby, constraint programming is used for eliminating parts of the search tree during the solution construction of ant colony optimization. In the context of a single machine scheduling problem, for example, it has been shown that the integration of constraint programming can significantly improve the ability of ant colony optimization to find feasible solutions. One of the remaining problems, however, concerns the elevated computation time requirements of the hybrid algorithm, which are due to constraint propagation. In this work we propose a possible solution to this problem by integrating constraint programming with a specific version of ant colony optimization known as Beam-ACO. The idea is to reduce the time spent for constraint propagation by parallelizing the solution construction process as done in Beam-ACO. The results of the proposed algorithm show indeed that it is currently the best performing algorithm for the above mentioned single machine job scheduling problem.

  • Beam-ACO Based on Stochastic Sampling for Makespan Optimization Concerning the TSP with Time Windows

     Lopez-Ibañez, M; Blum, Christian Clemens; Thiruvady, Dhananjay; Ernst, Andreas T.; Meyer, Bernd
    Lecture notes in computer science
    Vol. 5482, num. -, p. 97-108
    DOI: 10.1007/978-3-642-01009-5_9
    Date of publication: 2009-01
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Ant colony optimization for multicasting in static wireless ad-hoc networks

     Hernandez Pibernat, Hugo; Blum, Christian Clemens
    Swarm intelligence
    Vol. 3, num. 2, p. 125-148
    Date of publication: 2009-06
    Journal article

     Share Reference managers Reference managers Open in new window

  • Beam search for the longest common subsequence problem

     Blum, Christian Clemens; Blesa Aguilera, Maria Jose
    Computers & operations research
    Vol. 36, num. 12, p. 3178-3186
    Date of publication: 2009-12
    Journal article

     Share Reference managers Reference managers Open in new window