1,721,377 research outputs found
On the impact of small-world on local search
No full textThe impact of problem structure on search is a relevant issue in artificial intelligence and related areas. Among the possible approaches to analyze problem
structure, the one referring to constraint graph enables to relate graph parameters and characteristics with search algorithm behavior.
In this work, we investigate the behavior of local search applied to SAT instances associated to graphs with small-world topology.
Small-world graphs, such as friendship networks, have low characteristic path length and high clustering.
In this work, we first present a procedure to generate SAT instances characterized by an interaction graph with a small-world topology. Then we show experimental results concerning the behavior of local search algorithms applied to this benchmark
Special Issue on Local Search
No full textCollection of selected and peer reviewed papers on stochastic local search for constraint satisfaction
Introduction to the Special Issue on Local Search Techniques in Constraint Satisfaction
No full textConstraint satisfaction plays an important role in theoretical and applied computer
science. Constraint satisfaction problems (CSPs) are of particular interest to the
constraint programming research community and for many real world applications.
Along with pure systematic techniques for solving CSPs, stochastic local search
(SLS) and hybrid techniques have proved to be very effective on some classes of
problems. One central goal of research in SLS for constraint satisfaction is the
design and implementation of efficient algorithms for use in stand-alone solvers or
in conjunction with systematic techniques. As a result, there is a need to develop
high-level SLS strategies that will lead to further progress towards the maturation of
efficient and robust solvers for constraint satisfaction.
The design and analysis of SLS algorithms for constraint satisfaction involves a
wide range of issues related to algorithms, programming, statistics, probability and
empirical analysis. The design of SLS techniques for CSP is also a typical system
engineering process, as it involves modeling, design, analysis and implementation
activities. Moreover, empirical analysis is crucial for the assessment of performance
results and it has to comply with the scientific approach.
This special issue of Constraints offers a representative selection of the current
state-of-the-art in local search techniques for constraint satisfaction
An overview of AI research in Italy
No full textThis contribution is aimed at providing an overview of the main Italian research areas and activities. In this chapter we first analyze the collaboration structure of Italian research, that involves more than eight hundred scholars and researchers from both the University and the Industry and, from a network perspective, it appears to be scale-free. Then, we briefly illustrate the main subjects of investigation and applications. AI research in Italy traces back to the '70s with an increase in the last twenty years and spans the main research AI areas, from automated reasoning and ontologies, to machine learning, robotics and evolutionary computation
Introduction - Part V : Local Search Techniques in Constraint Satisfaction
No full textConstraint satisfaction plays an important role in theoretical and
applied computer science. Constraint satisfaction problems (CSPs) are
of particular interest to the constraint programming research
community, as well as for many real world applications. Along with
pure systematic techniques for solving CSPs, local search and hybrid
techniques have proved to be very effective on some classes of
problems.
Design and analysis of stochastic local search algorithms
for constraint satisfaction involve a wide number of issues in
algorithmics, programming, statistics, probability and empirical
analysis. The series of workshop named Local search
techniques in constraint satisfaction (LSCS) has been established
with the aim of providing an open and informal environment for
discussions of all aspects of local search techniques and related
areas, and for introducing recent results and ongoing research
On the Complexity of Baroque Music and Implications on Robotics and Creativity
No full textIn this paper we propose a perspective of baroque music as a phenomenon emerging from the interaction between a set of instructions (the score) and a frame of constraints in which to apply the instructions (the performance practice). This perspective provides a more principled setting for addressing the issue of estimating music complexity and suggests new ways towards artificial creativity through incompleteness. The considerations we elaborate on baroque music are extended to other complex processes, such as robotic behaviour
A Novel Online Adaptation Mechanism in Artificial Systems Provides Phenotypic Plasticity
No full textA framework supporting multi-compartment stochastic simulation and parameter optimisation for investigating biological system development
No full textIn this paper we propose a simulation framework specifically suited for developmental biology studies. It is mainly composed of three parts. First, it is based on a multiscale computational model, and related logic-oriented specification language compiler, supporting large-scale networks of compartments and an enhanced model of chemical reactions addressing molecule transfer. Second, we rely on a simulation engine based on an optimised version of the Gillespie stochastic simulation algorithm, which is able to simulate fine events at intracellular and multicellular level. Third, a metaheuristic-based module for automatically calibrating model parameters (such as reaction rates) is exploited. As a case study we model the first stages of Drosophila melanogaster development, which generate the early spatial pattern of gap gene expression. Results show the formation of a precise spatial pattern which has been successfully compared with observations acquired from the real embryo gene expressions. In particular, adopting the Covariance Matrix Adaptation Evolution Strategy for parameter estimation is crucial for the quality of the results achieved, reducing the error of a 60% from the initial formulation of parameters. The main contribution of this paper is the enhancement of a stochastic, multi-compartment simulator by means of a metaheuristic-based module for parameter estimation. This is the first such application available in literature, where the subject of parameter estimation is well-established only for deterministic single-compartment models. Moreover this is the first work demonstrating the ability of the Gillespie stochastic simulation algorithm, when properly equipped with additional parameter optimisation techniques, to model large-scale, complex biological systems
Complexity Measures: Open Questions and Novel Opportunities in the Automatic Design and Analysis of Robot Swarms
Full text linkComplexity measures and information theory metrics in general have recently been attracting the interest of multi-agent and robotics communities, owing to their capability of capturing relevant features of robot behaviors, while abstracting from implementation details. We believe that theories and tools from complex systems science and information theory may be fruitfully applied in the near future to support the automatic design of robot swarms and the analysis of their dynamics. In this paper we discuss opportunities and open questions in this scenario
Cell–Cell Interactions: How Coupled Boolean Networks Tend to Criticality
Full text linkBiological cells are usually operating in conditions characterized by intercellular signaling and interaction, which are supposed to strongly influence individual cell dynamics. In this work, we study the dynamics of interacting random Boolean networks, focusing on attractor properties and response to perturbations. We observe that the properties of isolated critical Boolean networks are substantially maintained also in interaction settings, while interactions bias the dynamics of chaotic and ordered networks toward that of critical cells. The increase in attractors observed in multicellular scenarios, compared to single cells, allows us to hypothesize that biological processes, such as ontogeny and cell differentiation, leverage interactions to modulate individual and collective cell responses
- …
