基于协同进化的平面追逃对策研究

建立了二维平面内动力学约束下迫逃运动的数学模型.首先为追捕者设计了基于比例制导算法和进化算法的混合追捕策略,以提高其追捕能力;然后利用协同进化算法对追捕者和逃跑者的追选策略进行进化.仿真结果表明,进化后的逃跑策略能有效规避比例制导的追捕者.逃跑者在协同进化过程中涌现出众多复杂多变的规避策略.     

Mechanical parts orienting: The case of a polyhedron on a table

The positioning and orienting of parts is a standard problem in manufacturing. Orienting parts is often a prelude to the assembly of parts at tight tolerances. This paper considers the problem of orienting a part resting on a table, by tilting the table. The initial orientation of the part is assumed to be completely unknown. The objective is to tilt the table in a manner that reduces the uncertainty in the part's orientation. This paper focuses on three-dimensional polyhedral parts, with infinite friction between the parts and the table, and for which all transitions between different face-table contacts may be regarded as rotations across edges. The paper proposes a planner that determines a sequence of tilting operations designed to minimize the uncertainty in the part's orientation. The planner runs in timeO(n ³), wheren is the number of faces of the polyhedron. The planner produces a sequence ofO(n) distinct tilting operations. Each tilting operation wobbles the table until the part is in steady state.This research was supported, through the Leonardo Fibonacci Institute, by the Istituto Trentino di Cultura, Trento, Italy. Additional support for M. Erdmann was provided by Carnegie Mellon University and by NSF Grant IRI-9010686, additional support for M. Mason was provided by Carnegie Mellon University, and additional support for G. Vanek was provided by NSF Grant CCR-86-19817 to Purdue University.     

GLEAM: a graph clustering framework based on potential game optimization for large-scale social networks

With the growing explosion of online social networks, the study of large-scale graph clustering has attracted considerable interest. Most of traditional methods view the graph clustering problem as an optimization problem based on a given objective function; however, there are few methodical theories for the emergence of clusters over real-life networks. In this paper, each actor in online social networks is viewed as a selfish player in a non-cooperative game. The strategy associated with each node is defined as the cluster membership vector, and each one’s incentive is to maximize its own social identity by adopting the most suitable strategy. The definition of utility function in our game model is inspired by the conformity psychology, which is defined as the weighted average of one’s social identity by participating different clusters. With this setting, the proposed game can well match a potential game. So that the cluster could be shaped by the actions of those closely interactive users who adopt the same strategy in a Nash equilibrium. To this end, we propose a novel Graph cLustering framework based on potEntial gAme optiMization (GLEAM) for parallel graph clustering. It first utilize the cosine similarity to weight each edge in the original network. Then, an initial partition, including a number of clusters dominated by those potential “leader nodes”, is created by a fast heuristic process. Third, a potential game-based weighted Modularity optimization is used to improve the initial partition. Finally, we introduce the notion of potentially attractive cluster, and then discover the overlapping partition of the graph using a simple double-threshold procedure. Three phases in GLEAM are carefully designed for parallel execution. Experiments on real-world networks analyze the convergence inside GLEAM, and demonstrate the high performance of GLEAM by comparing it with the state-of-the-art community detection approaches in the literature.     

Finding the exact volume of a polyhedron

This paper addresses the design and development of a computer program for finding the exact volume of a multi-dimensional polyhedron that is enclosed by a set of linear inequalities. The program is designed to calculate the volume of a polyhedron of any dimensions defined by a set of linear inequalities. The speed of the program depends on the number of inequalities and the number of variables. The program has been tested against several two- and three-dimensional polygons in which the volume can be calculated by formulae. The results of the tests show that the accuracy of the program is at least up to 10⁻⁶ and it can calculate the volume of a three-dimensional polygon defined by a few hundred inequalities in just a few minutes. However, as the number of variables increases, the computation time increases exponentially.The program can be used in some science and engineering application such as finding the probability of an event, the volume of a crystal in a wafer fabrication industry, and other applications in the manufacturing industry.     

Evaluation of the effectiveness of open-loop evasion strategies in a pursuit-evasion problem

A stochastic pursuit-evasion optimal control problem in the (X, z)-plane is considered. Owing to thrust, drag and gravitational forces, both players have variable speeds. The pursuer applies a feedback pursuit strategy whereas the evader applies an open-loop evasion strategy. By reducing the state-space of the encounter, a method is proposed for evaluating the effectiveness of open-loop evasion strategies.     

The discrete-time quaternionic quantum walk on a graph

Recently, the quaternionic quantum walk was formulated by the first author as a generalization of discrete-time quantum walks. We deal with the right eigenvalue problem of quaternionic matrices in order to study spectra of the transition matrix of a quaternionic quantum walk. The way to obtain all the right eigenvalues of a quaternionic matrix is given. From the unitary condition on the transition matrix of a quaternionic quantum walk, we deduce some remarkable properties of it. Our main results determine all the right eigenvalues of the quaternionic quantum walk by using those of the corresponding weighted matrix. In addition, we give some examples of quaternionic quantum walks and their right eigenvalues.     

