Networked Evolutionary Model of Snow-Drift Game Based on Semi-Tensor Product

This paper investigates the networked evolutionary model based on snow-drift game with the strategy of rewards and penalty. Firstly, by using the semi-tensor product of matrices approach, the mathematical model of the networked evolutionary game is built. Secondly, combined with the matrix expression of logic, the mathematical model is expressed as a dynamic logical system and next converted into its evolutionary dynamic algebraic form. Thirdly, the dynamic evolution process is analyzed and the final level of cooperation is discussed. Finally, the effects of the changes in the rewarding and penalty factors on the level of cooperation in the model are studied separately, and the conclusions are verified by examples.

A Semi-Tensor Product Based All Solutions Boolean Satisfiability Solver

Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively.

基于NSCT和半张量积在防跑道侵入检测技术的研究

为进一步提高跑道侵入告警系统的自动化水平,降低设施设备安装维护成本等问题,通过摄像设备获取机场场面的视频图像数据,采用稀疏表示对视频图像数据集进行检测处理;通过利用NSCT算法优化,结合半张量积,对样本数据集进行跟踪训练;根据单目摄像机测距建立坐标转换和测距模型,对机场场面航空器与跑道中线的距离进行准确测量,根据地面保护区设置合适的阈值实现跑道侵入告警。实验结果表明,优化后的模型图像重构质量提高了7.07%,平均处理时间降低了21.95%,模拟环境下跑道侵入告警准确率为95.2%。模型重构质量好,处理时间快、实时性好、准确率高,可以为预防跑道侵入事件的发生提供方法支持。

云存储中基于压缩感知和生命游戏的图像数据保护算法

为实现云存储中图像数据低成本采样和安全传输,本文提出一种基于压缩感知和生命游戏的图像数据保护算法.该算法利用生命游戏规则产生的置乱矩阵,置乱明文图像的稀疏矩阵,增强元素的随机性,使得矩阵有较好的置乱效果.结合半张量积和压缩感知技术对置乱后的矩阵进行加密和压缩,极大地节省图像数据在采样和传输过程中的存储空间.将压缩图像数据量化到0~255之间,提升图像数据的安全性.利用混沌系统产生的混沌序列实现压缩图像的扩散,增大图像信息熵.由于高维混沌系统产生混沌序列,该方案具有密钥敏感度高的优点.经实验分析,所提出的图像加密算法可以应用于云存储,且具有较高的安全性与传输效率.

基于矩阵半张量积解四元数广义Sylvester矩阵方程组

该文利用矩阵半张量积求解四元数广义Sylvester矩阵方程组.首先将实矩阵半张量积运算推广到四元数矩阵,进而利用四元数矩阵半张量积提出四元数矩阵在向量算子下的一些新结论,利用这些结论将四元数矩阵方程组转化为四元数线性方程组,最后转化为实线性方程组,从而得到四元数广义Sylvester矩阵方程组有解的充要条件及通解表达式,并给出其极小范数解.最后通过数值算例说明该方法的有效性.

四元数矩阵方程(A_(1)XB_(1),…,A_(k)XB_(k))=(C_(1),…,C_(k))的极小范数最小二乘Toeplitz解

基于四元数矩阵实表示,结合矩阵H-表示和矩阵半张量积提出一种求解四元数矩阵方程(A_(1)XB_(1),…,A_(k)XB_(k))=(C_(1),…,C_(k))的极小范数最小二乘Toeplitz解的有效方法,给出该四元数矩阵方程存在Toeplitz解的充要条件及通解表达式.给出数值算法并通过算例分别从误差与计算时间两个方面验证该方法的有效性.

Semi-tensor product of matrices and its application to Morgen's problem

This paper proposes a new matrix product, namely, semi-tensor product. It is a generalization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The purpose of introducing this product is twofold: (i) treat multi-dimensional data; (ii) treat nonlinear problems in a linear way. Then the computer and numerical methods can be easily used for solving nonlinear problems. Properties and formulas are deduced. As an application, the Morgen's problem for control systems is formulated as a numerically solvable problem.

Design of semi-tensor product-based kernel function for SVM nonlinear classification

