遗传算法的特点及其应用

遗传算法的特点及其应用

上海复旦大学附属中学张宁

目录

【关键词】

【摘要】

【正文】

§1遗传算法的基本概念

§2简单的遗传算法

1．选择

2．交换

3．变异

§3简单的遗传算法运算示例

1．计算机公司的经营策略优化问题

2．函数优化问题

§4遗传算法应用举例

1．子集和问题

2．TSP（旅行商）问题

§5结束语

【附录】

1．子集和问题源程序

2．TSP（旅行商）问题源程序

【参考文献】

【关键词】

遗传算法遗传变异染色体基因群体

【摘要】

遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。

文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。

文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。

【正文】

遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。

要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。

§1遗传算法的基本概念

遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它

根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。

对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，GA 提供了一个行之有效的新途径，也为人工智能的研究带来了新的生机。

GA由美国J. H. Holland博士1975年提出，当时并没有引起学术界的关注，因而发展比较缓慢。从80年代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域（如机器学习和神经网络），也开始在工业系统，如控制、机械、土木、电力工程中得到成功应用，显示出了诱人的前景。与此同时，GA也得到了国际学术界的普遍肯定。

从1985年至今国际上已举行了五届遗传算法和进化计算会议，第一本《进化计算》杂志1993年在MIT创刊，1994年IEEE神经网络汇刊出版了进化规划理论几应用专集，同年IEEE将神经网络，模糊系统，进化计算三个国际会议合并为’94IEEE全球计算智能大会（WCCI），会上发表进化计算方面的论文255篇，引起了国际学术界的广泛关注。

目前，GA已在组合优化问题求解、自适应控制、程序自动生成、机器学习、神经网络训练、人工生命研究、经济组合等领域取得了令人著目的应用成果，GA 也成为当前人工智能及其应用的热门课题。

§2简单的遗传算法

遗传算法（Genetic Algorithms，以下简称GA）是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。

在自然界的演化过程中，生物体通过遗传（传种接代，后代与夫辈非常相像）、变异（后代与夫辈又不完全相像）来适应外界环境，一代又一代地优胜劣汰，发展进化。

GA则模拟了上述进化现象。它把搜索空间（欲求解问题的解空间）映射为遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字串），称为一个染色体（chromosome，或个体），向量的每一个元素称为基因(genes)。所有染色体组成群体（population，或集团）。并按预定的目标函数（或某种评价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等）对每个染色提进行评价，根据其结果给出一个适应度的值。

算法开始时先随机地产生一些染色体（欲求解问题的侯选解），计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低（性能不佳）的染色体，留下适应度高（性能优良）的染色体，从而得到新的群体。

由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上明显优于上一代。GA就这样反复迭代，向着更优解的方向进化，直至满足某种预定的优化指标。上述GA的工作过程可用图1简要描述。

简单遗传算法的三个基本运算是选择、交换、变异，下面详细介绍。

1． 选择

选择运算又称为繁殖、再生，或复制运算，用于模拟生物界去劣存优的

自然选择现象。它从旧种群中选择出适应性强的某些染色体，放入匹配集（缓冲区），为染色体交换和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，其遗传基因在下一代群体中的分布就越广，其子孙在下一代出现的数量就越多。有多种选择方法，使用比较普遍的一种是适应度比例法，简述如下：

适应度比例法又称为轮转法，它把种群中所有染色体适应度的总和看作一个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子的一个扇区。每次染色体的选择可看作轮子的一次随机转动，它转到哪个扇区停下来，那个扇区对应的染色体就被选中。其实就是将适应度值视为其权值，权值大的被选中的概率也大。尽管这种选择方法是随机的，但它与各染色体适应度成比例。某一染色体被选中的概率（选择概率）为

Y

问题的初始（侯选）解 种群满足预定指标

编码为染色体（向量）

种群P （t ） 计算各染色体适应度

通过遗传运算存优去劣

种群P （t+1）

复制 交换 变异

种群P （t ） 种群P （t+1）

解码染色体 问题解答空间

N

图1 遗传算法工作原理示意图

