Local search with a generalized neighborhood in the optimization problem for pseudo-Boolean functions

In the optimization problem for pseudo-Boolean functions we consider a local search algorithm with a generalized neighborhood. This neighborhood is constructed for a locally optimal solution and includes nearby locally optimal solutions. We present some results of simulations for pseudo-Boolean functions whose optimization is equivalent to the problems of facility location, set covering, and competitive facility location. The goal of these experiments is to obtain a comparative estimate for the locally optimal solutions found by the standard local search algorithm and the local search algorithm using a generalized neighborhood.     

Seeking global edges for traveling salesman problem in multi-start search

This study investigates the properties of the edges in a set of locally optimal tours found by multi-start search algorithm for the traveling salesman problem (TSP). A matrix data structure is used to collect global information about edges from the set of locally optimal tours and to identify globally superior edges for the problem. The properties of these edges are analyzed. Based on these globally superior edges, a solution attractor is formed in the data matrix. The solution attractor is a small region of the solution space, which contains the most promising solutions. Then an exhausted enumeration process searches the solution attractor and outputs all solutions in the attractor, including the globally optimal solution. Using this strategy, this study develops a procedure to tackler a multi-objective TSP. This procedure not only generates a set of Pareto-optimal solutions, but also be able to provide the structural information about each of the solutions that will allow a decision-maker to choose the best compromise solution.     

Local and parallel finite element algorithm based on the partition of unity method for the incompressible MHD flow

Based on the partition of unity method (PUM), a local and parallel finite element method is designed and analyzed for solving the stationary incompressible magnetohydrodynamics (MHD). The key idea of the proposed algorithm is to first solve the nonlinear system on a coarse mesh, divide the globally fine grid correction into a series of locally linearized residual problems on some subdomains derived by a class of partition of unity, then compute the local subproblems in parallel, and obtain the globally continuous finite element solution by assembling all local solutions together by the partition of unity functions. The main feature of the new method is that the partition of unity provide a flexible and controllable framework for the domain decomposition. Finally, the efficiency of our theoretical analysis is tested by numerical experiments.     

Genetic local search for multi-objective combinatorial optimization

The paper presents a new genetic local search (GLS) algorithm for multi-objective combinatorial optimization (MOCO). The goal of the algorithm is to generate in a short time a set of approximately efficient solutions that will allow the decision maker to choose a good compromise solution. In each iteration, the algorithm draws at random a utility function and constructs a temporary population composed of a number of best solutions among the prior generated solutions. Then, a pair of solutions selected at random from the temporary population is recombined. Local search procedure is applied to each offspring. Results of the presented experiment indicate that the algorithm outperforms other multi-objective methods based on GLS and a Pareto ranking-based multi-objective genetic algorithm (GA) on travelling salesperson problem (TSP).     

A dual local search framework for combinatorial optimization problems with TSP application

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.     

An efficient algorithm for optimal design of area traffic control with network flows

An equilibrium network design (EQND) is a problem of finding the optimal design parameters while taking into account the route choice of users. This problem can be formulated as an optimization by taking the user equilibrium traffic assignment as a constraint. In this paper, the methods solving the EQND problem with signal settings are investigated via numerical calculations on two example road networks. An efficient algorithm is proposed in which improvement on a locally optimal search by combining the technique of parallel tangents with the gradient projection method is presented. As it shows, the method combines the locally optimal search and globally search heuristic achieved substantially better performance than did those other approaches.     

线性约束凸规划的鞍梯度法

求线性约束凸规划问题的最优解。方法：在鞍梯度法的基础上提出了一个具有全局收敛性的原一对偶外点算法。结果：每步迭代利用Lagrange函数的鞍梯度构造搜索方向，生成次可行解序列，由此得到的序列的极限就是原-对偶问题的最优解。结论：即使从原一对偶问题的不可行点开始迭代算法也收敛。     

A guided local search metaheuristic for the team orienteering problem

