【算法】一种用于云计算的SPSO算法
算法：
一种基于集合的离散粒子群算法，论文链接
本文前半部分以翻译为主，后半部分涉及算法直接给出算法思路。蓝色部分为关键字。
面向问题：
Quality of Service (QoS)：服务质量问题
cloud workflow scheduling problem：云工作流调度问题
deadline constraint：期限限制问题
the budget constraint：代价限制问题
the reliability constraint：实际限制问题
1.简介
cloud computing has emerged as a powerful and promising next-generation computing paradigm.
云计算成为最强大、也最有前景的下一代计算范式。
a Cloud is defined as a parallel and distributed system which is composed of a collection of interconnected and virtualized computing resources.
云的定义：由相互连接、虚拟化的计算资源集合构成的并行分布式系统。
complex scientific computing applications are managed in a workflow model. A workflow is defined as a collection of atomic tasks that are processed in a specific order
to accomplish a complicated goal
工作流定义：是复杂计算任务的载体，是按照一定顺序执行的原子任务的集合。
To manage a scientific workflow, the workflow management system (WfMS) needs to schedule and execute the workflow in an efficient way to satisfy the requirements of scientists.
流管理系统 (WfMS)：可以高效地进行工作流的管理、调度和执行。
A workflow is described by a directed acyclic graph (DAG). ...However, most of these approaches only consider a single QoS parameter, namely the execution time of the workflow.
工作流通常表示为有向无环图，但是多数图模型只考虑流运行时间这一单一因素。
As the cloud computing paradigm enables the WfMS to consider the different QoS requirements of users, the above traditional workflow scheduling methods become unsuitable for the new paradigm. this paper intends to develop a XXX particle swarm optimization approach.
云计算范式的引入，让流管理系统可以考虑用户的不同QoS需求。于是传统流调度方式不再适用。因此本文针对性地提出了一种新的调度策略——XXX粒子群算法。
The rest of this paper is organized as follows. ...
文章组织结构：作者在第二部分提出了工作流的云调度模型，第三部分复习了一下PSO和SPSO算法背景。第四部分提出自己的算法，第五部分进行对比实现。
2. 问题构造
we consider three types of QoS parameters, i.e., the cost , the execution time , and the service’s historical reliability .
引入QoS问题的三种参数，比如，代价、运行时间、历史稳定性。
Deadline constraint: the execution time of the workflow must be not larger than a user-defined variable Deadline.
Budget constraint: the total cost of the service instances consumed by the workflow must be not larger than a user-defined variable Budget.
Reliability constraint: the historical reliability of the service instances reserved for the workflow must be not smaller than a user-define variable MinReliability.
引入三种限制条件：截止时间限制、代价限制、可靠性限制。限制条件对应的是三个优化目标。
3. S-PSO背景
参考作者之前的研究：论文链接
Many combinatorial optimization problems (COPs) can be represented by “find from a set E a subset X that satisfies some constraints O: and optimizes the objective function f”.
许多组合优化问题可以表示为“ 从集合E中找到一个子集X，满足约束条件O，然后去优化目标函数f”
4. S-PSO算法步骤
(1) 定义粒子位置集合：X=(X1,X2,...,Xn)，符合条件O的位置被定义为可用。
(2) 定义粒子速度集合：V=(V1,V2,...,Vn)，其中，速度Vi=e/p(e), e属于Ej （Ej表示问题的第j个维度）
(3) 系数*（速度-速度）算子表示为：
(4) “位置-位置” 的算子表示为：A - B = {e | e属于 A ，且e 不属于 B}
(5) 系数*（位置-位置）算子定义为：
(6) "速度 + 速度" 算子定义为：
位置更新规则具体是：
第一步：把当前粒子的更新速度中的每个维度提取出来，构成明确集：
第二步：当前粒子i从空集开始，从明确集中提取元素叠加到自身。
第三步：如果明确集中没有元素，且构造没有完成，那么粒子选择上一个时间的位置作为当前位置。
第四步：如果构造还没完成，且之前的位置不可用，那么粒子选择其他可用的位置替代，最终得到新位置。
以上是基本的SPSO。本文章中，作者提出新的SCLPSO，规则可表示为：
算法步骤介绍完毕。补充一张形象的图。
接下来是应用细节，可查阅原论文。