辽宁科技大学本科生毕业设计（论文） 第 7页
1.5 本文工作
在查阅国内外大量的期刊、书籍、会议论文集等文献，了解了关于虚拟企业的相关研究情况的基础上，本文主要做了以下工作：
（1）
对虚拟企业及虚拟企业风险管理相关理论问题进行综述，并介绍了国内外研究现状。
（2）
[11]
介绍了应用于不确定网络图完工概率计算中的计划评审技术（PERT），
和智能优化算法-蚁群算法[12]。
（3）
考虑到虚拟企业以项目形式进行组织生产，在风险评价的基础上，提出了基于马尔可夫的虚拟企业风险规划模型，满足在投入费用和工期一定的情况下，使项目的完工概率最大。并针对该问题设计了蚁群算法。最后给出实例，利用c语言编程，并对仿真结果进行分析，证明了该方法的有效性。[9-10]分别着重的介绍了C语言程序的编程的基本知识;[8]介绍了用C语言编写网络图的一种具体方法（邻接表法）以及求关键的方法。
辽宁科技大学本科生毕业设计（论文） 第 8页
2 蚁群算法
2.1 导言
人类在自然界获得启发，发明了许多试图通过模拟自然生态系统机制来求解优化问题的方法。研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本自组织的，在许多场合中尽管这些合作都很简单，但它们却可以解决很多复杂的问题。每只蚂蚁智商并不高，看起来没有集中的指挥，但它们能协同工作寻找食物。据此，意大利学者提出了一种模拟昆虫王国中蚂蚁群体觅食方式的仿生优化算法——蚁群算法（ACA）。该算法引入正反馈并行机制，具有较强的鲁棒性，优良的分布式计算机制，易于与其他方法结合等优点。 2.1.1 蚂蚁觅食的特性
在自然界中，蚂蚁无论再多复杂的路况的下都可以找到食物，原来蚂蚁会分泌一种叫做信息素的化学物质，蚂蚁许多的行为受信息素的调控蚂蚁在运动的过程中，能够在其经过的路径上留下信息素，而且能够感知这种物质及其浓度，以此来指导自己的运动方向。蚂蚁会倾向于信息素浓度高的地方移动。 2.1.2 基本蚂蚁算法（AS）
基本蚂蚁算法（AS）是采用人工蚂蚁的行走路线来表示带求解问题可行解的一种方法。每只蚂蚁在解空间中独立地搜索可行解，当它们碰到一个还没有走过的路口时，就会随机挑选一条路径前进，同时释放出与路径长度有关的信息素。路径越短信息素浓度就越大。当后继的人工蚂蚁再次碰到这个路口时侯，以相对较大的概率选择信息素较多的路径，并在“行走路线”上留下更多信息素，影响后来的蚂蚁，形成正反馈机制。随着算法的推进，代表最优解的路线上的信息素渐渐增多，选择它的蚂蚁也会增多，其他路径的信息素会随着时间的推移而消逝，最终整个蚁群在正反馈的作用下集中到代表最优解的路径上，也就找到最优解。在整合寻优过程中，单只蚂蚁的的选择能力有限，但蚁群具有高度的自组织性，通过信息素交换路径信息，形成集体自催化行为，找到最优
辽宁科技大学本科生毕业设计（论文） 第 9页
路径。
很多文献对基本蚁群算法的介绍都是从旅行商问题（TSP）开始的。这是因为蚁群觅食的过程与TSP问题的求解非常相似，为了方便读者更好的理解蚁群算法的数学模型和实现过程，以n个城市TSP问题作为背景介绍基本蚁群算法。TSP问题属于一种典型的组合优化问题，是组合dij(1?i?n,1?j?n,i?j)。TSP问题是找到一条只经过每个城市一次且回到起点的、最短路径的回路。设城市之间的距离为dij，表示如式（2.1）所示
dij??xi?xj??yi?yj?2?122? (2.1)
TSP求解中，假设蚁群算法中的每只蚂蚁是具有以下特征的简单智能体。 ① 每次周游，每只蚂蚁在其经过的支路?i,j?上都留有信息素。
② 蚂蚁选择城市的概率与城市之间的距离和当前连接支路上所包含的信息素余量有关。
③ 为了强制蚂蚁进行合法周游，直到一次周游完成后，才允许蚂蚁游走已访问的城市（可由禁忌表控制）。
蚁群算法的基本变量和常数有：m,蚁群中的蚂蚁总数；n, TSP问题中的城市的个数；
dij，城市i和j之间的距离，其中i,j??1,n?;?ij?t?,表示t时刻在路径?i,j?连线上残留的
信息量。在初始时刻各条路径信息量相等，并设?ij?0??const（const为常数）。
蚂蚁k(k?1,2,3...,m)在运动过程中，根据各条路径上的信息量决定其转移方向。
k?t?表示在t时刻蚂蚁k有城市i转移到j的状态转移概率，pij根据这条路径上的残留信量
?ij?t?及路径启发信息?ij来计算的，如式（2.2)所示表示蚂蚁在选择路径时会尽量选择距离较近且信息素浓度较大的方向。
?[?ij(t)]?*[?ij(t)]?,j?allowedk???[?(t)]?*[?(t)]?kisis pij?? （2.2） s?allowedk???0
辽宁科技大学本科生毕业设计（论文） 第 10页
式中，allowedk?{C?tabuk}——表示在t时刻蚂蚁k下一步允许选择的城市（即还没有访问的城市）；
tabuk(k?1,2,......,m)——表示禁忌表，记录蚂蚁k当前已经走过的城市；
?——表示信息启发因子，反应了蚁群在运动过程中所残留的信息量的相对重要程
度；
?——表示期望启发因子，反应了期望值的相对重要程度；
?ij——表示由城市i转移到j的期望程度，被称为先验知识，这一信息可由要解决的问题给出，并由一定的算法来实现。TSP问题中一般取值为式（2.3）。
?ij?1 （2.3） dijk?t?也就越大。 对于蚂蚁k而言dij越小则?ij?t?越大，pij为了避免残留信息过多而淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息素进行更新处理。?t?n?时刻在路径?i,j?上的信息量可以按式（2.4）和式（2.5）所示的规则进行调整。
?ij?t?n???1????ij?t????ij?t?m （2.4）
k?t? （2.5） ??ij?t?????ij
k?1 式中，?——表示信息素挥发系数。模仿人类记忆特点，旧的信息将渐渐忘却消弱。为防止信息素的无限积累，?的取值范围[0,1]，用1??信息的表示残留系数。 ??ij?t?——表示本次循环中路径?i,j?上的信息素增量，初始时刻??ij?t?=0。
k?t?——表示第k只蚂蚁在本次循环中留在路径?i,j?上的信息素增量。 ??ij 根据信息素更新策略的不同，Dorigo M提出了三种不同的基本蚁群算法模型，分别为蚁周模型、蚁量模型、蚁密模型。
?Q?,第k只蚂蚁本次循环中经过（i,j）k ??ij(t)??Lk （2.6）
?0,其他?
辽宁科技大学本科生毕业设计（论文） 第 11页
蚁量模型
蚁密模型
?Q?d,第k只蚂蚁在t到t?1之间经过（i,j）k??ij(t)??ij （2.7）
?0,其他??Q,第k只蚂蚁在t到t?1之间经过（i,j）k??ij(t)?? （2.8）
?0,其他式中，Q——常量，表示蚂蚁循环一周或一个过程在经过路径上所释放的信息素总量，它在一定的程度上影响算法的收敛速度。 LK——表示第k只蚂蚁在本次循环过程所走路径的长度。
2.2 基本蚁群算法的具体实现
这里基本蚁群算法是基于蚁周模型的，实现步骤如下，见图2.1。
第一步：初始化参数。时间t?0，循环次数NC?0，设置最大循环次数Ncmax，令路径(i,j)的初始化信息量?ij?t??const，初始时刻??ij?0??0。
第二步：将m只蚂蚁随机放在n个城市上。 第三步：循环次数NC?NC?1。 第四步：令蚂蚁禁忌表索引号k?1。 第五步：k?k?1。
第六步：根据状态转移概率公式计算蚂蚁选择城市j的概率，j??C?tabuk?。 第七步：选择具有最大状态转移概率的城市，将蚂蚁移动到该城市，并把该城市记入禁忌表中。
第八步：若没有访问完集合C中的所有城市，即k?m,跳转至第五步；否则转至第九步。
第九步：根据式(2.4)和式(2.5)更新每条路径上的信息量。
第十步：若满足结束条件，循环结果输出计算结果；否则清空禁忌表并跳转到第三步。