Christian Blum, PhD
Senior Research Scientist
Artificial Intelligence Research Institute (IIIA)
Spanish National Research Council (CSIC)

Menu

Home
Research
Teaching
Journal Publications
Contact me





ORCID iD iconorcid.org/0000-0002-1736-3559

  Curriculum Vitae
Download PDF
  DBLP entries
  Google Scholar Citations

Research Interests

My research interests are twofold: On one side I am interested in swarm intelligence, which is an artificial intelligence discipline based on the inspiration taken, for example, from the collective behaviour of social insects, flocks of birds, and fish schools. On the other side I am also interested in the hybridization of metaheuristics with more classical artificial intelligence and operations research methods such as, for example, branch and bound techniques and dynamic programming.

I am making use of swarm intelligence concepts both for solving challenging combinatorial optimization problems and for problem solving in distributed enviroments such as adhoc and sensor networks. Well-known swarm intelligence algorithms for combinatorial optimization are ant colony optimization (ACO) and particle swarm optimization (PSO). In distributed environments I have lately made use of the self-organization of natural ant colonies for obtaining synchronized sleep-wake periods, and the self-desynchronization of the calling periods of Japanese tree frogs. Concerning the second research line, I am currently working mainly on two different types of hybridization. First, the hybridization of metaheuristics based on the construction of solutions with concepts from branch and bound. Second, I am working on the development of efficient large neighborhood search algorithms.

Concerning applications, my work has a strong interdisciplinary flavour. In fact, optimization and control tasks arise in many important application areas such as telecommunications, bio-informatics, neuroscience, and robotics. A representative example of recent interdisciplinary work concerns the colboration with the Computer Vision Lab of the EPFL (Lausanne, Switzerland) on the automated reconstruction of dentritic and axonal trees. Concerning the bio-informatics (respectively, bio-medical) field, some of my work has focused on DNA sequencing, the training of neural networks for medical pattern classification, and on the founder sequence reconstruction problem.

Important lines of my work are shortly summarized below.

Hybrid Metaheuristics

Concerning the hybridization of metaheuristics with other techniques for optimization I am mainly working on two different types of hybrids. The first one is known as Beam-ACO. This is an algorithm that results from the combination of ant colony optimization with beam search, a branch and bound derivative. The second hybrid is known as large neighborhood search, which is a special type of local search that uses a complete method for exploring large-scale neighborhoods. The following two papers are recent examples for this line of research.

Swarm Intelligence

Some of my recent work in swarm intelligence makes use of the self-synchronization observed in natural ant colonies for obtaining a mechanism for self-organized duty-cycling in sensor networks. Another example concerns the use of the calling behaviour of Japanese tree frogs for graph coloring.

Applications

Apart from classical operations research applications, I have recently focused on interesting applications in wireless sensor networks and from the bioinformatics field. An interdisciplinary application from the Neuroscience field is shortly described in the following.

Tree-like structures, such as dendritic, vascular, or bronchial networks, are pervasive in biological systems. Despite of many years of work towards automated delineation techniques, the existing techniques remain fragile and error-prone. In this work, we use 3D optical micrographs of neurons and 2D retinal fundus images to demonstrate the importance of taking global tree structure and geometry into account to improve topological accuracy of the delineations.

The approach that we propose is based on ant colony optimization. It builds a set of candidate trees over many different subsets of points likely to belong to the optimal delineation and then chooses the best one according to a global objective function that combines image evidence with geometric priors.

More information can be otained at http://cvlab.epfl.ch/research/medical/lm/.

Survey Papers

Problem Instances

For the purpose of the experimental evaluation of developed algorithms we frequently generate new sets of problem instances for diverse combinatorial optimization problems. Some of them are provided in the following.

  • Travelling Salesman Problem with Time Windows (TSPTW): Manuel López Ibáñez maintains a nice website providing a lot of information about this problem. Moreover, he offers the problem instances used in our paper for downloading.

  • Minimum Weight Vertex Cover (MWVC) Problem: graphs. The format of all files is as follows: the first line contains the number of nodes of the graph, the second line contains the node weights, and the remaining lines contain the incidence matrix. Moreover, note that the files containing ds in the file name, are the instances of so-called type II. These instances were used in this paper, published in Applied Soft Computing in 2012.

  • Firefighter (FF) Problem: random graphs, random geometric graphs. The format of all files is the DIMACS graph format. These instances were used in this paper, published in Computers and Operations Research in 2015.

  • Minimum Weight Dominating Set (MWDS) Problem: graphs. The format of all files is as follows: the first line contains the number of nodes of the graph. Then, for each node there is one line with its weight. Finally, for each edge there is one line with the two vertices that the edge connects (note that vertex indices range from 0 to n-1). These instances were used in this paper, published in Simulation Modelling Practice and Theory in 2016.

  • Minimum Common String Partition (MCSP): file containing all problem instances. Each file simply contains the two input strings. These instances were used in this paper, published in Computers and Operations Research in 2016. The names of the files indicate unambiguously to which instances in the paper they correspond.

  • Weighted Independent Domination Problem (WIDP): random graphs, random geometric graphs. The format of all files is as follows: the first line contains the number of nodes and the number of edges. Then, there is one line for each node, providing the node weight. Finally, there is one line for each edge, containing the node identifiers and the edge weight. These instances were used in this paper, which is in press at European Journal of Operational Research.

  • Repetition-Free Longest Common Subsequence (RFLCS) Problem: file containing Set1 and Set2 instances. The format of all files is as follows: the first line contains the number of input strings (this is 2 in all cases) and the alphabet size. Then, there are two lines for each input string. The first line indicates the length of the corresponding input string, and the second line contains the input string itself in terms of a sequence of integers from {0,...,alphabet_size - 1}. These instances were used in this paper, published in Journal of Heuristics in 2017. The names of the files indicate unambiguously to which instances in the paper they correspond.

  • Longest Arc Preserving Common Subsequence (LAPCS) Problem: random instances, real instances. The format of all files is as follows: the first line contains the number of input sequences (which is always 2) and the alphabet size. Then, for each of the input sequences the following information is provided. The first line contains the length of the sequence and the sequence itself. The second line provides the number of arcs (say X). Then there are X lines with the information for each arc: the left position and the right position.

  • Most Strings With Few Bad Columns (MSFBC) Problem: all problem instances. The files are organized in directories. At the first level they are split according to alphabet size. At the second level they are separated according to number of input strings and their length. The name of each file indicates, first, the number of input strings, then the length of the input strings, and then the alphabet size. Each file simply contains in the first line the alphabet size, and then one string per line. These instances were used in this paper, published in Soft Computing in 2017.

Software

Occasionally we provide executables of our optimization software (programmed in C++ and compiled under Ubuntu 14.04).


Webdesign: Logo design web | web hosting guide | stock photos
Design downloaded from FreeWebTemplates.com
Free web design, web templates, web layouts, and website resources!