The kernel function method in support vector machine(SVM)is an excellent tool for nonlinear classification.How to design a kernel function is difficult for an SVM nonlinear classification problem,even for the polynomial kernel function.In this paper,we propose a new kind of polynomial kernel functions,called semi-tensor product kernel(STP-kernel),for an SVM nonlinear classification problem by semi-tensor product of matrix(STP)theory.We have shown the existence of the STP-kernel function and verified that it is just a polynomial kernel.In addition,we have shown the existence of the reproducing kernel Hilbert space(RKHS)associated with the STP-kernel function.Compared to the existing methods,it is much easier to construct the nonlinear feature mapping for an SVM nonlinear classification problem via an STP operator.

Finding Cut-Edges and the Minimum Spanning Tree via Semi-Tensor Product Approach

Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.

Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices

In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed network.Thus,the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks.In this study,the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu,et al.(2011)via a new matrix product called semi-tensor product,based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs,which make determining the number of driver nodes tractable in computer.In addition,according to the proposed algorithm,the authors also construct an algorithm to distinguish critical arcs,redundant arcs and ordinary arcs of the directed network,which plays an important role in studying the robust control problem.An example of a small network from Liu’s paper is used for algorithm verification.

Dynamic output feedback stabilization of deterministic finite automata via the semi-tensor product of matrices approach

This paper deals with the dynamic output feedback stabilization problem of deterministic finite automata(DFA).The static form of this problem is defined and solved in previous studies via a set of equivalent conditions.In this paper,the dynamic output feedback(DOF)stabilization of DFAs is defined in which the controller is supposed to be another DFA.The DFA controller will be designed to stabilize the equilibrium point of the main DFA through a set of proposed equivalent conditions.It has been proven that the design problem of DOF stabilization is more feasible than the static output feedback(SOF)stabilization.Three simulation examples are provided to illustrate the results of this paper in more details.The first example considers an instance DFA and develops SOF and DOF controllers for it.The example explains the concepts of the DOF controller and how it will be implemented in the closed-loop DFA.In the second example,a special DFA is provided in which the DOF stabilization is feasible,whereas the SOF stabilization is not.The final example compares the feasibility performance of the SOF and DOF stabilizations through applying them to one hundred random-generated DFAs.The results reveal the superiority of the DOF stabilization.

异步时滞布尔网络的内同步

提出异步时滞布尔网络的内同步模型,通过利用矩阵半张量积理论,研究异步时滞影响下的布尔网络内同步问题,分析时滞对布尔网络内同步的影响,给出了异步时滞布尔网络内同步实现的充分必要条件.通过数值仿真实例进一步验证了该模型的可行性以及所得结果的正确性.

A SURVEY ON SEMI-TENSOR PRODUCT OF MATRICES

当二个因素矩阵不遇见匹配状况的尺寸时，矩阵的半张肌产品是为盒子的常规矩阵产品的归纳。Itwas 大约十年以前第一求婚了。从那以后，它被开发了并且适用于几个不同领域。在这篇论文，我们将首先给简短介绍。然后分别地在它的应用程序上把调查给动态系统，到逻辑，到微分几何学，到抽象代数学。

Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling

这份报纸由使用矩阵半张肌产品用申请调查柔韧的图着色问题到一种考试 timetabling，并且介绍很多新结果和算法。用矩阵半张肌产品，首先，柔韧的图着色被表示进收进矩阵，一个算法基于被设计为任何简单的图发现所有最柔韧的着色计划的一种代数学的形式的一种优化问题。第二，柔韧的图着色的一个相等的问题被学习，并且一个必要、足够的条件从发现所有最柔韧的着色计划的一个新算法从哪个被建立被建议。第三，一种考试 timetabling 被使用获得的结果，和一个方法设计一个适用的 timetabling 计划讨论被介绍。最后，在这份报纸介绍的结果 / 算法的有效性被二个解说性的例子显示出。

Semi-tensor product approach to networked evolutionary games

