基于并行遗传算法和agent的组合优化研究

基于并行遗传算法和agent的组合优化研究

徐斌董红斌

(哈尔滨师范大学计算机科学与技术系,黑龙江哈尔滨150080)

摘要：针对并行遗传算法中计算资源的分配问题,采用遗传算法和多智能体技术相结合的方法,实现了基于粗粒度的并行GA算法结构，该方法有利于改进遗传算法的性能,提高遗传算法搜索的效率.

关键词：遗传算法；多智能体；并行处理

1概述。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。遗传算法经过多年的研究与发展，取得了许多的应用和发展，并行性与遗传算法的结合，大大促进了遗传算法的发展。在遗传算法的并行化研究方面，提出了两大著名的并行模型，即粗粒度并行模型[2]和细粒度并行模型。在基于粗粒度的并行模型中引入agent,采用multi-agent方法实现了子群体内部的遗传操作及子群体之间的交互，这种方法将极大地减少通讯开销并充分发挥并行遗传算法的求解问题的能力。

2并行遗传算法。遗传算法的运算过程中，适应度的计算是很费资源的。因此,随着求解问题的复杂性及难度增加，提高遗传算法的运行速度便显得尤为突出。所以,遗传算法跟并行性的结合，是自然的，也是必要的。对于并行遗传算法，总的来说，并行遗传算法的实现有如下几种方案。2.1全局型。全局型又称主从式模型，顾名思义，并行系统分为一个主处理器和若干个从处理器。主处理器负责整个种群的运行，各个从处理器处理来自主处理器的个体主要负责个体的适应度计算，并把结果发给主处理器全局处理。全局型并行遗传算法模型最大的优点是简单，保留了传统遗传算法的搜索行为，因而可直接应用遗传算法的理论来预测一个具体问题能否映射到并行遗传算法上求解。对于适应度估值操作比其他遗传算子计算量大的多时，它是很有效的，并且不需要专门的计算机系统结构。2.2分布式型。这种模型又叫独立型、粗粒度模型或者孤岛模型，该种模型是对传统遗传算法的扩展，与全局型不同的是：它将种群划分为多个子种群与各个对应的处理器，每个处理器进行单独的完整遗传算法操作。定期互相交换最佳的算子，除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理各个分处理器之间的个体交换。在粗粒度模型的研究中，要解决的重要问题是参数选择,包括:迁移拓扑、迁移率、迁移周期等。典型的迁移率是子种群数目的12%到18%之间。迁移周期决定了个体迁移的时间间隔,一般是隔一定的代数迁移一次。通常，迁移率越高,则迁移周期就越长。有的采用同步迁移方式，有的采用异步迁移方式。迁移选择负责选出迁采用随机选取和替换的。2.3细粒度模型。也叫分散型模型或者叫邻域模型，为种群中的每一个个体分配一个处理单元，每个处理单元进行该个体的适应度计算，而选择、交叉、变异操作只在相邻的个体间进行。2.4混合并行遗传算法模型。该模型又称为多层并行模型，它结合不同并行遗传算法模型的特性，不仅染色体竞争求取最优解，而且在遗传算法的结构上也引入了竞争以提供更好的环境便于进化。通常，混合并行遗传算法以层次结构进行组合，上层多采用粗粒度模型，下层既可采用粗粒度模型也可采用细粒度模型。或者，种群可以按照粗粒度并行遗传算法模型分裂，迁移操作可以采用细粒度并行遗传算法模型。

3改进的并行遗传算法描述。我们知道，在生物的演化过程中，生命期模式在个体的成长占据十分重要的地位；生态环境中的生物个体在进化时，即使在它自己的局部环境，也是有生命周期的。个体在不同的局部环境和生命期的各个不同阶段具有不同的成长特性，并在生命期模式的控制个体现出实际成长的特点。遗传算法是一个群体优化过程，它是由一组初始值进行优化的，优化的过程是不断繁衍，竞争，遗传和变异的过程。传统的遗传算法存在着传统的遗传算法将个体进化过程放在一个种群内反复进行,这样做最大的缺点在于种群内基因交流畅通，个体很难向着各自的方向发展，从而导致种群多样度的降低和早熟收敛和后期收敛速度慢的弱点。我们采用遗传算法的改进粗粒度的并行模型把种群划分为多个子种群与各个对应的处理器并行独立进行遗传算法操作可以解决种群多样度的降低和早熟收敛和后期收敛速度慢的弱点。具体步骤如下：

