马尔可夫链模型学位论文

随着信息技术的飞速发展，软件开发规模及开发队伍越来越庞大，个人单打独斗的作坊式开发方式已经越来越不适应形势发展的需要。各软件企业都在积极将软件项目管理引入到开发活动中，怎样对软件项目进行有效的管理就成为一个需要研究的课题。而在软件项目管理过程中，项目进度的计划和控制管理是决定项目能否顺利实施的关键内容。本文对软件项目计划控制过程中的具体方法进行系统研究，为软件企业实施软件项目管理提供参考。 本文运用动态规划的思想和网络计划的方法，利用马尔可夫链模型进行软件项目进度预测，包括并行进度的预测。并结合参与项目开发课题的实际调研资料，对软件开发项目中的计划和控制应用进行研究，构建了一个并行的IT项目进度马尔可夫链预测模型。 本文首先介绍了论文的选题背景及依据、研究现状及意义、研究内容及框架。接着，综合运用项目管理、软件工程、软件项目管理方面的知识，对软件开发项目中的进度计划管理和进度控制管理进行了系统研究，重点分析了计划管理中的工作量估算、工作结构分解、制定计划的三种常用技术(Gantt，PERT，CPM)，并对软件项目进度控制中的常用技术(里程碑进度、人为设定活动进度、工作单元进展和挣值法)进行分析...

先直白得讲性质： 当前的状态只和上一时刻有关，在上一时刻之前的任何状态都和我无关。我们称其 符合 马尔可夫性质。

下面是理论化的阐述： 设{X(t), t ∈ T}是一个 随机过程 ，E为其状态空间，若对于任意的t1

马尔可夫链 是指具有马尔可夫性质的随机过程。在过程中，在给定当前信息的情况下，过去的信息状态对于预测将来 状态 是无关的。

例子： 在今天这个时间点而言，过去的股价走势对我预测未来的股价是毫无帮助的。 PS：上面马尔可夫链中提到的 状态 ，在本例指的是 股价 。

在马尔可夫链的每一步，系统根据 概率分布 ，可以从一个状态变成另外一个状态，也可以保持当前状态不变。状态的改变叫做 转移 ，状态改变的相关概率叫做 转移概率 。

例子： 当前时间状态下的股价，可以转变成下一时刻的股价，股价的转变即 状态的改变 。这个状态现在可以上升(股价提高)，状态也可以下降。我可以根据当前股票的价格去决定下一刻股价上升、下降、不变的概率。这种股价变动的概率称为 状态转移概率 。

马尔可夫链中的 三元素是 ：状态空间S、转移概率矩阵P、初始概率分布π。

1、状态空间S - 例： S是一个集合，包含所有的状态 S 股价 ={高，中，低} ；

2、初始概率分布π - 例： 股价刚发行的时候有一个初始价格，我们认为初始价格为高的概率为50%，初始价格为中的概率是30%，初始价格为低的概率是20%。我们记股票价格的初始概率分布为：π=(，，)；对应状态：(高、中、低)； 初始概率分布是一个向量 ，如果有n个状态，π是n维向量。

3、转移概率矩阵P - 例： 现在有个股价为中，下一个时刻状态转变的可能性有三种，中→高、中→低、中→中；将三种转变的概率。此外当前时刻也有股票的价格属于低，对应的转变可能包括低→高、低→低、低→中；即每种状态都有可能转变成其他的状态，若一共有n个状态，形成的 转移概率矩阵 应该是n×n阶矩阵。这里需要注意的是，股价从高→低，和低→高的概率是不同的。

设将天气状态分为晴、阴、雨三种状态，假定某天的天气状态只和上一天的天气状态有关，状态使用1(晴)、2(阴)、3(雨)表示，转移概率矩阵P如下：

第n+1天天气状态为j的概率为：

因此，矩阵P即为条件概率转移矩阵。矩阵P的第i行元素表示，在上一个状态为i的时候的分布概率，即每行元素的和必须为1。

