并行遗传算法研及其在组合优化问题中的应用.pdf

并行遗传算法研究及其在组合优化问题中的应用 摘要 遗传算法 Genetic Algorithm 作为一种基于模仿生物自然选择和遗传原理的高效有哪些信誉好的足球投注网站 技术 已经成功应用于工程设计 工商管理 科学实验等领域中的复杂优化问题的求解 一 般来讲 遗传算法可以在合理的计算时间内发现问题的满意最优解 随着科学技术的不断发 展 问题的规模不断扩大 面对复杂程度越来越高的有哪些信誉好的足球投注网站空间 遗传算法在优化效率(时间) 和求解质量上都显得 力不从心 并行遗传算法将并行计算机的高速并行性和遗传算法天 然的并行性相结合 极大地促进了遗传算法的研究与应用 并行处理的引入不但加速了遗传 算法的有哪些信誉好的足球投注网站过程 而且由于种群规模的扩大和各子种群的隔离 使种群的多样性得以丰富和 保持 减少了未成熟收敛的可能性 提高了求解质量 本文第一章对遗传算法及其基本理论进行了简要的回顾 然后在第二章里对并行遗传算 法 Parallel Genetic Algorithm, PGA 从其分类 工作机理等方面进行了介绍 在并行遗传算法里 粗粒度并行遗传算法 coarse grain parallel genetic algorithm 是研 究和应用最广的一类 它可以在多种计算环境中用MPI Message Passing Interface 来实现 MPI 是一种重要的消息传递并行编程模式的标准 本文第三章里对有关的MPI并行编程技术 进行了介绍 并在第四章里给出了用MPI实现的粗粒度并行遗传算法基本程序的说明 在第五章中 我们在基本粗粒度并行遗传算法的实现基础上 提出一种用基因块编码的 并行遗传算法 Building-block Coded Parallel GA简称 BCPGA该方法以粗粒度并行 遗传算法为基本框架 从染色体群体中识别出可能的基因块 然后用基因块作为新的基因单 位对染色体重新编码 产生长度较短的染色体作为下一次演化的初始群体 如此循环演化 直至结束 旅行商问题 Traveling Salesman ProblemTSP是经典的组合优化问题 和连续函 数的优化问题不同 组合优化问题大部分都没有解析解法 使用最多的是有哪些信誉好的足球投注网站类方法 我们 将BCPGA应用于一个 100城市的旅行商问题中 实验证明此方法可以提高遗传算法的有哪些信誉好的足球投注网站效 率,并且在相同条件下 BCPGA明显优于单纯的粗粒度并行遗传算法 Job-Shop问题是经典的生产线调度问题 此类问题是NP-hard难题 随着问题规模的 扩大 传统的分析方法在求解时间上会出现指数级的扩大 Job-Shop比经典的组合优化难 题 旅行商问题难度更大 使用遗传算法求解Job-Shop问题的一个关键问题是编码 在第六章里 我们提出了一 种求解Job-Shop问题的新的遗传算法的方法RPGARe-encoding Parallel GA此方法的 编码方式将Job-Shop问题转换为一个TSPTraveling Salesman问题 使得关Problem 于 TSP问题的遗传算法的方法可以用于解决 Job-Shop问题 这种编码方式可以满足 Job-Shop问题对工件加工顺序的要求 避免在进化过程中产生非可行解 RPGA的最重要的 特点在于染色体的再编码过程 再编码过程根据各工序的开工时间先后对染色体的各基因重 新赋值 使得编码空间和解空间一一对应 最后 本方法使用MPI并行编程技术实现了粗粒 度的并行模型 在此模型上我们对Fisher和Thompson的 10x10问题进行了求解实验 实 验表明本方法有这良好的求解效率 也证明了对染色体再编码过程对此问题的重要性 关键词 并行遗传算法 组合优化问题 MPI 旅行商问题 作业车间调度问题 Parallel Genetic Algorithms Research and Application in Combinatorial Problems As a kind of optimization techniques motivated from the principles of biological evolution and genetics, the Genetic Algorithms have been su