求解正交表问题的拟物拟人方法
文献类型：学位论文
| 作者 | 赵孝武 |
| 学位类别 | 博士 |
| 答辩日期 | 2000 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 中国科学院软件研究所 |
| 关键词 | 拟物法 拟人法 正交表 拉丁方 正交拉丁方 可满足性 NP问题 |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | 正交表是一类非常重要的数组结构，它在正交实验设计、编码理论、计算机安全等领域有着广泛的应用。人们对正交表的构造大都是纯数学方法。本文应用拟物拟人方法来求解若干正交表的构造问题。拟物拟人方法是一种求解诸如NP问题和其它困难数学问题的方法。所谓拟物就是主动地向自然界学习解决问题的方法，它是寻找到与原始数学问题等价的物理世界并观察这具世界中物质运动的生动形象，然后从中得出启发并逐步化为算法以求解问题。拟人方法则是向人，向人类的各种社会经验学习解决问题的策略。拟物方法将原始问题落实为优化问题，而用数学方法在求解优化问题时，常常会碰到计算落入目标函数的局部极小值陷阱的困境，如何从这种困境中逃逸出来，使得计算奔向前景更好的区域，拟物方法则无能为力，而应用拟人方法则可以设计出好的“跳出陷阱”策略。本学位论文围绕求解正交表问题的拟物拟人方法做了以下工作：第一，阐述了拟物拟人方法的涵义，通过对一些具体问题应用拟物拟人方法的心得和体会，总结出应用该方法求解问题的基本技术路线。第二，对于求角SAT问题的拟物拟人方法中所依赖的物理模型做了进一步分析，针对此模型的一个物理猜想，构造出反例，证明了这个物理猜想不成立。但是，考虑到拟物拟人算法吸引区的存在，此反例并不降低该物理模型的现实效果。这就从侧面反映出拟人方法是保证算法高效的必不可少的环节，从而加深了对拟物拟人方法的感性认识。第三，应用拟物拟人方法求解正交表的构造问题。我们首次建立了求解饱和正交表问题的物理模型，并从理论上证明了该模型的正确性。在此基础上，应用拟人方法设计出拟人化的“跳出局部极小值陷阱”的策略。从而得到了求解饱和正交表问题的拟物拟人算法。实验表明，其效果明显地高于基于纯数学的冲突数目标函数模型。应用此算法，我们成功地计算出难的三水平正交表L_(27)(3~(13))，并得到了一些不同构的正交表L_(27)~(3~(13))，其中有些结果与目前所看到的文献上的正交表也都不同构。第四，应用拟物拟人方法浓度求解古老而重要的拉丁方、正交拉丁方（它们事实上是正交表）问题。我们结合这些问题的特性，建立了新的物理模型，从理论上证明了这些物理模型的正确性，并设计出拟人化的“跳出局部极小值陷阱”的策略，得到了求解拉丁方、正交拉丁方的拟物拟人算法。实验表明，对某些问题算法有好的效果。虽然对于的求解两个10阶正交拉丁方问题没有成功，但按该拟物拟人算法搜寻的结果已非常接近其解。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 101 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6404]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 赵孝武. 求解正交表问题的拟物拟人方法[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2000. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。