Search

When we face real problems using computational resources, we understand that it is common to find combinatorial problems in binary domains. Moreover, we have to take into account a large number of possible candidate solutions, since these can be numerous and make it complicated for classical algorithmic techniques to address them. When this happens, in most cases, it becomes a problem due to the high resource cost they generate, so it is of utmost importance to solve these problems efficiently. To cope with this problem, we can apply other methods, such as metaheuristics. There are some metaheuristics that allow operation in discrete search spaces; however, in the case of continuous swarm intelligence metaheuristics, it is necessary to adapt them to operate in discrete domains. To perform this adaptation, it is necessary to use a binary scheme to take advantage of the original moves of the metaheuristics designed for continuous problems. In this work, we propose to hybridize the whale optimization algorithm metaheuristic with the Q-learning reinforcement learning technique, which we call (the QBWOA). By using this technique, we are able to realize an smart and fully online binarization scheme selector, the results have been statistically promising thanks to the respective tables and graphs. [ABSTRACT FROM AUTHOR]

Currently, the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems. In this sense, metaheuristics have been a common trend in the field in order to design approaches to solve them successfully. Thus, a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments. Following the No Free Lunch theorem, we are interested in testing the performance of the Fruit Fly Algorithm, this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces, based on the foraging behavior of the fruit fly, which usually has much better sensory perception of smell and vision than any other species. On the other hand, the Set Coverage Problem is a well-known NP-hard problem with many practical applications, including production line balancing, utility installation, and crew scheduling in railroad and mass transit companies. In this paper, we propose different binarization methods for the Fruit Fly Algorithm, using S-shaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space. We are motivated with this approach, because in this way we can deliver to future researchers interested in this area, a way to be able to work with continuous metaheuristics in binary domains. This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost. [ABSTRACT FROM AUTHOR]

We study a set of algorithms to discover the community structure of networks for languages from the Americas. Our experiments are based on a parallel corpus which allows us to represent each language as a co-occurrence network. Four methods to calculate network modularity, as a measure of the quality of community structure, were used. We studied several aspects of the community structure of co-occurrence networks. First, we were able to construct the map of modularity variations across languages from the Americas. With this, we separated large groups of languages into low- and high-modularity families. We suggested also a strong influence of functional words on low-modularity languages. Finally, we found a strong relationship between word entropy values and modularity. Our approach is thus a simple network-based contribution to face data scarcity of languages which are in danger of disappearing. [ABSTRACT FROM AUTHOR]

In complexity theory, there is a widely studied grouping of optimization problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set covering problem, known as one of Karp's 21 NP -complete problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set covering problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley's OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version. [ABSTRACT FROM AUTHOR]

Copyright of Cuadernos.info is the property of Pontificia Universidad Catolica de Chile, Facultad de Comunicaciones and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Constraint programming effectively solves constraint satisfaction and optimization problems by basically building, pruning, and exploring a search tree of potential solutions. In this context, a main component is the enumeration strategy, which is responsible for selecting the order in which variables and values are selected to build a possible solution. This process is known to be quite important; indeed a correct selection can reach a solution without failed explorations. However, it is well known that selecting the right strategy is quite challenging as their performance is notably hard to predict. During the last years, adaptive enumeration appeared as a proper solution to this problem. Adaptive enumeration allows the solving algorithm being able to autonomously modifying its strategies in solving time depending on performance information. In this way, the most suitable order for variables and values is employed along the search. In this paper, we present a new and more lightweight approach for performing adaptive enumeration. We incorporate a powerful classification technique named Top-k in order to adaptively select strategies along the resolution. We report results on a set of well-known benchmarks where the proposed approach noticeably competes with classical and modern adaptive enumeration methods for constraint satisfaction. [ABSTRACT FROM AUTHOR]

The balanced academic curriculum problem consists in the assignation of courses to academic periods satisfying all the load limits and prerequisite constraints. In this paper, we present the design of a solution to the balanced academic curriculum problem based on the ACO metaheuristic, in particular via the Best-Worst Ant System. We provide an experimental evaluation which illustrates the effectiveness of the proposed approach on a set of classic benchmarks as well as on real instances. [ABSTRACT FROM AUTHOR]

Subset problems (set partitioning, packing, and covering) are formal models for many practical optimization problems. A set partitioning problem determines how the items in one set (S) can be partitioned into smaller subsets. All items in S must be contained in one and only one partition. Related problems are set packing (all itemsmust be contained in zero or one partitions) and set covering (all itemsmust be contained in at least one partition).Here, we present a hybrid solver based on ant colony optimization (ACO) combined with arc consistency for solving this kind of problems. ACO is a swarm intelligence metaheuristic inspired on ants behavior when they search for food. It allows to solve complex combinatorial problems for which traditional mathematical techniques may fail. By other side, in constraint programming, the solving process of Constraint Satisfaction Problems can dramatically reduce the search space by means of arc consistency enforcing constraint consistencies either prior to or during search. Our hybrid approach was tested with set covering and set partitioning dataset benchmarks. It was observed that the performance of ACO had been improved embedding this filtering technique in its constructive phase. [ABSTRACT FROM AUTHOR]

Continuous query processing in data stream management systems (DSMS) has received considerable attention recently. Many applications share the same need for processing data streams in a continuous fashion. For most distributed streaming applications, the centralized processing of continuous queries over distributed data is simply not viable. This paper addresses the problem of computing approximate answers to continuous join queries over distributed data streams. We present a new method, called DHTJoin, which combines hash-based placement of tuples in a Distributed Hash Table (DHT) and dissemination of queries by exploiting the embedded trees in the underlying DHT, thereby incurring little overhead. DHTJoin also deals with join attribute value skew which may hurt load balancing and result completeness. We provide a performance evaluation of DHTJoin which shows that it can achieve significant performance gains in terms of network traffic. [ABSTRACT FROM AUTHOR]

Currently, industry is undergoing an exponential increase in binary-based combinatorial problems. In this regard, metaheuristics have been a common trend in the field in order to design approaches to successfully solve them. Thus, a well-known strategy includes the employment of continuous swarm-based algorithms transformed to perform in binary environments. In this work, we propose a hybrid approach that contains discrete smartly adapted population-based strategies to efficiently tackle binary-based problems. The proposed approach employs a reinforcement learning technique, known as SARSA (State–Action–Reward–State–Action), in order to utilize knowledge based on the run time. In order to test the viability and competitiveness of our proposal, we compare discrete state-of-the-art algorithms smartly assisted by SARSA. Finally, we illustrate interesting results where the proposed hybrid outperforms other approaches, thus, providing a novel option to tackle these types of problems in industry. [ABSTRACT FROM AUTHOR]