网络流量预测方法

分析网络流量的行为特性并建立模型进行预测,对于网络管理以及安全预警具有重要意义。基于此,针对网络异常处理滞后、网络服务质量差等问题,研究多种经典流量预测方法,从流量特性、建模复杂性、预测精度及应用场景等多角度进行分析比较。实验结果证明,预测模型与具体场景密切相关,实际操作时需根据流量特性及预测目标选择合适的模型。     

改进Dijkstra算法在PGIS中的应用

传统Dijkstra算法用于路径诱导会使路网节点的数量增多、搜索范围扩大,从而耗费大量时间和空间,降低停车诱导信息系统(PGIS)的运行效率和实时性。针对城市路网的特定环境和路径诱导需求,根据2点之间直线最短的原理,在Dijkstra算法的基础上,提出一种应用于PGIS、基于矩形搜索范围的改进Dijkstra算法,设计并实现城市路网模型中单行、禁行、交叉点时间延误等问题的解决方案。实验结果表明,改进Dijkstra算法可以减少路网节点搜索范围和计算复杂度,提高用户搜索路径的实时性。     

基于优化策略的不确定数据流预测方法

为解决不确定数据流的预测问题,根据数据流高速、无限和动态不确定性的特点,在复杂人工智能预测和时间序列预测的基础上,提出一种基于优化策略的预测方法。综合考虑数据流中元组的不确定性与不确定异常性,以降低预测计算代价。同时考虑不确定的统计特性对卡尔曼滤波预测的影响,对Q和R进行异步优化估计,以形成最佳状态预测。实验结果表明,该方法的预测性能较好。     

Solving single-product economic lot-sizing problem with non-increasing setup cost,constant capacity and convex inventory cost in O(N log N) time

This paper considers an economic lot sizing model with constant capacity, non-increasing setup cost, and convex inventory cost function. Algorithms with computational time of O(N×TD_N)have been developed for solving the model, where N is the number of planning periods and TD_N is the total demand. This study partially characterizes the optimal planning structure of the model. A new efficient algorithm with computational time of O(N log N) has also been developed based on the partial optimal structure. Moreover, computational study demonstrates that the new algorithm is efficient.     

Analysis of the maximum level policy in a production-distribution system

We consider a production-distribution system, where a facility produces one commodity which is distributed to a set of retailers by a fleet of vehicles. Each retailer defines a maximum level of the inventory. The production policy, the retailers replenishment policies and the transportation policy have to be determined so as to minimize the total system cost. The overall cost is composed by fixed and variable production costs at the facility, inventory costs at both facility and retailers and routing costs. We study two different types of replenishment policies. The well-known order-up to level (OU) policy, where the quantity shipped to each retailer is such that the level of its inventory reaches the maximum level, and the maximum level (ML) policy, where the quantity shipped to each retailer is such that the inventory is not greater than the maximum level. We first show that when the transportation is outsourced, the problem with OU policy is NP-hard, whereas there exists a class of instances where the problem with ML policy can be solved in polynomial time. We also show the worst-case performance of the OU policy with respect to the more flexible ML policy. Then, we focus on the ML policy and the design of a hybrid heuristic. We also present an exact algorithm for the solution of the problem with one vehicle. Results of computational experiments carried out on small size instances show that the heuristic can produce high quality solutions in a very short amount of time. Results obtained on a large set of randomly generated problem instances are also shown, aimed at comparing the two policies.     

Negation-Limited Complexity of Parity and Inverters

In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x ₁,…,x _n and outputs ¬ x ₁,…,¬ x _n . We show that: (a) for n=2 ^r ?1, circuits computing Parity with r?1 NOT gates have size at least 6n?log?₂(n+1)?O(1), and (b) for n=2 ^r ?1, inverters with r NOT gates have size at least 8n?log?₂(n+1)?O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x ₁≥???≥x _n . For an arbitrary r, we completely determine the minimum size. It is 2n?r?2 for odd n and 2n?r?1 for even n for ?log?₂(n+1)??1≤r≤n/2, and it is ?3n/2??1 for r≥n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n?3r for ?log?₂(n+1)?≤r≤n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.     

基于复杂性科学基本概念的MAS涌现性量化研究

在MAS(Multi-Agent System)领域,面向涌现的MAS研究将MAS看成一类特殊的复杂系统,其关注点是MAS宏观层面的涌现性问题.这类研究需要借用复杂性科学研究中的一些基本概念描述、阐述MAS涌现性研究中的问题.文中着重对几个常用的基本概念及其量化研究做一概览,以深化对它们的认识,并结合这些概念及其量化研究在MAS涌现性研究中的应用特点,阐明它们对面向涌现的MAS研究的作用,以促进进一步的研究.这些概念包括复杂性、混沌边缘、自组织、涌现、适应和进化等.     

Operational state complexity of nested word automata

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The results for union and complementation differ from corresponding bounds for ordinary finite automata. For reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.