Genetic algorithm is a kind of the optimization method which is commonly used in NP problem for approximate optimal solution, and it has been widely used in national defense, scientific research, economic management, engineering construction, and other important fields.But some problems often appear during its solving process, such as premature convergence to local optimal solution and the high computational complexity.To solve these problems, first of all, this paper proposes a parallel processing mechanism based on the solution space division which implement parallel processing to solve the optimization problem by dividing the problem solution space.Then the mechanism is introduced into the genetic algorithm, and this paper proposes a parallel genetic algorithm based on the solution space division.Finally, the experimental comparison indicate that the proposed algorithm in parallel processing has a good linear speedup, at the same time overcoming the premature convergence to local optimal solution is better than the standard genetic algorithm and coarse-grained parallel genetic algorithm.%遗传算法是一种常用于NP问题中寻求近似最优解的优化方法,已被广泛应用于国防、科研、经济管理、工程建设等重要领域,但其求解过程中常出现过早收敛于局部最优解、计算复杂度高等问题.针对这些问题,论文首先给出一种基于解空间分割的并行处理机制,通过对问题解空间的分割实现求解最优化问题的并行化处理;然后将该机制引入到遗传算法中,提出了一种基于解空间分割的并行遗传算法;最后,经实验对比表明论文所提算法在并行化处理方面具有良好的线性加速比,同时证明在克服过早收敛于局部最优解方面要优于标准遗传算法和粗粒度并行遗传算法.
展开▼
