用改进的竞争Hopfield神经网络求解多边形近似问题

多边形近似是提取曲线特征点和简化曲线描述的一种重要方法.提出一种改进的Hopfield神经网络多边形近似算法,该算法利用选择拐点策略减少了搜索空间,重新定义了神经网络的能量函数,使其更能反映优化目标;引?入合并拆分搜索策略,有效帮助神经网络脱离局部最小值.实验结果表明,提出的改进算法是有效的,比其它算法如关键点检测法、竞争Hopfield神经网络、混沌Hopfield神经网络、遗传算法等具有更优的性能.     

用改进的竞争Hopfieid神经网络求解多边形近似问题

多边形近似是提取曲线特征点和简化曲线描述的一种重要方法。提出一种改进的Hopfield神经网络多边形近似算法,该算法利用选择拐点策略减少了搜索空间,重新定义了神经网络的能量函数,使其更能反映优化目标;引入合并拆分搜索策略,有效帮助神经网络脱离局部最小值。实验结果表明,提出的改进算法是有效的,比其它算法如关键点检测法、竞争Hopfield神经网络、混沌Hopfield神经网络、遗传算法等具有更优的性能。     

基于混沌神经网络的图像复原算法

文章提出了一种基于混沌神经网络的图像复原新算法。在对退化图像进行复原的过程中,针对Hopfield算法易于陷入局部极小的缺点,在Hopfield神经网络中引入暂态混沌和时变增益,充分利用混沌理论的全局搜索性能进行＂粗＂搜索,当搜索到全局最优解附近时,再利用Hopfield算法进行局部搜索。通过对图像复原后的效果进行比较,证明基于混沌神经网络方法得到的图像复原的信噪比更高,目视效果更加。     

一种混沌Hopfiele网络及其在优化计算中的应用

文章讨论了神经网络算法在约束优化问题中的应用,提出了一种混沌神经网络模型。在Hopfield网络中引入混沌机制,首先在混沌动态下搜索,然后利用HNN梯度优化搜索。对非线性函数的优化问题仿真表明算法具有很强的克服陷入局部极小能力。     

一种混沌Hopfield网络及其在优化计算中的应用

文章讨论了神经网络算法在约束优化问题中的应用,提出了一种混沌神经网络模型。在Hopfield网络中引入混沌机制,首先在混沌动态下搜索,然后利用HNN梯度优化搜索。对非线性函数的优化问题仿真表明算法具有很强的克服陷入局部极小能力。     

基于CS的Hopfield神经网络数字识别应用

介绍了布谷鸟搜索(cuckoo search, CS)和Hopfield神经网络的基本原理,研究了基于Hopfield神经网络的数字识别应用。针对Hopfield网络权值在数字识别时易陷入局部最优,提出将CS引入Hopfield神经网络的解决方法。利用CS对复杂、多峰、非线性极不可微函数的全局搜索能力,使Hopfield网络在较高噪信比的情况下仍保持较高的联想成功率,并进行了仿真。仿真结果表明,该方法识别数字的效果更佳。     

混沌神经网络在求解优化问题中的应用

本文运用GCM混沌神经网络对Hopfield神经网络在求解优化方面的问题进行了改进。通过混沌遍历,可使Hopfield网络在整个相空间进行搜索,从而避免网络在运行过程中陷入局部极小值。通过对一个对弈的实例进行实验,结果显示Hopfield网络的寻优特性获得了较大改进。     

一种基于免疫和Hopfield神经网络的多峰值优化算法

分析了免疫算法和Hopfield神经网络的优缺点，提出了一种解决多峰值函数优化问题的混合算法。Hopfield神经网络易于硬件实现，具有简单、快速的优点，但是对初始值具有依赖性以及容易陷入局部极值。免疫算法具有识别多样性的特点，但搜索效率和精度不高。将两算法结合起来，优势互补。首先用免疫算法寻优，然后对所得具有全局多样性的解进行聚类分析，所得聚类中心作为Hopfield神经网络的初始搜索点，最后利用Hopfield神经网络逐个寻优。实验表明，该算法是一种有效的求解多峰函数优化问题的方法，与免疫算法相比，搜索效率和精度都较高。     

TSP问题的瞬态混沌神经网络算法

采用具有瞬态混沌特性的神经网络(TCNN)解TSP问题。利用神经元的自抑制反馈产生混沌动态，其遍历性能和随机搜索性能有效地克服了Hopfield神经网络(HNN)极易陷入局部极小的缺陷，同时利用一时变参数控制混沌行为，使网络再经过一个短暂的倍周期倒分岔后逐渐趋于一般的Hopfield神经网络，从而收敛到一个最优或近似最优的稳定平衡点。仿真结果表明，TCNN比HNN具有更强的全局寻优能力和更高的搜索效率。     

求解柔性作业车间调度问题的新型改进Jaya算法

为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。     

Competitive Hopfield Network Combined With Estimation of Distribution for Maximum Diversity Problems