On the edge-tenacity of the middle graph of a graph

We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S)=[| S|+τ (G?S)]/[w(G?S)]. Formally, the edge-tenacity of a graph G is defined as T′(G)=min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T′-set of G if T′(G)=sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, τ(G?S) is the number of vertices in the largest component of G?S and w(G?S) is the number of components of G?S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.     

The hub number of a graph

A hub set in a graph G is a set U⊆V(G) such that any two vertices outside U are connected by a path whose internal vertices lie in U. We prove that h(G)?hc(G)?γc(G)?h(G)+1, where h(G), hc(G), and γc(G), respectively, are the minimum sizes of a hub set in G, a hub set inducing a connected subgraph, and a connected dominating set. Furthermore, all graphs with γc(G)>hc(G)?4 are obtained by substituting graphs into three consecutive vertices of a cycle; this yields a polynomial-time algorithm to check whether hc(G)=γc(G).     

Spherical harmonic coefficients for the potential of a constant-density polyhedron

Recurrent relationships for the definitions of fully normalized spherical harmonic coefficients C?_n,m and S?_n,m are derived and integrated analytically to yield the gravitational potential of a constant-density polyhedron. The algorithm is expressed in a C language computer program.     

Matching perspective views of a polyhedron using circuits

We present a novel approach for finding corresponding points between two line drawings extracted from perspective views of a moving object whose surface is composed of planar polygons. In our approach, each circuit of the drawings is encoded with a boundary shape code which we call the RLCC code (run length code of convex and concave strings), then a clustering technique is used to obtain the matching result recursively. A series of measures are taken to make the algorithm tolerate considerable dissimilarities which may exist between the two drawings, such as missing lines, scale differences, rotation, perspective shape distortions, etc. Experimental results are presented.     

The graph topology on nth-order systems is quotientEuclidean

It is shown that on the set of m-input p-output minimal nth-order state-space systems the graph topology and the induced Euclidean quotient topology are identified. The author considers the set L_n^p×m of m -input p-output nth-order minimal state-space systems. The author presents three lemmas and a corollary from which a theorem is proved stating that the graph topology and the quotient Euclidean topology are identical on a quotient space L_n ^p×m/~. Since the graph topology is constructed to be weak, and the quotient Euclidean topology is intuitively strong, this result is unexpected     

The impact of a simulation game on operations management education

This study presents a new simulation game and analyzes its impact on operations management education. The proposed simulation was empirically tested by comparing the number of mistakes during the first and second halves of the game. Data were gathered from 100 teams of four or five undergraduate students in business administration, taking their first course in operations management. To assess learning, instead of relying solely on an overall performance measurement, as is usually done in the skill-based learning literature, we analyzed the evolution of different types of mistakes that were made by students in successive rounds of play. Our results show that although simple decision-making skills can be acquired with traditional teaching methods, simulation games are more effective when students have to develop decision-making abilities for managing complex and dynamic situations.     

The complexity of determining the rainbow vertex-connection of a graph

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. In this paper, we study the complexity of determining the rainbow vertex-connection of a graph and prove that computing rvc(G) is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether rvc(G)=2. We also prove that the following problem is NP-Complete: given a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected.     

The self-trapping attractor neural network. I. Analysis of a simple 1-D model

Attractor neural networks (ANNs) based on the Ising model are naturally fully connected and are homogeneous in structure. These features permit a deep understanding of the underlying mechanism, but limit the applicability of these models to the brain. A more biologically realistic model can be derived from an equally simple physical model by utilizing recurrent self-trapping inputs to supplement very sparse intranetwork interactions. This paper reports the analysis of a one-dimensional (1-D) ANN coupled to a second system that computes overlaps with a single stored memory. Results show that: 1) the 1-D self-trapping model is equivalent to an isolated ANN with both full connectivity of one strength and nearest neighbor synapses of an independent strength; 2) the dynamics of ANN and self-trapping updates are independent; 3) there is a critical synaptic noise level below which memory retrieval occurs; 4) the 1-D self-trapping model converges to a fully connected Hopfield model for zero strength nearest neighbor synapses, and has a greater magnitude memory overlap for nonzero strength nearest neighbor synapses; and (5) the mechanism of self-trapping is an iterative map on the mean overlap as a function of the reentrant input.     

The game chromatic number and the game colouring number of cactuses

We consider the colouring game and the marking game. A graph G is a cactus if any two cycles of G have at most one common vertex. We prove that χg(C)=colg(C)=5 for family of cactuses C.     

The largest tree in a random graph

In this paper we study the problem of finding the largest tree in a random graph. First of all, we estimate the size of the largest tree almost surely. Then we propose two approximate greedy algorithms. Both algorithms achieve a solution whose value is one half of the value of the optimal solution, with high probability.