?f(x)?CminF(x)??0?f(x)?Cminf(x)?Cmin (2.4)
式中，Cmin既可以是特定的输入值，也可以选取到目前为止所得到的目标函数
f(x)的最小值。
变换方法二：
(1)对于最小化问题，建立适应度函数f(x)和目标函数f(x)的映射关系：
F(x)?1c?0,c?f(x)?0 (2.5)
1?c?f(x)(2)对于最大化问题，一般采用下述方法：
F(x)?1c?0,c?f(x)?0 (2.6)
1?c?f(x)式中，c为目标函数界限的保守估计值。
2.4 约束条件的处理
在遗传算法中必须对约束条件进行处理，但目前尚无处理各种约束条件的一般方法，根据具体问题可选择下列三种方法，其罚函数法、搜索空间限定法和可行解变换法。 2.4.1 罚函数法
罚函数的基本思想是对在解空间中无对应可行解的个体计划其适应度时，处以一个罚函数，从而降低该个体的适应度，使该个体被选遗传到下一代群体中的概率减小。可以用下式对个体的适应度进行调整：
?F(x) F'(x)???F(x)?P(x)x?U （2.7） x?U其中，F(x)为原适应度函数，F'(x)为调整后的新的适应度函数，P(x)为罚函数，U为约束条件组成的集合。
如何确定合理的罚函数是这种处理方法难点之所在，在考虑罚函数时，既要度量解对约束条件不满足的程度，由要考虑计算效率。 2.4.2 搜索空间限定法
搜索空间限定法的基本思想是对遗传算法的搜索空间的大小加以限制，使得
搜索空间中表示一个个体的点与解空间中的表示一个可行解的点有一一对应的关系。对一些比较简单的约束条件通过适当编码使搜索空间与解空间一一对应，限定搜索空间能够提高遗传算法的效率。在使用搜索空间限定法时必须保证交叉、变异之后的解个体在解空间中有对应解。 2.4.3 可行解变换法
可行解变换法的基本思想：在由个体基因型到个体表现型的变换中，增加使其满足约束条件的处理过程，其寻找个体基因型与个体表现型的多对一变换关系，扩大了搜索空间，使进化过程中所产生的个体总能通过这个变换而转化成解空间中满足约束条件的一个可行解。可行解变换法对个体的编码方式、交叉运算、变异运算等无特殊要求，但运行效果下降。
2.5 遗传算子
遗传算法中包含了3个模拟生物基因遗传操作的遗传算子：选择（复制）、交叉（重组）和变异（突变）。遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。 2.5.1 选择操作
遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。遗传算法使用选择（复制）算子来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。选择操作建立在对个体适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。常用的选择方法有转轮法、排序选择法、两两竞争法。
1) 轮盘赌法。
简单的选择方法为轮盘赌法：通常以第i个个体入选种群的概率以及群体规模的上限来确定其生存与淘汰，这种方法称为轮盘赌法。轮盘赌法是一种正比选择策略，能够根据与适应函数值成正比的概率选出新的种群。轮盘赌法由以下五步构成：
1. 计算各染色体vk适应值F(vk)； 2. 计算种群中所有染色体的适应值的和；
Fall??F(vk) （2.6）
k?1n3. 计算各染色体vk的选择概率pk；
eval(vk) pk?,k?1,2,?,n (2.7)
Fall4. 计算各染色体vk的累计概率qk； qk??pj,k?1,2?,j?1k , n (2.8)
5. 在[0,1]区间内产生一个均匀分布的伪随机数r，若r?q1，则选择第一个染色体v1；否则，选择第k个染色体，使得qk?1?r?qk成立。
2) 排序选择法。
排序选择法的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。排序选择方法的具体操作过程是：
1. 对群体中的所有个体按其适应度大小进行降序排序。
2. 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。
3. 以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用轮盘赌法来产生下一代群体。
3) 两两竞争法。
锦标赛选择法的基本做法是：在选择时先随机的在种群中选择k个个体进行锦标赛式的比较，从中选出适应值最好的个体进入下一代，复用这种方法进行直到下一代个体数为种群规模时为止。这种方法也使得适应值好的个体在下一代具有较大的“生存”机会，同时它只能使用适应值的相对值作为选择的标准，而与适应值的数值大小不成直接比例，所以，它能较好的避免超级个体的影响，一定程度的避免过早收敛现象和停滞现象。 2.5.2 交叉操作
在遗传算法中，交叉操作是起核心作用的遗传操作，它是生成新个体的主要 方式。交叉操作的基本思想是通过对两个个体之间进行某部分基因的互换来实现 产生新个体的目的。常用交叉算子有：单点交叉算子、两点交叉算子和多点交叉算子、均匀交叉算子和算术交叉算子等等。
1) 单点交叉算子
交叉过程分两个步骤：首先对配对库中的个体进行随机配对；其次，在配对个体中随机设定交叉位置，配对个体彼此交换部分信息。
图2-1 单点交叉示意
2) 两点交叉算子
具体操作是随机设定两个交叉点，互换两个父代在这两点间的基因串，分别生成两个新个体。
3) 多点交叉算子
多点交叉的思想源于控制个体特定行为的染色体表示信息的部分无须包含于邻近的子串中，多点交叉的破坏性可以促进解空间的搜索，而不是促进过早的收敛。
4) 均匀交叉算子
均匀交叉式指通过设定屏蔽字来决定新个体的基因继承两个个体中那个个体的对应基因，当屏蔽字中的位为0时，新个体A?继承旧个体A中对应的基因，当屏蔽字位为1时，新个体A?继承旧个体B中对应的基因，由此可生成一个完整的新个体A?，同理可生成新个体B?。
图2-2 均与交叉示意图
2.5.3 变异操作
变异操作是指将个体染色体编码串中的某些基因座的基因值用该基因座的其他等位基因来替代，从而形成一个新的个体。变异运算是产生新个体的辅助方法，它和选择、交叉算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力，提高遗传算法的搜索效率；同时使遗传算法保持种群的多样性，以防止出现早熟收敛。在变异操作中，为了保证个体变异后不会与其父
体产生太大的差异，保证种群发展的稳定性，变异率不能取太大，如果变异率大于0.5，遗传算法就变为随机搜索，遗传算法的一些重要的数学特性和搜索能力也就不存在了。变异算子的设计包括确定变异点的位置和进行基因值替换。变异操作的方法有基本位变异、均匀变异、边界变异、非均匀变异等。
1) 基本位变异
基本位变异操作是指对个体编码串中以变异概率pm随机指定的某一位或某 几位基因作变异运算，所以其发挥的作用比较慢，作用的效果也不明显。基本位变异算子的具体执行过程是：
1. 对个体的每一个基因座，依变异概率pm指定其为变异点。
2. 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新个体。
2) 均匀变异
均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。均匀变异的具体操作过程是：
1. 依次指定个体编码串中的每个基因座为变异点。
2. 对每一个变异点，以变异概率pm从对应基因的取值范围内取一随机数来替代原有基因值。
假设有一个个体为vk?[v1v2?vk?vm]，若vk为变异点，其取值范围为
[vk,min,vk,max]，在该点对个体vk进行均匀变异操作后，可得到一个新的个体：
?v i n (2.9) ) , mvk?[v1v2?v'k?vm]，其中变异点的新基因值是
' vk?vk,mi?nr?(vk,makx式中，r为[0,1]范围内符合均匀概率分布的一个随机数。均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地移动，从而可以增加群体的多样性。 2.5.4 倒位操作
所谓倒位操作是指颠倒个体编码串中随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体。倒位操作的具体过程是：
1. 在个体编码串中随机指定二个基因座作为倒位点； 2. 以倒位概率颠倒这二个倒位点之间的基因排列顺序。
2.6 搜索终止条件
遗传算法的终止条件有以下两个，满足任何一个条件搜索就结束。