Statistical and computational tradeoff in genetic algorithm-based estimation

When a genetic algorithm (GA) is employed in a statistical problem, the result is affected by both variability due to sampling and the stochastic elements of algorithm. Both of these components should be controlled in order to obtain reliable results. In the present work we analyze parametric estimation problems tackled by GAs, and pursue two objectives: the first one is related to a formal variability analysis of final estimates, showing that it can be easily decomposed in the two sources of variability. In the second one we introduce a framework of GA estimation with fixed computational resources, which is a form of statistical and the computational tradeoff question, crucial in recent problems. In this situation the result should be optimal from both the statistical and computational point of view, considering the two sources of variability and the constraints on resources. Simulation studies will be presented for illustrating the proposed method and the statistical and computational tradeoff question.     

An improved approximation algorithm for uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the classical facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. The UFLWP problem has been effectively used to model the facility location problem with outliers. Three constant approximation algorithms have been obtained (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001; Jain et al. in J. ACM 50(6):795–824, 2003; Xu and Xu in Inf. Process. Lett. 94(3):119–123, 2005), and the best known performance ratio is 2. The only known hardness result is a 1.463-inapproximability result inherited from the uncapacitated facility location problem (Guha and Khuller in J. Algorithms 31(1):228–248, 1999). In this paper, We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm significantly reduces the gap between known performance ratio and the inapproximability result. Our algorithm first enhances the primal-dual method for the UFLWP problem (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001) so that outliers can be recognized more efficiently, and then applies a local search heuristic (Charikar and Guha in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pp. 378–388, 1999) to further reduce the cost for serving those non-rejected clients. Our algorithm is simple and can be easily implemented. The research of this work was supported in part by NSF through CAREER award CCF-0546509 and grant IIS-0713489. A preliminary version of this paper appeared in the Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON’05).     

经济领域的软法研究述评

随着软法研究在国内的兴起,众多经济法学者开始关注社会经济生活中存在的软法现象,包括经济领域软法兴起的背景、理论基础、特征、渊源和运行.此外,尚有不少学者将软法理论“嵌入”各类社会经济生活中,洞察具体经济领域的软法现象,梳理出一系列丰硕的研究成果,特别是国际经济、宏观调控、市场规制三领域.同时,软法研究者自身也注意检讨软法现象自身存在的先天不足,并寻求完善软法的合理路径,最大限度发挥软法的效用.由此,国内从事经济领域软法方面的学者,要随时关注社会经济生活出现的新情况,力求“竭泽而渔”,盘点国内外软法、经济领域软法方面的已有研究成果并加以消化,认真总结国内外经济软法理论的研究状况,以先进的理论范式与研究方法为指导展开研究,为后来的研究者提供有益的借鉴.     

基于求解TSP问题的双向扩展差额算法

旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.     

P2P应用层数据流量优化

为减少对主干网络带宽的消耗,提出了一套数据流量优化方法。首先通过把Peer间的邻居关系明确划分为物理邻居关系和逻辑邻居关系,并用探路者算法来发现Peer的物理邻居,实现拓扑匹配;然后在数据调度算法中,引入通报/退避机制,把大部分数据传输控制在城域网络内部。通过建立模拟仿真环境进行实验分析,证实了该方法可以减少90%以上的网络数据流量。     

Pricing decisions in a multi-criteria setting for product recovery facilities

Unpredictability in the arrival time and quantity of discarded products at product recovery facilities (PRFs) and varying demand for recovered components contribute to the volatility in their inventory levels. Achieving profit under such capricious inventory levels and stringent environmental legislations remains a challenge to many PRFs. This paper presents a multi-criteria decision model to determine a pricing policy that can simultaneously address two issues: stabilize inventory fluctuations and boost profits. The model considers that PRFs passively accepts discarded products as well as acquires them proactively if necessary. Under a multi-criteria setting, the current work determines prices of reusable and recyclable components to maximize revenue and minimize product recovery costs. A genetic algorithm is employed to solve the multi-criteria decision making problem. Sensitivity analysis is performed to investigate the effect of sorting yield, disassembly yield, and reusable component yield on the profits, prices, inventory levels, and disposal quantities.     

梯度相关的无线传感器网络成簇路由协议

分析了梯度和成簇无线传感器网络路由协议,确定了协议中存在的缺陷,设计了一种基于梯度的高效节能成簇路由协议(GBCRP)。采用基于跳数的梯度建立、能量相关的成簇算法、关键节点转发和功率自适应的簇头路由等技术,解决了无线传感器网络的节点能耗和路由失败而导致的数据传输可靠性问题。仿真实验表明,该协议有效地延长了网络的生命周期。针对不同密度的传感器节点,网络生命周期具有很好的稳定性,同时该协议也具有较好的可靠性保障。     

鱼类吞噬细胞和吞噬作用的研究进展

对鱼类吞噬细胞的分离鉴定、吞噬过程等方面的国内外研究成果进行了综述,并介绍了鱼类细胞吞噬作用的机理以及各种因子对吞噬作用的调节,对今后的研究方向进行了展望.     

实时调度算法研究

对实时调度进行了讨论：研究了单处理器下的经典调度算法：单调速率调度、最早死线调度和最短空闲时间优先调度;分析了多处理器系统中的典型调度算法：对分布式系统中的两种调度算法：广义单调速率调度和分布式风车调度做了简要论述;指出实时调度研究策略方向。     

《诗经》中的鱼文化

《诗经》中出现鱼字和鱼名的地方约有三十余处,涉及的鱼名有鲂、鳢、鲔等十二种;《诗经》中咏鱼诗篇的表现手法有实叙、比拟、象征等多种,也就是古人常说的"赋、比、兴"。并推断出《诗经》时代的捕鱼方法,有竿钓、网捕、笼捕、设池围捕等。文章最后一节,归纳出鱼在《诗经》时代人们生活中具有用于祭礼、烹制佳肴,表示兴盛,作为象征,取以饰物等多方面的作用。