Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.     

一种带局部搜索功能的入侵杂草优化算法

为了改善入侵杂草优化算法解的质量,提出一种带局部搜索功能的入侵杂草优化算法。该算法按照一定概率对每代产生的最优个体执行球体局部搜索算子或Logistic映射搜索算子,在最优个体周围进行精细搜索,并用搜索到的较优个体代替最优个体,提高了算法的局部搜索能力和优化精度。并对7个测试函数进行了仿真实验,结果表明:该算法具有较高的优化性能。     

Evolutionary local search for the edge-biconnectivity augmentation problem

This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph edge-biconnected. An application is the extension of an existing communication network to become robust against single link-failures. An evolutionary algorithm (EA) is presented which includes an effective preprocessing of the problem data and a local improvement procedure that is applied during initialization, recombination, and mutation. In this way, the EA searches the space of feasible, locally optimal solutions only. The variation operators were designed with particular emphasis on low computational effort and strong locality. Empirical results indicate the superiority of the new approach over two previous heuristic methods.     

Embedded local search approaches for routing optimization

This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.     

Evolutionary pattern search algorithms for unconstrained andlinearly constrained optimization

We describe a convergence theory for evolutionary pattern search algorithms (EPSA) on a broad class of unconstrained and linearly constrained problems. EPSA adaptively modify the step size of the mutation operator in response to the success of previous optimization steps. The design of EPSA is inspired by recent analyzes of pattern search methods. Our analysis significantly extends the previous convergence theory for EPSA. Our analysis applies to a broader class of EPSA and it applies to problems that are nonsmooth, have unbounded objective functions, and are linearly constrained. Further, we describe a modest change to the algorithmic framework of EPSA for which a nonprobabilistic convergence theory applies. These analyses are also noteworthy because they are considerably simpler than previous analyses of EPSA     

基于局部并行搜索的分布式约束优化算法框架

针对当前局部搜索算法在求解大规模、高密度的分布式约束优化问题（DCOP）时,求解困难且难以跳出局部最优取得进一步优化等问题,提出一种基于局部并行搜索的分布式约束优化算法框架（LPOS）,算法中agent通过自身的取值并行地搜索局部所有邻居取值来进一步扩大对解空间的搜索,从而避免算法过早陷入局部最优。为了保证算法的收敛性与稳定性,设计了一种自适应平衡因子K来平衡算法对解的开发和继承能力,并在理论层面证明了并行搜索优化算法可以扩大对解空间的搜索,自适应平衡因子K可以实现平衡目的。综合实验结果表明,基于该算法框架的算法在求解低密度和高密度DCOP时性能都优于目前最新的算法。特别是在求解高密度DCOP中有显著的提升。     

Multi-neighborhood local search optimization for machine reassignment problem

As the topic of the Google ROADEF/EURO Challenge 2012, machine reassignment problem (denoted as MRP) is an important optimization problem in load balance of cloud computing. Given a set of machines and a set of processes running on machines, the MRP aims at finding a best process-machine reassignment to improve the usage of machines while satisfying various hard constraints. In this paper, we present a metaheuristic algorithm based on multi-neighborhood local search (denoted as MNLS) for solving the MRP. Our MNLS algorithm consists of three primary and one auxiliary neighborhood structures, an efficient neighborhood partition search mechanism with respect to the three primary neighborhoods and a dynamic perturbation operator. Computational results tested on 30 benchmark instances of the ROADEF/EURO Challenge 2012 and comparisons with the results in the challenge and the literature demonstrate the efficacy of the proposed MNLS algorithm in terms of both effectiveness and efficiency. Furthermore, several key components of our MNLS algorithm are analyzed to gain an insight into it.     

A parallel boundary search particle swarm optimization algorithm for constrained optimization problems

