全局优化报告
——遗传算法和蚁群算法的比较
******
学号：**********
班级：硕2041
1遗传算法
1.1遗传算法的发展历史
遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。
1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。
遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基
础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。
遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下：
（1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。
（2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别适合解决这一类问题，能够在可以接受的计算时间内求得满意的近似最优解，如著名的旅行商问题、装箱问题等都可以用遗传算法得到满意的解。
（3）工程应用方面。工程方法的应用是遗传算法的一个主要应用领域，如管道优化设计、通风网络的优化设计、飞机外型设计、超大规模集成电路的布线等。
（4）计算机科学。遗传算法广泛应用于计算机科学的研究，如用于图像处理和自动识别、文档自动处理、VLSI设计等。
（5）生物学。遗传算法起源于对生物和自然现象的模拟，现在又反过来用于生物领域的研究，如利用遗传算法进行生物信息学的研究等。（6）社会科学。遗传算法在社会科学的许多领域也有广泛应用，如人类行为规范进化过程的模拟、人口迁移模型的建立等
（7）经济领域。经济学领域也用到遗传算法。例如，国民经济预测模型、市场预测模型和期货贸易模型等。遗传算法与神经网络相结合正成功地被应用于从时间序列分析来进行财政预算等。
1.2遗传算法的基本原理
遗传算法是一种基于自然选择和群体遗传机制的搜索算法，它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象。在利用遗传算法求解问题时，问题的每个可能的解都被编码成一个“染色体”，即个体，若干个个体构成了群体（所有可能解）。在遗传算法开始时，总是随机地产生一些个体（即初始解）。根据预定的目标函数对每个个体进行评估，给出了一个适应度值。基于此适应度值，选择个体用来复制下一代。选择操作体现了“适者生存”的原理，“好”的个体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经
过交叉和变异算子进行再结合生成新的一代。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。因此，遗传算法可以看成是一个由可行解组成的群体逐步进化的过程。图给出了简单遗传算法的基本过程。下面介绍遗传算法的编码及基本遗传操作过程。
1.2.1 编码
利用遗传算法求解问题时，首先要确定问题的目标函数和变量，然后对变量进行编码。这样做主要是因为在遗传算法中，问题的解是用数字串来表示的，而且遗传算子也是直接对串进行操作的。编码方式可以分为二进制编码和实数编码。若用二进制数表示个体，则将二进制数转化为十进制数的解码公式可以为
∑=---+=l j j ij l i
i i il i i b R T R b b b F 1121212),...,,(
其中，),...,,(il i i b b b 21为某个个体的第i 段，每段段长都为l ，每个ik b 都是0或者1，i T 和i R 是第i 段分量i X 的定义域的两个端点。
1.2.2 遗传操作
遗传操作是模拟生物基因的操作，它的任务就是根据个体的适应度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度看，遗传操作可以使问题的解逐代的优化，逼近最优解。遗传操作包括以下三个基本遗传算子：选择、交叉、变异。选择和交叉基本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到最接近最优解的能力。
1. 选择
