混合遗传算法GASA

11
（5）遗传算法在解空间进行高效启发式搜索，而非盲 目地穷举或完全随机搜索；
（6）遗传算法对于待寻优的函数基本无限制，它既不 要求函数连续，也不要求函数可微，既可以是数学解 析式所表示的显函数，又可以是映射矩阵甚至是神经 网络的隐函数，因而应用范围较广；
（7）遗传算法具有并行计算的特点，因而可通过大规 模并行计算来提高计算速度，适合大规模复杂问题的 优化。
26
（4）基本遗传算法的运行参数 有下述4个运行参数需要提前设定：
M：群体大小，即群体中所含个体的数量，一般取为 20~100； G：遗传算法的终止进化代数，一般取为100~500； Pc：交叉概率，一般取为0.4~0.99；
Pm：变异概率，一般取为0.0001~0.1。
27
10.4.2 遗传算法的应用步骤
遗传算法简称GA（Genetic Algorithms）是1962年 由美国Michigan大学的Holland教授提出的模拟自然 界遗传机制和生物进化论而成的一种并行随机搜索最 优化方法。
遗传算法是以达尔文的自然选择学说为基础发展起 来的。自然选择学说包括以下三个方面：
1
（1）遗传：这是生物的普遍特征，亲代把生物信息交 给子代，子代总是和亲代具有相同或相似的性状。生 物有了这个特征，物种才能稳定存在。
18
（3）生产调度问题 在很多情况下，采用建立数学模型的方法难以对生
产调度问题进行精确求解。在现实生产中多采用一些 经验进行调度。遗传算法是解决复杂调度问题的有效 工具，在单件生产车间调度、流水线生产车间调度、 生产规划、任务分配等方面遗传算法都得到了有效的 应用。
19
（4）自动控制。 在自动控制领域中有很多与优化相关的问题需要求
10

遗传算法基因冲突
一、遗传算法是一种基于生物进化原理的优化算法，通过模拟自然选择和遗传机制来寻找最优解。

在遗传算法中，基因冲突是一个常见的问题，它指的是在交叉和变异过程中，新产生的个体可能携带了不希望的特性和基因型，这可能会导致算法的性能下降或者陷入局部最优解。

二、基因冲突的产生原因主要有两个：
1. 交叉操作：在交叉过程中，两个父代个体的基因被混合在一起，可能会产生不希望的基因组合。

如果父代个体携带了不希望的基因，这些基因可能会传递给子代个体，导致子代个体具有不希望的特性。

2. 变异操作：变异操作是指对个体的基因进行随机的修改，这可能会导致产生新的基因组合。

如果变异后的个体携带了不希望的基因，这可能会导致算法的性能下降。

GA遗传算法概述GA（Genetic Algorithm，遗传算法）是一种模拟自然界中生物进化过程的优化算法，具有全局能力和适应性优化能力。

1980年由美国的John Holland提出，并在优化问题领域取得了许多成功的应用。

遗传算法的基本思想是通过模拟自然选择、基因交叉和变异等操作来问题的最优解。

具体而言，遗传算法从一个初始群体（种群）开始，通过不断的迭代进化，逐渐产生接近于最优解的个体。

其中，每个个体都可以看作是问题的一种解决方案。

遗传算法的主要步骤包括：初始化种群、适应度评估、选择操作、交叉操作、变异操作和终止条件。

下面将对这些步骤逐一进行介绍。

首先，初始化种群。

在该步骤中，需要确定种群的规模、编码方式以及初始个体的生成方式。

种群的规模一般较大，以增加空间的覆盖度。

编码方式是将问题的解表示为一个个体的基因型（即染色体），常见的编码方式有二进制编码和实数编码等。

初始个体的生成方式也需根据具体问题来确定。

其次，进行适应度评估。

适应度函数是衡量个体优劣的标准，通常是问题的目标函数。

适应度函数的设计要充分考虑问题的特点，使得适应度高的个体拥有更大的生存概率。

然后，进行选择操作。

选择操作的目的是根据适应度函数的评估结果，选择优秀个体作为下一代个体的父代。

常见的选择方法有轮盘赌选择、竞争选择和排名选择等。

轮盘赌选择法根据个体的适应度进行选择，适应度高的个体被选择概率大。

接着，进行交叉操作。

交叉操作是通过基因交换产生新的个体，以增加种群的多样性。

交叉操作的方式有很多，如一点交叉、多点交叉和均匀交叉等。

一般会在较高适应度个体之间进行交叉操作，以保留优良的基因。

然后，进行变异操作。

变异操作是通过基因突变产生新的个体，以增加种群的多样性。

变异操作是在交叉操作后进行的，其方式有变异率和变异步长等。

变异率决定了个体基因发生变异的概率，变异步长则决定了基因变异的程度。

最后，根据终止条件判断是否终止迭代。

终止条件可以是达到预定的迭代次数、找到满足要求的解或运行时间超过设定的阈值等。

第三部分遗传算法课后任务查找资料，学习了解个体编码的方法、交叉的方法和变异的方法。

、个体编码方法1、二进制编码：1）定义：二进制编码方法是使用二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。

二进制编码符号串的长度与问题所要求的求解精度有关。

（2）举例：OW XW1023,精度为1,m表示二进制编码的长度。

