IEEE Transactions on Neural Networks and Learning Systems, Accepted for publication, 2016.
Manuscript Number: TNNLS-2015-P-5760
Print ISSN: 2162-237X
Online ISSN: 2162-2388
Digital Object Identifier: 10.1109/TNNLS.2016.2537300
URL: DOI: 10.1109/TNNLS.2016.2537300
PDF preprint:
battiti-blm-ieee-tnnls.pdf
bb2016ijcnn
Mauro Brunato and Roberto Battiti
X-MIFS: Exact Mutual information for Feature
Selection
Proc. 2016 International Joint Conference on Neural Networks (IJCNN) , July 24-29, Vancover, Canada, 2016, pages 3469-3476
PDF:
(preprint) battiti-wcci2016.pdf
978-1-5090-0620-5/16/2016 IEEE
bb2016informatica
Mauro Brunato and Roberto Battiti
CoRSO (Collaborative Reactive Search Optimization):
Blending Combinatorial and Continuous Local Search
INFORMATICA, 2016, Vol. 27, No. 2, pages 299-322
DOI: http://dx.doi.org/10.15388/Informatica.2016.86
PDF:
(local preprint copy) informatica-2016.pdf
The-LION-way-book
The LION way. Machine Learning plus Intelligent Optimization.
R. Battiti and M. Brunato
LIONlab, University of Trento, Italy, Version 2.0, Apr 2015.
BibTex:
@book{LIONway2015
author = "Roberto Battiti and Mauro Brunato",
title = "The LION way. Machine Learning {\em plus} Intelligent Optimization",
publisher = "LIONlab, University of Trento, Italy",
year = "2014",
isbn = "978-14-960340-2-1"
}
Reactive-Search-And-Intelligent-Optimization-Book
Reactive Search and Intelligent Optimization, by R. Battiti, M. Brunato and F. Mascia
Abstract:
This book is about learning for problem solving. [...]
Human problem solving is strongly connected to learning.
Learning takes places when the problem at hand is not well known
at the beginning, and its structure becomes more and more clear
when more experience with the problem is available. [...]
What is critical for men is critical also in many human-developed
problem solving strategies. It is not surprising that many methods for
solving problems in Artificial Intelligence, Operations Research
and related areas, follow the search scheme [...]
We aim at giving the main principles and at developing some fresh
intuition for the approaches. We like mathematics but we also
think that hiding the underlying motivations and sources of
inspiration takes some color out of the scientific work [...].
On the other hand, pictures and hand-waving can be very dangerous
in isolation and we try to avoid these pitfalls by giving also
the basic equations when possible, or by at least directing the
reader to the bibliographic references for deepening a topic.
The point of view of the book is to look at the zoo of different
optimization beasts to underline opportunities for learning and self-tuning strategies.
(From the Introduction)
BibTex:
@BOOK{BBM2008,
AUTHOR = {Roberto Battiti and Mauro Brunato and Franco Mascia},
TITLE = {Reactive Search and Intelligent Optimization},
PUBLISHER = {Springer Verlag},
YEAR = {2008},
series = {Operations research/Computer Science Interfaces},
note = {ISBN: 978-0-387-09623-0},
ulr = {http://www.springer.com/978-0-387-09623-0}
}
Preprint of book (PDF) Reactive-Search-and-Intelligent-Optimization-Battiti-Brunato-Mascia-preprint.pdf
bb2015ijcnn
Mauro Brunato and Roberto Battiti
Stochastic Local Search for Direct Training of Threshold Networks
Proc. 2015 International Joint Conference on Neural Networks , pag. 1-8, 2015.
journal link ( DOI:
10.1109/IJCNN.2015.7280770 )
PDF:
(local copy) battiti-ijcnn2015.pdf
Link to IJCNN Conference:
IJCNN 2015 - Killarney
ZHANG2014
Liangjun Ke, Qingfu Zhang and Roberto Battiti
Hybridization of Decomposition and Local Search
for Multiobjective Optimization
IEEE Transaction on Cybernetics , vol. 44, no. 10, October 2014, pag. 1808-1820.
DOI: 10.1109/TCYB.2013.2295886
PDF:
(local cache copy) hybridization-2014.pdf
Link to IEEE publication:
IEEE Xplore Digital Library
ICDM2013
Duy Tin Truong, Roberto Battiti and Mauro Brunato
Discovering Non-Redundant Overlapping Biclusters on Gene Expression Data,
Proceedings The IEEE 13th International Conference on Data Mining series (ICDM 2013) ,
Dallas, Texas / December 7-10, 2013, pages 747-756.
IEEE Computer Society .
DOI 10.1109/ICDM.2013.36
PDF proofs:
biclustering-icdm2013.pdf
MICS2013-BP
Dinara Mukhlisullina, Andrea Passerini, Roberto Battiti
Learning to diversify in complex interactive Multiobjective
Optimization
Best Paper Award
MIC 2013: The X Metaheuristics International Conference
, Singapore, Aug 5-8, 2013, Singapore.
MIC 2013 website
PDF (preprint)
MIC-BEST-paper.pdf
MICS2013-ALPI
Paolo Campigotto, Andrea Passerini, and Roberto Battiti
Active learning of Pareto fronts with disconnected feasible
decision and objective spaces
MIC 2013: The X Metaheuristics International Conference
, Singapore, Aug 5-8, 2013, Singapore.
MIC 2013 website
PDF (preprint)
MIC-ALPI.pdf
TNNLS2013
Paolo Campigotto, Andrea Passerini, and Roberto Battiti
Active learning of Pareto fronts
IEEE Transactions on Neural Networks and Learning Systems
,
Volume:25 , Issue: 3,
March 2014
Page(s):
506 - 519
ISSN :
2162-237X
INSPEC Accession Number:
14111769
Digital Object Identifier: 10.1109/TNNLS.2013.2275918
PDF (preprint)
alp-2014.pdf
Abstract:
This work introduces the Active Learning of Pareto
fronts (ALP) algorithm, a novel approach to recover the Pareto
front of a multi-objective optimization problem. ALP casts the
identification of the Pareto front into a supervised machine
learning task. This approach enables an analytical model of the
Pareto front to be built. The computational effort in generating
the supervised information is reduced by an active learning
strategy. In particular, the model is learnt from a set of informative
training objective vectors. The training objective vectors
are approximated Pareto-optimal vectors obtained by solving
different scalarized problem instances. The experimental results
show that ALP achieves an accurate Pareto front approximation
with a lower computational effort than state-of-the-art Estimation
of Distribution Algorithms and widely-known genetic techniques.
TB2013
Duy Tin Truong and Roberto Battiti
A flexible cluster-oriented alternative clustering
algorithm for choosing from the Pareto front of solutions
Machine Learning
, Accepted: 3 April 2013.
Published online: 24 April 2013 at (springer.com) DOI 10.1007/s10994-013-5350-y
PDF (preprint)
cognac_journal.pdf
Abstract:
Supervised alternative clustering is the problem of finding a set of clusterings which are of high quality
and different from a given negative clustering. The task is therefore a clear multi-objective optimization
problem. Optimizing two conflicting objectives at the same time requires dealing with trade-offs. Most
approaches in the literature optimize these objectives sequentially (one objective after another one)
or indirectly (by some heuristic combination of the objectives). Solving a multi-objective optimization
problem in these ways can result in solutions which are dominated, and not Pareto-optimal. We develop a
direct algorithm, called COGNAC, which fully acknowledges the multiple objectives, optimizes them directly
and simultaneously, and produces solutions approximating the Pareto front. COGNAC performs the recombination
operator at the cluster level instead of at the object level, as in the traditional genetic algorithms.
It can accept arbitrary clustering quality and dissimilarity objectives and provides solutions dominating
those obtained by other state-of-the-art algorithms. Based on COGNAC, we propose another algorithm called
SGAC for the sequential generation of alternative clusterings where each newly found alternative clustering
is guaranteed to be different from all previous ones. The experimental results on widely used benchmarks
demonstrate the advantages of our approach.
Index Terms: Alternative clustering, Multi-objective optimization, Cluster-oriented recombination Genetic algorithms
TBB2013
Duy Tin Truong, Roberto Battiti and Mauro Brunato
A Repeated Local Search Algorithm
for BiClustering of Gene Expression Data
In: E. Hancock and M. Pelillo (Eds.): Proceedings of SIMBAD 2013, LNCS 7953, pp. 281-296, 2013.
, Springer Verlag.
PDF (preprint)
simbad-2013.pdf
Abstract:
Given a gene expression data matrix where each cell is the
expression level of a gene under a certain condition, biclustering is the
problem of searching for a subset of genes that coregulate and coexpress
only under a subset of conditions. The traditional clustering algorithms
cannot be applied for biclustering as one cannot measure the similarity
between genes (or rows) and conditions (or columns) by normal geometric
similarities. Identifying a network of collaborating genes and a subset of
experimental conditions which activate the specific network is a crucial
part of the problem. In this paper, the BIClustering problem is solved
through a REpeated Local Search algorithm, called BICRELS. The
experiments on real datasets show that our algorithm is not only fast
but it also significantly outperforms other state-of-the-art algorithms.
Index Terms: biclustering, co-clustering, local search, gene expression,
microarray.
KZB2012
Liangjun Ke, Qingfu Zhang, and Roberto Battiti
MOEA/D-ACO: A Multiobjective Evolutionary Algorithm Using Decomposition and Ant Colony
IEEE Transaction on Cybernetics ,
VOL. 43, NO. 6, DECEMBER 2013, pag. 1845-1859.
Digital Object Identifier 10.1109/TSMCB.2012.2231860
10.1109/TSMCB.2012.2231860
IEEE Explore
PDF (local cache copy)
ACOD-published.pdf
Abstract:
Combining ant colony optimization (ACO) and
multiobjective evolutionary algorithm based on decomposition
(MOEA/D), this paper proposes a multiobjective evolutionary
algorithm, MOEA/D-ACO. Following other MOEA/D-like algorithms,
MOEA/D-ACO decomposes a multiobjective optimization
problem into a number of single objective optimization problems.
Each ant (i.e. agent) is responsible for solving one subproblem.
All the ants are divided into a few groups and each ant has several
neighboring ants. An ant group maintains a pheromone matrix
and an individual ant has a heuristic information matrix. During
the search, each ant also records the best solution found so far
for its subproblem. To construct a new solution, an ant combines
information from its group's pheromone matrix, its own heuristic
information matrix and its current solution. An ant checks the
new solutions constructed by itself and its neighbors, and updates
its current solution if it has found a better one in terms of
its own objective. Extensive experiments have been conducted
in this paper to study and compare MOEA/D-ACO with other
algorithms on two set of test problems. On the multiobjective 0-1
knapsack problem, MOEA/D-ACO outperforms MOEA/D-GA on
all the nine test instances. We also demonstrate that the heuristic
information matrices in MOEA/D-ACO are crucial to the good
performance of MOEA/D-ACO for the knapsack problem. On the
biobjective traveling salesman problem, MOEA/D-ACO performs
much better than BicriterionAnt on all the 12 test instances.
We also evaluate the effects of grouping, neighborhood and the
location information of current solutions on the performance
of MOEA/D-ACO. The work in this paper shows that reactive
search optimization scheme, i.e., the "learning while optimizing"
principle, is effective in improving multiobjective optimization
algorithms.
Index TermsAnt colony optimization (ACO) , decomposition , multiobjective 0-1 knapsack problem (MOKP) ,
multiobjective optimization , multiobjective traveling salesman problem (MTSP) , reactive search optimization (RSO).
TB2012
Duy Tin Truong, Roberto Battiti
A Cluster-Oriented Genetic Algorithm for Alternative Clustering
Proceedings The IEEE International Conference on Data Mining series (ICDM 2012) ,
Bruxelles, Belgium, Dec 10-13, 2012.
PDF proofs:
PID2565417.pdf
Abstract:
Supervised alternative clusterings is the problem
of finding a set of clusterings which are of high quality and
different from a given negative clustering. The task is therefore
a clear multi-objective optimization problem. Optimizing two
conflicting objectives requires dealing with trade-offs. Most
approaches in the literature optimize these objectives sequentially
or indirectly, resulting in solutions which are dominated.
We develop a multi-objective algorithm, called COGNAC, able
to optimize the objectives directly and simultaneously and
producing solutions approximating the Pareto front. COGNAC
performs the recombination operator at the cluster level instead
of the object level as in traditional genetic algorithms. It can
accept arbitrary clustering quality and dissimilarity objectives
and provide solutions dominating those of other state-of-the-art
algorithms. COGNAC can also be used to generate a sequence
of alternative clusterings, each of which is guaranteed to be
different from all previous ones.
Keywords: alternative clustering; multi-objective optimization;
cluster-oriented; genetic algorithm.
Reactive-Business-Intelligence-book
Reactive Business Intelligence. From Data to Models to Insight.
R. Battiti and M. Brunato,
Reactive Search Srl, Italy, February 2011.
ISBN: 978-88-905795-0-9
Abstract:
It is obvious, you can see it! Think about how many times you intuitively associate clarity and real
understanding with vision. The word intelligence itself derives from the Latin verb intelligere (coming
from intus legere, "reading into something," a close cousin of "insight"), again related to reading and
seeing. Humans are innately visual creatures and a big portion of our brain is devoted to processing
visual information. Our ancestors needed to be very fast to identify predators in the jungle and to react
accordingly. They did not survive and transmit genes if they did not. We need to be very fast to transform
huge amounts of information into insight, knowledge, engineering designs, choices, decisions.
We decided to unite in this book aspects related to modeling and aspects related to visualizing data
and models. We are concerned with explanations of our world which can be used, used to predict, used
to build tools. This means measuring objects and events, mining and analyzing massive amounts of
data, and discovering interesting relationships emerging from the data. Visual analytics is a term used
to denote analytical reasoning facilitated by interactive visual interfaces. The effort is surely related to
data mining, the process of automatically extracting interesting patterns from massive amounts of data.
We prefer the term Reactive Business Intelligence (RBI) to underline its practical orientation and
the fast reaction implied by two basic learning components, one connecting the user to the software, a
second one internal to the software, through automated and intelligent self-tuning methods. A connection
between visualization and problem-solving strategies is also at the heart of RBI: the decision maker
can be, and should be, in an interactive loop, rapidly reacting to first results and visualizations to direct
the subsequent efforts to suit his needs and preferences.
(From the Introduction)
The material in this book is now extended and updated in our
LION way but pls contact me
if you are still interested in this particular book.
BB2011
Mauro Brunato and Roberto Battiti
R-evo: A Reactive Evolutionary Algorithm
for the Maximum Clique Problem
IEEE Transactions on Evolutionary Computation ,
Volume: 15 Issue:6,
page(s): 770-782,
ISSN: 1089-778X,
Digital Object Identifier: 10.1109/TEVC.2010.2043363,
December 2011.
link to IEEE Transactions on Evolutionary Computation paper
PDF proofs:
revo-2011.pdf
Abstract: see also AbstractPlus
An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem.
In the framework of estimation-of-distribution algorithms, guided mutation uses a model distribution to generate offspring
by combining the local information of solutions found so far with global statistical information. Each individual
is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure
that it represents a legal clique. A novel reactive and evolutionary algorithm R-EVO proposed in this paper starts
from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by
local search with memory, according to the reactive search optimization (RSO) principles. In particular,
the estimated distribution is used to periodically initialize the state of each individual based on the previous
statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution
concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably
robust with respect to the setting of the algorithm parameters. R-EVO adopts a drastically simplified
low-knowledge version of reactive local search (RLS), with a simple internal diversification mechanism
based on tabu-search, with a prohibition parameter proportional to the estimated best clique size.
R-EVO is competitive with the more complex full-knowledge RLS-EVO that adopts the original RLS algorithm.
For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G
for comparable or a smaller central processing unit time.
BBlum2010
C. Blum and R. Battiti (Eds.)
Proceedings of Learning and Intelligent OptimizatioN
LION 4, Jan 18-22, 2010, Venice, Italy.
Lecture Notes in Computer Science
Volume 6073, 2010, DOI: 10.1007/978-3-642-13800-3, pag. 232-246
Digital version available:
SpringerLink site
CPB2010
Paolo Campigotto, Andrea Passerini and Roberto Battiti
Handling concept drift in preference learning for
interactive decision making.
Proceedings of HaCDAIS 2010:
International Workshop on Handling Concept Drift
in Adaptive Information Systems, Barcelona, Spain, Sep 2010.
Mykola Pechenizkiy
and
Indre Zliobaite (Eds.), pag. 29-40. (online publications)
Digital version available:
hacdais2010.pdf ,
workshop page .
BACA2011
Roberto Battiti and Paolo Campigotto
An Investigation of Reinforcement Learning for
Reactive Search Optimization.
Youssef Hamadi and
Eric Monfroy (Eds.)Autonomous Search, Springer Verlag, 2011.
Digital version available:
autonomous-chapter10.pdf
CAPABA2011
Paolo Campigotto, Andrea Passerini, and Roberto Battiti
Active Learning of Combinatorial Features for
Interactive Optimization.
Proceedings of LION5, Learning and Intelligent OptimizatioN, Rome - Italy, Jan 17-21, Springer Verlag,
(Editor Carlos A.Coello Coello), volume 6683, series: Lecture Notes in Computer Science, 2011, pages 336-350.
link to Springer book ,
link to Springer book paper ,
Digital version available:
LION5-campigotto-pub.pdf
PRIB2010
Stefano Teso1, Cristina Di Risio, Andrea Passerini, and Roberto Battiti
An On/Off Lattice Approach to Protein
Structure Prediction from Contact Maps.
. Proceedings Pattern Recognition in Bioinformatics (PRIB2010),
Lecture Notes in Bioinformatics (LNBI), 2010
Digital version available:
prib2010.pdf
BB2010b
Roberto Battiti and Paolo Campigotto
Reactive Search Optimization: Learning While Optimizing. An
Experiment in Interactive Multi-Objective Optimization.
Proceedings of MIC2009, VIII Metaheuristic International Conference, 2010.
Digital version available:
mic2009.pdf
BBc2010
R. Battiti and M. Brunato
Reactive Search Optimization: Learning while Optimizing
Michel Gendreau and Jean-Yves Potvin (Eds.), Handbook of Metaheuristics (2nd edition),
Series: International Series in Operations Research & Management Science, Vol. 146, 2010.
Springer Science+Business Media, LLC 2010, pag. 543--571.
DOI 10.1007/978-1-4419-1665-5_18
Digital version available:
handbook2009.pdf ,
Springer link
BP2010
Roberto Battiti and Andrea Passerini
Brain-Computer Evolutionary Multi-Objective
Optimization (BC-EMO): a genetic algorithm
adapting to the decision maker
IEEE Transactions on Evolutionary Computation, Vol. 14, Issue 15, pag. 671 - 687, 2010. Digital Object Identifier : 10.1109/TEVC.2010.2058118
PDF proofs:
bcemo.pdf
BC-EMO.tgz
Software for Brain-Computer Evolutionary Multi-Objective Optimization (BC-EMO): a genetic
algorithm adapting to the decision maker.
BB2010-IEEETEVO
R. Battiti and M. Brunato.
R-EVO: a Reactive Evolutionary Algorithm for the
Maximum Clique Problem
IEEE Transactions on Evolutionary Computation, 2010.
PDF proofs:
ieee-tevo.pdf
Abstract:
An evolutionary algorithm with guided mutation
(EA/G) has been proposed recently for solving the maximum
clique problem. In the framework of estimation-of-distribution
algorithms (EDA), guided mutation uses a model distribution to
generate offspring by combining the local information of solutions
found so far with global statistical information. Each individual
is then subjected to a Marchiori's repair heuristic, based on
randomized extraction and greedy expansion, to ensure that it
represents a legal clique.
A novel reactive and evolutionary algorithm (R-EVO) proposed
in this paper starts from the same evolutionary framework
but considers more complex individuals, which modify tentative
solutions by local search with memory, according to the
Reactive Search Optimization (RSO) principles. In particular,
the estimated distribution is used to periodically initialize the
state of each individual based on the previous statistical knowledge
extracted from the population. We demonstrate that the
combination of the estimation-of-distribution concept with RSO
produces significantly better results than EA/G for many test
instances and it is remarkably robust w.r.t. the setting of the
algorithm parameters.
R-EVO adopts a drastically simplified low-knowledge version
of Reactive Local Search (RLS), with a simple internal diversification
mechanism based on tabu-search, with a prohibition
parameter proportional to the estimated best clique size. REVO
is competitive with the more complex full-knowledge RLSEVO
which adopts the original RLS algorithm. For most of
the benchmark instances, the hybrid scheme version produces
significantly better results than EA/G for comparable or a smaller
CPU time.
Index Terms: Maximum Clique, Reactive Search Optimization
(RSO), Estimation of Distribution, guided mutation
BB2010
Mauro Brunato and Roberto Battiti
Grapheur: A Software Architecture for Reactive and Interactive Optimization
Proceedings Learning and Intelligent OptimizatioN
LION 4, Jan 18-22, 2010, Venice, Italy.
Lecture Notes in Computer Science
Volume 6073, 2010, DOI: 10.1007/978-3-642-13800-3, pag. 232-246
Digital version available:
grapheur-lion4.pdf
HAIFA2009
Roberto Battiti
Graph and hyper-graph partitioning
Invited presentation at the 9th Haifa Workshop on Interdisciplinary Applications of Graph Theory,
Combinatorics and Algorithms, 20-21 May 2009, Haifa (Israel)
Slides:
haifa.pdf.
ECCO2009
Roberto Battiti and Paolo Campigotto
Brain-machine optimization: learning objective functions by interacting with the final user
European Chapter on Combinatorial Optimization (ECCO) XXII , May 17-19, 2009, Jerusalem
(Israel)
Slides:
ecco09.pdf.
BM2009
Roberto Battiti and Franco Mascia
Reactive and Dynamic Local Search for
Max-Clique: Engineering Effective Building Blocks.
Computers and Operations Research 37, issue 3 (March 2010) 534 -- 542
Digital version available (preprint):
COR.pdf ,
permanent link to published version(DOI
doi:10.1016/j.cor.2009.02.013 ) .
Abstract:
This paper presents results of an ongoing investigation about how
different algorithmic building blocks contribute to solving the Max-
imum Clique problem. We consider greedy constructions, plateau
searches, and more complex schemes based on dynamic penalties and/or
prohibitions, in particular the recently proposed technique of Dynamic
Local Search and the previously proposed Reactive Local Search (RLS).
We design a variation of the original RLS algorithm where the role of
long-term memory is increased (RLS-LTM). In addition, we consider
in detail the effect of the low-level implementation choices on the CPU
time per iteration. We present experimental results on randomly gen-
erated graphs with different statistical properties, showing the crucial
effects of the implementation, the robustness of different techniques,
and their empirical scalability.
BC2008b
Roberto Battiti and Paolo Campigotto
Reinforcement Learning and Reactive Search: an adaptive MAX-SAT solver,
in ECAI 08: 18th European Conference on Artificial Intelligence, Patras, Greece, Jul 21-25, 2008.
Digital version available:
reinforcement_ECAI08.pdf
Abstract:
This paper investigates Reinforcement Learning (RL) applied to online
parameter tuning in Stochastic Local Search (SLS) methods. In
particular, a novel application of RL is proposed in the Reactive Tabu
Search (RTS) scheme, where the appropriate amount of diversification
in prohibition-based local search is adapted in a fast online manner
to the characteristics of a task and of the local configuration. The
experimental tests demonstrate promising results onMaximumSatisfiability
(MAX-SAT) instances when compared with state-of-the-art
SLS SAT solvers, such us AdaptNovelty+, rSAPS and gNovelty+.
BC2008
Roberto Battiti and Paolo Campigotto
Penalties may have collateral effects. A MAX-SAT analysis.
, in Workshop on Modeling and Solving Problems with Constraints
(in conjunction with the 18th European Conference on Artificial Intelligence, ECAI 2008),
Patras, Greece, Jul 21-22, 2008.
Digital version available:
sideEffects_ECAI08.pdf
Abstract:
Many incomplete approaches for MAX-SAT have been proposed
in the last years. The objective of this investigation is not so much
horse-racing (beating the competition on selected benchmarks) but
understanding the qualitative differences between the various methods.
In particular, we focus on reactive search schemes where taskdependent
and local properties in the configuration space are used
for the dynamic on-line tuning of local search parameters and we
consider the choice between prohibition-based and penalty-based approaches.
To abstract from implementation details we focus on the
search trajectory characteristics and study the trade-off between diversification
and bias after starting from a local minimizer. We then
study the warping effects on the fitness surface of weight-update
schemes and the resulting dynamics, through an exhaustive analysis
of small MAX-SAT instances, and of the average evolution of individual
trajectories. The results are compatible with the conclusion
that penalty-based schemes achieve diversification from a starting local
optimum through a complex method with global and potentially
dangerous collateral effects, while prohibition-based schemes reach
comparable or better results in a more direct and controllable manner.
In the final part of this paper, we consider long runs of the complete
algorithms on selectedMAX-SAT instances, which confirm the
competitiveness of prohibition-based reactive approaches.
.
BM2007
Roberto Battiti and Franco Mascia
An Algorithm Portfolio for the Sub-Graph Isomorphism Problem
Proceedings of Stochastic Local Search 2007, Lecture Notes in Computer Science. Volume 4638/2007, Springer 2007,
Pages 106-120.
Digital version available:
Springer page , preprint:
battiti_mascia_portfolio.pdf
Abstract:
This work presents an algorithm for the sub-graph isomorphism
problem based on a new pruning technique for directed graphs.
During the tree search, the method checks if a new association between
two vertices is compatible by considering the structure of their local
neighborhoods, represented as the number of limited-length paths of different
type originating from each vertex. In addition, randomized versions
of the algorithms are studied experimentally by deriving their runtime
distributions. Finally, algorithm portfolios consisting of multiple
instances of the same randomized algorithm are proposed and analyzed.
The experimental results on benchmark graphs demonstrate that the
new pruning method is competitive w.r.t. recently proposed techniques.
Significantly better results are obtained on sparse graphs. Furthermore,
even better results are obtained by the portfolios, when both the average
and standard deviation of solution times are considered.
MBW2008
Vittorio Maniezzo, Roberto Battiti and Jean-Paul Watson (Eds.)
Learning and Intelligent Optimization
Second International Conference, LION 2007 II, Trento, Italy, December 8-12, 2007. Selected Papers
Series: Lecture Notes in Computer Science
Subseries: Theoretical Computer Science and General Issues , Vol. 5313
Maniezzo, Vittorio; Battiti, Roberto; Watson, Jean-Paul (Eds.)
2008, XII, 243 p., Softcover
ISBN: 978-3-540-92694-8
Springer book page
BBC2008
Roberto Battiti, Mauro Brunato, Paolo Campigotto.
Learning while Optimizing an Unknown Fitness Surface.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, December 2007), pag. 25-40.
LNCS 5313 - Springer, December 2008.
Digital version available: lionII-LSPI.pdf
Springer book page
(DOI: 10.1007/978-3-540-92695-5_3)
BHB2008
Mauro Brunato, Holger H. Hoos, Roberto Battiti.
On Effectively Finding Maximal Quasi-Cliques in Graphs.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, December 2007). LNCS 5313 - Springer, December 2008.
Digital version available: lionII-quasi.pdf
Springer book page
BB2008
Mauro Brunato, Roberto Battiti
RASH: A Self-adaptive Random Search Method.
In: Carlos Cotta, Marc Sevaux, and Kenneth Sörensen (Eds.),
Adaptive and Multilevel Metaheuristics.
Studies in Computational Intelligence, Vol. 136, Springer, 2008.
ISBN: 978-3-540-79437-0
Digital version available: RASH.pdf
Springer book page
CCGCB2008
ROBERTO G. CASCELLA, ZHEN CAO, MARIO GERLA, BRUNO CRISPO, ROBERTO BATTITI
Weak Data Secrecy via Obfuscation in Network Coding Based Content Distribution.
Accepted to the IFIP Wireless Days Conference, Dubai, United Arab Emirates, November 24-28 2008
Digital version available:
ifip-2008.pdf
GCCCB2008
MARIO GERLA, ROBERTO G. CASCELLA, ZHEN CAO, BRUNO CRISPO, ROBERTO BATTITI
An efficient weak secrecy scheme for network coding data dissemination in VANET - Invited Paper.
In Proceedings of the IEEE International Symposium on Personal,
Indoor and Mobile Radio Communications (PIMRC 2008), Cannes, France, September 15-18 2008,
pages 1-5.
Digital version available:
GCCCB08-VANET-PIMRC.pdf ,
IEEE Proceedings web site
Abstract:
Vehicular networks create a new communication paradigm that enables to exploit the movement
of cars to disseminate content. If network coding is used, vehicles have much more flexibility
in content sharing and the system stability and scalability are promoted also in presence
of mobility. Along this line, we propose an efficient mechanism to provide secrecy of the
information. Traditional approaches based on encryption decrease the cooperation
willingness of intermediate nodes, which have no expectation of recovering the file.
Our scheme is based on obfuscation by processing and polluting the original file
so that only the intended recipients, informed of corrupted blocks, can recover
the information timely.
We present several alternatives to efficiently provide weak secrecy and to foster cooperation.
We simulate the file distribution in a vehicular network and show that the proposed scheme
enhances content distribution in term of downloading speed and it is much more efficient
than the ones that use encryption.
CB2007
ROBERTO G. CASCELLA, ROBERTO BATTITI
Social Networking and Game Theory to foster Cooperation.
Input paper at the 2nd ENISA Workshop on Authentication Interoperability Languages held at the
ENISA/EEMA European eIdentity conference, Paris, France, June 12-13, 2007.
Digital version available:
CB07-ENISA.pdf
BB2007
ROBERTO BATTITI, MAURO BRUNATO
R-EVO: a Reactive Evolutionary Algorithm for the Maximum Clique Problem
Technical report DIT-07-034 Università di Trento, May 2007
Digital version available:
DIT-07-034.pdf
BB2007RS
Roberto Battiti and Mauro Brunato
REACTIVE SEARCH: MACHINE LEARNING FOR MEMORY-BASED HEURISTICS
Chapter 21 in:
Teofilo F. Gonzalez (Ed.), Approximation Algorithms and Metaheuristics ,
Taylor & Francis Books (CRC Press), Washington, DC, 2007, pag. 21-1 -- 21-17
Digital version available:
chap21.pdf
Abstract:
Most state-of-the-art heuristics are characterized by a certain number of choices and free parameters, whose
appropriate setting is a subject that raises issues of research methodology.
In some cases, these parameters are tuned through a feedback loop that includes the user as a crucial
learning component: depending on preliminary algorithm tests some parameter values are changed by the
user, and different options are tested until acceptable results are obtained. Therefore, the quality of results
is not automatically transferred to different instances and the feedback loop can require a lengthy \trial and
error" process every time the algorithm has to be tuned for a new application.
Parameter tuning is therefore a crucial issue both in the scientific development and in the practical use
of heuristics. In some cases the role of the user as an intelligent (learning) part makes the reproducibility of
heuristic results difficult and, as a consequence, the competitiveness of alternative techniques depends in a
crucial way on the user's capabilities.
Reactive Search advocates the use of simple sub-symbolic machine learning to automate the parameter
tuning process and make it an integral (and fully documented) part of the algorithm.
If learning is performed on line, task-dependent and local properties of the configuration space can be used
by the algorithm to determine the appropriate balance between diversification (looking for better solutions in
other zones of the configuration space) and intensification (exploring more intensively a small but promising
part of the configuration space). In this way a single algorithm maintains the
exibility to deal with related
problems through an internal feedback loop that considers the previous history of the search.
In the following, we shall call reaction the act of modifying some algorithm parameters in response to the
search algorithm's behavior during its execution, rather than between runs. Therefore, a reactive heuristic
is a technique with the ability of tuning some important parameters during execution by means of a machine
learning mechanism.
It is important to notice that such heuristics are intrinsically history-dependent; thus, the practical
success of this approach in some cases raises the need of a sounder theoretical foundation of non-Markovian
search techniques.
BG2007
Roberto Battiti and Anurag Garg
Digital Reputation for
Virtual Communities
Chapter 85 in:
Teofilo F. Gonzalez (Ed.), Approximation Algorithms and Metaheuristics ,
Taylor & Francis Books (CRC Press), Washington, DC, 2007, pag. 85-1 -- 85-16.
Digital version available:
chap85.pdf
Abstract:
A virtual community can be defined as a group of people sharing a common interest or goal who interact
over a virtual medium, most commonly the Internet. Virtual communities are characterized by an absence
of face-to-face interaction between participants which makes the task of measuring the trustworthiness of
other participants harder than in nonvirtual communities. This is due to the anonymity that the Internet
provides, coupled with the loss of audiovisual cues that help in the establishment of trust. As a result,
digital reputation management systems are an invaluable tool for measuring trust in virtual communities.
Trust is an important component of all human interactions whether they take place online or not. There
is an implicit assumption of trust in each interaction that we participate in that involves some investment
on our part. The Merriam-Webster dictionary defines trust as assured reliance on the character, ability,
strength, or truth of someone or something. Even more pertinent to virtual communities is an alternative
definition which states that trust is a dependence on something future or contingent; reliance on future
payment for property (as merchandise) delivered. These definitions illustrate that the basis of trust is an
expectation of future payment or reward and that the transaction partner will behave in an honest fashion
and fulfill their obligations.
The processes behind the creation of trust can be classified into four broad categories:
1. Personality-based trust. A person's innate disposition to trust others.
2. Cognitive trust. Through recognition of the characteristics of the transaction partner.
3. Institution-based trust. A buyer's perception that effective (third-party) institutional mechanisms
are in place to facilitate transaction success.
4. Transaction-based trust. That relies on a participant's past behavior to assess their trustworthiness.
Personality-based trust does not have a significant use in virtual communities where decisions on trust
aremade algorithmically.Most cognitive factors that formtrust in real-life interactions such as the manner
of a person, their body language, and the intonations of their speech are also absent in virtual communities.
However, there are alternative formsof cognition that can be used instead. These are almost invariably based
on the virtual identity of the communitymember. In most purely online contexts, as opposed to contexts
where the online identity is linked to a nononline identity such as with online banking, there are virtually
no costs to creating a new virtual identity.Obtaining an e-mail address on any of the free web-based e-mail
services such asYahoo,Hotmail, Gmail is trivial andwith each one comes a new virtual identity.While these
services are increasingly adopting strategies such as requiring image reading to counter automated registrationspamprograms,
it is not difficult tocreate say adozen accounts in 10 min.Andas the e-Bay scam case
showed, that is all a malicious user needs to surmount simple feedback systems and commit online fraud.
Enforcing trust in virtual communities is hard not only because of the difficulties in recognizing the
trustworthiness of participants but also because of the lack of adequate monitoring and appropriate
sanctions for dishonest behavior. This lack of institution-based trust is because there are not enough
trusted third parties with the power to punish to ensure honesty of all the players. This problem is
exacerbated in decentralized virtual communities and electronic marketplaces. An organization like e-Bay
with a centralized infrastructure can act as the trusted third party to at least store feedback information
in a reliable fashion even though the information itself may not be reliable. The problem becomes much
harder with decentralized systems such as peer-to-peer (P2P) networks where the absence of a centralized
authority is a defining feature of the system.
Hence, it appears that the best strategy for creating trust in virtual communities is through transactionbased
trust where feedback on participants' past behavior is collected and aggregated to decide their
trustworthiness. A transaction-based trust strategy is far from perfect and suffers from many of the same
shortcomings as the other strategies. For instance, the lack of verifiable identities can make a transactionbased
system vulnerable to manipulation. However, as many recent proposals have shown such
strategies are not contingent upon a trusted third party and the community as a whole provides the
institutional basis for trust. Hence, if the problem of identity can be solved, transaction-based systems are
capable of providing the solution for virtual communities.
Transaction-based trust creation strategies are also commonly known as reputation-based trust management
systems or just reputation systems. Some authors use the term reputation systems narrowly to
include only those systems that monitor past transactions of participants to compute their trustworthiness.
This information is then shared with other participants who decide whether or not to interact with
the target participant on its basis. We use the term in a more general sense to include recommendations
systems that recommend items as well as systems that perform distributed authentication by inferring
trustworthiness. All these systems have one feature in common: the collection and aggregation of feedback
in order to rate objects or people.
Reputation systems research lies at the intersection of several disciplines including evolutionary biology,
economics (game theory and mechanism design), sociology (social network theory), and computer science
(e-commerce, P2P systems, cryptography, etc.). In this chapter, we survey the
approaches taken by researchers fromthese disciplines to provide the context for digital reputation schemes.
We begin by listing the various applications of digital reputation systems. This is followed by a discussion of
what motivates the participants of a virtual community to cooperate with each other.We then look at what
are the requirements of a good reputation system. This is followed by a more detailed analysis of the components
of reputation systems.We classify different types of feedback and their role in constructing reputations.
We discuss second-order reputation and the motivations for providing feedback.Reputationmodifying
factors such as transaction context are looked at next followed by a discussion on howreputations can be
interpreted.We conclude by looking at several specific digital reputation systems that have been proposed.
LB2007
Bo Li and Roberto Battiti
Achieving optimal performance in IEEE 802.11 wireless
LANs with the combination of link adaptation
and adaptive backoff
Computer Networks 51 (2007), pag. 1574-1600.
Digital version available:
cn2007.pdf
(DOI doi:10.1016/j.comnet.2006.08.018)
Abstract:
IEEE 802.11 is one of the most popular wireless LAN standards. In the paper, we propose a simple analytical
model, which helps one obtain deep insight into the mechanism of achieving optimal performance by using IEEE 802.11
DCF (Distributed Coordination Function) protocol. The first contribution of this paper is the analysis of the optimal operation
point where maximum goodput can be achieved. Through the analysis, we answer some fundamental questions
about the existence and the uniqueness of the optimal operation point; about the maximum system goodput can be
achieved; about the existence of a simple rule to check out if the system operates under the optimal state or not; and
how do the data transmission rates, which is dependent on the selected physical transmission mode, and packet transmission
errors, caused by channel fading and (or) interference, affect the final system performance. Another contribution is the
proposal of a simple distributed adaptive scheme "LABS'' (i.e., Link adaptation and Adaptive Backoff Scheme), which
makes the system operate under the optimal operation point and, at the same time, achieves some pre-defined target service
differentiation ratio between different traffic flows. In the LABS, two adaptive schemes are combined: one is the so called
"Link Adaptation'' scheme, which dynamically selects an optimal modulation mode at a given time so as to improve the
achieved system goodput; the other one is the so called "Adaptive Backoff'' scheme, which adaptively adjusts the minimum
contention window size of each sending node to guarantee that the system operates under (or near) the optimal operation
point. Results obtained in the paper are relevant to both theoretical research and implementation of real systems.
SA2006
R. Battiti (Ed.)
ScienzAzienda 2006
Scienza e tecnologia per l'innovazione e lo sviluppo
Atti del convegno
8 maggio 2006
Facoltà di Scienze Matematiche Fisiche e Naturali,
Università di Trento
Digital version available:
sa.pdf
GMB2006
Garg, A. Montresor, A. Battiti, R.
Reputation Lending for Virtual Communities
Proceedings. 22nd International Conference on Data Engineering Workshops,
03-07 April 2006 (Digital Object Identifier: 10.1109/ICDEW.2006.128)
Digital version available:
lending.pdf
Abstract:
Reputation management schemes have recently emerged as a mechanism for improving trust
and security in peer-topeer networks. A new entrant in a network with reputation
management can either be given the benefit of doubt and be treated like a trusted
(or semi-trusted) peer until it misbehaves or it can be assumed to be untrusted
and have to earn the trust of others. The former case provides an incentive for
misbehaving peers to cast off their old identity and assume a new one regularly.
The latter case presents the problem of new peers being unable to bootstrap and
to gain a foothold in the network. In this paper, we present a mechanism in
which existing peers can choose to "lend" part of their reputation to new peers
that they know in order to give them a start. This mechanism mirrors the real
world where a reference or an introduction often gives one a foothold into an
otherwise closed group. If the new peer behaves well, the old peer is rewarded
for adding value to the group and if the new peer misbehaves the old peer
loses the reputation it lent. In this way, existing peers have a stake in
introducing new peers into the network and get a return on their investment
for introducing honest peers.
AAA2003
Garg, A.;
Battiti, R.; Cascella, R.G.;
"May I borrow Your
Filter?" Exchanging Filters to Combat Spam in a Community
20th International Conference on Advanced Information Networking and
Applications, AINA 2006, April 2006, Vienna.
IEEE Computer Society, Los Alamitos, CA, USA, Volume
2, 18-20 Page(s):489 - 493
Digital version available:
aina2006.pdf
Abstract:
Leveraging social networks in computer systems can be effective in dealing with
a number of trust and security issues. Spam is one such issue where the "wisdom
of crowds" can be harnessed by mining the collective knowledge of ordinary
individuals. In this paper, we present a mechanism through which members of a
virtual community can exchange information to combat spam. Previous attempts at
collaborative spam filtering have concentrated on digest-based indexing
techniques to share digests or fingerprints of emails that are known to be spam.
We take a different approach and allow users to share their spam filters
instead, thus dramatically reducing the amount of traffic generated in the
network. The resultant diversity in the filters and cooperation in a community
allows it to respond to spam in an autonomic fashion. As a test case for
exchanging filters we use the popular SpamAssassin spam filtering software and
show that exchanging spam filters provides an alternative method to improve spam
filtering performance.
GB2005
Anurag Garg and Roberto Battiti
DIGITAL REPUTATION FOR VIRTUAL
COMMUNITIES
Technical Report # DIT-05-066, Universita' di Trento, Oct 2005
Digital version available:
TR-05-066.pdf
Abstract:
In this report we provide an overview of digital reputation management systems
for virtual communities. We begin with a discussion on the how trust is created in
the real world. We then highlight how the process of trust creation differs in the
virtual world. Next, we talk about the different ways in which digital reputations are
useful to virtual communities such as incentivizing cooperation and punishing malicious
users, providing recommendations or as a form of distributed authentication.
We then discuss how evolutionary biology and game theory have informed research
in reputation systems. This is followed by a discussion of the various components
of reputation such as context, the forms of evidence, .rst and second order reputation
and architectural considerations including the role of distributed hash tables
in decentralized reputation management systems. We conclude with a discussion of
some reputation management systems such as complaints-based trust, EigenTrust,
PeerTrust and ROCQ.
BEBA2006
Sergei L. Bezrukov and Roberto Battiti
On Partitioning of Hypergraphs
Discrete Mathematics 307 (2007) 1737 - 1753
Digital version (preprint) available:
hyperlast.pdf
(DOI doi:10.1016/j.disc.2006.09.022 )
Abstract:
We study Edge-Isoperimetric Problems (EIP) for hypergraphs and extend some
technique in this area from graphs to hypergraphs. In particular, we establish some
new results on a relationship between the EIP and some extremal poset problems,
and apply them to obtain an exact solution of the EIP for certain hypergraph
families. We also show how to solve the EIP on hypergraphs in some cases when
the link to posets does not work. Another outcome of our results is a new series
of hypergraphs admitting nested solutions in the EIP. The obtained results can be
used for checking the quality of heuristics for hypergraph partitioning.
WB2006
Wei Wang and Roberto Battiti
Identifying Intrusions in Computer Networks
with Principal Component Analysis
Proceedings of ARES 2006
(The First International Conference on
Availability, Reliability and
Security), 20-22 Apr 2006, Vienna, Austria,
IEEE Computer Society, Los Alamitos, CA, USA. Pages 270-277.
Digital version available:
ares2006.pdf
Abstract:
Most current anomaly Intrusion Detection Systems
(IDSs) detect computer network behavior as normal or abnormal
but cannot identify the type of attacks. Moreover,
most current intrusion detection methods cannot process
large amounts of audit data for real-time operation. In this
paper, we propose a novel method for intrusion identification
in computer networks based on Principal Component
Analysis (PCA). Each network connection is transformed
into an input data vector. PCA is employed to reduce the
dimensionality of the data vectors and identification is handled
in a low dimensional space with high efficiency and
low use of system resources. The normal behavior is pro-
filed based on normal data for anomaly detection and models
of each type of attack are built based on attack data for
intrusion identification. The distance between a vector and
its reconstruction onto those reduced subspaces representing
the different types of attacks and normal activities is
used for identification. The method is tested with network
data from MIT Lincoln labs for the 1998 DARPA Intrusion
Detection Evaluation Program and testing results show that
the model is promising in terms of identification accuracy
and computational efficiency for real-time intrusion identification.
BM2006
Roberto Battiti
and Franco Mascia
Reactive and dynamic
local search for Max-Clique, does the complexity pay off?
Technical Report
DIT-06-027, Informatica e Telecomunicazioni, University of Trento, Apr 2006.
Digital version available:
rls-dls.pdf
Abstract:
This paper presents some preliminary results of an ongoing investigation about
how different algorithmic building blocks contribute to solving theMaximumClique
problem. In detail, we consider greedy constructions, plateau searches, and more
complex schemes based on dynamic penalties and/or prohibitions, in particular the
recently proposed technique of Dynamic Local Search and the previously proposed
Reactive Local Search. The experimental results consider both the empirical hardness,
measured by the iterations needed to reach empirical maxima, and the CPU time
per iteration.
BBP2006
Mauro Brunato, Roberto Battiti and Srinivas Pasupuleti
A Memory-Based RASH Optimizer
Proceedings of the
AAAI-06 workshop on
Heuristic Search, Memory Based Heuristics and Their applications , July 17, Boston.
Digital version available:
mrash-aaai.pdf
Abstract:
This paper presents a memory-based algorithm for global optimization
of multivariate functions of continuous variables.
The proposed algorithm, M-RASH, is based on the RASH
(Reactive Affine Shaker) heuristic, an adaptive search algorithm
based only on point-wise function evaluations. MRASH
is an extension of RASH in which promising starting
points for local search trails are suggested online by using
Bayesian Locally Weighted Regression. Both techniques
maintain memory about the previous history of the search
to guide the future exploration, but in very different ways.
RASH compiles the previous experience into the shape of
a local search area where sample points are drawn, while
locally-weighted regression saves the entire previous history
to be mined extensively when an additional sample point is
generated. Because of the high computational cost related to
the regression model, it is applied only to evaluate the potential
of an initial point for a local search run. The experimental
results show that M-RASH is indeed capable of leading to
good results for a smaller number of function evaluations.
BG2005
Roberto Battiti and Mario Gerla
Proceedings of Tridentcom (First International
Conference on Testbeds and Research Infrastructures for the
Development of Networks and Communities), Feb 23-25 2005, Trento Italy
IEEE Computer Society, Los Alamitos, CA, USA, ISBN 0-7695-2219-X
PB2006
Srinivas Pasupuleti and Roberto Battiti
The Gregarious Particle Swarm Optimizer (G-PSO)
Proceedings of
ACM Genetic and Evolutionary Computation
Conference (GECCO) 2006 , July 8-12, 2006, Seattle, Washington, USA. ACM.
Digital version available:
g-pso.pdf
Abstract:
This paper presents a gregarious particle swarm optimiza-
tion algorithm (G-PSO) in which the particles explore the
search space by aggressively scouting the local minima with
the help of only social knowledge. To avoid premature con-
vergence of the swarm, the particles are re-initialized with a
random velocity when stuck at a local minimum. Further-
more, G-PSO adopts a "reactive" determination of the step
size, based on feedback from the last iterations. This is in
contrast to the basic particle swarm algorithm, in which the
particles explore the search space by using both the individ-
ual "cognitive" component and the "social" knowledge and
no feedback is used for the self-tuning of algorithm parame-
ters. The novel scheme presented, besides generally improv-
ing the average optimal values found, reduces the computa-
tion effort.
GBC2005
Anurag Garg, Roberto Battiti and Roberto Cascella
"Reputation management: experiments on the robustness of ROCQ"
In Proceedings of the 7th International Symposium on Autonomous
Decentralized Systems (ISADS 2005) - First International Workshop on
Autonomic Communication for Evolvable Next Generation Networks (WAGEN),
Chengdu, China, 4-8 April 2005. IEEE Computer Society, 2005, pages 725-730.
Digital version available:
isads2005.pdf
SGB2005
Mikalai Sabel, Anurag Garg, Roberto Battiti
WIKIREP: DIGITAL REPUTATION IN VIRTUAL COMMUNITIES
DIT Technical Report DIT-05-050, University of Trento, Italy, June 2005.
Digital version available:
wikireptr-DIT-05-050.pdf
Accepted for publication in Proceedings: CONGRESSO ANNUALE AICA 2005 , Comunita' virtuale dalla
ricerca all'impresa, dalla formazione al cittadino, Udine, 5-7 ottobre 2005.
Abstract:
We present a framework for applying digital reputations to collaborative environments,
where multiple authors contribute to the same document. In our mechanism
readers evaluate a single document, and reputation data derived from the
feedbacks affect multiple authors and document versions. The digital reputation
encourages contribution and provides motivation for active participation, leading to
better quality of the content and to better user experience. Our approach is applicable
to user-managed communities, distributed moderation systems, and other
collaborative contexts.
The underlying ideas of our scheme are: separate ratings for different versions
of the same document, inheritance of previous ratings for newer versions, and appropriate
allocation of credit to versions and authors. We describe in detail both
the algorithms used to compute reputations, and our implementation, WikiRep, a
reputation-enabled Wiki application.
BBP2005
Roberto Battiti, Mauro Brunato, Srinivas Pasupuleti
Do not be afraid of local minima: Affine Shaker and Particle Swarm
DIT Technical Report DIT-05-049, University of Trento, Italy, May 2005.
Digital version available:
pso.pdf
Abstract:
Stochastic local search techniques are powerful and flexible methods to
optimize difficult functions. While each method is characterized by search
trajectories produced through a randomized selection of the next step, a
notable difference is caused by the interaction of different searchers, as exemplified
by the Particle Swarm methods. In this paper we evaluate two
extreme approaches, Particle Swarm Optimization, with interaction between
the individual "cognitive" component and the "social" knowledge,
and Repeated Affine Shaker, without any interaction between searchers
but with an aggressive capability of scouting out local minima. The results,
unexpected to the authors, show that Affine Shaker provides remarkably
efficient and effective results when compared with PSO, while
the advantage of Particle Swarm is visible only for functions with a very
regular structure of the local minima leading to the global optimum and
only for specific experimental conditions.
GPBG2005
Mario Gerla, Joon-Sang Park, Roberto Battiti, Anurag Garg
Intelligent Backbone Swarms for scalable, disruption tolerant wireless networking
Proceedings, 2005 IEEE Swarm Intelligence Symposium (SIS-05)
June 8-10, 2005
Pasadena, California, USA, IEEE press, page 432 -- 435
Digital version available:
swarm.pdf
Abstract:
In this paper, we propose a swarm intelligence
strategy for constructing a mobile backbone
multicasting network which leads to improved
scalability and connectivity compared to
conventional flat networks. The strategy combines a
simple clustering technique and On Demand
Multicast Protocol (ODMRP). Also we show benefits
of the mobile backbone network through a simulation
study.
LBF2005
Bo LI, Roberto BATTITI, and Akira FUKUDA
Performance Analysis of a Service-dependant Handoff
Scheme in Voice/Data Integrated Cellular Mobile Systems
Computer Networks, Volume 50, Issue 5, Pages 707-730 (April 2006)
Digital version available:
COMNET-2005.pdf
Abstract:
In this paper, we propose and analyze a service-dependent handoff and channel allocation
scheme in voice and data integrated cellular mobile systems, which combines the ideas of
"Variable Bandwidth" and "Preemptive Priority" together. In the scheme, voice and data traffic
are considered. According to the variations of the offered traffic intensity at each cell, both a
voice and a data call in service can occupy a full-rate channel or a half-rate channel. In order to
guarantee the Quality of Service (QoS) for both voice and data traffic, channel resources are
fairly shared between voice and data calls according to an optimal channel allocation scheme,
which minimizes the difference between the average bandwidth of a voice call in service and
that of a data call in service. To minimize the forced termination of a voice call, a voice call can
preempt a data call in service if all the calls in the channel pool of the current cell are already
assigned with half-rate service. The interrupted data call returns back to the queue specially
prepared for data traffic. By analysis, we obtain the most important system performance
measures. Comparisons with the scheme, which only supports "Preemptive Priority" without
"Variable Bandwidth" supporting, shows that if the total arrival rate for originating calls is not
very heavy, the new scheme can provide lower blocking probability and forced termination
probability for both voice and data traffic, and shorter average total transmission time for a
successfully completed data call.
BB2005
Mauro Brunato and Roberto Battiti
Statistical Learning
Theory for Location Fingerprinting in Wireless LANs
Computer Networks, 47 (6), 2005, pages 825-845
Digital version available:
ComNet.pdf
Abstract:
In this paper, techniques and algorithms developed in the framework of Statistical
Learning Theory are applied to the problem of determining the location of a wireless
device by measuring the signal strength values from a set of access points (location
fingerprinting). Statistical Learning Theory provides a rich theoretical basis for the
development of models starting from a set of examples. Signal strength measurement
is part of the normal operating mode of wireless equipment, in particular Wi-Fi, so
that no special-purpose hardware is required.
The proposed techniques, based on the Support Vector Machine paradigm, have
been implemented and compared, on the same data set, with other approaches
considered in scientic literature. Tests performed in a real-world environment show
that results are comparable, with the advantage of a low algorithmic complexity in
the normal operating phase. Moreover, the algorithm is particularly suitable for
classification, where it outperforms the other techniques.
CBC2004
Anurag Garg, Roberto Battiti and Gianni Costanzi
Dynamic Self-management of Autonomic Systems: The Reputation, Quality and Credibility (RQC) Scheme
Proceedings of The 1st IFIP TC6 WG6.6 International Workshop on Autonomic Communication
( WAC2004, Berlin, 18-19 Oct 2004 ), Lecture
Notes on Computer Science LNCS 3457, Michael Smirnov (Ed.), pag. 165-178, Springer, Berlin, 2005.
Digital version available:
wac2004.pdf
Abstract:
In this paper, we present a feedback-based system for managing trust and
detecting malicious behavior in autonomically behaving networks. Like other
distributed trust management systems, nodes rate the interactions they have with
other nodes and this information is stored in a distributed fashion.
Two
crucial insights motivate our work. We recognize as separate entities the trust
placed in a node, {\em reputation}, and the trust placed in the recommendations
made by a node, {\em credibility}. We also introduce the concept of quality of a
trust rating. Together, these two factors enhance the ability of each node to
decide how much confidence it can place in a rating provided to it by a third
party.
We implement our scheme on a structured P2P network, Pastry, though
our results can be extended to generic autonomic communication systems.
Experimental results considering different models for malicious behavior
indicate the contexts in which the RQC scheme performs better than existing
schemes.
LBC2004
Renato Lo cigno, Roberto Battiti, Marco Conti
Wireless on-demand network systems
Proceedings of the First Working Conference on Wireless On-demand Network Systems,
WONS 2004 Madonna di Campiglio, Italy, January 21 -
23, 2004
Springer, LNCS vol. 2928, pages 402, 2004
LB2004
Bo Li and Roberto Battiti
Analysis of the IEEE 802.11 DCF with Service Differentiation Support in Non-saturation Conditions
Lecture Notes in Computer Science Volume
3266 / 2004
Quality of Service in the Emerging Networking Panorama: Fifth
International Workshop on Quality of Future Internet Services, QofIS 2004, Barcelona, Spain.
Editors:
Josep Sol--Pareta, Michael Smirnov, Piet Van Mieghem, et al.
Publisher: Springer-Verlag
Heidelberg
ISSN: 0302-9743, pp. 64 - 73.
Digital version (preprint) available:
QoFIS2004final.pdf
Abstract:
Although the performance analysis of the IEEE 802.11 Distributed Coordination
Function (DCF) in saturation state has been extensively studied in the
literature, little work is present on performance analysis in non-saturation
state. In this paper, a simple model is proposed to analyze the performance of
IEEE 802.11 DCF with service differentiation support in non-saturation states,
which helps to obtain a deeper insight into the IEEE 802.11 DCF. Based on the
proposed model, we can approximately evaluate the most important system
performance measures, such as packet delays, which provide one with an important
tool to predict and optimize the system performance. Moreover, a practical
method to meet packet delay requirements is presented based on our theoretical
results. Comparisons with simulations show that this method achieves the
specified packet delay requirements with good accuracy.
SB2004
Elio Salvadori, Roberto Battiti
A Traffic Engineering Scheme for QoS Routing in G-MPLS Networks Based on
Transmission Quality
In 8th IFIP Working Conference on Optical Network Design and Modelling - ONDM
2004 proceedings, 2004
SB2004
Salvadori E., Battiti R.,
"Quality of Service in IP over WDM considering both
service differentiation and transmission quality".
Proceedings "IEEE
International Conference on Communications - ICC 2004", Paris - France, 20-24
June, 2004. IEEE, URL : http://www.icc2004.org/.
Digital preprint version available:
qoswdm.pdf
CBCA2004
Csaba Kiss Kallo', Roberto Battiti, Carla-Fabiana Chiasserini, Marco
Ajmone Marsan
Reducing the number of hops between communication peers in a bluetooth scatternet
Proceedings of the IEEE Wireless Communications and Networking Conference
(WCNC2004)
21-25 March 2004, Atlanta, Georgia, USA.
IEEE, Page(s):207 - 212. Vol.1
Digital preprint version available:
wcnc2004.pdf
B2004
Roberto Battiti, Renato Lo Cigno, Mikalai Sabel, Fredrik Orava, Bjorn Pehrson
Wireless LANs: from WarChalking to Open Access
Networks
Monet (Mobile Networks and
Applications), special issue dedicated to WMASH,
guest editors: Giuseppe Bianchi, Sung Ju Lee, Parviz Kermani, no. 10, 275--287, 2005.
Digital version available:
Battiti-Orava_05.df ,
monet-2005.pdf
WILMA2003
R. Battiti, M. Brunato, R. Lo Cigno,
A. Villani, R. Flor and G. Lazzari
WILMA: An Open Lab for 802.11 HotSpots
Lecture Notes in Computer Science
Publisher: Springer Berlin / Heidelberg
ISSN: 0302-9743
Subject: Computer Science
Volume 2775 / 2003
Title: PersonalWireless Communications
ISBN: 3-540-20123-8
DOI: 10.1007/b12004
Chapter: pp. 163 - 168
Digital version available:
LNCS
Abstract:
WILMA (Wireless Internet and Location Management
Architecture) is an ongoing research project based in Trento, Italy, whose aim
is the study of the management of 802.11-based HotSpot Networks and the value
added services that can be provided through such an infrastructure.
The WILMA project (www.wilmaproject.org)
is supported by the Province of Trento under Grant N. 437, issued on March 3,
2002.
LB2003
Bo Li, Roberto Battiti
Performance Analysis of An Enhanced IEEE 802.11 Distributed Coordination
Function Supporting Service Differentiation
G. Kerlsson and M.I.Simirnov (Eds.): "Quality for all", QofIS 2003,
LNCS 2811, pp. 152-161, 2003, Springer-Verlag Berlin.
Digital version available:
QoFIS2003.pdf
Abstract: As one of the fastest
growing wireless access
technologies, Wireless LANs (WLANs) must evolve to support adequate degrees of
service differentiation. Unfortunately, current WLAN standards like IEEE 802.11
Distributed Coordination Function (DCF) lack this ability. Work is in progress
to define an enhanced version capable of supporting QoS for multimedia traffic
at the MAC layer. In this paper, we aim at gaining insight into two mechanisms
to differentiate among traffic categories, i.e., scaling the minimum contention
window size and the length of the packet payload according to the priority of
each traffic flow. We propose an analysis model to compute the throughput and
packet transmission delays. In additions, we derive approximations to get
simpler but more meaningful relationships among different parameters.
Comparisons with simulation results show that a very good accuracy of
performance evaluation can be achieved by using the proposed analysis model.
BBS2003
Mauro Brunato, Roberto Battiti, Elio Salvadori
Dynamic
Load Balancing in WDM Networks
special issue di Optical Networks Magazine
"Dynamic Optical Networking: Around the Corner or Light Years Away?", Sep 2003.
Digital version available:
ONM.pdf
Abstract: In
this paper new load balancing techniques are proposed based on IP-like
routing, where the forwarding mechanism is only driven by the destination
address. The aim of this work is to consider the applicability of
this approach in the context of optical networks. The
proposed algorithm (RSNE | Reverse Subtree Neighborhood Ex- ploration)
implements a local search technique where the basic step is the modi
cation of a single entry in the routing table of a node. A randomized
method with reduced computational complexity (fRSNE | fast RSNE) is
also presented and analyzed. Both schemes allow an incremental imple-
mentation where local search steps are continuously performed as tra.c
conditions change.
Experiments under static and dynamic (time varying) tra.c scenar-
ios show a rapid reduction of the congestion. The performance of the
incremental scheme while tracking a changing tra.c matrix is compara-
ble to that obtainable through the complete re-optimization of the tra.c,
while the randomized implementation is particularly e.cient when scaling
properties are considered.
Bat-per
R. Battiti.
Partially persistent dynamic sets for history-sensitive
heuristics.
in: Data Structures, Near Neighbor Searches, and Methodology:
Fifth and Sixth DIMACS Challenges, M. H. Goldwasser, D. S. Johnson
And C.C. McGeoch,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Volume 59, 2002, pag. 1 --21
Preprint available:
persistent-challenge.pdf
Abstract:
Effective heuristic algorithms for combinatorial problems are based on
integrating local neighborhood search with history-sensitive
schemes, where the information collected during
the previous search phase is used to direct the future effort.
In particular, some algorithms (like REM tabu search
and reactive tabu search)
need to detect whether a configuration has already been encountered
during the previous phase of the search.
This letter analyzes the use of persistent dynamic sets
for this purpose and discusses the advantages of this
option with respect to popular but less efficient
realizations. In particular, when combined with hashing, the method
complexity per search iteration is of $O(L)$ average-case time and
$O(1)$ amortized space, when the search space
is given by $L$-bit binary strings.
A concrete realization of the abstract data type through a C++ class is
presented. The obtained memory occupation and timing results are
analyzed for selected ``dictionary'' benchmark tasks
and for the use of the structure to support
history--sensitive heuristic algorithms.
BB2003a
Mauro Brunato and Roberto Battiti
PILGRIM: A Location Broker and Mobility-Aware Recommendation System
Proceedings of
PerCom2003 the
first IEEE Annual Conference on Pervasive Computing and Communications - Fort
Worth (TX), USA, March 2003, edited by Das S., March
23-26, 2003. IEEE Computer Society, p. 265-272. URL : http://www.percom.org/
Digital version available:
percom2003.pdf
Abstract: Mobile computing adds
a mostly unexplored dimension to data mining: user's position is a relevant
piece of information, and recommendation systems, selecting and ranking links
of interest to the user, have the opportunity to take location into account.
In this paper, a mobility-aware recommendation system that considers the
location of the user to filter recommended links is proposed. To avoid the
potential problems and costs of insertion by hand, a new middleware layer, the
location broker, maintains a historic database of locations and corresponding
links used in the past and develops models relating resources to their spatial
usage pattern. These models are used to calculate a preference metric when the
current user is asking for resources of interest. Mobility scenarios are
described and analyzed in terms of possible user requirements. The features of
the PILGRIM mobile recommendation system are outlined together with a
preliminary experimental evaluation of different metrics.