隐马尔可夫模型(Hidden Markov Model, HMM)是一种统计模型，在语音识别、行为识别、NLP、故障诊断等领域具有高效的性能。

HMM是关于时序的概率模型，描述一个含有未知参数的马尔可夫链所生成的不可观测的状态随机序列，再由各个状态生成观测随机序列的过程。

HMM是一个双重随机过程---具有一定状态的隐马尔可夫链和随机的观测序列。

HMM随机生成的状态随机序列被称为状态序列；每个状态生成一个观测，由此产生的观测随机序列，被称为观测序列。

思考： z1,z2...,zn是 不可观测的状态，x1,x2,...xn是 可观测到的序列 ；不可观测的状态觉得可观测序列的值(z的取值决定x的取值)；

1、在 z1、z2 不可观测 的情况下，x1和z2独立吗？x1和x2独立吗？

回答： 这个问题可以回顾之前的 贝叶斯网络 来理解。 首先z1，z2都是离散的值，但x1的值可能是离散的也可能是连续的。比如z是天气情况，每天天气的改变是离散的。x是因为天气而改变的一些其他状态，比如x=(地面是否潮湿、路上行人数量、雨伞销售数量...)； 在z1和z2不可观测的情况下，x1和z2不独立，x1和x2也是不独立的。

2、 在 z1、z2可观测 的情况下，x1和z2独立吗？x1和x2独立吗？

回答： 在z1和z2可观测的情况下，因为x1和z2的取值只和z1有关，所以就独立了。同样在给定了z1和z2的情况下，x1和x2也独立。

请回顾贝叶斯网络中的独立性问题来思考这个问题。 04 贝叶斯算法 - 贝叶斯网络

回顾： 一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，可以是可观察到的变量，或隐变量，未知参数等等。连接两个节点之间的箭头代表两个随机变量之间的因果关系(也就是这两个随机变量之间非条件独立)；如果两个节点间以一个单箭头连接在一起，表示其中一个节点是“因”，另外一个节点是“果”，从而两节点之间就会产生一个条件概率值。

PS：每个节点在给定其直接前驱的时候，条件独立于其非后继。

HMM 由隐含状态S、可观测状态O、初始状态概率矩阵π、隐含状态转移概率矩阵A、可观测值转移矩阵B(又称为混淆矩阵，Confusion Matrix)；

π和A决定了状态序列，B决定观测序列，因此HMM可以使用三元符号表示，称为HMM的三元素：

S可以统计历史出现的所有状态； 初始概率分布π，统计S中各个状态各自出现的概率作为我们的初始概率分布π向量值；

S是所有可能的状态集合，O是所有可能的观测集合：

I是长度为T的状态序列，Q是对应的观测序列：

S={下雨，阴天，晴天}；O={地上干，地上湿} I = {晴，雨，雨，阴，晴，阴} Q={干，湿，湿，湿，干，干}

A是隐含状态转移概率矩阵:

其中aij是在时刻t处于状态si的条件下时刻t+1转移到状态sj的概率。 a 晴雨 = 某天是晴天条件下，下一天是雨天的概率。 （某一时刻→下一时刻）

B是可观测值转移概率矩阵:

其中bij是在时刻t处于状态si的条件下生成观测值oj的概率。 b 晴干 = 某天是晴天条件下，某天是地是干的的概率。 （同一时刻）

π是初始状态概率向量:

其中πi是在时刻t=1处于状态si的概率。 π 晴 = 初始第一天是晴天的概率； π 雨 = 初始第一天是雨天的概率；

p(i t | .....) 表示在从 t-1时刻的观测值q t-1 ，一直到第1时刻观测值q1 的条件下，在第t时刻发生状态的概率。

性质1： 最终分析结果发现，在第t时刻发生状态的概率it只和t-1时刻有关。 性质2： 第t时刻的观测值qt只和第t时刻的状态it有关。

假设有三个盒子，编号为1,2,3；每个盒子都装有黑白两种颜色的小球，球的比例。如下：