则有建议性说法：使2m-1< 1000 （跟精度有关）W 2m-1。

取m=10则X:00就可以表示一个个体，它所对应的问题空间的值是X=175。

3）优缺点优点：符合最小字符集原则，便于用模式定理分析；缺点：连续函数离散化时的映射误差。

2、格雷码编码：1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。

它是二进制编码方法的一种变形。

十进制数0—15 之间的二进制码和相应的格雷码分别编码如下。

二进制编码为：0000，0001，0010，001 1，0100。

0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111；格雷码编码为：0000，0001，0011，0010，0110，0111，0101，0100，1100，1101，1111，1110，1010，1011，1001，1000。

2）举例：对于区间[0。

1023]中两个邻近的整数X1=175 和X2=176，若用长度为10 位的二进制编码，可表示为X11：00 和X12 00，而使用同样长度的格雷码，它们可分别表示为X21：00 和X22：00。

3）优点：增强了遗传算法的局部搜索能力，便于连续函数的局部控件搜索。

3、符号编码法符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,CT。

符号编码的主要优点是：1）符合有意义积术块编码原则2）便于在遗传算法中利用所求解问题的专门知识3）便于遗传算法与相关近似算法之间的混合使用。

中，而一些适应函数值小的染色体则可能被淘汰。
一、遗传算法概述
1、智能优化算法 2、基本遗传算法 3、遗传算法的特点
1、智能优化算法
智能优化算法又称为现代启发式算法， 是一种具有全局优化性能、通用性强、 且适合于并行处理的算法。这种算法一 般具有严密的理论依据，而不是单纯凭 借专家经验，理论上可以在一定的时间 内找到最优解或近似最优解。
均点交叉运算 交叉前： 00000|01110|00000|00100|00 11100|00000|11111|10001|01 交叉后： 00000|00000|00000|10001|00 11100|01110|11111|00100|01 交叉点
均匀交叉又称“驻点交叉”，在交叉前先进行基因的变异 检测，通过后再行交叉。
（2） 利用比例选择算子的公式，计算每个个体被
选中遗传到下一代群体的概率；
（3） 采用模拟赌盘操作（即生成0到1之间的随机
数与每个个体遗传到下一代群体的概率进行匹配） 来确定各个个体是否遗传到下一代群体中。
以赌轮盘的方式來看，把一个轮盘分成若干扇形， 面积越大的编号，越容易中奖，因此奖金会比較低。 以适应性函数來看，其值越大者所占的面积就越大， 其选中的机率就越大。
轮盘赌选择又称比例选择算子，它的基本思想 是：各个个体被选中的概率与其适应度函数值大小 成正比。设群体大小为n ，个体i 的适应度为 Fi， 则个体i 被选中遗传到下一代群体的概率为：
P i F i / F i
i 1
n
轮盘赌选择方法的实现步骤
（1） 计算群体中所有个体的适应度函数值（需要 解码）；
身的要求而定。
选择算子
遗传算法使用选择运算来实现对群体中的个 体进行优胜劣汰操作：适应度高的个体被遗传到

交叉算子自适应遗传算法
自适应遗传算法(Adaptive Genetic Algorithm，AGA)是对基本遗传算法的一种改进，它通过对遗传参数的自适应调整，大大提高了遗传算法的收敛精度，加快了收敛速度。

适应度函数是评价个体适应环境的能力，在进行选择操作时经常用到，它的选取是否恰当直接影响到遗传算法的性能，所以就形成了很多计算适应度的函数，改进这些适应度函数是为了使适应度能更好的反映个体的优劣，使得适应度低的个体被淘汰，适应度高的个体被保留。

自适应的适应度函数可以随着种群代数的增加自适应的调整，在算法的开始阶段，适应度差别较大，为了防止一些适应度较差的个体在一开始就丢失，可以通过改变适应度函数使得它们得以保留下来，另外，当种群趋于收敛时，适应度差别很小，这时为了加快收敛的速度，应对适应度进行调整，使得个体适应度差别增大，从而更快的收敛到全局最优解。

常用的适应度变换方法有：线性变换、幂函数变换和指数变换。

另外，采用适应度结合了模拟退火的思想。

选择的作用是按某种方法从父代群体中选取一些将要进行交叉的个体，常用的选择方法很多，它们大多有一个共同的特点，就是都是基于适应度的选择，适应度大的个体被选中的概率就大，适应度小的个体被选中的概率就小。

常用的选择算法有适应度比例法、精英保留策略、联赛选择法等。

另外，也可以将这些选择算法混合使用，如今还出现了启发式的搜索选择策略，这种策略是用每个个体所带有的启发信息来确定它被选中的概率。

适应性》中首先提出的，它是一类借鉴生物界自然选择和
自然遗传机制的随机化搜索算法。GA来源于达尔文的进化 论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其
基本思想是模拟自然界遗传机制和生物进化论而形成的一
种过程搜索全局最优解的算法。
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(1) 达尔文的自然选择说
三、遗传算法的原理
标准遗传算法(Standard genetic algorithm, SGA)
Step1 在搜索空间U上定义一个适应度函 数f(x)，给定种群规模N，交叉率Pc和变异 率Pm，代数T； Step2 随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代 数计数器t=1； Step3 计算S中每个个体的适应度f(x)； Step4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算 法结束。否则，转Step5；
四、遗传算法的应用
用遗传算法求解：
f ( x) x sin(10 x) 2.0
分析：由于区间长度为3，求解结果精确到6位小数，因此可将自变量
定义区间划分为3×106等份。又因为221 < 3×106 < 222 ，所以本例的 二进制编码长度至少需要22位，编码过程实质上是将区间[-1，2]内对 应的实数值转化为一个二进制串（b21b20…b0）。

