Metaheuristics are used for solving optimization problems since they are able to compute near optimal solutions in reasonable times. However, solving large instances it may pose a challenge even for these techniques. ...
详细信息
ISBN:
(纸本)9781424481262
Metaheuristics are used for solving optimization problems since they are able to compute near optimal solutions in reasonable times. However, solving large instances it may pose a challenge even for these techniques. For this reason, metaheuristics parallelization is an interesting alternative in order to decrease the execution time and to provide a different search pattern. In the last years, GPUs have evolved at a breathtaking pace. Originally, they were specific-purpose devices, but in a few years they became general-purpose shared memory multiprocessors. Nowadays, these devices are a powerful low cost platform for implementing parallel algorithms. In this paper, we present a preliminary version of PUGACE, a cellular evolutionary algorithm framework implemented on GPU. PUGACE was designed with the goal of providing a tool for easily developing this kind of algorithms. The experimental results when solving the Quadratic Assignment Problem are presented to show the potential of the proposed framework.
cellular evolutionary algorithms (cEAs) use structured populations whose evolutionary cycle is governed by local interactions among individuals. This helps to prevent the premature convergence to local optima that usu...
详细信息
cellular evolutionary algorithms (cEAs) use structured populations whose evolutionary cycle is governed by local interactions among individuals. This helps to prevent the premature convergence to local optima that usually takes place in panmictic populations. The present work extends cEAs by means of a message passing phase whose main effect is a more effective exploration of the search space. The mutated offspring that potentially replaces the original individual under cEAs is considered under message passing cellular evolutionary algorithms (MPcEAs) as a message sent from the original individual to itself. In MPcEAs, unlike in cEAs, a new message is sent from the original individual to each of its neighbors, representing a neighbor's mutated offspring whose second parent is selected from the neighborhood of the original individual. Thus, every individual in the population ultimately receives one additional candidate for replacement from each of its neighbors rather than having a unique candidate. Experimental tests conducted in the domain of real function optimization for continuous search spaces show that, in general, MPcEAs significantly outperform cEAs in terms of effectiveness. Specifically, the best solution obtained through MPcEAs has an importantly improved fitness quality in comparison with that obtained by cEAs.
Distributed parallel computing platforms contribute for a large part to some of the most powerful computers. Such architectures are typically based on accelerators (General Purpose computing on Graphics Processing Uni...
详细信息
ISBN:
(纸本)9781467376846
Distributed parallel computing platforms contribute for a large part to some of the most powerful computers. Such architectures are typically based on accelerators (General Purpose computing on Graphics Processing Units, Many Integrated Cores e.g Xeon Phi co-processors) and/or a large number of interconnected computing nodes. Obviously, they raise new challenges, typically in terms of scalability, robustness, adaptability and security. At the advent of the quest for Ultrascale Computing Systems, this paper addresses the issue of fault tolerance toward Byzantine failures overs such platforms. Indeed, the inherent unpredictable nature of these errors render their detection, not speaking of their correction, hard or even impossible to perform at large-scale. At this level, algorithm-Based Fault Tolerance (ABFT) techniques where the fault tolerance scheme is tailored to the algorithm performed, seems the most promising approaches to deal with such failures. In this context, evolutionaryalgorithms (EAs), especially panmictic global parallel EAs, exhibit a remarkable resilience against byzantine failures modeled as cheating faults as demonstrated either empirically or theoretically in previous studies [1], [2]. In this paper, we extend this analysis to the case of distributed EAs based on the cellular model leading to distributed cellular evolutionary algorithms (dCEAs). Our empirical study over a set or reference optimization problem confirm the ABFT nature of dCEAs. To our knowledge, this is the first study of dCEAs under the perspective of cheating issues and crash faults in a domain of distributed computations, thus opening new insights and perspectives for the design of competitive ultra-scale system based on evolutionary programming models.
In this paper, a new fine-grained evolutionary model, called CCLA-EM, is proposed for solving the optimization problems, which greatly overcomes the premature convergence problem of the existing evolutionaryalgorithm...
详细信息
In this paper, a new fine-grained evolutionary model, called CCLA-EM, is proposed for solving the optimization problems, which greatly overcomes the premature convergence problem of the existing evolutionaryalgorithms. In the proposed model, a combination of an evolutionaryalgorithm with a cellular learning automaton is used. The population individuals are distributed on the cells of a cellular learning automaton. Each individual interacts and cooperates with the individuals of neighboring cells to reach the global optimum. Distributing the population individuals on the cells of a cellular learning automaton allows the parallel implementation of the proposed model. Also, in different stages of the proposed model, numbers generated by a chaotic process are used instead of random ones. The use of numbers generated by a chaotic process leads to a complete search of the search space and hence avoids being trapped in local optima. Experiments on various benchmarks of the community structure detection problem indicate the superiority of the proposed model to the well-known algorithms GA-net and ICLA-net.
The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. I...
详细信息
The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a cellular memetic algorithm is proposed for solving the examination timetabling problem. cellular evolutionary algorithms are population-based metaheuristics. They differ from non-cellularalgorithms in that the population is organised in a cellular structure, providing for a smooth actualisation of the populations that contributes to improving the population diversity. The proposed cellular evolutionary algorithm is hybridised with the threshold acceptance local search metaheuristic. The implemented algorithm uses feasible genetic recombination and local search operators, thus limiting the exploration to the feasible solution space. The effect of the threshold acceptance used in the hybrid algorithm for the examination timetabling problem is studied. It is shown that a low threshold decreasing rate is needed in order to rearrange the most difficult exams in better periods, allowing for the easy set of exams to be placed in good periods as well. The approach was tested on the public Toronto and ITC 2007 benchmark sets. The proposed hybrid is able to attain four and three new upper bounds for the Toronto and ITC 2007 benchmark sets, respectively. (C) 2018 Elsevier Ltd. All rights reserved.
In this paper we propose integrating two collective computational intelligence techniques gene expression programming and cellular evolutionary algorithms with a view to induce expression trees, which, subsequently, s...
详细信息
ISBN:
(纸本)9783642166921
In this paper we propose integrating two collective computational intelligence techniques gene expression programming and cellular evolutionary algorithms with a view to induce expression trees, which, subsequently, serve as weak classifiers. From these classifiers stronger ensemble classifiers are constructed using majority-voting and boosting techniques. The paper includes the discussion of the validating experiment result confirming high quality of the proposed ensemble classifiers.
In this paper, we present a computationally inexpensive method for maintaining genetic diversity in evolutionaryalgorithms using population injection. As opposed to other methods, e.g., cellular EAs, population injec...
详细信息
ISBN:
(纸本)9781450343237
In this paper, we present a computationally inexpensive method for maintaining genetic diversity in evolutionaryalgorithms using population injection. As opposed to other methods, e.g., cellular EAs, population injection does not require any maintenance or setup effort. Here, we present first experimental results comparing a (mu, lambda) EA with and without population injection and a cellular EA using the h1 benchmark. As can be observed in the results, population injection is worth to be considered for problems which suffer from premature convergence.
暂无评论