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

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

A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem

The set k‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLL_ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL_ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL_ccsm performs better than its competitors in terms of solution quality in most classical instances.     

A two‐phase harmony search algorithm for continuous optimization

Harmony search (HS) algorithm is inspired by the music improvisation process in which a musician searches for the best harmony and continues to polish the harmony to improve its aesthetics. The efficiency of evolutionary algorithms depends on the extent of balance between diversification and intensification during the course of the search. An ideal evolutionary algorithm must have efficient exploration in the beginning and enhanced exploitation toward the end. In this paper, a two‐phase harmony search (TPHS) algorithm is proposed that attempts to strike a balance between exploration and exploitation by concentrating on diversification in the first phase using catastrophic mutation and then switches to intensification using local search in the second phase. The performance of TPHS is analyzed and compared with 4 state‐of‐the‐art HS variants on all the 30 IEEE CEC 2014 benchmark functions. The numerical results demonstrate the superiority of the proposed TPHS algorithm in terms of accuracy, particularly on multimodal functions when compared with other state‐of‐the‐art HS variants; further comparison with state‐of‐the‐art evolutionary algorithms reveals excellent performance of TPHS on composition functions. Composition functions are combined, rotated, shifted, and biased version of other unimodal and multimodal test functions and mimic the difficulties of real search spaces by providing a massive number of local optima and different shapes for different regions of the search space. The performance of the TPHS algorithm is also evaluated on a real‐life problem from the field of computer vision called camera calibration problem, ie, a 12‐dimensional highly nonlinear optimization problem with several local optima.     

求解工程结构优化问题的改进布谷鸟搜索算法

针对布谷鸟搜索算法局部搜索能力不强的缺点, 提出一种基于随机局部搜索的改进布谷鸟搜索算法用于求解工程结构优化问题。引入惯性权重以平衡算法的勘探和开采能力; 利用随机局部搜索方法对当前最优解进行局部搜索, 以加快算法的收敛速度。两个工程结构优化问题的实验结果表明了该算法的可行性和有效性。     

Hybrid algorithms for the twin–screw extrusion configuration problem

The twin-screw configuration problem (TSCP) arises in the context of polymer processing, where twin-screw extruders are used to prepare polymer blends, compounds or composites. The goal of the TSCP is to define the configuration of a screw from a given set of screw elements. The TSCP can be seen as a sequencing problem as the order of the screw elements on the screw axis has to be defined. It is also inherently a multi-objective problem since processing has to optimize various conflicting parameters related to the degree of mixing, shear rate, or mechanical energy input among others. In this article, we develop hybrid algorithms to tackle the bi-objective TSCP. The hybrid algorithms combine different local search procedures, including Pareto local search and two phase local search algorithms, with two different population-based algorithms, namely a multi-objective evolutionary algorithm and a multi-objective ant colony optimization algorithm. The experimental evaluation of these approaches shows that the best hybrid designs, combining Pareto local search with a multi-objective ant colony optimization approach, outperform the best algorithms that have been previously proposed for the TSCP.     

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋以一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。     

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.     

A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem

Modern production systems require multiple manufacturing centers—usually distributed among different locations—where the outcomes of each center need to be assembled to generate the final product. This paper discusses the distributed assembly permutation flow‐shop scheduling problem, which consists of two stages: the first stage is composed of several production factories, each of them with a flow‐shop configuration; in the second stage, the outcomes of each flow‐shop are assembled into a final product. The goal here is to minimize the makespan of the entire manufacturing process. With this objective in mind, we present an efficient and parameter‐less algorithm that makes use of a biased‐randomized iterated local search metaheuristic. The efficiency of the proposed method is evaluated through the analysis of an extensive set of computational experiments. The results show that our algorithm offers excellent performance when compared with other state‐of‐the‐art approaches, obtaining several new best solutions.     

Algorithms for the circular two‐dimensional open dimension problem

In this paper, we propose three heuristics for the circular two‐dimensional open dimension problem, also known as the circular strip cutting/packing problem. We first propose an open strip generation solution procedure that uses the best local position rule into the open strip. Second, we propose a simple augmented version of the first heuristic by introducing an exchange‐order strategy. Third, we propose a hybrid heuristic that combines beam search and a series of target values belonging to a predetermined interval search. We evaluate the performance of these heuristics on several instances varying from small to large ones. Encouraging results have been obtained.     

MRMOGA: a new parallel multi‐objective evolutionary algorithm based on the use of multiple resolutions