循环交叉（Cycle Crossover）
交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换 组合，来产生新的优良品种！
二、遗传算法的基本操作
3 变异(mutation)
变异就是改变染色体某个(些)位上的基因 例如，设染色体s=11001101，将其第三位上的0变为1, 即

混合进化算法
混合进化算法是一种结合不同进化算法的优点而产生的新型优
化算法。

它可以同时应用启发式搜索、人工神经网络、模拟退火、遗传算法等多种进化算法，以期在优化问题中取得更好的效果。

混合进化算法的基本思想是将多个进化算法进行融合，形成一种新的优化算法。

这样做的好处是可以充分利用各种算法的优点，弥补各自的不足。

例如，遗传算法在搜索空间大的优化问题中表现优异，而模拟退火算法则在处理局部极值问题上有很好的效果。

混合进化算法可以将两者结合，同时兼顾全局搜索和局部搜索的效果。

混合进化算法的应用范围非常广泛，包括图像处理、数据挖掘、机器学习等领域。

在图像处理中，混合进化算法可以用来进行图像分割、边缘检测等操作。

在数据挖掘中，它可以用来进行聚类、分类、预测等任务。

在机器学习中，混合进化算法可以用来进行参数优化、特征选择等操作。

混合进化算法的优点在于可以在多个进化算法中挑选最佳的算
法组合，从而达到更好的优化效果。

同时，它可以对进化算法进行优化和改进，提高算法的效率和稳定性。

混合进化算法的缺点在于需要对多个算法进行熟练掌握，对算法的选择和组合需要一定的经验和技巧。

总之，混合进化算法是一种非常有效的优化算法，它可以在多个进化算法中选择最佳的算法组合，以期在优化问题中取得更好的效果。

它的应用领域非常广泛，对于需要解决优化问题的任务，都有很好的
应用前景。

mdvrp的混合式基因演算法
MDVRP（多点配送车辆路径规划）是指配送车辆从一个或多个出发点到达一个或多个目的地的路径规划问题。

混合式基因演算法是一种用于解决复杂优化问题的人工智能算法，它将遗传算法（Genetic Algorithm，GA）和粒子群算法（Particle Swarm Optimization，PSO）相结合，具有较好的收敛性和搜索能力。

在解决MDVRP问题时，混合式基因演算法可以通过调整参数来优化路径规划结果。

例如，可以调整遗传算法中的交叉率、变异率和选择方式，以及粒子群算法中的惯性权值、学习因子和群体规模，来改善解的质量和收敛速度。

此外，在使用混合式基因演算法解决MDVRP问题时，还需要考虑如何建模和编码。

通常使用距离矩阵或时间矩阵来表示路径的距离或时间，并使用路径拆分法或圆周拆分法来编码路径。

在建模时，还可以考虑加入限制条件，例如车辆容量限制、时间窗限制、路径长度限制等，以使得解更加符合实际需求。

总之，混合式基因演算法是一种有效的方法，可以用于解决MDVRP 问题。

它具有较好的收敛性和搜索能力，并且可以通过调整参数和建模方式来优化解的质量和收敛速度。

混合粒子群算法
混合粒子群算法（Mixed Particle Swarm Optimization，MPSO）是一种基于粒子群优化算法和遗传算法的混合模型。

它采用了粒子群优化算法中的速度和位置更新策略，并结合遗传算法的交叉和变异操作来提高算法的搜索能力和收敛速度。

MPSO算法的基本步骤包括：
1. 初始化算法参数，包括粒子群大小、遗传算法参数等；
2. 随机生成初始粒子群，并初始化粒子的位置和速度；
3. 根据粒子的位置和适应度函数计算粒子的适应度值；
4. 根据适应度值更新全局最优解和个体最优解；
5. 根据全局最优解和个体最优解，更新粒子的速度和位置；
6. 针对当前粒子群的一部分个体，采用遗传算法的交叉和变异操作进行优化；
7. 判断停止条件是否满足，若满足则输出当前最优解，否则返回步骤3。

MPSO算法相较于传统粒子群算法具有更强的全局搜索能力和局部搜索能力，适用于复杂多峰函数的优化问题。

遗传算法的详解及应用遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和遗传过程的算法。

在人工智能和优化问题中得到了广泛的应用。

本文将详细介绍遗传算法的基本原理和优化过程，并探讨它在实际应用中的价值和局限性。

一、遗传算法的基本原理遗传算法的基本原理是通过模拟生物进化的过程来寻找一个问题的最优解。

在遗传算法中，优秀的解决方案（也称为个体，Individual）在进化中拥有更高的生存几率，而劣质的解决方案则很快被淘汰。

在遗传算法的过程中，每个个体由若干个基因组成，每个基因代表某种特定的问题参数或者状态。