按照下列规则的方式进行有放回的抽取小球，得到球颜色的观测序列： 1、按照π的概率选择一个盒子，从盒子中随机抽取出一个球，记录颜色后放回盒子中； 2、按照某种条件概率选择新的盒子，重复该操作； 3、最终得到观测序列：“白黑白白黑”

例如： 每次抽盒子按一定的概率来抽，也可以理解成随机抽。 第1次抽了1号盒子①，第2次抽了3号盒子③，第3次抽了2号盒子②.... ； 最终如下： ①→③→②→②→③ 状态值 白→黑→白→白→黑 观测值

1、 状态集合： S={盒子1，盒子2，盒子3} 2、 观测集合： O={白，黑} 3、 状态序列和观测序列的长度 T=5 (我抽了5次) 4、 初始概率分布： π 表示初次抽时，抽到1盒子的概率是，抽到2盒子的概率是，抽到3盒子的概率是。 5、 状态转移概率矩阵 A：a11= 表示当前我抽到1盒子，下次还抽到1盒子的概率是； 6、 观测概率矩阵 B：如最初的图，b11=第一个盒子抽到白球概率，b12=第一个盒子抽到黑球概率;

在给定参数π、A、B的时候，得到观测序列为“白黑白白黑”的概率是多少?

这个时候，我们不知道隐含条件，即不知道状态值：①→③→②→②→③ ； 我们如何根据π、A、B求出测序列为“白黑白白黑”的概率？

02 隐马尔可夫模型 - HMM的三个问题 - 概率计算、学习、预测