This paper presents a discrete competitive Hopfield neural network (HNN) (DCHNN) based on the estimation of distribution algorithm (EDA) for the maximum diversity problem. In order to overcome the local minimum problem of DCHNN, the idea of EDA is combined with DCHNN. Once the network is trapped in local minima, the perturbation based on EDA can generate a new starting point for DCHNN for further search. It is expected that the further search is guided to a promising area by the probability model. Thus, the proposed algorithm can escape from local minima and further search better results. The proposed algorithm is tested on 120 benchmark problems with the size ranging from 100 to 5000. Simulation results show that the proposed algorithm is better than the other improved DCHNN such as multistart DCHNN and DCHNN with random flips and is better than or competitive with metaheuristic algorithms such as tabu-search-based algorithms and greedy randomized adaptive search procedure algorithms.      

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.     

改进的基于分解的多目标进化算法求解双目标模糊柔性作业车间调度问题

针对同时考虑最大模糊完工时间和总模糊机器负载的双目标模糊柔性作业车间调度问题(BFFJSP),本文提出了一种改进的基于分解的多目标进化算法(IMOEA/D),同时最优化最大模糊完工时间和总模糊机器负载,其主要特点是:1)采用3种初始化种群的策略; 2)提出了非支配解优先策略; 3)设计了结合5种局部搜索策略的变邻域搜索; 4)提出了计数器策略预防陷入局部解.运用大量实例进行了算法策略分析和对比实验,仿真结果表明, IMOEA/D在求解BFFJSP上具有更优性能.     

Optimal sub-tree scheduling for wireless sensor networks with partial coverage

In this paper, we consider the problem of scheduling optimal sub-trees at different time intervals for wireless sensor network (WSN) communications with partial coverage. More precisely, we minimize the total power consumption of the network while taking into account time dimension and multichannel diversity where different disjoint subsets of nodes are required to be active and connected under a tree topology configuration. Optimization problems of these types may arise when designing new wireless communication protocols in order to increase network lifetime. We propose mixed integer quadratic and linear programming (resp. MIQP and MILP) models to compute optimal solutions for the problem. Subsequently, we propose Kruskal-based variable neighborhood search (VNS) and simulated annealing (SA) meta-heuristic procedures. In particular, we introduce a new embedded guided local search strategy in our VNS algorithm to further strengthen the solutions obtained. Our numerical results indicate that some of the proposed models allow to obtain optimal solutions with CPLEX in significantly less CPU time. Similarly, VNS and SA algorithms proved to be highly efficient when compared to the optimal solutions and allow to obtain near optimal solutions for large instances. In particular, VNS and guided VNS strategies allow to obtain solutions in less CPU time whilst SA methods can reach better solutions at higher CPU times. Finally, optimizing over time dimension allows one to obtain important reductions in power savings which has never been reported before in the literature.     

A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature.     

Variable neighborhood search for the linear ordering problem

Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is coupled with a short-term tabu search for improved outcomes. Our extensive experimentation with both real and random instances shows that the proposed procedure competes with the best-known algorithms in terms of solution quality, and has reasonable computing-time requirements.Variable neighborhood search (VNS) is a metaheuristic method that has recently been shown to yield promising outcomes for solving combinatorial optimization problems. Based on a systematic change of neighborhood in a local search procedure, VNS uses both deterministic and random strategies in search for the global optimum.In this paper, we present a VNS implementation designed to find high quality solutions for the NP-hard LOP, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input–output tables in economics. Our implementation incorporates innovative mechanisms to include memory structures within the VNS methodology. Moreover we study the hybridization with other methodologies such as tabu search.     

A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this paper, we consider minimizing the total weighted earliness and tardiness with a restrictive common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this paper, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature.     

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。     

A population-based variable neighborhood search for the single machine total weighted tardiness problem

This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of all jobs. This problem is known to be strongly NP-hard, and thus provides a challenging area for metaheuristics. A population-based variable neighborhood search (PVNS) algorithm is developed to solve it. This algorithm differs from the basic variable neighborhood search (VNS). First, the PVNS consists of a number of iterations of the basic VNS, and in each iteration a population of solutions is used to simultaneously generate multiple trial solutions in a neighborhood so as to improve the search diversification. Second, the PVNS adopts a combination of path-relinking, variable depth search and tabu search to act as the local search procedure so as to improve the search intensification. Computational experiments show that the proposed PVNS algorithm can obtain the optimal or best known solutions within a reasonable computation time for all standard benchmark problem instances from the literature.     

Packing unit spheres into the smallest sphere using VNS and NLP

This paper addresses the NP hard optimization problem of packing identical spheres of unit radii into the smallest sphere (PSS). It models PSS as a non-linear program (NLP) and approximately solves it using a hybrid heuristic which couples a variable neighborhood search (VNS) with a local search (LS). VNS serves as the diversification mechanism whereas LS acts as the intensification one. VNS investigates the neighborhood of a feasible local minimum u in search for the global minimum, where neighboring solutions are obtained by shaking one or more spheres of u and the size of the neighborhood is varied by changing the number of shaken spheres, the distance and the direction each sphere is moved. LS intensifies the search around a solution u by subjecting its neighbors to a sequential quadratic algorithm with non-monotone line search (as the NLP solver). The computational investigation highlights the role of LS and VNS in identifying (near) global optima, studies their sensitivity to initial solutions, and shows that the proposed hybrid heuristic provides more precise results than existing approaches. Most importantly, it provides computational evidence that the multiple-start strategy of non-linear programming solvers is not sufficient to solve PSS. Finally, it gives new upper bounds for 29 out of 48 benchmark instances of PSS.