通过遗传算法，我们可以找到问题最优的解或者其中一个较优解。

遗传算法的基本流程如下：1. 初始化群体（Population）：首先，我们需要随机生成一组初始解作为群体的个体。

这些个体被称为染色体（chromosome），每一个染色体都由一些基因（gene）组成。

所以我们可以认为群体是由很多染色体组成的。

2. 选择操作（Selection）：选择运算是指从群体中选出一些个体，用来繁殖后代。

其目的是让优秀的个体留下更多的后代，提高下一代的平均适应度。

在选择操作中，我们通常采用轮盘赌选择（Roulette Wheel Selection）法、锦标赛（Tournament）法、排名选择（Ranking Selection）法等方法。

3. 交叉操作（Crossover）：交叉运算是指随机地从两个个体中选出一些基因交换，生成新的染色体。

例如，我们可以将染色体A和B中的第三个基因以后的基因交换，从而产生两个新的染色体。

4. 变异操作（Mutation）：变异运算是指随机改变染色体中的个别基因，以增加多样性。

例如，我们随机将染色体A的第三个基因改变，从而产生一个新的染色体A'。

5. 适应度评估（Fitness Evaluation）：适应度评估是指给每一个个体一个适应度分数，该分数是问题的目标函数或者优化函数。

遗传算法编码及算子简介遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块以逐渐逼近最优解。

由此可见，必须把群体中的个体转化成按一定基因结构组成的染色体或个体，即编码。

编码原则包括两条：1.有积极积木块编码规则，即所定编码应当易于生成所求问题相关的短距和低阶的积木块。

2.最小字符集编码规则，即所定编码应用最小字符集以使问题得到自然的表示或描述。

规则一是基于模式定理和积木块假设；规则二提供了一种更为实用的编码规则。

评估编码策略常采用的规范有：1.完备性：问题空间中的所有点都能作为GA空间的点表现。

2.健全性：GA空间中的染色体能对应所有问题空间中的候选解。

3.非冗余性：染色体和候选解一一对应。

这些评估规范是独立于问题领域的普遍准则。

对某个具体的应用领域而言，应该客观化地比较和评估该问题领域中所用的编码方法。

应用遗传算法进行优化，首先将问题描述成串的形式，以模拟染色体。

选择何种编码方式对算法的运行有很大的影响。

现在，流行的观点认为二进制编码能在相同的范围内表示最多的模式，能充分地体现所谓的隐含并行性。

但是，二进制编码方式的精度依赖于染色体的基因位数及设计变量的范围。

因而对于高精度、多变量问题，n值需很大，降低遗传算法的收敛速度。

另外，二进制编码不直接反映真实的设计空间。

其它的编码方式还有：格雷码编码、浮点编码、树结构编码、参数动态编码和多维编码等。

遗传算法主要有选择、交叉和突变算子选择算子遗传算法使用选择算子或称复制算子来对种群中的个体进行优胜劣汰操作：选择算子使适应性高的个体在后代中生存的概率较大，而适应度低的个体生存的概率很小甚至被淘汰。

遗传算法中的选择操作就是来确定如何从父代群体中按某种方法选取那些个体以传到下一代群体的一种遗传算法。

选择操作是建立在群体中个体的适应度评价基础上的。

选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。

量子遗传算法
量子遗传算法（Quantum Genetic Algorithm，QGA）是基于量子计算原理的一种优化搜索方法，由物理学家David Deutsch提出。

它将遗传算法中的遗传变异运算与量子力学中的量子干涉运算相结合，将最优化问题转化为多重态的量子干涉实验，以此来寻找最优解。

在QGA中，通常使用一个二进制的比特序列作为代表染色体的编码，即使用0/1来表示个体的基因。

利用量子力学中的量子运算，可以把这些比特序列干涉起来，形成多重态。

每一个基因上的比特都可以在多重态中取不同的值，这样就能够把最优化问题转化为搜索多重态的问题。

在QGA中，运算过程包括三个步骤：1.量子遗传运算；2.量子测量；3.量子变异。

首先，量子遗传运算会生成一组多重态的比特序列，然后通过量子测量，可以得到一组有效的比特序列，接着，量子变异运算会对这些比特序列进行变异，最后，重复这些步骤，直到找到最优解。

综上所述，量子遗传算法是一种基于量子力学原理的优化搜索方法，可以有效解决复杂的优化问题。

