俺曾经叫仔仔
范文一：遗传算法原理和应用
技 天 地INTELLIGENCE
遗传算法原理和应用
天津工业大学计算机科学与软件学院软件工程专业068班 杜 洋
摘 要：入侵检测系统的特点是利用生物免疫系统的原理与机制，实现对入侵行
为的检测。本文主要阐述遗传算法的实现原理，比较几种算法各自的特点，最后介绍遗传算法的应用领域。
关键词：免疫系统 否定选择算法 检测器
一、自然界免疫系统原理
自然免疫系统是一个相对复杂自适应过程，它能准确识别“自我”和“非我”，保护人体不受外界病原体的入侵。当受到病原体刺激的时候，淋巴细胞表面的“抗原识别受体”和病原体的“抗原决定基”相互结合使病原体失去致病性。当两者结构互补性越高，亲和力越强时，相互结合的几率就越大。
二、遗传算法
美国新墨西哥大学的Forrest研究小组在深入分析生物免疫与机制的基础上，提出了一种计算机免疫算法型。该模型将安全问题看成类似免疫系统中“自我”与“非我”的问题。Forrest思想是假定“自我集”随机分布在整个空间，为辨别“自我”与“非我”，空间随机产生检测器，删除检测到自己的检测器，使其余非己的检测器保留下来。入侵检测原理就是在“自我”与“非我”集合中构建一个边界，从而提高传统异常检测算法中效率和误报率低下的问题。
三、遗传算法对算子的操作
遗传算法对算子的基本操作分为三种，分别是选择、交叉和变异。
选择算子(selection/reproduction):
选择算子是指从群体中按某一概率选择个体，某个体xi被选择的概率Pi与其适应度值成正比。选择算子代码如下：
Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)
Dim=size(PopulationCode);
PopulationFitness=zeros(1,Dim(1));for i=1:Dim(1)
PopulationFitness(i)=
Transfer(PopulationCode(i,:),FunctionFitness,MinX，MaxX,MumberLength);
end
交叉算子(Crossover)
交叉算子将被选中的个体基因链按pc概率进行交叉，生成新的个体，交叉位置是随机的。
变异算子(Mutation):
变异也就是通过概率改变染色体位串上的某个基因，将新个体基因链的各位按pm概率进行变异。变异算子代码如下：
gen=0; pcross=pc; pmutation=pm; } ; virtual INDIVIDUAL& Select();
virtual void Crossover(INDIVIDUAL &parent1, INDIVIDUAL &parent2,
INDIVIDUAL &child1, INDIVIDUAL &child2); &child1, INDIVIDUAL &child2);
virtual ALLELE Mutation(ALLELE alleleval);virtual void Generate(); 四、遗传算法特点
遗传算法是求最优解的一种通用算法，对于各种通用问题都可以使用它。求最优解算法的共同特征为：
（1）首先选出一组候选解；
（2）依据适应性条件计算这些候选解的适应度范围；（3）根据适应度保留下某些候选解，淘汰其他的候选解；（4）对保留的候选解进行淘汰，最后所得即是新的最优解。
在遗传算法中，上述几个特征基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变等特征，将遗传算法与其它搜索算法区别开来。
五、遗传算法的应用
（1）遗传算法在入侵检测系统的应用
侵检测系统是一种主动防御体系，它从计算机系统中采集分析数据，通过检测引擎判断异常响应事件，在计算机系统受到危害之前拦截特征行为。譬如说计算机软件中毒之后, 入侵检测系统能收集病毒库相关信息并纳入防御体系，从而避免重中毒的行为。目前，遗传算法已经很好的应用于入侵检测系统当中，通过遗传算法的主动学习方式可以增强系统防范能力，有效弥补软件防火墙被动杀毒和病毒库特征需要升级的不足，很好的防护计算机的安全。
（2）优化函数
优化函数是遗传算法的经典应用领域。目前构造出各种各样复杂形式来测试函数：连续函数、离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多目标的函数优化问题用其它优化组合的方法难以求解，而遗传算法可以很好的得到较好的结果。
（3）组合优化
随着问题规模的增大，组合优化问题的搜索范围也随之急剧增大，有时在目前的计算上用枚举法很难求出问题的最优解。对于这类复杂问题，遗传算法可以寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中问题非常有效，例如遗传算法已经在求解旅行商问题、装箱问题、背包问题和图形划分问题等方面得到成功的应用。
六、小结
遗传算法是一类基于生物免疫系统功能、原理、特征建立的计算学习处理系统，拥有卓越的智能学习效率和自适应性，近年来用于故障诊断、行为仿真、入侵检测等领域。随着计算机技术的发展，遗传算法应用领域将会越来越广阔。
49
范文二：遗传算法的原理和应用
遗传算法的原理和应用
专业：信息与计算科学
班 级：信 计 1 3 1
学 号：1315030110
姓 名：马 琳
遗传算法的原理和应用
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：
1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。
2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。
3、 遗传算法使用多个点的搜索信息，具有隐含并行性。 4、 遗传算法使用概率搜索技术，而非确定性规则。
遗传算法的基本运算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：
1、 函数优化。
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。
2、 组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。
此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。
进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution
Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。
1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。
D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic
Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。
H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。
国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题
2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。 2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。
接下来，我们通过一个求解简单函数的最小值点的问题来初步展
示遗传算法的具体实现方法：
问题 1：
求函数 f (x)?? 11sin(6x)?? 7cos(5x) 在 x??[0, 2? ]区间上的最小值点。
上图为函数 f (x)?? 11sin(6x)?? 7cos(5x) 在 x??[0, 2? ]区间上的曲线图像， 可以看出，该函数有多个极值点，如果使用其他的搜寻方法，很容易陷入局部最小点，而不能搜寻到真正的全局最小点，但遗传算法可以较好地弥补这个缺陷。
遗传算法的具体实现如下：
1.问题分析。对于本问题，自变量 x 可以抽象为个体的基因组，即用二进制编码表示 x ；函数值 f ( x) 可以抽象为个体的适应度，函数值越小，适应度越高。关于二进制编码方式，在精度允许的范围下，可以将区间内的无穷多点用间隔足够小的有限点来代替，以降低计算量同时保证精度损失不大。如用 16 位二进制数来表示该区间的点，相邻点的函数值的变化幅度已经很小，由此带来的精度损失完全可以接受。
由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。
遗传算法的一些主要应用领域：
函数优化
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。
组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。
此外，GA也在生产调度问题、自动控制、机器人学、图像处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。
车间调度
车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。
范文三：简单蚁群算法的实现 - 遗传算法 - 瞎整技术
简单蚁群算法的实现
很久没有写博客了，一直都在忙着网站和论文的事，最近看了几篇蚁群算法的论文挺有意思的，总结了一下写成一篇论文附上重要部分的代码，顺便也完成了遗传算法的课程报告，有兴趣的朋友可以看看。
一 引言
蚁群算法(ant colony optimization，ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。初步的研究表明该算法具有许多优良的性质。针对PID控 制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价 值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。正因为蚁群算法有这些优 点，很多研究者都在致力研究和改过它，本文的目的正是为了介绍蚁群算法，学习如何编写蚁群算法。
二 蚁群算法的介绍
昆虫世界中，蚂蚁的组成是一种群居的世袭大家庭，我们称之为蚁群。蚂蚁分为世袭制的蚁王（后）和工蚁两种，它们具有高度组织的社会性，彼此沟通不仅可以借助触觉和视觉的联系，在大规模的协调行动中还可以借助外激素（有些书称信息素）之类的信息介质。
首 先我们要理解蚂蚁是如何觅食的，蚂蚁平时在巢穴附近作无规则行走，一量发现食物并不立即进食而是将之搬回蚁穴与其它蚂蚁分享，在食物小时则独自搬回蚁穴， 否则就回蚁穴搬兵，一路上会留下外激素，食物越大外激素的浓度就越大，越能吸引其它的蚂蚁过去一起搬去食物，这样最终就能将食物全部搬回蚁穴。这个过程用 程序实现看似非常复杂，要编写一个“智能”的蚂蚁也看似不太可能，事实上每个蚂蚁只做了非常简单的工作：检查某个范围内有无食物，并逐渐向外激素浓的方向 运动。简而言之，蚁群运动无非是同时反复执行多个简单规则而已。下面详细说明蚁群中的这些简单规则：
1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有外激素，外激素有两种，一种是找到食物的蚂蚁洒下的食物外激素，一种是找到窝的蚂蚁洒下的窝的外激素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让外激素消失。
3、 觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有外激素，并且比较在能感知的范围内哪一点的外激素最多，这样，它就朝 外激素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往外激素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的外激素做出反应，而对食 物外激素没反应。
4、移动规则： 每只蚂蚁都朝向外激素最多的方向移，并且，当周围没有外激素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有外激素指引的话，它会按照觅食的规则行为。
7、播撒外激素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的外激素最多，并随着它走远的距离，播撒的外激素越来越少。
根 据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过外激素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到 了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒外激素，当其它的蚂蚁经过它附近的时候，就会感觉到外激素的存在，进而根据外激素的指引找到 了食物。成功的觅食算法正是最小化搜索食物的时间。
三 蚁群算法的实现
理解蚁群算法的实质之后写出一个简单蚁群算法也不是太困难，关键是实现以上介绍的几个规则，下面用JAVA简单讲述一下以上规则的实现。
1、蚂蚁：蚂蚁是蚁群中最小的单位，是所以简单规则应用的最小个体。
public class Ant
{
public Square SQUARE;????????//蚂蚁所在方格
public Food CARRYING = null;????//所搬的食物数
public int ID;????????????//蚂蚁的编号
public boolean HELPING = false;????????//是否帮忙搬运食物
public void move(int turn)
{
//蚂蚁移动到下一个方格
}
}
2、范围：蚂蚁所在的方格应该包含附近的方格编号，所含食物数量，蚂蚁数量，外激素的浓度，以及坐标等信息。
public class Square
{ public Square NE;????????????//附近的8个方向的方格
public Square N;
public Square NW;
public Square W;
public Square SW;
public Square S;
public Square SE;
public Square E;
public LinkedList ANTS;????????//本方格中包含的蚂蚁
public Food FOOD;????????????//本方格中包含的食物数
public Nest NEST;????????????????//方格为蚁穴
public Pheromone_1 PHEROMONE_1;????????????//本方格中的外激素含量
public int X;????????????//本方格的坐标
public int Y;
private World WORLD;????????????//所属的环境
public boolean WALL;????????????//是否有障碍物
public Square(int x, int y, World world)
{
FOOD = null;
NEST = null;
PHEROMONE_1 = null;
X = x;
Y = y;
WORLD = world;
WALL = false;
ANTS = new LinkedList();
}
3、环境：环境是由多个方格组成的，是一个平面的，因此用一个方格的二维数组来表示是最合适不过的。
public class World
{
private Square[][] WORLD;????????//定义环境二维数组
private int WIDTH;????????????????//环境的长宽
private int HEIGHT;
private Pheromone_1List P1LIST;????????//保存所有外激素的列表
public World(Pheromone_1List p1list)
{
this.WIDTH = Settings.WIDTH;
this.HEIGHT = Settings.HEIGHT;
this.P1LIST = p1list;
WORLD = new Square[WIDTH][HEIGHT];
}
4、觅食规则，移动规则和避障规则：这三种规则全都跟蚂蚁的移动方向有关，并在移动前都要先计算周围方格的外激素浓度，选择外激素浓度最高的方格方向移动。 private Square chooseBestSquare()
{
Square[] square_list = {SQUARE.E, SQUARE.NE, SQUARE.N, SQUARE.NW, SQUARE.W, SQUARE.SW, SQUARE.S, SQUARE.SE};
double current_best_value = 0;
double value = 0;
Square square = SQUARE;
// 选择最好的方格
for(int i=0;i<>
{
value = calculateSquareValue(square_list[i]);//计算方格值
if(value > current_best_value)
{
current_best_value = value;
square = square_list[i];
}
}
if(square.ANTS.size() >= Settings.MAXIMUM_NUMBER_OF_ANTS)
{
return SQUARE;
}
return square;
}
private double calculateSquareValue(Square s)
{
double[] thresholds = Settings.THRESHOLDS;
if(s==null || s.WALL) // 方格有障碍物
{
return -100000;
}
// 计算方格中各项参数的值
return s.getFood()*thresholds[0]????????// 食物
+ s.getPheromone_1() * thresholds[1]????// 外激素
}
5、播撒外激素规则：每只蚂蚁找到食物后会根据食物的数量播撒相应量的外激素，以便其它蚂蚁能够更快得找到这堆食物。
private void putPheromone_1(double amount)
{
if(SQUARE.getPheromone_1() <>
SQUARE.addPheromone_1(amount);
}
从 以上蚁群算法中各个要素的代码来看，实现蚁群算法并不难。每只蚂蚁并不是像我们想象的需要知道整个环境的信息，它们只关心很小范围内的眼前信息，而且根据 这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律。
四 蚁群算法的不足
本 文实现的蚁群算法只是简单的大致模拟蚁群的觅食过程，真正的蚂蚁觅食过程远比这个复杂，比如增加蚂蚁搬运食物的距离和数量，蚂蚁在搬运食物发现更大的食物 可能会丢弃原有食物，还可以增加蚂蚁搬运食物回蚁穴的最短路径的求解。同时需要注意的是，由于蚁群算法觅食的过程，蚁群算法可能会过早的收敛并陷入局部最 优解。
范文四：基于遗传算法的混合蚁群算法
４２２００８，４４（１６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
基于遗传算法的混合蚁群算法
肖宏峰１，２，谭冠政２
ＸＩＡＯＨｏｎｇ－ｆｅｎｇ１，２，ＴＡＮＧｕａｎ－ｚｈｅｎｇ２
１．湖南师范大学计算机教学部，长沙４１００８１
２．中南大学信息科学与工程学院机器人研究所，长沙４１００８３
１．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＴｅａｃｈｉｎｇ，ＨｕｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８１，Ｃｈｉｎａ
２．ＲｏｂｏｔｉｃＩｎｓｔｉｔｕｔｉｏｎ，ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＣｅｎｔｒａｌＳｏｕｔｈＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８３，ＣｈｉｎａＥ－ｍａｉｌ：ｘｈｆ７１＠ｈｕｎｎｕ．ｅｄｕ．
ＸＩＡＯＨｏｎｇ－ｆｅｎｇ，ＴＡＮＧｕａｎ－ｚｈｅｎｇ．ＨｙｂｒｉｄＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ
（１６）：４２－４５．ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４
Ａｂｓｔｒａｃｔ：ＰｒｏｐｏｓｅａｎｅｗＡｎｔＣｏｌｏｎｙＳｙｓｔｅｍ（ＡＣＳ）ｆｏｒｏｂｔａｉｎｉｎｇｏｐｔｉｍａｌｖａｌｕｅｏｆｃｏｎｔｉｎｕｏｕｓｓｐａｃｅ．ＣｏｍｐａｒｉｎｇｔｈｅｉｒａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｂｅｔｗｅｅｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ（ＧＡ）ａｎｄＡｎｔＣｏｌｏｎｙＳｙｓｔｅｍａｎｄａｎａｌｙｚｉｎｇｔｈｅｉｒｂａｓｉｃｆｕｓｉｏｎｃｏｎｄｉｔｉｏｎ，ｐｒｏｐｏｓｅｔｗｏ
ｎｅｗｓｔｒａｔｅｇｉｅｓｏｆｆｕｓｉｎｇＧＡｉｎｔｏＡＣＳ：ＯｎｅｉｓｆｉｒｓｔｕｓｉｎｇｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｏｏｂｔａｉｎｓｏｍｅｒｏｕｇｈｓｏｌｕｔｉｏｎｓｔｏｔｈｅｐｒｏｂｌｅｍａｎｄｔｈｅｎｏｂｔａｉｎｉｎｇｔｈｅｍｏｒｅｐｒｅｃｉｓｅｓｏｌｕｔｉｏｎｓＸ＊ｂｅｓｔｂｙＡＣＳ，ｔｈｅｏｔｈｅｒｉｓｉｍｐｒｏｖｉｎｇｔｈｅａｂｉｌｉｔｙｏｆｇｌｏｂａｌｓｅａｒｃｈｂｙｕｓｉｎｇｔｗｏｔｏｕｒｐａｔｈｓｉｎＡＣＳｔｏｇｅｎｅｒａｔｅａｎｏｔｈｅｒｔｗｏｎｅｗｔｏｕｒｐａｔｈｓｌｉｋｅｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｉｏｎｏｆＧＡ．Ｂａｓｅｄｏｎａｂｏｖｅｎｅｗｉｄｅａｓ，ｔｗｏｎｅｗｈｙｂｒｉｄａｎｔｃｏｌｏｎｙｓｙｓｔｅｍｓｂａｓｅｄｏｎＧＡｒｅｓｐｅｃｔｉｖｅｌｙｃａｌｌｅｄＧＡ－ＨＡＣＳ－ＩａｎｄＧＡ－ＨＡＣＳ－ＩＩａｒｅｂｕｉｌｔｉｎｔｈｉｓｐａｐｅｒ．Ａｔｌａｓｔ，ｖｅｒｉｆｙｔｈｅｃｏｒｒｅｃｔｉｏｎｏｆＧＡ－ＨＡＣＳ－ＩａｎｄＧＡ－ＨＡＣＳ－ＩＩｂｙｔｅｓｔｆｕｎｃｔｉｏｎＲｏｓｅｎｂｒｏｃｋａｎｄｔｅｓｔｆｕｎｃｔｉｏｎＳｈｕｂｅｒｔ．
Ｋｅｙｗｏｒｄｓ：ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｈｙｂｒｉｄａｎｔｃｏｌｏｎｙｓｙｓｔｅｍ；ａｌｇｏｒｉｔｈｍｆｕｓｉｏｎ；ｏｐｔｉｍｉｚａｔｉｏｎｏｆｃｏｎｔｉｎｕｏｕｓｓｐａｃｅ
摘
要：提出了一种新的求连续空间最优值的蚁群算法。结合遗传算法和蚁群算法各自的优点以及两种算法融合基础，提出了遗
传算法融入到蚁群算法融合中的两种新策略，第一种策略是先利用遗传算法具有比较强的全局搜索能力，在大范围内寻找一组解，然后以此为基础，用蚁群算法快速寻找最优解Ｘ＊ｂｅｓｔ；另一种策略是利用遗传算法交叉操作产生蚁群算法中的新旅行路径，以此提高蚁群算法的全局搜索能力。用上述策略构造两个基于遗传算法的混合遗传算法。用测试函数Ｒｏｓｅｎｂｒｏｃｋ和测试函数Ｓｈｕｂｅｒｔ验证了混合蚁群算法的正确性。
关键词：遗传算法；混合蚁群算法；算法融合；连续空间优化
ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２００８．１６．０１２文章编号：１００２－８３３１（２００８）１６－００４２－０４文献标识码：Ａ中图分类号：ＴＰ１８
１引言
遗传算法和蚁群算法（ＡＣＳ，ＡｎｔＣｏｌｏｎｙＳｙｓｔｅｍ）都具有适
献［８－１０］。
遗传算法和蚁群算法具有互补性，它们完全有可能有机地融合在一起，以克服各自缺点，发挥各自优点。遗传算法与蚁群算法融合的策略，根据它们两者在某个集成算法中所处的地位和优势不同，大体可以划分为两个大类：一类是以蚁群算法为主体的混合蚁群算法，如文献［１１］利用遗传算法ＧＡ寻找ＡＣＳ中ρ的最优组合；另一类是以遗传算法为主体混合遗传算、、αβ法，如参考文献［４－７］。蚁群算法适合于求离散空间的最优解，而连续空间优化时不是很方便；遗传算法没有此限制。用遗传算法和蚁群算法来求连续空间优化问题时的基本出发点是如何离散连续系统。遗传算法采用二进制编码方式是一个比较好而且又统一的解决方案。对蚁群算法来说，很多的学者采用各种各样的不同方法来离散化连续系统，他们几乎有一个共同的特
应范围广、通用性能强等共同的特点，广泛用于离散系统工程优化。两者有各自的优缺点：遗传算法有比较强的全局搜索的优点，特别是当交叉概率比较大时，能产生大量的新个体，提高了全局搜索范围，遗传算法收敛速度也比较慢，为此众多学者采用各种方法来改善提高遗传算法的收敛速度，他们的方法可以划分两种类型，一种是采用与求解的具体问题有关的交叉算子［１－３］，另一种是在遗传算法中融合其它算法，如拟牛顿优化算蚁群算法采用正反馈法、模拟退火算法，构成混合遗传算法［４－７］。原理，具有局部搜索能力强和收敛速度比较快等优点，但全局搜索能力相对遗传算法来说要弱一些，提高蚁群算法全局搜索能力的一个重要方法是采用自适应蚁群算法等，如参考文
基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．５０２７１５０）；高等院校博士学科点专项科研基金（ｔｈｅ
ＣｈｉｎａＳｐｅｃｉａｌｉｚｅｄＲｅｓｅａｒｃｈＦｕｎｄｆｏｒｔｈｅＤｏｃｔｏｒａｌＰｒｏｇｒａｍｏｆＨｉｇｈｅｒＥｄｕｃａｔｉｏｎｕｎｄｅｒＧｒａｎｔＮｏ．２００４０５３３０３５）。
作者简介：肖宏峰，博士研究生，讲师，主要研究领域：智能控制、智能优化理论与算法等；谭冠政，博士，博士生导师，主要研究领域：智能仿生机器
人、模式识别与智能控制及先进控制理论与控制算法等。
收稿日期：２００７－０７－２０
修回日期：２００７－１２－１９
肖宏峰，谭冠政：基于遗传算法的混合蚁群算法
点：把连续空间转化为类似于用蚁群算法求解旅行商问题（ＴＳＰ，ＴｒａｖｅｌｉｎｇＳａｌｅＰｒｏｂｌｅｍ）
［１２－１８］
２００８，４４（１６）
如果第ｋ只蚂蚁经过边Ｅｄｇｅ（ｊ，ｉ，ｉｊ）时否则
ｋ
１
４３
，得到一个比较复杂的类似
Ｑ
ｋ
ｋ
）! τｊ，ｉ，ｉ＝Ｆ（ｘ１，ｘ２，…，ｘｎ
ｊ
ＴＳＰ问题的图形，给蚁群算法带来困难，影响蚁群算法计算速
度。本文采用遗传算法中二进制编码的方法表示蚁群算法中旅行路径，蚂蚁在除最后一个节点之外的任何一个节点时，只有两个后继节点，也就是说只有两条路径可以选择，蚂蚁旅行路径得到了极大地简化，同时也奠定两个算法融合的一个基础。另外利用激素分布来处理连续函数的计算，如参考文献［１９］。
"
$#$$$%
（４）
０
其中，ｍ为蚂蚁数量，! τ（ｊ，ｉ）节点ｊ，ｉ，ｉ表示第ｋ只蚂蚁在坐标为与坐标为（ｊ，ｉ，ｉｊ）上增加的激素浓（ｊ＋１，ｉ１）节点所连接的边ｅｄｇｅ
ｋ度；Ｆ（ｘ１，ｘ２，…，ｘｎ）表示第ｋ只蚂蚁所寻求到的解。
２．３．２新蚁群算法转移概率分析
根据图１，第ｋ蚂蚁由节点Ｋｎｏｔ－ｊｉ只能转移到后继节点
２求连续空间最优解的新蚁群算法
２．１连续空间离散方法
采用二进制编码表示蚂蚁旅行路径。设函数的ｎ个自变量为ｘ１，…，ｘｎ，自变量ｘｉ的范围为（ａｉ，ｂｉ），长度为ｌ位，ｎ个自变量编码总长度为（（两ｒｒ＝ｌｎ）位。设二进制编码为０１１００１－１１０００１个自变量），以该二进制的某一位为纵坐标，蚂蚁旅行时间为横坐标，构成１２个点：（１，０）、（２，１）、（３，１）、（４，０）、（５，０）、（６，１）、（８，１）、（９，０）、（１０，０）、（１１，０）和（１２，１），连接这些点组（７，１）、
成的折线设为蚂蚁旅行路径，用图１表示；反之，类似图１的旅行路径也可用二进制表示。这样构成二进制编码与路径对应关系。第ｋ只蚂蚁的一条旅行路径可表示为：Ｔ（ｂ１，ｉｂ２，ｉ…ｂｊ，ｉｂｊ＋１，ｉ
１
２
ｊ
Ｎｅｘｔ－ｋｎｏｔ－０和Ｎｅｘｔ－ｋｎｏｔ－１。选择下一旅行节点的概率分别是：
ｐｊ，ｉ，ｉ＝
ｊ
ｋ
［τｊ，ｉ，ｉ］［$ｊ，ｉ，ｉ］
ｊ
ｊ
#ｋ%’
ｋ
(
［τｊ，ｉ，０］［&ｊ，ｉ，０］＋［τｊ，ｉ，１］［&ｊ，ｉ，１］
#ｋ%
（５）
其中，τ（ｊ，ｉ，０）、（ｊ，ｉ，１）上的激素τＥｄｇｅｊ，ｉ，０、ｊ，ｉ，１分别表示边Ｅｄｇｅ浓度；&ｊ，ｉ，０、（ｊ，ｉ，０）、（ｊ，ｉ，１）能见度函&ｊ，ｉ，１分别表示边ＥｄｇｅＥｄｇｅ数；’、(是激素浓度与能见度函数对选择下一个旅行节点时的影响系数。
２．３．３新蚁群算法能见度函数表示
当第ｋ只蚂蚁在旅行节点Ｋｎｏｔ－ｊｉ时，假设其它节点保
持不变，改变其后继节点，得到两条路径Ｔｏｕｒ０、Ｔｏｕｒ１，表示为Ｔ（ｂ１，ｉｂ２，ｉ…ｂｊ，０ｂｊ＋１，ｉ…ｂｒ，ｉ）、（ｂ１，ｉｂ２，ｉ…ｂｊ，１ｂｊ＋１，ｉ…ｂｒ，ｉ）。Ｔ
１
２
ｊ＋１
ｒ
１
２
ｊ＋１
ｒ
ｋｋｋｋ
ｋｋｋｋｋｋｋｋｋｋ
ｊ＋１
…ｂｒ，ｉ），（ｂｊ，ｉ＝０，１；ｉｊ＝０，１）。对该二进制编码按照遗传算法方法
ｒ
ｊ
ｋｋ
Ｔｏｕｒ０和Ｔｏｕｒ１两条路径对应的位置关系如图３，对应的路径
编码分别是１１１１００１１１、１１１１００１１１。Ｆ０、Ｆ１是Ｔｏｕｒ０和
解码：
ｘｉ＝
（ｘｉ＿ｃｏｄｅ）２
（１１…１１）
Ｔｏｕｒ１对应函数值。Ｆ０、Ｆ１分别与当前已得到的函数最优值Ｆ＊
（ｂｉ－ａｉ）×
２
（１）
的相对误差的倒数定义为第ｋ只蚂蚁在边Ｅｄｇｅ（ｊ，ｉ，０）、Ｅｄｇｅ（ｊ，ｉ，１）能见度函数&ｊ，ｉ，０、&ｊ，ｉ，１：
ｋ
ｋ
２．２新蚁群算法中边的表示
蚁群算法中每只蚂蚁在它所经过的路径的边上留有激素，
蚁群算法中激素浓度更新操作针对某一边而采取操作。（ｊ＝１…ｒ，ｉ＝０，１）表示坐标为（ｊ，ｉ）旅行节点。除最后Ｋｎｏｔ－ｊｉ
一个节点之外，其余每个节点都有两个后继旅行节点Ｎｅｘｔ－（ｊ＋１，０）和（ｊ＋１，１），Ｋｎｏｔ－ｊｉｋｎｏｔ－０、Ｎｅｘｔ－ｋｎｏｔ－１，其坐标分别是
和Ｎｅｘｔ－ｋｎｏｔ－０、Ｎｅｘｔ－ｋｎｏｔ－１所连接的两条边分别表示为Ｅｄｇｅ（ｊ，ｉ，０）、（ｊ，ｉ，１），简写为ｅｄｇｅ（ｊ，ｉ，ｉｊ），其中，ｉｊ＝０，１。它们对Ｅｄｇｅ应关系如图２。这两边也可表示为Ｅｄｇｅ（ｂｊ，ｉｂｊ＋１，ｉ）。
ｊ
&ｊ，ｉ，ｏ＝
ｋ
１
Ｆｏ－Ｆ＊＝
｜Ｆ＊｜｜Ｆ＊｜
（６）＝ｋｋｋｋ
｜Ｆｏ－Ｆ＊｜｜Ｆ（Ｔ（ｂ１，ｉ…ｂｊ，ｉｂｊ＋１，ｏ…ｂｒ，ｉ））－Ｆ＊｜
１
ｊ
ｒ
其中ｏ＝０，１，Ｆ（Ｔ（ｂ１，ｉ…ｂｊ，ｉｂｊ＋１，ｉ…ｂｒ，ｉ））表示路径Ｔ（ｂ１，ｉ…ｂｊ，ｉ
１
ｊ
ｊ＋１
ｒ
１
ｋｋｋｋｋｋ
ｊ
ｂｊ＋１，ｉ…ｂｒ，ｉ）所对应的函数值。
ｊ＋１
ｒ
ｋｋ
２．４新蚁群算法描述
Ｎｅｗ－ＡＣＳ：
Ｓｔｅｐ１．初始化各个参数：等；（１）α，β，ρ
（路径长度），ｍ（蚂蚁数量）；（２）ＡＣＳ－ｃｙｃｌｅｓ，ｒ
（３）Ｔ＋←Φ，Ｔ（０）←Φ，ｔ←０。
ｋｋ
Ｓｔｅｐ２．迭代计算：ＷｈｉｌｅｔＡＣＳ－ｃｙｃｌｅｓ）。输出最优结果。
（／＊以下更新路径上的激素＊／）
（Ｔ１′（Ｂ１，ｉ…Ｂｊ，ｉ…ｂｒ，ｉ））ＡＣＳ－ｃｙｃｌｅ）Ｓｔｅｐ３输出。
３．２算法ＧＡ－ＨＡＣＳ－Ｉ
算法描述：
步骤１用遗传算法获得一组最优解ＴＢｅｔｔｅｒ（０）。
步骤２以ＴＢｅｔｔｅｒ（０）为初始路径，用蚁群算法求更精确解
（ＧＡ）
（ＧＡ）
（ｔ）。Ｘｂｅｓｔ
＊
４实验与分析
４．１单峰值函数验证
采用单峰值函数验证算法ＧＡ－ＨＡＣＳ－Ｉ、ＧＡ－ＨＡＣＳ－ＩＩ的收敛速度和计算精度。Ｒｏｓｅｎｂｒｏｃｋ函数Ｆ１：
（ｘ１－ｘ２）＋（１－ｘ１）ｍｉｎ（ｆｘ１，ｘ２）＝１００
２
２
２
３．３算法ＧＡ－ＨＡＣＳ－Ⅱ
上述蚁群算法的旅行路径表示方法与遗传算法的染色体
二进制编码相同，这奠定了两者融合的另一基础。采用路径交叉操作，对已有路径重新组合，产生新路径，这时由于遗传算法有更强发现新解的能力。对每次得到新的路重新更新激素。
（１）路径交叉操作
随机选择两条路径Ｔ（Ｔ（１ｂ１，ｉ…ｂｊ，ｉ…ｂｒ，ｉ）、２ｂ１，ｉ…ｂｊ，ｉ…ｂｒ，ｉ）
１
ｊ
ｒ
１
ｊ
ｒ
－２．０４８≤ｘｉ≤２．０４８
ｉ＝１，２
是一个二维函数，它具有一个全局极小值（ｆ１，１）＝０。该函数虽然是单峰值的函数，但它是病态的，难以进行全局极小化。
实验参数：ｍ＝５０，ＡＣＳ－ｃｙｃｌｅ＝５０，ｎ＝２，ｌ＝８，ｍ＝１０，ρ＝０．８，Ｑ＝
ｋ１ｋ１ｋ１ｋ２ｋ２ｋ２
＝１，β＝２；遗传算法实验参数：染色体种群大小Ｐ＝ｍ，ＧＡ－１，α
ｃｙｃｌｅ＝２０，ｐｃ＝０．６，ｐｍ＝０．１；ｐＴｃ＝０．６。
和一个交叉位置ｐｏｓ，按照遗传算法中单点交叉思路，交换数据，得到两条新路径Ｔ１（′Ｂ１，ｉ…Ｂｊ，ｉ…ｂｒ，ｉ）、Ｔ２（′Ｂ１，ｉ…Ｂｊ，ｉ…ｂｒ，ｉ），
１
ｊ
ｒ
１
ｊ
ｒ
ｋ１ｋ１ｋ１ｋ２ｋ２ｋ２
４．２Ｒｏｓｅｎｂｒｏｃｋ测试函数优化结果
图５是所有算法ｘ１、ｘ２的初始分布图；图６是算法ＧＡ－
路径交叉原理如图４。
Ｐｒｏｃｅｄｕｒｅ：Ｔ－ｃｒｏｓｓｏｖｅｒｐｒｏｃｅｄｕｒｅ
Ｂｅｇｉｎ
产生路径交叉概率ｐＴｃ；
ＨＡＣＳ－Ｉ第２０次循环时变量ｘ１、ｘ２的分布图；图７是算法
求最小值ＧＡ－ＨＡＣＳ－ＩＩ第２０次循环时变量ｘ１、ｘ２的分布图。表２分别是ＧＡ、（ｆ１．００２，１．００２）＝０．０００４。表１、ＧＡ－ＨＡＣＳ－Ｉ和（共５０次实验）。ＧＡ－ＨＡＣＳ－ＩＩ的计算速度与计算精度比较
Ｉｆ（ｐ０．１４８６
结论
根据遗传算法与蚁群算法的优缺点和用遗传算法的二进
ｆ＜０．００５
ＧＡ－ＡＣＳ－Ｉ／％ＧＡ－ＡＣＳ－Ⅱ／％
ＳＧＡ／％
５
０．００５＜ｆ＜０．０１１４１４２８
０．０１＜ｆ＜０．１
１０１２８
５
７２６６５８
制编码形式解决蚁群算法连续函数的离散化，构造两种混合蚁群算法ＧＡ－ＨＡＣＳ－Ｉ和ＧＡ－ＨＡＣＳ－ＩＩ。算法充分利用遗传算法中交叉算子能产生新的个体特点来产生蚁群算法中的新路径，从而达到遗传算法和蚁群算法的融合。
?（ｉ＋１）ｘ１＋ｉ］｝×?（ｉ＋１）ｘ２＋ｉ］｝ｍｉｎ（ｆｘ１，ｘ２）＝｛! ｉｃｏｓ［｛! ｉｃｏｓ［
ｉ＝１
ｉ＝１
ｓ．ｔ．－１０≤ｘｉ≤１０
ｉ＝１，２
参考文献：
［１］ＷｈｉｔｌｅｙＤ．Ｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓａｎｄｔｒａｖｅｌｉｎｇｓａｌｅｓｍｅｎ：ｔｈｅｇｅｎｅｔｉｃ
ｅｄｇｅｒｅｂｉｎａｔｉｏｎｏｐｅｒａｔｏｒ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｏｆ３ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎ－ｆｅｒｅｎｃｅｏｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ．［Ｓ．ｌ．］：ＭｏｒｇａｎＫａｕｆｎｍａｎｎｎ，１９８９：１３３－１４０．
［２］ＤａｖｉｓＬ．Ａｄａｐｔｉｎｇｏｐｅｒａｔｏｒｐｒｏｂａｂｉｌｉｔｉｅｓｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｐｒｏ－
ｃｅｅｄｉｎｇｓｏｆ３ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ．［Ｓ．ｌ．］：ＭｏｒｇａｎＫａｕｆｍａｎｎ，１９８９：６１－６９．
［３］ＯｌｉｖｅｒＬＭ．Ａｓｔｕｄｙｏｆｐｅｒｍｕｔａｔｉｏｎｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒｓｏｎｔｈｅ
ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｏｆ２ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ，１９８７：２２４－２３０．
［４］ＣｈｅｎＨ，ＦｌａｎｎＮＳ．Ｐａｒａｌｌｅｌｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｎｄｇｅｎｅｔｉｃａｌｇｏ－
ｒｉｔｈｍｓ：ａｓｐａｃｅｏｆｈｙｂｒｉｄｍｅｔｈｏｄｓ［Ｍ］／／ＰａｒａｌｌｅｌＰｒｏｂｌｅｍＳｏｌｖｉｎｇｆｒｏｍＮａｔｕｒｅ３．［Ｓ．ｌ．］：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９４：４２８－４３８．
［５］ＬｅｅＳ，ｏＬｓｏｎＤ．Ａｇｒａｄｉｅｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｃｈａｎｃｅｃｏｎｓｔｒａｉｎｅｄｎｏｎ－
ｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，（１）：３４３－３６９．１９７７，１１
这是一个二维函数，它具有１８个全局极小点（ｆｘ１，ｘ２）＝
－１８６．７３１。
４．４Ｓｈｕｂｅｒｔ测试函数优化结果
用ＧＡ－ＨＡＣＳ－ＩＩ、ＧＡ－ＨＡＣＳ－Ｉ算法进行５０次试算，每次都可以得到多个全局最优值。表３、表４是ＧＡ－ＨＡＣＳ－Ｉ、ＧＡ－
ＨＡＣＳ－ＩＩ算法前１０次得到最小值个数列表；表５是ＧＡ－
ＧＡ－ＨＡＣＳ－ＩＩ算法一组实验中找到全部１８个最小值ＨＡＣＳ－Ｉ、
的命中率统计结果，实验分两种，第一种每１０次实验为１组统计命中率，第二种每５次实验为１组统计命中率。表６是采用ＧＡ－ＨＡＣＳ－Ｉ算法得到最小值数量最多的一次统计结果；表７是采用ＧＡ－ＨＡＣＳ－ＩＩ算法得到最小值数量最多的一次
统计结果。
表３
实验序号
ＧＡ－ＨＡＣＳ－Ｉ前１０次得到最小值个数
最小值个数
实验序号
最小值个数
４５
４４５５４
６７８９１０
４４５５４
［６］ＭａｈｆｏｕｄＳＷ，ＧｏｌｄｇｅｒｇＤＥ．Ａｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｐａｒａｌｌｅｌｓｉｍ－
ｕｌａｔｅｄａｎｎｅａｌｉｎｇ［Ｍ］／／ＰａｒａｌｌｅｌＰｒｏｂｌｅｍＳｏｌｖｉｎｇｆｒｏｍＮａｔｕｒｅ２，ＮｏｒｔｈＨｏｌｌａｎｄ，１９９２：３０１－３１０．
［７］ＢｉｌｃｈｅｖＧ，ＰａｒｍｅｅＩＣ．Ａｄａｐｔｉｖｅｓｅａｒｃｈｉｎｇｓｔｒａｔｅｇｉｅｓｆｏｒｈｅａｖｉｌｙ
ｃｏｎｓｔｒａｉｎｅｄｄｅｓｉｇｎｓｐａｃｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ２２ｎｄＩｎｔｅｒｎａｔｉｏｎａｌ９５，Ｙｅｌｔａ：Ｕｋｒａｉｎｅ，１９９５：ＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＡｉｄｅｄＤｅｓｉｇｎ’２３０－２３５．
［８］孙宏，詹士昌，金柏林．自适应进化的蚁群算法及其仿真研究［Ｊ］．杭
州师范大学学报，２００３，２（５）：３１－３４．
表４
实验序号
ＧＡ－ＨＡＣＳ－ＩＩ前１０次得到最小值个数
最小值个数
实验序号
最小值个数
４５
５６４５５
６７８９１０
４７５６５
［９］陈崚，秦玲，陈宏建．具有感觉和知觉特征的蚁群算法［Ｊ］．系统仿真
学报，２００３，１５（１０）：１４１８－１４２５．
（下转１３４页）
１３４２００８，４４（１６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
系统挖掘出的关联规则及对应的置信度。
项集的阶数不会大于４。表１￣表４分别给出了各阶频繁项集及其支持度的计算结果。
表１
频繁项集
３．３
Ａ３６９．５３Ｃ３４５．７０
Ｂ２Ｃ４
Ｂ３Ｄ３
Ｂ４Ｄ４
Ｂ５７．４８Ｄ５
挖掘结果分析
表５中的关联规则主要反映了４门科目成绩中等和较差
１阶频繁数据项集与其支持度
Ａ２Ｃ２
６．５０３７．８０４７．３０３８．２１２２．０９
情况下，彼此之间的关联性。这主要是因为给定了４％最小支持度阈值ｍｉｎｓｕｐ，而４门科目成绩分别达到优秀和良好的考生相对较少导致，从而使关联规则没有反映各科目高分成绩之间的关联性。解决这个问题的方法是降低ｍｉｎｓｕｐ值，使小概率发生事件，即少部分高分考生进入挖掘范围，但这将降低挖掘规则的普遍性和代表性，同时会大大增加系统生成的频繁项集数目，对系统性能产生一定的消极影响。
表５
关联规则
置信度／％
支持度／％２５．６３频繁项集
支持度／％１２．４２６５．３３１０．６３
表２
频繁项集支持度／％频繁项集支持度／％频繁项集支持度／％频繁项集支持度／％
２阶频繁数据项集与其支持度
Ａ２Ｃ２７．２０Ａ３Ｃ２５．１１Ｂ３Ｃ４８．４５Ｃ２Ｄ３５．０８
Ａ２Ｃ３１３．７９Ａ３Ｃ３３１．４４Ｂ３Ｄ３１４．９３Ｃ２Ｄ４６．１０
Ａ２Ｃ４４．００Ａ３Ｃ４３２．１０Ｂ３Ｄ４２１．７９Ｃ３Ｄ３１３．５４
Ａ２Ｄ３８．８２Ａ３Ｄ３１３．１３Ｂ４Ｃ３１９．１５Ｃ３Ｄ４２９．１０
Ａ２Ｄ４１４．３７Ａ３Ｄ４４８．８８Ｂ４Ｃ４２５．０９Ｃ４Ｄ４２９．３９
Ａ３Ｂ３２３．９３Ａ３Ｄ５７．３０Ｂ４Ｄ４３８．１２Ｃ４Ｄ５５．４６
７．８５
Ａ２Ｂ３１３．４１Ａ３Ｂ４３７．７８Ｂ３Ｃ２７．００Ｂ４Ｄ５５．８７
Ａ２Ｂ４Ａ３Ｂ５４．６１Ｂ３Ｃ３２２．１２Ｂ５Ｃ４４．０６
关联规则与其置信度
置信度／％
关联规则
置信度／％
关联规则
Ｂ４→Ａ３Ｃ４→Ａ３Ｃ４→Ｄ４Ａ３Ｂ４→Ｄ４Ｂ３Ｃ４→Ａ３Ｂ４Ｃ３→Ａ３
７９．８７８４．００７６．９２８１．８２８１．１８７６．７１
Ｂ４Ｃ４→Ａ３Ｂ４Ｄ４→Ａ３Ｂ４Ｄ５→Ａ３Ａ３Ｃ４→Ｄ４Ｂ４Ｃ３→Ｄ４Ｂ４Ｃ４→Ｄ４
８５．２５８１．０９８４．６７７７．８８７９．３２８２．９０
Ｃ４Ｄ４→Ａ３Ｃ４Ｄ５→Ａ３Ｂ３Ｃ４Ｄ４→Ａ３Ａ３Ｂ４Ｃ３→Ｄ４Ｂ４Ｃ４Ｄ４→Ａ３
８５．０６８５．５３８４．６３８１．１５８５．４５
表３
频繁项集支持度／％频繁项集支持度／％频繁项集支持度／％频繁项集支持度／％
３阶频繁数据项集与其支持度
Ａ２Ｂ３Ｄ３５．８１Ａ３Ｂ３Ｄ３９．０４Ａ２Ｃ３Ｄ３４．９２Ｂ３Ｃ３Ｄ３９．８５
Ａ２Ｂ３Ｄ４７．３７Ａ３Ｂ３Ｄ４１４．０６Ａ２Ｃ３Ｄ４８．２６Ｂ３Ｃ３Ｄ４１１．８２
Ａ２Ｂ４Ｃ３４．１７Ａ３Ｂ４Ｃ３１４．６９Ａ３Ｃ３Ｄ３８．５６Ｂ３Ｃ４Ｄ４５．９２
Ａ２Ｂ４Ｄ４５．８５Ａ３Ｂ４Ｃ４２１．３９Ａ３Ｃ３Ｄ４２０．４８Ｂ４Ｃ３Ｄ４１５．１９
Ａ３Ｂ３Ｃ３１３．７５Ａ３Ｂ４Ｄ４３０．９１Ａ３Ｃ４Ｄ４２５．００Ｂ４Ｃ４Ｄ４２０．８０
Ａ２Ｂ３Ｃ３８．２５Ａ３Ｂ３Ｃ４６．８６Ａ３Ｂ４Ｄ５４．９７Ａ３Ｃ４Ｄ５４．６７
４结束语
数据仓库与数据挖掘技术是一个具有广泛用途的领域，本
文在分析教育考试数据资源应用现状的基础上，构建了教育考试数据集市雪花模型，并采用Ａｐｒｉｏｒｉ算法生成频繁数据项集，进而挖掘考生各科目成绩之间的关联性，并得出了考生４科成绩之间的关联规则，各规则的置信度均达到７５％以上。
表４
频繁项集支持度／％频繁项集支持度／％
４阶频繁数据项集与其支持度
Ａ２Ｂ３Ｃ３Ｄ４４．５１Ａ３Ｂ３Ｃ４Ｄ４５．００
Ａ３Ｂ３Ｃ３Ｄ３６．１５Ａ３Ｂ４Ｃ３Ｄ４１１．９１
Ａ３Ｂ３Ｃ３Ｄ４７．２４Ａ３Ｂ４Ｃ４Ｄ４１７．７６
参考文献：
［１］ＨａｎＪ，ＫａｍｂｒＭ．Ｄａｔａｍｉｎｉｎｇ：ｃｏｎｃｅｐｔｓａｎｄｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｂｅｉｊｉｎｇ：
ＢｅｉｊｉｎｇＨｉｇｈｅｒＥｄｕｃａｔｉｏｎＰｒｅｓｓ，２００１：５－９．
［２］王战军，瞿斌．学位与研究生教育评估数据仓库的模型设计［Ｊ］．哈尔
滨工业大学学报，２００３，３５（１１）：１３１４－１３１６．
（３）给定最小置信度阈值ｍｉｎｃｏｎｆ为７５％，挖掘满足最小置信度阈值的规则。
设项集Ｘ和项集Ｙ，且Ｘ" Ｙ，Ｘ和Ｙ的支持度分别为（Ｘ）和Ｓｕｐｐ（Ｙ），则０≤Ｓｕｐｐ（Ｘ）≤１，０≤Ｓｕｐｐ（Ｙ）≤１。根据Ｓｕｐｐ
（Ｙ）Ｓｕｐｐ条件概率原理，规则Ｒ：Ｘ→Ｙ的置信度为ｃｏｎｆ；（Ｒ）＝
（Ｘ）Ｓｕｐｐ
（Ｙ）Ｓｕｐｐ更进一步，Ｒ：Ｘ→Ｙ－Ｘ的置信度为ｃｏｎｆ（Ｒ）＝。表５是（Ｘ）Ｓｕｐｐ（上接４５页）
［１０］王颖，谢剑英．一种自适应蚁群算法及其仿真［Ｊ］．系统仿真学报，
（１）：３１－３３．２００２，１４
［３］樊湄筑，张凡．数据仓库技术在地铁交通系统中的应用［Ｊ］．贵州工业
大学学报：自然科学版，２００６，３５（２）：８３－８７．
［４］陈安，陈宁，周龙骧，等．数据挖掘技术及应用［Ｍ］．北京：科学出版
社，２００６：５０－５５．
［５］ＡｇｒａｗａｌＲ，ＳｒｉｋａｎｔＲ．Ｆａｓｔａｌｇｏｒｉｔｈｍｓｆｏｒｍｉｎｉｎｇａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ
ｉｎｌａｒｇｅｄａｔａｂａｓｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｏｆｔｈｅ２０ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒ－ｅｎｃｅｏｎＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓ，Ｓａｎｔｉａｇｏ，Ｃｈｉｌｅ，Ｓｅｐ，１９９４：４８７－４９９．
ｖｉｅｒＰｕｂｌｉｓｈｉｎｇ，１９９１：１３４－１４２．
［１７］魏平，熊伟清．用于一般函数优化的蚁群算法［Ｊ］．宁波大学学报：理
工版，２００１，１４（４）：５２－５５．
［１１］ＺｈａｎＳｈｉ－ｃｈａｎｇ，ＸｕＪｉｅ，ＷｕＪｕｎ．Ｔｈｅｏｐｔｉｍａｌｓｅｌｅｃｔｉｏｎｏｎｔｈｅ
ｐａｒａｍｅｔｅｒｓｏｆｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ［Ｊ］．ＢｕｌｌｅｔｉｎｏｆＳｃｉｅｎｃｅａｎｄ（５）：３８１－３８６．Ｔｅｃｈｎｏｌｏｇｙ，２００３，１９
［１８］林锦，朱文兴．凸整数规划问题的混合蚁群算法［Ｊ］．福州大学学报：
自然科学版，１９９９，２７（６）：５－９．
［１２］陈崚，沈洁，秦玲．蚁群算法进行连续参数优化的新途径［Ｊ］．系统工
程理论与实践，２００３，１８（３）：４８－５３．
［１９］黄樟灿，吴方才，胡晓林．基于信息素的整数规划的演化求解［Ｊ］．计
算机应用研究，２００１，１０（７）：２７－２９．
［１３］杨勇，宋晓峰，王建飞，等．蚁群算法求解连续空间优化问题［Ｊ］．控
制与决策，２００３，１８（５）：５７３－５７６．
［２０］ＢｏｎａｂｅａｕＥ，ＤｏｒｉｇｏＭ，ＴｈｅｒａｕｌａｚＧ．Ｓｗａｒｍｉｎｔｅｌｌｉｇｅｎｃｅｆｒｏｍｎａｔｕ－
ｒａｌｔｏａｒｔｉｆｉｃｉａｌｓｙｓｔｅｍｓ［Ｍ］．ＮｅｗＹｏｒｋ：ＯｘｆｏｒｄＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９９９．［２１］ＤｏｒｉｇｏＭ，ＧａｍｂａｒｄｅｌｌａＬＭ．Ａｎｔｃｏｌｏｎｙｓｙｓｔｅｍ：ａｃｏｏｐｅｒａｔｉｖｅ
ｌｅａｒｎｉｎｇａｐｐｒｏａｃｈｔｏｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍｅｎｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ（３）：１６１－１６３．ＴｒａｎｓｏｎＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，１９９６，２１
［１４］汪镭，吴启迪．蚁群算法在连续空间寻优问题中的应用［Ｊ］．控制与
决策，２００３，１８（１）：４５－４８．
［１５］高尚，钟娟，莫述军．连续优化问题的蚁群算法研究［Ｊ］．微机发展，
（１）：２１－２３．２００３，１３
［２２］ＹｕＬｏｎｇ－ｊｉａｎｇ，ＰｅｎｇＸｉ－ｙｕａｎ，ＰｅｎｇＹｕ．Ａｔｅｓｔｓｅｔｏｐｔｉｍｉｚａｔｉｏｎ
ｍｅｔｈｏｄｏｆｂａｓｅｄｏｎａｎｔａｌｇｏｒｉｔｈｍ［Ｊ］．ＡＣＴＡＥｌｅｃｔｒｏｎｉｃＳＩＮＩＣＡ，（８）：１１７８－１１８１．２００３，３１
［１６］ＣｏｌｏｒｎｉＡ，ＤｏｒｉｇｏＭ，ＭａｎｉｅｚｚｏＶ．Ｄｉｓｔｒｉｂｕｔｅｄｏｐｔｉｍｉｚａｔｉｏｎｂｙａｎｔ
ｃｏｌｏｎｉｅｓ［Ｃ］／／ＰｒｏｃｏｆＥｕｒｏｐｅＣｏｎｆｏｎＡｒｔｉｆｉｃｉａｌＬｉｆｅ．Ｐａｒｉｓ：Ｅｌｓｅ－
范文五：遗传算法
基本原理：
遗传算法是一种典型的启发式算法，属于非数值算法范畴。它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它是采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群，每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应度函数的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化进行不断演化，直到满足期望的终止条件。
运算流程：
Step 1：对遗传算法的运行参数进行赋值。参数包括种群规模、变量个数、交叉概率、变异概
率以及遗传运算的终止进化代数。
Step 2：建立区域描述器。根据轨道交通与常规公交运营协调模型的求解变量的约束条件，设置变量的取值范围。
Step 3：在Step 2的变量取值范围内，随机产生初始群体，代入适应度函数计算其适应度值。
Step 4：执行比例选择算子进行选择操作。
Step 5：按交叉概率对交叉算子执行交叉操作。
Step 6：按变异概率执行离散变异操作。
Step 7：计算Step 6得到局部最优解中每个个体的适应值，并执行最优个体保存策略。
Step 8：判断是否满足遗传运算的终止进化代数，不满足则返回Step 4，满足则输出运算结果。
运用遗传算法工具箱:
运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库。目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学开发的遗传算法工具箱GATBX、GAOT以及Math Works公司推出的GADS。实际上，GADS就是大家所看到的Matlab中自带的工具箱。我在网上看到有问为什么遗传算法函数不能调用的问题，其实，主要就是因为用的工具箱不同。因为，有些人用的是GATBX带有的函数，但MATLAB自带的遗传算法工具箱是GADS，GADS当然没有GATBX里的函数，因此运行程序时会报错，当你用MATLAB来编写遗传算法代码时，要根据你所安装的工具箱来编写代码。
以GATBX为例，运用GATBX时，要将GATBX解压到Matlab下的toolbox文件夹里，同时，set path将GATBX文件夹加入到路径当中。 例子：
这块内容主要包括两方面工作：1、将模型用程序写出来（.M文件），即目标函数，若目标函数非负，即可直接将目标函数作为适应度函数。2、设置遗传算法的运行参数。包括：种群规模、变量个数、区域描述器、交叉概率、变异概率以及遗传运算的终止进化代数等等。
求解模型： f(x)=x*sin(10*pi*x)+2.0,x的范围在【-1,2】
根据上面的求解模型，可以写出模型的.M文件如下，即适应度函数
function z=shang(x)
z=x.*sin(10*pi*x)+2.0;
然后写入遗传算法的参数：
figure(1);
fplot('variable.*sin(10*pi*variable)+2.0',[-1,2]); %画出函数曲线
NIND=40; %个体数目(Number of individuals)
MAXGEN=25; %最大遗传代数(Maximum number of generations)
PRECI=20; %变量的二进制位数(Precision of variables)
GGAP=0.9; %代沟(Generation gap)
trace=zeros(2, MAXGEN); %寻优结果的初始值
FieldD=[20;-1;2;1;0;1;1]; %区域描述器(Build field descriptor)
Chrom=crtbp(NIND, PRECI); %初始种群
gen=0; %代计数器
variable=bs2rv(Chrom, FieldD); %计算初始种群的十进制转换
ObjV=shang(variable); %计算目标函数值
while genFitnV=ranking(-ObjV); %分配适应度值(Assign fitness values)
SelCh=select('sus', Chrom, FitnV, GGAP); %选择
SelCh=recombin('xovsp', SelCh, 0.7); %重组
SelCh=mut(SelCh); %变异
variable=bs2rv(SelCh, FieldD); %子代个体的十进制转换
ObjVSel=shang(variable); %计算子代的目标函数值
[Chrom ObjV]=reins(Chrom, SelCh, 1, 1, ObjV, ObjVSel); %重插入子代的新种群 variable=bs2rv(Chrom, FieldD);
gen=gen+1; %代计数器增加
%输出最优解及其序号，并在目标函数图像中标出，Y为最优解,I为种群的序号
[Y, I]=max(ObjV);hold on;
plot(variable(I), Y, 'bo');
trace(1, gen)=max(ObjV); %遗传算法性能跟踪
trace(2, gen)=sum(ObjV)/length(ObjV);
end
variable=bs2rv(Chrom, FieldD); %最优个体的十进制转换
hold on, grid;
plot(variable,ObjV,'b*');
figure(2);
plot(trace(1,:));
hold on;
plot(trace(2,:),'-.');grid
legend('解的变化','种群均值的变化')
