智能优化算法的主要步骤和基本流程

尽管遗传算法这种自适应寻优技术已经在求解大量复杂的线性、非线性问题中表现出优良的计算性能，但其工作机理十分简单。遗传算法的主要步骤为：

①编码；②产生初始群体；③设计适应度函数；④设计遗传算子；⑤设定控制参数。这5步构成遗传算法的核心内容，决定了计算结果的优劣。下面，对以上的各步骤做进一步的描述。

1.编码

编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应，这很大程度上依赖于具体问题的性质，并将影响遗传操作的设计。由于GA的优化过程不是直接作用在问题参数本身，而是在一定的编码机制对应的码空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。

函数优化中，不同的码长和码制对问题求解的精度与效果有很大影响。二进制编码将问题的解用一个二进制串来表示，十进制编码将问题的解用一个十进制串来表示，显然码长将影响算法的精度，较长的码算法将付出较大的存储量。实数编码将问题的解用一个实数来表示，解决了编码对算法精度和存储量的影响，也有利于优化中引入问题的相关信息，实数编码在高维复杂优化问题中得到广泛应用，但也有其局限性。

组合优化中，由于问题本身的性质，编码方式需要具体问题具体设计。

2.产生初始群体

遗传算法初始群体中的个体是随机产生的，群体规模的确定受选择操作的影响很大。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小，所以从群体多样性出发，群体规模应较大。但群体规模太大会增加计算量，从而影响算法效能；同时群体中个体太多时，少量适应度很高的个体会被选择而生存下来，但大多数个体被淘汰，这会影响配对库的形成，从而影响交叉操作。另一方面，群体规模太小，会使遗传算法的搜索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛现象。在实际应用群体个体数的取值范围一般为数十至数百。

3.设计适应度函数

适应度函数用于对个体进行评价，一般应满足以下特点：单值、连续、非负、最大化、合理、一致性、计算量小和通用性强。在简单问题的优化时，通常可以直接把目标函数作为适应度函数，在复杂问题的优化时，往往需要构造合适的评价函数作为适应度函数，使其适应GA进行优化。

例如，当目标是求取费用函数（代价函数）g（x）的最小值，而不是求效能函数或利润函数u（x）的最大值时，就需要把最小化问题转化为最大化问题，同时为了保证在各种情况下非负，适应度函数一般取为

Cmax可以是一个合适的输入值，也可以采用迄今为止进化过程中g（x）的最大值或当前群体中g（x）的最大值。Cmax也可以是前K代中的最大值，Cmax最好与群体无关。

当求解问题的目标函数为利润函数时，为了保证其非负性，可以用下变换式

式中系数Cmin可以是合适的输入值，或是当前一代或前K代中的u（x）的最小值，也可以是群体方差的函数。

4.设计遗传算子

优胜劣汰是设计GA的基本思想，它应在选择、交叉、变异等遗传算子中得以体现，而且要考虑对算法效率与性能的影响。

5.设定控制参数(www.xing528.com)

遗传算法需要设定的控制参数主要有个体编码串长度l、群体规模M、变叉概率pc、变异概率pm、终止代数T。这些参数对遗传算法的性能有较大的影响，需恰当地选取。

假设给定了一个问题，并且用定义好的长度为m的染色体串代表候选解，遗传算法的流程可以简单地描述为：

Step1：随机生成72个长度为m的染色体串，形成初始的染色体群。

Step2：将染色体群中每个染色体串代入适应度函数，计算适应度。

Step3：判断是否满足终止条件，若是，则适应度值最大的染色体对应的候选解就是需要的满意解；若否，则转Step4。

Step4：重复下列步骤直至产生了n个后代。

①在当前的染色体群中随机选取两个染色体作为父本，选取染色体的概率函数应该是适应度的增函数。在选取父本的过程中，一个染色体可以被多次选中。

②对于选中的父本，按照交叉概率pc决定是否交叉产生两个新的后代，发生交叉的位置是随机的，每个位置的概率是相同的。如果不发生交叉，则两个后代是对两个选中的父本进行严格地复制的结果，注意这里定义的交叉是两个父本在一个随机的位置上进行交叉互换.在遗传算法中有时会用到多点的交叉，即在多个随机的点上发生交叉。

③对于产生的两个后代，分别在每个位置上按照变异概率户pm发生变异。将两个后代放入新的染色体群。

如果n是奇数，可以随机地放弃一个新的后代。

Step5：生成n个新的染色体后，用新的染色体群代替原来的染色体群。

Step6：转向Step2。

每次迭代这一过程称为一个世代.一个遗传算法的应用通常需要迭代50到500个世代，可以指定迭代的世代数作为算法的终止条件。

上述简单的模型只是描述了大多数遗传算法所共有的基本步骤，遗传算法也有一些很复杂的版本，这里就不介绍了。

基本遗传算法的流程图描述，如图2.1所示。

图2.1　基本遗传算法的流程框图