遗传算法与禁忌搜索算法的混合策略李大卫①(鞍山钢铁学院,鞍山114002)　王　莉(鞍山师范学院,鞍山114005)　王梦光(东北大学,沈阳110006) 摘要　遗传算法与禁忌搜索算法的出现为解决高维组合优化问题提供了强有力工具.二者既有共性,又有个性.通过对遗传算法与禁忌搜索算法的分析,提出了一种遗传算法与禁忌搜索算法的混合策略,把禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中,构造了新的重组算子,并把禁忌搜索算法作为遗传算法的变异算子,对旅行商问题的求解表明:混合策略在许多方面优于遗传算法.关键词:遗传算法,禁忌搜索,混合策略,旅行商问题分类号:N94GENETIC ALGORITHM AND TABU SEARC H:A HYBRID STRATEGYLi Dawei(Anshan Institute of Iron and Steel Techno logy,Anshan114002)Wang Li(Anshan Normal College,Ansha n114005)Wang Mengguang(No rtheastern Univ ersity,Shenya ng110006)Abstract　The appearance of genetic alg orithm s and tabu sea rch prov ide pow erful tools fo r solving combina to rial o ptimizatio n problems in high dimen-sio ns.Th e two m ethods either hav e som e co mmo n bo nds,or sig nificant differ-ences.Through a nalysing,w e propose a hy brid strategy o f genetic algo rithm andtabu search.The m em ory function o f tabu search is introduced into procedure o fg enetic alg orithms.A new recombina tion o perator is co nstructed,w hile mutatio no perator is replaced by tabu sea rch.Genetic alg orithm and hybrid stra tegy a reused separately to solv e trav eling salesma n problem.The experiment resultssho w that the hybrid strateg y is superio r to the standard g enetic alg orithm inm any aspects.Key words:g enetic algo rithm,tabu search,hy brid strategy0　引　言在过去的20年里,由美国学者H o lland和他的同事、学生们提出的遗传算法(genetic alg orithms,GA)成为求解任意函数优化问题的强有力的工具[1].GA是一种进化搜索算法,它的基本思想是基于Da rw in的进化论和M endel的遗传学说.其中重组和变异算子是GA 1998年9月 J O U RN AL O F SY ST EM S EN G IN EERIN G Sep.1998①36岁,男,博士,讲师.36,male,Dr.,lectur er.本文1997年4月11日收到.的两个最重要的组成部分,它们被重复地应用到对问题的解进行编码而构成的染色体上.在许多优化问题和工业实际应用上,G A 已经得到了成功的应用[2].禁忌搜索(Tabu Sea rch,T S)是另一个著名的启发式搜索算法,最早由Glov er 提出[3].具有记忆功能是T S 独创的特点之一.许多研究人员对TS 的理论和应用作了研究,使得TS 在调度领域,运输问题,专家系统和神经网络等方面得到了广泛的应用[5].GA 开创了在解空间中从多出发点搜索问题最优解的先河,而TS 是在搜索过程中使用记忆功能的先驱者.它们在解决各种实际应用问题所取得的成功表明,使用二者解决复杂的问题是有价值的.尽管GA 和TS 的适用范围很广,但由于某些条件约束,所以GA 和TS 并不是对所有的问题都是万能的算法,或多或少存在着某些缺陷.因此有必要对GA 和TS 作进一步的研究.本文对此作些尝试性的工作,在对GA 与T S 算法进行分析的基础上,提出了一种G A 与T S 的混合策略(GAT S),把TS 独有的记忆功能引入到GA 搜索过程之中,构造了新的重组算子,并把TS 作为GA 的变异算子.1　GA 与TS 的比较1.1　GA 简介GA 可用如下的五维向量组形式描述 GA =(N pop ,N gen ,K ,f eval ,f sel )其中N pop 为群体规模;N gen 为迭代代数;K 为遗传算子(重组和变异)及它们的概率集合;f eval 为评价函数,或称作适应值;f sel 表示再生选择规则.这里并不关心染色体的具体编码的形式,因此假设GA 和TS 可以使用同样的编码.GA 的特点可以概括成下面的4点[2]:1)利用变量的编码方式,而不使用变量本身;2)在解空间中从多出发点搜索问题的解,而不像某些传统的搜索方法从一点出发搜索问题的解;3)直接利用目标函数的函数值信息,而不使用函数的导数或其它的辅助信息;4)使用概率转移规则,而不采用确定性的转移规则.GA 的求解过程如图1所示:beg in　t =0;initialize P (t );　ev aluate structures in P (t );　while terminatio n co ndition not satisfied do t =t +1; select P (t )fro m P (t -1); recombine structures in P (t ); ev aluate structures in P (t );end(其中P (t )表示第t 代群体)图1　G A 的求解过程1.2　TS 简介类似地,TS 也可用五维向量组的形式描述·29·1998年9月 李大卫等:遗传算法与禁忌搜索算法的混合策略 TS =(N pop ,N gen ,Λ,f move ,tabu list)其中N p op 表示一个初始解;N gen 为迭代代数;Λ表示移动的构成方式;f move 为移动值;tabu list 是长度为T 的禁忌表,其中T 可以是定长的,也可以是变长的.TS 求解过程可以表示成如图2的形式:beg in　t =0;g enerate N pop ;set T ;　set the best and present solutions x =x 0=N pop ;　while terminatio n co ndition not satisfied do t =t +1; m ov e x to x ′; update (x ;x 0;tabu list);end 图2　T S 的求解过程T S 也是一种迭代搜索算法.由于TS 使用了记忆功能,在搜索过程中可以接受劣解,所以TS 具有强的“爬山”能力(相对于全局最小值问题),这样使得TS 在搜索过程中能够跳出局部最优解,进而转向其它区域进行搜索,从而获得更好的解或全局最优解的概率也大大增加.2　GA 的局限性和T S 的缺陷2.1　GA 的局限性尽管GA 能够胜任任意函数,高维空间的组合优化问题,但是对于像优化大规模神经元网络的权系数,优化网络的结构等超大规模的优化问题,GA 的应用就受到了限制.究其原因,主要在于GA 在进化搜索过程中,每代总是要维持一个较大的群体规模,从而使计算次数呈非多项式时间增加,限制了GA 的使用.GA 的另一个不足之处是“早熟”.造成这种成熟前收敛的原因,一方面是GA 中最重要的遗传算子——交叉算子使群体中的染色体具有局部相似性,从而使搜索停滞不前;另一方面是变异概率又太小,以至于不能使搜索转向其它的解空间进行搜索.此外,GA 还有爬山能力差的弱点.这也是由于变异概率低造成的.因此,如何提高GA 的爬山能力成为一个重要的研究方向,为了提高GA 的爬山能力,Ackley 开发了一个具有随机爬山功能的称作SIGH 的算法[6].他的分析表明,随机爬山能够促进GA 的搜索速度和解的准确性.2.2　TS 的缺陷T S 的搜索速度比GA 的搜索速度快,但TS 对于初始解具有较强的依赖性.一个较好的初始解可使T S 在解空间中搜索到更好的解,而一个较差的初始解则会降低TS 的收敛速度.为此人们往往使用启发式算法来获得一个较好的初始解,提高TS 的性能.T S 的另一缺陷是在搜索过程中初始解只能有一个,在每代也只是把一个解移动到另一解,而不像GA 那样每代都是对解集(群体)进行操作.·30·系　统　工　程　学　报 第13卷　第3期3　GA 与TS 的混合策略GA TS开发混合算法的目的是使原算法的优点被保持,弱点被克服或者被削弱,提高算法的力度.M ǜhlenbein 最早把记忆功能引入到GA 中[6],而TS 的创始人Glov er 对混合GA 与TS 的必要性和可行性进行了理论上的分析和论述[7],被公认为混合GA 与TS 的理论基础.通过上面对GA 和TS 的分析,在Glov er 理论的基础上,本文提出一种GA 与TS 的混合策略GATS.把TS 独有的记忆功能引入到GA 进化搜索过程之中,构造了新的重组算子TSR,针对GA 爬山能力差的缺陷,利用T S 爬山能力强的优点,使用TS 算法改进GA 的爬山能力,即把TS 作为GA 的变异算子TSM.GAT S 综合了GA 具有多出发点和T S 的记忆功能和爬山能力强的特点,克服了GA 爬山能力差的弱点,并保持了GA 具有多出发点的优势.设x 是一个解(染色体),则T SM 的操作过程如图3所示:beg in t =0;set the best so lution x 0=x ;set T ; w hile termina tion conditio n no t sa tisfied do t =t +1; mov e x to x ′; upda te(x ;x 0;tabu list);end图3　T SM 的操作过程T SM 与标准变异算子极为类似.首先,T SM 把一个解(染色体)作为输入(初始解),经T SM 作用,返回一个解作为输出.不同之处在于TSM 是一个搜索过程,因此需要调用评价函数来确定移动值,并根据移动值和禁忌表决定接受哪个移动(输出).同样由于T SM 是一个TS 搜索过程,在搜索过程中可以接受劣解,因此T SM 具有强于其它变异算子(例如倒位和部分倒位变异算子)的爬山能力.T SR 算子作为重组算子,使用一个长度为T 的禁忌表,表中记录染色体的适应值,渴望水平取作父代群体适应值的平均值.进行TSR 操作时,首先把子代的适应值同渴望水平相比较,如果比渴望水平好,则破禁,即这个子代染色体进入到下一代之中;如果子代比渴望水平差,但不属于禁忌,也接受这个子代;若是属于禁忌,则选择最好的那个父代进入到下一代中,具体过程如图4所示:beg in if fitness of x >av erage value o f po pulatio n,then accept x else if offspring x is not in tabu list accept x else choose the better of tw o parents to the nex t g eneratio n; upda te tabu list;end 图4　T SR 的重组过程·31·1998年9月 李大卫等:遗传算法与禁忌搜索算法的混合策略从TSR 的重组过程可以看出,具有高适应值的子代进入到下一代的机会是很大的,但是并不是所有的高适应值的子代一定都进入到下一代,因为TSR 使用了禁忌表,它可以限制适应值相同的子代出现的次数,因此可使群体中尽可能保持染色体结构的多样性,从而避免算法早熟.下面给出GA 与T S 的混合策略GATS :GATS 的求解步骤:Step 0参数设置(最大代数N gen ,群体规模N pop ,重组概率p c ,变异概率p m )Step 1令t =0;生成初始群体;Step 2计算当前代群体中染色体的适应值;Step 3选择:按滚轮方式选出N pop 个染色体,放入交配池中;Step 4重组　step 4.1生成0,1之间的随机数r i ,i =1,2,…,N pop ;如果r i <p c ,则交配池中第i 个染色体作为交叉的父代,产生均值为p c *N pop 个父代染色体;　step 4.2对每对双亲进行交叉操作,产生两个子代;　step 4.3调用TSR 对交叉后得到的子代进行重组;Stpe 5变异　step 5.1生成0,1之间的随机数r i ,i =1,2,…,N pop ;如果有r i <p m ,则调用T SM 对交配池中第i 个染色体进行变异操作;　step 5.2t =t +1;如果t <N gen ,转Step 2;否则输出最优解,终止算法.4　GATS 的性能分析在这一节中,分别用GA 及GATS 算法求解具体的TSP 问题,对n =10,67的T SP 问题分别进行求解,所用的数据分别来自文[8,9].为了比较两个算法的性能,使用本单位独自开发的求解线性规划的软件包求得最优解.此外,关心引入TSM /T SR 算子是否能提高GA 的性能,所以并不是让GA 和GATS 都收敛.相反,算法在一个预先给定的代数上停止.4.1染色体的编码应用GA 解决TSP 问题时,通常使用自然数编码构造染色体,而不使用二进制编码[2].使用自然数编码的优点在于染色体比较直观,并且无论是进行交叉操作还是进行变异操作,染色体总是能够满足T SP 问题的约束条件,即总保持染色体对应的解是可行解.因此也使用自然数对染色体进行编码.例如: P ={8,2,4,6,1,5,7,3}P 为一个染色体,表示访问顺序依次为8,2,4,…,3,8.需要注意的是,因为访问路径是一个闭合的回路,所以两个不同染色体所表示的路径可能是相等的,因此适应值也应相等.例如: Q ={2,4,6,1,5,7,3,8}尽管Q 与P 是完全不同的染色体,但是两者所表示的是相同的路径,故P 与Q 的适应值也是相等的.4.2适应值T SP 问题是求最短路径,故染色体P 的适应值f (P )定义为:·32·系　统　工　程　学　报 第13卷　第3期 f (P )=C max -问题的目标值其中C max 是一个较大的正数,它保证适应值非负.4.3遗传算子在标准GA 中,交叉算子分别取PMX,CX 和OX 算子[2],变异算子为部分倒位操作,在GATS 中,利用TSR 进行重组,其中交叉算子也分别取PMX,CX 和OX 算子,变异算子为T SM.4.4初始群体采用随机生成的办法,随机地排列自然数1,2,…,n N pop 次,构成初始群体.在实验中,GA 及GATS 使用的参数为:群体规模取为30,交叉概率和变异概率分别为0.8和0.03.对于n =10,算法在搜索100代后停止.对于n =67,算法在搜索1000代终止.表1和表2给出了实验结果,图5和图6给出了使用PM X 时GA 和GAT S 的搜索过程.表1　10个城市T SP 问题的实验结果(单位:km )GA GATS 交叉算子PM X CX OX PM X CX OX 最好值839580737373最优值73表2　67个城市T SP 问题的实验结果(单位:km )GAGATS 交叉算子PM X CX OX PM X CX OX 最好值175317951780165316791672最优值1615图5　10个城市T SP 问题的G A 和GA T S 的搜索过程(PM X ) 图5中的目标值指的是每代群体中染色体对应目标值的平均值.从图5可以看出,GA 在40代之后才达到稳态,而GAT S 在6到10代为平稳的搜索过程,从第11代开始爬山,并在13代搜索到最优解. 对于67个城市TSP 问题,GA在400代搜索到的解为2875,600代为2217,800代为1753,而GAT S 图6　67个城市T SP 问题的GA 和G A T S 的搜索过程(PM X )在400代的解为1737,600代为1653,这个值与最优解比较接近.下面讨论不使用TSR 作为重组算子时对GAT S 算法(即在GA 中只使用TSM 作为变异算子)的影响.图7是对于67个城市的TSP 问题的搜索过程. 在这种情况下,GATS 的搜索曲线变化不大,仍然能够搜索到接近最优解的近优解,但是在700代之后才搜索到,因此可以说明TSR 的引入的确能够改善GATS 的搜索效率.·33·1998年9月 李大卫等:遗传算法与禁忌搜索算法的混合策略图7　未使用T SR 的G A T S 搜索过程(PM X)最后再讨论GATS 的计算量问题.GATS 的计算量由GA 和TS 的计算量构成.当群体规模为N 时,GA 的计算量是O (N 3)[2].但在实验中发现在相同代数下GATS 的执行时间略大于GA 的执行时间.如对67城市的TSP 问题,GATS 所用的时间约是GA 所用时间的1.2倍.多出的部分主要是因为在GAT S 中变异算子TSM 是一个搜索过程,所以要占用一部分时间.5　结　论用重组算子TSR 和变异算子TSM 取代标准GA 中的重组算子和变异算子,提出了GA 算法与TS 算法的混合策略GATS,使得GATS 混合策略在许多方面优于标准GA 算法.通过求解TSP 问题,可以看出GATS 既保持了GA 具有多个解(染色体)的优点,又提高了GA 的爬山能力.参考文献1　Holland J .Adaption in na tural and ar tificia l systems .The U niv er sity of Michig an Press ,Ann Arbo r ,19752　Goldberg D.Genetic a lg orithm in search,optimizatio n and machine lea rning.Addiso n-W esley Publish-ing ,19893　Glov er F .Future Paths fo r intege r prog ra mming a nd links to ar tificial intellige nce .Co mpute rs OpsRes.,1986;5:533～5494　Glov er F,Laguna M.Tabu sear ch.In M oder n Heuristic Techniques for Com bina torial Pro blems(Edit-ed by C.Reev es),O xfo rd :Blackw ell Scientific,19935　Ackley D .Stochastic iter ated genetic hillclimbing .Ph .D .Diss .,Dept .Co mp .Sci .CM U -CS -87-107,Ca rnegie M ello n U niv er sity ,M a rch 19876　M ǜh lenbein H .Para llel g ene tic algo rithms in combinato rial optimiza tio n.Co mpute r Science a nd Opera-tio ns Resear ch (Edited by Osman Ba lci ),O x for d:Per gamo n Pr ess ,19957　Glov er F ,Kelly J ,Lag una M .Gene tic algo rithms a nd ta bu sea rch :hy brids fo r optimizatio ns .Co mput-ers Ops.Res.,1995,22(1):111～1348　Fo ulds L.Co mbinato rial fo r under g radua tes.Spring -V erlag N ew Yo rk Inc.,19849　Nemhanser G ,W olsey L .Integ er and com bina torial optimiza tio n .Wiley -Inter Science ,1986·34·系　统　工　程　学　报 第13卷　第3期。

