《元胞粒子群优化算法及其在柔性作业车间调度中的应用》由会员分享，可在线阅读，更多相关《元胞粒子群优化算法及其在柔性作业车间调度中的应用（76页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 元胞粒子群优化算法及其在柔性作业车间调度中的应用 姓名：石杨 申请学位级别：硕士 专业：工业工程 指导教师：高亮 2010-05-28 华 中 科 技 大 学 硕 士 学 位 论华 中 科 技 大 学 硕 士 学 位 论 文文 I 摘摘 要要 优化技术是一门以数学为基础，用于解决工程问题并为之提供最优解和满意解的 应用技术。在求解实际工程问题时，问题的多变量、多参数、非线性以及多约束等特 点使得优化成为一个极富挑战性的研究方向。粒子群优化算法是基于群体智能理论的 新兴的智能优化算法，该算法利用生物群体内个体的合作与竞争等行为指导搜索，原 理简单，参数较少，收敛速度快
2、，受到学术界的广泛关注。 本文首先介绍了基本的粒子群优化算法，总结了粒子群优化算法的研究与应用。 接着，从元胞自动机的角度分析粒子群优化算法，提出了元胞粒子群优化算法的总体 框架。根据元胞自动机的信息交互机制的不同，提出了内元胞粒子群优化算法和外元 胞粒子群优化算法。随后，针对两种元胞粒子群优化算法，分别对其收敛性进行了理 论分析，从数学角度证明了算法的收敛性。结合具体实例中的粒子轨迹，验证了提出 算法的有效性。 为了验证提出的两种元胞粒子群优化算法的有效性，本文选取了自 PSO 研究以来 比较有代表性的 9 个版本的 PSO 算法，分别针对 30 个著名的标准测试函数进行优化 测试，结果显示
3、了两种元胞粒子群优化算法的有效性。特别是外元胞粒子群优化算 法，对于大部分问题的优化结果优于其他版本的 PSO 算法。 接下来，本文设计了离散化的元胞粒子群优化算法求解柔性作业车间调度问题， 采用了针对问题本身特点的编码方法。在本算法中，采用有效的邻域函数，并利用禁 忌搜索思想指导局部搜索。基于标准测试问题的实验结果表明了该算法能有效地求解 柔性作业车间调度问题。 最后，对全文进行了总结，并对元胞粒子群优化算法的进一步研究方向进行了展 望。 关键词：关键词：粒子群优化算法 元胞自动机 元胞粒子群优化算法 柔性作业车间调度问题 禁忌搜索 华 中 科 技 大 学 硕 士 学 位 论华 中 科 技
4、大 学 硕 士 学 位 论 文文 II Abstract Optimization technique is a kind of application technology based on mathematics, aiming to solve engineering problems and provide the optimal solution or satisfactory solution. When solving real-world engineering problems, characteristics such as multivariable, nonlinear
5、, multiparameter, and multiconstraint of problems make optimization a very challenging research direction. Particle Swarm Optimization algorithm (PSO), a emerging intelligent optimization algorithm based on swarm intelligence theory, uses the cooperation and competition within the individuals of a b
6、iological swarm to guide the search. And it arouses wide academic attentions due to its simple principle, few parameters and fast convergence speed. Firstly, the basic PSO algorithm is introduced, and its developments and applications are summarized. Secondly, PSO is analyzed from the view of CA, an
7、d the general framework of Cellular Particle Swarm Optimization is proposed. According to the information exchange mechanism of CA, CPSO-inner and CPSO-outer are designed. Then, mathematical justification is conducted to analyze the convergence of CPSO-inner and CPSO-outer. In the following, the beh
8、aviors of a particle in CPSO-inner and CPSO-outer are discussed by presenting the trajectories of particles. Thirdly, in order to verify the effectiveness of the proposed algorithms, nine representative variants of PSO are selected to conduct the comparison on thirty famous benchmark problems. The e
9、xperimental results show the effectiveness of the two proposed algorithms, especially CPSO-outer, which outperforms other variants of PSO on most of problems. Next, CPSO is extended to a discrete version to better suit for Flexible Job Shop Scheduling Problem (FJSP), and an effective encoding method
10、 is adopted. In this algorithm, an effective neighborhood function is designed based on tabu search. The experimental results of benchmark problems for FJSP show that the proposed algorithm could effectively solve FJSP. Finally, the research in the dissertation is summarized, and the further researc
11、h direction of CPSO is discussed. Keywords: Particle Swarm Optimization; Cellular Automata; Cellular Particle Swarm Optimization; Flexible Job Shop Scheduling Problem；Tabu Search 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方
12、式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本论文属于 （请在以上方框内打） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华 中 科 技 大 学 硕 士 学 位 论华 中 科 技 大 学 硕 士 学 位 论 文文
13、1 1 绪绪 论论 1.1 课题概述课题概述 1.1.1 课题来源课题来源 国家863项目：复杂制造系统中与工艺规划集成的车间调度，项目编号： 2007AA04Z107。 1.1.2 课题目的课题目的 本课题的研究目的在于，通过研究粒子群优化算法的原理和寻优过程，分析其作 用机理；通过研究元胞自动机的原理，将元胞自动机思想应用于粒子群优化算法中， 提出元胞粒子群优化算法；通过数学分析来证明元胞粒子群优化算法的收敛性，并通 过大量的经典测试函数集合验证提出算法的有效性，对比已有的粒子群优化算法的研 究成果，验证本元胞粒子群优化算法的优越性。在此基础上，通过对柔性作业车间调 度问题的建模和分析，提
14、出应用元胞粒子群优化算法求解柔性作业车间调度问题的方 法。本课题的相关研究成果具有广泛的应用前景，一是对粒子群优化算法研究的有效 补充，使算法的性能得到有效提高，同时为柔性作业车间调度问题提供一种新而有效 的解法，缩短生产周期，节约生产成本，提高设备利用率，减少在制品库存，满足交 货期，从而提高制造企业的综合竞争力，为企业带来经济效益。 1.1.3 课题意义课题意义 最优化问题是人们在科学研究和工程应用等很多领域中经常遇到并需要解决的问 题。解决最优化问题的方法主要有两种：一种是精确方法，如运筹学中的分支定界 法，整数规划和拉格朗日松弛法等数学方法；另一种是近似方法，如一些启发式方法 和元启发
15、式方法。随着问题规模和复杂性的加大，精确方法不能很好地解决实际中的 大规模复杂优化问题，从而人们越来越多地将目光转向近似方法，特别是遗传算法、 禁忌搜索等算法、蚁群算法等元启发式方法12345，它能在合理的时间内求得问题 的最优解或近优解（满意解） ，以满足科学研究和工程应用的要求，它求解问题的优越 性得到越来越多学者的关注和研究。本文研究近年来提出的一种新型优化算法粒 子群优化算法，分析其优化机理，提高其优化性能，为实际问题提供一种有效解法， 对于解决复杂实际优化问题有重要意义。 华 中 科 技 大 学 硕 士 学 位 论华 中 科 技 大 学 硕 士 学 位 论 文文 2 元胞自动机是一种
16、时间和空间都离散的动力学模型，是研究复杂系统的一个典型 方法。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模 型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规 则构成。元胞自动机可以用于模拟现实中的物理过程和生物现象，其优点在于直接通 过简单的微观局部规则揭示复杂的宏观行为67。目前元胞自动机被广泛应用于模拟各 种物理系统和自然现象，在计算机、物理、化学、军事等领域有着广泛的应用。本文 将元胞自动机的思想应用于粒子群优化算法的研究，提出内元胞粒子群优化算法和外 元胞粒子群优化算法，来提高粒子群优化算法的性能，同时也通过算法的优化效果验 证了元胞自动机的重要作用。 车间调度问题一直是制造系统中一个研究的热点问题，也是理论研究中最为困难 的组合优化问题之一。随着科学的进步，生产方式的改进，生产机器性能和功能的提 高，车间的计划与调度问题变得越来越复杂。加之国际化分工与协作，产品的生产向 多品种、小批量发展，客户的需求也变得复杂多样，给企业实际的车间调
