多Agent遗传算法（精选11篇）
多Agent遗传算法 第1篇
为了更好地求解多目标优化问题,将多Agent技术、遗传算法、正交试验相结合,设计每个智能体进化算子,以更好地改进传统遗传算法。最后用标准测试函数进行测试,并加入Matlab仿真。仿真结果表明,改进后的算法可以找到多目标优化问题分布较均匀的Pareto最优解,具备较强的全局优化能力。
1一种求多目标优化问题的正交多Agent遗传算法
1.1正交试验设计的基本原理
正交试验设计是利用正交表来安排与分析多因素试验的一种设计方法。它是由试验因素的全部水平组合中,挑选部分有代表性的水平组合进行试验的,通过对这部分试验结果的分析了解全面试验的情况,找出最优的水平组合。在试验安排中,每个因素在研究的范围内选几个水平,就好比在选优区内打上网格,如果网上的每个点都做试验,就是全面试验。
1.2正交初始化算子
初始化步骤如下:首先,将可行解空间[l,u]分割成R个子空间[l(1),u(1)], [l(2),u(2)],…, [l(R),u(R)];其次,量化每个子空间,用正交表LM(QN)产生M个染色体;然后,从MR个染色体中选择K个适应度好的个体作为初始Agent种群。最后,将Agent一一对应分布到网格上,计算每个Agent能量值。
1.3邻域竞争算子
竞争行为,主要表现为竞争失败的Agent将无法在环境中继续存活。种群中每个Agent,都将与其邻域内能量最大的Agent进行竞争比较,当Agent的能量小于其邻域内最大能量时,该Agent将无法继续生存,其位置由新的Agent代替。
具体描述为:设网格内某一智能体为Ai,j,如果满足式(1), 则为胜者,否则为败者,将不适合在网格内生存。
Ai,j的能量大于其邻域内能量最大的智能体时,则可以继续在网格上存活,参与下一步的交叉、变异;否则其将不能继续存活,空出的位置被Maxi,j替代。 Maxi,j有两种替代空位置的策略方法,它每次以概率U(0,1) 进行选择,Maxi,j产生新智能体Newi,j=(e1,e2,...,en) 的方法如式(2)所示。
如果U(0,1) 大于0.5,则选择(1);如果小于等于0.5,则选择(2),其中U(*,*) 表示*区间均匀分布的随机数。
1.4正交交叉算子
交叉,指的是生存在环境中的智能体与邻域中的其他个体交换某部分基因,从而形成两个新智能体,以提高自身能量。 智能体的交叉行为,体现的是智能体的“强强联合”以及“从别处获得经验”。
本文采用正交交叉算子来进行交叉,作用于两个父代Agent。首先对子空间进行量化,然后用正交试验生成有代表性的子代Agent。
两个父代Agent定义如下:
Agent a1=(a1,1,a1,2,…,a1,N),Agent a2=(a2,1,a2,2,…,a2,N)。Agent a1、Agent a2二者确定的子空间为[p,q],其中,p=[min(a1,1,a2,1),…min(a1,N,a2,N)],q=[max(a1,1,a2,1),…,max(a1,N,a2,N)]
1.5变异算子
变异方式如下:首先选取两个变异点,将这两点进行交换, 然后再按式(3)产生新的智能体R1,i=(r1,r2,...,rn):
其中,U(0,1) 和U(-1,1) 为区间内的随机数,pm为变异概率,η 为学习率,一般取 η = 0.1~0.2 。
自适应的变异概率
其中pm1为初始变异率,取值为0.01,u为变异率的比例系数,取值为0.19。
1.6算法描述
假设多智能体种群L的规模为Lsize×Lsize,Lt表示第t代的智能体种群。Lt+1/3和Lt+2/3是Lt和Lt+1的中间代种群。
步骤1:正交初始化种群L ;
步骤2:判断停机条件。若满足停机条件,则终止算法并输出结果;否则,继续;
步骤3:对Lt中的智能体进行邻域竞争操作,得到Lt + 1/3;
步骤4:对Lt + 1/3上的每个智能体以概率pc执行正交交叉操作,得到Lt+ 2/3;
步骤5:对Lt + 2/3上的每个智能体以概率pm执行变异操作, 得到Lt+ 1;
步骤6:Agent利用已有知识进行启发式搜索以提高自身能量,转步骤2。
2实验结果
本文采用2个标准测试函数来测试改进算法的性能,这2个测试函数的仿真结果如下:
1)SCH:具有凸的Pareto最优前端,用式(14)来表示。
扶植
2)ZDT2:具有非凸的Pareto最优前端,用式(5)来表示。
在实验中,将本文算法和传统遗传算法进行了对比分析。 参数设置如下:种群规模N=100,进化代数T = 200。编码长度为7,自学习概率ps为0.3。
从上面的仿真图形可以看出,在求解SCH问题时,本文算法与传统遗传算法的性能差别不大,都可以很好的收敛到问题的最优区域,而在求解ZDT2时,本文算法表现出较好的性能, 所求Pareto解的分布性和收敛性均优于传统遗传算法。
3结束语
本文主要提出了一种求解多目标优化问题的正交多Agent遗传算法。本文算法在多目标遗传算法的基础上,结合多Agent技术和正交试验,改进传统遗传算法,对求解多目标优化问题取得了良好的效果。
参考文献
[1]陈国良,王煦法,庄镇泉,等.遗传算法及应用[M].北京:人民邮电出版社,2001.
[2]钟伟才,薛明志,刘静,等.多智能体遗传算法用于超高维函数优化[J].自然科学进展2003,13(10):1078-1079.
[3]Leung Y W,Wang Y.An Orthogonal Genetic Algorithm withQuantization for Global Numerical Optimization[J].IEEETrans.Evolutionary Computation,2001,5(1):41-53.
[4]王朝辉,张伟丰.基于混合编码的多智能体遗传算法[J].武汉科技大学学报:自然科学版,2009,29(6):603-60.
[5]潘晓英.混合多智能体遗传算法[J].计算机工程与应用,2010,46(3):9-12.
[6]丁承民,张传生,刘贵忠.正交试验遗传算法及其在函数优化中的应用[J].系统工程与电子技术,1997,19(10):57-60.
[7]孟红云,刘三阳.求解多目标优化问题的多智能体遗传算法[J].西北大学学报,2005,35(1):13-16.
多Agent遗传算法 第2篇
2 多岛遗传算法
遗传算法是一类借鉴生物界的进化规律演化而来的非经典优化算法。与传统的优化算法相比，遗传算法不存在求导和目标函数连续性的限定，且具有全局寻优能力。但传统的遗传算法在优化过程中基因突变的概率较低，容易在进化几代后出现早熟现象，导致优化结果收敛于局部最优解。
3 数值算例
以某飞行器为例，依据其一级满油、一级空油、二级满油、二级空油 4 种典型飞行状态下的前两阶模态频率和振型试验结果，选取各舱段材料的弹性模量为优化变量，数值分析与试验结果差异为优化目标，采用本文方法进行动力学模型修正。
4 结 论
a)提出了基于多岛遗传算法的多状态结构动力学模型并行修正方法，改进了传统方法针对同一产品不同试验状态分别修正模型，导致同一产品模型参数不一致的不足，更符合工程实际;
b)动力学模型并行修正方法中各试验状态的残差之间相互独立，且对残差的物理意义没有约束，可以同时对动力学特性和动力学响应模型进行修正;
c)采用多岛遗传算法驱动优化流程，避免了经典优化算法需要对目标函数求导的限制，同时保证了设计参数收敛于全局最优解;
多Agent遗传算法 第3篇
关键词:资源约束;项目调度;遗传算法
中图分类号:O224 文献标识码:A文章编号:1006-8937(2010)10-0017-01
经济的全球化加剧了日益激烈的市场竞争,同时对企业的生存与发展提出了更高的要求。无论是软件开发、建筑工程、制造业等大型产业,还是进行批量生产的小型企业,为了进一步增强自身竞争优势,项目管理技术的应用已经越来越广泛。而项目调度问题作为项目管理技术中的一个重要分支,合理的调度计划能够有效地缩短项目周期、降低企业成本、提高产品质量。但是由于项目调度问题较为复杂,不仅存在前驱后继关系,还常伴有资源的约束,求解极为困难。
因此,文章所研究的主要内容就是对求解多模式资源约束项目调度问题的遗传算法进行优化。
1存在问题
在更多的实际项目中,为了提高资源的利用率,项目负责人往往会依据项目中各活动的轻重缓急程度来决定对各个活动的资源投入量,而在现实的工作过程中,各工作所获得的实际资源投入量会直接影响到该活动的工期。所以,当活动比较紧急时,可以通过加大资源投入量的方法,来缩短完成这项活动所需要的工期。当活动不是很紧张,可以略有拖延时,我们也可以考虑通过减少该活动的资源投入量,从而降低成本,这样就可以在工程进度中获得更大的收益。这种可以使用不同资源分配模式的资源约束项目调度问题就是多模式资源约束项目问题(multi-mode RCPSP,MRCPSP)。如果能够更好的为每项调度中的活动合理安排投入的资源,那么最终可以使得项目的完成情况更接近或超过预期目标。
2求解方法遗传算法是基于自然选择,在计算机上模拟生物进化机制的优化算法。它把欲求解问题的解空间映射作为遗传算法的搜索空间,把每一个可能的解编码作为一个解向量,也称为染色体(Chromosome),染色体中的每一个元素称为基因(Gene)。所有的染色体就可以组成一个种群。根据所研究问题的求解情况设定一个目标函数值,即评价指标,比如工程项目中的工期等。通过这个目标函数值,也称为个体适应度,来评价所有染色体,从而决定染色体的好坏优劣。这样,按照遗传算法的流程和对应的操作,不断进化种群中的染色体,来调整其基因值,使之愈来愈趋近于目标函数值所倾向的个体,也就是我们所研究问题中期望的较优解。
遗传算法通常包括六个基本步骤。步骤1,初始化种群:按照预先设定的优先规则(LFT,LST,MTS,MSLK,RND)和对应的个体数(比例,如LFT:LST:MTS:MSLK:RND=1:1:1:1:1)产生初始种群链表initGroupList,大小为GS。步骤2,选择操作:按照选定的选择操作的策略(轮盘赌、二人竞赛)和交叉率进行选择操作,将选中的个体加入到双亲链表parentsGroupList。步骤3,交叉操作:按照选定的交叉操作的策略(单点、两点、均匀、最大资源利用)进行交叉操作。从parentsGroupList中选择双亲进行交叉,交叉后的新个体保存到子代链表childrenGroupList。步骤4,变异操作:按照选定的变异操作的策略(基插、染插、交换、基邻插、染邻插、邻交换)进行变异操作。对childrenGroupList中的新个体按照变异率进行变异,变异后的个体加入到初始种群链表initGroupList。步骤5,维持种群:保证数量不变。步骤6,终止条件:是否达到最大迭代次数,如未达到则重复步骤2。否则,输出迭代中最好的个体。遗传算法编码和解码解析。根据目前的研究资料表明,紧前关系相容链表是目前较好的一种染色体编码方式。该方法简单易用并且求解效率高。
所选择的适应度函数。通常情况下,遗传算法的通用适应度函数公式定义如下:
f(x) = T (1)式中,f(x)是个体x的适应度值;T是个体x的项目工期。
选择、交叉和变异算子。遗传算法的核心操作是三个操作算子——选择、交叉和变异。这三个算子主导了遗传算法如何进行,也决定了所研究问题的求解质量。
①选择应运二人竞赛策略。在生物的遗传和进化的过程中,任何一个物种对生存环境适应度较高的个体都会有更多的机会将优良基因遗传到下一代中,反之被保留的机会就会减少,甚至被淘汰。根据预先设定的选择概率,在种群中对每个个体进行选择。在被选中的个体中依次进行选择,每次选择都从两个个体中选择最优的一个个体进入待交叉列表。因而选择操作在遗传算法中往往起着更为重要的作用,它会从父代中选出最好的基因遗传于子代之中。
②两点交叉策略。记参与交叉的两个父代个体为A和B,随机生成两整数p,q,1 ③基于基因和邻域搜索的插入变异策略。基于基因插入变异策略是在基于基因的插入变异策略的基础上,根据变异概率和变异因子记录本次变异中出现过的最好染色体作为变异的结果,这个过程也称为邻域搜索。其中变异因子为在区间中尝试的位置次 3实验结果 为了研究遗传算法应用于MRCPSP求解的问题,文章选择了PSPLIB实例库中多模式J10作为测试依据,来验证遗传算法各个策略的优劣,结果如下:①选择策略。赌轮机制(比例复制)在运行J10项目中平均偏差率、最优解比例均不如二人竞赛策略。因此,文章融合算法中遗传算法部分采用二人竞赛的选择策略。②交叉策略。两点交叉相对于其它交叉策略具有更好的效果,平均偏差率、最优解比例都有很好成绩,因此文章融合算法中遗传算法部分采用两点交叉。③变异策略。文提出的基于基因和邻域搜索的插入变异策略相对于其他变异策略具有更好的效果,平均偏差率、最优解比例都有很好成绩,因此文章融合算法中遗传算法部分采用基于基因和邻域搜索的插入变异策略。 4结语 从实验结果可以看出,应运遗传算法解决资源约束项目调度问题具有很高的求解效率和质量。对遗传算法的变异策略进行改进,应运与求解具体的实例中更具有一定优势。 参考文献: [1] 刘立东,蔡淮.融入遗传算法的混合蚁群算法[J].计算机工 程与设计,2008,(5). [2] 陈国良,王煦法,庄镇权,等.遗传算法及其应用[M].北京:人 民邮电出版社,1996. [3] (日)玄光男,程润传.遗传算法与工程设计[M].北京:科学出 版社,2000. [4] 金菊良.遗传算法及其在水问题中的应用[D].南京:河海大 学,1998. [5] 韩万林,张幼蒂.遗传算法的改进[J].中国矿业大学学报, 2000,(7). [6] 杨启文,蒋静坪,张国宏.遗传算法优化速度地改进[J].软件 学报,2000,(4). [7] 翟梅梅.基于蚁群算法的改进遗传算法[J].安徽理工大学 学报(自然科学版),2009,(3). [8] 张晓玲,黄力.融入遗传算子的蚁群算法求解TSP问题[J]. 广西民族大学学报, 2009,(3). [9] 黄立军,许永花.遗传算法和蚁群算法融合求解TSP[J].东 北农业大学学报, 2008,39(4):109-113. [10] 徐金荣,李允,刘海涛,等.一种求解TSP的混合遗传蚁群算法[J].计算机应用,2008,(8). 自适应PID调速器参数优化主要是针对机组过渡过程寻找最优控制参数的过程。一般中小机组主要接受调度命令进行各种工况的调整,如增减负荷、停机等,负荷变化相对较慢。但对在系统中担任主调峰调频的机组,如三峡机组而言,由于工作水头和机组出力变化大且快,导致其运行工况经常变化。若对整个水电机组控制域应用传统固定PID参数,往往很难获取全工作域的最优调节。为此,三峡机组选择适应式变参数PID控制策略[1,2,3],其主要思想为:随着工况(水头和出力)的改变,自动在线地改变调速器控制参数,使机组性能在全工域的各种工况下都达到最优。为满足实时性要求,还必须对各工况点对应的PID参数进行离线优化整定。因而,建立符合实际的机组模型并选择一种合适的优化算法是实现上述控制策略的关键所在。 遗传算法是一种模拟自然选择和遗传机制的全局概率寻优算法,由于遗传算法对优化对象的数学模型、初始参数、变量数量等都没有特殊限制,因而得到了广泛的应用[4,5]。但是,对于复杂的优化模型,遗传算法适应度的计算往往占有绝大部分时间资源[7]。例如在MATLAB中仿真运行三峡机组调节系统模型,每次需耗时20 s左右,假设种群规模为30,进化代数为150,若采用传统单客户的遗传算法,其优化总耗时超过20 h,这仅是针对某一种工况,对于三峡机组,由于要求自适应PID控制,显然需要对各种工况进行优化,传统的遗传算法优化时间可达数月之久,显然这无法体现遗传算法并行计算的优势。因此,随着求解问题的复杂性及难度增加,提高遗传算法的运行速度便显得尤为重要。作为人工智能的一个分支,多Agent系统由于具有自治性、开放性、社会性等特点,特别适合解决大规模分布式复杂问题[6,7]。针对上述问题,本文提出了一种基于多Agent的遗传算法MAGA(Multi-Agent Genetic Algorithm),并基于JADE平台进行了仿真验证。 1 水电机组调节系统数学仿真模型 建立水电机组调节系统数学仿真模型是PID参数优化的前提。水电机组调节系统是一个水、机、电过程相互影响、相互制约的复杂系统,针对三峡机组,本文利用MATLAB/Simulink工具箱建立起非线性全数字仿真模型,见图1。该模型主要包括调速器模块、液压随动系统模块和水轮发电机模块。为提高模型精度,在水轮机的建模中,本文利用Simulink扩展工具S函数(S_function Q、S_function Mt)分别建立了2个反映水轮机动态特性的非线性数学模型:Q=f(a,h,x)和Mt=f(a,h,x),其中,Q和Mt分别反映了流量、力矩和水轮机开度a、水头h、转速x的非线性关系。Q、Mt及其导数在整个区域内连续,保证了迭代过程的收敛;同时建模时还充分考虑了调节过程中的饱和、限速、限幅等非线性因素的影响。这种建模方法具有很强的开放性,模型的结构易于修改和重构,能够较好地适应水电站个性强的特点。 频率扰动量经过并联PID模型微分环节时会产生很高的频率尖峰,从而增加调节时间,而采用串联PID模型,扰动量则可以绕过微分环节,避免了尖峰的产生。因此,图1中的调速器子系统采用的是串联PID调速器,如图2所示。控制参数为暂态转差系数bt、缓冲时间常数τd、比例微分时间常数τn。显然,自适应PID调速器的参数优化就是希望在任何工况下都能找到一组最优的参数整定值,使得在机组的整个控制域内,既能保证调节系统的稳定,又能获得良好的动态品质。 图1中的液压伺服子系统由ALSTOM公司提供,如图3所示。其中的虚框部分是在机组全甩负荷时的导叶二段关闭模型,在空载频率扰动和负荷扰动时需将其去掉。 2 MAGA模型 2.1 体系拓扑结构 本文所提出的网络体系如图4所示,可以看出,该网络平台中主要活动着一个调度Agent(GADispatcher)和一组PS Agent,它们分布在不同的网络计算节点上。其中GADispatcher负责遗传算法的进化调度工作,是实施遗传算法的核心Agent。当获得优化请求时,GADispatcher便开始组建由若干PS Agent组成的初始种群。实际上,这些PS Agent分别代表问题域内的一个潜在解(即一套PID控制参数)。当所有这些PS Agent移动到指定的网络计算节点上后,进化环境即构建完毕。随后,GADispatcher将获得每一代种群遗传操作的控制权(不是全部),即GADispatcher将负责调度遗传算子的操作如复制、交叉、变异等。特别地,该Agent将根据每个PS Agent的性能好坏来控制进化的方向:性能好的PS Agent将会赢得更多机会在下一代生存,而性能差的PS Agent可能会被淘汰。在进化过程中,所有的PS Agent是遗传算法的承担者,它们能够感知外部世界信息(如来自GADispatcher或其他PS Agent的信息),同时是遗传操作的执行者。由于种群中的PS Agent被设计成移动Agent,并且在遗传进化开始前已移动到不同的网络节点上,因此可以确保个体适应度计算的真正并行性,从而大幅提高了优化效率。 2.2 MAGA交互模型 图5是基于Agent统一建模语言(AUML)的MAGA交互模型,用来描述MAGA的实现过程以及表达Agent之间的消息传递过程。下面给出消息顺序的具体解释。 步骤1当获得优化请求时,GADispathcer创建由一定数目的PS Agent(PS1—PSn)组成的初始种群。然后,GADispathcer指派所有的PS Agent通过网络移动到目的远程机器上(即空闲的网络节点2到节点n)。 步骤2所有的PS Agent开始随机产生一组PID控制参数(即bt、τd和τn)。 步骤3所有的PS Agent将初始控制参数传递给位于本网络节点的MATLAB机组调速系统仿真模型,并启动仿真,仿真结束后记录反映控制性能的2个重要参数:超调量、调节时间。 步骤4所有的PS Agent根据式(1)分别计算各自的适应度。 式(1)反映了超调量mp和调节时间ts的综合性能指标。其中,T1、T2分别为mp和ts的约束值,它们的引进可有效地消除物理量纲,当mp和ts超标时,该PS Agent的适应度设置为0;K2、K1为比例因子,分别反映了对ts和mp的重视程度,本文中K2取为2,K1取为1,主要原因是超调量比调节时间更容易得到满足。 步骤5 PS Agent向GADispathcer发送消息,以告之自身的适应度。 步骤6当收集到来自所有PS Agent的适应度信息后,GADispathcer会执行一些统计工作,如计算总的适应度、平均适应度、最大/最小适应度等。 步骤7 GADispathcer应用轮盘赌法来决定上一代种群中的PS Agent在下一代中存活的机会。性能较差的PS Agent将可能会被淘汰,而性能较好的PS Agent在下一代中有机会被复制多次。如:PS3在轮盘赌中被淘汰,而性能较好的个体PS2被克隆至PS3,具体操作是把PS2的染色体作为消息内容传送给PS3。 步骤8复制操作结束后,GADispathcer随后负责交叉操作。特别地,GADispathcer负责配对需要交叉的PS Agent,然后向所有配对的PS Agent发送交叉信息,包括需要交叉的Agent名字、网络计算节点地址以及染色体中需要交叉的位置。 步骤9当要求执行交叉操作时,所有配对的PS Agent根据收到的交叉信息,从自身染色体中提取需要交换的位串,然后相互发送,并根据收到的位串重新组装成新的染色体。 步骤10 PS Agent根据一定的变异概率进行变异操作。 步骤11一旦3个遗传操作执行完毕,新一代种群中的PS Agent再一次调用机组调速系统仿真模型。 步骤12根据返回的超调量与调节时间,由式(1)再次计算适应度,随后的进化过程和消息传递过程将重复步骤5—12,直至得到期望的解或达到指定的代数为止。 步骤13 GADispathcer获取最优解。 步骤14 GADispathcer结束所有PS Agent的生命周期,并等待下一次优化指令。 3 基于JADE中间件的实现模型 3.1 基于JADE的MAGA实现平台 JADE是一个完全由JAVA编写的符合FIPA标准的多Agent软件开发框架,它既为应用程序员提供现成的功能片断,也为自定义的应用程序任务提供抽象接口。作为中间件,JADE提供了多Agent应用的基本服务功能。其中Agent管理系统(AMS)提供白叶服务,负责管理平台内Agent的注册以及Agent的生命周期;目录服务(DF)Agent提供黄叶服务,以方便注册、发现、订购等服务功能的管理;ACC提供底层的Agent通信服务,负责控制所有Agent之间的消息传输。 图6是基于JADE的MAGA实现平台,可以看出,系统中所有Agent驻留在不同主机的容器(Container)中,其中的主容器(Main Container)中运行着AMS与DF。该容器在Agent平台中必须是活动的,且是唯一的,平台中首先启动的容器必须是主容器,其他容器需要根据主机与端口发现主容器以便注册。可以看出,整个MAGA实现平台由网络上若干不同主机(Host、Host1、…、Hostn)构成。其中,Host内活动着系统Agent(AMS与DF);Host1内活动着控制遗传进化的GADispacher,为增强系统的开放性,本文把GADispacher提供的优化能力作为一种服务事先注册到DF;而Host2至Hostn负责接受Host1内GADispacher在构建进化环境时产生并派送过来的PS Agent,这些PS Agent主要具体执行遗传算子和计算适应度。除此之外,Host2至Hostn内还驻留有机组调速系统的MATLAB仿真模型,每个PS Agent有能力控制调速系统模型的仿真过程,并根据仿真结果返回的超调量和调节时间计算适应度。需要注意的是:MAGA实现平台中的每台主机都有一个JAVA虚拟机作为Agen的基本容器,以便为系统中所有的Agent提供完整的运行环境。另外,系统中所有的Agent均使用Agent通信语言(ACL)进行沟通与交互,语义使用protégé-2000设计的ontology来定义。 3.2 Agent的行为模型 JADE行为模型允许Agent执行并行任务以响应不同的外部事件。为了提高Agent的管理效率,每一个基于JADE的应用Agent由1个单一线程构成。隐藏的调度器运用轮循非抢占的策略对Agent活动行为队列中的并行行为进行调度。 图7给出了实现MAGA的行为类层次,其中Sequential Behavior是一个复合行为类,该类顺序执行其子行为直到所有子行为执行完毕为止,因此实际行为执行是定义在子行为类中,如Control Selection子行为和Control Crossover子行为。抽象类Cyclic Behavior派生出的原子类能循环执行,抽象类One Shot Behavior派生出的原子类仅执行依次且不能阻塞。 MAGA中每个Agent的任务任务被执行成JADE行为,任务描述如下,其中,a-g为GADisptcher Agen行为,h-m为PS Agent行为。 a.Create PSAgents,行为类型为Oneshot Behavior,该行为产生由若干PS Agent构成的初始种群,以构建进化环境。 b.Ready To Move,行为类型为Cyclic Behavior,在PS Agent移动前,该行为负责一些初始化工作。 c.Migrate To Dest,行为类型为Oneshot Behavior,当收到优化请求时,该行为使得PS Agent通过网络移动到目的网络节点上去。 d.Statatic,行为类型为Cyclic Behvior,该行为执行一些统计工作,如计算每一代总的适应度、平均适应度以及最大/最小适应度等。 e.Evolution Schedule,行为类型为Sequential Behavior,该行为用来调度其中的子行为,使得它们能够顺序执行。 f.Control Selection,行为类型为One Shot Behavior,该行为是Evolution Schedule的子行为,该子行为使用轮盘赌算法控制PS Agents在下一代的存活机会。 g.Control Crossover,行为类型为One Shot Behavior,该行为是Evolution Schedule的子行为,该子行为根据交叉率随机对PS Agent进行配对并且决定染色体交叉位置。 h.Initialize PS,行为类型为One Shot Behavior,该行为随机产生一组优化PID参数。 i.Calculate Fitness,行为类型为One Shot Behvior,用来计算适应度。 j.Perform Selection,行为类型为Cyclic Behaviour,该行为执行复制遗传算子,这取决于GADispacher执行的轮盘赌算法结果。 k.Wait For Crossover Info,行为类型为Cyclic Behavior,该行为接受来自GADispacher的交叉信息,同时准备需要与配对PS Agents交换的染色体信息。 l.Perform Crossover,行为类型为Cyclic Behaviour,该行为具体执行交叉遗传算子,负责重新组装染色体。 m.Perform Mutation,行为类型为Cyclic Behaviour,该行为根据变异率执行变异遗传算子。 4 仿真结果 仿真所用到的试验参数如下。 三峡电站的基本参数:机组惯性时间常数τa=9.863 s;水流惯性时间常数τw=2.632 9 s;空载频率扰动和甩全负荷时en=0.05,负荷扰动时en=0.45,en为机组综合自调节系数。 MAGA用到的控制参数:种群规模为30,染色体长度l=30,繁殖代数g=150,交叉概率Pc=0.8,变异概率Pm=0.02。 在32台计算机组成的局域网上建立仿真环境,利用优化MAGA对在各种工况下(水头为61~113 m,负荷为10%~120%)的三峡机组进行了大量的优化仿真。在仿真中,通过在给定功率上加一个阶跃信号(±10%额定负荷)来模拟调度指令实现负荷扰动。限于篇幅,下面仅给出带负荷扰动的部分优化结果。 表1中的数据分别表示机组在不同工况下的3个PID优化控制参数:暂态转差系数bt/暂态缓冲时间常数τd(单位s)/比例微分时间常数τn(单位s)。 在得到机组在各个工况下的优化参数后,就可以对控制系统应用适应性变参数的控制策略,具体实现方法是:将参数表存入调速器的变参数模块中,以水头信号和机组出力作为该模块的输入。在调速器调节过程中的每个控制周期里,变参数模块根据水头信号和机组出力判断该周期的工况点在参数表中的位置,进行查表,将结果输出到调速器中作为该控制周期的控制参数。这样,在每个控制周期中,参数是固定的,保证了控制系统的稳定性;而在整个调节过程中、不同的控制周期里,变参数模块根据机组状况始终在参数表里寻优,输出相应的控制参数。 表2为单机传统GA、单容器MAGA和32容器MAGA对同一工况点进行优化的平均优化时间对比。由于单机传统GA受单CPU限制,平均优化时间长达93 456 s。单机单容器MAGA比单机传统GA优化耗时稍长,是Agent通信产生了额外开销。而32机32容器MAGA的平均耗时只有3 420 s,由于实现了适应度真正的并行计算,虽然Agent通过网络传递消息也产生额外开销,但与适应度计算相比,几乎可以忽略。 5 结论 混合遗传算法及其在翼型气动[1*9/9]多目标优化设计中的应用 把基于实数编码的自适应遗传算法(SAGA)与可变容差法相结合,建立了数值优化设计中的混合遗传算法(HGA),并将其与翼型的气动分析相结合进行跨声速翼型的单目标和多目标气动优化设计.与自适应遗传算法相比,混合遗传算法的优化质量略有改善,优化效率有明显的`提高.优化结果表明混合遗传算法在翼型单目标和多目标气动优化设计中是十分有效的. 作 者：王晓鹏 作者单位：西北工业大学刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA年，卷(期)：19(3)分类号：V211.1关键词：混合遗传算法 跨声速翼型 气动优化设计 摘要：针对目前企业配电网节能技术的不足，提出了一种基于多智能体遗传算法的配电网节能降耗综合管理系统。结合遗传算法（Genetic algorithm，GA）和多智能体系统（Multi-Agentsystem，MAS）技术构造了一种GA-MAS算法，每一个多智能体相当于遗传算法中一个个体，相邻的多智能体相互作用，并结合遗传算法的进化机理进行全局最优求解。提出了该系统各节能设备智能体结构模型和高压/低压多智能体系结构模型，运用GA_MAS算法，得出各个节能设备的最佳调节力度，使节能设备以最小的调节代价获得最大的节能效益。具体算例仿真及工程实际应用表明本文提出的配电网节能降耗综合管理系统能使总有功网损降低，电容器投入总组数减少，实现节能设备的最佳调节，同时表明GA_MAs算法收敛速度较快。 关键词：综合管理系统；节能降耗；节能设备多智能体；遗传算法 中图分类号：TM92 文献标识码：A 节能已成为我国经济和社会发展的一项长远战略方针，节电则是国家节能战略的重要组成部分。纵观目前企业配电网节能技术，存在以下不足：1）整个配电网缺乏全局的规划与管理手段，能量管理水平不高，没有形成“全方位、多方面”的综合节能降耗。2）企业配电网只是进行了局部优化管理，具有很大的局限性。3）企业配电网的节能设备还是单一运行的，形成“孤岛”林立的局面，信息比较分散，集成度不高，不便于高层管理和控制。4）单一独立节点节能设备之间相互影响，一旦局部调节过度或不足会造成临近线路的故障，形成“要害区域”。5）单一节能设备只具备某一方面的节能职能，不能满足社会对全方面节能的需要。且节能设备的独立控制容易导致设备调节过于频繁，设备使用寿命缩短，维护成本增加。 智能体（Agent）是一种具有感知能力、问题求解能力和与外界通信能力的实体。多智能体系统（Multi-Agent System，MAS）由多个松散耦合的、粗粒度的、具有感知能力、问题求解能力、能够与系统中其他智能体通信的智能体组成的网络结构。MAS在兼顾单个智能体系统优点的同时，通过协商、协调和协作，完成复杂的控制任务或解决复杂的问题。 遗传算法（GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法。本文结合GA和MAS技术构造了多智能体遗传优化算法（GA-MAS），该算法利用Agent的局部感知、竞争协同和自学习等特性来实现生物对环境的自适应。由于所有操作都作用于局部种群而不是整个种群，从而维持了群体的多样性，在一定程度上抑制了遗传算法的早熟现象。 针对上述现有技术的不足及其存在的缺陷，结合GA和MAS技术，提出了一种基于多智能体遗传优化算法（GA-MAS）的配电网节能降耗综合管理系统。给出了管理系统的基本结构模型和节能设备多智能体的结构模型，运用GA-MAS算法，得出各个节能设备的最佳调节力度，使节能设备以最小的调节代价获得最大的节能效益。通过具体算例仿真及工程实际应用表明本文提出的管理系统能使总有功网损降低，电容器投人总组数减小，同时表明GA-MAS算法有很好的计算效率及收敛稳定性。 1 无功优化模型 在实际工程应用中，无功补偿装置必然会产生有功损耗及运行维护费用，另外，当配电网无功资源不足时，需要增加无功补偿设备，产生额外投资。因而，系统在追求有功网损最小的同时，综合考虑无功补偿装置总投入最小建立目标函数：其中，N为系统节点数，n为加装无功补偿装置的节点数，QCi为节点i上无功补偿容量，△PC为每kVar无功补偿容量的有功损耗，C为上网电价，丁为年运行小时数，K1为电容器年运行维护费用，△P为系统有功损耗，t为每年最大负荷运行时间。Vi，Vj分别指节点i，j的电压幅值，Gij，Bij分别指网络导纳矩阵的互导纳元素（互电导、互电纳），θij指节点电压相位差。其中，△u为控制变量的变化量；m为补偿装置种类数，即cui为第i种装置调节代价。以变压器为例，成本为Acost元，允许抽头总调节次数为Tn次，抽头永远不调整时的预期寿命是a年，经过Tn次的抽头调整后寿命缩短到a'年，调整设备所增加的运行维护工作量为B，则该变压器的抽头每次操作的调节代价（元/次）为： cu11=B+（a-a'）Acost/aTn。 （4） 由式（4）可类似地计算无功补偿装置投切开关的调节代价。 Vi为节点i电压，QCiSVC，QCiHAPF，QCiIVC，QCiDSTATCOM分别为SVC，HAPF，IVC，DSTATCOM的无功补偿容量，Ti为有载调压变压器分接头档位，QCi为发电机无功出力。 2 多智能体遗传优化算法（GA-MAS） 2.1 Agent的环境 多智能体遗传优化算法是结合GA算法和MAS的主要特征构造的一种算法。首先构造Agent的生存环境，每个Agent与其邻域相互作用，并结合GA算法的进化机制，使其能快速、准确地收敛到全局最优解。 将任意一个Agenta相当于GA算法中一个体，其适应值为： f（α）=FQ。 （9） Agenta的目的就是在满足运行条件的限制下尽可能减小其适应值。 所有的Agent都被放人一个生存环境，即一个L×L的网格，其中L=根号下N，N为群体中个体数。如图1所示，每个Agent都“居住”在该环境里，并且被固定在一个格子中。每个Agent都有其生存周期和自学习能力，能感知其邻域中的个体，并根据感知到的信息自主采取行动策略来完成其意图和目的。每个Agent和其邻域的个体组成了该Agent的局部环境，如图1所示，虚线框构成了Agent2，2的局部环境。每个Agent只和邻域内其他智能体交配产生新个体，具有一定局部性，而它邻域内其他个体又和自身邻域个体交配，由于邻域的重叠性，因而所有个体间均存在信息交换，又具有一定的全局性，可以维持群体的多样性。 2.2 GA-MAS算法流程 GA-MAS算法流程图如图2所示。 1）Pareto择优操作 每个Agent根据其局部环境与其邻域个体两两比较寻找最优解。在任意一个智能体的局部环境中，若该个体优于周围其他个体，则该个体为其邻域中的Pareto最优解。由于是在每个个体的局部环境中进行择优操作，而不是作用于整个群体，因而保证了群体的多样性。 2）交配操作其中，rand是[0，1]中的一个随机数。Pareto择优操作后得到的种群以交叉概率pc按式（12）（13）进行交叉。交叉后得到的子代个体与其父代进行优劣比较，若子代优于父代，则保留子代，否则，继续保留父代。 3）死亡和再生操作 智能体A1，A2，如果两点的距离d（A1，A2） 3 基于GA-MAS的配电网节能降耗综合管理系统 3.1 系统结构 依据多智能体分层分布式系统理论，基于多智能体的配电网节能降耗综合管理系统结构图如图3所示，包括高压侧、低压侧两级多智能体和管理层。 高/低压侧各个智能体的交互和协调通过任务协调智能体完成，且任务协调智能体之间可相互通信；各个智能体通过任务分解智能体与管理层连接，使不同的智能体连通了相应的管理层的各个系统。管理层各系统通过智能体之间的通信和交互相互连接起来，实现了操作平台的互联、互操作和互协调。管理层各系统的数据可通过TCP/IP协议实现各数据库之间互访，达到数据共享与交换的目的。从而管理层各系统连通了高压侧多智能体和低压侧多智能体，实现了高低压侧智能体的交互和协作，进一步实现多层次节能降耗。 3.2 节能设备智能体结构模型 节能设备智能体是具有节能设备功能结构属性的智能体。图3中节能设备智能体构建过程如下： 第j个节能设备智能体结构属性为： Shj={ghj，Msj，Mrj，Ncj，T1}。 （14） 式（14）中ghj为第j个节能设备智能体对其他节能设备智能体的信念度；Msj为第j个节能设备智能体的初始状态；Mrj为第j个节能设备智能体的目标状态；Ncj为第j个节能设备智能体的优先级指标；T1为定义时间间隔。 1）SVC智能体 第K个SVC智能体其初始状态MsSVCk和目标状态MrSVCk分别为： 式（15）中QSVCk为第K个SVC设备补偿无功；VSVCk为第K个SVC设备节点电压；iSVCk为第K个SVC设备输出电流；NSVCk为第K个SVC设备优先级；TSVCk为时间脉冲。 那么第K个SVC智能体结构属性为： 式（17）中IHAPFk为第K个HAPF设备补偿谐波电流；VHPAFk为第K个HAPF设备节点电压；iHAPFk为第K个HAPF设备输出电流；NHAPFk为第K个HAPF设备优先级；THAPFk为时间脉冲。 那么第K个HAPF智能体结构属性为： 3）IVC智能体 第K个IVC智能体其初始状态MsIVCk和目标状态MrIVCk分别为： 式（19）中QIVCk为第K个IVC设备补偿无功；VIVCk为第K个IVC设备节点电压；iIVCk为第K个IVC设备输出电流；NIVCk为第K个IVC设备优先级；TIVCk为时间脉冲。 那么第K个IVC智能体结构属性分别为： 4）DSTATCOM智能体 第K个DSTATCOM智能体其初始状态MsDCOMk和目标状态MrDCOMk为： 式（21）中IDCOMk为第K个DSTATCOM设备补偿无功；VDCOMk为第K个DSTATCOM设备节点电压；iDCOMk为第K个DSTATCOM设备输出电流；NDCOMk为第K个DSTATCOM设备优先级；TDCOMk为时间脉冲。 那么第K个DSTATCOM智能体结构属性为： 3.3 高压/低压多智能体系结构模型 在节能设备智能体基础上，构建的高压/低压多智能体系结构为： HV/LVMSh={Sh1，Sh2，…，Shj，N，T} （23） 式（23）中sh1，…，Shj为图3中高/低压侧各个节能设备智能体；N为各个智能体的优先级信息表；T为时间脉冲。在实例中可具体表示为： 3.4 系统的管理方法 图4是基于多智能体遗传优化算法的配电网节能降耗综合管理系统的管理方法流程图。首先从系统获取实时数据，比较各节能设备智能体当前状态和目标状态。然后高压/低压多智能体汇总所有信息，运用GA-MAS优化算法制定优化方案，再通过任务协调与分解智能体，根据优先级别N确定哪些节能设备智能体参与任务，根据时间脉冲T确定节能设备什么时候响应任务，实现各个节能设备智能体之间的交互和协作，减小节能设备之间的相互影响。 4 仿真分析 为验证以上算法的正确性与可行性，在Delphi环境下应用Pascal语言编制程序，对IEEE-14节点系统进行计算分析。在本文选取的IEEE-14节点系统中，设节点数为14个、发电机数6个、变压器数4个、节能装置6套。变压器当成有载调压变压器，变压器变比调节范围在1±1.25%×8，共分为0～16共17档，并且限制变压器的一次调节档位±2档，其档位与实际变比的换算关系为：T=0.9+n×1.25%（n=0，1，…，16），发电机端电压上下限制为0.9～1.1pu，节点电压限制在0.95～1.05pu。计算过程中，有功功率基准值为100MW，无功功率基准值为100MVar。 表1和表2为基于GA-MAS优化算法与PSO优化算法的配网节能降耗比对结果，对于IEEE-14节点系统，利用优化算法求解高低压节能设备投入套数，总有功网损最小，同时满足节点电压约束，控制方案合理，达到节能设备优化运行效果。在节点电压控制、发电机有功出力和电压最大最小畸变率等方面，本文所提基于GA-MAS的配网节能降耗系统展现出了优异结果。相比于PSO优化算法，当GA-MAS优化算法实施后，总有功网损降低到0.135pu，而PSO优化算法高达0.138pu，节能设备投入总数减少2套。 图5为GA-MAS和PSO迭代曲线，其中实线表示的是GA-MAS迭代曲线，虚线表示的是PSO迭代曲线。从图中可以看出，GA-MAS算法的收敛精度和速度比PSO算法要好，在算法计算速度方面，经GA-MAS和PSO优化的时间分别为16.3s和34.5s，由此看出，GA-MAS的计算速度和收敛性明显优于PSO算法。 5 工程应用 某企业配电网拥有110kV变电站一座，自备热电厂一座，10kV配电变电站两座。其中，25000kVA容量110±8×1.25%有载调压变压器2台，110kV线路两回，分别从不同的变电站引人为厂区供电，6300kVA容量10±8×1.25%有载调压变压器4台，10kV馈线143回，6kV馈线256回，6300kVA发电机组2台，系统共接人各种高低压节能设备16套。本文所提出的基于多智能体遗传优化算法的配电网节能降耗管理系统，被成功应用于该企业配电网，产生的节能降耗效益如下： 1）减少了有载调压变压器分接头开关的动作次数。变压器分接头由本文所提系统投运前的每台每周3.87次降低到目前的每台每周2.08次，动作次数降低了46%，提高了设备的使用寿命，减轻了检修劳动强度。 2）提高了配电网进线端口功率因数，减少了节能设备投入套数。系统接人运行后，使配电网内总的无功补偿容量降低了33%，同时，功率因数由原来的0.92稳步提升至0.96。节能设备总计投入11套，总共减少了5套。 3）减少电能损耗，取得了明显的节能降耗效果。对配电网三个月网损率的统计分析表明，平均网损率为8.0%，比系统接人运行前同比降低了1.9个百分点，节能降耗效果显著。 4）提高了电压质量。图6（a）～（c）分别为110kV，10kV，6kV节点整点时刻电压曲线，从中可以看出，使用本文提出的配电网节能降耗综合系统，并经过系统优化后，各节点电压得到明显改善，其中110kV节点优化前最低电压为101.1kV，优化后最低电压为105.4kV；10kV节点优化前最低电压9.51kV，优化后最低电压为9.82kV；6kV节点优化前最低电压为5.69kV，优化后最低电压为5.91kV。据统计，系统接人运行的三个月内，地区电网6kV以上母线电压合格率为99.96%，同比提高了0.4个百分点。 6 结论 智能特性是Agent的重要特性之一, 将各种智能算法融合进多Agent系统中, 以提高多Agent系统的智能特性;另一方面, 各种智能算法被嵌入到多Agent系统后, 可以有效地分散计算任务, 使得计算任务在不同的Agent中完成, 从而提高计算的并发性和时间效率[2]。 根据在多Agent系统中, 遗传算法所处的位置不同, 可以将内嵌遗传算法的多Agent计算模型划分为以下3种模式。 1 集中模式 1.1 各Agent的职能和交互 存在一个masterAgent和多个slaveAg ent, 其中, masterAgent负责复杂计算任务的分解和向各slaveAgent分派子任务。各个slaveAgent在地位上是平等的, 它们主要负责给masterAgent收集地理分散的数据, masterAgent与各slaveAgent交互是通过ACL (Agent Communication Language) 进行的, 过程如图1所示。 遗传算法被嵌入在masterAgent中, 待各slaveAgent回传来数据后, 对来自各slaveAgent的的数据运用遗传算法进行集中计算, 进行优劣评价, 从中选择最优的slaveAgent组合并向选中的各个slaveAgent分派计算子任务。当各slaveAgent完成各自的子任务时, 分别向masterAgent回传完成结果, 如图2所示。 1.2 应用场景——网络资源调度 对于一个复杂的计算任务, 往往需要将其先分解为若干个小的子任务, 这些子任务之间存在着一定的依赖关系或可以被并行执行, 任务被表示为T= (t1, t2, …, tm) , m表示子任务的个数。 但每个独立可执行的子任务需要网络当中具有特定功能的资源 (计算机或设备) 来完成。因而, 需要一种网络资源的分配与调度机制, 通过对网络中可以完成某个特定子任务的大量候选资源进行优选和任务分配, 让被选中的各个网络资源协同完成复杂的计算任务。 网络资源在地理上分布在不同的位置, 对于同一类网络资源, 往往存在多个。若将候选资源表示为R= (r1, r2, …, rm) , 其中ri= (ri1, ri2, …, rin) , i∈[1..m], n≥1表示对应于每个子任务的候选资源数。而各个网络资源的实时情况不尽相同如资源的可用性, 完成任务所需的时间、价格等信息, 都要通过配置在每个网络资源上的slaveAgent实时监控和获取[3], 各候选资源对应的slaveAgent表示为:slaveAgent= (slaveAgent1, slaveAgent2 …, slaveAgentm) , 其中slaveAgenti= (slaveAgenti1, slaveAgenti2, …, slaveAgentin) , i∈[1..m], n≥1。 针对一个复杂计算任务分解出的多个子任务, 选择出一个最优 (或较优) 的资源组合, 是典型的组合优化问题, 适合运用遗传算法进行计算[4,5]。 2 分散模式 2.1 Agent的职能和交互 分散模式是指将遗传算法嵌入到各个slaveAgent中, 而masterAgent负责获取各slaveAgent的实时信息并分解计算任务, 给具有子任务求解能力的多个slaveAgent分派计算子任务, 当计算子任务被分派到各slaveAgent中时, 各slaveAgent运用遗传算法完成子任务的计算, 如图3所示。 2.2 分散模式的应用场景 类似于主—从模式并行遗传算法[5], 适合于可以将一个复杂的计算任务分解为独立可并行计算的一系列子任务的情形, 前提是, 被分解的计算任务和分解出的各个子任务具有自相似性并都适合于运用遗传算法进行求解。 任务的分解由masterAgent来完成, 并将分解出的各个子任务派发到网络当中其他具有这些子任务求解能力的计算机进行求解, 从而提高计算的并行性和效率。各个完成子任务求解的计算机都配置有一个slaveAgent, 当完成子任务计算时, 各个slaveAgent向masterAgent回传计算结果, masterAgent合并和整理出最终的计算结果。 该模式的不足之处在于, 当完成各个计算子任务的资源分布较零散时, masterAgent与各slaveAgent的之间的通信速度成为影响整个计算效率的瓶颈, 因此, 该模式只适合计算子任务的计算时间远远大于各Agent之间通信的时间的情形。 3 对等模式 3.1 Agent的职能和交互 与分散模式一样, 该模式是指masterAgent只负责复杂计算任务的分解、子任务的分派和结果合并。遗传算法也是被嵌入在各个slaveAgent中。不同之处在于, 该模式运用粗粒度并行遗传算法的思想[5], 各个slaveAgent在进行子任务计算的过程中, 定期相互交换一部分优秀的个体, 从而改善各个slaveAgent中遗传算法的寻优效率, 如图4所示。 3.2 对等模式的应用场景 该模式中, 各个slaveAgent之间为了定期交换由遗传算法计算产生的优秀个体, 都存在着频繁的数据交换。 因此, 该模式适合于各子任务的计算时间远远大于各slaveAgent之间通信时间以及masterAgent与各slaveAgent通信时间的场合。一般情况下, 局域网中的各计算机之间通信速度较快, 可以将各个slaveAgent配置在局域网环境下, 从而保证计算效率, 克服各slaveAgent之间的通信速度慢的瓶颈。 4 结论 将遗传算法等智能算法加入到多Agent系统中, 可以有效提高多Agent的智能特性。对于较大的计算任务, 可以通过分布在多Agent系统中的各个不同Agent中的遗传算法对任务进行并行求解, 从而改善计算效率。 摘要：在多Agent系统中的一个或多个Agent中加入遗传算法后, 根据遗传算法在各个成员Agent中所处的位置及功能不同, 可以构成不同的计算模式, 各种模式适用于不同的应用场景。重点对比分析和讨论了3种计算模式, 并研究了其各自的适用场景。 关键词：多Agent,遗传算法,融合,计算模式,应用场景 参考文献 [1]张洁, 高亮, 李培根.多Agent技术在先进制造中的应用[M].科学出版社, 2004:1-3. [2]张秋余, 黄鹏, 迟宁.基于JADE的并行遗传算法的设计与实现[J].计算机应用, 2006, 26 (7) :1706-1708, 1712. [3]李瑞生.网格资源管理与调度的多Agent模型[J].科学技术与工程, 2010, 10 (7) :294-297. [4]玄光男, 程润伟.遗传算法与工程优化[M].于歆杰, 周根贵译.清华大学出版社, 2004:29. 关键词：遗传算法,蚁群算法,Agent联盟,混合蚁群遗传算法 一、采用混合蚁群遗传算法求解的出发点 遗传算法和蚁群算法都是解决组合优化等NP问题的较好方法, 而且它们各自存在优缺点如下: 1. 遗传算法 遗传算法的优点: (1) 直接对结构对象进行操作, 不存在求导或函数连续性的限定; (2) 具有潜在的并行性和全局搜索能力; (3) 采用概率随机搜索, 能自动获取搜索知识, 自适应地搜索; (4) 搜索快速, 鲁棒性强; (5) 可扩展性强, 易于同其他算法结合。 遗传算法的缺点: (1) 容易过早收敛于局部最优解; (2) 系统中的反馈信息利用不够, 当求解到一定范围时常常做大量无用的冗余迭代, 求精确解效率低。 2. 蚁群算法 蚁群算法的优点: (1) 采用正反馈机制, 通过信息素的更新收敛到最优解; (2) 是一种分布式的算法, 能够并行地处理问题; (3) 采用概率随机搜索, 自适应地搜索, 融入了人类的智能; (4) 是一种全局优化算法, 能处理多目标优化问题 蚁群算法的缺点: (1) 算法是正反馈, 且转移概率一定, 容易陷入局部最优解; (2) 初始信息素匮乏, 求解速度慢。 由此可以看出, 遗传算法和蚁群算法之间存在优势互补。即:蚁群算法能够适当弥补遗传算法的信息反馈以及提高求解精度, 而遗传算法又能适当弥补蚁群算法的求解速度慢的问题。 二、混合蚁群遗传算法用于求解Agent联盟 由于蚁群算法在缺乏初始信息素分布时, 求解速度慢。而遗传算法能快速收敛, 因此, 在算法的前一阶段, 利用遗传算法的随机性, 产生初始信息素分布, 再利用蚁群算法的并行正反馈求解问题的解。在混合蚁群算法和遗传算法这两种算法时, 采用的是改进的遗传算法和蚁群算法, 以加强算法的求解精度, 加快收敛速度。 1. 遗传算法部分 该部分是算法的第一阶段, 具体设置如下: (1) 编码:采用二进制编码。设M A S中有n个Agent, 记MAS={A1, A2, …, An}。 采用n位二进制编码, 从左往右, 每位编码对应相应序号的Agent, 如果该Agent在联盟内则编码为1, 否则编码为0。如MAS={A1, A2, …, A6}, 联盟{A1, A3, A5, A6}编码为C=101011。 (2) 适应度函数:定义的适应度函数为个体的效用。由于一般遗传算法常采用赌轮法进行个体选择, 这样造成在算法运行初期, 个体差异明显, 这样个别适应度大的个体优势明显, 其后代容易充斥整个群体, 造成早熟;在算法运行后期, 个体差异不明显, 个体之间适应度差别不大, 容易使算法停滞。为改善这种状况, 在遗传算法中加入最速下降算子, 对适应度进行拉伸。这里采用Paul L.Stoffa提出的模拟退火遗传算法 (SAGA) , 来加快收敛, 提高求解精度。即: 其中, 为遗传代数, 为温度, 为初始温度。这样, 在算法前期, 温度较高, 适应度相近的个体产生的后代概率相近;随遗传代数的增加, 温度不断下降, 拉伸作用加强, 个体适应度差异变大, 优秀个体优势明显。 (3) 选择:采用赌轮选择法。 (4) 交叉:采用二点交叉。过程如下: a) 选择父母个体 b) 随机选择交叉点 c) 交叉 (5) 变异:采用逆转变异, 0、1位互相调换。如下: 以迭代次数作为算法结束条件。算法结束后将优化解放入向量中, 并作为蚁群算法的初始信息素分布。以下是算法的第二部分, 采用蚁群算法。 2. 蚁群算法部分 (1) 随机放置m只蚂蚁到n个Agent上。前一步 (即遗传算法) 得到的优化解中每一个代表第i个Agent在优化联盟中。之间用边连接。设置初始信息素分布规律如下: 其中, 为Agent之间边的信息素最小值, 该值由预先设定。为根据遗传算法求解结果转换的信息素值。即:在遗传算法中求得的解中, 如果, 则边的信息素就是。。 (2) 蚂蚁k根据各条边上的信息素量决定转移的方向, 每到一个节点就将该Agent加入到同一个联盟中。蚂蚁k由节点i移动到节点j的概率由式 (2-4) 得到。 当蚂蚁到达节点j时, 就计算当前联盟的能力向量, 如果当前联盟能力已超过任务要求的能力向量, 则该联盟能够完成任务, 蚂蚁停止寻径;否则, 继续下一步的寻径。 (3) 各条边上的信息素随时间而挥发。 三、改进算法 除了上述初始信息素分布的设置, 为了缓解正反馈过程中容易陷入局部最优解, 进化过程中又做了适当改进和调整。 由于基本蚁群算法的路径转移概率使用固定的公式, 在算法运行初期, 如果问题的规模较大, 则蚂蚁很难在众多路径中找出一条较好的路径, 这也是除了初始信息素分布情况缺乏外的另一个问题。为了加快算法的收敛, 蚂蚁路径选择的概率值应当取比较大的数, 这样较好的路径被选择的概率较高, 较优联盟中的Agent容易找到。随着算法的运行, 正反馈的作用越来越明显, 一些路径上的信息素明显高于其他路径, 但这些路径不一定是最优的, 因而容易停滞。这时, 应该减少路径选择的概率, 使解的搜索更多样化, 有利于找到全局最优解。为此, 第k只蚂蚁在节点i选择下一个节点j的规则是: 其中, 均匀分布的一个随机数, 是预先设置的一个阈值, 是服从概率分布的一个随机变量。 为此, 在算法运行初期, 应当尽量减小挥发因子, 采用较小的更新系数;在算法运行后期, 应当尽量增大挥发因子, 采用较大的更新系数。这里, 我们采用如式 (2-7) 的信息素更新规则, 同时借鉴比利时学者Tomas Stutzle提出的MMAS (max-min ant system) 算法的思想, 将各路径的信息素大小控制在之间, 这样可以比较有效地避免算法早熟问题。 其中, 是挥发因子, 是信息素更新系数, 它们满足如下公式: 其中, N为蚁群算法循环的次数。 这样, 在算法运行开始, 在算法运行初期, 比较大, 挥发因子比较小, 信息素更新系数比较小, 这样既有利于信息素浓度大的路径脱颖而出, 又能避免过早收敛。随着算法的运行, 逐渐变小, 逐渐变大, 逐渐变大。在算法运行后期, 比较小, 挥发因子比较大, 信息素更新系数λ比较大, 这样能改善传统遗传算法和蚁群算法后期算法容易停滞等缺点, 加快算法收敛速度。 四、结论 实验结果显示, 混合蚁群遗传算法不论在解的精度还是在时间上都明显优于其他两种算法, 求解效率较高, 运用于求解Agent联盟, 能较高效的找到优化解, 是多Agent联盟协作求解的一个有效方法。 参考文献 [1]胡山立, 石纯一.给定限界要求的联盟结构生成[J].计算机学报.2001, 24 (11) :1185-1190. [2]徐晋辉.Agent模型与联盟机制研究[D].北京:清华大学, 2000. [3]史忠植.知识发现[M].北京:清华大学出版社.2002. 遗传算法(GA)是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法。它是模仿自然界生物进化过程中“物竞天择,适者生存”的原理而进行的一种多参数、多群体的并行优化方法,其应用优势在于处理传统搜索方法难于解决的复杂的非线性问题。经过20多年的发展,遗传算法已经在组合优化、生产调度、函数优化、机器学习、图象处理等许多领域得到成功的应用,并显示出其良好的性能。 通过遗传算法求解问题时,人们总是期望在尽量短的时间内达到或尽可能接近问题的全局最优解。当遗传算法停止时,往往只是取出种群中最优个体作为遗传算法的结果。这是因为,群体中最优个体和全局最优解之间的亲和度[1]要大于群体中其他个体和全局最优解之间的亲和度。因此,在遗传算法中如何利用每一代的最优个体所包含的特征信息去产生下一代更优秀个体是其必须考虑的问题。Eiben等用Markov链证明了保留最优个体(Elitist Preserved)遗传算法的概率全局收敛性[2];Rudolph用齐次有限Markov链证明了带有选择、交叉、变异操作的经典遗传算法收敛不到全局最优解[3]。但是,若在遗传算法中保留每一代的最优个体,则算法将收敛到全局最优解。这些都表明种群最优个体对算法的重要意义。在遗传算法中采用最优保留策略可以保证算法的全局收敛性。因此,对保留下来的最优个体如何利用,以提高算法性能则需要进一步研究。 蜜蜂进化型遗传算法(BEGA)[4]从蜜蜂的繁殖进化过程中抽取出适合遗传算法的一些机制并融入算法之中。BEGA充分利用种群中最优个体对种群的进化作用,同时,为维持个体的多样性,引入了蜜蜂繁殖过程中“外来种群”的思想,在算法性能上较标准遗传算法有了很大提高。本文受到启发,提出一种多蜂群进化型遗传算法(MBEGA),算法中保持多个蜂群同时进化,蜂王可以选择同一蜂群或其他蜂群中的雄蜂进行交配,蜂王在其所处蜂群中采用相似性判断,以抑制其中产生过于接近蜂王的个体,最后选取多个蜂群中最优的蜂王作为问题的解。这样,既提高了种群的多样性,又避免了进化过程中的“早熟”现象,通过对函数优化问题的求解表明,这种MBEGA算法能够有效提高遗传算法的性能。 1 多蜂群遗传的抽象模型 关于蜂群的数量:蜂群数量设为M(2～50),以模拟自然界中的多个不同蜜蜂群体,在并行计算中可以将M理解为并行的处理机个数。 关于种群的构成:为降低算法复杂度,将工蜂和雄蜂统一看作普通蜜蜂,每个蜂群由一个蜂王和若干普通蜜峰构成。在与蜂王交配产生后代时,普通蜜蜂被当作雄蜂;在受到蜂王信息素抑制时,普通蜜蜂被当作工蜂。普通蜜蜂数量设为N(30～100)。 关于参与交配的雄蜂选择:在交叉概率Pc的作用下,通过选择算子按照比例γ从本种群中选择γ·N/2个个体;将其余M-1个种群看作一个整体,从中随机选择(1-γ)·N/2个个体,最后这N/2个选中个体作为选中雄蜂参与同蜂王的交配。 关于蜂王和雄蜂交配:蜂王作为种群中的最优个体,与选中的N/2雄蜂个体交配产生子代C。 关于争夺蜂王:C中的最优个体与此蜂群的蜂王竞争,失败者不是消亡(死亡或逃走),而是成为子代C中普通的蜜蜂个体,胜利者晋升成为新蜂王。 关于新蜂群:新蜂王与子代C构成新的蜂群。 关于蜂王信息素抑制:蜂王与蜂群中的工蜂逐个比较,若工蜂与蜂王间的海明距离小于阈值τ时,认为此工蜂威胁到蜂王的地位,驱逐此工蜂,并用随机算法生成新的工蜂个体补齐蜂群。 2 多蜂群遗传算法 2.1 算法描述 设定M表示蜂群个数;N表示种群大小;Bee(i,j)表示第i个蜂群中的第j个个体;Bee(i).Queen表示第i个蜂群中的蜂王;γ表示本蜂群中选择雄蜂个体的概率;τ表示抑制的阈值;Pc表示交叉概率;Pm表示变异概率。 2.2 编码方案 针对函数优化问题的特点,采用二进制编码,每个变量采用20位的0/1串表示,包括1个符号位,若干整数位(根据约束条件中的取值范围决定,若-5≤x1,x2≤5,则整数位取3),剩余位表示小数位,为解码方便,编码采用反码方案。 如染色体编码: 0011100000000000000010010011001100110000将被解码成x1=3.5,x2=-0.199 951。 2.3 杂交算子 采用均匀模板杂交算子:对选出的2个个体,随机产生一个与其串长相同的0/1串作为模板,当模板中某基因位为1时,母体中两个个体的相应位基因进行杂交互换。杂交过程如下所示。这种杂交算子对个体串中的每个基因位以等概率杂交,以等概率对每个解空间进行搜索,提高了搜索的并行性与效率。 模板:10001101000011010100 蜂王:01110010000010110010 雄蜂:11001000001011010000 子代1:11111010000011110010 子代2:01000000001010010000 2.4 变异算子 采用级联单点变异:首先将个体串拆分成每一个参量子串;然后对各子串进行单点变异;最后将子串拼接成总个体串。变异过程如下所示: 变异前: 0111001000001011000000101111001100000000 拆分: 01110010000010110000 00101111001100000000 分别在3,4位变异: 01100010000010110000 00100111001100000000 拼接: 0110001000001011000000100111001100000000 这种变异算子使每个解空间都获得相同的变异概率,不易造成参量解之间精度差异过大。同时,每个解的变异只限一位,不易因随机变异面积过大而造成个体适应值振荡,具有较好的稳定性。 2.5 选择算子 在交叉概率Pc的作用下,选择算子选出与蜂王进行交叉运算的雄蜂。算法采用两种选择方式:轮赌选择法、随机选择法。 例如:当给Bee(i).Queen选择雄蜂时,用轮赌选择法从Bee(i)蜂群中选出γ·N/2个个体;用随机选择法从其余的M-1个蜂群中选出(1-γ)·N/2个个体。 2.6 抑制算子 算法计算蜂王与本蜂群中普通蜜蜂的海明距离d(x,y)=∑(x[i]⊕y[i]),若d<τ,说明蜂王与蜜蜂个体间的相似度太高,将来杂交时难以产生相异子代,蜂王抑制该个体,将其驱逐,然后采用随机算法重新产生新的蜜蜂个体加入蜂群。抑制算子可以避免蜂群中普通蜜蜂与蜂王间的血缘太近,相似度太高,而在杂交时产生近亲繁殖,难以产生有效的相异子代,对进化无法提供有效的支持;新蜜蜂的引入,增加了蜂群的生物多样性,提高了杂交效率,有利于跳出局部最优解。 2.7 停止准则 定义1s∈S是规模为N的种群,种群s的适应度定义为该种群中最优个体的适应度。 为考察算法的性能,排除遗传算法中大量随机操作的影响,在统计学原理上采用平均进化代数和平均最大适应度[4]两个性能指标对算法进行评估。 针对种群最优个体的进化能力,为衡量算法优劣,采用两种不同的停止准则: 停止准则1:给定整数T≥1,如果 停止准则2:种群的适应度与全局最大适应度的差小于等于0.001。为保证各种不同算法均在有限迭代次数内停止,设最大迭代次数为2 000,若算法在迭代2 000次后,仍不能收敛到全局最大适应度,认为该次实验失败,否则认为成功。 2.8 改进措施 在BEGA[4]基础上,MBEGA提出两种改进策略: (1) 将蜂群个数增加到多个,雄蜂的选择来自于其他蜂群而不是随机产生。 (2) 根据蜂王分泌信息素抑制工蜂卵巢发育的生物学特点,引入抑制算子,驱逐与蜂王个体差异小于阈值的蜜蜂个体。 第一个改进策略主要针对于BEGA中外来雄蜂随机产生的问题。在BEGA中随机产生的个体虽然能保证个体多样性,但这些参与交配的个体带有不可预知性,无法保证其质量,其产生的子代可能进化,也可能退化,带有盲目性,与生物学上“优胜劣汰”的基本思想相矛盾。 而在MBEGA中,外来雄蜂来自于其他蜂群,这样既避免了单个蜂群内部繁殖带来的“早熟”问题,又避免了随机蜂群的不可预知性,并且来自于其他蜂群的雄蜂会携带其他蜂群中的优良基因片段产于参与本蜂群的进化,对进化具有指导意义。 此外,MBEGA中引入多个蜂群能提高算法开采解空间的能力。因为MBEGA中规定多蜂群中所有的蜜蜂(包括蜂王和普通蜜蜂)都必须互不相同,这种限制使多个蜂群在同时进化时,其中的蜜蜂个体分布于解空间的不同角落上,这样不但扩大了对解空间的搜索范围,而且能减少陷入局部最优的可能性。 在算法的实现过程中,发现存在这样一种问题:由于蜂王是蜂群中的优势个体,蜂群进化若干代后,蜂群中的普通蜜蜂都会与现任蜂王存在直接或间接的血缘关系,蜂群中的生物多样性不足,其中与蜂王个体差异很小的个体与蜂王进行杂交时,杂交算子局部搜索能力下降,无法顺利产生出不同于蜂王的后代,导致算法效率下降或失败。第二个改进策略专门用于解决这一问题。 例如:假设算法采用16位二进制编码,蜂王与雄蜂如下,则均匀模板杂交很生成有效的模板序列,使杂交后的子代与父代相异。 蜂王:0100101100010101 雄蜂:1100101100010101 通过计算海明距离,对这种不利于进化的个体进行驱逐,由随机算法重新构建新的个体,可以有效地保持蜂群的生物多样性,帮助算法开辟新的搜索空间,提高算法的勘探能力。 3 实验结果与分析 3.1 实验设计 为验证MBEGA的有效性,选择五个典型函数进行性能测试,并与简单遗传算法(SGA)、最优保持遗传算法(EGA)[5]及BEGA进行了比较。 典型测试函数如下: 其中:f1,f2,f3,f4,f5的适应度函数分别为 实验中,采用二进制编码,除f2个体长度为20,其余均为40。种群规模N=50,Pc=0.85,Pm=0.01,蜂群算法中,γ=0.2;多蜂群算法中,M=20,τ=4,T=5。 针对平均进化代数、平均最大适应度两个性能指标,分别根据不同的停止准则做了两个实验。 实验一:采用停止准则1与时间边界法结合。若算法在连续T代中平均适应度值没有发生改变或算法已运行400 ms(考虑到MBEGA需要同时优化20个种群,将时间适当延长为2 000 ms)停止。SGA,EGA,BEGA和MBEGA分别对每个函数独立求解1 000次,计算其平均最大适应度,实验结果如表1所示。 实验二:采用停止准则2。SGA,EGA,BEGA和MBEGA分别对每个函数独立求解1 000次,计算其平均进化代数(只包含成功实验)和成功率,试验结果如表2所示。 3.2 实验结果及分析 实验结果及分析如表1,表2所示。 与SGA相比,EGA,BEGA和MBEGA增加了寻找最佳个体和替换最佳个体的操作,BEGA额外增加了随机生成新个体操作,MBEGA额外增加了抑制操作,并且需要同时对20个种群进行优化。虽然BEGA与MBEGA在选择候选个体时减少了一半的数量,但从总体上来看,在每次迭代过程中花费的时间超过了SGA和EGA,因此单纯比较算法寻优的时间没有实际意义。为比较的合理性,实验一中设定了算法运行时间的上限(对MBEGA做了适当延长)。表1的结果表明,在规定的时间内,MBEGA得到的解都优于SGA,EGA,在部分函数上优于BEGA,因此从平均最大适应度来看,MBEGA的优化效果最好。 实验2中的成功率是一种对算法在规定时间内优化到全局最优解的概率统计。从表2可以看出,在规定解的精度(0.001)要求下,SGA,EGA在函数f1上基本失败,在其他函数上的收敛速度(平均进化代数)也很慢,BEGA的收敛速度和成功率都有所提高,而MBEGA在收敛速度和成功率上都获得了最好的结果。因此从收敛速度和成功率上来看,MBEGA的优化效率最好。 根据表1和表2的结果可以看出,不论是优化效率还是优化效果,MBEGA均优于SGA,EGA和BEGA。 4 结 语 受BEGA的启发,本文提出了一种新型的遗传算法——MBEGA。结合蜜蜂群体的生物学特点,针对BEGA的不足,提出了两种改进措施:多蜂群同时优化,提高算法在解空间中的勘探能力,杂交个体部分来自于其他蜂群提高优化效率和抗“早衰”能力;引入抑制算子增加蜂群的生物多样性,提高了跳出局部最优的能力。最后的实验结果表明,MBEGA很好地提高了BEGA的优化效率和优化效果,因此MBEGA是一种提高遗传算法性能的有效改进算法。 参考文献 [1]王煦法,张显俊,曹先彬,等.一种基于免疫原理的遗传算法[J].小型微型计算机系统,1999,20(2):117-120. [2]Eiben A E,Arts E H,Van Hee K M.Global Convergence ofGenetic Algorithms:An Infinite Markov Chain Analysis[A].Parallel Problem Solving from Nature[C].Heidelberg,Berlin:Springer-Verlag,1991:4-12. [3]Rudolph G.Convergence Analysis of Canonical Genetic Al-gorithms[J].IEEE Trans.on Neural Networks,1994,5(1):96-101. [4]孟伟,韩学东,洪炳镕.蜜蜂进化型遗传算法[J].电子学报,2006,34(7):1 294-1 300. [5]Goldberg D E.Genetic Algorithms in Search,Opti mizationand Machine Learning[M].New York:Addison-Wesley,1989. [6]梁艳春,周春光,李寿范.基于遗传算法的Rosenbrock函数优化问题的研究[J].软件学报,1997,8(9):701-708. 随着市场竞争的加剧,企业承接的项目数量过度增长。由于人力、物力、财力等因素,不能按时完成承接的所有项目的风险日益提高。如何最大限度地选择承接的部分项目并合理调度,这已成为企业项目管理的科技核心难题。针对于此,文献[1,2]中将各项目视为整体,探讨了多项目资源配置问题,获得其优化模型及求解的智能算法。这些研究为本文将各项目的任务流程规划问题和项目层资源配置问题统筹考虑奠定了基础。为此,本文探讨资源限制下含承继约束的多项目多任务选择计划问题的数学模型,并设计求解此模型的多项目多任务选择计划免疫遗传算法MPTSIGA(Multi-project and Multi-task Selection Planning Immune Genetic Algorithm)。数值实验显示所获模型是合理的及算法是有效的。 1 问题描述及模型设计 设某企业在T天内有N个待选项目,项目集为C={ci|i=1,2…,N},C中部分项目之间存在紧前关系(注:如果ci是cj的紧前项目,那么cj只能在ci完工之后才能开始);每个项目均有M个任务,在同一项目内,任务与任务之间满足时序约束;Si表示ci的所有紧前项目构成的集合。cis表示ci的第s个任务,Pik表示ci的第k个任务的所有紧前任务构成的集合(注:在ci内,如果cis是cik的紧前任务,那么cis完工之后cik才能开始)。对于ci,利用bi代表其是否被选中执行,若被选中执行,则bi=1,否则,bi=0。用bij表示ci在第j天是否被选中执行,若被选中执行,则bij=1,否则,bij=0。用ajis表示ci的第s个任务在第j天是否执行,若执行,则ajis=1,否则,ajis=0。si表示ci的开始时间,tis和dis分别表示ci的第s个任务的开始时间和执行时间。为确保ci在合同截止日期内完成,则si≤ei-Ti,其中,ei为ci的合同截止日期,Ti为ci的持续时间。假定企业有R种资源可供使用,第k种资源在第j天的总限量为Rjk,第k种资源在T天内总限量为Rk。ci的第s个任务在单位时间(天)内使用第k种资源量为risk,则第k种资源在第j天的资源约束为: 在T天内,第k种资源的总资源约束为: 第k种资源的资源利用方差为: 于是,多项目多任务选择计划数学模型(P)如下: 式中, 2 算法描述及算子设计 2.1 算法描述 (1)抗体编码 抗体由项目层编码和项目的任务层编码组成,记为Ab≡(Ab1,Ab2),在此, 其中,C=c1c2…cN表示项目编号序列;S=s1s2…sN表示项目序列中各项目的对应开始时间;B=b1b2…bN表示项目序列中各项目是否被选中的二进制串。J=J1J2…JN表示各项目的任务序列的排序,Ji是ci的任务序列排序;E=E1E2…EN是各项目的任务序列的对应开始时间,Ei是Ji的开始时间。Ji=ji1ji2…jiM表示ci的任务调度序列;Ei=ei1ei2…eiM表示ci中任务调度序列的对应任务的开始时间,如ei1是ji1的开始时间。 (2)抗体亲和力 对于抗体群X中的Ab,其在群体中的重要程度用亲和力度量。亲和力函数设计为: 其中,f(x)表示抗体x在模型中对应的决策方案获得的目标函数值。基于抗体亲和力及免疫系统中的克隆选择、细胞繁殖、亲和突变、记忆细胞获取等机理[3],MPTSIGA描述如下: Step1置n←1,依据抗体生成规则,产生规模为N的初始抗体群An及规模为m的初始记忆池Me; Step2计算每个抗体对应的目标函数值和亲和力; Step3对当前群体An中各抗体繁殖2个克隆,获等规模的克隆群Bn和Cn; Step4对Bn和Cn分别实施基因重组和基因漂移操作,获B'n和C'n;然后对C'n执行变异操作获C″n,计算B'n、C″n中每个抗体对应的目标函数值和亲和力; Step5将An、B'n、C″n进行组合,获组合群体Dn,选择N个亲和力较高的抗体进入群体A'n+1; Step6取A'n+1中亲和力较高的m个抗体插入Me中,保留Me中亲和力较高的m个记忆细胞; Step7依据抗体生成规则产生d个新抗体代替A'n+1中亲和力较低的d个抗体,获下一代群体An+1; Step8若满足终止条件,则输出结果,并结束;否则,置n←n+1,返回Step 2。 2.2 免疫算子设计 (1)抗体生成规则 依次对各项目按权值从大到小排序且保证满足时序约束,设所获序列为C=c1c2…cN,按该顺序,从前往后对每个项目进行安排。具体步骤如下: Step1检验ci是否满足总资源约束,如果满足,则进行下一步;否则,检验ci+1; Step2对ci内的各任务进行拓扑排序[4],生成任务序列ji1ji2…jiM。对ji1从第一天开始进行安排,如果ci的紧前项目和ji1的紧前任务在第一天已完成,且ji1从此天开始,在ji1不间断执行时间内都满足每天的资源限制量,则ji1开始的时间ei1为第一天,如果不同时满足以上的所有条件,则检验第二天,按照以上方式依次进行检验,直到确定ji1的开始时间ei1为止; Step3按照与Step2同样的方法确定ji2…jiM的开始时间ei2…eiM,由ji1ji2…jiM的开始时间及持续时间确定ci的开始时间及完成时间,如果满足合同约束,则bi=1;否则bi=0,且此项目的开始时间和结束时间及各任务的开始时间都规定为0。 (2)基因重组 给定抗体群X中抗体Ab,此群体中最好的抗体设为AbF,另外,从记忆池中随机选择一个抗体设为AbM,用C、CF和CM分别表示Ab、AbF和AbM中的项目编号序列基因块,不妨设C=c1,c2,…,cN,CF=c1F,c2F,…,cNF,CM=c1M,c2M,…,cNM,Ab、AbF、AbM经由基因重组产生AbS的基因块CS=c1S,c2S,…,cNS时,AbS中JS的基因继承Ab中的任务序列块J中与CS=c1S,c2S,…,cNS中项目对应的任务序列基因。CS的产生方式如下: Step1对C、CF、CM,随机产生两个整数α和β(1<α<β<N)作为重组点; Step2CS的前α个基因继承Ab的基因块C的前α个基因; Step3从AbF的基因块CF中去掉出现在CS中的第1到第α位置上的基因,然后在CF中依次选取没被删除的β-α个基因依次放入CS中的第α+1至第β位置上; Step4同上,从AbM的基因块CM中去掉出现在CS中的第1到第β位置上的基因,然后在CM中依次选取没被删除的N-β个基因依次放入CS中的第β+1至N位置上。进而,CS取代C。 注:以上基因重组所获个体是有效个体,可利用文献[5]进行证明。 (3)基因漂移 对于项目序列块C,首先随机产生一个整数r(1<r<N)作为漂移点,然后找出所有与漂移点处权值相等的项目,漂移点处的项目在此范围内进行随机移动,如果满足项目的紧前约束则基因漂移,否则不进行基因漂移。对于基因块J中Ji不进行基因漂移,仅随项目序列进行整体移动。 (4)变异操作 对于基因块J中的Ji=(Ji1,Ji2,…,JiM),首先随机产生一个整数r(1<r<M)作为变异点,然后确定第r个变异点基因的所有紧前任务在此基因块中的最后位置r1及所有紧后任务在此基因块中最前面的位置r2,在r1和r2之间随机选择一个基因座r',将变异点基因插在r'位置前[6]。 3 数值实验 鉴于将项目的流程规划与项目群选择规划统筹考虑的研究和这类问题的智能优化算法很少报道,在此选取三种基于优先准则的启发式算法[7](Long T、MaxR、MaxTS)与MPTSIGA进行比较;三种启发式算法仅各自执行1次;为减少随机性对算法性能的影响,将MPTSIGA对以下问题独立运行30次;该算法的参数设置为:最大进化代数Max=200,群体规模N=30,记忆细胞数m=6,新成员个数d=4。 问题设某企业在T=120(天)中有40个项目待选择执行,每个项目含20个任务,且各项目分别消耗4种资源(在此省略相关数据),此4种资源的权值分别为0.2,0.2,0.3,0.3,其在单位时间内提供的资源量分别为20、20、20、20,且在T天内提供的总资源量分别为2000、2000、1900、1900。现要求寻找一种最佳方案,使得各种资源在T天内分配尽可能均衡且得到最大利用。 MPTSIGA与Long T、MaxR、MaxTS所获统计结果如表1所示(在此省略各任务的相关数据);MPTSIGA的平均搜索曲线如图1所示。 由表1可知,四种算法都获得了问题的可行决策方案。三种启发式算法中MaxTS的效果最好,这说明不同优先规则的启发式算法对同一问题的处理效果不同;MPTSIGA在30次独立运行中,所获结果说明该算法获得的可行决策方案比三种启发式算法获得的方案更能充分利用资源且选中的项目更多,其原因在于三种启发式算法是确定性算法,它们仅能获得可行解,而MPTSIGA是随机搜索算法,基因重组、基因漂移和变异模块有机结合使算法能较快找出满意的解。图1是MPTSIGA在30次独立运行过程中获得问题的目标函数值的平均搜索曲线。此图表明,该算法的多样性好、收敛速度快,没有陷入局部搜索,并且随着进化代数的增加还能得到更好的决策方案。 4 结论 针对企业中多项目多任务选择计划问题,在已有文献基础上,进一步考虑项目内部各任务的规划问题,并建立相应的规划模型,进而,借助遗传算法及免疫学的相关机理设计免疫遗传算法对其求解。数值实验结果说明本文建立的模型是合理的以及算法是有效的。由于多项目多任务选择计划问题较为复杂,不管是模型的建立还是算法的探讨,均需做进一步深入探讨。 摘要：针对多资源受限下项目群选择计划及项目流程调度问题,依据项目的权重和承继约束,将项目群按权值从大到小进行排序,各项目内部的任务分别采用网络计划图进行拓扑排序,并以资源约束和合同期等因素为项目选择标准,建立多项目多任务选择计划的资源配置数学模型。进而,在遗传算法中引入免疫系统的记忆性和多样性功能,设计免疫遗传算法求解所获模型的最佳决策方案。比较性的数值实验结果说明了模型的合理性和算法的有效性。 关键词：多项目多任务选择计划,资源均衡,承继约束,拓扑排序,免疫遗传算法 参考文献 [1]张著洪,曾茜.多资源受限多项目选择计划模型及其智能决策方案[J].数学的实践与认识2,009,39(19):9-19. [2]雷宏,张著洪.多项目选择计划及其两层决策免疫遗传算法[J].计算机工程与设计,20103,1(9):1900-1994. [3]黄席樾,张著洪,等.现代智能算法理论及应用[M].科学出版社,2005. [4]邓林义,林焰,金朝光,等.资源约束下多项目调度的拓扑优化方法[J].系统仿真学报2,007,8(16):3846-3849. [5]Hartmann S.A competitive genetic algorithm for resource-constrained project scheduling[J].Naval Research Logistics,1998,45:733-750. [6]Boctor F F.Resource-constrained project scheduling by simulated an-nealing[J].International Journal of Production Research,1996,34:2335-2351. 鉴于遗传算法在求解组合优化问题上的优势[6]，笔者用遗传算法求解多跑道航班调度问题。 1 多跑道航班调度的数学模型 1.1 多跑道航班排序染色体表示 假设航班排序的染色体表示可以描述为A[k](k=1,2,…,n)。如图1所示。其中A[k]是染色体第k个遗传坐标位置上的遗传因子,该遗传因子是航班序列中的某一航班Ai(i=1,2,…,n),航班Ai将唯一对应一个进场航班进、离港时刻。W条跑道的排序如图2所示。各跑道航班数目不尽相等,这是由于航班进港时间、离港时间及滑行路线调度所引起的。航班排序的染色体表示(图1)可以唯一对应航班序列(图2)。 1.2 航班调度的适应度函数 航班调度的适应度函数为： 其中，Fi是子适应度函数,αi是加权因子αi>0,m是子适应度函数的个数，FiA[·]是如图2所确定的航班序列。这里假定,函数F值越小,染色体的适应度就越高;F越大，适应度就越低。式(1)中函数的极小值,表明适应度函数高,航班排序处于最佳状态。 航班排序的子适应度函数,一方面由上级机场部门的要求确定,另一方面由机场运转要求确定这些子适应度函数,如下： 1)最少交叉接发时间,即在同一跑道上尽量减少进、离港航班上下行交叉的情况,提高安全可靠运转。 假设C【i,in】C【i,out】，是相应于图1中航班Ai的进港(着陆)、离港(起飞)航班,这是一个0,1变量,即C【i,in】=1为上行进港变量，C【i,in】=0为下行进港变量;C【i,out】=1为上行离港变量，C【i,out】=0为下行离港变量。(所谓上行下行是指同一跑道相对两个方向，这里借用列车运行中的术语)。 航班排序问题中最少交叉进离港航班的子适应度函数,可以描述为进离港变量的异或非关系之和,即 式(2)中,符号茌是异或关系,符号—是非关系。航班排序的异或非关系总和的极小化,表明在任一跑道上的航班将尽可能地在上行或下行方向滑行,以保证先行航班与后继航班不在同滑行路线方向，双求和符号中内层求和上标z是根据每一跑道可以容纳的航班列数确定的,机场内w个跑道中每个跑道确定的z不尽相同。并且,实际确定内层求和上标z的,是从第1跑道、第2跑道……,依次试凑得到的。内层求和表明某一跑道航班排序的异或非之和,外层求和表明所有跑道航班排序异或非之和。 2)航班最小滑行时间,反映航班滑行效率的重要指标,即 其中，h[i,in]，h[i,out]是相应于图1中航班滑行序列A[i]的进港、离港时间。子适应度函数F2的极小值，表明后继航班A[i*w+j]进港时间h[i*w+j,in]与先行航班A[(i-1)*w+1]离港时间h[(i-1)*w+j,out]之差总和最小，使航班滑行时间最小。双求和符号中内层求和上标z的物理意义和计算方法如式(2)所述。内层求和表明某一跑道航班排序的最小进、离港时间之和，外层求和表明所有跑道航班进离港时间之和。 3)航班滑行始末时间约束,即某一跑道上相邻航班进、离港时间限制,到场先行航班A[i]离港时间与后继航班A[i+w+1]的进港时间之差不能小于安全时间Cij，最小时间间隔矩阵如图3所示。 其中，h[i,*]如式(3)所述。 1.3 约束条件 首先定义如下变量:A={1,2,...,n}为航班的集合,Ain奂A(进场降落航班集合),Aout奂A(离场航班集合;L为跑道长度;Vtmin(i=1,2,...n)表示航班i的最小速度;Vtmax(i=1,2,...,n)表示航班i的最大速度;hi表示航班i到达的实际时间;Ehi表示航班i可能到达最早时间;Lhi表示航班i可能到达的最晚时间;二元变量yij=1表示航班i在j之前到达，否则为0。约束条件为： (5)式表示航班的实际到达时间一定在最快到达时间和最慢到达时间之间;式(6)和式(7)分别求出最快和最慢到达时间;式(8)确保两架航班不会相互超过;式(9)表示变量y只能在0和1中取值。其他的约束条件如两架航班不能相遇;相邻两架航班保持最小安全间距已分别包含在式(2)、(4)中。 2 多跑道航班调度的遗传算法 2.1 初始种群生成 航班排序的初始状态,选定染色体群体初始状态为m=10个，航班的序列用试凑方式,并且主要考虑到满足式(4),即一条跑道上的航班,先行航班与后继航班不能接尾,直接组成染色体群体初始状态A[1],A[2],…A[n]其余(m-1)个染色体由A1,A2,…An均匀分布随机产生。 2.2 遗传算子 1)选择操作：航班排序的选择操作采用删除保存策略,淘汰适应度低的航班排序,保留适应度高的航班排序,以保持染色体群体m=10个的规模。 2)交叉操作：航班排序的交叉操作采用多点顺序交叉,即在航班排序的染色体结构中,进行多个区间内的交叉操作。具体作法是以7k(k=1,2，…,15)为中心点,以[7k-3,7k+3]为遗传区间,进行第k个区间的顺序交叉。所谓顺序交叉,即在染色体某一个遗传坐标区间内,其中所有遗传因子的排列次序全部反转过来,产生子代染色体。 3)变异操作：航班排序的突然变异操作采用多点移位(shift)和单点逆位方式(inversion)[4].具体作法是以7k(k=1,2，…,15)为中心点,以[7k-3,7k+3]为遗传坐标区间,进行15个区间的移位操作;以航班排序的染色体结构为一个整个区间,以第n个遗传因子(航班)配置于第1个遗传坐标，第1,2,…n-1个遗传因子依次向后推移,进行单点逆位操作。航班排序遗传算法控制比例参数选作P1:P2:P31:P32=10:5:1:1。其中P1是问题的生存染色体数目比例因子,P2是交叉操作数目比例因子,P31是突然变异中移位操作数目比例因子,P32是突然变异中逆位操作数目比例因子. 在前述讨论的适应度函数(1)-(3)和约束条件(4)-(9)基础上,可以采用遗传算法步骤进行航班排序问题的计算。约束条件(4)可以处理为：凡是不符合约束条件的航班排序,均作为适应度最低的情况淘汰。 对不能满足式(5)的航班，即hi 3 实验参数及仿真结果分析 实验数据取于某机场下午15时10架航班的时刻表。该机场共有3条平行跑道共有n=10架有效进离港航班，将航班排序设置成n=10个遗传因子,如图1的染色体。10架航班的进离港时刻均已由上级部门确定，将这些航班由北京时间为零计时,依到场时刻先后排列,其遗传因子排序为A1,A2,…A10。其航班时刻如表1所示。表中的ETA0、ETA1、ETA2分别为各飞机在跑道0、1、2上的预计降落时间(格式为：hhmms)。 航班排序问题的遗传算法仿真实验是在微机上进行的,采用C语言编程。遗传算法的子适应度函数的加权因子α=(10,10)，遗传算法的终止条件,采用有限遗传代数方法终止。遗传过程达到30000代。最后仿真结果如表2所示。 由表2的仿真结果可以看出,最终遗传算法与传统的FCFS方法调度结果相似,但有部分变动。在遗传算法中综合考虑飞机在各跑道上的具体情况,可以使得所有飞机的总延误尽量减小。仿真结果显示,FCFS排序系统总的延迟时间是290秒;遗传算法排序总的延迟是254秒。从本文方法的计算结果可以看出,大多数飞机的降落时间STA等于或接近其在相应跑道上的预计降落时间ETA,不要求各跑道上的飞机连续降落,这样可以使飞机在确定降落跑道后,基本按照标准降落程序完成降落,不需管制员付出太多精力对其进行复杂的调度。 摘要：该文使用遗传算法对多跑道进出港航班进行优化调度。算法用染色体表示多跑道航班排序,适应度函数的构建综合考虑了航班的各种约束条件,通过选择、交叉、变异得到优化输出。仿真结果表明了遗传算法用于航班调度的可行性。 关键词：航班调度,组合优化,遗传算法 参考文献 [1]Beasley J E,Krishnamoorthy M,Sharaila Y M,et al.Scheduling aircraft landing--the static case[J].ransport Scince,2000,34:180-197. [2]Beasley J E,Sonander J,Havelock P.Scheduling aircraft landings at London Heathrow using a population heuristic[J].Journal of the Operational Research Society,2001,52:483-493 [3]Cheng V H L,Crawford L S,Menon P K.Air traffic control using genetic search Techniques[C]//Proceedings of the1999IEEE Inter-national Conference on Lontrol Applications,1999,1:249-254. [4]John E.Fuzzy reasoning-based sequencing of arrival aircraft in the terminal area[C]//AIAA Guidance,Navigation and control Confer-ence,New Orleans,LA,1997:1-11. [5]徐肖豪,黄宝军.终端区飞机排序的模糊综合评判方法研究[J].航空学报,2001,22(3):259-261.多Agent遗传算法 第4篇
多Agent遗传算法 第5篇
多Agent遗传算法 第6篇
多Agent遗传算法 第7篇
多Agent遗传算法 第8篇
多蜂群进化遗传算法 第9篇
多Agent遗传算法 第10篇
基于遗传算法的多跑道航班调度 第11篇