基于遗传算法原理优化数据研究

摘 要：遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。遗传算法中的TSP问题即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。

关键词：遗传算法；TSP；人工智能

一、背景和国内外发展现状

遗传算法被提出之后立即受到了各国学者的广泛关注，有关遗传算法的研究成果不断涌现。从20世纪80年代中期起，遗传算法和进化计算到达一个研究高潮，以遗传算法和进化计算为主题的国际学术会议在世界各地定期召开。此外，进化规划年会（annual conference on Evolutionary programming， ACEP）每隔两年召开一届，它具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。其他类型的各种会议，如以遗传编程、进化策略或进化编程为主题的研讨会也很频繁。

二、算法原理

遗传算法把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

典型的遗传算法CGA（Canonical Genetic Algorithm）通常用于解决下面这一类的静态最优化问题：考虑对于一群长度为L的二进制编码bi，i=1，2，3，4，n；有bi{0，1}L（3-84）给定目标函数f，有f（bi），并且f（bi）f（bi+1）求满足下式max{f（bi）|bi{0，1}L}的bi。很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。

长度为L的n个二进制串bi（i=1，2，…，n）组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：

选择（Selection）这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生（Reproduction）。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生（differential reproduction）。

交叉（Crossover）这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

变异（Mutation）这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0，同理反之。

三、算法实现及分析

使用遺传算法第一件事情就是确定染色编码方式，它根据不同的问题模型使用不同编码方式，有二进制编码也有整数编码和浮点数编码，面对TSP问题，我肯定选用整数编码，因为很简单，对于每个城市用一个整数来编号，例如有48个城市，就用0到47来标识每一个城市，然后一个路径就是一条染色体编码，染色体长度为48，如：0，1，2，3，4…47就是一个染色体，它表达的意思就是旅行者从0号城市出发，依次访问1，2，…47号城市再回到0号城市；遗传算法的第二个要点就是评价函数，TSP的评价函数很简单，就是染色体编码表达的路径总长度；最后很简单，其实在这个模型中就是将0到47这48个数进行全排列，从中找出最短的一条路径（想想48个数全排列，然后比较）清楚了解了这些，就可以按照上面的遗传算法框架来进行编程了。

我们使用TSP问题依然来自于tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其距离计算方法如下所示：

xd=x[i]-x[j]；

yd=y[i]-y[j]；

rij=sqrt[（xd*xd+yd*yd）/10.0]；

tij=nint（rij）；

if（tijelse dij=tij

遗传算法还具有以下几方面的特点：

（1）遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局擇优。

（2）遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。

（3）遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

（4）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。

（5）具有自组织，自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

（6）此外，算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。

基本的遗传算法是有很多不足的，如容易选入局部收敛，全局搜索能力不够强，但是有很多可以改进的地方，如交叉算子的设计、变异算子的设计、选择策略等等，有关遗传算法个人觉得作为一种智能启发式搜索算法它甚至比别的普通算法（如动态规划）理解起来还容易，而且它特别容易与别的算法相结合，设计新的混合算法。

参考文献：

[1]郑寒冰.基于混合遗传算法的导频优化[J].电信科学.2016（9）.

[2]赵礼峰.求解最短路径问题的混合遗传算法[J].计算机技术与发展.2016（9）.

作者简介：

唐友（1979.05—），男，教授，高级工程师，硕士。

（作者单位：黑龙江财经学院）