Guided restarting local search for production planning

Planning problems can be solved with a large variety of different approaches, and a significant amount of work has been devoted to the automation of planning processes using different kinds of methods. This paper focuses on the use of specific local search algorithms for real-world production planning based on experiments with real-world data, and presents an adapted local search guided by evolutionary metaheuristics. To make algorithms efficient, many specifics need to be considered and included in the problem solving. We demonstrate that the use of specialized local searches can significantly improve the convergence and efficiency of the algorithm. The paper also includes an experimental study of the efficiency of two memetic algorithms, and presents a real-world software implementation for the production planning.     

Evaluating a local genetic algorithm as context-independent local search operator for metaheuristics

Local genetic algorithms have been designed with the aim of providing effective intensification. One of their most outstanding features is that they may help classical local search-based metaheuristics to improve their behavior. This paper focuses on experimentally investigating the role of a recent approach, the binary-coded local genetic algorithm (BLGA), as context-independent local search operator for three local search-based metaheuristics: random multi-start local search, iterated local search, and variable neighborhood search. These general-purpose models treat the objective function as a black box, allowing the search process to be context-independent. The results show that BLGA may provide an effective and efficient intensification, not only allowing these three metaheuristics to be enhanced, but also predicting successful applications in other local search-based algorithms. In addition, the empirical results reported here reveal relevant insights on the behavior of classical local search methods when they are performed as context-independent optimizers in these three well-known metaheuristics.     

Two-level iterated local search for WDM network design problem with traffic grooming

Two important problems arise in WDM network planning: network design to minimize the operation cost and traffic grooming to maximize the usage of the high capacity channels. In practice, however, these two problems are usually simultaneously tackled, denoted as the network design problem with traffic grooming (NDG). In this paper, a mathematical formulation of the NDG problem is first presented. Then, this paper proposes a new metaheuristic algorithm based on two-level iterated local search (TL-ILS) to solve the NDG problem, where a novel tree search based neighborhood construction and a fast evaluation method are proposed, which not only enhance the algorithm's search efficiency but also provide a new perspective in designing neighborhoods for problems with graph structures. Our algorithm is tested on a set of benchmarks generated according to real application scenarios. We also propose a strengthening formulation of the original problem and a method to obtain the lower bound of the NDG problem. Computational results in comparison with the commercial software CPLEX and the lower bounds show the effectiveness of the proposed algorithm.     

多智能体布谷鸟算法的网络计划资源均衡优化

网络计划资源均衡属于组合优化问题,为了能快速有效地求解此类问题,提出了一种多智能体布谷鸟算法。针对标准布谷鸟算法缺乏信息共享的缺陷,将多智能体系统引入布谷鸟算法中。多智能体的邻域竞争合作算子实现智能体间信息的交流,加快算法收敛速度;变异算子扩大搜索范围增加种群多样性;自学习算子提高局部寻优的能力;布谷鸟算法的Levy飞行进化机制能有效地跳出局部最优实现全局收敛。实例仿真结果证实了,与其他算法相比多智能体布谷鸟算法能更有效地求解网络计划资源均衡优化问题。     

Chaotic local search algorithm

The steepest descent search algorithm is modified in conjunction withchaos to solve the optimization problem of an unstructured search space. The problem is that given only the gradient information of the quality function at the present configuration,X(t), we must find the value of a configuration vector that minimizes the quality function. The proposed algorithm starts basically from the steepest descent search technique but at the prescribed points, i.e., local minimum points, the chaotic jump is performed by the dynamics of a chaotic neuron. Chaotic motions are mainly caused because the Gaussian function has a hysteresis as a refractoriness. An adaptation mechanism to adjust the size of the chaotic jump is also given. In order to enhance the probability of finding the global minimum, a parallel search strategy is developed. The validity of the proposed method is verified in simulation examples of the function minimization problem and the motion planning problem of a mobile robot. This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1996     

IGP/MPLS混合的IP网络不确定流量规划方法

随着IP网络的迅速发展,网络的业务量越来越呈不确定性和不可预测性。针对此问题,提出了以软管模型为基础的不确定业务量模型下的IGP/MPLS混合IP流量规划问题的混合整数规划(MIP)模型,并将该模型分解成权重设计子问题和流量分配子问题进行求解。实验结果表明,该方法能在标签交换路径(LSP)较少的情况下达到较理想的优化效果。     

CS算法优化BP神经网络的短时交通流量预测

为了提高短时交通流量的预测精度,提出一种布谷鸟搜索算法优化BP神经网络参数的短时交通流量预测模型（CS-BPNN）。基于混沌理论对短时交通流量时间序列进行相空间重构,将重构后的时间序列输入到BP神经网络进行学习,采用布谷鸟搜索算法找到BP神经网络最优参数,建立短时交通流量预测模型,通过具体实例对CS-BPNN性能进行测试。仿真结果表明,相对于对比模型,CS-BPNN提高了短时交通流量的预测精度,更加准确反映了短时交通流量的变化趋势。     