During the past decade, considerable research has been conducted on constrained optimization problems (COPs) which are frequently encountered in practical engineering applications. By introducing resource limitations as constraints, the optimal solutions in COPs are generally located on boundaries of feasible design space, which leads to search difficulties when applying conventional optimization algorithms, especially for complex constraint problems. Even though penalty function method has been frequently used for handling the constraints, the adjustment of control parameters is often complicated and involves a trial-and-error approach. To overcome these difficulties, a modified particle swarm optimization (PSO) algorithm named parallel boundary search particle swarm optimization (PBSPSO) algorithm is proposed in this paper. Modified constrained PSO algorithm is adopted to conduct global search in one branch while Subset Constrained Boundary Narrower (SCBN) function and sequential quadratic programming (SQP) are applied to perform local boundary search in another branch. A cooperative mechanism of the two branches has been built in which locations of the particles near boundaries of constraints are selected as initial positions of local boundary search and the solutions of local boundary search will lead the global search direction to boundaries of active constraints. The cooperation behavior of the two branches effectively reinforces the optimization capability of the PSO algorithm. The optimization performance of PBSPSO algorithm is illustrated through 13 CEC06 test functions and 5 common engineering problems. The results are compared with other state-of-the-art algorithms and it is shown that the proposed algorithm possesses a competitive global search capability and is effective for constrained optimization problems in engineering applications.     

混合分散搜索的进化多目标优化算法

在进化多目标优化算法中,种群的多样性、对目标空间的搜索能力及算法的鲁棒性直接影响算法的收敛能力和解集的分散性。针对这些问题,提出了一种混合分散搜索的进化多目标优化算法(SSMOEA)。SSMOEA在混合分散搜索算法架构的同时,重新设计其多样性的选取策略,并引入协同进化机制。此外,为了提高算法的自适应性和鲁棒性,采用了一种新颖的自适应多交叉算子选择方法。SSMOEA与经典的多目标进化算法SPEA2、NSGA-Ⅱ和MOEA/D在12个基准测试函数上的对比结果表明,SSMOEA不仅在求得的Pareto最优解集的宽广性、均匀性和逼近性上有明显优势,而且算法的鲁棒性也有明显的提高。     

基于Powell局部搜索策略的全局优化布谷鸟算法

为了解决布谷鸟搜索算法后期收敛速度慢、求解精度不高、易陷入局部最优等缺陷,提出了一种基于Powell局部搜索策略的全局优化布谷鸟搜索算法.算法将布谷鸟全局搜索能力与Powell方法的局部寻优性能有机地结合,并根据适应度值逐步构建精英种群候选解池在迭代后期牵引Powell搜索的局部优化,在保证求解速度、尽可能找到全局极值点的同时提高算法的求解精度.对52个典型测试函数实验结果表明,该算法相比于传统的布谷鸟搜索算法不仅寻优精度和寻优率有所提高,并且适应能力强、鲁棒性好,与最新提出的其他改进算法相比也具有一定的竞争优势.     

An efficient modified harmony search algorithm with intersect mutation operator and cellular local search for continuous function optimization problems

This paper proposes a modified harmony search (MHS) algorithm with an intersect mutation operator and cellular local search for continuous function optimization problems. Instead of focusing on the intelligent tuning of the parameters during the searching process, the MHS algorithm divides all harmonies in harmony memory into a better part and a worse part according to their fitness. The novel intersect mutation operation has been developed to generate new -harmony vectors. Furthermore, a cellular local search also has been developed in MHS, that helps to improve the optimization performance by exploring a huge search space in the early run phase to avoid premature, and exploiting a small region in the later run phase to refine the final solutions. To obtain better parameter settings for the proposed MHS algorithm, the impacts of the parameters are analyzed by an orthogonal test and a range analysis method. Finally, two sets of famous benchmark functions have been used to test and evaluate the performance of the proposed MHS algorithm. Functions in these benchmark sets have different characteristics so they can give a comprehensive evaluation on the performance of MHS. The experimental results show that the proposed algorithm not only performs better than those state-of-the-art HS variants but is also competitive with other famous meta-heuristic algorithms in terms of the solution accuracy and efficiency.     

PANMIN: sequential and parallel global optimization procedures with a variety of options for the local search strategy

We present two sequential and one parallel global optimization codes, that belong to the stochastic class, and an interface routine that enables the use of the Merlin/MCL environment as a non-interactive local optimizer. This interface proved extremely important, since it provides flexibility, effectiveness and robustness to the local search task that is in turn employed by the global procedures. We demonstrate the use of the parallel code to a molecular conformation problem.

