基于和声搜索和模拟退火的混合算法解决TSP问题

和声搜索是一种新的启发式优化算法,算法模拟了音乐创作中乐师们凭借自己的记忆,通过反复地调整乐队中各乐器的音调,最终能达到一个美妙的和声状态的过程.针对和声搜索算法容易陷入局部最优的缺陷,将其与模拟退火算法结合,得到了两种混合算法.实验表明混合算法针对TSP问题具有较高的求解质量.     

New neural network algorithm for image reconstruction from fan-beam projections

Neural networks have some applications in computerized tomography, in particular to reconstruct an image from projections. The presented paper describes a new practical approach to the reconstruction problem using a Hopfield-type neural network. The methodology of this reconstruction algorithm resembles a transformation formula—the so-called ρ-filtered layergram method. The method proposed in this work is adapted for discrete fan beam projections, already used in practice. Performed computer simulations show that the neural network reconstruction algorithm designed to work in this way outperforms conventional methods in obtained image quality, and in perspective of hardware implementation in the speed of the reconstruction process.     

Guided Local Search for Solving SAT and Weighted MAX-SAT Problems

In this paper, we show how Guided Local Search (GLS) can be applied to the SAT problem and show how the resulting algorithm can be naturally extended to solve the weighted MAX-SAT problem. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real-life problems, such as the traveling salesman problem, BT"s workforce scheduling problem, the radio link frequency assignment problem, and the vehicle routing problem. We present empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compare them with the results of other local search algorithms for the SAT problem.     

求解多车型校车路径问题的混合集合划分的GRASP算法

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性。     

组合优化问题反问题的研究进展

本文重点介绍了组合优化问题反问题的研究进展。具体内容包括：线性规划问题反问题、最短路问题反问题、最小费用流问题反问题和网络容量扩充问题反问题的提出背景、研究成果、应用前景及一些可能的研究方向。     

动态电阻抗图象重建的正则化方法

电阻抗图象重建是一个严重病态的反问题,特别是当重建模型的有限单元增大时,重建图象会严差,甚至发散,提出一种全新的基于空间滤波理论的正则化方法,它不依赖于阻抗分布的先验估计,因此它比最大后验（MAP）正则比方法易于实现,而且计算机模拟实验结果表明,利用这种新的正则化方法重建的动态阻抗图象质量好于Tikhonov正则化方法。     

Sequential search and its application to vehicle-routing problems

Local search is the most frequently used heuristic technique for solving combinatorial optimization problems. It is also the basis for modern metaheuristics, like, e.g., Tabu Search, and Variable Neighborhood Search. The paper introduces sequential search as a generic technique for the efficient exploration of local-search neighborhoods. One of its key concepts is the systematic decomposition of moves, which allows pruning within local search based on associated partial gains. The application of theoretical concepts to several well-known neighborhoods of the vehicle-routing problem (VRP) is demonstrated. Computational tests show substantial speedup factors, e.g., up to 10 000 for the 3-opt* neighborhood. This underlines the superiority of sequential search over straightforward techniques in the VRP context.     

A novel grouping harmony search algorithm for the multiple-type access node location problem

In this paper we present a novel grouping harmony search algorithm for the Access Node Location Problem (ANLP) with different types of concentrators. The ANLP is a NP-hard problem where a set of distributed terminals, with distinct rate demands, must be assigned to a variable number of concentrators subject to capacity constraints. We consider the possibility of choosing between different concentrator models is given in order to provide service demand at different cost. The ANLP is relevant in communication networks design, and has been considered before within the design of MPLS networks, for example. The approach we propose to tackle the ANLP problem consists of a hybrid Grouping Harmony Search (GHS) algorithm with a local search method and a technique for repairing unfeasible solutions. Moreover, the presented scheme also includes the adaptation of the GHS to a differential scheme, where each proposed harmony is obtained from the same harmony in the previous iteration. This differential scheme is perfectly adapted to the specifications of the ANLP problem, as it utilizes the grouping concept based on the proximity between nodes, instead of being only based on the grouping concept. This allows for a higher efficiency on the searching process of the algorithm. Extensive Monte Carlo simulations in synthetic instances show that this proposal provides faster convergence rate, less computational complexity and better statistical performance than alternative algorithms for the ANLP, such as grouping genetic algorithms, specially when the size of the scenario increases. We also include practical results for the application of GHS to a real wireless network deployment problem in Bizkaia, northern Spain.     

