粒子群优化算法在复杂产品中的应用

-1-粒子群优化算法在复杂产品中的应用***（上海大学机电工程与自动化学院，上海200072）摘要：本文概述了复杂产品的概念、特性，分析了关于复杂产品的优化问题的特点。详细介绍了粒子群优化算法的原理和发展现状。同时总结了粒子群优化算法在复杂产品的生产制造中应用的主要方面。最后，通过一个虎钳装配序列规划的实例详细展示了粒子全算法的具体应用。关键词：粒子群算法；复杂产品；优化；应用ApplicationofParticleSwarmOptimizationinComplicatedProducts***(SchoolofMechatronicsEngineeringandAutomation,ShanghaiUniversity,Shanghai200072,China)Abstract:Thispaperoutlinestheconceptandfeaturesofcomplicatedproducts.Andthecharacteristicsofoptimizationproblemsincomplicatedproductsareanalyzed.ThePSOalgorithmtheoryanditsdevelopmentstatusareproposedindetail.AndmainaspectsofthePSOapplicationsincomplicatedproductsaresummarized.Finally,theapplicationprocessofPSOisillustratedviaexemplificationofassemblysequenceplanningforavise.Keywords:PSO;ComplicatedProducts;Optimization;Application0引言复杂产品（ComplicatedProduct）在一国经济中占据重要地位，它属于大型资本型产品，为生产“简单”产品以及提供现代化的服务创造了条件，因此它是经济和社会现代化的支撑平台[1]。复杂产品开发不确定、零件数量巨大、存在系统耦合等特性决定了其设计、制造、维护等过程极具复杂性。在全球化、集群化和信息化的发展趋势下，复杂产品研究开发、生产制造、营销服务和资本运作均已推向世界。在全球范围配置制造资源、形成制造业优势产业链、抢占世界市场已成为世界各国制造业发展的首选战略。在此背景下，复杂产品的生产制造业也面临着巨大的挑战。为了减少开发时间、控制生产节奏、合理化物流等以减少产品生产维护成本和降低风险、增强企业竞争力，需要对复杂产品的生产制造维护的各个环节进行优化。粒子群算法自从提出以来，引起了国际上众多相关领域学者的关注和研究。粒子群优化算法本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化。鉴于其通用性和有效性，在解决一些典型优化问题时，其性能甚至超过了遗传算法，已成功应用于函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化等众多领域。并且，由于其优化数学模型的简单，更加适合处理复杂问题，因而在复杂产品的设计、生产和维护领域得到了广泛的应用。-2-1复杂产品介绍复杂产品也称为复杂产品及系统，这个概念是20世纪90年代中期英国的一些学者在创新研究的过程中提出的，它是一个和简单产品相对应的概念，它是由产品所包含的元件的数量、种类、连接方式和实现功能的多少来决定的。Hobday认为，复杂产品是指高成本、技术密集、工程密集、客户定制的产品、系统、网络和建筑，它是相对于低成本、基于标准零部件的规模化生产的产品而言的[2]。1.1复杂产品特性复杂产品及系统包括了大型电信通讯系统、大型计算机、航空航天系统、智能大厦、电力网络控制系统、大型船只、高速列车、半导体生产线、信息系统等等，一般是关系到国计民生的大型产品和系统。与简单大规模生产的产品相比，复杂产品在产品特性、生产特性、市场特性等方面存在显著不同[3]：（1）产品特性复杂产品往往由许多具有复杂界面、为用户定制的子系统和元器件组成。单位成本较高，产品涉及多种知识和技能的应用，产品的生命周期较长，在产品投入使用或运营后，还需要根据客户的需求、技术变化等不断地进行改进和创新。（2）生产特性复杂产品系统一般为特定用户或市场以单件或小批量进行开发、定制和生产。项目决策可能需要数月甚至数年。生产的重点在于设计、开发、工程管理和系统集成。（3）市场特性复杂产品制造产业是一个资本密集型、技术密集型、劳动密集型相结合的产业。作为产业核心的复杂产品制造商也多为经济、技术实力雄厚的大企业。另一方面，由于复杂产品的特点，复杂产品的用户一般为政府、军方或者大型运营商，在复杂产品市场上，用户一般处于优势和主导地位。1.2复杂产品的优化复杂产品的优化包括：设计过程优化、供应链管理优化、生产制造过程优化、维护优化四大类。对复杂产品的优化目的在于通过分析复杂产品系统的动态模型，采用一定的优化算法进行优化，以建立更高效率、更合理、更可靠、成本更低的系统。复杂产品系统的优化过程与一般的项目优化过程相比具有如下特点：（1）优化涉及对象规模大、结构复杂，涉及多种学科领域和知识体系；（2）系统产品系统模型的数学描述是一个极其庞大的非线性优化问题；（3）由于复杂产品系统是多属性的，因此系统优化就是多属性优化或者是多属性综合优化；（4）优化模型本身存在着不确定性、非程序性、多目标性和矛盾性，并且系统优化各要素与人得主观因素的相互关联作用将产生更深的不确定性；常规方法对高维、非线性模型通常不能取得满意的结果。复杂产品的优化过程主要由四个步骤组成：①对系统进行数学建模，得到系统动态模型的数学描述；②分析系统的评价指标，即提取影响复杂产品系统性能、成本的关键因素；③采用优化方法建立优化数学模型，根据系统数学模型的特点，选择适当的优化算法，并建立相应的优化数学模型；④计算优化结果与评价，利用计算机根据优化数学模型计算得到优化结果，对结果进行合理性分析并决定是否继续优化过程。优化过程实质是建立优化方法，把一个多层次、多指标问题分解成单层次、单指标形式的优化问题，从而使系统平均意义上达到最优。2粒子群优化算法的原理粒子群优化算法[4]（ParticleSwarmOptimization，PSO）是1995年由美国社会心理学家JamesKennedy和电气工程师RussellEberhart共同提出，通过模拟鸟群的觅食过程，群体中的鸟被抽象成为没有质量和体积的“微粒”，通过这些“微粒”的相互协作和信息共享，其运动速度受到自身和群体的历史运动状态信息的影响，以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响，能较好地协调“微粒”本身和群体运动之间的关系，在复杂的解空间中寻找最优解。为了更好的阐述粒子群优化算法的原理，不失一般性求解全局最大值，数学模型描述为[5]：考虑全局优化max{𝑓(𝑥):𝑥∈𝛺},𝑓:𝛺∈𝑅𝑛→𝑅𝑙，𝛺为n维解空间，该问题的多个可行解组成一个种群(swarm)，种群中的每个元素（可行解）称为一个粒子(particle)粒子的个数称为种群规模(size)。向量𝑋𝑖=(𝑥𝑖1,𝑥𝑖2,…,𝑥𝑖𝑛)𝑇∈-3-Ω表示第i个粒子的位置，V𝑖=(𝑣𝑖1,𝑣𝑖2,…,𝑣𝑖𝑛)𝑇∈Ω表示第i个微粒的速度。粒子自身经历的最佳位置为𝑃𝑝𝑖=(𝑝𝑝𝑖1,𝑝𝑝𝑖2,…,𝑝𝑝𝑖𝑛)𝑇，种群中最佳位置为𝑃𝑔=(𝑝𝑔1,𝑝𝑔2,…,𝑝𝑔𝑛)𝑇。微粒在每一代中的速度和位置公式如下：xid(t+1)=xid(t)+vid(t+1),(1)vid(t+1)=vid(t)+c1rand()(ppid−xid(t))+c2rand()(pgi−xid(t)),(2)式中，i=1,2,…,n，rand()是服从U(0,1)分布的随机数，学习因子C1和C2为非负常数，C1=C2=2；𝑣𝑖𝑑(𝑡+1)是𝑣𝑖𝑑(𝑡)、(𝑝𝑝𝑖𝑑−𝑥𝑖𝑑(𝑡))、(𝑝𝑔𝑖−𝑥𝑖𝑑(𝑡)))构成的矢量和。通常，为了减少在进化过程中，微粒离开搜索空间的可能性，𝑣𝑖𝑗通常限定在一定的范围内，即𝑣𝑖𝑗∈[−𝑣𝑚𝑎𝑥,𝑣𝑚𝑎𝑥]。算法的基本流程如图1所示。从社会学的角度来分析，式（2）所描述的速度进化方程中，第一部分为微粒先前的速度，表示微粒对当前自身运动状态的信任；第二部分为“认知”部分，表示微粒本身的思考；第三部分为“社会部分”，表示微粒间的社会信息共享。“社会”部分可以通过代理概念[6]来理解，当观察者观察到某一行为加强时，将增加它实行该行为的概率，即微粒模仿优秀微粒的认知行为。图1PSO算法流程图3粒子群优化算法的研究现状PSO算法作为一种新颖的优化搜索算法，从其出现至今的十多年时间里，研究者对理论研究主要集中在以下两个个方面：（1）PSO算法的改进为了权衡“勘探”与“开发”，很多研究工作围绕基本PSO算法的改进展开。Shi等[7]引入了惯性权重ω的PSO算法，改进速度更新公式为：𝑣𝑖𝑑(𝑡+1)=𝜔𝑣𝑖𝑑(𝑡)+𝑐1𝑟𝑎𝑛𝑑()(𝑝𝑝𝑖𝑑−𝑥𝑖𝑑(𝑡))+𝑐2𝑟𝑎𝑛𝑑()(𝑝𝑔𝑖−𝑥𝑖𝑑(𝑡)),(3)由ω大小来调节算法的全局与局部寻优能力，ω值越大，全局寻优能力越强，局部寻优能力越弱；ω值越小，全局寻优能力越弱，局部寻优能力越强。Shi[8]通过惯性权值ω对优化性能影响的研究，发现较大的值有利于跳出局部极小点，而较小的值有利于算法收敛，提出了一种是根据算法迭代次数使惯性权值线性递减的方法，即另：否是开始随机初始化粒子群评价种群中每个个体的适应度通过适应度的比较来更新pbest和gbest根据式（1）和式（2）更新粒子的位置和速度是否达到最大迭代数结束-4-ω𝑡=𝜔𝑚𝑎𝑥−𝑡∗𝜔𝑚𝑎𝑥−𝜔𝑚𝑖𝑛𝑚𝑎𝑥𝑔𝑒𝑛,(4)式中，ωt为当前代数的惯性权值，ωmax、ωmin为惯性权值的上、下限值，t为当前迭代的代数，maxgen为最大迭代代数。Chatterjee等[9]提出非线性变化惯性权重的PSO算法，提高算法的收敛速度。Clerc[10]和Eberhart[11]为了保证算法的收敛性，采用收缩因子的方法，即选择和控制参数C1、C1和ω，使其满足：𝜔=2/|2−𝜑−√𝜑2−4𝜑|，𝜑=𝑐1+𝑐2,𝜑≥4(5)收缩因子法不再需要最大速度限制，但是后续研究表明设定最大速度限制可以提高算法的性能。Ratnaweera[12]的研究结果表明，在单模函数求解中收缩因子PSO优于带惯性因子的PSO算法，而在复杂函数求解中带惯性权重的PSO算法效果较优。对粒子群的邻域拓扑结构研究可以深刻理解PSO算法的工作方式，Richards[13]提出一种邻域结构随算法逐步由环形结构向完全连接进化的微粒群算法。Mohais等[14]将有向图的概念引入邻域结构模型，提出了随机边迁移和邻域两种动态改变邻域结构的方法。穆华平[15]等利用神经网络的小世界网络，动态调整邻居结构，提出了一种具有动态邻域结构的微粒群算法。倪庆剑[16]等引入多簇结构型拓扑，基于多簇结构提出了动态可变拓扑策略，通过控制PSO算法中最优信息的传播提高算法的性能。（2）PSO算法与其它算法的融合很多学者考虑把具有全局搜索能力的进化算法与PSO算法结合起来以获得更好的性能。PSO算法也是基于种群的方法，基于遗传算法的思想，Angeline[17]设计具有选择机制的PSO算法，该算法对复杂的测试函数效果较优。Rasmussen[18]提出了在每轮迭代中随机选择一定的粒子作为父代，随机两两交叉以产生具有新的子代粒子取代父代，并且把种群分为若干子种群，交叉可以在同一子种群内进行。目前引入变异因子来改善粒子群算法的全局搜索能力是一个热点。赫然[19]等研