STEP1：初始化。1．1确定种群规模N，杂交概率Pt，变异概率Pm,进化的代数gen,进化中止的准则。1．2确定初始种群。1．3计算初始种群个体的适应度值。

STEP2：划分子种群。2．1将初始种群个体的适应度值进行降序排序。2．2是否满足中止准则。2．3根据优化问题的复杂度将排序好的适应度值划分成若干子种群。2．4将子种群分配给各个处理机。

STEP3：种群优化。在每个子种群内都执行以下操作。3．1（选择）重复在子种群中选出N对个体为母体。3．2（杂交）根据交叉概率Pt，独立的对N对母体进行杂交操作以产生新的N个中间个体。3．3（变异）根据交叉概率Pm，独立的对N新产生的个体进行变异以产生新新一带的种群。3．4计算子种群个体的适应度值。3．5将子种群个体发送到STEP2上去。

STEP4：While(不满足结束条件)

STEP5：再转到STEP2继续执行操作。

STEP6：EndWhile

STEP7：输出结果

4Agent的引入。Agent是指具有智能的人或其它智能物或相当于智能物体的实体，以及能进行种种工作的软件等。这种Agent对结定介质环境中的事件变化能迅速作出反应，具有自治、推测、反响、协作、自学习和相互学习等能力。鉴于Agent的这些特点,借助Darwin自然进化论与Mendel遗传变异理论将Agent引入并行遗传算法当中是科学的，合理的。根据我们上面设计的算法把Agent分成二种类型的agent。其中一类用于实施各子群体的遗传操作以及计算子群体的适应度值并把子种群传送到STEP2上去，这类agent每个子群体一个，分布在不同的处理机上；另一类agent用作排序初始种群适应度值并划分种群分配给不同的处理机我们叫它控制agent。4.1Agent的结构。根据改进的并行遗传算法的描述将两种Agent结构设计如图1、2；4.2Agent的结构功能。4.2.1接受层。接受控制agent分配层发送过来的子种群，或接受操Agent发送回操作完的子种群。4.2.2操作层。对子种群执行选择、杂交、变异等遗传算法操作。4.2.3发送层。将操作完成的子种群发送回控制agent。4.2.4排序及评价层。对初始种群的适应度值进行排序评价。4.2.5分配层。将排序完成的子种群分配给Agent。

结束语

讨论的基于多智能体的并行遗传算法，实现了粗粒度的并行模型，是多智能体技术与遗传进化技术的一种有效结合。在遗传算法中引入智能体之后，更加接近自然，并充分发挥遗传算法的群体搜索策略的优势。作出如下工作：5.1给出了基于Agent的遗传算法描述；5.2遗传算法早熟现象进行了分析，给出了解决方案；5.3给出了Agent的演化模型。只是研究工作仅的一部分，还有许多内容需要补充，在今后的工作中将给出基于Agent的遗传算法理论的进一步完善该内容，使这些理论成果对今后应用起到积极的作用。

参考文献

[1]肖国强,王丽萍,彭斌.遗传算法及其并行性研究[J].微处理机,2007.

[2]高家全,何桂霞.并行遗传算法研究综述[J].浙江工业大学学报,2007.

[3]郑金华,蔡自兴.基于agent的并行GA[J].湘潭大学自然科学学报,2004.

[4]李凡长.基于Agent的遗传算法描述与演化模型研究[J].小型微型计算机系统,2003.

[5]杨俊杰,任雪梅,黄鸿.基于遗传算法的多智能体协作行为研究[J].计算机仿真,2006.

[6]郏宣耀,王芳.一种改进的小生境遗传算法[J].重庆邮电学院学报(自然科学版),2005.

[7]丁燕君,焦玉玺.Agent组织研究综述[J].人工智能及识别技术.2007.

[8]贾丽媛,杜欣.并行遗传算法研究[J].湖南城市学院学报(自然科学版)，2006.