遗传算法均匀交叉遗传算法（Genetic Algorithm）是一种高效的搜索算法，可以解决优化问题。

在求解问题过程中，遗传算法采用了生物遗传学中的进化理论，通过模拟自然选择和遗传交叉等过程来逐步优化种群。

交叉（Crossover）作为遗传算法的重要操作之一，可以有效地改变种群的结构，加快收敛速度并提高种群质量。

常用的交叉模式有两种：一是单点交叉，即对两个父代染色体进行单点切割重组；二是均匀交叉，即随机地选取每个基因位上一个父代染色体的基因，交叉生成一个新个体。

本文将重点讲解均匀交叉。

均匀交叉是遗传算法中一种常用的交叉方式，适用于连续空间中的优化问题。

其基本思想是将两个父代染色体的每一个基因位按一定概率（通常为0.5）随机地从其中选择一个基因，用从两个父代染色体选择的基因进行交叉生成一个新染色体。

由于交叉率低，新个体与父代相比具有更多的多样性和变异性。

均匀交叉的步骤如下：1）选取两个父代染色体A和B，以及交叉概率p（一般为0.5）；2）对于每一个基因位，按照p的概率从A或B中选择一个基因进行交叉，并按选中的基因放到新染色体中；3）生成一个新染色体C作为子代，用于后续的遗传操作。