In the team orienteering problem (TOP) a set of locations is given, each with a score. The goal is to determine a fixed number of routes, limited in length, that visit some locations and maximise the sum of the collected scores. This paper describes an algorithm that combines different local search heuristics to solve the TOP. Guided local search (GLS) is used to improve two of the proposed heuristics. An extra heuristic is added to regularly diversify the search in order to explore more areas of the solution space. The algorithm is compared with the best known heuristics of the literature and applied on a large problem set. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. Applying GLS to solve the TOP appears to be a very promising technique. Furthermore, the usefulness of exploring more areas of the solution space is clearly demonstrated.     

NeuroGenetic approach for combinatorial optimization: an exploratory analysis

Given the NP-Hard nature of many optimization problems, it is often impractical to obtain optimal solutions to large-scale problems in reasonable computing time. For this reason, heuristic and metaheuristic search approaches are used to obtain good solutions fast. However, these techniques often struggle to develop a good balance between local and global search. In this paper we propose a hybrid metaheuristic approach which we call the NeuroGenetic approach to search for good solutions for these large scale optimization problems by at least partially overcoming this challenge. The proposed NeuroGenetic approach combines the Augmented Neural Network (AugNN) and the Genetic Algorithm (GA) search approaches by interleaving the two. We chose these two approaches to hybridize, as they offer complementary advantages and disadvantages; GAs are very good at searching globally, while AugNNs are more proficient at searching locally. The proposed hybrid strategy capitalizes on the strong points of each approach while avoiding their shortcomings. In the paper we discuss the issues associated with the feasibility of hybridizing these two approaches and propose an interleaving algorithm. We also provide empirical evidence demonstrating the effectiveness of the proposed approach.     

Global search in the optimal control problem with a terminal objective functional represented as the difference of two convex functions

A nonconvex optimal control problem is examined for a system that is linear with respect to state and has a terminal objective functional representable as the difference of two convex functions. A new local search method is proposed, and its convergence is proved. A strategy is also developed for the search of a globally optimal control process, because the Pontryagin and Bellman principles as applied to the above problem do not distinguish between the locally and globally optimal processes. The convergence of this strategy under appropriate conditions is proved.     

Ant colony approach to constrained redundancy optimization in binary systems

This paper presents an ant colony optimization algorithm to address the constrained redundancy allocation problem in order to maximize system reliability for complex binary systems. The constraints involved, though separable, are both linear and non-linear. We couple an adaptive penalty function with the basic ant colony approach to handle highly constrained problems and embed a local search technique to find still better locally optimal solutions. The proposed algorithm has been tested on a large number of problems, containing even up to 500 subsystems, with both fixed and randomly generated parameters. Experimental results demonstrate the advantage of the proposed algorithm to solve similar types of problems.     

A non-interior continuation method for second-order cone programming

We extend the smoothing function proposed by Huang, Han and Chen [Journal of Optimization Theory and Applications, 117 (2003), pp. 39–68] for the non-linear complementarity problems to the second-order cone programming (SOCP). Based on this smoothing function, a non-interior continuation method is presented for solving the SOCP. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that our algorithm is globally and locally superlinearly convergent in absence of strict complementarity at the optimal solution. Numerical results indicate the effectiveness of the algorithm.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

Optimal control of bioprocess systems using hybrid numerical optimization algorithms

In the paper, we consider the bioprocess system optimal control problem. Generally speaking, it is very difficult to solve this problem analytically. To obtain the numerical solution, the problem is transformed into a parameter optimization problem with some variable bounds, which can be efficiently solved using any conventional optimization algorithms, e.g. the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. However, in spite of the improved Broyden–Fletcher–Goldfarb–Shanno algorithm is very efficient for local search, the solution obtained is usually a local extremum for non-convex optimal control problems. In order to escape from the local extremum, we develop a novel stochastic search method. By performing a large amount of numerical experiments, we find that the novel stochastic search method is excellent in exploration, while bad in exploitation. In order to improve the exploitation, we propose a hybrid numerical optimization algorithm to solve the problem based on the novel stochastic search method and the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. Convergence results indicate that any global optimal solution of the approximate problem is also a global optimal solution of the original problem. Finally, two bioprocess system optimal control problems illustrate that the hybrid numerical optimization algorithm proposed by us is low time-consuming and obtains a better cost function value than the existing approaches.     

