Fundamenta Informaticae - Volume 174, issue 3-4

Authors: Eiter, Thomas | Maratea, Marco | Vallati, Mauro

Article Type: Other

DOI: 10.3233/FI-2020-1939

Citation: Fundamenta Informaticae, vol. 174, no. 3-4, pp. i-iii, 2020

Authors: Baioletti, Marco | Di Bari, Gabriele | Milani, Alfredo | Santucci, Valentino

Article Type: Research Article

Abstract: Crossover operators are very important components in Evolutionary Computation. Here we are interested in crossovers for the permutation representation that find applications in combinatorial optimization problems such as the permutation flowshop scheduling and the traveling salesman problem. We introduce three families of permutation crossovers based on algebraic properties of the permutation space. In particular, we exploit the group and lattice structures of the space. A total of 34 new crossovers is provided. Algebraic and semantic properties of the operators are discussed, while their performances are investigated by experimentally comparing them with known permutation crossovers on standard benchmarks from four popular …permutation problems. Three different experimental scenarios are considered and the results clearly validate our proposals. Show more

Keywords: Permutation crossovers, Algebraic crossovers, Lattice operators

DOI: 10.3233/FI-2020-1940

Citation: Fundamenta Informaticae, vol. 174, no. 3-4, pp. 201-228, 2020

Authors: Chen, Qian Matteo | Finzi, Alberto | Mancini, Toni | Melatti, Igor | Tronci, Enrico

Article Type: Research Article

Abstract: In critical infrastructures like airports, much care has to be devoted in protecting radio communication networks from external electromagnetic interference. Protection of such mission-critical radio communication networks is usually tackled by exploiting radiogoniometers: at least three suitably deployed radiogoniometers, and a gateway gathering information from them, permit to monitor and localise sources of electromagnetic emissions that are not supposed to be present in the monitored area. Typically, radiogoniometers are connected to the gateway through relay nodes . As a result, some degree of fault-tolerance for the network of relay nodes is essential in order to offer a …reliable monitoring. On the other hand, deployment of relay nodes is typically quite expensive. As a result, we have two conflicting requirements: minimise costs while guaranteeing a given fault-tolerance. In this paper, we address the problem of computing a deployment for relay nodes that minimises the overall cost while at the same time guaranteeing proper working of the network even when some of the relay nodes (up to a given maximum number) become faulty (fault-tolerance ). We show that, by means of a computation-intensive pre-processing on a HPC infrastructure, the above optimisation problem can be encoded as a 0/1 Linear Program, becoming suitable to be approached with standard Artificial Intelligence reasoners like MILP, PB-SAT, and SMT/OMT solvers. Our problem formulation enables us to present experimental results comparing the performance of these three solving technologies on a real case study of a relay node network deployment in areas of the Leonardo da Vinci Airport in Rome, Italy. Show more

DOI: 10.3233/FI-2020-1941

Citation: Fundamenta Informaticae, vol. 174, no. 3-4, pp. 229-258, 2020

Authors: Oddi, Angelo | Rasconi, Riccardo

Article Type: Research Article

Abstract: In this work we investigate the performance of greedy randomised search (GRS) techniques to the problem of compiling quantum circuits to emerging quantum hardware. Quantum computing (QC) represents the next big step towards power consumption minimisation and CPU speed boost in the future of computing machines. Quantum computing uses quantum gates that manipulate multi-valued bits (qubits ). A quantum circuit is composed of a number of qubits and a series of quantum gates that operate on those qubits, and whose execution realises a specific quantum algorithm. Current quantum computing technologies limit the qubit interaction distance allowing the execution of …gates between adjacent qubits only. This has opened the way to the exploration of possible techniques aimed at guaranteeing nearest-neighbor (NN) compliance in any quantum circuit through the addition of a number of so-called swap gates between adjacent qubits. In addition, technological limitations (decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized. One core contribution of the paper is the definition of two lexicographic ranking functions for quantum gate selection, using two keys: one key acts as a global closure metric to minimise the solution makespan; the second one is a local metric, which favours the mutual approach of the closest qstates pairs. We present a GRS procedure that synthesises NN-compliant quantum circuits realizations, starting from a set of benchmark instances of different size belonging to the Quantum Approximate Optimization Algorithm (QAOA) class tailored for the MaxCut problem. We propose a comparison between the presented meta-heuristics and the approaches used in the recent literature against the same benchmarks, both from the CPU efficiency and from the solution quality standpoint. In particular, we compare our approach against a reference benchmark initially proposed and subsequently expanded in [1] by considering: (i) variable qubit state initialisation and (ii) crosstalk constraints that further restrict parallel gate execution. Show more

Keywords: Quantum Computing, Optimization, Scheduling, Planning, Greedy Heuristics, Random Algorithms

DOI: 10.3233/FI-2020-1942

Citation: Fundamenta Informaticae, vol. 174, no. 3-4, pp. 259-281, 2020

Authors: Sinisi, Stefano | Alimguzhin, Vadim | Mancini, Toni | Tronci, Enrico | Mari, Federico | Leeners, Brigitte

Article Type: Research Article

Abstract: In Silico Clinical Trials (ISCT), i.e. clinical experimental campaigns carried out by means of computer simulations, hold the promise to decrease time and cost for the safety and efficacy assessment of pharmacological treatments, reduce the need for animal and human testing, and enable precision medicine. In this paper we present methods and an algorithm that, by means of extensive computer simulation-based experimental campaigns (ISCT) guided by intelligent search, optimise a pharmacological treatment for an individual patient (precision medicine ). We show the effectiveness of our approach on a case study involving a real pharmacological treatment, namely the downregulation …phase of a complex clinical protocol for assisted reproduction in humans. Show more

Keywords: Artificial Intelligence, Virtual Physiological Human, In Silico Clinical Trials, Simulation, Personalised Medicine, In Silico Treatment Optimisation

DOI: 10.3233/FI-2020-1943

Citation: Fundamenta Informaticae, vol. 174, no. 3-4, pp. 283-310, 2020

Authors: Wallace, Richard J.

Article Type: Research Article

Abstract: Algorithms based on singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. Such consistencies, despite their partial character, are still …well-characterized in that algorithms have unique fixpoints. Heuristic strategies for choosing an effective subset of variables are described and tested, the best being choice by highest degree and a more complex strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as the corresponding full version of the algorithm in terms of values discarded or problems proven unsatisfiable, while significantly reducing the effort required to achieve this. Show more

DOI: 10.3233/FI-2020-1944

Citation: Fundamenta Informaticae, vol. 174, no. 3-4, pp. 311-344, 2020