Program summary

Title of program: PANMINCatalogue identifier: ADSUProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADSUProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer for which the program is designed and others on which it has been tested: PANMIN is designed for UNIX machines. The parallel code runs on either shared memory architectures or on a distributed system. The code has been tested on a SUN Microsystems ENTERPRISE 450 with four CPUs, and on a 48-node cluster under Linux, with both the GNU g77 and the Portland group compilers. The parallel implementation is based on MPI and has been tested with LAM MPI and MPICHInstallation: University of Ioannina, GreeceProgramming language used: Fortran-77Memory required to execute with typical data: Approximately O(n²) words, where n is the number of variablesNo. of bits in a word: 64No. of processors used: 1 or manyHas the code been vectorised or parallelized?: Parallelized using MPINo. of bytes in distributed program, including test data, etc.: 147163No. of lines in distributed program, including the test data, etc.: 14366Distribution format: gzipped tar fileNature of physical problem: A multitude of problems in science and engineering are often reduced to minimizing a function of many variables. There are instances that a local optimum does not correspond to the desired physical solution and hence the search for a better solution is required. Local optimization techniques can be trapped in any local minimum. Global Optimization is then the appropriate tool. For example, solving a non-linear system of equations via optimization, one may encounter many local minima that do not correspond to solutions, i.e. they are far from zeroMethod of solution: PANMIN is a suite of programs for Global Optimization that take advantage of the Merlin/MCL optimization environment [1,2]. We offer implementations of two algorithms that belong to the stochastic class and use local searches either as intermediate steps or as solution refinementRestrictions on the complexity of the problem: The only restriction is set by the available memory of the hardware configuration. The software can handle bound constrained problems. The Merlin Optimization environment must be installed. Availability of an MPI installation is necessary for executing the parallel codeTypical running time: Depending on the objective functionReferences: [1] D.G. Papageorgiou, I.N. Demetropoulos, I.E. Lagaris, Merlin-3.0. A multidimensional optimization environment, Comput. Phys. Commun. 109 (1998) 227-249. [2] D.G. Papageorgiou, I.N. Demetropoulos, I.E. Lagaris, The Merlin Control Language for strategic optimization, Comput. Phys. Commun. 109 (1998) 250-275.     

A parallel hybrid local search algorithm for the container loading problem

In this contribution, a parallel hybrid local search algorithm for the three‐dimensional container loading problem (CLP) is proposed. First a simulated annealing method for the CLP is developed, which is then combined with an existing tabu search algorithm to form a hybrid metaheuristic. Finally, parallel versions are introduced for these algorithms. The emphasis is on CLP instances with a weakly heterogeneous load. Numerical tests based on the well‐known 700 test instances from Bischoff and Ratcliff are performed, and the outcome is compared with methods from other authors. The results show a high solution quality obtained with reasonable computing time.     

局部随机搜索扰动的粒子群优化算法

在粒子群优化（PSO）算法中,gBest粒子的行为对算法的收敛性能有较大的影响。提出一种新的改进粒子群优化算法——SLS-PSO算法。该算法以基本PSO算法为框架,融合随机局部搜索算法（SLS）对进化中的gBest粒子进行局部寻优计算,以改善PSO算法在进化中特别是进化后期的收敛性能。通过典型测试函数的计算表明,该算法在收敛速度和精度上都有不同程度的改善。     

求解函数优化问题的改进布谷鸟搜索算法

为了提高布谷鸟搜索算法求解函数优化问题的求精能力和收敛速度,提出了一种基于自适应机制的改进算法.自适应机制用于控制缩放因子和发现概率,以提高种群的多样性,避免早熟,从而使更多的个体参与演化,达到提高求精能力和收敛速度的效果.仿真实验结果表明,与标准的布谷鸟搜索算法相比,基于自适应机制缩放因子的改进算法(rCS)和基于自适应机制发现概率的改进算法(paCS)在求精能力和收敛速度上都有明显的提高;同时具有自适应缩放因子和自适应发现概率的改进算法(iCS)比rCS和paCS具有更优的求精能力和收敛速度.     

