近邻法
近邻法(nearest neighbor) 推销员从某个城镇出发,永远选择前往最近且尚未去过的城镇,最后再返回原先的出发点。这方法简单,也许是多数人的直觉做法,但是近邻法的短视使其表现非常不好,通常后段的路程会非常痛苦。
插入法
插入法(insertion) 先产生连接部分点的子路线,再根据某种法则将其它的点逐一加入路线。比如最近插入法(nearest insertion),先针对外围的点建构子路线,然后从剩余的点里面评估何者加入后路线总长度增加的幅度最小,再将这个点加入路线。又比如最远插入法(farthest,insertion),是从剩余的点里面选择距离子路线最远的点,有点先苦后甜的滋味。
模拟退火算法
模拟退火算法(Recuit Algorithm) 来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,
粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解。
遗传算法
遗传算法是仿真生物遗传学和自然选择机理,通过人工方式所构造的一类搜索算法
遗传算法是解决NP问题的一种较理想的方法
,从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。生物种群的生存过程普遍遵循达尔文进化准则,群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上,其染色体包含若干基因,相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码,仍叫染色体,有时也叫个体;适应能力是对应着一个染色体的一个数值来衡量;染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。
神经网络算法
根据一个简化的统计,人脑由百亿条神经组成 — 每条神经平均连结到其它几千条神经。通过这种连结方式,神经可以收发不同
数量的能量。神经的一个非常重要的功能是它们对能量的接受并不是立即作出响应,而是将它们累加起来,当这个累加的总和达到某个临界阈值时,它们将它们自己的那部分能量发送给其它的神经。大脑通过调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述。但同样可以充分有力地被看作是神经网络的模型。