Taxi-passenger matching plays a crucial role in modern taxi systems. However, currently, the greedy mechanisms are widely adopted, which may limit the quality of services provided by the systems. In this paper, we fir...
详细信息
ISBN:
(纸本)9781538627266
Taxi-passenger matching plays a crucial role in modern taxi systems. However, currently, the greedy mechanisms are widely adopted, which may limit the quality of services provided by the systems. In this paper, we first formulate the taxi-passenger matching as a global optimization problem by considering the pickup rate and average waiting time of passengers. Then, we propose a parallel genetic algorithm to solve the problem. New operators, including initialization, crossover, and mutation, are designed specifically for the problem. In addition, we use a divide-and-conquer strategy for dimension reduction. The problem is divided into a number of sub-problems according to the geographical locations of passengers and taxis. Each sub-problem is then solved in a parallel way by a sub-component of our proposed algorithm. Experimental results validate the effectiveness and efficiency of the proposed algorithm. It is able to greatly enhance the quality of services provided by the taxi systems.
A parallel genetic algorithm (GA) implemented on GPU clusters is proposed to solve the Uncapacitated Single Allocation Hub Location problem. The GA uses binary and integer encoding with genetic operators adapted to th...
详细信息
ISBN:
(纸本)9781509043200
A parallel genetic algorithm (GA) implemented on GPU clusters is proposed to solve the Uncapacitated Single Allocation Hub Location problem. The GA uses binary and integer encoding with genetic operators adapted to this problem. Our GA is improved by initially locating hubs at middle nodes. In our implementation we use the power of the GPU to compute in parallel several initial solutions, varying the number of hubs. The obtained experimental results compared with the best known solutions on all benchmarks. They show that our approach outperforms most well-known heuristics in terms of solution quality and time execution. Also it allowed to solve instances problem unsolved before.
Pairwise testing is an effective test generation technique that requires all pairs of parameter values to be by at least one test case. It has been proven that generating minimum test suite is an NP-complete problem c...
详细信息
Pairwise testing is an effective test generation technique that requires all pairs of parameter values to be by at least one test case. It has been proven that generating minimum test suite is an NP-complete problem covered geneticalgorithms have been used for pairwise test suite generation by researchers. However, it is always a time-consuming process, which leads to significant limitations and obstacles for practical use of geneticalgorithms towards large-scale test problems. parallelism will be an effective way to not only enhance the computation performance but also improve the quality of the solutions. In this paper, we use Spark, a fast and general parallel computing platform, to parallelize the geneticalgorithm to tackle the problem. We propose a two-phase parallelization algorithm including fitness evaluation parallelization and genetic operation parallelization. Experimental results show that our algorithm outperforms the sequential geneticalgorithm and competes with other approaches in both test suite size and computational performance. As a result, our algorithm is a promising improvement of the geneticalgorithm for pairwise test suite generation.
The current paper presents a path planning method based on probability maps and uses a new geneticalgorithm for a group of UAVs. The probability map consists of cells that display the probability which the UAV will n...
详细信息
The current paper presents a path planning method based on probability maps and uses a new geneticalgorithm for a group of UAVs. The probability map consists of cells that display the probability which the UAV will not encounter a hostile threat. The probability map is defined by three events. The obstacles are modeled in the probability map, as well. The cost function is defined such that all cells are surveyed in the path track. The simple formula based on the unique vector is presented to find this cell position. Generally, the cost function is formed by two parts;one part for optimizing the path of each UAV and the other for preventing UAVs from collision. The first part is a combination of safety and length of path and the second part is formed by an exponential function. Then, the optimal paths of each UAV are obtained by the geneticalgorithm in a parallel form. According to the dimensions of path planning, genetic encoding has two or three indices. A new genetic operator is introduced to select an appropriate pair of chromosome for crossover operation. The effectiveness of the method is shown by several simulations.
The serial geneticalgorithms (SGAs) have been widely applied in improving support vector machine (SVM) performance (e.g., classification accuracy), and these hybrid SGA-SVM methods show good capability to detect brea...
详细信息
The serial geneticalgorithms (SGAs) have been widely applied in improving support vector machine (SVM) performance (e.g., classification accuracy), and these hybrid SGA-SVM methods show good capability to detect breast cancer. However, there remain two great challenges: (1) the improvements tend to be at the great cost of time-consuming training;and (2) the SGA-based search may risk the premature convergence to local optima and thereby decrease the quality of the solutions found. The study aimed to investigate the use of parallel genetic algorithms (PGAs) in improving SVM performance, and build an efficient and accurate classifier of detecting breast cancer. A coarse-grained parallel genetic algorithm (CGPGA) was used to select a feature subset and optimize the parameters of SVM simultaneously. This approach (CGPGA-SVM) was then applied to a well characterized breast cancer dataset, consisting of 699 samples (458 benign and 241 malignant samples). In addition, the proposed CGPGA-SVM classier was compared with a range of SVM-based classifiers to understand its performance improvements. Compared with the SGA-SVM classifier, the training time of the CGPGA-SVM classier decreased by 75.77% on a commonly used 4-core CPU;moreover, the classification accuracy and sensitivity of the CGPGA-SVM classifier increased by 0.43% and 1.25%, respectively.
Multiprocessor task scheduling is one of the hardest combinatorial optimization problems in parallel and distributed systems. It is known as NP-hard and therefore, scanning the whole search space using an exact algori...
详细信息
ISBN:
(纸本)9781509006793
Multiprocessor task scheduling is one of the hardest combinatorial optimization problems in parallel and distributed systems. It is known as NP-hard and therefore, scanning the whole search space using an exact algorithm to find the optimal solution is not practical. Instead, metaheuristics are mostly employed to find a near-optimal solution in a reasonable amount of time. In this paper, a multi-population based parallel genetic algorithm is presented for the optimization of multiprocessor task scheduling in the presence of communication costs. To the best of our knowledge, this parallel genetic algorithm approach is applied to the problem at hand for the first time using a benchmark set that includes well-known task graphs from different sources. Our experiments conducted on several task graphs with different sizes from the benchmark set showed the superiority of the approach over a conventional geneticalgorithm and the related works in the literature in terms of two different performance metrics. Our parallel implementation not only decreased the execution time but also increased the quality of the scheduling solutions considerably.
Taxi-passenger matching plays a crucial role in modern taxi systems. However, currently, the greedy mechanisms are widely adopted, which may limit the quality of services provided by the systems. In this paper, we fir...
详细信息
Taxi-passenger matching plays a crucial role in modern taxi systems. However, currently, the greedy mechanisms are widely adopted, which may limit the quality of services provided by the systems. In this paper, we first formulate the taxi-passenger matching as a global optimization problem by considering the pickup rate and average waiting time of passengers. Then, we propose a parallel genetic algorithm to solve the problem. New operators, including initialization, crossover, and mutation, are designed specifically for the problem. In addition, we use a divide-and-conquer strategy for dimension reduction. The problem is divided into a number of sub-problems according to the geographical locations of passengers and taxis. Each sub-problem is then solved in a parallel way by a sub-component of our proposed algorithm. Experimental results validate the effectiveness and efficiency of the proposed algorithm. It is able to greatly enhance the quality of services provided by the taxi systems.
Multiprocessor task scheduling is one of the hardest combinatorial optimization problems in parallel and distributed systems. It is known as NP-hard and therefore, scanning the whole search space using an exact algori...
详细信息
ISBN:
(纸本)9781509006809
Multiprocessor task scheduling is one of the hardest combinatorial optimization problems in parallel and distributed systems. It is known as NP-hard and therefore, scanning the whole search space using an exact algorithm to find the optimal solution is not practical. Instead, metaheuristics are mostly employed to find a near-optimal solution in a reasonable amount of time. In this paper, a multi-population based parallel genetic algorithm is presented for the optimization of multiprocessor task scheduling in the presence of communication costs. To the best of our knowledge, this parallel genetic algorithm approach is applied to the problem at hand for the first time using a benchmark set that includes well-known task graphs from different sources. Our experiments conducted on several task graphs with different sizes from the benchmark set showed the superiority of the approach over a conventional geneticalgorithm and the related works in the literature in terms of two different performance metrics. Our parallel implementation not only decreased the execution time but also increased the quality of the scheduling solutions considerably.
In this paper, we present the step parallelization of a dividing geneticalgorithm (DGA) for the parallel, distributed, and distributed/parallel computing environments. The DGA is employed in a method for road traffic...
详细信息
ISBN:
(纸本)9781467379670
In this paper, we present the step parallelization of a dividing geneticalgorithm (DGA) for the parallel, distributed, and distributed/parallel computing environments. The DGA is employed in a method for road traffic network division, which we developed. The step parallelization, which performs all steps of the geneticalgorithm at least partially concurrently, is an alternative to the commonly used island model for the parallelization of geneticalgorithms. All three non-sequential executions of the DGA were thoroughly tested and compared to the sequential DGA. The results are also part of the paper.
Graph coloring problem (GCP) has proven to be an NP hard problem, until now there is no way to solve it in polynomial time. In this paper, a novel parallel genetic algorithm is presented to solve the GCP based on Comp...
详细信息
ISBN:
(纸本)9781467392006
Graph coloring problem (GCP) has proven to be an NP hard problem, until now there is no way to solve it in polynomial time. In this paper, a novel parallel genetic algorithm is presented to solve the GCP based on Compute Unified Device Architecture (CUDA). The initialization, crossover, mutation and selection operators are designed parallel in threads. Moreover, the performance of our algorithm is compared with the other graph coloring algorithms using benchmark graphs, and experimental results show that our algorithm converges much more quickly than other algorithms and achieves competitive performance for solving graph coloring problem.
暂无评论