In this paper, we introduce MRMOGA (Multiple Resolution Multi‐Objective Genetic Algorithm), a new parallel multi‐objective evolutionary algorithm which is based on an injection island approach. This approach is characterized by adopting an encoding of solutions which uses a different resolution for each island. This approach allows us to divide the decision variable space into well‐defined overlapped regions to achieve an efficient use of multiple processors. Also, this approach guarantees that the processors only generate solutions within their assigned region. In order to assess the performance of our proposed approach, we compare it to a parallel version of an algorithm that is representative of the state‐of‐the‐art in the area, using standard test functions and performance measures reported in the specialized literature. Our results indicate that our proposed approach is a viable alternative to solve multi‐objective optimization problems in parallel, particularly when dealing with large search spaces. Copyright © 2006 John Wiley & Sons, Ltd.     

JAMES: An object‐oriented Java framework for discrete optimization using local search metaheuristics

This paper describes the Java Metaheuristics Search framework (JAMES, v1.1): an object‐oriented Java framework for discrete optimization using local search algorithms that exploits the generality of such metaheuristics by clearly separating search implementation and application from problem specification. A wide range of generic local searches are provided, including (stochastic) hill climbing, tabu search, variable neighbourhood search and parallel tempering. These can be applied to any user‐defined problem by plugging in a custom neighbourhood for the corresponding solution type. Using an automated analysis workflow, the performance of different search algorithms can be compared in order to select an appropriate optimization strategy. Implementations of specific components are included for subset selection, such as a predefined solution type, generic problem definition and several subset neighbourhoods used to modify the set of selected items. Additional components for other types of problems (e.g. permutation problems) are provided through an extensions module which also includes the analysis workflow. In comparison with existing Java metaheuristics frameworks that mainly focus on population‐based algorithms, JAMES has a much lower memory footprint and promotes efficient application of local searches by taking full advantage of move‐based evaluation. Releases of JAMES are deployed to the Maven Central Repository so that the framework can easily be included as a dependency in other Java applications. The project is fully open source and hosted on GitHub. More information can be found at http://www.jamesframework.org . Copyright © 2016 John Wiley & Sons, Ltd.     

Multi‐objective memetic algorithm: comparing artificial neural networks and pattern search filter method approaches

In this work, two methodologies to reduce the computation time of expensive multi‐objective optimization problems are compared. These methodologies consist of the hybridization of a multi‐objective evolutionary algorithm (MOEA) with local search procedures. First, an inverse artificial neural network proposed previously, consisting of mapping the decision variables into the multiple objectives to be optimized in order to generate improved solutions on certain generations of the MOEA, is presented. Second, a new approach based on a pattern search filter method is proposed in order to perform a local search around certain solutions selected previously from the Pareto frontier. The results obtained, by the application of both methodologies to difficult test problems, indicate a good performance of the approaches proposed.     

An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion

An ILS algorithm is proposed to solve the permutation flowshop sequencing problem with total flowtime criterion. The effects of different initial permutations and different perturbation strengths are studied. Comparisons are carried out with three constructive heuristics, three ant-colony algorithms and a particle swarm optimization algorithm. Experiments on benchmarks and a set of random instances show that the proposed algorithm is more effective. The presented ILS improves the best known permutations by a significant margin.     

An evolutionary algorithm for the multi‐objective pick‐up and delivery pollution‐routing problem

The design of sustainable logistics solutions poses new challenges for the study of vehicle‐routing problems. The design of efficient systems for transporting products via a heterogeneous fleet of vehicles must consider the minimization of cost, emissions of greenhouse gases, and the ability to serve every customer within an available time slot. This phenomenon gives rise to a multi‐objective problem that considers the emission of greenhouse gases, the total traveling time, and the number of customers served. The proposed model is approached with an ε‐constraint technique that allows small instances to be solved and an evolutionary algorithm is proposed to deal with complex instances. Results for small instances show that all the points that approach the Pareto frontier found by the evolutionary algorithm are nondominated by any solution found by the multi‐objective model. For complex instances, nondominated solutions that serve most of the requests are found with low computational requirements.     

An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times

Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.     

Evolutionary algorithms for the multi‐objective test data generation problem

