第三章 遗传算法 1 第三章 遗传算法 遗传算法（Genetic Algorithm）是一种通过自然进化过程搜索最优解的方法。过去 30 年中，在解决复杂的全局优化问题方面，遗传算法取得了成功的应用，并受到了人们广泛的关注。在优化问题中，如果目标函数是多峰的，或者搜索空间不规则，就要求所使用的算法必须具有高度的鲁棒性，以避免在局部优化解附近徘徊。遗传算法的优点恰好是擅长全局搜索。另外，遗传算法本身并不要对优化问题的性质作一些深入的数学分析，从而对那些不太熟悉数学理论和算法的使用者来说，无疑是方便的。 大家知道，生物遗传物质的主要载体是染色体，在遗传算法中，染色体是一串数据（或数组），用来作为优化问题的解的代码，其本身不一定是解。遗传算法一般经过这样几个过程：首先，随机产生一定数目的初始染色体，这些随机产生的染色体组成一个种群。种群中染色体的数目称为种群的大小或种群的规模。然后，用评价函数来评价每个染色体的优劣，即染色体对环境的适应程度（称为适应度），用来作为以后遗传操作的依据。接着，进行选择过程，选择过程的目的是为了从当前种群中选出优良的染色体。判断染色体的优良与否的准则就是各自的适应度，即染色体的适应度越高，其被选择的机会就越多。通过选择过程，产生一个新的种群。对这种新的种群进行交叉操作，交叉操作是遗传算法中主要的遗传操作之一。接着进行变异操作，变异操作的目的是挖掘种群中的个体的多样性，克服有可能陷入局部解的弊病。这样，经过上述运算产生的染色体称为后代。然后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。 遗传算法已被广泛应用业于最优控制、运输问题、调度、生产计划、资源分配、统计及模式识别等，下面我们介绍一下遗传算法的一些基本知识。 第一节 优化问题的遗传算法 回顾一下单目标规划、多目标规划及目标规划模型的基本形式。在数学规划中，目标函数不一定是单峰的，可行域也不一定是凸集。最优化问题的解有两种表示方式：二进制向量或浮点向量。使用二进制向量作为一第三章 遗传算法 2 个染色体来表示决策变量的真实值，向量的长度依赖于要求的精度，但使用二进制代码的必要性已经受到了批评。求解复杂优化问题时，二进制向量表示结构有时不太方便。 另一种表示方法是浮点向量，每一个染色体由一个浮点向量表示，其长度与解向量相同。这里用向量),...,(21...
