蚁群算法PLC电力线载波通信网络的组网技术研究(4)
2.1.1 旅行商问题
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NP问题无法通过公式按部就班地直接求解，但是可以间接地“猜测”答案，通常这些问题有能够判断答案正确与否却无法直接求解的算法。其中NP完全问题( non-deterministic polynomial complete)的答案非常容易验证，但没有任何一个够快的方法可以在合理的时间内（意即多项式时间）找到答案。
旅行商问题( Traveling Salesman Problem，简称TSP) 是一个典型的组合优化问题，易于描述却难于求解，是一个NP complete难题。旅行商问题可描述如下：给定n 个城市和两两城市之间的距离，一个旅行商从某个城市出发去访问每个城市一次，且仅一次，最后回到出发城市，要求确定一条最短线路。
2.1.2 方案选择
对于大规模的TSP问题，完美地求解方法仍未找到。但是通过遗传算法、蚁群算法、模拟退火算法等可以在合理的时间内求得一定精度的近似完美解。下面对这几种在TSP问题的解决上具有较好表现的算法进行讨论。
a) 遗传算法
遗传算法( Genetic Algorithm，GA)[16]于生物自然选择与遗传机理的随机搜索算法，它的基本思想来源于达尔文的进化论和孟德尔的遗传学说。该算法自从1975年被Holland J 等人提出后，获得了广泛的应用。该算法将问题的求解过程表示为“染色体”的优胜劣汰的过程，通过种群的一代一代的进化，其中包括复制、交叉、变异等操作，最终求得最适应环境的一个“染色体”，也就是问题的最优解或者近似最优解。
遗传算法的优点是使用简单、通用性强、易于实现，并具有并行性和全局搜索能力。缺点是易出现早熟收敛和收敛性差的现象。
b) Hopfield神经网络
Hopfield神经网络[16]是1982年由美国物理学家Hopfield教授提出的一种单层反馈神经网络，并在1985年将其应用于TSP问题的求解。该方法将问题的合法解映射为一个换位矩阵，并构造合适的能量函数。随着网络状态的变化，其能量不断减少，最后达到平衡时，将得到一个局部最优解即满足换位矩阵要求的能量函数的最小值与问题的最优解相对应。
Hopfield神经网络的优点是简单、规范、快速，但是其优化性较差，实验表明，其只有局部搜索能力，并且在求解TSP问题时存在两难问题，即提高解有效性概率会导致解的路径长度优化能力降低，而提高网络路径长度优化能力则导致解有效性概率降低，所以需要恰当的网络运行参数的设置。
c) 模拟退火算法
模拟退火算法( Simulated Annealing Algorithm，AA)是受物理学启发而来的一种随机寻优算法，将固体加热至充分高温，使固体融为液体，让其缓缓冷却[16] 。加温时，固体内部粒子随温度的升高变为无序状，内能增大，而缓缓冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小，这个过程称为退火。SA算法由某一较高初温开始，即从某一初始解开始，在解空间中根据抽样策略随机产生另一个解，随着温度参数的不断下降重复抽样过程，最终得到全局最优解。
模拟退火算法的优点是具有较好的鲁棒性、全局收敛性，易于并行计算， 并能以较大概率求得全局最优解，但是SA算法的运算效率不高，优化时间较长。
d) 人工免疫算法
人工免疫算法(Artificial Immune Algorithm，AIA)[16]，是一类基于生物免疫系统的功能、原理、基本特征以及相关理论免疫学说而建立的用于解决各种复杂问题的计算系统。在使用人工免疫算法求解优化问题时，满足约束条件的最优解作为抗原，候选解作为抗体。抗体和抗原之间的亲和力反映了候选解和最优解的接近程度，抗体和抗原的排斥力反映了不同候选解之间的差异，而保持抗体的多样性可以防止算法陷入局部最优解。
下一篇：双曲型方程的特征理论+文献综述