The Networks of genetic Processors (NGPs) are non-conventional models of computation based on genetic operations over strings, namely mutation and crossover operations as it was established in geneticalgorithms. Init...
详细信息
The Networks of genetic Processors (NGPs) are non-conventional models of computation based on genetic operations over strings, namely mutation and crossover operations as it was established in geneticalgorithms. Initially, they have been proposed as acceptor machines which are decision problem solvers. In that case, it has been shown that they are universal computing models equivalent to Turing machines. In this work, we propose NGPs as enumeration devices and we analyze their computational power. First, we define the model and we propose its definition as parallel genetic algorithms. Once the correspondence between the two formalisms has been established, we carry out a study of the generation capacity of the NGPs under the research framework of the theory of formal languages. We investigate the relationships between the number of processors of the model and its generative power. Our results show that the number of processors is important to increase the generative capability of the model up to an upper bound, and that NGPs are universal models of computation if they are formulated as generation devices. This allows us to affirm that parallel genetic algorithms working under certain restrictions can be considered equivalent to Turing machines and, therefore, they are universal models of computation.
The current intelligent scheduling method of foreign service staff based on intelligent optimization algorithm realizes the scheduling of staff by individual coding, which leads to the low stability of the algorithm b...
详细信息
ISBN:
(纸本)9781450396882
The current intelligent scheduling method of foreign service staff based on intelligent optimization algorithm realizes the scheduling of staff by individual coding, which leads to the low stability of the algorithm because the constraints and optimization of the objective function are not comprehensive enough. In this regard, the intelligent scheduling method of foreign service staff of busy time airlines based on parallelgenetic algorithm is proposed. By setting the optimal parameters such as population size, the objective function is constructed with the airline operation revenue and passenger service degree as the objectives, and the shallow copy of data is used to optimize and constrain the function, and the outbound flight service staff scheduling model is constructed. In the experiment, the stability of the proposed intelligent scheduling method is verified. The analysis of the experimental results shows that the objective function constructed by using the proposed method has a high degree of convergence and high stability.
Splitting a population into multiple instances is a technique used extensively in recent years to help improve the performance of nature-inspired optimization algorithms. Work on those populations can be done in paral...
详细信息
Splitting a population into multiple instances is a technique used extensively in recent years to help improve the performance of nature-inspired optimization algorithms. Work on those populations can be done in parallel, and they can interact asynchronously, a fact that can be leveraged to create scalable implementations based on, among other methods, distributed, multi-threaded, parallel, and cloud-native computing. However, the design of these cloud-native, distributed, multi-population algorithms is not a trivial task. Using as a foundation monolithic (single-instance) solutions, adaptations at several levels, from the algorithmic to the functional, must be made to leverage the scalability, elasticity, (limited) fault-tolerance, reproducibility, and cost-effectiveness of cloud systems while, at the same time, conserving the intended functionality. Instead of an evolutive approach, in this paper, we propose a cloud-native optimization framework created from scratch, that can include multiple (population-based) algorithms without increasing the number of parameters that need tuning. This solution goes beyond the current state of the art, since it can support different algorithms at the same time, work asynchronously, and also be readily deployable to any cloud platform. We evaluate this solution's performance and scalability, together with the effect other design parameters had on it, particularly the number and the size of populations with respect to problem size. The implemented platform is an excellent alternative for running locally or in the cloud, thus proving that cloud-native bioinspired algorithms perform better in their "natural" environment than other algorithms, and set a new baseline for scaling and performance of this kind of algorithms in the cloud. (C) 2020 Elsevier B.V. All rights reserved.
parallel island models (PIMs) are used to enhance the performance of evolutionary algorithms (EAs). In PIMs, each island executes an EA for evolving its local population, and periodically individuals migrate to neighb...
详细信息
parallel island models (PIMs) are used to enhance the performance of evolutionary algorithms (EAs). In PIMs, each island executes an EA for evolving its local population, and periodically individuals migrate to neighborhoods synchronously or asynchronously. Neighborhoods are organized through a topology of communication, and migration policies guide individual exchange. This work explores migration policies over different communication topologies in synchronous and asynchronous PIMs to improve the speed-up and accuracy of geneticalgorithms (GAs). The aim is to explain such models' adequacy from a general perspective, attempting to answer questions such as the best way to implement GAs in PIMs. To reach this goal, the quality of the solutions and the running time provided by proposed PIMs are evaluated over four .MP-hard problems of different combinatorial nature: reversal and translocation evolutionary distance, task mapping and scheduling, and N-Queens. The experiments show that tuning the parameters of the breeding cycle and migration policies is vital to guarantee that all proposed PIMs reach good speed-ups and more accurate solutions than the sequential GA. In addition, experiments ratify that synchronous models provide the best solutions, while asynchronous models deliver the best speed-ups. Finally, the results show that no model provides either better speed-up or accuracy in general since, as for sequential models, the nature of the problem define which would be the best-adapted PIM.
The Tartarus Problem is one of the candidate benchmark problems in evolutionary algorithms. We take advantage of the graphical processing unit (GPU) to improve the results of the software agents that use finite state ...
详细信息
The Tartarus Problem is one of the candidate benchmark problems in evolutionary algorithms. We take advantage of the graphical processing unit (GPU) to improve the results of the software agents that use finite state machines (FSMs) for this benchmark. While doing so we also contribute to the study of the problem on several grounds. Similar to existing studies we use geneticalgorithms to evolve FSMs, but unlike most of them we use adaptive operators for controlling the parameters of the algorithm. We show that the actual number of valid boards is not 297,040, but 74,760, because the agent is indifferent to the rotations of the board. We also show that the agent can only come across 383 different combinations, rather than 6561 that is used in the current literature. A final contribution is that we report the first true scores for the agents by testing them with all available 74,760 boards. Our best solution has a mean score of 8.5379 on all boards. (C) 2020 Elsevier Inc. All rights reserved.
Multicore processors are becoming common whereas current genetic algorithm-based implementation techniques for synthesizing Field Programmable Gate Array (FPGA) circuits do not fully exploit this hardware trend. Genet...
详细信息
ISBN:
(纸本)9781618397867
Multicore processors are becoming common whereas current genetic algorithm-based implementation techniques for synthesizing Field Programmable Gate Array (FPGA) circuits do not fully exploit this hardware trend. genetic Algorithm (GA) based techniques are known to optimize multiple objectives, and automate the process of digital circuit design. In this paper, parallel GA algorithms are proposed for the synthesis of digital circuits for LUT-based FPGA architectures. parallel modes of the GA such as Master-Slave and the Island model are compared to see which scheme results in better speedup and quicker convergence for effective utilization of current multicore hardware. Speedup of about five over the sequential single-threaded implementation is achieved with both the schemes on a six-core machine. Convergence is also found in fewer number of generations. The methods described here-in can be employed in Evolvable Hardware Systems as well as FPGA CAD tools.
Scalability issues might prevent geneticalgorithms from being applied to real world problems. Exploiting parallelisation in the cloud might be an affordable approach to getting time efficient solutions that benefit o...
详细信息
Scalability issues might prevent geneticalgorithms from being applied to real world problems. Exploiting parallelisation in the cloud might be an affordable approach to getting time efficient solutions that benefit of the appealing features of scalability, resource discovery, reliability, fault-tolerance and costeffectiveness. Nevertheless, parallel computation is very prone to cause considerable overhead for communication. Also, making geneticalgorithms distributed in an on-demand fashion is not trivial. Aiming at keeping under control the communication cost and, at the same time, supporting developers in the construction and deployment of parallel genetic algorithms, we designed and implemented a novel approach to distribute geneticalgorithms in the form of a cloud-based application. It is based on the master/slave model, exploiting software containers, their cloud orchestration and message queues. We also devised a conceptual workflow covering each cloud geneticalgorithms distribution phase, from resources allocation to actual deployment and execution, in an engineered fashion. Then, the application performance has been evaluated using a benchmark problem. According to the performance and setup times results, it emerged that the cloud can be considered a compelling way of scaling geneticalgorithms and an excellent alternative to other technologies strictly related to the physically owned hardware. (C) 2018 Elsevier B.V. All rights reserved.
The emergence of GPU-CPU heterogeneous architectures has led to a fundamental paradigm shift in parallel programming. Accelerating geneticalgorithms (GAs) on these architectures has received significant attention fro...
详细信息
The emergence of GPU-CPU heterogeneous architectures has led to a fundamental paradigm shift in parallel programming. Accelerating geneticalgorithms (GAs) on these architectures has received significant attention from both practitioners and researchers ever since GPUs emerged. In the past decade we have witnessed many progresses on migrating parallel GM from CPU to GPU (Graphical Processing Unit) architecture, which makes this research field truly enter into the world of High Performance Computing (HPC), and demonstrates a great potential to many research disciplines and industrial worlds that can benefit from the power of GPU accelerated stochastic global search to explore large and complex search spaces for better solutions. Designing a parallel algorithm on GPU is quite different from designing one on CPU. On CPU architecture, we typically consider how to distribute data across tens of CPU threads, while on GPU architecture, we have more than hundreds of thousands of GPU threads running simultaneously. Therefore, we should rethink the design approaches and implementation strategies of parallelalgorithms to fully utilize the computing power of GPUs to accelerate the computation of GAs. The intention of this paper is to give an overview on selective works of parallel GM designed for GPU architecture. In this survey paper, we first reexamine the concept of granularity of parallelism for GM on GPU architecture, discuss how the aspect of data layout affect the kernel design to maximize memory bandwidth, and explain how to organize threads in grid and blocks to expose sufficient parallelism to GPU. The comprehensive overview on selective works since 2010 then follows. The focus is mainly on the perspective of GPU architecture: how to accelerate GAs with GPU computing. Performance issues are not touched in this review, because most of these works are conducted on very early GPU cards, which are out of date already. We finally discuss some future research suggestions i
Achieving an optimal solution for NP-complete problems is a big challenge nowadays. The paper deals with the Traveling Salesman Problem (TSP) one of the most important combinatorial optimization problems in this class...
详细信息
Achieving an optimal solution for NP-complete problems is a big challenge nowadays. The paper deals with the Traveling Salesman Problem (TSP) one of the most important combinatorial optimization problems in this class. We investigated the parallelgenetic Algorithm to solve TSP. We proposed a general platform based on Hadoop MapReduce approach for implementing parallel genetic algorithms. Two versions of parallel genetic algorithms (PGA) are implemented, a parallelgenetic Algorithm with Islands Model (IPGA) and a new model named an Elite parallelgenetic Algorithm using MapReduce (EPGA) which improve the population diversity of the IPGA. The two PGAs and the sequential version of the algorithm (SGA) were compared in terms of quality of solutions, execution time, speedup and Hadoop overhead. The experimental study revealed that both PGA models outperform the SGA in terms of execution time, solution quality when the problem size is increased. The computational results show that the EPGA model outperforms the IPGA in term of solution quality with almost similar running time for all the considered datasets and clusters. geneticalgorithms with MapReduce platform provide better performance for solving large-scale problems.
This paper presents a fine-grained parallelgenetic algorithm improved with a 2-opt heuristic for finding solutions near to the optimum to the Quadratic Assignment Problem (QAP). The proposed algorithm is fully implem...
详细信息
ISBN:
(纸本)9783319984469;9783319984452
This paper presents a fine-grained parallelgenetic algorithm improved with a 2-opt heuristic for finding solutions near to the optimum to the Quadratic Assignment Problem (QAP). The proposed algorithm is fully implemented on Graphics Processing Units (GPUs). Unlike previous approaches reported in the literature our implementation a two-dimensional GPU grid of size 10x10 defines the population of the genetic algorithm (set of permutations of the QAP) and each GPU block consists of n GPU threads where n is the size of QAP. Each GPU block is used to represent the chromosome of a single individual and each GPU thread represents a gene of such chromosome. The proposed algorithm is tested on a subset of the standard QAPLIB data set. Our results show that our implementation is able to find good solutions for large QAP instances in few parallel iterations of the evolutionary process.
暂无评论