18 research outputs found
The influence of linkage-learning in the linkage-tree GA when solving multidimensional knapsack problems
No full textUma abordagem com multi-mochilas multidimensionais para o problema de alocação de ações de redução de perdas na distribuição de energia
No full textIn developing countries, non-technical energy losses caused by factors unrelated to the transportation, transformation and distribution processes are considered by distribution companies as some of the greatest causes of loss. In Brazil, part of those losses can be passed on to consumers as an increase in the energy bill. However, the maximum value of this increase is limited by the regulatory agency, as a way to encourage distribution companies to make improvements on their activities. This limit is defined in the form of non-technical energy loss reduction goals. The optimization problem adressed in this work treats the loss reduction from the distribution companies point of view. In order to achieve the goals established by the regulatory agency, the companies have several loss reduction actions, which must be allocated in multiyear plans. These plans try to achieve the reduction goals without exceeding predefined budgets, always aiming to obtain the highest possible profit with the actions allocation. This work approaches the problem of those plans definition as a generalization of the Knapsack Problem. A formal model is defined as an integer programming problem and the model’s hardness is analysed through computational experiments, using a generic solver applied to a variety of instances to obtain the exact solution. Two heuristics are then proposed, the first one based in a greedy approach and the second on the Tabu Search metaheuristic, and applied to the problem. Finally, the techniques are compared considering the quality of the solutions.Em países em desenvolvimento, perdas não-técnicas são consideradas pelas companhias de distribuição de energia como algumas das maiores causas de prejuízos. No Brasil, parte dessas perdas pode ser repassada ao consumidor nas tarifas, entretanto o valor máximo deste repasse é limitado pela agência reguladora, como forma de incentivar melhorias por parte das distribuidoras. Este limite é definido na forma de metas de redução de perdas.
O problema de otimização abordado neste trabalho trata da redução de perdas do ponto de vista da distribuidora. Para atingir as metas estabelecidas pela agência reguladora, as distribuidoras possuem várias ações de redução de perdas, que devem ser alocadas em planos multianuais. Estes planos tentam atingir a meta estabelecida, respeitando alguns orçamentos disponíveis, e objetivando sempre obter o maior lucro possível com a alocação das ações. Este trabalho aborda o problema como uma generalização do Problema da Mochila. Uma modelagem formal é definida e a dificuldade da mesma é analisada através de testes computacionais, utilizando um resolvedor genérico aplicado a uma variedade de instâncias para obter a solução exata. Duas heurísticas são então propostas, a primeira baseada em uma abordagem gulosa e a segunda na metaheurística Busca Tabu, e aplicadas ao problema. Finalmente, as técnicas são comparadas considerando a qualidade das soluções encontradas
Investigating Smart Sampling as a population initialization method for Differential Evolution in continuous problems
No full textRecently, researches have shown that the performance of metaheuristics can be affected by population initialization. Opposition-based Differential Evolution (ODE), Quasi-Oppositional Differential Evolution (QODE), and Uniform-Quasi-Opposition Differential Evolution (UQODE) are three state-of-the-art methods that improve the performance of the Differential Evolution algorithm based on population initialization and different search strategies. In a different approach to achieve similar results, this paper presents a technique to discover promising regions in a continuous search-space of an optimization problem. Using machine-learning techniques, the algorithm named Smart Sampling (SS) finds regions with high possibility of containing a global optimum. Next, a metaheuristic can be initialized inside each region to find that optimum. SS and DE were combined (originating the SSDE algorithm) to evaluate our approach, and experiments were conducted in the same set of benchmark functions used by ODE, QODE and UQODE authors. Results have shown that the total number of function evaluations required by DE to reach the global optimum can be significantly reduced and that the success rate improves if SS is employed first. Such results are also in consonance with results from the literature, stating the importance of an adequate starting population. Moreover, SS presents better efficacy to find initial populations of superior quality when compared to the other three algorithms that employ oppositional learning. Finally and most important, the SS performance in finding promising regions is independent of the employed metaheuristic with which SS is combined, making SS suitable to improve the performance of a large variety of optimization techniques. (C) 2012 Elsevier Inc. All rights reserved.CAPES (a Brazilian Research Agency
On promising regions and optimization effectiveness of continuous and deceptive functions
No full textCaracterização do perfil de consumo de recursos de programas binários utilizando a técnica DAMICORE
No full text
General subpopulation framework and taming the conflict inside populations
No full textStructured evolutionary algorithms have been investigated for some time. However,\ud
they have been under explored especially in the field of multi-objective optimization.\ud
Despite good results, the use of complex dynamics and structures keep the understanding\ud
and adoption rate of structured evolutionary algorithms low. Here, we propose a\ud
general subpopulation framework that has the capability of integrating optimization\ud
algorithms without restrictions as well as aiding the design of structured algorithms.\ud
The proposed framework is capable of generalizing most of the structured evolutionary\ud
algorithms, such as cellular algorithms, island models, spatial predator-prey, and\ud
restricted mating based algorithms. Moreover, we propose two algorithms based on\ud
the general subpopulation framework, demonstrating that with the simple addition\ud
of a number of single-objective differential evolution algorithms for each objective,\ud
the results improve greatly, even when the combined algorithms behave poorly when\ud
evaluated alone at the tests. Most importantly, the comparison between the subpopulation\ud
algorithms and their related panmictic algorithms suggests that the competition\ud
between different strategies inside one population can have deleterious consequences\ud
for an algorithm and reveals a strong benefit of using the subpopulation framework
Enhanced Van der Waals calculations in genetic algorithms for protein structure prediction
No full textSeveral ab initio computational methods for protein structure prediction have been designed using full-atom models and force field potentials to describe interactions among atoms. Those methods involve the solution of a combinatorial problem with a huge search space. Genetic algorithms (GAs) have shown significant performance increases for such methods. However, even a small protein may require hundreds of thousands of energy function evaluations making GAs suitable only for the prediction of very small proteins. We propose an efficient technique to compute the van der Waals energy (the greatest contributor to protein stability) speeding up the whole GA. First, we developed a Cell-List Reconstruction procedure that divides the tridimensional space into a cell grid for each new structure that the GA generates. The cells restrict the calculations of van der Waals potentials to ranges in which they are significant, reducing the complexity of such calculations from quadratic to linear. Moreover, the proposal also uses the structure of the cell grid to parallelize the computation of the van der Waals energy, achieving additional speedup. The results have shown a significant reduction in the run time required by a GA. For example, the run time for the prediction of a protein with 147,980 atoms can be reduced from 217 days to 7 h.FAPESPCAPESCNP