∑=)(/)(i c c x f x f P

式中x i 为种群中第i 个染色体对应的数字串，f(x i )是第i 个染色体的适应度值，∑)(i x f 是种群中所有染色体的适应度值之和。

用适应度比例法进行选择时，首先计算每个染色体的适应度，然后按比例于各染色体适应度的概率进入交换（匹配）集的染色体，其具体步骤如下：

（1） 计算每个染色体的适应度值f(x i )； （2） 累加所有染色体的适应度值，得最终累加值SUM=∑)(i x f ，记录对应于每个染色体的中间累加值g(x i )； （3） 产生一个随机数N ，0

集。 （5） 重复（3），（4），直到交换集中包含足够多的染色体数字串为止。 重复上述过程，直到交换集中包含足够多的染色体为止。显然，此法要求染色体的适应度应为正值。请看下例：

[例1]：某种群包含10个染色体，按适应度比例法选择进入交换集的过程示于表1及表2。

表1

染色体编号 1 2 3 4 5 6 7 8 9 10 适应度 8 2 3 16 6 12 11 7 3 7 选择概率 0.11 0.03 0.04 0.21 0.08 0.16 0.15 0.09 0.04 0.09 适应度累加值 8 10 13 29 35 47 58 65 68 75

表2

随机数 23 49 70 14 28 37 57 所选染色体号 4 7 10 4 4 6 7

由表1,表2可以看到，3号染色体的选择概率最高，被选中的次数最多，其他选择概率较低的染色体被选中的次数就少。当然，用适应度比例法进行选择时，性能最坏的染色体也可能被选择，但概率极小，当种群长度较大时，这种情况可以忽略不计。

2． 交换

复制操作虽然能够从旧种群中选择出优秀者，但不能创造新的染色体，因此，遗传算法的开创者提出了交换操作。它模拟生物进化过程中的繁殖现象，优良品种，即：在匹配集中任选两个染色体（称为双亲的染色体）；随机选择一点或多点交换点位置J （0

[例2]：从匹配集中取出的一对染色体为： 染色体A 0111|1010 染色体B 0101|0010

随机产生的一点交换位置是4，交换染色体A，B中第4位右边的部分——1010和0010，则得两个下一代（子孙）染色体数字串：

染色体A’ 01111010

染色体B’ 01010010

3．变异

变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，它以很小概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变成0，或由0变成1。若只有选择和交换，而没有变异操作，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而终止进化过程，从而使解的质量受到很大限制。通过变异操作，可确保群体中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解，获得质量较高的优化解答。

§3简单的遗传算法运算示例

让我们从下面两个非常简单的例子来具体了解一下简单遗传算法的各种操作。虽然下面的例子都有更好处理方式，但为了深入了解遗传算法的各种操作，还是从简单的例子入手：

[例3]：计算机公司的经营策略优化问题

一个计算机公司追求的目标是最高的利润，为达此目标，必须选择适当的经营策略。一种可能的策略是对以下四个问题作出决策：

·每台PC计算机的价格定为5000元（低价）还是8000元（高价）；

·与PC机配套的免费软件是Windows2000还是Linux；

·是否提供网络技术服务；

·提供保修期为半年或是一年；

下面用遗传算法来解决这个决策优化问题。

（1）把问题的可能解表示为染色体数字串。因为有四个决策变量，而每个变量只有两种选择，其取值可用0或1来表示，于是，可用四位的二进制数表示一种可能的经营策略，解的搜索空间为24=16，即共有16种经营策略可供选择，表3表示出了其中计算机公司经理已知的4种经营策略（初始解答）。表中数字串的第一位取0表示高价，1表示低价；第二位取0表示Windows2000，1表示配套Linux；第三位取0表示不支持网络技术服务，1表示支持网络技术服务；第四位取0表示保修期为一年，1表示表示保修期为半年。

表3 问题的初始解答

序号价格配套软件网络服务保修期染色体数字串

1 高Linux 支持一年0110

2 高Windows2000 支持半年0011

3 低Linux 不支持一年1100

4 高Linux 不支持半年0101

（2）求各染色体的适应度。在这个问题中，我们不妨设染色体的适应度就是染色体的二进制数字串的数值，对应经营策略的利润。

表4 第0代种群的适应度

序号i 染色体串x

i 适应度f(x

i

)

1 0110 6

2 0011 3

3 1100 12

4 0101 5

适应度总和26

最坏适应度 3

最好适应度12

平均适应度 6.5

（3）选择进入交换集的染色体

由表4可知，所有染色体串适应度的总和是26，串1100的适应度是12，占适应度总和的6/13，也就是串1100被选中的机会接近两次；串0110，0011，0101被选中的概率分别是3/13，3/26，5/26。按前述适应度比例法，选择进入交换集的染色体串及其适应度情况如表5所示。

表5 第0代种群选择后的适应度

序号i 染色体串x

i 适应度f(x

i

)

1 0110 6

2 1100 12

3 1100 12

4 0101 5

适应度总和35

最坏适应度 5

最好适应度12

平均适应度8.75

由表5可知，选择操作的作用是改进了种群的平均适应度，使其由原来的6.5提高到了8.75，最坏适应度由原来的3改进为5，性能最差的染色体已从种群中删除。但是，选择不能创造新的染色体，须进行交换操作。（4）交换操作

设采用单点交换，随机产生的交换点是2，从交换集中任取一对染色体1100和0101，互换它们的第3，4位，得子孙染色体串1101和0100。

由此得到下一代种群。如表6所示。

表6 第1代种群的适应度

序号i 染色体串x

i 适应度f(x

i

)

1 0110 6

2 1101 13

3 1100 12

4 0100 4 适应度总和 3

5 最坏适应度 4 最好适应度 13 平均适应度 8.75

（5） 估新一代的种群的适应度

由表6可知，在新一代（第1代）种群中，最优染色体适应度由原来12提高到了13，其对应的二进制串是1101，表示一种优化的经营策略。平均适应度由原来的6.5提高到8.75，整个种群的适应度从总体上提高了，被优化了。

遗传算法重复地执行每一代的运算操作，产生新的一代，直到满足某些终止标准或条件。在本例中，假定已知染色体数字串1111代表的是已知的最好利润15%，则遗传算法停止运行。 [例4]：函数优化问题

设有函数f(x)=2x 2-5x+4（x ∈Z ，x ∈[0，63]），求其在区间内的最大值。下面用遗传算法求解这一问题。 （1） 确定适当的编码，把问题的可能解表示为染色体数字串。因为有一个决策

变量x ，其取值范围为[0，63]，26=64，使用6位无符号二进制数组成染色体数字串，即可表达变量x ，以及问题的解答方案。

（2） 选择初始种群。通过随机的方法产生由4个染色体数字串组成的初始种

群，见表7。

（3） 计算适应度值及选择概率。此问题中染色体的适应度取函数自身

f(x)=2x 2-5x+4。将每个染色体的f(x)计算出来，作为适应度值。在此基础上计算选择概率P s =∑f f i /。

（4） 选择进入交换集的染色体。按适应度比例法，选择进入交换集的染色体串，

如表8。可见，染色提1和2都被选择了1次；染色体4被选择了2次；染色体3没有被选择。所选的4个染色体被送到交换集，准备参加交换。 （5） 交换染色体。首先对进入交换集的染色体进行随机配对，此例中是染色体

1和3配对，染色体2和4配对。接着随机确定交换位置，结果是第1对染色体的交换位置是1，第2对染色体的交换位置是4。经过交换操作后

表7 函数优化过程 编号 染色体

X 值 适应度（目标函数）f(x)=2x 2-5x+4 选择概率

∑f f i /

实选染色

体编号

1 011010 26 1226 0.15 1

2 100100 36 2416 0.29 1

3 010101 21 781 0.09 0

4 101110 46 4006 0.48 2 和 8429 1 4 平均 2107.2

5 0.25 1 最大 400

6 0.49 2

得到的新种群如表8所示。

（6） 变异。若此例中变异概率取0.01。由于种群中4个染色体总共只有24位

代码，变异的期望值为24*0.01=0.24位，可以忽略不计。

表8 函数优化过程

复制后交换集种群 交换配对 交换位置 新染色体 X 值 适应度（目标函数）f(x)=2x 2-5x+4 011010 3 3 001110 14 326 100100 4 4 100110 38 2702 101110 1 3 111010 58 6442 101110 2 4 101100 44 3656 和 13126 平均 3281.5 最大 6442

从表8可以看出，虽然仅进行了一代遗传操作，但种群适应度的平均值及最大值却比初始群有了很大提高，平均值由2107.25变到3281.5，最大值由4006变到6442。这说明随着遗传运算的进行，种群正向着优化的方向发展。

§4遗传算法应用举例

1.[例5]：GA 在子集和问题上的应用

子集和问题SUBSET_SUM ：给定正整数集合S 和一个整数t ，判定是否存在S 的一个子集S S ?'使得S’中整数的和为t 。

例如，若S={1，4，16，64，256，1040，1041，1093，1284，1344}且t=3754，则子集S’={1，16，64，256，1040，1093，1284}是一个解。

设子集和问题的一个实例为。其中，S 是一个正整数的集合{x 1，x 2，…，x n }，t 是一个正整数。子集和问题要求判定是否存在S 的一个子集S’，使得∑∈='

S x i i t x 。我们已知道该问题是一个NP-完全问题。在实际应用中，我们常遇

到的是最优化子集和问题。在这种情况下，我们要找出S 的一个子集S’，使得其和不超过t ，但又尽可能接近于t 。例如，我们有一辆载重车，其载重量不能超过t 公斤。有n 个不同的箱子要用载重车来装运，其中第i 个箱子重x i 公斤。我们希望在不超过载重限制的前提下将载重车尽可能地装满。这个问题实质上就是一个最优化形式的子集和问题。

下面用遗传算法来解决： 若集合S 中元素的个数为n ，每个元素只有两种可能：属于S’或不属于S’。因此我们可以用n 为二进制数来表示每个染色体。每一位，若为0则说明这个元素不属于S’，若为1则说明这个元素属于S’。

确定了问题的描述方式，我们只需随机取出染色体组成初始群体。接着，便可以按前所述，进行选择、交换以及变异运算。

我们将染色体所表示的子集的元素和与所给t 的差异记为适应度。 即令染色体x 的每一位为x i ，所表示元素的值为S i 则 t S x f i x i -=∑≠0

)(

但是经过实践后发现由于适应度相对差异较小，使得适应度非常接近，难以区分优秀的染色体，使得遗传进化变得非常缓慢，且f(x)可能为负值，因此还需对适应度函数做一下变换，才可以适合本题的要求。

令|f(k)|为当前群体中所有染色体适应度的最大值 f’(x)=|f(k)-f(x)| 所以适应度为f’(x)。

选择时可以用前面所介绍的适应度比例法，但采用随机方式，可能会出现随机错误，使得优秀的染色体没有子孙。因此，在这里我们对选择方法作一下改进，采用确定性选择法，使得选择不依靠随机的好坏，先计算群体中每个串的生存概率∑=j i s f f P /，1

接着可以进行交换运算，交换运算与前述相同，不过若进行单点交换有可能使得两个染色体在交换时产生的差异过大，使得遗传变得不稳定，优秀的染色体不能遗传到下一代。因此可以采用多点交换，不过本题中只需进行两点交换即可，其实两点交换与单点交换是类似的。

设有两个父辈染色体A 和B ： A ：10100100101110 B ：01001110110001

设两个交换点选择如下： A ：10100|10010|1110 B ：01001|11011|0001

则两点交换运算就是交换染色体A 和染色体B ，两个交换点之间的部分，则交换结果如下：

A’：10100110111110 B’：01001100100001 交换运算完成后，可进行变异运算，变异运算时，只需注意变异概率的取值，至于具体算法如前面所述。

在本题中的一些数值不妨取值如下： 种群长度（染色体个数）：20 选择概率：0.9 变异概率：0.1

结束条件：当前最优解在100代遗传后仍未改变，或已取到最优解

2.[例6]：GA 在TSP （旅行商）问题求解中的应用

设存在N 个城市， D ij 表示城i 与城j 之间的距离， D ij =D ji ，现在要求一条遍历所有N 个城市，且不走重复路的最短路径（最短哈密尔顿圈）。

这是一个典型的排列顺序问题，属于NP-完全问题。传统解法诸如：限界剪枝法，或是最小支撑树算法，对此都并不太奏效（或是运算速度上的缺陷，或是解的质量上的缺陷）。下面我们试着用遗传算法来解决这道题目。

我们先采用十进制编码，每个染色体由按一定顺序排列的N 个城市的序号组

成，表示一条可能的旅行路径，其中每个基因表示一个城市。染色体的长度为N ，解空间为N!。适应度为一条旅行路径对应的距离，路径越短的染色体适应度越高。例如，取N=10，城市代号为1，2，3，4，5，6，7，8，9，10。

则种群中的染色体：2 8 4 10 5 1 7 3 6 9；

表示一条旅行路径：2→8→4→10→5→1→7→3→6→9→2；

其总路径长9269367317511054108428D D D D D D D D D D D ij +++++++++=∑ 我们可以采用非负变换，把最小化优化目标函数变换为以最大值为目标的适应度函数，可以如下定义：

∑-=ij D c x f max )( 其中c max 为可以取为进化过程中路径长度的最大值，或者为了保证f(x)为正而预先设定为一个与种群无关的常数。

下面介绍具体算法：

首先我们由城市数目N ，可以确定染色体长度为N ，染色体的基因代码由城市编码组成。但是，我们仍须确定种群长度、变异概率等参数。这些参数都由人为确定，与算法无关，可暂时不考虑，讨论完算法后，可再行确定具体数值。

随机组合成染色体，每个染色体须表示一条哈密尔顿回路，生成初始种群。然后分别计算每一个染色体的适应度，按适应度比例法选择染色体到交换集。不过，我们也可以考虑一下改进后的选择方法。

适应度比例法实现简单，缺点是选择过程中最好的染色体可能在下一代产生不了子孙，可能发生随机错误。因此我们可以采用择优选择法，即对于群体中最优秀（适应度最高）的染色体不进行交换和变异运算，而是直接把它们复制到下一代。以免交换和变异运算破坏种群中的优秀解答。这种方法可加快局部搜索速度，但又可能因群体中优秀染色体的急剧增加而导致搜索陷入局部最优解。同时，我们也可以采用确定性选择法，使得选择不依靠随机的好坏，先计算群体中每个串的生存概率∑=j i s f f P /，1

完成选择运算后，可以进行交换运算。但是，此处的交换运算不同于前，须改进原有的交换运算，具体做法如下：

因为两个染色体，若进行简单的交换运算，可能会使得染色体所表示路径中会重复经过同一城市，即同一染色体中的两个基因有着相同的城市编号。这就造成了染色体不再表示一条哈密尔顿回路，因此须改进交换运算。

我们可以采用部分匹配交换运算（PMX ）。它先用随机均匀分布方法在欲交换两父染色体串中各产生两个交换点，把这两点之间的区域定义为匹配区域，再对两个匹配区域中的基因通过对应匹配置换。例如，两父染色体串为：

A ： 2 8 4 10 * 5 1 7 3 * 6 9

B ： 5 6 7 1 * 10 2 8 3 * 9 4 符号“*”表示交换点。

对染色体串A ，其匹配区域中有四个元素5，1，7，3，应与染色体串B 匹配区域中的四个元素10，2，8，3，逐一匹配，即通过在染色体串A 内进行元素间的置换，使得匹配区域内这四个元素换为10，2，8，3。为此，染色体串A 中的

元素作如下置换：

对染色体串B，其匹配区域中有四个元素10，2，8，3，应与染色体串A匹配区域中的四个元素5，1，7，3，逐一匹配，即通过在染色体串B内进行元素

A：2 8 4 10 * 5 1 7 3 * 6 9

A’：1 7 4 5 * 10 2 8 3 * 6 9

间的置换，使得匹配区域内这四个元素换为5，1，7，3。为此，染色体串B中的元素作如下置换：

B：5 6 7 1 * 10 2 8 3 * 9 4

B’：10 6 8 2 * 5 1 7 3 * 9 4

当然，在本题中最简单的做法是不进行交换运算，而直接进行变异运算，因为在变异运算中本就隐含了交换的含义。

对于群体中某些染色体进行变异运算，由于基因采用的是城市编码，变异操作与二进制编码时不同，从群体中随机抽取一个染色体，随机抽取两个基因，将两者交换，即颠倒城市次序，用以完成变异运算。

当然我们还需确定一下终止条件，因为目前使用严格的数学方法判定遗传算法的终止（收敛）条件还比较困难。因此，在实现时采用的主要还是启发式方法，我们可以以连续几次迭代后得到的解群中最优解是否变化来作为终止时的判定条件。

算法的主要部分已经讨论完了，但是还有一点值得提出的，由于遗传算法是一种不断优化的搜索算法，因此给出的初始群体的优劣程度会影响到最终解答的优劣程度及其出解速度。因此，我们可以用贪心算法构造初始群，或当TSP问题具有三角不等式性质时，我们可以考虑先使用速度较快的最小支撑树算法的解答来构造初始群。

我们再考虑用最小支撑树算法来构造初始群是有利有弊，由于有了高质量的初始群使得遗传算法能在较短的时间内收敛，且得到的解有质量上的保证，稳定性也高。但是由于初始群的优秀，对于后代的影响很大，容易造成过早收敛于局部最优解，因此在使用时，需按情况而定，在解的要求、时间上的要求综合考虑下作出决定。这些，是我在解决TSP问题时，总结的一些经验，希望能对大家在解决问题的过程中有一定的指导意义。

题目中的一些数值不妨取值如下：

种群长度（染色体个数）：20

变异概率：0.1

通过两道例题，我们在遗传算法原有简单定义上，加以扩充，介绍了若干高级遗传算法在具体实例中的应用，旨在打开思想的局限性，不仅仅在原有简单定义下做文章，而是充分发挥想象，对于不同问题，采取不同对策，在遗传算法的

框架下，安排使用合理的算法，改进原有算法，或与原有算法相结合。这样，才能充分发挥遗传算法的长处解决问题。

§5结束语

遗传算法的原理是简单的，但是如何熟练运用遗传算法却并不是一个简单的问题，理论要结合实际，对于不同问题，遗传算法要稍加变化，就如同画龙点睛一般，切忌不可生搬硬套。我认为遗传算法应当与现有优化算法结合，可产生比单独使用遗传算法或现有优化算法更好，更实用的算法。

本文的主要目的还是让大家对遗传算法能够有一个初步的了解，这样对大家进行深入的实践是有帮助的。希望大家通过本文的指导，能够将遗传算法熟练应用在各个方面。

【附录】

1.例5子集和问题源程序：

program subset_sum_GA;

const inp='subset.in';{输入文件}

out='subset.out';{输出文件}

maxn=1000;{集合最大元素个数}

pl=20;{群体中染色体个数}

pc=10;{交换次数}

pv=0.1;{变异概率}

ec=100;{结束条件}

type ch=array[1..maxn] of 0..1;

var sset:array[1..maxn] of integer;{集合}

pop,pop1:array[1..pl] of ch;{群体}

result:ch;{结果}

n:integer;{集合元素个数}

t{子集和},sum{集合元素和},diff{当前最优解的差距}:longint;

procedure input;{输入}

var fin:text;

i:integer;

begin

assign(fin,inp);

reset(fin);

readln(fin,n,t);

for i:=1 to n do

readln(fin,sset[i]);

close(fin);

end;

procedure init;{初始化}

var i,j,k:integer;

begin

randomize;

sum:=0;

for i:=1 to n do

inc(sum,sset[i]);

if sum<=t then

begin

for i:=1 to n do

result[i]:=1;

exit;

end;

k:=trunc(sum/t)+1;

for i:=1 to pl do

begin

for j:=1 to n do

if random(k)=0 then

pop[i,j]:=1

else

pop[i,j]:=0;

end;

diff:=t;

end;

procedure solve;{遗传算法}

var f1:array[1..pl] of longint;{适应度}

dc,pr:integer;

work:boolean;

procedure select;{选择运算}

var f:array[1..pl] of longint;{适应度}

g:array[1..pl] of integer;{复制数}

fs,fm:longint;

i,j,k:integer;

begin

fm:=0;

for i:=1 to pl do

begin{计算适应度}

f[i]:=0;

for j:=1 to n do

inc(f[i],sset[j]*pop[i,j]);

f[i]:=f[i]-t;

if (f[i]<0) and (abs(f[i])

diff:=abs(f[i]);

dc:=0;

result:=pop[i];

end;

if f[i]=0 then

begin

work:=false;

exit;

end;

if abs(f[i])

fs:=f[i];

end;

inc(dc);

for i:=1 to pl do{适应度作变换}

if f[i]<0 then

f[i]:=fm+f[i]

else

f[i]:=fm-f[i];

fs:=0;

for i:=1 to pl do{计算适应度和}

inc(fs,abs(f[i]));

k:=0;

for i:=1 to pl do

begin{分配复制数}

g[i]:=trunc(abs(f[i])/fs*pl);

inc(k,g[i]);

end;

while k

begin

inc(g[random(pl)+1]);

inc(k);

end;

k:=0;

for i:=1 to pl do{复制到交换集}

for j:=1 to g[i] do

begin

inc(k);

pop1[k]:=pop[i];

f1[k]:=f[i];

end;

pop:=pop1;

end;

procedure cross;{交换运算}

var i,j,k,u,v,p,q:integer;

begin

for i:=1 to pc do

begin

u:=random(pl)+1;{染色体A}

v:=random(pl)+1;{染色体B}

p:=random(n)+1;{交换点1}

q:=random(n)+1;{交换点2}

if p>q then

begin

k:=p;

p:=q;

q:=k;

end;

k:=0;

for j:=p to q do

inc(k,pop[u,j]-pop[v,j]);{计算交换部分差距}

if not (((f1[u]<0) and (f1[v]>0) and (k>0)) or

((f1[u]>0) and (f1[v]<0) and (k<0))) then{若差异变大则不交换}

continue;

dec(f1[u],k);

inc(f1[v],k);

for j:=p to q do

begin{交换}

k:=pop[u,j];

pop[u,j]:=pop[v,j];

pop[v,j]:=k;

end;

end;

end;

procedure variety;{变异运算}

var i,j,k:integer;

begin

for i:=1 to pr do

begin

j:=random(pl)+1;{染色体}

k:=random(n)+1;{基因}

if ((f1[j]<0) and (pop[j,k]=0)) or {变异} ((f1[j]>0) and (pop[j,k]=1)) then

begin

inc(f1[j],(1-2*pop[j,k])*sset[k]);

pop[j,k]:=1-pop[j,k];

end;

end;

end;

begin

if sum<=t then

exit;

work:=true;

pr:=round(n*pl*pv);{计算变异次数}

dc:=0;

while work do

begin

select;{选择}

if dc>ec then

exit;{是否满足结束条件}

if work then

begin

cross;{交换}

variety;{变异}

end;

end;

end;

procedure output;{输出}

var fout:text;

i,k:integer;

s:longint;

begin

assign(fout,out);

rewrite(fout);

s:=0;

k:=0;

for i:=1 to maxn do

if result[i]=1 then

begin

inc(s,sset[i]);

inc(k);

end;

writeln(fout,s);

writeln(fout,k);

for i:=1 to maxn do

if result[i]=1 then

writeln(fout,i);

close(fout);

end;

begin{主程序}

input;

init;

solve;

output;

end.

说明：

在子集和问题中，随机构造的数据基本上都能达到最优解，偶尔也会收敛到准最优解。总体情况非常良好。

2.例6 TSP问题源程序

program TSP_GA;

const inp='tsp.in';{输入文件}

out='tsp.out'; {输出文件}

maxn=100;{城市最大值}

pl=100;{染色体个数}

pv=0.1;{遗传概率}

ec=100;{结束条件}

no=10000;{无通路}

type ch=array[1..maxn] of integer;

var d:array[1..maxn,1..maxn] of integer;{邻接矩阵}

pop,pop1:array[1..pl] of ch;{染色体}

result:ch;{结果}

n:integer;{城市个数}

min:longint;{当前最短路径长度}

procedure input;{输入}

var i,j:integer;

fin:text;

begin

assign(fin,inp);

reset(fin);

readln(fin,n);

for i:=1 to n do

for j:=1 to n do

begin

read(fin,d[i,j]);

if d[i,j]=-1 then

d[i,j]:=no;

end;

close(fin);

end;

procedure init;{初始化}

var temp:ch;

i:integer;

procedure greedy;{贪心}

var use:array[1..maxn] of boolean; i,j,k,min,r:integer;

begin

r:=random(n)+1;

fillchar(use,sizeof(use),true);

temp[1]:=r;

use[r]:=false;

for i:=2 to n do

begin

min:=no+1;

k:=0;

for j:=1 to n do

if use[j] then

if d[r,j]

begin

min:=d[r,j];

k:=j;

end;

temp[i]:=k;

use[k]:=false;

r:=k;

end;

end;

begin{构造初始群}

randomize;

for i:=1 to pl do

begin

greedy;

pop[i]:=temp;

end;

min:=no;

end;

procedure solve;{遗传算法}

var f1:array[1..pl] of longint;

dc,pr:integer;

work:boolean;

function suit(a:ch):longint;{适应度} var p:longint;

begin

p:=0;

for i:=1 to n-1 do

inc(p,d[a[i],a[i+1]]);

inc(p,d[a[n],a[1]]);

suit:=p;

end;

procedure select;{选择}

var f:array[1..pl] of longint;

g:array[1..pl] of integer;

fs,fm:longint;

i,j,k:integer;

begin

fm:=0;

for i:=1 to pl do

begin

f[i]:=suit(pop[i]);

if f[i]

begin

min:=f[i];

result:=pop[i];

dc:=0;

end;

if f[i]>fm then

fm:=f[i];

end;

inc(dc);

fs:=0;

for i:=1 to pl do

inc(fs,fm+1-f[i]);

for i:=1 to pl do

g[i]:=trunc((fm+1-f[i])/fs*pl); k:=0;

for i:=1 to pl do

for j:=1 to g[i] do

begin

inc(k);

pop1[k]:=pop[i];

f1[k]:=f[i];

end;

for i:=k+1 to pl do

begin

pop1[i]:=result;

f1[i]:=min;

end;

pop:=pop1;

end;

procedure variety;{变异}

var i,j,k,l,p:integer;

t:longint;

begin

for i:=1 to pr do

begin

j:=random(pl)+1;

k:=random(n)+1;

l:=random(n)+1;

temp:=pop[j];

p:=temp[k];

temp[k]:=temp[l];

temp[l]:=p;

t:=suit(temp);

if t

begin

pop[j]:=temp;

f1[j]:=t;

end;

end;

end;

begin

work:=true;

pr:=round(n*pl*pv);

dc:=0;

while true do

begin

select;

if dc>ec then

exit;

if work then

variety;

end;

end;

procedure output;{输出}

var i:integer;

fout:text;

begin

assign(fout,out);

rewrite(fout);

for i:=1 to n do

writeln(fout,result[i]);

close(fout);

end;

begin{主程序}

input;

init;

solve;

output;

end.

说明：

遗传算法的优缺点

遗传算法属于进化算法( Evolutionary Algorithms) 的一种, 它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子: 选择、交叉和变异. 。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法( GA)。算法中称遗传的生物体为个体( individual )，个体对环境的适应程度用适应值( fitness )表示。适应值取决于个体的染色体(chromosome),在算法中染色体常用一串数字表示，数字串中的一位对应一个基因 (gene)。一定数量的个体组成一个群体(population )。对所有个体进 行选择、交叉和变异等操作,生成新的群体,称为新一代( new generation )。遗传算法计算程序的流程可以表示如下［3］：第一步准备工作 (i)选择合适的编码方案，将变量(特征)转换为染色体(数字串，串长为m。通常用二 进制编码。 (2 )选择合适的参数，包括群体大小(个体数M)、交叉概率PC和变异概率Pm (3、确定适应值函数f (x、。f (x、应为正值。 第二步形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中，取已分析的可能滑裂 面组作为初始群体。 第三步对每一染色体(串)计算其适应值fi ,同时计算群体的总适应值。 第四步选择 计算每一串的选择概率Pi=fi/F 及累计概率。选择一般通过模拟旋转滚花轮 ( roulette ,其上按Pi大小分成大小不等的扇形区、的算法进行。旋转M次即可选出M个串来。在计算机 上实现的步骤是：产生［0,1］间随机数r，若rpc ,则该串参加交叉操作,如此选出参加交叉的一组后,随机配对。 (2)对每一对，产生［1 , m］间的随机数以确定交叉的位置。 第六步变异 如变异概率为Pm则可能变异的位数的期望值为Pm x mx M,每一位以等概率变异。具体为 对每一串中的每一位产生［0 , 1］间的随机数r,若r

遗传算法应用论文

论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日

摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由

基本遗传算法及应用举例

基本遗传算法及应用举例 遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。 针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L 为一固定的数，如 X=1010100 表示一个个体，该个体的染色体长度L=20。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a ，b]，我们用长度为L 的二进制编码符号串来表示该参数，总共能产生L 2种不同的编码，若参数与编码的对应关系为 00000000000……00000000=0 →a 00000000000……00000001=1 →a+δ ? ? ? ……=L 2-1→b 则二进制编码的编码精度1 2--= L a b δ 假设某一个个体的编码是kl k k k a a a x 21=，则对应的解码公式为 )2(121 ∑=---+=L j j L kj L k a a b a x 例如，对于x ∈[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串：

基于数据挖掘的遗传算法

基于数据挖掘的遗传算法 xxx 摘要:本文定义了遗传算法概念和理论的来源，介绍遗传算法的研究方向和应用领域，解释了遗传算法的相关概念、编码规则、三个主要算子和适应度函数，描述遗传算法计算过程和参数的选择的准则，并且在给出的遗传算法的基础上结合实际应用加以说明。 关键词：数据挖掘遗传算法 Genetic Algorithm Based on Data Mining xxx Abstract：This paper defines the concepts and theories of genetic algorithm source, Introducing genetic algorithm research directions and application areas, explaining the concepts of genetic algorithms, coding rules, the three main operator and fitness function，describing genetic algorithm parameter selection process and criteria，in addition in the given combination of genetic algorithm based on the practical application. Key words: Data Mining genetic algorithm 前言 遗传算法(genetic algorithm，GAs)试图计算模仿自然选择的过程，并将它们运用于解决商业和研究问题。遗传算法于20世界六七十年代由John Holland[1]发展而成。它提供了一个用于研究一些生物因素相互作用的框架，如配偶的选择、繁殖、物种突变和遗传信息的交叉。在自然界中，特定环境限制和压力迫使不同物种竞争以产生最适应于生存的后代。在遗传算法的世界里，会比较各种候选解的适合度，最适合的解被进一步改进以产生更加优化的解。 遗传算法借助了大量的基因术语。遗传算法的基本思想基于达尔文的进化论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。生物在自然界的生存繁殖，显示对其自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机制研究和行为模拟。通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。现在已经广泛的应用于计算机科学、人工智能、信息技术及工程实践。[2]在工业、经济管理、交通运输、工业设计等不同领域，成功解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法作为一类自组织于自适应的人工智能技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。 1.遗传算法的应用领域和研 究方向 1.1遗传算法的特点 遗传算法作为一种新型、模拟生物进化过程的随机化搜索方法，在各类结 构对象的优化过程中显示出比传统优 化方法更为独特的优势和良好的性能。 它利用其生物进化和遗传的思想，所以 它有许多传统算法不具有的特点[3]： ※搜索过程不直接作用在变量上，而是 作用于由参数集进行了编码的个体 上。此编码操作使遗传算法可以直接 对结构对象进行操作。 ※搜索过程是从一组解迭代到另一组 解，采用同时处理群体中多个个体的 方法，降低了陷入局部最优解的可能 性，易于并行化。

第七章遗传算法应用举例

第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。 7.1 简单一元函数优化实例 利用遗传算法计算下面函数的最大值： ()sin(10) 2.0[1,2]f x x x x π=?+∈-， 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。 下面为一元函数优化问题的MA TLAB 代码。 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 = variable.*sin (10*pi*variable)+2.0; % 计算目标函数值 while gen < MAXGEN, FitnV = 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 =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值 [Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加 % 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号 [Y,I]=max(ObjV),hold on; plot (variable (I),Y , 'bo'); trace (1,gen)=max (ObjV); %遗传算法性能跟踪

遗传算法的研究及应用

龙源期刊网 https://www.docsj.com/doc/5e8981885.html, 遗传算法的研究及应用 作者：彭志勇邓世权 来源：《计算机光盘软件与应用》2013年第07期 摘要：遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式，它可以应用与生活中的很多领域。 关键词：遗传算法；函数优化；生产调度；自动控制 中图分类号：TP183文献标识码：A文章编号：1007-9599 (2013) 07-0000-02 遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式。与传统的数学模型进行比较，遗传算法有很多的不同的地方，因为它能够解决很多复杂的问题，而传统的数学模型却没办法做到。 1遗传算法的理论研究 1.1遗传算法的由来。美国密西根大学的霍兰德（Holland）将该算法应用于自然和人工系统的自适应行为的研究之中，并且在二十世纪七十年代中期，出版他的第一部著作《自然与人工系统中的适应》。随后，Holland与他的学生们将该算法进行了大力的推广，并把它应用到优化及机器学习等问题之中，而且正式定名为遗传算法。 1.2遗传算法的发展。遗传算法的兴起于20世纪70年代，而到了20世纪80年代的时 候，它正好属于一个发展中的过程，到了20世纪90年代时，它已经发展到了颠疯时刻。为一种实用性较强而又很有效率的优化技术，遗传算法的发展还是非常迅速，在国内外已经造成了非常大的影响力。 1.3遗传算法的基本思想。遗传算法是从一个种群（population）开始的，而这个种群代表问题可能潜在解集的，一个种群是由经过基因（gene）编码（coding）的一定数目的个体（individual）所组成。染色体是遗传物质的主要载体，它是由多个基因的集合，其内部表现是某种基因组合决定的。自从初始种群产生以后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小来挑选（selection）个体，遗传算法是采纳了选择、交叉、变异、迁移、局域 与邻域等自然进化模型，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），从而产生出代表新的解集的种群。 遗传算法和传统搜索算法有很大的不同，它是通过一组随机产生的初始解开始搜索过程。染色体是类似于二进制串的一串符号，对于染色体的测量，我们通常是用适应度来它的好坏

matlab基本遗传算法应用实例

基本遗传算法应用实例。用基本遗传算法求下面函数的最大值 10090060)(23++-=x x x x f 300≤≤x 个体数目取50，最大进化代数取100，离散精度取0.001，杂交概率取0.9，变异概率取0.004 1、在editor 中建立基本遗传算法函数：GA 程序如下： function[xv,fv]=GA(fitness,a,b,NP,NG,pc,pm,eps) %待优化的目标函数:fitness %自变量下界:a %自变量上界:b %种群个体数:NP %最大进化代数:NG %杂交概率:pc %自变量概率:pm %自变量离散精度:eps %目标函数取最小值时的自变量值：xm %目标函数的最小值:fv L=ceil(log2((b-a)/eps+1)); %根据离散精度，确定二进制编码需要的码长 x=zeros(NP,L); for i=1:NP x(i,:)=Initial(L);%种群初始化 fx(i)=fitness(Dec(a,b,x(i,:),L)); %个体适应值 end for k=1:NG sumfx=sum(fx); %所有个体适应值之和 px=fx/sumfx; %所有个体适应值的平均值 ppx=0; ppx(1)=px(1); for i=2:NP %用于轮盘赌策略的累加 ppx(i)=ppx(i-1)+px(i); end for i=1:NP sita=rand(); for n=1:NP if sita<=ppx(n) SelFather=n; %根据轮盘赌策略确定的父亲 break; end end Selmother=floor(rand()*(NP-1))+1; %随机选择母亲 posCut=floor(rand()*(L-2))+1; %随机选择交叉点 r1=rand(); if r1<=pc %交叉

遗传算法的特点及其应用

遗传算法的特点及其应用 上海复旦大学附属中学张宁 目录 【关键词】 【摘要】 【正文】 §1遗传算法的基本概念 §2简单的遗传算法 1．选择 2．交换 3．变异 §3简单的遗传算法运算示例 1．计算机公司的经营策略优化问题 2．函数优化问题 §4遗传算法应用举例 1．子集和问题 2．TSP（旅行商）问题 §5结束语 【附录】 1．子集和问题源程序 2．TSP（旅行商）问题源程序 【参考文献】

【关键词】 遗传算法遗传变异染色体基因群体 【摘要】 遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。 文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。 文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。 【正文】 遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。 §1遗传算法的基本概念 遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

遗传算法

遗传算法的基本理论 一、起源： 早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的John Holland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“Adaption in Natural and Artificial System”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。 二、发展： 年份贡献者内容 1962Holland程序漫游元胞计算机自适应系统框架 1968Holland模式定理的建立 1971Hollstein具有交配和选择规则的二维函数优化 1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究 1973Holland遗传算法中试验的最优配置和双臂强盗问题 1973Martin类似遗传真法的概率算法理论 1975De Jong用于5个测试函数的研究基本遗传算法基准参数 1975Holland 出版了开创性著作《Adaptation in Natural and Artificial System》 1981Bethke应用Walsh函数分析模式 1981Brindle研究遗传算法中的选择和支配问题 1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP) 1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法 1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、Lingle TSP问题个采用部分匹配交叉 1985Grefenstette、Fitzpattrick对含噪声的函数进行测试 1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计 1986Grefenstette元级遗传算法控制的遗传算法 1987Baker选择中随机误差的减少方法 1987Goldberg复制和交叉时最小欺骗问题(MDP) 1987Goldberg、Richardson借助分享函数的小生境和物种归纳法

遗传算法应用实例【精品毕业设计】(完整版)

遗传算法及其应用实例 遗传算法（Genetic Algorithm）是由美国Michigan大学的Holland 教授（1969）提出，后经由De Jong（1975），Goldberg（1989）等归纳总结所形成的一类模拟进化算法。 遗传算法搜索最优解的方法是模仿生物的进化过程，即通过选择 与染色体之间的交叉和变异来完成的。遗传算法主要使用选择算子、交叉算子与变异算子来模拟生物进化，从而产生一代又一代的种群。()Xt （1）选择算子：是模拟自然选择的操作，反映“优胜劣汰”原 理。它根据每一个个体的适应度，按照一定规则或方法，从代种群中选择出一些优良的个体（或作为母体，或让其遗传到下一代种群）。 t (1)Xt. （2）交叉算子：是模拟有性繁殖的基因重组操作，它将从种群 所选择的每一对母体，以一定的交叉概率交换它们之间的部分基因。 （3）变异算子：是模拟基因突变的遗传操作，它对种群中 的每一个个体，以一定的变异概率改变某一个或某一些基因座上的基因值为其他的等位基因。 交叉算子与变异算子的作用都在于重组染色体基因，以生成新的 个体。

遗传算法的运算过程如下： 步1（初始化） 确定种群规模，交叉概率，变异概率和终止进化准则；随 机生成个个体作为初始种群；置。 NcPmP (0)X0t. 步2（个体评价） 计算评估中各个体的适应度。 步3（种群进化） 3.1. 选择（母体）从中运用选择算子选择出对母体 （）。 /2M MN. 3.2. 交叉对所选择的对母体，以概率执行交叉，形成 个中间个体。 M 3.3. 变异对个中间个体分别独立以概率执行变异，形成 个候选个体。 M 3.4. 选择（子代）从上述所形成的个候选个体中依据适应度 选择出个个体组成新一代种群。N 步4（终止检验） 如已满足终止准则，则输出中具有最大适应度的个体作为 最优解，终止计算，否则置并转步2。1tt.. 以上运算过程只是遗传算法的多种实现方式中的一种，根据实际问题的不同，遗传算法的实现也是多种多样的。

遗传算法综述

遗传算法综述 摘要 遗传算法（Genetic Algorithm，GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。本文从遗传算法的起源谈起，论述了遗传算法的基本思想和基本原理，并对其性能和收敛性进行了分析，最后还介绍了几种改进的遗传算法及其在求解旅行商问题（TSP）方面的应用。 Genetic algorithm ( Genetic, Algorithm, GA ) is a kind of biological natural selection and genetic mechanism of the random search algorithm, its main characteristic is the group searching strategy and individual in the colony between the exchange of information, search does not rely on gradient information. It is especially suitable for the processing of traditional search method to solve the complex and nonlinear problems, can be widely used in combinatorial optimization, machine learning, adaptive control, planning design and artificial life etc.. This article from the origin of the genetic algorithm, the genetic algorithm basic thought and basic principle, and its performance and convergence are analyzed, finally introduces several improved genetic algorithm for solving the traveling salesman problem ( TSP ) with respect to the application. 关键词：遗传算法；搜索算法；TSP；遗传算法收敛性 Key words: genetic algorithm; search algorithm; TSP; genetic algorithm convergence 1 引言 在自然界中，生物要生存下去，就必须进行生存斗争。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。遗传算法是根据这种生物的自然进化思想而启发得出的一种全局优化算法。 遗传算法是由美国的J. Holland教授于1975年在他的专著《自然和人工系统的适应性》中首先提出的，他将遗传算法应用于函数优化中，设计了遗传算法执行策略和性能评价指标。1989年，Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》，系统总结了遗传算法的主

遗传算法基本理论及实例

目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ........ 错误！未定义书签。附录一：运行程序.. (19)

遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的

遗传算法参考文献

1.遗传算法在激光整形中的应用 【作者】王卫兵；赵帅；郭劲；王挺峰；2012-10第42卷 1115—1119 激光与红外 同爬山算法相比,遗传算法具有全局优化能力,为了研究遗传算法的波前整形能力,利用32单元变形镜和12项Zernike多项式构成的畸变波前建立了激光波前整形系统仿真模型。基于Zernike多项式的单位正交性特点,得到了两个常数矩阵,简化了算法的运算过程,加快了算法运行时间。然后分别对遗传1000,10000和100000代后的斯特列尔比和整形效果进行了模拟仿真,仿真结果为:进行100000代遗传后,遗传算法可分别将初始畸变波前的斯特列尔比从0.3771整形到0.9049,波前峰谷值从 0.8078λ整形到0.3758λ,均方根从0.1572λ整形到0.0503λ,并且随着遗传代数的增加,斯特列尔比逐渐和整形效果均逐渐趋于最优,进一步表明遗传算法是一种优化逼近控制算法,可以通过对变形镜驱动电压的优化控制来实现波前整形,为遗传算法应用于波前整形技术中提供了理论依据。 2.基于改进遗传算法的物流配送路径优化 【作者】罗勇；陈治亚； 118-122 系统工程 2012-8第30卷 物流配送路径规划对于提高物流配送效率、节约配送成本具有重要意义。以物流配送路径总长度为优化目标,将其转换为经典TSP优化问题进行求解并建立了数学模型。基于该数学模型,提出改进的遗传算法,针对遗传算法的选择、交叉和变异分别提出了基于序的选择算子、基于最小代价树的交叉算子和基于随机点长度控制的变异算子。改进的遗传算法与简单遗传算法的对比仿真实验表明,所改进的遗传算法有较好的全局寻优能力,且其收敛速度快,是解决物流配送路径优化问题的有效方法。 3.改进的混合遗传算法在配电网规划中的应用 【作者】黄慧；齐岩；吴利乐；168-170 水电能源科学 2012-9第30卷 【摘要】利用遗传算法解决NP问题(非确定性多项式问题)的良好能力、模拟退火算法在当前点邻域内搜索最优解的能力和禁忌搜索算法较快的搜索速度,提出了改进的混合遗传算法,即将模拟退火选择算子和禁忌搜索变异算子应用到遗传操作中,提高了种群选择的有效性和遗传算法局部搜索能力,避免了单一遗传算法中收敛速度慢和早熟现象的产生。并将改进的混合遗传算法应用到河南省北部A 地区电网规划中,对水平年电力网架进行了优化,结果满足电力系统经济性和可靠性的要求,运行实践证明该算法效果较好。更多还原 （注：本资料素材和资料部分来自网络，仅供参考。请预览后才下载，期待您的好评与关注！）