Category: Journals

New Paper on Hybrid Metaheuristics for the Template Design Problem

The Template Design Problem (TDP) arises in the area of manufacturing and entails finding the best way of mass producing a collection of different packagings, i.e., trying to minimize the usage of raw materials. This entails determining a number of printing patterns/templates, which results in a combinatorial optimization problem plagued with symmetries (that is, an internal reordenation of designs within a template or the reordenation of templates thmeselves results in an equivalent solution).

To tackle these issues we have considered the use of alternative representations within the context of memetic algorithms. Our findings have been published in the paper:

The paper is freely accessible in the link above, and its abstract follows:

The template design problem (TDP) is a hard combinatorial problem with a high number of symmetries which makes solving it more complicated. A number of techniques have been proposed in the literature to optimise its resolution, ranging from complete methods to stochastic ones. However, although metaheuristics are considered efficient methods that can find enough-quality solutions at a reasonable computational cost, these techniques have not proven to be truly efficient enough to deal with this problem. This paper explores and analyses a wide range of metaheuristics to tackle the problem with the aim of assessing their suitability for finding template designs. We tackle the problem using a wide set of metaheuristics whose implementation is guided by a number of issues such as problem formulation, solution encoding, the symmetrical nature of the problem, and distinct forms of hybridisation. For the TDP, we also propose a slot-based alternative problem formulation (distinct to other slot-based proposals), which represents another option other than the classical variation-based formulation of the problem. An empirical analysis, assessing the performance of all the metaheuristics (i.e., basic, integrative and collaborative algorithms working on different search spaces and with/without symmetry breaking) shows that some of our proposals can be considered the state-of-the-art when they are applied to specific problem instances.

Special Issue of Swarm Evol. Comput. on Memetic Computing

Swarm and Evolutionary ComputationSwarm and Evolutionary Computation
(JCR 6.330, Q1 COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE)
ISSN: 2210-6502
Elsevier

Overview

For at least the last three decades of the field of Evolutionary Computing, a growing number of researchers have focused their efforts on combining different methods and functionalities into a single solver. In general, the aim was to overcome disadvantages of some individual solvers and/or to improve the performance rendered by off-the-shelf optimization methods. In this regard, Memetic Algorithms (MA) spearhead this design principle by exploiting the synergies of individual search procedures in evolutionary optimization frameworks leading to development of the Memetic Computing (MC) field. Since its inception by Moscato and Norman in late ’80s, MC has blossomed into a manifold of algorithmic variants, to yield one of the most prolific areas within Swarm Intelligence and Evolutionary Computation to date. Indeed, MC have been growing fast to yield complex techniques with extremely sophisticated exploitation and cooperation mechanisms. A variety of MAs continue to use Evolutionary/Bio-inspired/Swarm Intelligence approaches for global optimization (both combinatorial and non-linear or mixed) with separate individual improvement and adaptive or learning mechanisms, generally incorporating domain-specific knowledge for the problem under analysis.

Scope

This special issue aims at disseminating the latest findings and research achievements in MAs, with a special attention paid to contributions focused on problem-dependent individual/local search methods and solutions. We also welcome theoretical research ideas and their application to real-world problems. To this end, we solicit high-quality original submissions to this special issue that reflect the unprecedented momentum garnered by this research area.

Topics

Topics of interest include, but are not limited to:

  • Recent advances on the combination of population-based global optimization solvers with problem-dependent local search procedures.
  • Real-world applications of Memetic Computation and Memetic Algorithms.
  • Evidences of the applicability of Memetic Algorithms and Memetic Computing to emerging paradigms such as Large-Scale Global Optimization, Transfer Optimization or Neuroevolution.
  • Novel insights of Memetic Computing applied to multi- and many-objective optimization.
  • Memetic Algorithms for symbolic regression and time-series prediction.
  • Complete Anytime Memetic Algorithms (MAs that can deliver feasible solutions if stopped but that will stop by themselves if they have found the optimal solution).
  • New findings on memetic transmission, design selection and design patterns.
  • Advances on co-evolving methods and self-adaptive memetic schemes.
  • Theoretical and practical studies exploring the balance between exploration and exploitation in MAs.
  • New procedures for detecting and quantifying the level of stagnation on MAs, and novel trends for enhancing diversification.

Submission

Submitted papers should be original and are not be under consideration elsewhere for publication. Prospective authors should follow the journal guidelines, regarding the manuscript content and its format when preparing their manuscripts. All papers will be reviewed by at least three independent reviewers for their suitability in terms of technical novelty, scientific rigor, scope, and relevance to this special issue. When submitting papers, please select Article Type “VSI: Memetic Computing”

Important Dates

  • June 1, 2020: Call for papers.
  • August 1, 2020: Deadline for Initial Paper Submission.
  • November 1, 2020: Notification of First Round Decision.
  • December 15, 2020: Deadline for Revised Paper Submission.
  • February 15, 2021: Final acceptance decision.
  • June 1, 2021: Target publication date.

Guest Editors

New paper on the placement of suicide bomber detectors using metaheuristics

Suicide bombing is one of the prevalent ways in which terrorist organizations substantiate their infamous actions. The defense from this kind of attacks is a highly cross-disciplinary endeavor that can be approached from many points of views. From a tactical point of view, it is often useful to analyze it from a political-rational perspective, that is, using a cost-benefit analysis analogous to the rational calculations of a military staff or a corporate board.

Some works in the literature have taken some steps in this direction. We have built on our previous research in which we focused on the problem of determining the distribution of detectors on a given area under threat, aiming to maximize the probability of detecting and neutralizing suicide bombers. This problem, seminally approached by greedy techniques in the literature, was tackled with metaheuristics in our work

As in the previous literature, the simplistic assumption that the terrorist attacker would pick a certain target and the path to reach it uniformly at random was used. We have taken a step beyond this premise, and considered the problem from two perspectives. In the first one, the terrorist attacker takes weighted decisions based on the relative importance of each target. In the second one, we take a game-theory perspective: two parties are involved, the attacker and the defender; the defender tries to place detectors so as to minimize the inflicted damage received by the attacker; conversely the attacker tries to select the target and the path to reach it so as to maximize this inflicted damage, knowing that the defender will try to negate these attempts. From the point of view of the defender that has to place the detectors, this amounts to minimize losses in a worst-case scenario.

Springer's Natural ComputingWe have approached the resulting problem in a recent paper entitled

considering hill climbing, tabu search and evolutionary algorithms. The evolutionary algorithms reveals itself as particularly well-adapted for this problem when the worst-case perspective (which provides a more challenging optimization scenario) is used. The full abstract of the paper follows:

We consider an operational model of suicide bombing attacks –an increasingly prevalent form of terrorism– against specific targets, and the use of protective countermeasures based on the deployment of detectors over the area under threat. These detectors have to be carefully located in order to minimize the expected  number of casualties or the economic damage suffered, resulting in a hard  optimization problem for which different metaheuristics have been proposed.  Rather than assuming random decisions by the attacker, the problem is approached by considering different models of the latter, whereby he takes informed decisions on which objective must be targeted and through which path it has to be reached based on knowledge on the importance or value of the objectives or on the defensive strategy of the defender (a scenario that can be regarded as an adversarial game). We consider four different algorithms, namely a greedy heuristic, a hill climber, tabu search and an evolutionary algorithm, and study their performance on a broad collection of problem instances trying to resemble different realistic settings such as a coastal area, a modern urban area, and the historic core of an old town. It is shown that the adversarial scenario is harder for all techniques, and that the evolutionary algorithm seems to adapt better to the complexity of the resulting search landscape.