下载文档原格式
基于粒子群算法求解多目标优化问题一、本文概述随着科技的快速发展和问题的日益复杂化，多目标优化问题在多个领域，如工程设计、经济管理、环境保护等，都显得愈发重要。
传统的优化方法在处理这类问题时，往往难以兼顾多个目标之间的冲突和矛盾，难以求得全局最优解。
因此，寻找一种能够高效处理多目标优化问题的方法，已成为当前研究的热点和难点。
粒子群算法（Particle Swarm Optimization, PSO）作为一种群体智能优化算法，具有收敛速度快、全局搜索能力强等优点，已经在多个领域得到了广泛应用。
近年来，粒子群算法在多目标优化问题上的应用也取得了显著的成果。
本文旨在探讨基于粒子群算法求解多目标优化问题的原理、方法及其应用，为相关领域的研究提供参考和借鉴。
本文首先介绍多目标优化问题的基本概念和特性，分析传统优化方法在处理这类问题时的局限性。
然后，详细阐述粒子群算法的基本原理和流程，以及如何将粒子群算法应用于多目标优化问题。
接着，通过实例分析和实验验证，展示基于粒子群算法的多目标优化方法在实际问题中的应用效果，并分析其优缺点。
对基于粒子群算法的多目标优化方法的发展趋势和前景进行展望，为未来的研究提供方向和建议。
二、多目标优化问题概述多目标优化问题（Multi-Objective Optimization Problem, MOP）是一类广泛存在于工程实践、科学研究以及社会经济等各个领域中的复杂问题。
与单目标优化问题只寻求一个最优解不同，多目标优化问题涉及多个相互冲突的目标，这些目标通常难以同时达到最优。
因此，多目标优化问题的解不再是单一的最优解，而是一组在各个目标之间达到某种平衡的最优解的集合，称为Pareto最优解集。
多目标优化问题的数学模型通常可以描述为：在给定的决策空间内，寻找一组决策变量，使得多个目标函数同时达到最优。
这些目标函数可能是相互矛盾的，例如，在产品设计中，可能同时追求成本最低、性能最优和可靠性最高等多个目标，而这些目标往往难以同时达到最优。
基于粒子群算法的多目标优化问题研究一、引言随着各行各业的发展，许多问题的优化变得越来越复杂，不同的目标也需要在一定的限制条件下得到最好的解决方案。
多目标优化问题因其需要同时考虑多个目标而更加困难，因此需要一种高效而有效的算法解决。
粒子群算法(PSO)作为群体智能算法的一种，因其易于实现和全局搜索能力而成为应用最广泛的算法之一，在多目标优化问题中也有很好的表现。
本文将研究基于粒子群算法的多目标优化问题。
二、粒子群算法粒子群算法是模拟鸟群捕食行为而发展出来的一种群体智能算法，其核心思想是模拟所有粒子的位置和速度，在每个时间步更新粒子的速度和位置，通过不断迭代，搜索到全局最优解。
具体来说，粒子群算法的基本步骤如下：1.初始化粒子位置和速度；2.计算每个粒子的适应度值；3.记录全局最优解和个体最优解；4.更新速度和位置；5.重复2-4步骤，直至达到停止条件。
在更新速度和位置时，粒子的速度和位置受到自身和全局最优解的影响，其中自身影响称为认知因子(cognitive factor)，全局最优解的影响称为社会因子(social factor)。
通过调节这两个因子的权重，可以控制算法的搜索行为。
三、多目标优化问题多目标优化问题要求在一定的约束条件下，同时最小化或最大化多个目标函数。
例如，在工程设计中，需要考虑成本、重量、强度等多个因素，而这些因素之间通常存在着矛盾关系，需要在达到一定平衡的情况下得到最优方案。
具体来说，多目标优化问题的数学定义为：$$min_{x∈X}\ \{f(x)=(f_1(x),f_2(x),...,f_m(x))\}$$其中，$X$为问题的可行解集合，$m$为目标函数个数。
多目标优化问题需要使用一种多维坐标表示方法，这样才能方便地对多个目标函数进行比较。
四、基于粒子群算法的多目标优化问题研究在多目标优化问题中，粒子群算法需要进行一些改进才能达到更好的效果。
本文将介绍三种基于粒子群算法的改进算法。
基于粒子群优化算法的多目标优化问题研究随着计算机技术的快速发展，在各种领域中需要处理的大规模、多维度的多目标优化问题越来越复杂，传统的优化算法已经无法满足实际需求。
粒子群优化算法（Particle Swarm Optimization，PSO）作为一种全局优化方法，在多目标优化问题中得到了广泛的应用。
PSO算法是一种模拟生物群体行为的优化算法，通过模拟“鸟群寻食”等行为，将种群成员看作是在一个信息空间中的“粒子”，通过迭代搜索过程来寻找优化问题的全局最优解或近似最优解。
与遗传算法（Genetic Algorithm，GA）和模拟退火算法（Simulated Annealing，SA）等传统优化算法相比，粒子群算法具有收敛速度较快、易于实现等优势，因此得到了广泛应用。
在多目标优化问题中，PSO算法的应用也越来越广泛。
多目标优化问题是指需要优化多个目标函数的问题，例如在工程设计中需要优化的成本、效率、质量等多个目标函数。
传统的单目标优化算法无法解决这一类型的问题，而多目标优化算法则可以同时优化多个目标函数，得到一系列的最优解。
多目标优化算法中，粒子群算法的应用主要包括两种方法：帕累托前沿解方法和加权函数法。
帕累托前沿解方法是指通过多次迭代搜索，得到所有非支配解并构成帕累托前沿。
而加权函数法则是通过设定一组加权参数，将多个目标函数进行线性叠加得到一个单一目标函数，并利用粒子群算法进行迭代搜索，得到合适的加权参数。
在帕累托前沿解方法中，PSO算法的核心是根据粒子间的相对位置、速度信息来决定每个粒子的移动方向和速度，以实现问题的最优化。
该方法通过同时优化多个目标函数，得到一系列非支配解并构成帕累托前沿。
具体来说，将每个粒子看作是某一个解空间中的一个候选点，每个粒子具有自己的位置和速度。
每次迭代时，都会更新每个粒子的速度和位置，并根据当前位置的目标函数值来调整粒子的位置。
通过循环迭代，最终得到帕累托前沿解。
基于多目标粒子群算法的配电网多目标优化重构陈萍;毛弋;童伟;邓海潮;陈艳平;胡躲华【摘要】本文建立了系统有功损耗、节点最低电压幅值及开关操作次数的配电网多目标优化重构模型,并运用多目标粒子群优化算法求解.多目标粒子群算法的关键是如何选取个体的极值和全局极值,本文依据Pareto支配关系对个体极值进行选择,外部存储器就是全局极值的候选解集,计算外部存储器中各粒子与其他粒子的海明距离之和并作为各粒子的适应值,然后采用与适应值呈比例的轮盘赌方式选取粒子的全局最优位置,避免种群多样性的丧失.带时限的粒子全局极值淘汰策略使粒子能跳出局部最优,防止算法早熟收敛,保持了良好的收敛性.通过IEEE 33节点测试系统仿真计算,实验结果表明了该方法的可行性和有效性.【期刊名称】《电力系统及其自动化学报》【年(卷),期】2016(028)007【总页数】5页(P68-72)【关键词】多目标优化;配电网重构;粒子群算法;Pareto支配;海明距离【作者】陈萍;毛弋;童伟;邓海潮;陈艳平;胡躲华【作者单位】湖南大学电气与信息工程学院,长沙410082;湖南大学电气与信息工程学院,长沙410082;湖南大学电气与信息工程学院,长沙410082;湖南大学电气与信息工程学院,长沙410082;湖南大学电气与信息工程学院,长沙410082;湖南大学电气与信息工程学院,长沙410082【正文语种】中文【中图分类】TM72配电网络中含有大量的常闭分段开关与少量的常开联络开关，配电网重构就是通过变换这些开关的开断状态来改变网络拓扑结构。
通过重构可以降低网损、均衡线路负荷、消除过载、提高供电电压质量等［1］。
以往的研究大多数只选取配电网的1个指标进行单目标优化［2-9］，而配电网重构是多目标非线性混合优化问题。
传统的配电网多目标优化重构方法中，对多目标采取加权法［10-11］，将多目标问题转换成单目标后再加以求解。
优化结果受权重系数影响较大，算法每次运行只能得到1个解，多次运行程序后才能得到1组近似Pareto最优解。
基于粒子群优化算法的多目标优化问题求解摘要多目标优化问题是现代科学技术中经常遇到的问题之一。
传统的优化算法难以有效地解决这类问题，因此需要一种高效的优化算法来解决这种问题。
粒子群优化算法(Particle Swarm Optimization, PSO)作为一种新兴的优化算法，在多目标优化问题中表现出了良好的效果，本文将介绍基于粒子群优化算法的多目标优化问题求解的思路和方法。
1. 引言随着现代科学技术的不断发展，各行各业都涉及到了多目标优化问题。
例如，自动化工厂调度、工厂布局优化、电力系统调度等领域都需要解决多目标优化问题，传统的优化算法在解决这类问题上显得无能为力。
因此，研究高效的解决多目标优化问题的算法已成为当前的研究热点。
2. 多目标优化问题的定义与分类多目标优化问题(Multi-objective Optimization Problem, MOP)是指存在多个相互矛盾的目标函数需要最小化或最大化的优化问题。
多目标优化问题具有多样性、复杂性和不确定性等特点，它的解决涉及到数学、统计、计算机等多个领域。
根据问题的特征，多目标优化问题可分为以下几类：(1)在选择解时采用 Pareto 最优的非支配解集（Pareto Optimal Non-Dominated Solution Set, PONDS）作为解的选择标准，通常称为 Pareto 优化问题。
Pareto优化问题的主要研究方向是改进搜索算法和维护非支配解集。
(2)基于权衡的多目标优化问题。
在权衡的多目标优化问题中，目标函数的权值在不同的情况下有所不同，因此需要对不同权值下的优化结果进行比较，然后选择最优的结果。
该问题通常用加权平均法或效用函数法等方法来求解。
(3)约束多目标优化问题。
约束多目标优化问题是指在多目标优化问题的基础上，加入了约束条件。
该问题中要求解最优解，同时需要满足一定的约束条件。
3. 粒子群优化算法的概述粒子群优化算法(PSO)是一种优化算法，它是由Kennedy和Eberhart在1995年提出的。
基于粒子群优化算法的多目标优化技术研究随着科技的飞速发展和数学理论的不断完善，多目标优化技术得以广泛应用。
多目标优化技术是指在多个约束和目标函数下进行优化，而这些目标可能存在着相互冲突或依存的关系。
如何找到最合适的解决方案？基于粒子群优化算法的多目标优化技术引起了研究者的极大兴趣。
一、粒子群优化算法的基本原理粒子群优化算法是由美国社会模拟研究中心的Eberhart和Kennedy于1995年提出的，它是一种进化算法，是模拟自然界中群体行为规律的一种数学模型。
把目标函数映射到一个高维空间中，粒子在这个空间中自由移动，不断寻找最优解。
粒子群的运动包括两种情况：①粒子本身在探寻最佳的位置，也就是局部寻优；②群体之间的信息共享，也就是全局寻优。
基本的粒子群优化算法采用了简单的三个步骤：初始化粒子位置和速度、根据粒子最优位置和群体最优位置更新粒子位置和速度、结束条件满足时输出最终最优解。
在算法运行的过程中，每一个粒子的位置代表一个状态解，每一个维度代表的是状态解中的一个决策变量值。
二、粒子群优化算法在多目标优化中的应用针对多目标优化问题，有许多粒子群优化算法的衍生模型，如Nondominated Sorting Particle Swarm Optimizer(NSPSO)、Pareto Particle Swarm Optimization(P-PSO)等。
相比遗传算法等多目标优化算法，粒子群优化算法具有以下特点：①算法执行效率高、搜索过程较快；②对搜索空间的搜索能力较强；③可对约束条件进行有效处理，有很强的鲁棒性；④不会出现“早熟”和“过度”现象。
因此，基于粒子群优化算法的多目标优化技术在工程、经济、管理等领域中得到了广泛的应用。
以下是一些实际应用场景。
2.1 多机械臂任务协同规划在多机械臂任务协同规划中，每个机械臂都有自己的控制参数，因此会涉及到多目标优化的问题。
基于NSPSO的多目标协同规划算法可以寻找到最优的协同决策方案，从而提高协同规划的效率和精度。
一种改进的粒子群优化算法袁琳;苑薇薇【摘要】When the PSO algorithm optimization is used in complex problems,it is likely to be trapped at local minima phenomenon, the exploration and exploitation ability of the algorithm were regulated through introducing two criteria in the evolutionary process, the population-fitness-variance and the population-position-variance to preserve population diversity , which can effectively overcome the problem of premature convergence encountered by PSO. In the middle-end of the algorithm, based on the different expression of the particle, the inertia weight adapted by itself , so it can keep the inertia weight diversity. Finally, in this paper, to test four basic math function can improve the optimization capability of it.%针对基本粒子群算法在处理复杂问题时有可能陷入局部极小的现象,引入群体适应度方差及群体位置方差,协调算法的种群多样性,使之能有效地克服基本粒子群算法容易陷入局部收敛的问题.在算法的中后期,根据粒子的表现不同,自适应调整惯性权重,保持群体惯性权重的多样性.通过选取4个基准函数进行测试,验证了改进算法可提高粒子群算法的优化性能.【期刊名称】《沈阳理工大学学报》【年(卷),期】2012(031)003【总页数】4页(P15-18)【关键词】粒子群算法;种群多样性;惯性权重多样性;基准函数测试【作者】袁琳;苑薇薇【作者单位】沈阳理工大学信息科学与工程学院,辽宁沈阳110159;沈阳理工大学信息科学与工程学院,辽宁沈阳110159【正文语种】中文【中图分类】TP18粒子群优化算法是一种基于种群搜索的群智能进化计算技术［1－2］，在标准PSO(Particle Swarm Optimization，粒子群优化)算法中，惯性权重是非常重要的参数。
基于改进型多目标粒子群算法的晶圆制造系统瓶颈工作站调度周炳海;胡新宇;孙超【摘要】为了尽可能提高瓶颈工作站利用率,在获得较高系统产能的同时得到一个合理的制造周期,构建了以最小化瓶颈工作站的平均加权提前/拖期时间和最小化瓶颈工作站流程时间为优化目标的改进型多目标粒子群算法,并对瓶颈工作站进行了性能分析.将准时交货和快速生产要求分别映射为瓶颈工作站平均加权提前/拖期时间和流程时间,并构建了多目标优化模型.通过改进速度和位置的更新机制,对陷入局部最优的粒子进行交叉操作,设计了用于瓶颈工作站调度的改进型多目标粒子群算法.在不同作业规模下从算法的稳定性、Pareto前沿质量、收敛速度及运行时间出发,进行了调度仿真试验.结果表明该算法对提高瓶颈工作站的调度性能是有效的、可行的.【期刊名称】《江苏大学学报（自然科学版）》【年(卷),期】2014(035)001【总页数】6页(P63-68)【关键词】半导体晶圆制造系统;瓶颈;工作站;调度;改进型多目标粒子群算法【作者】周炳海;胡新宇;孙超【作者单位】同济大学机械与能源工程学院,上海201804;同济大学机械与能源工程学院,上海201804;同济大学机械与能源工程学院,上海201804【正文语种】中文【中图分类】C934如何解决延时生产与顾客准时交货之间的矛盾，不断提高产能，降低制造周期，是目前半导体制造企业面临的主要问题.半导体制造系统中，瓶颈制约着整个系统的产出，必须最大限度地利用瓶颈资源［1］.因此，如何调度瓶颈工序，使瓶颈工作站避免出现空闲现象，保证系统产出率，对提高半导体晶圆制造系统的效率具有重要意义.瓶颈调度属于NP难问题，目前对于该调度研究，国内外的研究方法大致可以归为:通过投料策略调控瓶颈区、基于启发式规则、基于 DBR(drum，buffer and rope)理论、基于智能算法［2］.随着晶圆重入流增加，整个制造过程复杂度增加，投料策略对瓶颈工作站的调控能力大幅降低［3］.启发式规则以其简单、快速的优势得以在半导体晶圆制造系统中被广泛应用，但由于其无法进行优化，解的质量不高.例如，Wang Zuntong等［4］采用启发式派工规则赋予瓶颈前待加工工件优先级，进行瓶颈工作站调度.基于DBR理论的晶圆制造系统调度方法通常是结合晶圆制造系统多重入特点与DBR思想，基于“层”对瓶颈区进行调控，此方法主要关注瓶颈的利用率，而没有考虑瓶颈工作站的优化调度问题.例如，Cao Zhengcai等［5］通过保证一定的“层”装载量以避免瓶颈工作站空闲，进而结合缓冲大小与“层”装载量进行瓶颈工作站调度.一些学者也尝试用智能算法来调度晶圆制造系统瓶颈工作站.Yang Fengcheng等［6］研究了基于时间窗和遗传算法的晶圆制造系统瓶颈工序光刻区的多目标调度问题，但该方法是通过赋予4个目标一定的权重，将其转化成单一目标，简化了调度问题.为了能有效解决半导体生产系统瓶颈工作站多目标调度问题，文中将引入多目标粒子群优化(multi-objective particle swarm optimization，MOPSO)算法，通过改进速度和位置的更新机制，对陷入局部最优的粒子进行交叉操作，设计用于瓶颈工作站调度的改进型多目标粒子群算法.1 问题描述半导体晶圆制造系统规模庞大，具有多重入性，一个晶圆为了完成所有的电路层，必须多次访问光刻工作站.光刻工作站在晶圆制造系统中利用率最高，为瓶颈工作站.为有效地描述基于改进型多目标粒子群算法的半导体晶圆制造系统瓶颈工作站调度，做如下定义和假设:① 晶圆在每个电路层的最后一道工序是光刻，访问瓶颈工作站多少次，就意味着晶圆完成加工需经历多个电路层;② 晶圆按批(lot)进行加工;③ 生产多种晶圆，每种晶圆有固定加工路径，每条路径上串联着多个工作站，每个工作站中有若干台平行机;④同一工作站中的平行机的平均有效处理时间相同，且已知;⑤ 晶圆完成所有工序的总加工时间已知，晶圆的交货期已知;⑥ 假设晶圆到达系统服从泊松分布;⑦系统输入的晶圆数量无限，同时成批到达，即系统输入缓冲区无限;⑧非瓶颈工作站按先进先出原则(first in first out，FIFO)进行加工.2 调度建模为解决顾客准时交货与企业自身延时生产之间的矛盾，将准时交货要求映射为瓶颈工作站平均加权提前/拖期时间，将快速生产要求映射为瓶颈工作站流程时间，从而确定了优化目标为最小化瓶颈工作站平均加权提前/拖期时间和最小化瓶颈工作站流程时间.于是，得到如下数学规划模型:式中:i为晶圆种类;w为工作站编号;k为设备编号;hij为第i种晶圆第j次访问瓶颈工作站;Qi为第i种晶圆的权重;I为晶圆总数;Tdhij为第i种晶圆在第j个电路层上瓶颈工序交货期提前/拖期时间;Chij为第i种晶圆在第j个电路层上瓶颈工序完工时间;ti为第i种晶圆到达系统的时刻;Eijwk为第i种晶圆在第j个电路层上工作站w中设备k上的完工时刻;Sijwk为第i种晶圆在第j个电路层上工作站w中设备k 上的开始加工时刻;tew为工作站w中机器的有效处理时间;Xijwk为1表示第i种晶圆在第j电路层上工作站w中设备k上加工，为0表示其他情况;Rijfgwk为1表示第i种晶圆在第j电路层和第f种晶圆的第g个电路层均需经过工作站w中设备k，且前者的加工优先后者，为0表示其他情况.式(1)-(2)为目标函数;式(3)表示对于某一晶圆，其下一工序必须在上一工序全部完工后才能开始;式(4)表示工作站w中设备k不能同时加工2种晶圆;式(5)表示晶圆在工作站w中设备k上的完工时刻与其开始时刻之差不能小于其所需加工时间;式(6)表示晶圆在工作站w上的加工由该工作站中的唯一一台设备独立完成.3 算法构建为求解上述多目标优化问题，设计了一种改进型多目标粒子群算法.算法的核心思想如下:① 运用排列组合编码方式表达粒子;②由于基本粒子群(particle swarm optimization，PSO)算法的位置及速度更新公式难以表述离散域问题，采用交换子及交换序概念，设计位置及速度的更新机制;③引入约束支配概念［7］，进行约束处理;④ 基于 Pareto支配关系，采用排除法构造非支配集，用于存放非支配粒子;⑤采用文献［8］中ε支配关系构造并更新外部集，用于存放全局极值;⑥ 文献［9］指出，粒子群算法在局部最优值附近收敛缓慢，容易陷入局部最优.为减少粒子早熟现象的发生，加强粒子多样性，提高IMOPSO的全局搜索能力，对陷入局部最优的粒子设计交叉操作，克服早熟收敛问题［8，10］.图1描述了IMOPSO算法的组件及每个组件的操作及组件之间的相互关系.图1 改进型多目标粒子群算法示意图改进型多目标粒子群算法的具体步骤归纳如下.1)初始化粒子群，种群大小为P.①在可行域内随机初始化粒子群中粒子的位置向量Ya，初始化交换序，即粒子的速度向量Va.其中，Ya的编码采用排列组合方式.即若瓶颈工作站前有n个待加工晶圆，则Ya为{1，2，…，n}的一个排列.Va初始化为一个交换子，即在(1，2，…，n)中随机生成2个不同的元素，构成一个交换子.② 设置惯性权重ωd及学习因子α，β.ωd采用如下惯性因子:式中:ωmax，ωmin分别为惯性权重最大值及最小值;Itermax，Itercur分别为最大迭代次数及当前迭代次数.③粒子a的个体极值Pbesta和全局极值Gbesta均初始化为粒子本身.2)求各粒子的适应度函数值f1(a)，f2(a).3)更新非支配集.非支配集的更新采用基于Pareto支配关系的排除法.具体思想如下:将粒子群体中的每个个体a依次与非支配集(初始化为空集)中的个体e比较.如果aPareto支配e，将e从非支配集中剔除.如果a不被非支配集中任意一个个体支配，则将a并入非支配集.当非支配集为空集时，直接将a并入其中.4)更新个体极值.基于竞争选取原则进行个体极值的更新.具体思想如下:若当前粒子a支配Pbesta，用a更新Pbesta;若Pbesta支配a，则个体极值不变;若两者互不支配时，以50%的概率进行替换.5)更新外部集.采用外部集保存当前找到的非支配解集，将ε支配概念用于更新外部集，以使算法保持较好的分布性.其中，外部集即为粒子全局极值的候选集，而外部集保留的最终解即为算法求解的结果.具体思想如下:若某个非支配粒子不被外部集中任一粒子ε支配，则将其并入外部集;若外部集中某一粒子被新并入的非支配粒子ε支配，则将该粒子剔除.6)更新全局极值.利用外部集是粒子全局极值的候选集合这一概念，进行全局极值的更新.具体思想如下:对于粒子a，从外部集中随机选取一粒子，若该候选粒子支配a的全局极值Gbesta，则将该候选粒子作为a的新全局极值;若Gbesta支配该候选粒子，则全局极值不变;若两者互不支配，则以50%的概率进行替换.7)计算粒子的停滞代数Sa，若Sa大于或等于该粒子的健康度阈值Ha，表明该粒子出现早熟现象，转到步骤8)，进行交叉操作;否则，转到步骤9).8)交叉操作.将出现早熟现象，即陷入局部最优的粒子a与外部集中随机选取的较优粒子e进行交叉操作，交叉后a的停滞代数更新为0.交叉方法具体思路如下:对于粒子a和e的位置向量Ya，Ye，在其位置元素总数n中产生一个随机数q，保留Ya中的前q个元素，将Ye中后n-q个元素插入Ya中相应的n-q个位置，而Ya中其余元素则顺序后延，则生成一个新的位置;然后保持新插入元素不变，剔除中其余位置重复出现的元素，则得到粒子a的更新后的位置.具体实现步骤如图2所示(假设n=9).图2 交叉操作9)分别按式(8)，(9)更新粒子的速度及位置，转至步骤2)直至满足中止条件(迭代次数达到最大迭代次数)退出.式中:γ1，γ2为［0，1］上的随机数.上述表示式中，“⊕”表示参与运算的交换子之间的作用顺序.则粒子速度即为多组交换子的“⊕”运算;“［+］”表示为两个速度各自的交换子按序作“⊕”运算;“—”表示了由位置Ya变换到位置Ye所需的一组交换子.“+”表示是将速度中各项交换子按序作用于位置.常数r(r∈［0，1］)与速度Va“⊗”运算关系如下:先计算r×‖Va‖(其中，‖Va‖表示速度Va中交换子的个数)，且对该结果向下取整，记为‖‖;由前‖‖个交换子构成新的速度 ;如果‖ ＞1，则 r⊗Va=，否则，在 Ya中随机选择两个元素，构成一个交换子，从而生成速度，则4 试验分析为有效评价文中设计的改进型多目标粒子群算法，进行如下仿真试验设计:①以经典的Mini-Fab模型为原型，根据本算法假设条件，对Mini-Fab进行适当改变，形成如下仿真模型:晶圆制造系统有5个工作站，各工作站中有2-3台机器，其中光刻工作站有2台机器;晶圆种类为3种，各晶圆经历的电路层层数均为2层;晶圆以lot进行加工，不考虑batch处理.②晶圆到达系统服从参数λ=5的泊松分布;非瓶颈工作站调度采用FIFO规则.③ 运用IMOPSO算法对瓶颈工作站调度时，参数设置如下:种群规模P=30，最大迭代次数Itermax=50，粒子健康度阈值 Ha=5，惯性权重ωmax=1.0，ωmin=0.6，学习因子α =0.8，β =0.8.④ 仿真试验硬件为主频 2.13 GHz、内存4 GB的PC机，采用C++编程语言进行仿真程序编程. 4.1 仿真分析t=19.28 s时刻进行瓶颈调度时，瓶颈工作站前有7 个待加工晶圆，将其分别标记为 l1，l2，l3，l4，l5，l6，l7.结合文献［11］对 MOPSO 算法的应用及文献［10］对PSO算法粒子的表达及交叉设计，通过200次运行，与未对出现早熟现象粒子进行交叉操作的MOPSO算法进行比较，分析IMOPSO算法性能.1)分别统计IMOPSO，MOPSO算法中出现率大于等于40%的调度方案，结果如表1，2所示.表1 IMOPSO运行结果统计/%l5，l4，l6，l1，l2，l7，l3各晶圆加工顺序 f1(x) f2(x) 出现率0.713 176.376 85 l4，l5，l2，l6，l3，l7，l1 0.687 180.856 78 l4，l1，l2，l5，l6，l3，l7 0.598 188.304 66 l5，l3，l1，l7，l4，l6，l2 0.583 191.894 61 l4，l1，l3，l5，l7，l2，l6 0.579 193.685 57 l5，l4，l2，l1，l3，l7，l6 0.723 171.739 54 l3，l5，l2，l4，l7，l6，l10.736 168.832 49表2 MOPSO运行结果统计/%l6，l5，l4，l2，l3，l1，l7各晶圆加工顺序 f1(x)f2(x) 出现率0.725 178.639 74 l6，l2，l5，l4，l1，l7，l3 0.716 182.213 68 l3，l5，l4，l6，l7，l2，l1 0.631 191.457 53 l3，l6，l4，l5，l2，l7，l1 0.618 195.812 48 l2，l5，l4，l3，l6，l1，l7 0.749 173.208 45 l2，l5，l1，l4，l6，l7，l30.755 169.436 42统计IMOPSO算法运行结果，根据表1所罗列的调度方案的两个目标值与该算法趋近稳定后两个目标值均值的偏差，可以得到如表3所示的结果.由表3可以看出，上述IMOPSO算法中出现次数较多的调度方案的两个目标值与该算法趋近稳定后目标值均值的偏差较小，这说明该算法所输出的结果相对较优，Pareto前沿的质量相对较高，能获得准时交货与快速生产两者的较优配合.表3 IMOPSO目标值分析 %与均值偏差l5，l4，l6，l1，l2，l7，l3各晶圆加工顺序 f1(x)与均值偏差 f2(x)10.5 6.3 l4，l5，l2，l6，l3，l7，l1 6.5 8.9 l4，l1，l2，l5，l6，l3，l7 -7.3 13.4 l5，l3，l1，l7，l4，l6，l2 -9.6 15.6 l4，l1，l3，l5，l7，l2，l6 -10.2 16.7 l5，l4，l2，l1，l3，l7，l6 12.1 3.5 l3，l5，l2，l4，l7，l6，l114.1 1.7由表1可以看出，上述IMOPSO算法所输出的结果相对较稳定.准时交货与快速生产两者达到较优组合的晶圆排序(l5，l4，l6，l1，l2，l7，l3)与(l4，l5，l2，l6，l3，l7，l1)在200次运行中出现率分别为85%和78%，这表明运用该算法进行瓶颈调度时可以较好地解决准时交货与延时生产要求间的矛盾.由表1及表2可以看出，IMOPSO比MOPSO有更好的性能，拥有更优的Pareto最优解集，在进行瓶颈调度时更稳定.2)IMOPSO，MOPSO算法外部集中两个目标函数的演化曲线如图3所示.其中曲线代表每代外部集解群体的平均目标值.图3 目标函数f1和f2的Pareto最优演化过程由图3可以看出，随着算法的不断演化，曲线不断下降，外部集解群体的目标平均值越来越趋于Pareto最优和稳定，相比之下，IMOPSO算法的收敛速度更快.3)分别统计IMOPSO，MOPSO算法下200次运行的时间，记录最好结果、最差结果及平均结果，见表4.表4 IMOPSO，MOPSO算法运行时间统计算法运行时间/s最好结果最差结果平均结果IMOPSO 17.326 23.574 18.569 MOPSO 8.783 12.832 10.513由表4可知，IMOPSO算法在运行时间上稍逊于MOPSO算法，但其仍能在连续200次计算中较快速地搜索到相对稳定的Pareto最优解群体，完成对瓶颈区调度结果的输出.4.2 系统性能分析为了进一步验证文中提出的改进型粒子群算法能有效调度瓶颈工作站，在解决准时交货与延时生产间矛盾的同时，能进一步降低制造周期，获得相对较高的系统产能及合理的在制品水平，文中选用瓶颈区FIFO调度规则与本算法进行系统绩效分析，其中运用本算法进行瓶颈调度时，采取从外部集中随机选取某一调度方案的规则，用以确定瓶颈工作站晶圆的加工顺序.系统绩效指标为产能(throughput，TH)及在制品(work in process，WIP)，分别以 QTH及 QWIP表示.根据Little定理，QTH一定时，QWIP增加，制造周期(cycle time，CT)会相应增加.因此，系统最佳目标亦是取得较高QTH和较低QWIP，从而得到二者最佳配合.整个仿真试验时间是6个月，数据选取自后4个月.试验结果如表5所示，表中分别记录了两个算法的系统产能QTH与QWIP的最佳值、最差值及平均值.其中，每个数据都是经过10次仿真试验得到的.表5 QTH，QWIP的比较结果算法QTH/(lots·h-1)QWIP/lots最佳值最差值平均值最佳值最差值平均值IMOPSO 0.658 0.613 0.633 55 64 59.3 FIFO 0.573 0.551 0.562 53 58 55.8根据10次仿真得到的系统绩效指标值QTH和QWIP，分别绘制两个算法下QTH，QWIP关于仿真次数的趋势图，见图4.图4 QTH和 QWIP趋势由表5及图4可见，运用IMOPSO算法进行瓶颈工作站调度比用FIFO调度能获得相对更高的系统产能.虽然前者的系统QWIP值基本都比后者高，但是前者相对后者的QWIP值增幅却远小于其QTH的增幅，因此采用文中提出的改进型多目标粒子群算法对瓶颈工作站进行调度时，不仅可以得到较高的系统产能，而且可以得到相对合理的在制品，即相对合理的制造周期，这说明本算法是有效的.5 结论1)通过改进速度和位置的更新机制，设计交叉操作用于克服粒子的早熟现象，构建了改进型多目标粒子群算法，用于瓶颈工作站调度.2)试验分析表明，文中提出的改进型多目标粒子群算法所输出的Pareto前沿的质量相对较高，算法稳定性较好.随着算法的不断演化，外部集解群体的目标平均值越来越趋于Pareto最优和稳定，收敛速度较快.算法运行时间较短，能较快速地搜索到相对稳定的Pareto最优解群体.在较好解决企业延时生产要求与客户准时交货要求间矛盾的同时，可以取得较高的系统产能及相对合理的在制品水平，达到二者的较佳配合.3)调度模型和算法可为半导体晶圆制造系统瓶颈工作站调度研究提供借鉴和指导作用.参考文献(References)【相关文献】［1］Tsou C M.On the strategy of supply chain collaboration based on dynamic inventory target level management:a theory of constraint perspective［J］.Applied Mathematical Modeling，2013，37(7):5204-5214.［2］Tang Chunhui，Qian Yuliang，Zhu Jun，et al.A scheduling method in semiconductor manufacturing lines based on genetic algorithm and simulated annealing algorithm［C］∥Proceeding of the 2010 International Conference on Information，Networking and Automation.Kunming:IEEE Computer Society，2010，doi:10.1109/ICINA.2010.5636524.［3］Bahaji N，Kuhl M E.A simulation study of new multiobjective composite dispatching rules，CONWIP，and push lot release in semiconductor fabrication［J］.InternationalJournal of Production Research，2008，46(14):3801-3824.［4］Wang Zuntong，Wu Qidi，Qiao Fei.A lot dispatching strategy integrating WIP management and wafer start control［J］.IEEE Transactions on Automation Science and Engineering，2007，4(4):579-583.［5］Cao Zhengcai，Peng Yazhen，Wang Yongji.A drumbuffer-rope based scheduling method for semiconductor manufacturing system［C］∥Proceedings of the 2011 IEEE International Conference on Automation Science and Engineering.Trieste，Italy:IEEE Computer Society，2011:120-125.［6］Yang Fengcheng，Kuo Chunnan.A time window rolling and GA-based method for the dynamic dispatching problem in photolithography area［C］∥Proceeding of the 2010 40th International Conference on Computers and Industrial Engineering.Awaji，Japan:IEEE Computer Society，2010，doi:10.1109/ICCIE.2010.5668209.［7］Vergidis K，Saxena D，Tiwari A.An evolutionary multiobjective framework for business process optimisation［J］.Applied Soft Computing Journal，2012，12(8):2638-2653.［8］Chen Yu，Zou Xiufen，Xie Weicheng.Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front［J］.Information Sciences，2011，181(16):3336-3355.［9］张鼎逆，刘毅.基于混合粒子群法的RLV上升段轨迹优化［J］.江苏大学学报:自然科学版，2013，34(1):54-59.Zhang Dingni，Liu Yi.RLV ascent trajectory optimization based on hybrid PSO method［J］.Journal of Jiangsu University:Natural Science Edition，2013，34(1):54-59.(in Chinese)［10］杨虎林，闭应洲，王仁民，等.基于改进粒子群优化算法求解带时间窗的车辆路径问题研究［J］.广西师范学院学报:自然科学版，2011，28(4):98-102.Yang Hulin，Bi Yingzhou，Wang Renmin，et al.An improved particle swarm optimization algorithm for vehicle routing problem with time window［J］.Journal of Guangxi Teachers Education University:Natural Science Edition，2011，28(4):98-102.(in Chinese)［11］Zizler E.Evolutionary algorithms for multiobjective optimization:methods and applications［D］.Zurich:Swiss Federal Institute of Technology，1999.。