均匀交叉的主要优点在于可以有效避免陷入局部最优解，增加了搜索的广度和深度，并且可以比较精确地维持种群多样性。

不过，相对于单点交叉而言，均匀交叉的计算量较大，需要耗费更多的时间和资源。

在实际应用中，交叉操作是遗传算法中一个非常重要的环节。

合理选择和应用交叉方式可以有效提高遗传算法的性能和效率。

近年来，越来越多的遗传算法研究者将均匀交叉与其他优化方法、算法结合起来，形成了一系列新的算法变种。

这些变种算法在优化搜索过程中不仅具有更好的鲁棒性，而且能够有效地避免陷入局部最优解，进而提高算法的求解能力和效率。

总之，均匀交叉是遗传算法中一种非常有效的交叉方式，在实际问题求解中广泛应用。

通过随机地选择两个父代染色体的基因进行交叉，能够有效地提高遗传算法的性能和效率，实现优化问题的高效求解。

遗传算法（Genetic Algorithm，GA）是一种模拟生物进化过程的搜索算法，它通过模拟自然选择和遗传机制来寻找问题的最优解。

在遗传算法中，交叉（Crossover）是一种重要的操作，用于将两个个体的基因组合并成一个新的个体。

下面将对遗传算法中的交叉算子进行详细讲解。