In this paper a comprehensive introduction for modeling and control of networked evolutionary games(NEGs) via semi-tensor product(STP) approach is presented. First, we review the mathematical model of an NEG, which consists of three ingredients:network graph, fundamental network game, and strategy updating rule. Three kinds of network graphs are considered, which are i) undirected graph for symmetric games; ii) directed graph for asymmetric games, and iii) d-directed graph for symmetric games with partial neighborhood information. Three kinds of fundamental evolutionary games(FEGs) are discussed, which are i) two strategies and symmetric(S-2); ii) two strategies and asymmetric(A-2); and iii) three strategies and symmetric(S-3).Three strategy updating rules(SUR) are introduced, which are i) Unconditional Imitation(UI); ii) Fermi Rule(FR); iii) Myopic Best Response Adjustment Rule(MBRA). First, we review the fundamental evolutionary equation(FEE) and use it to construct network profile dynamics(NPD)of NEGs.To show how the dynamics of an NEG can be modeled as a discrete time dynamics within an algebraic state space, the fundamental evolutionary equation(FEE) of each player is discussed. Using FEEs, the network strategy profile dynamics(NSPD) is built by providing efficient algorithms. Finally, we consider three more complicated NEGs: i) NEG with different length historical information, ii) NEG with multi-species, and iii) NEG with time-varying payoffs. In all the cases, formulas are provided to construct the corresponding NSPDs. Using these NSPDs, certain properties are explored. Examples are presented to demonstrate the model constructing method, analysis and control design technique, and to reveal certain dynamic behaviors of NEGs.

ON THE OBSERVABILITY OF FREE BOOLEAN NETWORKS VIA THE SEMI-TENSOR PRODUCT METHOD

This paper investigates the observabihty of free Boolean networks by using the semi-tensor product method,and presents some new results.First,the concept of observability for free Boolean networks is proposed,based on which and the algebraic form of Boolean networks,a kind of observabihty matrix is constructed.Second,by the observability matrix,a new necessary and sufficient condition is given for the observability of Boolean networks.Third,the concept of observabihty index for observable Boolean networks is defined,and an algorithm is established to calculate the observability index.Finally,a practical example of D.Melanogaster segmentation polarity gene networks is studied to support our new results.The study of the illustrative example shows that the new results obtained in this paper are very effective in investigating the observability of free Boolean networks.

On Semi-tensor Product of Matrices and Its Applications

The left semi-tensor product of matrices was proposed in [2]. In this paper the right semi-tensor product is introduced first. Some basic properties are presented and compared with those of the left semi-tensor product.Then two new applications are investigated. Firstly, its applications to connection, an important concept in differential geometry, is considered. The structure matrix and the Christoffel matrix are introduced. The transfer formulas under coordinate transformation are expressed in matrix form. Certain new results are obtained.Secondly, the structure of finite dimensional Lie algebra, etc. are investigated under the matrix expression. These applications demonstrate the usefulness of the new matrix products.

Solving type-2 fuzzy relation equations via semi-tensor product of matrices

The problem of solving type-2 fuzzy relation equations is investigated. In order to apply semi-tensor product of matrices,a new matrix analysis method and tool, to solve type-2 fuzzy relation equations, a type-2 fuzzy relation is decomposed into two parts as principal sub-matrices and secondary sub-matrices; an r-ary symmetrical-valued type-2 fuzzy relation model and its corresponding symmetrical-valued type-2 fuzzy relation equation model are established. Then, two algorithms are developed for solving type-2 fuzzy relation equations, one of which gives a theoretical description for general type-2 fuzzy relation equations;the other one can find all the solutions to the symmetrical-valued ones. The results can improve designing type-2 fuzzy controllers,because it provides knowledge to search the optimal solutions or to find the reason if there is no solution. Finally some numerical examples verify the correctness of the results/algorithms.

The Computation of Nash Equilibrium in Fashion Games via Semi-Tensor Product Method

Using the semi-tensor product of matrices, this paper investigates the computation of purestrategy Nash equilibrium(PNE) for fashion games, and presents several new results. First, a formal fashion game model on a social network is given. Second, the utility function of each player is converted into an algebraic form via the semi-tensor product of matrices, based on which the case of two-strategy fashion game is studied and two methods are obtained for the case to verify the existence of PNE.Third, the multi-strategy fashion game model is investigated and an algorithm is established to find all the PNEs for the general case. Finally, two kinds of optimization problems, that is, the so-called social welfare and normalized satisfaction degree optimization problems are investigated and two useful results are given. The study of several illustrative examples shows that the new results obtained in this paper are effective.