论文部分内容阅读
TSP问题是组合优化问题的一个典型代表,数学家已经证明在图灵机上无法获得其精确的最优解,它属于NP难的问题。求解TSP问题无论在理论上还是在工农业生产或国民经济中都具有重大实际意义。两个多世纪以来,人们发明出各种方法来求解其近似最优解或满意解。本文证明和验证了,在引入基准变换算子后,定性映射模型可以用以解决TSP问题。 定性映射模型是一个新兴的数学模型,它表达的是事物属性量一质特征转化关系,其哲学基础是事物质量互变规律,其基本内涵是依据特定的属性基准,从事物的一个或多个量特征中抽取出质特征。在数学上已经证明它可以推导出人工神经元,用它可以解决异或分类问题,双螺旋问题等人工智能问题中的经典难题,它在核事故决策支持系统和高考招生系统中已经得到实际的应用。 质特征pi(o)的量x∈(αi,βi)越接近其(αi,βi)的边缘,也越容易发生质变。也就是说,若x1,x2∈(αi,βi)同属一个定性基准,经量—质特征转化后,尽管它们对应的性质同属一个质特征类,即:pi(x1),pi(x2)∈pi(o),但在转化为pi(o)的程度上,pi(x1)和pi(x2)却会因x1≠x2而产生很大的差异。这种因量不同而导致的质转化程度差异,普遍存在于属性量一质转化及其诱导的各种定性判断和模式识别之中,而定性映射τi(x)却无法表现这种差异,转化程度函数就是用来刻画这种差异的一种数学工具。 基准变换是指以某种规则形式对定性基准进行调控,从而使定性映射能根据输入变量、外界环境、决策者心理经验标准等因素变成一个动态映射,本文提出了一类特殊的基准变换——基准变换算子,从而得到了动态程度转化函数,它可用于解决TSP问题,我们的模型无需事先学习或训练,而是边学习边搜索,模型具有较好的稳定性,从而为这个经典问题提供了一种新的解决思路,拓宽了转化程度函数的功能,也为定性映射找到了新的应用领域。 论文的第一章介绍相关背景,介绍TSP的历史、意义、现有的解决方法、实际应用和最新进展,并对现有的一些解决方法如贪婪法,模拟退火算法和遗传算法等做一个比较,指出它们的不足之处。 论文的第二章主要介绍定性映射模型及其诱导的线性规划问题和人工神经元网络。 论文的第三章讨论用定性映射模型求解TSP问题,遇到的问题及解决方法。 论文的第四章详细介绍启发式定性映射模型以及如何用它来求解TSP问题。 论文的第五章介绍Traveller软件,分析用其求解中国TSP问题的试验结果,并对全上海海运学院硕士学位论文文做出结论。