A stochastic local search algorithm for constrained continuous global optimization

This paper presents a new stochastic local search algorithm known as feasible–infeasible search procedure (FISP) for constrained continuous global optimization. The proposed procedure uses metaheuristic strategies for combinatorial optimization as well as combined strategies for exploring continuous spaces, which are applied to an efficient process in increasingly refined neighborhoods of current points. We show effectiveness and efficiency of the proposed procedure on a standard set of 13 well‐known test problems. Furthermore, we compare the performance of FISP with SNOPT (sparse nonlinear optimizer) and with few successful existing stochastic algorithms on the same set of test problems.     

A parallel genetic local search algorithm for intrusion detection in computer networks

The security of networked computers plays a strategic role in modern computer systems. This task is so complicated because the determination of normal and abnormal behaviors in computer networks is hard, as the boundaries cannot be well defined. One of the difficulties in such a prediction process is the generation of false alarms in many anomaly based intrusion detection systems. However, fuzzy logic is an important solution to reduce the false alarm rate in determining intrusive activities. This paper proposes a parallel genetic local search algorithm (PAGELS) to generate fuzzy rules capable of detecting intrusive behaviors in computer networks. The system uses the Michigan's approach, where each individual represents a fuzzy rule which has the form “if condition then prediction.” In the presented algorithm the global population is divided into some subpopulations, each assigned to a distinct processor. Each subpopulation consists of the same class fuzzy rules. These rules evolve independently in the proposed parallel manner. Experimental results show that the presented algorithm produces fuzzy rules, which can be used to construct a reliable intrusion detection system.     

Hybrid parallel chaos optimization algorithm with harmony search algorithm

The application of chaotic sequences can be an interesting alternative to provide search diversity in an optimization procedure, named chaos optimization algorithm (COA). Since the chaotic motion is pseudo-randomness and chaotic sequences are sensitive to the initial conditions, the search ability of COA is usually effected by the starting values. Considering this weakness, parallel chaos optimization algorithm (PCOA) is studied in this paper. To obtain optimum solution accurately, harmony search algorithm (HSA) is integrated with PCOA to form a novel hybrid algorithm. Different chaotic maps are compared and the impacts of parallel parameter on the hybrid algorithm are discussed. Several simulation results are used to show the effective performance of the proposed hybrid algorithm.     

A parallel local search framework for the Fixed-Charge Multicommodity Network Flow problem

We present a parallel local search approach for obtaining high quality solutions to the Fixed Charge Multicommodity Network Flow problem (FCMNF). The approach proceeds by improving a given feasible solution by solving restricted instances of the problem where flows of certain commodities are fixed to those in the solution while the other commodities are locally optimized. We derive multiple independent local search neighborhoods from an arc-based mixed integer programming (MIP) formulation of the problem which are explored in parallel. Our scalable parallel implementation takes advantage of the hybrid memory architecture in modern platforms and the effectiveness of MIP solvers in solving small problems instances. Computational experiments on FCMNF instances from the literature demonstrate the competitiveness of our approach against state of the art MIP solvers and other heuristic methods.     

融合分区和局部搜索的多模态多目标优化

为解决多模态多目标优化中种群多样性维持难和所得等价解数量不足问题,基于分区搜索和局部搜索,本研究提出一种融合分区和局部搜索的多模态多目标粒子群算法(multimodal multi-objective particle swarm optimization combing zoning search and local search,ZLS-SMPSO-MM)。在所提算法中,整个搜索空间被分割成多个子空间以维持种群多样性和降低搜索难度;然后,使用已有的自组织多模态多目标粒子群算法在每个子空间搜索等价解和挖掘邻域信息,并利用局部搜索能力较强的协方差矩阵自适应算法对有潜力的区域进行精细搜索。通过14个多模态多目标优化问题测试,并与其他5种知名算法进行比较;实验结果表明ZLS-SMPSO-MM在决策空间能够找到更多的等价解,且整体性能要好于所比较算法。