A two-phase method for selecting IMRT treatment beam angles: Branch-and-Prune and local neighborhood search

This paper presents a new two-phase solution approach to the beam angle and fluence map optimization problem in Intensity Modulated Radiation Therapy (IMRT) planning. We introduce Branch-and-Prune (B&P) to generate a robust feasible solution in the first phase. A local neighborhood search algorithm is developed to find a local optimal solution from the Phase I starting point in the second phase. The goal of the first phase is to generate a clinically acceptable feasible solution in a fast manner based on a Branch-and-Bound tree. In this approach, a substantially reduced search tree is iteratively constructed. In each iteration, a merit score based branching rule is used to select a pool of promising child nodes. Then pruning rules are applied to select one child node as the branching node for the next iteration. The algorithm terminates when we obtain a desired number of angles in the current node. Although Phase I generates quality feasible solutions, it does not guarantee optimality. Therefore, the second phase is designed to converge Phase I starting solutions to local optimality. Our methods are tested on two sets of real patient data. Results show that not only can B&P alone generate clinically acceptable solutions, but the two-phase method consistently generates local optimal solutions, some of which are shown to be globally optimal.     

Interactive model-based search with reactive resource allocation

We revisit the interactive model-based approach to global optimization proposed in Wang and Garcia (J Glob Optim 61(3):479–495, 2015) in which parallel threads independently execute a model-based search method and periodically interact through a simple acceptance-rejection rule aimed at preventing duplication of search efforts. In that paper it was assumed that each thread successfully identifies a locally optimal solution every time the acceptance-rejection rule is implemented. Under this stylized model of computational time, the rate of convergence to a globally optimal solution was shown to increase exponentially in the number of threads. In practice however, the computational time required to identify a locally optimal solution varies greatly. Therefore, when the acceptance-rejection rule is implemented, several threads may fail to identify a locally optimal solution. This situation calls for reallocation of computational resources in order to speed up the identification of local optima when one or more threads repeatedly fail to do so. In this paper we consider an implementation of the interactive model-based approach that accounts for real time, that is, it takes into account the possibility that several threads may fail to identify a locally optimal solution whenever the acceptance-rejection rule is implemented. We propose a modified acceptance-rejection rule that alternates between enforcing diverse search (in order to prevent duplication) and reallocation of computational effort (in order to speed up the identification of local optima). We show that the rate of convergence in real-time increases with the number of threads. This result formalizes the idea that in parallel computing, exploitation and exploration can be complementary provided relatively simple rules for interaction are implemented. We report the results from extensive numerical experiments which are illustrate the theoretical analysis of performance.     

Fast local search and guided local search and their application to British Telecom's workforce scheduling problem

This paper reports a fast local search (FLS) algorithm which helps to improve the efficiency of hill climbing and a guided local search (GLS) algorithm which was developed to help local search to escape local optima and distribute search effort. To illustrate how these algorithms work, this paper describes their application to British Telecom's workforce scheduling problem, which is a hard real life problem. The effectiveness of FLS and GLS are demonstrated by the fact that they both outperform all the methods applied to this problem so far, which include simulated annealing, genetic algorithms and constraint logic programming.     

Fitness landscape analysis for the no-wait flow-shop scheduling problem

The fitness landscape of the no-wait (continuous) flow-shop scheduling problem is investigated by examining the ruggedness of the landscape and the correlation between the quality of a solution and its distance to an optimal solution. The results confirm the presence of a big valley structure as known from other combinatorial optimization problems. The suitability of the landscape for search with evolutionary computation and local search methods is discussed. The observations are validated by experiments with two evolutionary algorithms.     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

A new branch and bound algorithm for solving quadratic programs with linear complementarity constraints

In order to find a global solution for a quadratic program with linear complementarity constraints (QPLCC) more quickly than some existing methods, we consider to embed a local search method into a global search method. To say more specifically, in a branch-and-bound algorithm for solving QPLCC, when we find a new feasible solution to the problem, we utilize an extreme point algorithm to obtain a locally optimal solution which can provide a better bound and help us to trim more branches. So, the global algorithm can be accelerated. A preliminary numerical experiment was conducted which supports the new algorithm.