Title:  求解正交表问题的拟物拟人方法 
Author:  赵孝武

Issued Date:  2000

Major:  计算机软件与理论

Degree Grantor:  中国科学院软件研究所

Place of Degree Grantor:  中国科学院软件研究所

Degree Level:  博士

Keyword:  拟物法
; 拟人法
; 正交表
; 拉丁方
; 正交拉丁方
; 可满足性
; NP问题

Abstract:  正交表是一类非常重要的数组结构，它在正交实验设计、编码理论、计算机安全等领域有着广泛的应用。人们对正交表的构造大都是纯数学方法。本文应用拟物拟人方法来求解若干正交表的构造问题。拟物拟人方法是一种求解诸如NP问题和其它困难数学问题的方法。所谓拟物就是主动地向自然界学习解决问题的方法，它是寻找到与原始数学问题等价的物理世界并观察这具世界中物质运动的生动形象，然后从中得出启发并逐步化为算法以求解问题。拟人方法则是向人，向人类的各种社会经验学习解决问题的策略。拟物方法将原始问题落实为优化问题，而用数学方法在求解优化问题时，常常会碰到计算落入目标函数的局部极小值陷阱的困境，如何从这种困境中逃逸出来，使得计算奔向前景更好的区域，拟物方法则无能为力，而应用拟人方法则可以设计出好的“跳出陷阱”策略。本学位论文围绕求解正交表问题的拟物拟人方法做了以下工作：第一，阐述了拟物拟人方法的涵义，通过对一些具体问题应用拟物拟人方法的心得和体会，总结出应用该方法求解问题的基本技术路线。第二，对于求角SAT问题的拟物拟人方法中所依赖的物理模型做了进一步分析，针对此模型的一个物理猜想，构造出反例，证明了这个物理猜想不成立。但是，考虑到拟物拟人算法吸引区的存在，此反例并不降低该物理模型的现实效果。这就从侧面反映出拟人方法是保证算法高效的必不可少的环节，从而加深了对拟物拟人方法的感性认识。第三，应用拟物拟人方法求解正交表的构造问题。我们首次建立了求解饱和正交表问题的物理模型，并从理论上证明了该模型的正确性。在此基础上，应用拟人方法设计出拟人化的“跳出局部极小值陷阱”的策略。从而得到了求解饱和正交表问题的拟物拟人算法。实验表明，其效果明显地高于基于纯数学的冲突数目标函数模型。应用此算法，我们成功地计算出难的三水平正交表L_(27)(3~(13))，并得到了一些不同构的正交表L_(27)~(3~(13))，其中有些结果与目前所看到的文献上的正交表也都不同构。第四，应用拟物拟人方法浓度求解古老而重要的拉丁方、正交拉丁方（它们事实上是正交表）问题。我们结合这些问题的特性，建立了新的物理模型，从理论上证明了这些物理模型的正确性，并设计出拟人化的“跳出局部极小值陷阱”的策略，得到了求解拉丁方、正交拉丁方的拟物拟人算法。实验表明，对某些问题算法有好的效果。虽然对于的求解两个10阶正交拉丁方问题没有成功，但按该拟物拟人算法搜寻的结果已非常接近其解。 
English Abstract:  Orthogonal table, which has wide applications in experimental design, coding theory and computer security, is an important sort of array structures. People usually use the pure mathematical approaches to construct orthogonal tables. This paper we use the quasiphysical and quasisociological methods to solve the problem of construct orthogonal tables. The quasiphysical and quasisociological methods for problemsolving is a new approach to solve problems including NPcompleted and other pure mathematical problems. As far as the quasiphysical method is concerned, it is a way that people actively turn to nature for wisdom to solving problem. In other words, it works in such a way that to find natural phenomena which we equivalent to the original mathematical problem in the physical world and then observe the evolution of the motion of matter in it so as to be inspired to obtain a formalistic algorithm for solving the mathematical problem. The quasisociological method, however, is learning from human beings and their rich social experiences for wisdom to solving problem. The quasiphysical method makes the original problem an optimization problem in mathematics. There is often the possibility of going to a local minimum of object function when we solve the optimization problem mathematically. As for how to jump out of the trap of local minimum so that the calculation can head for a region with better prospects, the quasiphysical method is helpless. However, the quasisociological method can give us good strategies for jumping out of a trap of local minimum with the help of human beings' behavior and experiences. This dissertation includes the following main works on the quasiphysical and quasisociological methods for solving some problems of orthogonal table: Firstly, we set forth the original ideas and the meaning of quasiphysical and quasisociological methods. cording to the comprehension of which we applied the quasiphysical and quasisociological methods to some real problems, we sum up a basic technical path how the quasiphysical and quasisociological methods work. Secondly, we further analyze the physical model on which the quasiphysical and quasisociological methods for solving SAT problem based. Considering a physical hypothesis on this model, we construct a counterexample to show that the hypothesis is not true. However, it does not damage the good practical effect of applying this physical model to solve SAT problem considering the existence of algorithmic region, which reflects that the quasisociological method is very necessary for assuring the high efficient of the whole algorithm and therefore deepens our comprehension on the quasiphysical and quasisociological methods. Thirdly, we apply the quasiphysical and quasisociological methods to the pure mathematical problem of construction of orthogonal tables. We successfully establish a physical optimization model for solving saturated orthogonal tables, which was proved to be correct in theory. We think out good personated strategies for jumping out of the trap of local minimum using quasisociological method based on the physical model. Thus we get the whole quasiphysical and quasisociological algorithm for the problem of construction of saturated orthogonal tables. The experimental results show that the physical model is highly efficient than the conflicting number model based on the pure mathematical background. We successfully work out the famous orthogonal table with 3 levels using the quasiphysical and quasisociological algorithm. We got some orthogonal tables of L_(27)(3~(13)) which are not isomorphic. Moreover, some of our results are also not isomorphic to the results appeared in the open references we got up to now. Lastly, for the ancient and important porblems of construction of Latin square and orthogonal Latin squares (most of Latin square and orthogonal Latin squares actually are orthogonal tables), we try to use the quasiphysical and quasisociological methods to solve them. We build new optimization models based on physical background according to the characteristic of these problems and prove them theoretically. We also get the new quasiphysical and quasisociological algorithms for the problem of construction of Latin square and orthogonal Latin squares based on the new physical models and the new personated strategies for jumping out of the trap of local minimum which we designed using quasisociological method. The experimental results show that these algorithms are efficient for some problems. Although the algorithm fails to work out the important and famous two orthogonal Latin squares of order 10, the result using the quasiphysical and quasisociological algorithm is very close to the solution. 
Language:  中文

Content Type:  学位论文

URI:  http://ir.iscas.ac.cn/handle/311060/6404

Appears in Collections:  中科院软件所

File Name/ File Size 
Content Type 
Version 
Access 
License 

LW004414.pdf（1731KB）      限制开放    联系获取全文 

Recommended Citation: 
赵孝武. 求解正交表问题的拟物拟人方法[D]. 中国科学院软件研究所. 中国科学院软件研究所. 20000101.