基于深度邻域搜索PSO 算法的装配序列优化问题

针对产品结构特征建立几何约束矩阵, 以最大化满足几何约束条件装配次数和最小化装配方向改变次数为目标, 研究产品装配序列优化问题. 利用值变换的粒子位置和速度更新规则, 基于具有随机性启发式算法产生初始种群, 提出一种带有深度邻域搜索改进策略的粒子群算法解决装配序列问题. 通过装配实例验证了所提出算法的性能并对装配序列质量进行了评价, 所得结果表明了该算法在解决装配序列优化问题上的有效性与稳定性.

     

Models for robust tactical planning in multi-stage production systems with uncertain demands

We consider the problem of designing robust tactical production plans, in a multi-stage production system, when the periodic demands of the finished products are uncertain. First, we discuss the concept of robustness in tactical production planning and how we intend to approach it. We then present and discuss three models to generate robust tactical plans when the finished-product demands are stochastic with known distributions. In particular, we discuss plans produced, respectively, by a two-stage stochastic planning model, by a robust stochastic optimization planning model, and by an equivalent deterministic planning model which integrates the variability of the finished-product demands. The third model uses finished-product average demands as minimal requirements to satisfy, and seeks to offset the effect of demand variability through the use of planned capacity cushion levels at each stage of the production system. An experimental study is carried out to compare the performances of the plans produced by the three models to determine how each one achieves robustness. The main result is that the proposed robust deterministic model produces plans that achieve better trade-offs between minimum average cost and minimum cost variability. Moreover, the required computational time and space are by far less important in the proposed robust deterministic model compared to the two others.     

Robust network planning in nonuniform traffic scenarios

Robustness to the environmental variations is an important feature of any reliable communication network. This paper reports on a network theory approach to the design of such networks where the environmental changes are traffic fluctuations, topology modifications, and changes in the source of external traffic. Motivated by the definition of betweenness centrality in network science, we introduce the notion of traffic-aware betweenness (TAB) for data networks, where usually an explicit (or implicit) traffic matrix governs the distribution of external traffic into the network. We use the average normalized traffic-aware betweenness, which is referred to as traffic-aware network criticality (TANC), as our main metric to quantify the robustness of a network. We show that TANC is directly related to some important network performance metrics, such as average network utilization and average network cost. We prove that TANC is a linear function of end-to-end effective resistances of the graph. As a result, TANC is a convex function of link weights and can be minimized using convex optimization techniques. We use semi-definite programming method to study the properties of the optimization problem and derive useful results to be employed for robust network planning purposes.     

Medical image reconstruction using a multi-objective genetic local search algorithm

Image reconstruction from projections is a key problem in medical image analysis. In this paper, we cast image reconstruction from projections as a multi-objective problem. It is essential to choose some proper objective functions of the problem. We choose the square error, smoothness of the reconstructed image, and the maximum entropy as our objective functions of the problem. Then we introduce a hybrid algorithm comprising of multi-objective genetic and local search algorithms to reconstruct the image. Our algorithm has remarkable global performance. Our experiments show that we can get different results when we give different weights to different objective functions. We can also control the noise by giving different weights on different objective function. At the same time, we can adjust the parameter to let it have good local performance. Though the computation demands of the hybrid algorithm tends to be larger because of the random search of the GA, it is really a common feature of the global optimization method. Our results show that the hybrid algorithm is a more effective than the conventional method. We think our method is very promising for the medical imaging field.     

结合粗糙集和禁忌搜索的网络流量特征选择

针对网络流量特征属性的优化选择问题,提出了一种结合粗糙集和禁忌搜索的网络流量特征选择方法(RS-TS).该方法通过粗糙集算法对网络流量特征属性进行约简,将所得到的特征子集作为禁忌搜索的初始解,并利用禁忌搜索得到最优特征子集.实验验证RS-TS方法优于基于GA的特征选择方法和基于IG的特征选择方法,能够有效地去除网络流量的冗余特征属性,提高网络流量分类精度.     

求解k中间点问题的新局部搜索算法

为有效求解大规模k中间点问题,利用适应度距离相关性方法分析,发现该问题局部最优解的适应度与其到全局最优解的距离无太大关系,且多个局部最优解求交所得子集以极大概率包含全局最优解中的元素,进而提出一种基于求交操作的k中间点问题局部搜索算法。实验结果表明该算法在求解质量上与目前已知算法相比有较大改进。     

Limited-Damage A*: A path search algorithm that considers damage as a feasibility criterion

