GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found. © 2011 Elsevier Ltd. All rights reserved.

Domain reduction using GRASP construction phase for transmission expansion planning problem

This paper proposes a new strategy to reduce the combinatorial search space of a mixed integer linear programming (MILP) problem. The construction phase of greedy randomized adaptive search procedure (GRASP-CP) is employed to reduce the domain of the integer variables of the transportation model of the transmission expansion planning (TM-TEP) problem. This problem is a MILP and very difficult to solve specially for large scale systems. The branch and bound (BB) algorithm is used to solve the problem in both full and the reduced search space. The proposed method might be useful to reduce the search space of those kinds of MILP problems that a fast heuristic algorithm is available for finding local optimal solutions. The obtained results using some real test systems show the efficiency of the proposed method. © 2012 Springer-Verlag.

The acylpolyamines from spider venoms

Acylpolyamines are low molecular mass toxins occurring exclusively in the venoms from solitary wasps and some groups of spiders. Their chemical structures have been elucidated using hyphenated techniques of mass spectrometry, such as LC-MS and MS/MS, or through direct analysis with different types of NMR analyses. The chemical structures of the acylpolyamine toxins from the venoms of Nephilinae orb-web spiders appear to be organized into four parts based on the combinatorial way that the chemical building blocks are bound to each other. An aromatic moiety (part I) is connected through a linker amino acid (part II) to a polyamine chain (part III), which in turn may be connected to an optional tail (part IV). The polyamine chains were classified into seven subtypes according to the different combinations of chemical building blocks. These polyamine chains, in turn, are connected to one of three chromophore moieties: a 2,4-dihydroxyphenyl acetyl group, a 4-hydroxyindolyl acetyl group, or an indolyl acetyl group. They may be connected through an asparagine residue or sometimes through the dipeptide ornithyl asparagine. Also, nine different types of backbone tails may be attached to the polyamine chains. These toxins are noncompetitive blockers of ionotropic glutamate receptors with neuroprotective action against the neuronal death and antiepileptic effect. Thus, compounds of this class of spider venom toxin seem to represent interesting molecular models for the development of novel neuropharmaceutical drugs. © 2012 Elsevier B.V. All rights reserved.

A genetic algorithm for crop rotation

In the last few years, crop rotation has gained attention due to its economic, environmental and social importance which explains why it can be highly beneficial for farmers. This paper presents a mathematical model for the Crop Rotation Problem (CRP) that was adapted from literature for this highly complex combinatorial problem. The CRP is devised to find a vegetable planting program that takes into account green fertilization restrictions, the set-aside period, planting restrictions for neighboring lots and for crop sequencing, demand constraints, while, at the same time, maximizing the profitability of the planted area. The main aim of this study is to develop a genetic algorithm and test it in a real context. The genetic algorithm involves a constructive heuristic to build the initial population and the operators of crossover, mutation, migration and elitism. The computational experiment was performed for a medium dimension real planting area with 16 lots, considering 29 crops of 10 different botanical families and a two-year planting rotation. Results showed that the algorithm determined feasible solutions in a reasonable computational time, thus proving its efficacy for dealing with this practical application.

BBA: A binary bat algorithm for feature selection

Feature selection aims to find the most important information from a given set of features. As this task can be seen as an optimization problem, the combinatorial growth of the possible solutions may be in-viable for a exhaustive search. In this paper we propose a new nature-inspired feature selection technique based on the bats behaviour, which has never been applied to this context so far. The wrapper approach combines the power of exploration of the bats together with the speed of the Optimum-Path Forest classifier to find the set of features that maximizes the accuracy in a validating set. Experiments conducted in five public datasets have demonstrated that the proposed approach can outperform some well-known swarm-based techniques. © 2012 IEEE.

Photodynamic and Antibiotic Therapy Impair the Pathogenesis of Enterococcus faecium in a Whole Animal Insect Model