Automatic test data generation is a very popular domain in the field of search‐based software engineering. Traditionally, the main goal has been to maximize coverage. However, other objectives can be defined, such as the oracle cost, which is the cost of executing the entire test suite and the cost of checking the system behavior. Indeed, in very large software systems, the cost spent to test the system can be an issue, and then it makes sense by considering two conflicting objectives: maximizing the coverage and minimizing the oracle cost. This is what we did in this paper. We mainly compared two approaches to deal with the multi‐objective test data generation problem: a direct multi‐objective approach and a combination of a mono‐objective algorithm together with multi‐objective test case selection optimization. Concretely, in this work, we used four state‐of‐the‐art multi‐objective algorithms and two mono‐objective evolutionary algorithms followed by a multi‐objective test case selection based on Pareto efficiency. The experimental analysis compares these techniques on two different benchmarks. The first one is composed of 800 Java programs created through a program generator. The second benchmark is composed of 13 real programs extracted from the literature. In the direct multi‐objective approach, the results indicate that the oracle cost can be properly optimized; however, the full branch coverage of the system poses a great challenge. Regarding the mono‐objective algorithms, although they need a second phase of test case selection for reducing the oracle cost, they are very effective in maximizing the branch coverage. Copyright © 2011 John Wiley & Sons, Ltd.     

A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time

A variety of metaheuristics have been developed to solve the permutation flow shop problem minimizing total flow time. Iterated local search (ILS) is a simple but powerful metaheuristic used to solve this problem. Fundamentally, ILS is a procedure that needs to be restarted from another solution when it is trapped in a local optimum. A new solution is often generated by only slightly perturbing the best known solution, narrowing the search space and leading to a stagnant state. In this paper, a strategy is proposed to allow the restart solution to be generated from a group of solutions drawn from local optima. This allows an extension of the search space, while maintaining the quality of the restart solution. A multi-restart ILS (MRSILS) is proposed, with the performance evaluated on a set of benchmark instances and compared with six state of the art metaheuristics. The results show that the easily implementable MRSILS is significantly better than five of the other metaheuristics and comparable to or slightly better than the remaining one.     

Using iterated local search for solving the flow‐shop problem: Parallelization,parametrization, and randomization issues

Iterated local search (ILS) is a powerful framework for developing efficient algorithms for the permutation flow‐shop problem (PFSP). These algorithms are relatively simple to implement and use very few parameters, which facilitates the associated fine‐tuning process. Therefore, they constitute an attractive solution for real‐life applications. In this paper, we discuss some parallelization, parametrization, and randomization issues related to ILS‐based algorithms for solving the PFSP. In particular, the following research questions are analyzed: (a) Is it possible to simplify even more the parameter setting in an ILS framework without affecting performance? (b) How do parallelized versions of these algorithms behave as we simultaneously vary the number of different runs and the computation time? (c) For a parallelized version of these algorithms, is it worthwhile to randomize the initial solution so that different starting points are considered? (d) Are these algorithms affected by the use of a “good‐quality” pseudorandom number generator? In this paper, we introduce the new ILS‐ESP (where ESP is efficient, simple, and parallelizable) algorithm that is specifically designed to take advantage of parallel computing, allowing us to obtain competitive results in “real time” for all tested instances. The ILS‐ESP also uses “natural” parameters, which simplifies the calibration process. An extensive set of computational experiments has been carried out in order to answer the aforementioned research questions.     

Exploring the fitness landscape and the run-time behaviour of an iterated local search algorithm for cost-based abduction

Cost-based abduction (CBA) is an important problem in reasoning under uncertainty, and can be considered a generalization of belief revision. CBA is known to be NP-hard and has been a subject of considerable research over the past decade. In this paper, we investigate the fitness landscape for CBA, by looking at fitness–distance correlation for local minima and at landscape ruggedness. Our results indicate that stochastic local search techniques would be promising on this problem. We go on to present an iterated local search algorithm based on hill-climbing, tabu search, and simulated annealing. We compare the performance of our algorithm to simulated annealing, and to Santos' integer linear programming method for CBA.     

Improved trust‐region gradient‐search algorithm for accelerated optimization of wideband antenna input characteristics

Full‐wave electromagnetic (EM) simulation models are ubiquitous in carrying out design closure of antenna structures. Yet, EM‐based design is expensive due to a large number of analyses necessary to yield an optimized design. Computational savings can be achieved using, for example, adjoint sensitivities, surrogate‐assisted procedures, design space dimensionality reduction, or similar sophisticated means. In this article, a simple modification of a rudimentary trust‐region‐embedded gradient search with numerical derivatives is proposed for reduced‐cost optimization of input characteristics of wideband antennas. The approach exploits information and history of relative changes of the design (as compared with the trust region size) during algorithm iterations to control the updates of components of the antenna response Jacobian, specifically, to execute them only if necessary. It is demonstrated that the proposed framework may lead to over 50% savings over the reference algorithm with only minor degradation of the design quality, specifically, up to 0.3 dB (or <3%). Numerical results are supported by experimental validation of the optimized antenna designs. The presented algorithm can be utilized as a stand‐alone optimization routine or as a building block of surrogate‐assisted procedures.