用混合遗传算法求解图的邻强边着色问题

图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。     

双目标进化算法求解图着色问题

根据图着色问题的特征,提出了求解图着色问题的双目标模型;设计的有效、简洁的杂交算子和变异算子,均直接产生可行的后代个体;理论分析表明算法以概率1收敛到问题的最优解集.对标准算例进行了仿真实验,结果表明,双目标进化算法可以获得问题高质量的解,即对图进行着色所使用的颜色接近图的色数.     

Simulated annealing algorithm for detecting graph isomorphism

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.     

EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS

In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.     

Star Chromatic Numbers of Planar Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＤｅｆｉｎｉｔｉｏｎ１．１Ｌｅｔｋ,ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ,ａ（ｋ,ｄ）－ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ,Ｅ）ｉｓａｍａｐｐｉｎｇｃ：Ｖ→Ｚｋ,ｓｕｃｈｔｈａｔｆｏｒｅａｃｈｅｄ...     

MPS上作业的分配和调度问题

多处理机系统MPS(MultiprocessorSystem)上作业的分配和调度问题是其运行效率的关键.本文讨论的是具有不相容性作业集的作业分配和调度问题,提出了一种启发式方法及其定量分析技术,并证明了相关定理和若干推论.     

CONVERGENCE OF A CLASS OF MULTI-AGENT SYSTEMS IN PROBABILISTIC FRAMEWORK

Multi-agent systems arise from diverse fields in natural and artificial systems, and a basic problem is to understand how locally interacting agents lead to collective behaviors （e.g., synchronization） of the overall system. In this paper, we will consider a basic class of multi-agent systems that are described by a simplification of the well-known Vicsek model. This model looks simple, but the rigorous theoretical analysis is quite complicated, because there are strong nonlinear interactions among the agents in the model. In fact, most of the existing results on synchronization need to impose a certain connectivity condition on the global behaviors of the agents＇ trajectories （or on the closed-loop dynamic neighborhood graphs）, which are quite hard to verify in general. In this paper, by introducing a probabilistic framework to this problem, we will provide a complete and rigorous proof for the fact that the overall multi-agent system will synchronize with large probability as long as the number of agents is large enough. The proof is based on a detailed analysis of both the dynamical properties of the nonlinear system evolution and the asymptotic properties of the spectrum of random geometric graphs.     

Research and application of hierarchical model for multiple fault diagnosis

1.INTRODUCTION Failureanalysisanddiagnosisoflarge scalesystems havereceivedconsiderableattentionduringtherecent years[1～3].Thesesystemshaveevolvedfromthepre viousonesbasedonheuristicknowledgeofsymptom faultassociationstothemorerecentonesbasedon structure,behaviorandfunctionalityofthedevice andsubsystemtobediagnosed[4].Inthecaseof complexsystem,theapplicationofmodel baseddiag nosisalgorithmsbecomescomputationallyverydiffi cultorevenintractable.Ahierarchicaldiagnosisap proachcansignificant…     

一类混杂系统的推广自动机模型及其仿真

通过分析混杂系统的特点,以混杂系统自动机建模理论为基础,结合一种特殊的并行投影结构（Projection Construct）,提出了针对混杂系统的推广自动机模型。该模型着眼于连续状态空间的划分。并行投影结构有效的处理了离散事件动态子系统和连续变量动态子系统之间的接口问题。该方法获得的混杂系统模型由图形的方式表示,简单直观。最后用两个实例介绍了推广自动机模型的建模过程,并借助Matlab环境中的Stateflow工具箱,对模型进行了仿真,结果表明该模型能够很好地解决混杂系统中离散部分和连续部分的同步协调问题。     

Learning multivariate time series causal graphs based on conditional mutual information

Detection and clarification of cause-effect relationships among variables is an important problem in time series analysis.This paper provides a method that employs both mutual information and conditional mutual information to identify the causal structure of multivariate time series causal graphical models.A three-step procedure is developed to learn the contemporaneous and the lagged causal relationships of time series causal graphs.Contrary to conventional constraint-based algorithm, the proposed algorithm does not involve any special kinds of distribution and is nonparametric.These properties are especially appealing for inference of time series causal graphs when the prior knowledge about the data model is not available.Simulations and case analysis demonstrate the effectiveness of the method.     

基于图论的作战指挥决策群组划分算法

从作战任务相关程度的角度出发,研究作战指挥决策群组划分问题。针对以往的群组划分需要预先设定决策群组的个数,且没有充分利用群组内成员间相关程度的传递特性的不足,设计了根据指挥决策个体作战意图间的相关程度进行聚类的算法。引入了意图距离的概念,给出了自适应的阈值设定方法,并将群组划分问题转换为图论中的赋权完全图的联通分图求解问题,给出了求解算法。算例证明了该方法的可行性和有效性。     