一、交叉算子的概念交叉算子是遗传算法中用于产生新的个体的一种操作，它通过将两个个体的基因组合并起来，形成新的个体。

在遗传算法中，交叉操作通常在两个父代个体之间进行，通过交换部分基因来产生新的后代。

这种操作有助于在搜索过程中保持种群的多样性，避免陷入局部最优解。

二、交叉算子的类型遗传算法中的交叉算子有多种类型，常见的包括：1. 一点交叉（Single Point Crossover）：选择两个父代个体，在它们之间随机选择一个点进行交叉。

两个父代的基因序列被分成两半，并在选定的点处交换一半的基因。

2. 均匀交叉（Uniform Crossover）：选择两个父代个体，随机选择基因序列的区间进行交叉。

通常选择一段长度为两个父代个体基因长度之和的区间进行交叉，以产生新的子代个体。

3. 配对交叉（Pairwise Crossover）：这是一种更高级的交叉方法，它允许父代个体之间进行一对一的交叉操作。

这种方法有助于保持种群的多样性，并减少搜索过程中的基因浪费。

4. 变异交叉（Mutation Crossover）：在某些情况下，可以在交叉操作之前或之后进行变异操作，以引入一些随机性。

变异交叉是在基因序列上随机引入突变位点，以保持种群的随机性。

三、交叉算子的应用交叉算子在遗传算法中起着至关重要的作用，它有助于产生新的个体，并在搜索过程中保持种群的多样性。

通过交叉操作，遗传算法能够跳出局部最优解，并逐渐向全局最优解逼近。

在实际应用中，根据问题的特性和搜索空间的大小，可以选择合适的交叉算子来优化搜索过程。

总之，遗传算法中的交叉算子是实现种群多样性和产生新个体的关键操作。