基于晶格的人工内分泌系统模型及在多机器人系统中的应用

为了解决多机器人系统分布式控制问题,借鉴人体内分泌系统研究的理论成果,提出基于晶格的人工内分泌系统模型.该模型以环境晶格化为基础,以细胞智能化为依托,以累加激素为纽带,以靶细胞为导向,能够适应外环境的持续变化,保持内环境的相对稳定,充分体现人体内分泌系统的自组织和自修复特性.实验结果表明,无需复杂的集中控制策略,基于该...     

基于单调邻域粗糙集的特征基因提取

为了避免连续数据离散化处理时造成的信息损失,降低样本属性邻域求解的复杂度,提高特征基因提取的效率。该文在单调度量空间上,提出了一种基于单调邻域粗糙集的特征基因提取方法。并在两个标准的基因表达数据上进行了实验,结果证明该方法是有效可行的。     

基于冯•诺依曼邻域结构的人工鱼群算法

提出了一种基于冯¢ 诺依曼邻域结构的人工鱼群算法. 每条人工鱼只和与自己相连的上下左右的人工鱼进行信息交换, 从而减少了计算邻域中心位置和极值位置的计算量, 有效地维持了种群的多样性, 加快了算法的运行速度. 在觅食行为中, 人工鱼通过直接移动到搜索到的较好位置, 来加快搜索速度. 在随机游动行为中, 人工鱼以小半径进行搜索, 因此算法的优化精度得到了提高. 采用动态调整人工鱼视野和步长的方法, 较好地平衡了全局搜索能力和局部搜索能力. 仿真和实例计算结果表明, 该算法具有更好的优化性能.     

Heuristics for the multi-period orienteering problem with multiple time windows

We present the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering problem (OP) and team orienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application. The problem itself comes from a real industrial case. Specific route duration constraints result in a route feasibility subproblem. We propose an exact algorithm for this subproblem, and we embed it in a variable neighborhood search method to solve the whole routing problem. We then provide experimental results for this method. We compare them to a commercial solver. We also adapt our method to standard benchmark OP and TOP instances, and provide comparative tables with state-of-the-art algorithms.     

The distributed permutation flowshop scheduling problem

This paper studies a new generalization of the regular permutation flowshop scheduling problem (PFSP) referred to as the distributed permutation flowshop scheduling problem or DPFSP. Under this generalization, we assume that there are a total of F identical factories or shops, each one with m machines disposed in series. A set of n available jobs have to be distributed among the F factories and then a processing sequence has to be derived for the jobs assigned to each factory. The optimization criterion is the minimization of the maximum completion time or makespan among the factories. This production setting is necessary in today's decentralized and globalized economy where several production centers might be available for a firm. We characterize the DPFSP and propose six different alternative mixed integer linear programming (MILP) models that are carefully and statistically analyzed for performance. We also propose two simple factory assignment rules together with 14 heuristics based on dispatching rules, effective constructive heuristics and variable neighborhood descent methods. A comprehensive computational and statistical analysis is conducted in order to analyze the performance of the proposed methods.     

基于动态二进制搜索算法的改进防碰撞算法

该文在动态二进制搜索算法的基础上提出了一种新的防碰撞算法,该算法充分利用已得到的冲突信息,有效减小判断过程中数据的传输量。通过对新算法的分析,可知本算法相对于动态二进制搜索算法有明显的优势。     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports

The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15%. Moreover, improvements of up to 41% can be achieved for some test instances.     

Graph searching with advice

Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70–84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of bits of advice   of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. Moreover, the clearing of the graph must be performed using the optimal number of searchers, i.e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. We show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is Θ(nlogn)$\Theta (nlogn)$, where n$n$ is the number of nodes of the network. More precisely, we first provide a labelling of the vertices of any graph G$G$, using a total of O(nlogn)$O(nlogn)$ bits, and a protocol using this labelling that enables the optimal number of searchers to clear G$G$ in a monotone connected distributed way. Then, we show that this number of bits of advice is optimal: any distributed protocol requires Ω(nlogn)$\Omega (nlogn)$ bits of advice to clear a network in a monotone connected way, using an optimal number of searchers.     

A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems

This paper presents a novel discrete differential evolution (DDE) algorithm for solving the no-wait flow shop scheduling problems with makespan and maximum tardiness criteria. First, the individuals in the DDE algorithm are represented as discrete job permutations, and new mutation and crossover operators are developed based on this representation. Second, an elaborate one-to-one selection operator is designed by taking into account the domination status of a trial individual with its counterpart target individual as well as an archive set of the non-dominated solutions found so far. Third, a simple but effective local search algorithm is developed to incorporate into the DDE algorithm to stress the balance between global exploration and local exploitation. In addition, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is shown that the proposed DDE algorithm is superior to a recently published hybrid differential evolution (HDE) algorithm [Qian B, Wang L, Huang DX, Wang WL, Wang X. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research 2009;36(1):209–33] and the well-known multi-objective genetic local search algorithm (IMMOGLS2) [Ishibuchi H, Yoshida I, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 2003;7(2):204–23] in terms of searching quality, diversity level, robustness and efficiency. Moreover, the effectiveness of incorporating the local search into the DDE algorithm is also investigated.