EQUITABLE COLORINGS OF LINE GRAPHS AND COMPLETE r-PARTITE GRAPHS

1. IntroductionLet G be a graph with vertex set V(G), edge set E(G), maximum degree A(G), minimumdegree 8(G), vertex chromatic number X(G), and edge chromatic number X'(G). G is equitablyk-colorable if V(G) can be pajrtitioned icao k independent sets VI, V2,'', Vk such that llKI III 1 5 1 for all i and j. The such smallest integer k as above is called the equitable chromaticnumber of G, denoted by X= (G). Similaxly we can define the equitable edge chromatic numberof a graph G and d…     

多色图及其在仿真复杂对象及系统时的应用

在介绍了多色图的概念,多色图的组成和多色图的数学模型后,阐述了在围道析取矩阵的多色图PG和围道合取矩阵的多色图PG中路径F（μi）的计算公式和方法。最后举出了简例。多色图这一新的信息处理工具对复杂对象和系统具有强大的仿真功能。     

GRAPHS WHOSE CIRCULAR CLIQUE NUMBER EQUAL THE CLIQUE NUMBER

The circular clique number of a graph G is the maximum fractional k/d such that G^kd admits a homomorphism to G. In this paper, we give some sufficient conditions for graphs whose circular clique number equal the clique number, we also characterize the K1,3-free graphs and planar graphs with the desired property.     

一类具有分形和小世界特性的网络图

提出一类具有分形和小世界特性的网络图.利用数学归纳的方法计算出了网络图的集聚系数,平均最短路径和网络图的直径,证明了网络图的小世界特性.用盒维数和豪斯道夫维数来衡量网络图的分形性,得到其维数均为1.585.最后对网络图的构造方法作了进一步地拓展,并给出了拓展的网络图的相关拓扑特性的表达式,并认为其和原来的网络图可归结为一类具有分形和小世界特性的网络图.     

粗糙网络及其应用

粗糙图理论是知识发现、知识挖掘的新的理论工具。对粗糙图理论做进一步的研究,首先给出了有向粗糙图的定义,并进一步定义了粗糙网络及粗糙网络中的类流,又讨论了有向粗糙图及粗糙网络的表示形式。通过推广传统最大流算法,给出了粗糙网络中的类最大流算法,并将其应用于新的一类关系挖掘问题中。     

ON THE CONNECTIVITY OF CAYLEY COLOR GRAPHS

In this paper we obtain the necessary and sufficient condition for the connec-tivity of the Cayley color graphs or the Cayley graphs to be equal to their minimum degree.The sharp lower bounds of connectivity of Cayley color graphs and the Cayley graphs arealso obtained. Our results generalize the previous results obtained in [1] to [3].     

Projective Group Consensus of Multi-Agent Systems with Arbitrary Parameter

In this paper, the projective group consensus issue for second order multi-agent systems(MASs) in directed graphs with a dynamic leader is investigated. The proposed projective group consensus with arbitrary parameter includes traditional consensus, reverse group consensus and cluster consensus as its special cases. Novel distributed control protocols are designed to obtain projective group consensus without analyzing signed directed graph as in most current literatures on bipartite consensus problem. On the basis of Lyapunov stability property, algebraic graph and some necessary matrix theory, sufficient conditions for delay and delay-free cases are derived. Finally, simulations of nonlinear chaotic MASs are adopted to testify the theoretical results.     

微粒群算法的可视化仿真及算法改进

微粒群算法是一种群体智能算法,它是通过模拟以鸟类、昆虫等为微粒的自然界的群体行为,来构造的一种随机寻优的进化算法。现有的微粒群算法在某些情况下存在收敛速度慢、而且不能收敛于全局最优解的问题。通过采用可视化的仿真方法对微粒群的搜索运动轨迹进行分析,我们提出了变尺度微粒群算法。变尺度微粒群算法将变尺度方法引入微粒的搜索过程中,采用不同的尺度动态地改变微粒群的搜索空间、速度限制区间等,通过对一些典型的试验函数的测试,结果表明,变尺度微粒群算法在收敛速度和全局寻优能力等方面都有较大的改进。     

基于决策图贝叶斯的多目标QoS组播路由算法

随着实时组播通信需求的不断增长，要求网络能够提供更加严格高效的QoS(Quality of Service)路由保证，需要设计一个能够同时满足不同QoS约束的高效组播路由算法。此问题可归结为图论中的NP(Non-Polymenital)问题，一般方法是把多个QoS参数加权合并为一单目标函数进行优化。提出了一种基于决策图贝叶斯的多目标QoS组播路由算法，算法在不需做预处理的情况下可对多个不同的QoS参数同时进行优化。仿真结果表明，所提出的算法能够快速收敛于一组满足不同QoS约束的非支配解。