Pathfinding algorithms used in todays computer games consider the path length or a similar criterion as the only measure of optimality. However, these games usually involve opposing parties, whose agents can inflict damage on those of the others. Therefore, the shortest path in such games may not always be the safest one. Consequently, a new suboptimal offline path search algorithm based on the A¹ algorithm was developed, which takes the threat zones in the game map into consideration. Given an upper limit as the tolerable amount of damage for an agent, this algorithm searches for the shortest path from a starting location to a destination, where the agent may suffer damage less than or equal to the specified limit. Due to its behavior, the algorithm is called Limited-Damage A¹ (LDA¹). Performance of LDA¹ was tested in randomly-generated maze-like grid-based environments of varying sizes, and in hand-crafted fully-observable environments, in which 8-way movement is utilized. Results obtained from LDA¹ are compared with those obtained from Multiobjective A¹ (MOA¹), which is a complete and optimal algorithm that yields exact (best) solutions for every case. LDA¹ was found to perform much faster than MOA¹, yielding acceptable sub-optimality in path length.     

Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm

The Vehicle Routing Problem (VRP) has been thoroughly studied in the last decades. However, the main focus has been on the deterministic version where customer demands are fixed and known in advance. Uncertainty in demand has not received enough consideration. When demands are uncertain, several problems arise in the VRP. For example, there might be unmet customers’ demands, which eventually lead to profit loss. A reliable plan and set of routes, after solving the VRP, can significantly reduce the unmet demand costs, helping in obtaining customer satisfaction. This paper investigates a variant of an uncertain VRP in which the customers’ demands are supposed to be uncertain with unknown distributions. An advanced Particle Swarm Optimization (PSO) algorithm has been proposed to solve such a VRP. A novel decoding scheme has also been developed to increase the PSO efficiency. Comprehensive computational experiments, along with comparisons with other existing algorithms, have been provided to validate the proposed algorithms.     

Satisfying demands in a multicellular network: A universal power allocation algorithm

Power allocation to satisfy user demands, in the presence of large number of interferers (in a multicellular network), is a challenging task. Further, the power to be allocated depends upon the system architecture, for example upon components like coding, modulation, transmit precoder, rate allocation algorithms, available knowledge of the interfering channels, etc. This calls for an algorithm via which each base station in the network can simultaneously allocate power to their respective users so as to meet their demands (whenever they are within the achievable limits), using whatever information is available of the other users. The goal of our research is to propose one such algorithm which in fact is universal: the proposed algorithm works from a fully co-operative setting to almost no co-operation and or for any configuration of modulation, rate allocation, etc. schemes. The algorithm asymptotically satisfies the user demands, running simultaneously and independently within a given total power budget at each base station. Further, it requires minimal information to achieve this: every base station needs to know its own users demands, its total power constraint and the transmission rates allocated to its users in every time slot. We formulate the power allocation problem in a system specific game theoretic setting, define system specific capacity region and analyze the proposed algorithm using ordinary differential equation (ODE) framework. Simulations further confirm the effectiveness of the proposed algorithm. We also demonstrate the tracking abilities of the algorithm.     

基于非线性算法的网络业务流量预测

基于递归最小二乘支持向量机,提出了一种网络业务流量非线性预测算法。通过最小二乘支持量机首先将原始的网络流量数据映射到一个高维空间中,进而在这个高维空间中对流量数据进行预测,使得在低维空间中非线性预测转化为高维空间中的线性预测,提高了预测性能。仿真结果表明,预测误差能够维持在5%以内。     

地标导向的启发式路径规划算法

为提高大规模交通网络路径规划算法的查询效率,以A*算法为基础,提出一种地标导向的启发式算法。在预处理中将重要的顶点和边选为地标,在点对点寻径时使用地标作为启发式函数的启发参数,并进行分段计算。实验结果表明,此算法在处理长距离的路径规划问题时有较高的查询效率和更合理的计算结果。     

Optimizing urban traffic light scheduling problem using harmony search with ensemble of local search

This study addresses urban traffic light scheduling problem (UTLSP). A centralized model is employed to describe the urban traffic light control problem in a scheduling framework. In the proposed model, the concepts of cycles, splits, and offsets are not adopted, making UTLSP fall in the class of model-based optimization problems, where each traffic light is assigned in a real-time manner by the network controller. The objective is to minimize the network-wise total delay time in a given finite horizon. A swarm intelligent algorithm, namely discrete harmony search (DHS), is proposed to solve the UTLSP. In the DHS, a novel new solution generation strategy is proposed to improve the algorithm’s performance. Three local search operators with different structures are proposed based on the feature of UTLSP to improve the performance of DHS in local space. An ensemble of local search methods is proposed to integrate different neighbourhood structures. Extensive computational experiments are carried out using the traffic data from partial traffic network in Singapore. The DHS algorithm with and without local search operators and ensemble is evaluated and tested. The comparisons and discussions verify the effectiveness of DHS algorithms with local search operators and ensemble for solving UTLSP.     

Genetic algorithm with iterated local search for solving a location-routing problem

This paper deals with a location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. We seek for new methods to make location and routing decisions simultaneously and efficiently. For that purpose, we describe a genetic algorithm (GA) combined with an iterative local search (ILS). The main idea behind our hybridization is to improve the solutions generated by the GA using a ILS to intensify the search space. Numerical experiments show that our hybrid algorithm improves, for all instances, the best known solutions previously obtained by the tabu search heuristic.