Local search with constraint propagation and conflict-based heuristics

Search algorithms for solving csp (Constraint Satisfaction Problems) usually fall into one of two main families: local search algorithms and systematic algorithms. Both families have their advantages. Designing hybrid approaches seems promising since those advantages may be combined into a single approach. In this paper, we present a new hybrid technique. It performs a local search over partial assignments instead of complete assignments, and uses filtering techniques and conflict-based techniques to efficiently guide the search. This new technique benefits from both classical approaches: a priori pruning of the search space from filtering-based search and possible repair of early mistakes from local search. We focus on a specific version of this technique: tabu decision-repair. Experiments done on open-shop scheduling problems show that our approach competes well with the best highly specialized algorithms.     

废弃物处理站选址问题的和谐搜索算法

近年来,随着人们环保意识的增强和环保法规力度的加大,逆向物流逐渐受到人们的关注与重视。废弃物处理站的选址问题(end-of-life items disposal facilities' location prohlem, EIDFI_P)是逆向物流研究领域的关键问题,该问题能否有效解决直接关系到人们的日常生活环境能否得到有效改善。针对文献中的具有多个目标的EIDFLP,首先将问题转化为单目标问题,之后采用一种新颖的和谐搜索优化算法(harmony search algorithm, HSA)对问题进行了求解。计算结果显示:1)本算法的最优解与文献中的最优解相同;2)本算法的计算时间明显少于文献中算法的计算时间;3)原文献中的一个解存在错误之处。     

无线传感网中基于和声搜索和局部搜索的节点定位问题的研究

准确的节点定位信息对于无线传感网中收集重要数据是必须的。基于有噪声的距离相关测量值对网络中所有未知定位节点的位置进行评估,该评估通常由于网络可能不是唯一可定位的事实而进一步加重。为了有效地处理该问题,提出一种新的双目标定位方法,该方法基于和声搜索算法和局部搜索过程的组合。此外还利用基于连通性的几何约束来限制传感器节点可定位的区域。在标准化定位误差和三种多目标质量指标方面,所提方法用一种基于Pareto存档进化策略的元启发式定位方案,在不同网络配置中进行测试和比较。结果表明所提方案获得相当不错的精度,并在大多数情况下优于Pareto存档进化策略。     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

A Gauss–Newton approach to joint image registration and intensity correction

We develop a new efficient numerical methodology for automated simultaneous registration and intensity correction of images. The approach separates the intensity correction term from the images being registered in a regularized expression. Our formulation is consistent with the existing non-parametric image registration techniques, however, an extra additive intensity correction term is carried throughout. An objective functional is formed for which the corresponding Hessian and Jacobian is computed and employed in a multi-level Gauss–Newton minimization approach. In this paper, our experiments are based on elastic regularization on the transformation and total variation on the intensity correction. Validations on dynamic contrast enhanced MR abdominal images for both real and simulated data verified the efficacy of the model.     

Pick sequencing optimization problem in the rotary rack S／R system

The problem of pick sequencing in the rotary, rack S/R system (PPS-RRS) is investigated with the objective of mininizing the execution rime. The rotary rack S/R system consists of one S/R machine and multiple levels of carousals that can rotate independently in bi-directions. The routing policy, namely the decision on the storage or retrieval sequence, donfinates the efficiency and the throughput for such S/R systems, due to the complicated relationship between all levels of carousels and the S/R machine. For the purpose of optimizing the PPS-RRS, a computational model is developed in temps of execution time for picking multiple items in one trip. Characteristics of the PPS-RRS are analyzed and a local search heuristic based on a newly proposed neighborhood is presented. Integrated with the proposed local search procedure a new hybrid genetic algorithm is developed. Experimental results demonstrate the structure characteristics of good sequence and the efficiency and effectiveness of the proposed sequencing algorithms.     

A wave-splitting based optimization approach to multi-dimensional time-domain electromagnetic inverse problems

An optimization approach to a multi-dimensional electromagnetic inverse problem in the time domain is considered. Wave-splitting is integrated in the optimization algorithm. An analysis based on energy estimates is given to show that the wave-splitting provides the best linear combination of the fields for use in this type of inverse problem. The permittivity, permeability and conductivity are reconstructed by minimizing an objective functional. An explicit expression for the gradient of the objective functional is derived by introducing some auxiliary functions and using the Gauss theorem. The parameters are reconstructed by an iterative conjugate gradient algorithm. Numerical results are presented.