1,721,429 research outputs found
Criticality and Parallelism in GSAT
No full textIn this work we show some empirical results on the parallelization of GSAT. We subdivided the set of variables in τ equal subsets and we applied GSAT in parallel on each subset. We observed the existence of an optimum degree of parallelism (τopt) for which the best performance, in terms of efficiency (time and number of iterations) and effectiveness (fraction of solved instances) is obtained. Moreover, we found that τopt is strictly correlated to the connectivity parameter (q)
Critical parallelization of local search for MAX-SAT
No full textIn this work we investigate the effects of the parallelization of a local search algorithm for MAX-SAT. The variables of the problem are divided in subsets and local search is applied to each of them in parallel, supposing that variables belonging to other subsets remain unchanged. We show empirical evidence for the existence of a critical level of parallelism which leads to the best performance. This result allows to improve local search and adds new elements to the investigation of criticality and parallelism in combinatorial optimization problems
Solving the satisfiability problem through boolean networks
No full textIn this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework for local search algorithms
Emergence of macro spatial structures in dissipative cellular automata
No full textThis paper presents a new class of cellular automata, namely dissipative cellular automata, that exhibit peculiar emergent behaviors with potentially interesting applications
Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison
No full textThe field of metaheuristics for the application to combinatorial optimization problems is a rapidly growing field of research. This is due to the importance of combinatorial optimization problems for the scientific as well as the industrial world. We give a survey of the nowadays most important metaheuristics from a conceptual point of view. We outline the different components and concepts that are used in the different metaheuristics in order to analyze their similarities and differences. Two very important concepts in metaheuristics are intensification and diversification. These are the two forces that largely determine the behavior of a metaheuristic. They are in some way contrary but also complementary to each other. We introduce a framework, that we call the I&D frame, in order to put different intensification and diversification components into relation with each other. Outlining the advantages and disadvantages of different metaheuristic approaches we conclude by pointing out the importance of hybridization of metaheuristics as well as the integration of metaheuristics and other methods for optimization
Easyanalyzer: an object-oriented frameowrk for the experimental analysis of stochastic local search algorithms
No full textEvolutionary Music: Statistical Learning and Novelty for Automatic Improvisation
Full text linkIn this work we combine aspects of implicit learning with novelty search in an evolutionary algorithm with the aim to automatically generate melodies with improvisational flavour. Using Markov chains, the technique we present combines implicit statistical knowledge, extracted from musical corpora, with an adaptive novelty search mechanism. The algorithm is described along with the main design choices. Preliminary results are shown in two different musical contexts: Irish music and counterpoint compositions
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