并行遗传算法及其应用1、遗传算法（GA）概述GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。生物遗传物质的主要载体是染色体，在GA中同样将问题的求解表示成“染色体Chromosome”，通常是二进制字符串表示，其本身不一定是解。首先，随机产生一定数据的初始染色体，这些随机产生的染色体组成一个种群（Population），种群中染色体的数目称为种群的大小或者种群规模。第二：用适值度函数来评价每一个染色体的优劣，即染色体对环境的适应程度，用来作为以后遗传操作的依据。第三：进行选择（Selection），选择过程的目的是为了从当前种群中选出优良的染色体，通过选择过程，产生一个新的种群。第四：对这个新的种群进行交叉操作，变异操作。交叉、变异操作的目的是挖掘种群中个体的多样性，避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。GA通常包含5个基本要素：1、参数编码：GA是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常选择二进制编码。2、初始种群设定：GA随机产生一个由N个染色体组成的初始种群（Population），也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3、适值度函数的设定：适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4、遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5、控制参数设定：在GA的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率，进化代数等。GA的优点是擅长全局搜索，一般来说，对于中小规模的应用问题，能够在许可的范围内获得满意解，对于大规模或超大规模的多变量求解任务则性能较差。另外，GA本身不要求对优化问题的性质做一些深入的数学分析，从而对那些不太熟悉数学理论和算法的使用者来说，无疑是方便的。2、遗传算法的运行机理：对GA运行机理的解释有两类: 一是传统的模式理论；二是1990 年以后发展起来的有限状态马尔可夫链模型。（1）模式理论：由Holland创建，主要包括模式定理，隐并行性原理和积木块假说三部分。模式是可行域中某些特定位取固定值的所有编码的集合。模式理论认为遗传算法实质上是模式的运算，编码的字母表越短，算法处理一代种群时隐含处理的模式就越多。当算法采用二进制编码时，效率最高，处理规模为N的一代种群时，可同时处理O(N3)个模式。遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性。模式理论还指出，目标函数通常满足积木块假说，即阶数高，长度长，平均适应度高的模式可以由阶数低，长度短，平均适应度高的模式(积木块)在遗传算子的作用下，接合而生成。而不满足积木块假说的优化问题被称为问题(deceptive problem)。模式理论为遗传算法构造了一条通过在种群中不断积累、拼接积木块以达到全局最优解的寻优之路。但近十多年的研究，特别是实数编码遗传算法的广泛应用表明，上述理论与事实不符。（2）有限状态马尔可夫链模型：由于模式理论的种种缺陷，研究者开始尝试利用有限状态马尔可夫链模型研究遗传算法的运行过程。对于遗传算法可以解决的优化问题，问题的可行域都是由有限个点组成的，即便是参数可以连续取值的问题，实际上搜索空间也是以要求精度为单位的离散空间，因此遗传算法的实际运行过程可以用有限状态马尔可夫链的状态转移过程建模和描述。对于有 m 个可行解的目标函数和种群规模为N的遗传算法，N 个个体共有 种组合，相应的马尔可夫模型也有 个状态。实际优化问题的可行解数量 m 和种群规模 N 都十分可观，马尔可夫模型的状态数几乎为天文数字，因此利用精确的马尔可夫模型计算种群的状态分布是不可能的。为了换取模型的可执行性，必须对实际模型采取近似简化，保持算法的实际形态，通过对目标函数建模，简化目标函数结构实现模型的可执行性。遗传算法优化的过程，可以看作算法在循环过程中不断对可行域进行随机抽样，利用前面抽样的结果对目标点的概率分布进行估计，然后根据估计出的分布推算下一次的抽样点。马尔可夫模型认为遗传算法是通过对搜索空间不同区域的抽样，来估计不同区域的适应度，进而估计最优解存在于不同区域的概率，以调整算法对不同区域的抽样密度和搜索力度，进而不断提高对最优解估计的准确程度。可见，以邻域结构为依据划分等价类的马尔可夫模型更符合实际，对问题的抽象更能体现优化问题的本质。3、并行遗传算法（PGA）虽然在许多领域成功地应用遗传算法，通常能在合理的时间内找到满意解，但随着求解问题的复杂性及难度的增加，提高GA的运行速度便显得尤为突出，采用并行遗传算法（PGA）是提高搜索效率的方法之一。由于GA从种群出发，所以具有天然的并行处理特性，非常适合于在大规模并行计算机上实现，而大规模并行计算机的日益普及，为PGA奠定了物质基础。特别是GA中各个体适值计算可独立进行而彼此间无需任何通信，所以并行效率很高。实现PGA，不仅要把串行GA等价地变换成一种并行方案，更重要的是要将GA的结构修改成易于并行化实现的形式，形成并行种群模型。并行种群模型对传统GA的修改涉及到两个方面：一是要把串行GA的单一种群分成多个子种群，分而治之；二是要控制、管理子种群之间的信息交换。不同的分治方法产生不同的PGA结构。这种结构上的差异导致了不同的PGA模型：全局并行模型、粗粒度模型、细粒度模型和混合模型。3、1全局PGA模型该模型又称主从PGA模型，它是串行GA的一种直接并行化方案，在计算机上以master-slave编程模式实现。它只有一个种群，所有个体的适应度都根据整个种群的适应度计算，个体之间可以任意匹配，每个个体都有机会和其他个体杂交而竞争，因而在种群上所作的选择和匹配是全局的。对于这个模型有多种实现方法：第一种方法是仅仅对适值度函数计算进行并行处理；第二种方法是对遗传算子进行并行处理。全局模型易于实现，如果计算时间主要用在评价上，这是一种非常有效的并行化方法。它最大的优点是简单，保留了串行GA 的搜索行为，因而可直接应用GA 的理论来预测一个具体问题能否映射到并行GA上求解。对于适应度估值操作比其他遗传算子计算量大的多时，它是很有效的，并且不需要专门的计算机系统结构。3、2粗粒度PGA模型该模型又称分布式、MIMD、岛模式遗传算法模型，它是对经典GAs 结构的扩展。它将种群划分为多个子种群(又称区域)，每个区域独自运行一个GA。此时，区域选择取代了全局选择，配偶取自同一区域，子代与同一区域中的亲本竞争。除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。在粗粒度模型的研究中，要解决的重要问题是参数选择，包括：迁移拓扑、迁移率、迁移周期等。在种群划分成子种群(区域)后，要为种群指定某种迁移拓扑。迁移拓扑确定了区域之间个体的迁移路径，迁移拓扑与特定的并行机结构有着内在的对应关系，大多采用类似于给定并行处理机的互连拓扑。如果在顺序计算机上实现粗粒度模型，则可以考虑采用任意结构。拓扑结构是影响PGA 性能的重要方面，也是迁移成本的主要因素。区域之间的个体交换由两个参数控制：迁移率和迁移周期。迁移基本上可以采用与匹配选择和生存选择相同的策略，迁移率常以绝对数或以子种群大小的百分比形式给出，典型的迁移率是子种群数目的10%到20%之间。迁移周期决定了个体迁移的时间间隔，一般是隔几代(时期) 迁移一次，也可以在一代之后迁移。通常，迁移率越高，则迁移周期就越长。有的采用同步迁移方式，有的采用异步迁移方式。迁移选择负责选出迁移个体，通常选择一个或几个最优个体，有的采用适应度比例或者排列比例选择来选择迁移个体，也有采用随机选取和替换的。在大多数情况下,是把最差或者有限数目的最差个体替换掉.与迁移选择类似，可采用适应度比例或者排列比例选择，确定被替换的个体，以便对区域内部的较好个体产生选择压力。基于国内的现状，分布式PGA为国内PGA研究的主要方向。分布式PGA作为PGA的一种形式，一般实行粗粒度及全局级并行，各子种群间的相互关系较弱，主要靠一些几乎串行GA来加速搜索过程。采用分布式PGA求解问题的一般步骤为：（1）将一个大种群划分为一些小的子种群，子种群的数目与硬件环境有关；（2）对这些子种群独立的进行串行GA操作，经过一定周期后，从每个种群中选择一部分个体迁移到另外的子种群。对于个体迁移存在多种方法，第一种方法，在执行迁移操作时，每次从子种群中随机选择一部分染色体发送出去，接收的染色体数应该与发出的染色体相同。第二种方法，在执行迁移操作时，首先在每个子种群内只使用选择而不使用其它遗传算子繁殖一些后代，这些后代的数目与迁移数相同。然后再将这些后代的原子种群合并成一个大子种群并均匀随即地从该子种群中选择个体进行迁移。这样，待迁移后子种群的规模便又恢复到正常状态。而当子种群接收到从其他子种群迁移来的个体时则均匀随即地替换掉子种群内的个体。第三种方法，将其中一个子种群设置为中心子种群，其他子种群与中心子种群通信。中心子种群始终保持着整个种群中当前的最优个体，其他子种群通过“引进”中心子种群中的最优个体来引导其加快收敛速度，改善个体特征。3、3 细粒度PGA模型该模型又称领域模型或SIMD PGA模型，对传统GA作了修改。虽然细粒度模型也只有一个种群在进化，但在种群平面网格细胞上，将种群划分成了多个非常小的子种群(理想情况是每个处理单元上只有一个个体)，子种群之间具有极强的通信能力，便于优良解传播到整个种群。全局选择被领域选择取代，个体适应度的计算由局部领域中的个体决定，重组操作中的配偶出自同一领域，且子代同其同一领域的亲本竞争空间，即选择和重组只在网格中相邻个体之间进行。细粒度模型要解决的主要问题是领域结构和选择策略。领域结构既决定了种群中个体的空间位置，也确定了个体在种群中传播的路径。领域结构主要受特定并行计算机的内存结构和通信结构影响。领域拓扑确定一个个体的邻居，构成该个体的局部领域。通常，只有一个拓扑的直接领域才属于其局部领域，若把某个固定步数内所能到达的所有个体也包含在内，则可以扩大领域半径。在确定选择策略时，要考虑到选择压力的变化，而选择压力与领域结构有关。与全局匹配选择类似，局部匹配选择可以采用局部适应度比例、排列比例选择，以及随机行走选择。局部生存选择确定局部邻域中被替换的个体，如果子代自动替换邻域中心的那个个体，那么可以直接使用代替换作为局部生存策略。3、4 混合PGA模型该模型又称为多层并行PGA模型，它结合不同PGA模型的特性，不仅染色体竞争求取最优解，而且在GA结构上也引入了竞争以提供更好的环境便于进化。通常，混合PGA以层次结构组合，上层多采用粗粒度模型，下层既可采用粗粒度模型也可采用细粒度模型。或者，种群可以按照粗粒度PGA模型分裂，迁移操作可以采用细粒度PGA模型。3、5 四种模型的比较就现有的研究结果来看，很难分出各模型的高低。在评价并行模型的差异时，有时还得深入到实现细节上，如问题的差异、种群大小、或者不同的局部搜索方法等。但有一个结论是肯定的：不采用全局并行模型，而采用粗粒度模型或者细粒度模型通常能获得更好的性能。粗粒度模型与细粒度模型孰优孰劣，尚是一个未知数。目前，以粗粒度模型最为流行，因为一是其实现较容易，只需在串行GA中增加迁移子例程，在并行计算机的节点上各自运行一个副本，并定期交换几个个体即可；二是在没有并行计算机时，也可在网络或单机系统上模拟实现。虽然并行GA能有效地求解许多困难的问题，也能在不同类型的并行计算机上有效地实现，但仍有一些基本的问题需要解决。种群大小可能既影响大多数GA的性能，也决定GA找到解所需时间的主要因素。在PGA中，另一个重要问题是如何降低通信开销，包括迁移率的确定，使得区域的行为象单个种群一样；确定通信拓扑，既能充分地组合优良解，又不导致过多的通信开销；能否找到一个最优的区域数等。另外，对不同的应用问题，混合模型难以设定基本GA的参数，其节点的结构是动态变化的，它比粗粒度和细粒度模型更具有一般性，算法更为复杂，实现代价更高。4、并行遗传算法的评价模型：并行遗传算法的性能主要体现在收敛速度和精度两个方面，它们除了与迁移策略有关，还与一些参数选取的合理性密切相关，如遗传代数、种群数目、种群规模、迁移率和迁移间隔。利用Amdahl定律评价并行遗传算法，即绝对加速比(speedup) = Ts/Tp，其中，Ts为串行遗传算法(单个处理器)的执行时间；Tp为并行遗传算法的执行时间。Amdahl定律适用于负载固定的情况，对于并行遗传算法而言，就是适用于总种群规模不变的情况。所以，Amdahl定律适用于主从式和细粒度模型，在适应度评价计算量较大时，主从式模型可以得到接近线性的加速比。由于细粒度模型的应用较少，适用的SIMD并行机的可扩展性也不突出，所以很少有人评价细粒度模型的加速比。利用Amdahl定律评价粗粒度模型时，需保持总的种群规模，即子种群数量和子种群规模成反比。这种情况下粗粒度模型的加速比接近线性，这是由于粗粒度模型的通信开销和同步开销都不大。5、实例：带约束并行多机调度5、1 问题描述最小化完工时间的带约束并行多机调度问题可描述如下：有 n 个相关的工件，m 台机器，每个工件都有确定的加工时间，且均可由 m 台机器中的任一台完成加工任务。要找一个最小调度，即确定每台机器上加工的工件号顺序，使加工完所有工件所需时间最短。算法关键在于：(1) 如何表示工件之间的关系。可以把 n 个相关工件表示成一个后继图，如上图所示。图中节点间的有向边表示工件之间的后继或编序关系。因此，Ti →Tj 表示工件 Tj 在完成之后才能启动工件Ti。显然对于 n 个相关工件，我们可以根据工件间的约束关系所表示成的后继图产生一符合约束条件的工件序列( a0，a1，…，ai，…，an-1) (0 ≤ai 硕士学位论文, 、王冠. 并行遗传算法及其在组合优化问题上的分布式应用, 武汉理工大学硕士学位论文, 、吴昊, 程锦松. 用并行遗传算法解决带约束并行多机调度问题. 微机发展, 2001.