Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 基于改进ＰＳＯ算法的任务分配研究 曾文权，余爱民 ＺＥＮＧ Ｗｅｎｑｕａｎ．ＹＵ Ａｉｍｉｎ 广东科学技术职业学院计算机工程学院，广东珠海５ １ ９０９０ Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｄｏｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｕｈａｉ，Ｇｕａｎｇｄｏｎｇ ５ １ ９０９０，Ｃｈｉｎａ ＺＥＮＧ Ｗｅｎｑｕａｎ，ＹＵ Ａｉｍｉｎ．Ｒｅｓｅａｒｃｈ ｏｎ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐ— ｐｌｉｃａｔｉｏｎｓ，２０１３，４９（１３）：５１—５５． Ａｂｓｔｒａｃｔ：Ｔｏ ｓｏｌｖｅ ｔｈｅ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｉｎ ｖｉｒｔｕａｌ ｅｎｔｅｒｐｒｉｓｅ．ａ ｍｕｌｔｉ．ｏｂｊｅｃｔ ｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｏｄｅｌ ｏｎ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｉｓ ｃｏｎｓｔｒｕｃｔｅｄ．Ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ａｌｇｏｒｉｔｈｍ ｉｓ ａｎａｌｙｚｅｄ．Ｉｔ ｉｓ ｉｍｐｒｏｖｅｄ ｂｙ ａｕｔｏｍａｔｉｃａｌｌｙ ａｄｊｕｓｔｉｎｇ ｔｈｅ ｗｅｉｇｈｔ ｏｆ ｓｐｅｅｄ ｉｎｅｒｔｉａ ａｎｄ ａｃｃｅｌｅｒａｔｉｏｎ ｃｏｅｆｉｃｉｅｎｔ，ａｎｄ ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ｍｕｔａｔｉｆｏｎ ｏｐｅｒａｔｉｏｎ ｉｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．Ｉｎ ｐｒｏ— ｃｅｓｓ ｏｆ ｓｏｌｖｉｎｇ ｔｈｅ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ｍｏｄｅｌ ｂｙ ｔｈｅ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｍａｐｐｉｎｇ ｂｅｔｗｅｅｎ ｐｒｏｂｌｅｍｓ ａｎｄ ｐａｒｔｉｃｌｅｓ ａｎｄ ｔｈｅ ｃｏｍｐｕｔｉｎｇ ｍｅｔｈｏｄ ｏｆ ｐａｒｔｉｃｌｅ ｐｏｓｉｔｉｏｎ ｆｉｔｎｅｓｓ ｖａｌｕｅ ｂｙ Ｔｅｃｈｎｉｑｕｅ ｆｏｒ Ｏｒｄｅｒ Ｐｒｅｆｅｒｅｎｃｅ ｂｙ Ｓｉｍｉｌａｒｉｔｙ ｔｏ Ｉｄｅａｌ Ｓｏｌｕｔｉｏｎ（Ｔ０ＰＳＩＳ） ａｒｅ ｒｅｓｅａｒｃｈｅｄ．Ｔｈｅｎ，ａ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｉｓ ｄｅｓｉｇｎｅｄ．Ｆｉｎａｌｌｙ，ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ａｎｄ ｖａｌｉｄｉｔｙ ｏｆ ｔｈｅ ｍｅｔｈｏｄ ｉｓ ｖｅｒｉｆｉｅｄ ｂｙ ａｎ ａｐｐｌｉｃａｔｉｏｎ ｅｘａｍｐｌｅ ａｎｄ ａ ｓｉｍｕｌａｔｉｏｎ ｔｅｓｔ． Ｋｅｙ ｗｏｒｄｓ：ｖｉｒｔｕａｌ ｅｎｔｅｒｐｒｉｓｅ；Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）：ｔａｓｋ ａｌｌｏｃａｔｉｏｎ；Ｔｅｃｈｎｉｑｕｅ ｏｒｆ Ｏｒｄｅｒ Ｐｒｅｆｅｒｅｎｃｅ ｂｙ Ｓｉｍｉｌａｒｉｔｙ ｔｏ Ｉｄｅａ１ Ｓｏｌｕｔｉｏｎ（ＴＯＰＳＩＳ） 摘要：为了解决虚拟企业中的任务分配问题，建立了任务分配的多目标决策优化模型。分析了传统的ＰＳＯ算法，通过设 置算法中速度惯性权重和加速度系数的自动调整，以及引入遗传算法中的变异操作，实现了对该算法的改进。基于改进 的ＰＳＯ算法求解任务分配模型，研究了求解问题与粒子的映射以及采用ＴＯＰＳＩＳ计算粒子位置适应度的方法，进而设计了 一种基于改进ＰＳＯ算法的任务分配算法。通过应用实例及仿真实验，证明了改进的ＰＳＯ算法应用于任务分配的可行性和 有效性。 关键词：虚拟企业；粒子群优化算法；任务分配；逼近理想解排序 文献标志码：Ａ 中图分类号：ＴＰ３９１ ｄｏｉ：１０ ３７７８￣．ｉｓｓｎ．１００２—８３３１．１２１１．００３２ １ 引言 虚拟企业是一种企业经营模式，在获得客户订单后， 搜索精度与迭代效率不高等缺陷 。因此，实际应用中， 对基于ＰＳＯ求解任务分配与调度问题大多需要进行改 进。改进的方法包括：引入声搜索策略以克服陷入局部最 优ｎ ；采用自适应惯性权重提高算法的收敛速度川；在算法 中引入遗传算法中的克隆和变异算子… ；模拟生物免疫系 统的特征和机制改进ＰＳＯ算法 基于网格的特性与ＰＳＯ的 盟主企业首先将订单任务分解和分类为若干个子任务，然 后采用招投标或协商等方式为每个子任务选择合适的供 应商，该过程即虚拟企业中的任务分配或任务调度。 针对虚拟企业中的任务分配或调度问题，已有研究大 多基于多Ａｇｅｎｔ的协商与协作能力，首先建立起任务分配 或调度的数学模型，然后采用各种数学方法或智能优化算 法进行模型的求解 。 ；或者基于多Ａｇｅｎｔ技术设计和开发 任务的分配或调度系统 。任务的分配与调度是一个ＮＰ 难题 ，ＰＳＯ算法由于其具有收敛速度快以及鲁棒性好等 优点而得到了广泛应用，如针对多无人作战飞机的协同控 制 、雷达干扰ｕ 、多机器人系统ｕ”、网格系统 等领域的 任务分配与调度。然而，ＰＳＯ算法存在着易早熟收敛、后期 混合粒子群的算法 等。由于虚拟企业中订单任务的分配 是一个多目标优化问题，盟主企业期望以最少的费用、最 短的交货期、最高的供应质量和最小的风险等完成订单任 务。因此，本文首先建立起订单任务分配的多目标优化决 策模型，然后在分析传统ＰＳＯ算法的基础上对其进行改 进，并基于该方法求解任务的分配问题，最后通过实际应 用实例和仿真实验来验证该方法的可行性和有效性。 基金项目：广东省自然科学基金（Ｎｏ．￥２０１ １０１０００２５３７）；广东省科技计划项目（Ｎｏ．２０１２Ａ０３０４０００２９）。 作者简介：曾文权（１９７８一），男，副教授，主要研究方向：计算机应用技术，图像处理和分析；余爱民（１９６３一），男，博士，教授，主要研究方 向：计算机应用技术，图像处理和分析。Ｅ—ｍａｉｌ：ｂｌｅｓｓ３６５＠１２６．ｃｏｍ 收稿日期：２０１２．１１．０５ 修回日期：２０１２—１２—３１ 文章编号：１００２—８３３１（２０１３）１３－００５１—０５ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ２任务分配的多目标决策模型 搜索，并记录下搜索过程中单个粒子所经历的最好位置 ２．１模型假设 记ｎ个待分配任务记为 ＝ ｔ ，…， －．，ｔ ｝，则模型 假设和参数描述为： （１）任务ｔ 之间相互独立，任务ｔ 的候选供应商集合记 为Ｐ ：｛ｐｆ１，Ｐｆ２，…，Ｐ ，…，ｐｆ ｝； （２）若任务ｔ，分配给了供应商ｐ ，则状态变量Ｕ ＝ｌ， 否则“ ＝０； （３）供应商Ｐ 申请任务ｔ 的信息中包括完成任务的费 用Ｃ 、交货期限ｔ『『、质量等级ｇ （４）盟主企业对供应商Ｐ 的综合信任度为ｒ （５）盟主企业期望以最少的费用（ｃ）、最短的交货期限 （Ｔ）、最高的质量等级（Ｑ）和最小的风险（尺）完成订单任务。 ２．２建立模型 任务分配的目标即为每个 （ｆ＝１，２，…，ｎ）从尸 中选 择一个供应商Ｐｆ，（ｉ＝１，２，…，ｎ； ＝１，２，…，ｍ ），以满足盟 主企业的期望。假设盟主企业对供应商的信任度记为 豫，则其任务分配的目标函数为： ｏｂｊ（ｚ）＝｛ｍｉｎＣ，ｒａｉｎＴ，ｍａｘＱ，ｍａｘＴＲ｝＝ ｛ｍｉｎ（∑∑ｃｉ＝１ ＝１ “ ），ｍｉｎ（∑∑ｆｉ＝１』＝１ “ ）， Ｉ ｎ ｍａｘ（￣Ｅｑ “ ），ｍａｘ（ｙ＇￣ｔｒ “ ）｝ 然而，上述目标在实际中是不可能实现的，针对该目 标只能求得一组优化解。在对 ｔ ｇ ，以及护 按 Ｍｉｎ．Ｍａｘ方法归一化处理后，建立任务分配目标的决策优 化模型为： ｎ ＾ Ｏｐｔ（Ｚ）＝Ｏｐｔ｛ｍｉｎ［（￣＇ｉ＝１』＝１∑ｃ “ ），（∑∑ｆｌ：１』＝１ “ ）， ｌ ｎ ｌ∑∑（１ Ｊ＝１ １＿ｇ Ｕ∑∑（ｆ＝１ Ｊ＝１ １－ｔｒ＇ｒ） Ｕ ］｝ （１） 其中，ｃ 、ｔ 、ｇ 、ｒ 分别是ｃ 、０、 和ｒ 归一化的结果。 ３ ＰＳＯ算法与改进 建立的任务分配决策模型是一个组合优化问题，其求 解即从丌？，ｍ 个候选解中选出最优的一个。实际中，当 任务数ｎ或申请任务的候选供应商ｍ 足够大，若采用穷举 法则工作量巨大而不可行。由于ＰＳＯ算法解决多维空间 和动态目标寻求优化解时具有较怏的收敛速度，以及鲁棒 性好的优点，它是求解模型（１）较好的选择。但传统的ＰＳＯ 算法存在着易早熟收敛，易陷入局部优化解，以及算法后 期的迭代效率低的缺陷。因此，本文首先分析传统ＰＳＯ算 法，进而提出相应的改进方法。 ３．１ ＰＳＯ算法 ＰＳＯ算法模拟鸟群的觅食行为，其基本思想是：粒子 （一个候选解）从随机的初始位置以随机的初始速度开始 （个体最优解），以及整个粒子群体所经历过的最好位置 （全局最优解），一次搜索结束后各个粒子通过个体最优解 和全局最优解更新自己的飞行速度和位置，并进行下一轮 的搜索，依此直至搜索次数达到设定值，则全局最优解为 搜索问题的优化解。 ＰＳＯ算法描述为：设粒子群有ｍ个个体，求解问题的维 ，最埘 ｒ为 ；粒子 的虚置为 ＝ …，ｚ ）， 飞行速度为 ＝（ｖ ｖ …，ｖ ），位置适应度值为厂（ ），个 体最优解为 ＿（…Ｘｐｂｅｓｔ，ｘ Ｐｂ ‘，…，ｘ２ ）；粒子群的全局 最优解为 咖“＝（ ‘， ‘，…， ‘）；若搜索次数 ＝Ｔ， 则算法结束，否则第七＋１次搜索时首先更新粒子的速度和 位置，更新公式为： ｖ ＝ＣＯＶ ＋Ｃｌｒｌ（ 一 ）＋ｃ２ｒ２（ 一 ） （２） ｘＵｋ ： ＋ ｘ ＋ｖ （３）ｊｊ 其中∞为速度惯性权重；Ｃ 和Ｃ，为加速度系数，分别为将 粒子推向 和ｂ 的权重； 和，：为区间［０，１］上的随 机数。 ３．２ ＰＳＯ算法的改进 实践证明，ＰＳＯ算法具有收敛速度快和通用性强的优 点，但存在着易早熟收敛，搜索精度不高，以及后期迭代效 率不高等缺陷 。因此，本文从ＰＳＯ算法参数的调整，并 引入遗传算法中的变异操作对其进行改进，在保留其优势 的同时克服其不足。 （１）速度惯性权重的调整 速度惯性权重∞取值较大时有利于克服算法陷入局 部最优，而取值较小时有利于算法收敛。因此，在算法的 起初阶段，由于粒子缺乏对搜索空间的认识且没有足够的 参照，ＣＯ应取较大值以扩大粒子群的搜索范围，从而提高 搜全率；而在算法的收敛阶段，ＣＯ应取较小值以尽可能搜 索最优解周边的小范围，从而提高搜准率。因此，设定∞ 的自动调整公式为： （Ｔ一 （ｃｏ ～∞ ）．， ， 一———— ——一 其中∞ 为第ｋ ＝２，３，…， ）次搜索时的惯性权重， 为 最大搜索次数，ｎ） 为惯性权重的初始值。 （２）Ｃ，和Ｃ 的调整 Ｃ 和Ｃ，是分别用于调整个体最优解与全局最优解在 粒子搜索过程中所起作用大小的两个参数。对Ｃ 和Ｃ，的 调整策略为：若粒子当前位置的适应度大于粒子群体适应 度的平均值，则增大Ｃ．且减小Ｃ，，以增加粒子沿自身方向 飞行的速度，而减少向全局极值方向飞行的速度，反之采 用相反策略。 Ｃ 和Ｃ，的自动调整方式描述为：记第ｋ次搜索时粒子 位置的适应度值为．厂（ ），而粒子群体适应度的平均值为 ｆ（Ｘ ），则第｜ｊ｝＋１次搜索时Ｃ 和Ｃ，的调整公式如下： 若ｆ（Ｘｉ ） ｆ（ｘ ），则 曾文权，余爱民：基于改进ＰＳＯ算法的任务分配研究 步骤４计算出各个粒子的位置适应度值，公式为： ｍａｘｆ（Ｘｉ ）一ｆ（Ｘ ） ｋ“ｃ２＝。 “： ＋ （５） ｄ一 厂（ ）＝ ＋ （９） ２一ｃ “ ４．３任务分配模型的求解算法 基于改进的ＰＳＯ算法求解任务分配模型（１）的算法步 ｆ（Ｘ ）一＿厂（ ） 否则 Ｃ． ＋。 ＝一骤为： （６） ｆ（Ｘ ）一 ｆｌ厂（ ） 步骤１设置算法的参数。设粒子群粒子个数为ｍ，最 大搜索次数（迭代次数）为 ，粒子群惯性权重初始值和最 后一次搜索时的值分别为０９ 和０９ ，设定ｃ 和ｃ，的初始 值，以及变异阈值 。 步骤２随机生成粒子群的初始位置 ＝（ ） 和初 Ｉｃ２ｋ ＝２一ｃｋ１¨ （３）引入变异操作 为了避免粒子群陷入局部最优，在算法中引入遗传算 法中的变异操作。若单个粒子的个体最优解 （变异阈值）次没有更新，则采用两点变异策略对 连续 做 始速度 ＝（ｖ ） 。 步骤３计算出粒子群中各个粒子的位置适应度值，进 而得到单个粒子的个体最优解 解 。 变异操作。首先，产生［１，ｎ］内的两个随机数ｎ 和 （１≤ ≠ ６≤，ｚ），然后将 中位置序号分别为，ｚ 和 ６ 和粒子群的全局最优 的两个元素交换位置后作为粒子新的个体最优解。 步骤４采用式（２）和（３）更新粒子群的速度ｖ 和位置 Ｘ 对ｖ 和 的取值按４．１节的方法进行处理。 步骤５若搜索次数后＝Ｔ，转步骤７；否则转步骤６。 步骤６对步骤３中连续 次未变化过的 ‘做变异操 作，然后按（４）、（５）和（６）式更新 权重，ｃ 和ｃ，，并转步骤３。 步骤７输出步骤３中的 解，算法结束。 ，即为模型（１）的最优 ４基于改进ＰＳＯ算法求解任务分配模型 ４．１ 问题与粒子的映射 针对模型（１），待分配的任务数ｎ即粒子搜索空间的维 度，则粒子ｉ的位置为 ＝（ Ｘ …，Ｘ …， ），Ｘ 即为 任务ｔ，分配的候选供应商序号，且Ｘ ，取区间［１，ｍ，】内的整 数，ｍ，为申请任务ｔ 的供应商个数；粒子速度ｖ 的取值范 围设定为［一 ，一１）， ，一１）ｏ ５应用实例及仿真实验 ５．１ 应用实例 某面向全球范围从事机械类零部件产品加工定制的 虚拟企业，盟主企业将４类待分配任务ｔ 、ｔ，、ｔ 和ｔ 向虚 由于 取整数，当采用式（３）更新粒子位置后，若其值 在［１，ｍ，】内，则直接取结果的整数部分。否则，若 ＞ｍｊ， 则 ＝ｍｊ；若 ＜１，则 ＝１。当按式（４）更新粒子的速 度后，若 ＞ 一１，则 ＝ ，一１；若 ＜一（ 一１），则 一拟企业中的供应商成员企业发布后，针对各个任务，收集 到供应商提交的任务申请信息包括费用（万元）、交货期限 （天）、质量等级，如表１所示。 表１ 各供应商对任务的申请信息 ｔ１ ｔ２ ｔ３ ｔ４ （ 厂１）。 ４．２粒子位置适应度值的计算 在计算粒子群中各粒子位置的适应度值时，本文采用 ＴＯＰＳＩＳ［” 方法进行计算。设粒子群的粒子个体数ｍ，则其 计算方法描述为： 步骤１根据各粒子的位置 ，得到粒子群的位置 ＝ （ 订，…， ，…， ）ｍ 。 步骤２根据 读取出对应的费用信息Ｃｆ『、交货期限ｔｆ『、 质量等级ｑ ，和综合信任度ｔｒ ，则Ｍ变形为Ｍ ＝［（ｃ ｔ ｑｆ１’ｔｒｆ１），…，（ ，ｔ ，ｑ ，ｔｒ ），…，（ｃ ，ｔ ｑ ｔｒ ）］ 。 对表１中的信息加上盟主企业对各供应商的信任度值 后，按Ｍｉｎ—Ｍａｘ方法进行归一化处理后的结果，如表２所示。 表２归一化后的任务申请信息 步骤３针对Ｍ 中的（ｃ ，ｔ ，ｇ ，ｔｒ ｆ），首先对各个分量 按列进行归一化处理后，然后计算 中各行与正理想解 和负理想解之间的距离，其计算公式分别为： ｔｌ ｔ２ ｔ３ ｔ４ （０，０，１，Ｏ．６５） （Ｏ．３８，Ｏ．５０，０，０）（Ｏ．４３，１，０，Ｏ．６５）（Ｏ．２５，０，１，１） （０，１，０，０） （Ｏ．６０，０．６７，０．５０，０．７３）（１，Ｏ．８８，０，０．５４）（１，０．６０，０．３３，０．７２） ，＝ｆ２ Ｌ＜ｏ—ｃ ） ＋（ｏ—ｆ ） ＋（１一ｇ ） ＋（１一护 ） ］（７） ，＝１ （０．７５，０．３３，０．５０，１）（０．７５，１，Ｏ．５０，１） （０．５７，０，１，１） （１，０．５０，１０，０．５６） （１，１，０，０） （０，Ｏ．７５，１，０．３８） （０，０，Ｏ．６７，０） （Ｏ．１３，０，０．５０，０．６０） ＝ｆ２ Ｅ（１一ｃ ） ＋（１一ｆ ） ＋（ｏ—ｇ ） ＋（０一 ＇ｏ３ ］（８） ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 按照本文的任务分配求解算法，采用Ｍａｔｌａｂ ７．０提供 的ＰＳＯ算法工具进行求解。求解过程中，设置粒子群粒子 的个数ｍ＝ｌ０，粒子搜索空间的维度ｎ＝４，最大搜索次数 ＝个、５０个、７０个和１００个，各个任务的候选供应商个数假设 都为ｌ０个，供应商提交的任务申请信息以及盟主企业对供 应商的信任度值取［０，１】上随机数的条件下，分别采用本文 的方法和传统ＰＳＯ算法进行求解。求解时：设定粒子群个 ¨ ５０，初始惯性权重和最后一次搜索的惯性权重分别为 ∞ ＝０．９和ＣＯ ＝０．１，Ｃ，和Ｃ 的初始值分别设为２，变异阈值 ＝４，求解结果如表３所示。 表３算法运行结果 对表２中所有的２４０种任务分配组合分别进行适应度 值计算后，其结果与算法的求解结果一致，均表明任务分 配序列（２，３，３，３）为最优解。 ５．２仿真实验 为了验证本文方法有效性，任务数分别设为１０个、２０ 迥 蚓 迭代次数 图１ １０个任务的实验结果 蚓 图３ ５０个任务的实验结果 迭代次数 图５ １００个任务的实验结果 数ｍ＝５０，搜索空间维度为任务的个数，最大迭代次数 Ｔ＝１ ０００；针对本文改进的ＰＳＯ算法，设定∞ ＝０．９， ∞ ＝０．１，ｃ．和Ｃ，的初值均为２， ＝４；ＰＳＯ算法中∞＝０．９， Ｃ ＝２，Ｃ，＝２。针对不同任务数的仿真结果分别如图１～图 ５所示，各任务数与收敛时的搜索次数关系如图６所示。 图１～图５的实验结果表明，本文对ＰＳＯ算法进行改进 后，既提高了传统ＰＳＯ算法的收敛速度，也克服了其易陷 入局部最优解的缺陷。并且从图６可看出，随着求解问题 规模的扩大，算法的收敛次数不是呈指数变化，进一步说 明本文方法有较好的优化特性。 ６结束语 为了提高ＰＳＯ算法的收敛速度，尽量避免算法陷入局 ０．５ｌ５ ｌ Ｏ ９ ８ ７ ６ ５ ４ ３如如如如如如如改进ＰｓＯ算法 ５ｌｏ ／ｆ ， 传统Ｐｓｏ算法 蚓 妻ｏ．５ｏ５ ０．５００ ２００ 迭代次数 图２ ２０个任务的实验结果 趔 蚓 图４ ７０个任务的实验结果 辍 ｌ０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ １０Ｏ 任务数 图６任务个数不同时的搜索次数 曾文权。余爱民：基于改进ＰＳＯ算法的任务分配研究 ２０１３，４９（１３） ５５ 部最优，通过ＰＳＯ算法中可调节参数的自动调整，并引入 群算法求解［Ｊ】＿控制与决策，２０１２，２７（１１）：１７５１－１７５５． 遗传算法中的变异操作，进而设计了基于改进ＰＳＯ算法求 ［８国博，８］王社伟，陶军．基于改进粒子群算法的多无人机任务分 解任务分配多目标优化模型的方法。实验证明该方法既 配研究［Ｊ］．计算机仿真，２００９，２６（７）：６２—６５． 保留了ＰＳＯ算法易实现和收敛速度快的优点，同时克服了 ［９］有伟，王社伟，陶军．基于免疫粒子群算法的多ＵＣＡＶ协同任务 其容易陷入局部最优的缺陷。本文的方法对类似多目标 分配［Ｊ］ｌ计算机工程与应用，２０１０，４６（３２）：２２４ ２２７． 组合优化问题的求解具有一定的参考意义。 ［１０］李俊，郝成民，刘湘伟．改进ＰＳＯ算法在雷达干扰任务分配中 的应用［Ｊ］．计算机仿真，２００８，２５（１２）：２７—２９． ［１１］李济泽．基于粒子群遗传优化算法的多机器人任务分配研究［Ｊ］ ＿参考文献： 机械与电子，２００７（１０）：４５—４８． ［１】高阳，周伟．基于多Ａｇｅｎｔ的虚拟企业调度研究与实现［Ｊ］．中国 ［１２】王成昌，陈闳中，方钰，等．基于混合粒子群算法的网格任务调 机械工程，２００４，１５（１１）：９７８—９８２． 度［Ｊ］ｌ计算机科学，２０１２，３９（２）：ｌ８．２１． ［２］赵强，肖人彬．基于多Ａｇｅｎｔ的虚拟企业任务调度模型［Ｊ］．控制 ［１ ３］Ａｎｇｅｌｉｎｅ Ｐ Ｊ．Ｅｖｏｌｕｔｉｏｎａｒｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｖｅｒｓｕｓ ｐａｒｔｉｃｌｅ ｓｗａＦＩＴＩ 理论与应用，２００９，２６（４）：４５９．４６２． ｏｐｔｉｍｉｚａｔｉｏｎ：ｐｈｉｌｏｓｏｐｈｙ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｄｉｆｆｅｒｅｎｃｅ［Ｃ］／／ ［３程方启，３］王洪飞，叶飞帆．横向虚拟企业订单分配模型研究［Ｊ］＿ Ｐｒｏｃ ｏｆ ｔｈｅ ７ｔｈ Ａｎｎｕａｌ Ｃｏｎｆ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｐｒｏｇｒａｍｍｉｎｇ， 机电工程，２００９，２６（４）：５０—５２． Ｇｅｒｍａｎｙ，１９９８． ［４］Ｋｙｕｎｇ－Ｈｙｕｎ Ｃ，Ｄｏｎｇ—Ｓｏｏ Ｋ，Ｙａｎｇ—Ｈｏｉ Ｄ．Ｍｕｌｔｉ—ａｇｅｎｔ ｂａｓｅｄ ［１４］刘衍民．粒子群算法的研究及应用［Ｄ］．济南：山东师范大学， ｔａｓｋ ａｓｓｉｇｎｍｅｎｔ ｓｙｓｔｅｍ ｆｏｒ ｖｉｒｔｕａｌ ｅｎｔｅｒｐｒｉｓｅｓ［Ｊ］．Ｒｏｂｏｔｉｃｓ ２０ｌ１． ａｎｄ Ｃｏｍｐｕｔｅｒ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ，２００７，２３：６２４—６２９． ［１５］陈大川，张荣国，黄付亮，等．ＰＳＯ算法在子任务分配中的应用［Ｊ］． ［５】Ｓｈｅｎ Ｃｈｅｎｇｌｉｎ．Ｄｅｃｉｓｉｏｎ ｍｏｄｅｌｓ ｏｆ ｔａｓｋ ａｓｓｉｇｎｍｅｎｔ ｆｏｒ ｖｉｒｔｕａｌ 计算机工程，２０１１，３７（２４）：１８３．１８６． ｅｎｔｅｒｐｒｉｓｅ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ－－ａｇｅｎｔ ｔｈｅｏｒｙ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ Ｉｎｔｅｒ・－ ［１６］叶春晓，罗娟．基于网格的混合微粒群算法解决任务调度问 ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｎａｇｅｍｅｎｔ ａｎｄ Ｓｅｒｖｉｃｅ Ｓｃｉｅｎｃｅ， 题［Ｊｆ．计算机工程与应用，２０１２，４８（１２）：３４．３７． ２００９． ［１７］Ｅｒｔｕｑｒｕｌ Ｉ，Ｋａｒａｋａｓｏｑｌｕ Ｎ．Ｐｅｒｆｏｒｍａｎｃｅ ｅｖａｌｕａｔｉｏｎ ｏｆ Ｔｕｒｋｉｓｈ ［６］Ｌｉｎ Ｗ，Ｂｙｍｅｓ Ｃ．Ｃｏｎｔｒｏｌ ｏｆ ｄｉｓｃｒｅｔｅ—ｔｉｍｅ ｎｏｎｌｉｎｅａｒ ｓｙｓｔｅｍ［Ｊ］． ｃｅｍｅｎｔ ｆｉｒｍｓ ｗｉｔｈ ｆｕｚｚｙ ａｎａｌｙｔｉｃ ｈｉｅｒａｒｃｈｙ ｐｒｏｃｅｓｓ ａｎｄ ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｔｏｍａｔｉｃ Ｃｏｎｔｒｏｌ，１９９６，４１（４）：４９４—５１０． ＴＯＰＳＩＳ ｍｅｔｈｏｄｓ［Ｊ］．Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎ，２００９， ［７】杜继永，张凤鸣，杨骥，等．多ＵＣＡＶ协同任务分配模型及粒子 ３６（１）：７０２。７１５． （上接２５页） ［７】Ｘｕ Ｃ Ｃ，Ｗａｎｇ Ｗ，Ｃｈｅｎ Ｊ，ｅｔ ａ１．Ａｎａｌｙｚｉｎｇ ｔｒａｖｅｌｅｒｓ’ｉｎｔｅｎｔｉｏｎ 基础上，分析并计算模型参数，得到了多源出行信息影响 ｔｏ ａｃｃｅｐｔ ｔｒａｖｅｌ ｉｎｆｏｒｍａｔｉｏｎ ｓｔｒｕｃｔｕｒａｌ ｅｑｕａｔｉｏｎ ｍｏｄｅｌｉｎｇ［Ｊ］． 下驾驶员任务集聚认知模式的决策模型。该模型的有效 Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｒｅｃｏｒｄ，２０１０，２１５６：９３—１００． 性得到了较好验证，从而可知，有序多分类Ｌｏｇｉｓｔｉｃ回归模 ８戢晓峰，成卫．基于出行决策的出行信息认知模式研究［Ｊ］．人类 工效学，２０１１，１７（１）：６０—６９． 型在驾驶员信息认知模式中具有很好的适应性和实用性。 ［９］魏雪梅，戢晓峰，陈方．基于ＳＥＭ的驾驶员出行信息搜寻行为 分析［Ｊ］．交通运输系统工程与信息，２０１２，１２（３）：１７４—１７９． 参考文献： ［１０］潘泉．信息融合理论的基本方法与进展［Ｊ】．自动化学报，２００３， ［１］Ｂｅｓｔ Ｊ Ｂ［美］．认知心理学［Ｍ］．黄希庭，译．北京：中国轻工业出 ２９（４）：６００—６０５． 版社，２０００． ［１１］王雷，王晓原，杨新月基于多源信息融合的驾驶员行为协调 ［２】Ｒａｍｍｉｎｇ Ｍ Ｓ．Ｎｅｔｗｏｒｋ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｒｏｕｔｅ ｃｈｏｉｃｅ［Ｄ］，Ｍａｓ— 仿真算法［Ｊ】．交通运输系统工程与信息，２００６，６（１）：８６—９０． ｓａｃｈｕｓｅｔｔｓ Ｃａｍｂｒｉｄｇｅ：Ｍａｓｓａｃｈｕｓｅｔｔｓ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， ［１２］Ｃｈｏｒｕｓ Ｃ Ｇ，Ｍｏｌｉｎ Ｅ Ｊ Ｅ，Ａｒｅｎｔｚｅ Ｔ Ａ，ｅｔ ａ１．Ｖａｌｉｄａｔｉｏｎ ｏｆ ａ ２００２． ｍｕｌｔｉｍｏｄａｌ ｔｒａｖｅｌ ｓｉｍｕｌａｔｏｒ ｗｉｔｈ ｔｒａｖｅｌ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｖｉ— ［３】Ｄｅｌｌ’Ｏｒｃｏ Ｍ，Ｔｅｏｄｏｒｏｖｉｃ Ｄ．Ｄａｔａ ｆｕｓｉｏｎ ｆｏｒ ｕｐｄａｔｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ ｓｉｏｎ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ：Ｐａｒｔ Ｃ，２００７，１５（３）：１９１—２０７． ｉｎ ｍｏｄｅｌｉｎｇ ｄｒｉｖｅｒｓ’ｃｈｏｉｃｅ ｂｅｈａｖｉｏｒ［Ｊ］．Ｔｒａｎｓｐｏｒｔ Ｍｅｔｒｉｃ， ［１ ３］Ｃｈｏｒｕｓ Ｃ，Ａｒｅｎｔｚｅ Ｔ，Ｔｉｍｍｅｒｍａｎｓ Ｈ．Ｉｎｆｏｒｍａｔｉｏｎ ｉｍｐａｃｔ ｏｎ ２００９，５（２）：１０７．１２３． ｑｕａｌｉｔｙ ｏｆ ｔｒａｖｅｌ ｃｈｏｉｃｅｓ：ａｎａｌｙｓｉｓ ｏｆ ｄａｔａ ｆｒｏｍ ａ ｍｕｌｔｉｍｏｄａｌ ［４］Ｃｈｏｒｕｓ Ｃ Ｇ．Ｔｒａｖｅｌｅｒｓ’ｎｅｅｄ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ：ａｎ ｅｍｐｉｉｒｃａｌ ｓｔｕｄｙ ｔｒａｖｅｌ ｓｉｍｕｌａｔｏｒ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８６ｔｈ Ａｎｎｕａｌ Ｍｅｅｔｉｎｇ ｉｎｔｏ ｔｈｅ ｒｏｌｅ ｏｆ ｋｎｏｗｌｅｄｇｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８５ｔｈ Ａｎｎｕａｌ ｏｆ ｔｈｅ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｂｏａｒｄ，Ｗａｓｈｉｎｇｔｏｎ ＤＣ，２００７． Ｍｅｅｔｉｎｇ ｏｆ ｔｈｅ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｂｏａｒｄ，Ｗａｓｈｉｎｇｔｏｎ ［１４】戢晓峰，陈方，韩春华城市出行信息环境分层规划方法［Ｊ］．城 ＤＣ，２００６． 市问题，２０１１，４（１）：４８—５１． ［５］莫一魁，苏永云，沈旅欧．基于结构方程的小汽车驾驶员信息 ［１５］戢晓峰．公共交通乘客出行信息接受水平评价方法［Ｊ］＿城市交 偏好分析［Ｊ］．系统工程，２００８，２７（８）：８５—８９． 通，２００９，７（１）：７２—７５． ［６］戢晓峰，刘澜．多模式公共交通系统的出行信息有效性研究［Ｊ１． ［１６］王济川，郭志刚．Ｌｏｇｉｓｔｉｃ回归模型——方法与应用［Ｍ］．北京： 武汉理工大学学报：交通科学与工程版，２００９，３３（５）：９８０—９８３． 高等教育出版社，２００１．