Enterococcus faecium has emerged as one of the most important pathogens in healthcare-associated infections worldwide due to its intrinsic and acquired resistance to many antibiotics, including vancomycin. Antimicrobial photodynamic therapy (aPDT) is an alternative therapeutic platform that is currently under investigation for the control and treatment of infections. PDT is based on the use of photoactive dye molecules, widely known as photosensitizer (PS). PS, upon irradiation with visible light, produces reactive oxygen species that can destroy lipids and proteins causing cell death. We employed Galleria mellonella (the greater wax moth) caterpillar fatally infected with E. faecium to develop an invertebrate host model system that can be used to study the antimicrobial PDT (alone or combined with antibiotics). In the establishment of infection by E. faecium in G. mellonella, we found that the G. mellonella death rate was dependent on the number of bacterial cells injected into the insect hemocoel and all E. faecium strains tested were capable of infecting and killing G. mellonella. Antibiotic treatment with ampicillin, gentamicin or the combination of ampicillin and gentamicin prolonged caterpillar survival infected by E. faecium (P = 0.0003, P = 0.0001 and P = 0.0001, respectively). In the study of antimicrobial PDT, we verified that methylene blue (MB) injected into the insect followed by whole body illumination prolonged the caterpillar survival (P = 0.0192). Interestingly, combination therapy of larvae infected with vancomycin-resistant E. faecium, with antimicrobial PDT followed by vancomycin, significantly prolonged the survival of the caterpillars when compared to either antimicrobial PDT (P = 0.0095) or vancomycin treatment alone (P = 0.0025), suggesting that the aPDT made the vancomycin resistant E. faecium strain more susceptible to vancomycin action. In summary, G. mellonella provides an invertebrate model host to study the antimicrobial PDT and to explore combinatorial aPDT-based treatments.

A heuristic algorithm based on multi-assignment procedures for nurse scheduling

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses' preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. © 2013 Springer Science+Business Media New York.

The integrated lot sizing and cutting stock problem in a furniture factory

This work studies the integrated lot sizing and cutting stock problem, where the goal is to capture the dependency that exists between two important decisions in the production process, in order to economize raw materials and also reduce production and inventory costs. The integrated lot sizing and cutting stock problem is studied in a small furniture factory that produces wardrobes, dressing tables and cupboards and the lot sizing and cutting stock decisions are taken by the production manager. A column-generation technique is used to solve a linear relaxation of the proposed model. The computational results, using real data from the factory, show that it is possible to reduce total inventory and raw material costs when integrated planning is used. © 2013 IFAC.

Binary Bat Algorithm for Feature Selection

Feature selection aims to find the most important information to save computational efforts and data storage. We formulated this task as a combinatorial optimization problem since the exponential growth of possible solutions makes an exhaustive search infeasible. In this work, we propose a new nature-inspired feature selection technique based on bats behavior, namely, binary bat algorithm The wrapper approach combines the power of exploration of the bats together with the speed of the optimum-path forest classifier to find a better data representation. Experiments in public datasets have shown that the proposed technique can indeed improve the effectiveness of the optimum-path forest and outperform some well-known swarm-based techniques. © 2013 Copyright © 2013 Elsevier Inc. All rights reserved.

Optimizing feature selection through binary charged system search

Feature selection aims to find the most important information from a given set of features. As this task can be seen as an optimization problem, the combinatorial growth of the possible solutions may be inviable for a exhaustive search. In this paper we propose a new nature-inspired feature selection technique based on the Charged System Search (CSS), which has never been applied to this context so far. The wrapper approach combines the power of exploration of CSS together with the speed of the Optimum-Path Forest classifier to find the set of features that maximizes the accuracy in a validating set. Experiments conducted in four public datasets have demonstrated the validity of the proposed approach can outperform some well-known swarm-based techniques. © 2013 Springer-Verlag.

Análise e implementação de um algoritmo de busca dispersa para o planejamento da expansão de sistemas de transmissão

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Novas aplicações de metaheurísticas na solução do problema de planejamento da expansão do sistema de transmissão de energia elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Metaheurística GRASP para o problema de planejamento da expansão de sistemas de transmissão de energia elétrica

Pós-graduação em Engenharia Elétrica - FEIS

Metaheurística particle swarm utilizada para alocação ótima de bancos de capacitores em sistemas de distribuição radial

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Uma ferramenta alternativa para síntese de circuitos lógicos usando a técnica de circuito evolutivo

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)