2024年6月12日发(作者：之星腾)
第２７卷第３期 计算机应用与软件
Ｖｏ１．２７ Ｎｏ．３
２０１０年３月
Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ
Ｍａｒ．２０１０
基于混合粒子群优化算法的现金流优化
黄少荣
（广东司法警官职业学院信息管理系 广东广州５１０５２０）
摘要 以最大化现金流净现值为优化目标的多模式资源约束调度问题ＭＭＲＣＰＳＰ（Ｍｕｌｔｉ－ｍｏｄｅ Ｒｅｓｏｕｒｃｅ－Ｃｏｎｓｔｒａｉｎｅｄ Ｐｒｏｊｅｃｔ
Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ）是一类带有复杂非线性特征的ＮＰ－ｈａｒｄ问题，传统粒子群算法在解决该类离散问题上具有一定局限性。从粒子
群算法的优化原理出发，结合遗传算法，在粒子群算法中引入交叉和变异操作，得出一种应用于ＭＭＲＣＰＳＰ现金流优化的快速、易实
现的混合粒子群算法，拓宽了粒子群优化算法在离散优化领域的应用。仿真实验结果验证了算法的有效性和高效性。
关键词 粒子群算法现金流优化 净现值 交叉 变异
ｏＩ．ｒＩ＇ＩＭＩＳＩＮＧ ＣＡＳＨ ＦＬｏＷ ＢＡＳＥＤ ｏＮ ＨＹＢＲＩＩ）ＰＡＲＴＩＣＬＥ ＳＷＡＩ Ｍ ｏＰＴｎ压ＩＳＡＴＩＯＮ
Ｈｕａｎｇ Ｓｈａｏｒｏｎｇ
（Ｄｅｐａｒｔｍｅｎｔ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ，Ｇｕａｎｇｄｏｎｇ Ｊｕｓｔｉｃｅ Ｐｏｌｃｉｅ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ，Ｇｕａｎｇｚｈｏｕ ５１０５２０，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉａｎ）
Ａｂｓｔｒａｃｔ Ｍｕｌｔｉ－ｍｏｄｅ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ（ＭＭＲＣＰＳＰ）ｉｓ ａｎ ＮＰ—ｈａｒｄ ｐｒｏｂｌｅｍ ｗｉｔｈ ｃｏｍｐｌｅｘ ｎｏｎ－ｌｉｎｅａｒ ｆｅａｔｕｒｅ，
ｗｈｉｃｈ ｈａｓ ｔｈｅ ｏｐｔｉｍｉｓａｔｉｏｎ ｏｂｊｅｃｔ ｏｆ ｍａｘｉｍｉｓｉｎｇ ｔｈｅ ｃａｓｈ ｌｆｏｗ ｎｅｔ ｐｒｅｓｅｎｔ ｖａｌｕｅ．Ｔｒａｄｉｔｉｏｎａｌ ｐａｒｔｉｃｌｅ ｓｗａｌｒｎ ｏｐｔｉｍｉｓａｔｉｏｎ ｈａｓ ｃｅｒｔａｉｎ ｌｉｍｉｔａｔｉｏｎ
ｉｎ ｓｏｌｖｉｎｇ ｓｕｃｈ ｄｉｓｃｒｅｔｅ ｐｒｏｂｌｅｍｓ．Ｐｒｏｃｅｅｄｉｎｇ ｆｒｏｍ ｔｈｅ ｏｐｔｉｍｉｓａｔｉｏｎ ｐｒｉｎｃｉｐｌｅ ｏｆ ＰＳＯ ａｎｄ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ ｗｅ
ｉｎｔｒｏｄｕｃｅ ｃｒｏｓｓｏｖｅｒ ａｎｄ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｉｏｎ ｔｏ ＰＳＯ ａｎｄ ｄｅｒｉｖｅ ａ ｈｙｂｒｉｄ ＰＳＯ ｔｏ ｂｅ ａｐｐｌｉｅｄ ｔｏ ＭＭＲＣＰＳＰ ｃａｓｈ ｆｌｏｗ ｏｐｔｉｍｉｓａｔｉｏｎ，ｉｔ ｉｓ ｆａｓｔ ａｎｄ
ｅａｓｙ ｔｏ ｕｓｅ，ａｎｄ ｗｉｄｅｎｓ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ＰＳＯ・ｉｎ ｄｉｓｃｒｅｔｅ ｏｐｔｉｍｉｓａｔｉｏｎ ｆｉｅｌｄ．Ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｈｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｖａｌｉｄｉｔｙ ａｎｄ ｅｆｆｉ・
ｃｉｅｎｃｙ ｏｆ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ．
Ｋｅｙｗｏｒｄｓ Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｓａｔｉｏｎ（ＰＳＯ） Ｃａｓｈ ｌｆｏｗ ｏｐｔｉｍｉｓａｔｉｏｎ Ｎｅｔ ｐｒｅｓｅｎｔ ｖａｌｕｅ Ｃｒｏｓｓｏｖｅｒ Ｍｕｔａｔｉｏｎ
项目中各活动的执行模式，还要确定活动的开工期，随着项目规
０ 引 言
模的不断扩大，必须运用启发式算法才能计算。因此，本文选择
智能算法ＰＳＯ对问题进行求解。在此基础上，根据ＰＳＯ的优化
粒子群优化算法ＰＳＯ（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ）是最早
本质，针对传统ＰＳＯ在优化现金流时速度难以表达的问题，借
由Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｔｒ在研究鸟类和鱼类的群体行为基础上于 鉴遗传算法的基本思想，在ＰＳＯ中引入交叉和变异操作，不仅
１９９５年提出的一种群智能算法…，其思想来源于人工生命和演
巧妙地分解了速度项，而且改善了解的质量和多样性。
化计算理论，模仿鸟群觅食行为，通过鸟集体协作使群体达到最
优。由于ＰＳＯ概念简单，容易实现，收敛速度快，执行性能高效
１现金流优化模型
等优势，逐渐被应用到越来越多的科学研究和工程实践中。
资金是企业从事生产经营活动的“血液”，项目中消耗资源
１．１ 问题描述
的任何施工生产活动，都离不开资金的流动，都不外乎现金的流
ＭＭＲＣＰＳＰ现金流优化问题描述如下 Ｊ：给定一个项目，包
人和流出，现金流贯穿项目管理的始终。可以说，项目管理的过
含多个事件，每个事件可有多个活动，每个活动有多种执行模
程实际上也就是现金流量的流转过程，因此，做为项目管理核心
式，具有不同的现金流、工期和资源需求，且活动间有优先关系
的项目调度首先应关注项目的现金流量动态。而传统的带资源
约束。问题的解是对项目各活动的执行模式和开工期进行合理
约束的项目调度问题ＲＣＰＳＰ（Ｒｅｓｏｕｒｃｅ．Ｃｏｎｓｔｒａｉｎｅｄ Ｐｒｏｊｅｃｔ
调度，在满足资源约束和优先约束的前提下，使项目的净现值
Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ）一般以最短工期为优化目标，不能有效反映
ＮＰＶ（Ｎｅｔ Ｐｒｅｓｅｎｔ Ｖａｌｕｅ）最大化。
项目收益，与实际项目调度目标不符。因此，在ＲＣＰＳＰ中引入
（１）活动网络图采用ＡｏＡ（Ａｃｔｉｖｉｔｙ—ｏｎ。Ａｒｃ）网络图来描述，
现金流优化目标 ，对项目中的现金流入与现金流出进行管理
箭线代表活动，节点代表事件，活动发生的现金流都按一定折现
和优化，保持现金流出与现金流入之间最佳结构关系，实现现金
率折算到项目开始时。
净收入的最大化显得尤为重要，能有效规避项目风险，并使企业 （２）活动具有资源约束和优先约束，执行模式一旦选定便
收益最大化，在实际应用中具有重要意义。 不能更改，且具有非抢占式的特性。每种资源的可获得量及单
传统ＲＣＰＳＰ已被证明是ＮＰ－ｈａｒｄ问题，本文根据施工实际
在调度时还必须考虑每个活动有多种可执行模式，即多模式资
收稿日期：２００８—０９—１５。黄少荣，讲师，主研领域：进化算法和人
源约束调度问题ＭＭＲＣＰＳＰ，它比ＲＣＰＳＰ更加复杂，不仅要选择
工智能。
２７６
位成本为已知。
计算机应用与软件 ２０１０丘
２．２ 改进ＰＳｏ
ＰＳＯ算法的本质是利用当前位置、全局极值和个体极值三
（３）现金流指项目各活动发生的现金流人和现金流出。现
金流入包括项目开工时业主对承包商的预付款、业主在支付节
个信息，指导粒子下一步迭代位置。其个体充分利用自身经验
和群体经验调整自身的状态是ＰＳＯ算法具有优异特性的关键。
粒子可以从多种形式从其个体极值和全局极值中获得更新信
息，传统的速度一位移更新模型仅为符合此优化原理的具体实现
之一，反映粒子所代表的解在连续空间内，跟随个体极值以及全
局极值以矢量运算的形式进行更新，仅适合于处理连续优化问
题。对于离散优化问题，由于解空间是离散点的集合，利用ＰＳＯ
点按一定比例支付与完成进度成正比的工程款、项目提前完工
获得的奖金 现金流出包括各种资源费用、直接费用、间接费
用、延迟完工的罚金等。
１．２模型
设ｃ 为活动（ｉ，Ｊ）的现金流，非负整数ｔ 为该活动的开始
执行时间，参考文献［３，４ 中的模型，建立如下非线性规划
模型：
ｍａｘＮＰＶ＝∑ＣＦｉ
ｌ
￣ｅｘｐ（一ｓｔ ） （１）
＝
Ｓ．ｔ．
ｌＩ２，…， （２）
＝１，２，…，Ｖ ＝１，２，…，Ｋ
ｌ ４
∑￡≤∑（
Ｅ ｆ ｔ
￡一∑ ）
Ｒ １
＝１ ２一，Ｎ （３）
ｉ Ｅ ｎ Ｓ（ｎ
式（１）表示最大化项目净现值， 为折现率；式（２）表示资
源约束，即项目执行中，正在执行的活动的各种资源的使用量不
能超过其最大使用限额。』４ 表示在时期ｔ时正在进行的活动集
合，Ｖ为资源种类数，ｒ 为活动（ｉ√）用模式ｋ执行时单位工期所
需资源 的数量；式（３）表示优先关系约束：事件 的前趋活动
（ｉ， ）必须在事件 的后继活动（ ，１）开始之前完成， 为活动
（ｉ， ）以模式 执行时的活动工期，［Ｅ ，Ｌ ，］为活动（ｉ，，）的时
间窗
２基本粒子群算法及其改进
２．１基本ＰＳＯ
ＰＳ０算法首先初始化一群随机粒子，然后通过迭代找到最
优解。在每一次迭代中，粒子通过跟踪两个“极值”即个体极值
和全局极值来更新自己的速度与位置。假设ｍ个粒子组成一
个种群并在Ｄ维空间搜索，第ｉ个粒子在第ｔ代的位置表示为
一
个Ｄ维的向量 （ｔ）＝（ ， ，…， ∞），飞翔速度为 （ｔ）＝
（ ，…， 。），粒子本身历史最佳位置为Ｐ （ｔ）＝（Ｐ Ｐ ，…，
Ｐ 。），群体历史最佳位置为Ｐ （ｔ）＝（Ｐ Ｐ ，…，Ｐ Ｄ）。ＰＳＯ算
法迭代公式如下：
（ｔ＋１）＝ × （ｔ）＋Ｃ】×ｒｌ×（Ｐ （ｔ）～ （ｔ））＋
ｃ２×１＂２ ｘ（Ｐ （ｔ）一 （ｔ）） （４）
（ｔ＋１）＝ （ｔ）＋ （ｔ＋１） （５）
其中， 为惯性权重，ｃ 和ｃ：为加速系数， 和ｒ２是两个独立的
介于Ｅｏ，１］之间的随机数，ｔ为进化代数。式（４）第一部分为粒
子先前行为的惯性；第二部分为“认知”部分，表示粒子本身的
思考；第三部分为“社会”部分，表示粒子间的信息共享与相互
合作。
ＰＳＯ保留了基于种群的全局搜索策略，其特有的记忆可以
动态地跟踪当前的搜索情况来调整下一步的搜索策略，是一种
更高效的并行搜索算法，已成功应用于函数优化、多目标优化、
动态优化、神经网络训练等领域，但大部分应用都是基于传统的
速度一位移模型中，在解决离散问题时很难取得突破。
进行优化时不能直接移植传统模型，必须对问题进行变形，或者
修正速度和位置更新公式 。
ＭＭＲＣＰＳＰ现金流优化问题，若按传统ＰＳＯ模型，其速度难
以表达，因此需对公式进行变形。ＰＳＯ的关键在于确定粒子的
更新方式以及粒子的局部搜索和随机搜索方法，参照遗传算法
的基本思想，由交叉和变异完成粒子位置的更新 ：把公式（４）
中的６０× （ ）项看作变异操作，即随机搜索，ｃ ×ｒ。×（Ｐ （ｔ）一
（ｔ））＋Ｃ：×ｒ：×（Ｐ （ｔ）一 （ｔ））项看作交叉操作，即粒子与全
局极值和个体极值的信息交换。
引入遗传操作的粒子群算法称混合粒子群算法ＨＰＳ０（Ｈｙ—
ｂｒｉｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ），主要方法为：每一代中，每个粒
子先与全局极值交叉，再与个体极值交叉来产生更接近最优解
的新位置，并加入变异操作以增加解的多样性。该算法既克服
了ＰＳＯ在解决上述模型中速度难以表达的缺点，又结合了遗传
算法简单通用、鲁棒性强、适用于并行处理等优点．并且交叉操
作直接从全局极值和个体极值中获得更新信息，有效提高解的
质量，变异操作又能提高解的多样性，能更好地解决ＭＭＲＣＰＳＰ
现金流优化问题。
３ 求解ＭＭＲＣＰｓＰ现金流优化模型的混合粒
子群算法
３．１编码及初始化
传统粒子群算法中，粒子的位置和速度均以连续参数的形
式表示，限制了粒子群算法在离散优化领域的应用。本文针对
这一问题，对种群进行初始化时借鉴遗传算法中解的编码设计，
提出了一种采用基于时间序列的整数编码方式。
Ｓｔｅｐｌ对活动的执行模式进行编码，活动用自然数（Ｏ－－Ｍ
＋１）表示，自然数ｍ表示第ｍ个活动（０、Ｍ＋１表示虚拟活
动），每个活动有ｋ种执行模式，由于执行模式是以字符表示，在
对其进行编码时，依据顺序对每个活动的每种模式进行编码，第
１活动的第１种执行模式用１表示，第２种模式用２表示，…，第
ｋ种模式用ｋ表示；第２个活动的第１种执行模式用ｋ＋１表示，
第２种执行模式用ｋ＋２表示，…；第ｍ个活动的第ｋ种执行模
式用ｍｋ表示。
Ｓｔｅｐ２在未分配资源的活动中选择没有紧前活动或其紧
前活动都已经分配资源的活动，组成候选集合，如果候选集合为
空，则转Ｓｔｅｐ４；
Ｓｔｅｐ３从候选集合中随机选择一个候选模式，为其安排开
始的时间；其最早开始的时间为其所有紧前活动中最晚结束的
时间，如果在其持续的时段内所剩的资源不能满足该活动，则改
变该活动的实施模式或者将其开始时间后移，直到满足资源约
第３期
束条件，转Ｓｔｅｐ２；
Ｓｔｅｐ４结束。
黄少荣：基于混合粒子群优化算法的现金流优化
最后输出全局极值ｇ蛔 和全局极值位置Ｐ 。
２７７
从算法流程可以看出，相对于遗传算法中染色体互相共享信
息，整个种群比较均匀地向最优区域移动比较，混合ＰＳＯ中的粒 重复此过程，即可生成初始种群，每个粒子位置由一系列包
含了活动、执行模式、开工期三方面信息的模式代码组成，表示
一
个可行调度。
子直接从全局极值和个体极值获得更新信息，整个搜索过程是一
种单向的信息流动机制，其目的性更强，效率更高，对解的改进影
响更大，所有粒子将更快地收敛到最优解。而且，避免了大量冗
３．２适应值函数
由于优化目标是最大化项目现金流净现值，故直接以ＮＰＶ
的计算公式作为适应值函数，适应值越大，整个项目的净现值越
大，效益越好。适应值设定如下：
Ｍ
余的更新操作，减少寻优迭代次数，提高了算法效率 。
传统粒子群算法中涉及到的速度更新的参数虽然只有三个：
惯性权重 ，加速系数ｃ 和ｃ：，但这些参数的最优取值组合的选
择非常困难，有时微小的差别就能带来巨大的结果差异，尤其对
Ｆｉｔｎｅｓｓ（ ）＝∑ＣＦｉｉｅｘｐ（ａｔ ） （６）
Ｉ ｌ
３．３粒子的更新
粒子通过与全局极值和个体极值交叉来获得更新信息，这
种单向流动的目的性很强，为防止算法早熟，结果落人局部最
优，在算法中加入变异操作，让与全局极值和个体极值分别交叉
后产生的新粒子按一定概率进行变异，并把变异前后的粒子按
适应值大小进行择优保留。通过交叉变异操作，粒子位置得到
更新。
１）交叉操作采用了单点次序交叉，具体方法如下：
（１）粒子ｐ１和ｐ２交叉，随机产生一个交叉点。
（２）保留ｐｌ交叉点前的模式，并依序遍历ｐ２中的模式，如
果该模式不与ｐ１中保留的模式属于同一个活动，则保留，否则
删除，然后将剩余的模式按顺序插入ｐ１交叉点后的位置，产生
新粒子口１。
（３）同理，产生新粒子ｑ２。
由于产生的新粒子在交叉点前的模式编码是满足资源约束
和优先约束的，交叉点后的模式编码是父粒子中的一部分且其
优先次序保持不变，也是满足资源约束和优先约束的，因此新粒
子一般能满足资源约束和优先约束。
２）变异操作采用整体变异方式，以变异率决定某个粒子
是否执行变异，若执行，按３．１节编码方式重新随机生成新粒
子。由于是直接对各个活动的各种可执行模式进行编码，每个
模式编码实际上包含了活动、执行模式以及开工期三方面的信
息，而且满足资源约束和优先约束。
３．４算法流程
设定迭代次数为 ，变异率Ｗ，随机产生ｎ个粒子。
根据公式（６）计算每个粒子的适应值 ，设置当前适应值
为个体极值Ｐ ，当前位置为个体极值位置ｐ；，根据各个粒子的
适应值找出全局极值ｇ 和全局极值位置 。
Ｗｈｉｌｅ（迭代次数＜Ｔ）ｄｏ
ｆｏｒｉ＝１：Ｔ
ｆ０ｒｊ＝１：ｎ
第ｊ个粒子位置Ｘ０（ｊ）与Ｐ 交叉，记为Ｘ １（ｊ）。
Ｘ １（ｊ）与Ｐｉ交叉，记为Ｘ １（ｊ）。
对Ｘ” （ｊ）按一定概率进行变异，选取适应值高的粒子位置记为
Ｘ１（ｊ）。
根据当前位置计算适应值ｆ．。
如果ｆ （ｊ）＞Ｐｉ （ｊ），则ＰＩｂ。 （ｊ）＝ｆ１（ｊ），Ｐ （ｊ）：Ｘ１（ｊ）。
Ｅｎｄ
根据各个粒子的个体极值Ｐ ，找出全局极值ｇ 和全局极值位
置Ｐｇ。
Ｘ０ Ｘｌ。
Ｅｎｄ
于复杂、高维函数模型，通过传统ＰＳＯ算法很难获得最优解，容易
陷入局部最优。本文提出的ＨＰＳＯ算法，由于粒子通过交叉方式
直接从全局极值和个体极值获得更新信息，使算法的可调参数减
少，避免了 ，ｃ，，ｃ 这三个参数的组合选择，更容易实现。
４实例及分析
４．１ 实例
某项目包括９个事件、１２个活动，其网络图如图１所示，项
目中的每个活动均有两种可执行模式，不同模式下各活动的信
息如表１所示。项目总价为３００００元，项目开工业主即支付
２０％总价作为预付款，在支付节点业主按７０％的比例支付已经
完工的活动工程款，项目完工时结清余款。项目工期为３０±５
天，每提前（推后）一天完成按项目总价的１％（１．５％）进行奖励
或惩罚。资源单位工期限定为１Ｏ，单价为１２元，单位工期发生
的间接费用为１２０元，所有现金流以０．０２的折现率折现到项目
开工时，现要求在不同支付节点下（支付１）对项目作出合理调
度，以使净收益最大。
图１项目ＡｏＡ网络图
表１ 多模式下各活动的现金流、工期以及资源需求量
常规模式（ｎ） 加急模式（ｃ）
活动号 工程款
工期 直接费用 资源／工期 工期 直接费用 资源／工期
１（１，２） ｌｏｏＯ ５ ５ｏｏ ４ ４ ５５０ ５
２（１，３） ８０ｏ ４ ４ｏｏ ５ ３ ４８０ ４
３（２，４） ｌ５００ ４ ４５０ ５ ２ ５０ｏ ３
４（２，５） ７０ｏ ３ ３０ｏ ４ ２ ３５０ ５
５（３，５） １２０ｏ ６ ６８０ ３ ４ ７５０ ３
６（３，６） ｌ６００ ６ ６５０ ３ ４ ７ｏｏ ４
７（４，７） １７ｏｏ ７ ７２０ ４ ５ ８５０ ４
８（４，８） ２５０ｏ ５ ６０ｏ ３ ４ ６５０ ５
９（５，９） ｌ２ｏｏ ４ ３０ｏ ３ ３ ３５０ ４
１０（６，８） ３５０ｏ １０ ８００ ７ ８ ６００ ８
１１（７，９） ９０ｏ ３ ２３０ ２ ２ ２８０ ３
１２（８，９） ２３００ ８ ６５０ ３ ６ ７５０ ４
２７８
４．２参数设置
计算机应用与软件 ２０１０丘
用到更切合实际工程的多模式、带基于进度的多节点支付和带
奖惩机制并以净现值为优化目标的资源约束项目调度问题中，
是对ＰＳＯ算法应用领域的一个成功拓展，为ＰＳＯ在离散优化领
域的应用提供了一种新的思路。
本文提出的ＨＰＳＯ算法操作简单，可调参数少，方便调试。
根据优化模型及上述具体问题，测试后最佳参数设置为：粒子数
为２０，迭代次数为１００，变异概率为０．１。算法用ＶＣ语言编程
实现，程序运行环境为个人ＰＣ。
４．３算法结果
在上述实例运行ＨＰＳＯ，运算结果如表２所示。
表２不同支付事件下的项目净收益（ＮＰＶ）
支付节点 最优调度（①活动②模式③开工期）
①１—２—６—５—３—８—１０—７—１２—４—９—１１
②ｅ—ｎ—ｃ—ｃ—ｎ—ｎ—ｃ—ｃ—ｃ—ｎ～ｃ—ｎ
（３，７）
③１—１—５—５—５—９—９—１４—１７—１７—２０—２０
ＮＰＶ：１３５０５．７（项目工期２２天）
①１—２—６—３—８—４—１０—５—７—１２—９—１１
②Ｃ—ｎ—ｅ—ｃ—ｎ—ｃ—ｃ—ｃ—ｃ—ｃ～ｎ—ｃ
（２，４，６）
③１—１—５—５—７—７—９—１２—１６—１７—１７—２１
ＮＰＶ＝１３７５６（项目工期２２天）
４．４结果分析
（１）从表２可以看出，ＨＰＳＯ算法能有效地解决ＭＭＲＣＰＳＰ
现金流优化问题，做出合理、高效、实用的项目调度。表中ＮＰＶ
值反映出不同的支付节点带来不同的净现值，～般地，支付节点
越多越靠前，现金流人越多越快，项目净现值越大。
（２）ＨＰＳＯ算法在最大化项目净现值前提下能尽量缩短工
期，提高项目施工效率，达到多目标优化的目的。而且，现金流
优化模型弹性大，可灵活设置活动数目、执行模式、资源种类及
限制、不同的支付节点等，适用于现实复杂项目调度。
（３）对于较大规模的算例，混合粒子群算法同样表现了良
好的收敛性能。将ＨＰＳＯ与简单遗传算法（ＧＡ）两种方法应用
于包含１８个事件、３Ｏ个活动的大型项目上测试，两种方法均运
行ｌ０次，并将结果做比较，结果如表３所示。由此可见，ＨＰＳＯ
在解决现金流优化问题上性能具有优越性，算法具有更快的收
敛速度，优化结果也更接近实际的全局最优。
表３ Ｉ－ＩＰＳＯ／ＧＡ算法性能对比
方法 找到最优解次数 最优解平均误差 找到最优解平均代数
ＧＡ ５７ ７．８％ ４７
ＨＰＳ０ ８６ ３．４％ ２３
５结论
ＰＳＯ算法作为一种新兴算法，尚缺乏数学理论支撑，仅适合
于连续问题的优化，难以应用于离散领域的优化。对算法本身
需要加强其数学理论研究和不断拓宽其应用领域的广度和深
度。通过与遗传算法、蚁群算法、模拟退火、人工神经网络及模
糊逻辑系统等其它人工智算法渗透结合，将是提升算法性能和
拓宽应用的主要途径。本文从ＰＳＯ的优化原理出发，引入遗传
算法的交叉和变异操作，并把改进后的混合粒子群优化算法应
参考文献
［１］Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ．Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／ＩＥＥＥ Ｉｎｔｅｒ－
ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ，ｐｅｒｔｈ，Ａｕｓｔｒａｌｉａ，１９９５：１９４２
—
１９４８．
［２］Ｒｕｓｓｅｌｌ Ａ Ｈ＿Ｃａｓｈ ｆｌｏｗｓ ｉｎ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９７０，
１６（４）：３５７—３７３．
［３］张静文，徐渝，何正文．多模式资源约束型折现流时间一费用权衡项
目进度［Ｊ］．系统工程，２００５，２３（５）：１７～２１．
［４］张颖，刘艳秋，汪定伟，等．ＲＣＰＳＰ中现金流优化问题的ＨＧＡ方法
［Ｊ］．基础自动化，２００１，８（４）：５—７．
［５］彭传勇，高亮，邵新宇，等．求解作业车间调度问题的广义粒子群优
化算法［Ｊ］．计算机集成制造系统，２００６，１２（６）：９１１—９２３．
［６］高尚，杨静宇．群智能算法及其应用［Ｍ］．中国水利水电出版社，
２００６．８９—９０．
（上接第２６７页）
终端通过ａｓｔｅｒｉｓｋ建立会话并结束会话的过程，发起会话的ＳＩＰ
终端Ａ和应答会话的ＳＩＰ终端Ｂ的ＪＰ地址分别为１９２．１６８．１．
１１２和１９２．１６８．１．１１０，ａｓｔｅｒｉｓｋ服务器的ＩＰ地址为１９２．１６８．１．
２Ｏ。由Ｅｔｈｅｒｅａｌ捕获的ＳＩＰ消息可以看到，Ａ发送ＩＮＶＩＴＥ请求
消息发起呼叫，Ｂ接收到后回复２００ ＯＫ消息，Ａ再发送ＡＣＫ请
求消息，这个消息流程完全符合ＲＦＣ３２６１的ＳＩＰ协议规范。同
时在３２路ＳＩＰ会话同时进行的网络负载下进行１００次测试呼
叫，成功率为１００％。
Ｅ１１ ｌｓ｛ｐ …… 口・
图５ ＳＩＰ会话过程网络监控图
５ 结论
ＳＩＰ协议的不断发展和完善，使其越来越受到关注。本文
设计的系统实现了具有基本呼叫功能的ＳＩＰ终端，测试结果表
明系统运行稳定且高效，并且易于扩展实现事件通知机制和参
考方法等ＳＩＰ扩展方法以支持会议终端功能，可以广泛应用于
许多多媒体会议系统中 ］。
参考文献
［１］Ｒｏｓｅｎｂｅｒｇ Ｊ，Ｓｃｈｕｌｚｒｉｎｎｅ Ｈ．Ｓｅｓｓｉｏｎ Ｉｎｉｔｉａｔｉｏｎ Ｐｒｏｔｏｃｏｌ［Ｓ］．ＲＦＣ ３２６１，
２ｏｏ２．
［２］沈鑫剡．多媒体传输网络与ＶＯＩＰ系统设计［Ｍ］．北京：人民邮电
出版社，２００５．
［３］熊华，刘风新，潘小莉．Ｗｉｎｄｏｗｓ动态链接库原理分析及其应用
［Ｊ］．北京：北京化工大学学报，２００４．
［４］Ｄａｎｉｅｌ Ｃｏｌｌｉｎｓ．ＶｏｌＰ技术与应用［Ｍ］．北京：人民邮电出版
社．２００３．
2024年6月12日发(作者：之星腾)
第２７卷第３期 计算机应用与软件
Ｖｏ１．２７ Ｎｏ．３
２０１０年３月
Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ
Ｍａｒ．２０１０
基于混合粒子群优化算法的现金流优化
黄少荣
（广东司法警官职业学院信息管理系 广东广州５１０５２０）
摘要 以最大化现金流净现值为优化目标的多模式资源约束调度问题ＭＭＲＣＰＳＰ（Ｍｕｌｔｉ－ｍｏｄｅ Ｒｅｓｏｕｒｃｅ－Ｃｏｎｓｔｒａｉｎｅｄ Ｐｒｏｊｅｃｔ
Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ）是一类带有复杂非线性特征的ＮＰ－ｈａｒｄ问题，传统粒子群算法在解决该类离散问题上具有一定局限性。从粒子
群算法的优化原理出发，结合遗传算法，在粒子群算法中引入交叉和变异操作，得出一种应用于ＭＭＲＣＰＳＰ现金流优化的快速、易实
现的混合粒子群算法，拓宽了粒子群优化算法在离散优化领域的应用。仿真实验结果验证了算法的有效性和高效性。
关键词 粒子群算法现金流优化 净现值 交叉 变异
ｏＩ．ｒＩ＇ＩＭＩＳＩＮＧ ＣＡＳＨ ＦＬｏＷ ＢＡＳＥＤ ｏＮ ＨＹＢＲＩＩ）ＰＡＲＴＩＣＬＥ ＳＷＡＩ Ｍ ｏＰＴｎ压ＩＳＡＴＩＯＮ
Ｈｕａｎｇ Ｓｈａｏｒｏｎｇ
（Ｄｅｐａｒｔｍｅｎｔ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ，Ｇｕａｎｇｄｏｎｇ Ｊｕｓｔｉｃｅ Ｐｏｌｃｉｅ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ，Ｇｕａｎｇｚｈｏｕ ５１０５２０，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉａｎ）
Ａｂｓｔｒａｃｔ Ｍｕｌｔｉ－ｍｏｄｅ ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ（ＭＭＲＣＰＳＰ）ｉｓ ａｎ ＮＰ—ｈａｒｄ ｐｒｏｂｌｅｍ ｗｉｔｈ ｃｏｍｐｌｅｘ ｎｏｎ－ｌｉｎｅａｒ ｆｅａｔｕｒｅ，
ｗｈｉｃｈ ｈａｓ ｔｈｅ ｏｐｔｉｍｉｓａｔｉｏｎ ｏｂｊｅｃｔ ｏｆ ｍａｘｉｍｉｓｉｎｇ ｔｈｅ ｃａｓｈ ｌｆｏｗ ｎｅｔ ｐｒｅｓｅｎｔ ｖａｌｕｅ．Ｔｒａｄｉｔｉｏｎａｌ ｐａｒｔｉｃｌｅ ｓｗａｌｒｎ ｏｐｔｉｍｉｓａｔｉｏｎ ｈａｓ ｃｅｒｔａｉｎ ｌｉｍｉｔａｔｉｏｎ
ｉｎ ｓｏｌｖｉｎｇ ｓｕｃｈ ｄｉｓｃｒｅｔｅ ｐｒｏｂｌｅｍｓ．Ｐｒｏｃｅｅｄｉｎｇ ｆｒｏｍ ｔｈｅ ｏｐｔｉｍｉｓａｔｉｏｎ ｐｒｉｎｃｉｐｌｅ ｏｆ ＰＳＯ ａｎｄ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ ｗｅ
ｉｎｔｒｏｄｕｃｅ ｃｒｏｓｓｏｖｅｒ ａｎｄ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｉｏｎ ｔｏ ＰＳＯ ａｎｄ ｄｅｒｉｖｅ ａ ｈｙｂｒｉｄ ＰＳＯ ｔｏ ｂｅ ａｐｐｌｉｅｄ ｔｏ ＭＭＲＣＰＳＰ ｃａｓｈ ｆｌｏｗ ｏｐｔｉｍｉｓａｔｉｏｎ，ｉｔ ｉｓ ｆａｓｔ ａｎｄ
ｅａｓｙ ｔｏ ｕｓｅ，ａｎｄ ｗｉｄｅｎｓ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ＰＳＯ・ｉｎ ｄｉｓｃｒｅｔｅ ｏｐｔｉｍｉｓａｔｉｏｎ ｆｉｅｌｄ．Ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｈｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｖａｌｉｄｉｔｙ ａｎｄ ｅｆｆｉ・
ｃｉｅｎｃｙ ｏｆ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ．
Ｋｅｙｗｏｒｄｓ Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｓａｔｉｏｎ（ＰＳＯ） Ｃａｓｈ ｌｆｏｗ ｏｐｔｉｍｉｓａｔｉｏｎ Ｎｅｔ ｐｒｅｓｅｎｔ ｖａｌｕｅ Ｃｒｏｓｓｏｖｅｒ Ｍｕｔａｔｉｏｎ
项目中各活动的执行模式，还要确定活动的开工期，随着项目规
０ 引 言
模的不断扩大，必须运用启发式算法才能计算。因此，本文选择
智能算法ＰＳＯ对问题进行求解。在此基础上，根据ＰＳＯ的优化
粒子群优化算法ＰＳＯ（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ）是最早
本质，针对传统ＰＳＯ在优化现金流时速度难以表达的问题，借
由Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｔｒ在研究鸟类和鱼类的群体行为基础上于 鉴遗传算法的基本思想，在ＰＳＯ中引入交叉和变异操作，不仅
１９９５年提出的一种群智能算法…，其思想来源于人工生命和演
巧妙地分解了速度项，而且改善了解的质量和多样性。
化计算理论，模仿鸟群觅食行为，通过鸟集体协作使群体达到最
优。由于ＰＳＯ概念简单，容易实现，收敛速度快，执行性能高效
１现金流优化模型
等优势，逐渐被应用到越来越多的科学研究和工程实践中。
资金是企业从事生产经营活动的“血液”，项目中消耗资源
１．１ 问题描述
的任何施工生产活动，都离不开资金的流动，都不外乎现金的流
ＭＭＲＣＰＳＰ现金流优化问题描述如下 Ｊ：给定一个项目，包
人和流出，现金流贯穿项目管理的始终。可以说，项目管理的过
含多个事件，每个事件可有多个活动，每个活动有多种执行模
程实际上也就是现金流量的流转过程，因此，做为项目管理核心
式，具有不同的现金流、工期和资源需求，且活动间有优先关系
的项目调度首先应关注项目的现金流量动态。而传统的带资源
约束。问题的解是对项目各活动的执行模式和开工期进行合理
约束的项目调度问题ＲＣＰＳＰ（Ｒｅｓｏｕｒｃｅ．Ｃｏｎｓｔｒａｉｎｅｄ Ｐｒｏｊｅｃｔ
调度，在满足资源约束和优先约束的前提下，使项目的净现值
Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ）一般以最短工期为优化目标，不能有效反映
ＮＰＶ（Ｎｅｔ Ｐｒｅｓｅｎｔ Ｖａｌｕｅ）最大化。
项目收益，与实际项目调度目标不符。因此，在ＲＣＰＳＰ中引入
（１）活动网络图采用ＡｏＡ（Ａｃｔｉｖｉｔｙ—ｏｎ。Ａｒｃ）网络图来描述，
现金流优化目标 ，对项目中的现金流入与现金流出进行管理
箭线代表活动，节点代表事件，活动发生的现金流都按一定折现
和优化，保持现金流出与现金流入之间最佳结构关系，实现现金
率折算到项目开始时。
净收入的最大化显得尤为重要，能有效规避项目风险，并使企业 （２）活动具有资源约束和优先约束，执行模式一旦选定便
收益最大化，在实际应用中具有重要意义。 不能更改，且具有非抢占式的特性。每种资源的可获得量及单
传统ＲＣＰＳＰ已被证明是ＮＰ－ｈａｒｄ问题，本文根据施工实际
在调度时还必须考虑每个活动有多种可执行模式，即多模式资
收稿日期：２００８—０９—１５。黄少荣，讲师，主研领域：进化算法和人
源约束调度问题ＭＭＲＣＰＳＰ，它比ＲＣＰＳＰ更加复杂，不仅要选择
工智能。
２７６
位成本为已知。
计算机应用与软件 ２０１０丘
２．２ 改进ＰＳｏ
ＰＳＯ算法的本质是利用当前位置、全局极值和个体极值三
（３）现金流指项目各活动发生的现金流人和现金流出。现
金流入包括项目开工时业主对承包商的预付款、业主在支付节
个信息，指导粒子下一步迭代位置。其个体充分利用自身经验
和群体经验调整自身的状态是ＰＳＯ算法具有优异特性的关键。
粒子可以从多种形式从其个体极值和全局极值中获得更新信
息，传统的速度一位移更新模型仅为符合此优化原理的具体实现
之一，反映粒子所代表的解在连续空间内，跟随个体极值以及全
局极值以矢量运算的形式进行更新，仅适合于处理连续优化问
题。对于离散优化问题，由于解空间是离散点的集合，利用ＰＳＯ
点按一定比例支付与完成进度成正比的工程款、项目提前完工
获得的奖金 现金流出包括各种资源费用、直接费用、间接费
用、延迟完工的罚金等。
１．２模型
设ｃ 为活动（ｉ，Ｊ）的现金流，非负整数ｔ 为该活动的开始
执行时间，参考文献［３，４ 中的模型，建立如下非线性规划
模型：
ｍａｘＮＰＶ＝∑ＣＦｉ
ｌ
￣ｅｘｐ（一ｓｔ ） （１）
＝
Ｓ．ｔ．
ｌＩ２，…， （２）
＝１，２，…，Ｖ ＝１，２，…，Ｋ
ｌ ４
∑￡≤∑（
Ｅ ｆ ｔ
￡一∑ ）
Ｒ １
＝１ ２一，Ｎ （３）
ｉ Ｅ ｎ Ｓ（ｎ
式（１）表示最大化项目净现值， 为折现率；式（２）表示资
源约束，即项目执行中，正在执行的活动的各种资源的使用量不
能超过其最大使用限额。』４ 表示在时期ｔ时正在进行的活动集
合，Ｖ为资源种类数，ｒ 为活动（ｉ√）用模式ｋ执行时单位工期所
需资源 的数量；式（３）表示优先关系约束：事件 的前趋活动
（ｉ， ）必须在事件 的后继活动（ ，１）开始之前完成， 为活动
（ｉ， ）以模式 执行时的活动工期，［Ｅ ，Ｌ ，］为活动（ｉ，，）的时
间窗
２基本粒子群算法及其改进
２．１基本ＰＳＯ
ＰＳ０算法首先初始化一群随机粒子，然后通过迭代找到最
优解。在每一次迭代中，粒子通过跟踪两个“极值”即个体极值
和全局极值来更新自己的速度与位置。假设ｍ个粒子组成一
个种群并在Ｄ维空间搜索，第ｉ个粒子在第ｔ代的位置表示为
一
个Ｄ维的向量 （ｔ）＝（ ， ，…， ∞），飞翔速度为 （ｔ）＝
（ ，…， 。），粒子本身历史最佳位置为Ｐ （ｔ）＝（Ｐ Ｐ ，…，
Ｐ 。），群体历史最佳位置为Ｐ （ｔ）＝（Ｐ Ｐ ，…，Ｐ Ｄ）。ＰＳＯ算
法迭代公式如下：
（ｔ＋１）＝ × （ｔ）＋Ｃ】×ｒｌ×（Ｐ （ｔ）～ （ｔ））＋
ｃ２×１＂２ ｘ（Ｐ （ｔ）一 （ｔ）） （４）
（ｔ＋１）＝ （ｔ）＋ （ｔ＋１） （５）
其中， 为惯性权重，ｃ 和ｃ：为加速系数， 和ｒ２是两个独立的
介于Ｅｏ，１］之间的随机数，ｔ为进化代数。式（４）第一部分为粒
子先前行为的惯性；第二部分为“认知”部分，表示粒子本身的
思考；第三部分为“社会”部分，表示粒子间的信息共享与相互
合作。
ＰＳＯ保留了基于种群的全局搜索策略，其特有的记忆可以
动态地跟踪当前的搜索情况来调整下一步的搜索策略，是一种
更高效的并行搜索算法，已成功应用于函数优化、多目标优化、
动态优化、神经网络训练等领域，但大部分应用都是基于传统的
速度一位移模型中，在解决离散问题时很难取得突破。
进行优化时不能直接移植传统模型，必须对问题进行变形，或者
修正速度和位置更新公式 。
ＭＭＲＣＰＳＰ现金流优化问题，若按传统ＰＳＯ模型，其速度难
以表达，因此需对公式进行变形。ＰＳＯ的关键在于确定粒子的
更新方式以及粒子的局部搜索和随机搜索方法，参照遗传算法
的基本思想，由交叉和变异完成粒子位置的更新 ：把公式（４）
中的６０× （ ）项看作变异操作，即随机搜索，ｃ ×ｒ。×（Ｐ （ｔ）一
（ｔ））＋Ｃ：×ｒ：×（Ｐ （ｔ）一 （ｔ））项看作交叉操作，即粒子与全
局极值和个体极值的信息交换。
引入遗传操作的粒子群算法称混合粒子群算法ＨＰＳ０（Ｈｙ—
ｂｒｉｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ），主要方法为：每一代中，每个粒
子先与全局极值交叉，再与个体极值交叉来产生更接近最优解
的新位置，并加入变异操作以增加解的多样性。该算法既克服
了ＰＳＯ在解决上述模型中速度难以表达的缺点，又结合了遗传
算法简单通用、鲁棒性强、适用于并行处理等优点．并且交叉操
作直接从全局极值和个体极值中获得更新信息，有效提高解的
质量，变异操作又能提高解的多样性，能更好地解决ＭＭＲＣＰＳＰ
现金流优化问题。
３ 求解ＭＭＲＣＰｓＰ现金流优化模型的混合粒
子群算法
３．１编码及初始化
传统粒子群算法中，粒子的位置和速度均以连续参数的形
式表示，限制了粒子群算法在离散优化领域的应用。本文针对
这一问题，对种群进行初始化时借鉴遗传算法中解的编码设计，
提出了一种采用基于时间序列的整数编码方式。
Ｓｔｅｐｌ对活动的执行模式进行编码，活动用自然数（Ｏ－－Ｍ
＋１）表示，自然数ｍ表示第ｍ个活动（０、Ｍ＋１表示虚拟活
动），每个活动有ｋ种执行模式，由于执行模式是以字符表示，在
对其进行编码时，依据顺序对每个活动的每种模式进行编码，第
１活动的第１种执行模式用１表示，第２种模式用２表示，…，第
ｋ种模式用ｋ表示；第２个活动的第１种执行模式用ｋ＋１表示，
第２种执行模式用ｋ＋２表示，…；第ｍ个活动的第ｋ种执行模
式用ｍｋ表示。
Ｓｔｅｐ２在未分配资源的活动中选择没有紧前活动或其紧
前活动都已经分配资源的活动，组成候选集合，如果候选集合为
空，则转Ｓｔｅｐ４；
Ｓｔｅｐ３从候选集合中随机选择一个候选模式，为其安排开
始的时间；其最早开始的时间为其所有紧前活动中最晚结束的
时间，如果在其持续的时段内所剩的资源不能满足该活动，则改
变该活动的实施模式或者将其开始时间后移，直到满足资源约
第３期
束条件，转Ｓｔｅｐ２；
Ｓｔｅｐ４结束。
黄少荣：基于混合粒子群优化算法的现金流优化
最后输出全局极值ｇ蛔 和全局极值位置Ｐ 。
２７７
从算法流程可以看出，相对于遗传算法中染色体互相共享信
息，整个种群比较均匀地向最优区域移动比较，混合ＰＳＯ中的粒 重复此过程，即可生成初始种群，每个粒子位置由一系列包
含了活动、执行模式、开工期三方面信息的模式代码组成，表示
一
个可行调度。
子直接从全局极值和个体极值获得更新信息，整个搜索过程是一
种单向的信息流动机制，其目的性更强，效率更高，对解的改进影
响更大，所有粒子将更快地收敛到最优解。而且，避免了大量冗
３．２适应值函数
由于优化目标是最大化项目现金流净现值，故直接以ＮＰＶ
的计算公式作为适应值函数，适应值越大，整个项目的净现值越
大，效益越好。适应值设定如下：
Ｍ
余的更新操作，减少寻优迭代次数，提高了算法效率 。
传统粒子群算法中涉及到的速度更新的参数虽然只有三个：
惯性权重 ，加速系数ｃ 和ｃ：，但这些参数的最优取值组合的选
择非常困难，有时微小的差别就能带来巨大的结果差异，尤其对
Ｆｉｔｎｅｓｓ（ ）＝∑ＣＦｉｉｅｘｐ（ａｔ ） （６）
Ｉ ｌ
３．３粒子的更新
粒子通过与全局极值和个体极值交叉来获得更新信息，这
种单向流动的目的性很强，为防止算法早熟，结果落人局部最
优，在算法中加入变异操作，让与全局极值和个体极值分别交叉
后产生的新粒子按一定概率进行变异，并把变异前后的粒子按
适应值大小进行择优保留。通过交叉变异操作，粒子位置得到
更新。
１）交叉操作采用了单点次序交叉，具体方法如下：
（１）粒子ｐ１和ｐ２交叉，随机产生一个交叉点。
（２）保留ｐｌ交叉点前的模式，并依序遍历ｐ２中的模式，如
果该模式不与ｐ１中保留的模式属于同一个活动，则保留，否则
删除，然后将剩余的模式按顺序插入ｐ１交叉点后的位置，产生
新粒子口１。
（３）同理，产生新粒子ｑ２。
由于产生的新粒子在交叉点前的模式编码是满足资源约束
和优先约束的，交叉点后的模式编码是父粒子中的一部分且其
优先次序保持不变，也是满足资源约束和优先约束的，因此新粒
子一般能满足资源约束和优先约束。
２）变异操作采用整体变异方式，以变异率决定某个粒子
是否执行变异，若执行，按３．１节编码方式重新随机生成新粒
子。由于是直接对各个活动的各种可执行模式进行编码，每个
模式编码实际上包含了活动、执行模式以及开工期三方面的信
息，而且满足资源约束和优先约束。
３．４算法流程
设定迭代次数为 ，变异率Ｗ，随机产生ｎ个粒子。
根据公式（６）计算每个粒子的适应值 ，设置当前适应值
为个体极值Ｐ ，当前位置为个体极值位置ｐ；，根据各个粒子的
适应值找出全局极值ｇ 和全局极值位置 。
Ｗｈｉｌｅ（迭代次数＜Ｔ）ｄｏ
ｆｏｒｉ＝１：Ｔ
ｆ０ｒｊ＝１：ｎ
第ｊ个粒子位置Ｘ０（ｊ）与Ｐ 交叉，记为Ｘ １（ｊ）。
Ｘ １（ｊ）与Ｐｉ交叉，记为Ｘ １（ｊ）。
对Ｘ” （ｊ）按一定概率进行变异，选取适应值高的粒子位置记为
Ｘ１（ｊ）。
根据当前位置计算适应值ｆ．。
如果ｆ （ｊ）＞Ｐｉ （ｊ），则ＰＩｂ。 （ｊ）＝ｆ１（ｊ），Ｐ （ｊ）：Ｘ１（ｊ）。
Ｅｎｄ
根据各个粒子的个体极值Ｐ ，找出全局极值ｇ 和全局极值位
置Ｐｇ。
Ｘ０ Ｘｌ。
Ｅｎｄ
于复杂、高维函数模型，通过传统ＰＳＯ算法很难获得最优解，容易
陷入局部最优。本文提出的ＨＰＳＯ算法，由于粒子通过交叉方式
直接从全局极值和个体极值获得更新信息，使算法的可调参数减
少，避免了 ，ｃ，，ｃ 这三个参数的组合选择，更容易实现。
４实例及分析
４．１ 实例
某项目包括９个事件、１２个活动，其网络图如图１所示，项
目中的每个活动均有两种可执行模式，不同模式下各活动的信
息如表１所示。项目总价为３００００元，项目开工业主即支付
２０％总价作为预付款，在支付节点业主按７０％的比例支付已经
完工的活动工程款，项目完工时结清余款。项目工期为３０±５
天，每提前（推后）一天完成按项目总价的１％（１．５％）进行奖励
或惩罚。资源单位工期限定为１Ｏ，单价为１２元，单位工期发生
的间接费用为１２０元，所有现金流以０．０２的折现率折现到项目
开工时，现要求在不同支付节点下（支付１）对项目作出合理调
度，以使净收益最大。
图１项目ＡｏＡ网络图
表１ 多模式下各活动的现金流、工期以及资源需求量
常规模式（ｎ） 加急模式（ｃ）
活动号 工程款
工期 直接费用 资源／工期 工期 直接费用 资源／工期
１（１，２） ｌｏｏＯ ５ ５ｏｏ ４ ４ ５５０ ５
２（１，３） ８０ｏ ４ ４ｏｏ ５ ３ ４８０ ４
３（２，４） ｌ５００ ４ ４５０ ５ ２ ５０ｏ ３
４（２，５） ７０ｏ ３ ３０ｏ ４ ２ ３５０ ５
５（３，５） １２０ｏ ６ ６８０ ３ ４ ７５０ ３
６（３，６） ｌ６００ ６ ６５０ ３ ４ ７ｏｏ ４
７（４，７） １７ｏｏ ７ ７２０ ４ ５ ８５０ ４
８（４，８） ２５０ｏ ５ ６０ｏ ３ ４ ６５０ ５
９（５，９） ｌ２ｏｏ ４ ３０ｏ ３ ３ ３５０ ４
１０（６，８） ３５０ｏ １０ ８００ ７ ８ ６００ ８
１１（７，９） ９０ｏ ３ ２３０ ２ ２ ２８０ ３
１２（８，９） ２３００ ８ ６５０ ３ ６ ７５０ ４
２７８
４．２参数设置
计算机应用与软件 ２０１０丘
用到更切合实际工程的多模式、带基于进度的多节点支付和带
奖惩机制并以净现值为优化目标的资源约束项目调度问题中，
是对ＰＳＯ算法应用领域的一个成功拓展，为ＰＳＯ在离散优化领
域的应用提供了一种新的思路。
本文提出的ＨＰＳＯ算法操作简单，可调参数少，方便调试。
根据优化模型及上述具体问题，测试后最佳参数设置为：粒子数
为２０，迭代次数为１００，变异概率为０．１。算法用ＶＣ语言编程
实现，程序运行环境为个人ＰＣ。
４．３算法结果
在上述实例运行ＨＰＳＯ，运算结果如表２所示。
表２不同支付事件下的项目净收益（ＮＰＶ）
支付节点 最优调度（①活动②模式③开工期）
①１—２—６—５—３—８—１０—７—１２—４—９—１１
②ｅ—ｎ—ｃ—ｃ—ｎ—ｎ—ｃ—ｃ—ｃ—ｎ～ｃ—ｎ
（３，７）
③１—１—５—５—５—９—９—１４—１７—１７—２０—２０
ＮＰＶ：１３５０５．７（项目工期２２天）
①１—２—６—３—８—４—１０—５—７—１２—９—１１
②Ｃ—ｎ—ｅ—ｃ—ｎ—ｃ—ｃ—ｃ—ｃ—ｃ～ｎ—ｃ
（２，４，６）
③１—１—５—５—７—７—９—１２—１６—１７—１７—２１
ＮＰＶ＝１３７５６（项目工期２２天）
４．４结果分析
（１）从表２可以看出，ＨＰＳＯ算法能有效地解决ＭＭＲＣＰＳＰ
现金流优化问题，做出合理、高效、实用的项目调度。表中ＮＰＶ
值反映出不同的支付节点带来不同的净现值，～般地，支付节点
越多越靠前，现金流人越多越快，项目净现值越大。
（２）ＨＰＳＯ算法在最大化项目净现值前提下能尽量缩短工
期，提高项目施工效率，达到多目标优化的目的。而且，现金流
优化模型弹性大，可灵活设置活动数目、执行模式、资源种类及
限制、不同的支付节点等，适用于现实复杂项目调度。
（３）对于较大规模的算例，混合粒子群算法同样表现了良
好的收敛性能。将ＨＰＳＯ与简单遗传算法（ＧＡ）两种方法应用
于包含１８个事件、３Ｏ个活动的大型项目上测试，两种方法均运
行ｌ０次，并将结果做比较，结果如表３所示。由此可见，ＨＰＳＯ
在解决现金流优化问题上性能具有优越性，算法具有更快的收
敛速度，优化结果也更接近实际的全局最优。
表３ Ｉ－ＩＰＳＯ／ＧＡ算法性能对比
方法 找到最优解次数 最优解平均误差 找到最优解平均代数
ＧＡ ５７ ７．８％ ４７
ＨＰＳ０ ８６ ３．４％ ２３
５结论
ＰＳＯ算法作为一种新兴算法，尚缺乏数学理论支撑，仅适合
于连续问题的优化，难以应用于离散领域的优化。对算法本身
需要加强其数学理论研究和不断拓宽其应用领域的广度和深
度。通过与遗传算法、蚁群算法、模拟退火、人工神经网络及模
糊逻辑系统等其它人工智算法渗透结合，将是提升算法性能和
拓宽应用的主要途径。本文从ＰＳＯ的优化原理出发，引入遗传
算法的交叉和变异操作，并把改进后的混合粒子群优化算法应
参考文献
［１］Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ．Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／ＩＥＥＥ Ｉｎｔｅｒ－
ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ，ｐｅｒｔｈ，Ａｕｓｔｒａｌｉａ，１９９５：１９４２
—
１９４８．
［２］Ｒｕｓｓｅｌｌ Ａ Ｈ＿Ｃａｓｈ ｆｌｏｗｓ ｉｎ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９７０，
１６（４）：３５７—３７３．
［３］张静文，徐渝，何正文．多模式资源约束型折现流时间一费用权衡项
目进度［Ｊ］．系统工程，２００５，２３（５）：１７～２１．
［４］张颖，刘艳秋，汪定伟，等．ＲＣＰＳＰ中现金流优化问题的ＨＧＡ方法
［Ｊ］．基础自动化，２００１，８（４）：５—７．
［５］彭传勇，高亮，邵新宇，等．求解作业车间调度问题的广义粒子群优
化算法［Ｊ］．计算机集成制造系统，２００６，１２（６）：９１１—９２３．
［６］高尚，杨静宇．群智能算法及其应用［Ｍ］．中国水利水电出版社，
２００６．８９—９０．
（上接第２６７页）
终端通过ａｓｔｅｒｉｓｋ建立会话并结束会话的过程，发起会话的ＳＩＰ
终端Ａ和应答会话的ＳＩＰ终端Ｂ的ＪＰ地址分别为１９２．１６８．１．
１１２和１９２．１６８．１．１１０，ａｓｔｅｒｉｓｋ服务器的ＩＰ地址为１９２．１６８．１．
２Ｏ。由Ｅｔｈｅｒｅａｌ捕获的ＳＩＰ消息可以看到，Ａ发送ＩＮＶＩＴＥ请求
消息发起呼叫，Ｂ接收到后回复２００ ＯＫ消息，Ａ再发送ＡＣＫ请
求消息，这个消息流程完全符合ＲＦＣ３２６１的ＳＩＰ协议规范。同
时在３２路ＳＩＰ会话同时进行的网络负载下进行１００次测试呼
叫，成功率为１００％。
Ｅ１１ ｌｓ｛ｐ …… 口・
图５ ＳＩＰ会话过程网络监控图
５ 结论
ＳＩＰ协议的不断发展和完善，使其越来越受到关注。本文
设计的系统实现了具有基本呼叫功能的ＳＩＰ终端，测试结果表
明系统运行稳定且高效，并且易于扩展实现事件通知机制和参
考方法等ＳＩＰ扩展方法以支持会议终端功能，可以广泛应用于
许多多媒体会议系统中 ］。
参考文献
［１］Ｒｏｓｅｎｂｅｒｇ Ｊ，Ｓｃｈｕｌｚｒｉｎｎｅ Ｈ．Ｓｅｓｓｉｏｎ Ｉｎｉｔｉａｔｉｏｎ Ｐｒｏｔｏｃｏｌ［Ｓ］．ＲＦＣ ３２６１，
２ｏｏ２．
［２］沈鑫剡．多媒体传输网络与ＶＯＩＰ系统设计［Ｍ］．北京：人民邮电
出版社，２００５．
［３］熊华，刘风新，潘小莉．Ｗｉｎｄｏｗｓ动态链接库原理分析及其应用
［Ｊ］．北京：北京化工大学学报，２００４．
［４］Ｄａｎｉｅｌ Ｃｏｌｌｉｎｓ．ＶｏｌＰ技术与应用［Ｍ］．北京：人民邮电出版
社．２００３．