遗传算法问题

㈠ 请问遗传算法的主要缺陷是什么

遗传算法在广泛问题解决上显示了强大的适应性，但这种通用性也是其主要缺陷。其核心问题在于，为了能够应对各种问题，算法不具备针对特定问题的结构化利用能力。

以连续优化问题为例，梯度下降法是更高效的选择，因为它直接利用了问题的连续性和梯度信息。同理，求解最短路径问题时，Dijkstra算法是更优解，因为它能准确地利用问题的结构。

为弥补这种通用性缺陷，遗传算法提供了大量的参数，如保留精英策略、交叉和变异操作的设置等。然而，这反而引发了一个问题：在解决特定问题时，是否应该思考该问题的结构并利用结构，还是通过调整通用搜索算法来提高效率？

值得注意的是，并非所有通用算法都是低效的。例如，图灵完备语言的编译器在某种意义上是高度通用的，但它们并未牺牲对问题结构的利用。编译器通过分析程序结构，优化重复计算，这正是遗传算法所缺乏的。

归根结底，遗传算法试图模拟自然演化的过程，这一想法看似美妙，但其背后的复杂性甚至可能不及一些简单的算法，如Tarjan的强连通分量算法。对于通用问题求解器来说，至少它们尝试思考问题的子结构。因此，尽管遗传算法在通用性上表现出色，但在特定问题解决上的效率和效果仍存在改进空间。

㈡ 遗传算法解决tsp问题怎么编码

研究对象的初始基因是固定的，因此选择了一种特定的编码方式。初始种群可以通过随机生成或者使用某种算法生成，关键在于保持种群的多样性。在种群初始化阶段，需考虑以下几点：

1. 根据问题固有的知识，确定最优解所占的空间范围，然后在此范围内设定初始群体。这样可以更有效地找到潜在的最优解。

2. 随机生成一定数量的个体，从中挑选出最佳个体加入群体。这一过程需要不断迭代，直到初始种群中的个体数量达到预定规模。

亲和度的设定为1/f，其中f代表总路径长度。在确定亲和度之后，接下来可以根据城市序号进行选择、交叉和变异操作。

在选择阶段，可以根据亲和度从种群中选择个体，以确保选择出的个体具有较高的适应性。交叉操作则通过交换两个个体的某些基因片段，生成新的个体，从而增加种群的多样性。

变异操作则通过对个体的某些基因进行随机改变，以引入新的变异和多样性。通过选择、交叉和变异操作，可以不断优化种群，逐步接近最优解。

在整个过程中，保持种群的多样性是非常重要的，因为这有助于避免陷入局部最优解，提高算法的全局搜索能力。

通过这种编码方式，遗传算法能够更有效地解决TSP问题，找到近似最优的路径。

㈢ 遗传算法的收敛性问题

是算子有问题，交叉的方法都是比较简单的，但对于某些情况可能并不好用，也就是说算法本身无法体现出优胜劣汰的规则，可能因此导致无法收敛。

收敛数列令为一个数列，且A为一个固定的实数，如果对于任意给出的b>0,存在一个正整数N，使得对于任意n>N,有|an-A|<b,则数列存在极限A，数列被称为收敛。非收敛的数列被称作“发散”（divergence)数列。

可见收敛不是指数值越来越小，而是指与极限值的距离（即差的绝对值）越来越小，只要你的目标函数是压缩映射，那么使用遗传算法就一定可以计算出全局收敛的近似值。

(3)遗传算法问题扩展阅读：

由于遗传算法不能直接处理问题空间的参数,因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。这一转换操作就叫做编码，也可以称作（问题的）表示（representation）。

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。