Page 156 - 大数据技术及安全研究

大数据技术及安全研究
Big Data Technology and Security Research

法执行过程中进行调整，因而算法缺乏微调（Fine-tuning）的功能。在求解高维
优化问题或要求精度很高时，二进制串很长，因而算法的搜索效率很低。基于上
述原因，有人提出了 Gray 编码、动态编码等策略。Gray 编码是将二进制编码通
过 Gray 变换后得到的编码，目的是减少翻转次数，克服二进制编码的 Hamming

悬崖（Hamming Cliffs）的缺点。动态编码是当算法收敛到某局部最优时，增加
搜索的精度。办法是：在保持二进制串长不变的前提下减小搜索区域。为了克服
二进制编码的缺点，对于问题的变量是实向量的情况，也可直接采用实进制进行
编码。这样，可直接在解的表现型上进行遗传操作，从而便于引入与问题领域相

关的启发式信息，以增加演化算法的搜索能力。从演化计算的各分支看，在求解
数值优化问题时，演化策略及演化规划都采用实数编码，而且在早期不使用杂交
算子（演化策略中现在使用的重组算子非常类似杂交算子）。遗传算法则较多地
采用二进制编码。近几年，遗传算法在求解高维或复杂优化问题时也大多使用实

数编码。由于实数编码表示比较自然，而且较易引入相关的领域知识，因此，我
们认为其使用将越来越广泛。对很多组合优化问题，目标函数的值不仅与表示解
的字符串中各字符的值有关，而且与其所在字符串的位置有关，这样的问题称为
有序问题。若目标函数的值只与表示解的字符串中各字符的位置有关，与其具体

的字符值无关，则称为纯有序问题。对这类问题，较自然的编码表示就是有序串
编码。用演化算法求解有序问题时，传统的遗传操作可能产生非法的后代。因此，
对这类问题要针对具体问题专门设计有效且能保证后代合法的遗传算子。这类编
码方案较多地用在组合优化问题中。对很多问题，更自然的表示是树或图的形式。

这时，采用其他形式的编码可能很困难。这种将问题的解表示成树或图的形式的
编码称为结构式编码。对这种非线性编码方式，我们应非常谨慎地设计遗传算子，
以便不产生或少产生非法的后代。对结构式编码要讨论通用的遗传算子很困难，
一般是就具体问题具体分析。因为遗传算子直接在解的表现型上进行操作，所以

比较容易加入与领域有关的知识和一些启发式信息。
（三）适应函数的确定
在自然界中，个体的适应值就是其繁殖能力，这将直接关系到其后代的数量。
在演化计算中，适应函数是区分群体中个体好坏的标准，是算法演化过程的驱动

力，是进行自然选择的唯一依据。改变种群内部结构的操作都通过适应值进行控
制。在演化计算中，度量适应性的方法有很多种，既可以用目标函数的形式给出，

·144·