改进二进制人工蜂群算法求解多维背包问题

针对二进制人工蜂群算法收敛速度慢、易陷入局部最优的缺点,提出一种改进的二进制人工蜂群算法。新算法对人工蜂群算法中的邻域搜索公式进行了重新设计,并通过Bayes公式来决定食物源的取值概率。将改进后的算法应用于求解多维背包问题,在求解过程中利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正。通过对典型多维背包问题的仿真实验,表明了本文算法在解决多维背包问题上的可行性和有效性。     

Allocating metrology capacity to multiple heterogeneous machines

The measurement of lots to check process quality is crucial but also a non-added value operation in manufacturing systems. This paper is motivated by semiconductor manufacturing, where metrology tools are expensive, thus limiting metrology capacity which must be optimally used. In a context where multiple heterogeneous machines are sharing a common metrology workshop, the problem of minimising risk while considering metrology capacity arises. An integer linear programming (ILP) model is presented, which corresponds to a multiple-choice knapsack problem. Simple rounding heuristics are proposed, whose results on randomly generated instances are compared with the optimal solutions obtained using a standard solver on the ILP. Additionally, numerical experiments on industrial data are presented and discussed.     

Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem

This article addresses a Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem, an NP-hard combinatorial optimization problem. The problem is solved by using a cooperative approach that uses a local search for exploring a series of neighbourhoods induced from the Lagrangian relaxation. Each neighbourhood is submitted to an optimization process using two alternative strategies: reducing and moving strategies. The reducing strategy serves to reduce the current search space whereas the moving strategy explores the new search space. The performance of the proposed approach is evaluated on benchmark instances taken from the literature. Its obtained results are compared with those reached by some recent methods available in the literature. New solutions have been obtained for almost 80% of the instances tested.     

Conceptual design optimization of rectilinear building frames: A knapsack problem approach

This article presents an automated technique for preliminary layout (conceptual design) optimization of rectilinear, orthogonal building frames in which the shape of the building plan, the number of bays and the size of unsupported spans are variables. It adopts the knapsack problem as the applied combinatorial optimization problem, and describes how the conceptual design optimization problem can be generally modelled as the unbounded multi-constraint multiple knapsack problem. It discusses some special cases, which can be modelled more efficiently as the single knapsack problem, the multiple-choice knapsack problem or the multiple knapsack problem. A knapsack contains sub-rectangles that define the floor plan and the location of columns. Particular conditions or preferences for the conceptual design can be incorporated as constraints on the knapsacks and/or sub-rectangles. A bi-objective knapsack problem is defined with the aim of obtaining a conceptual design having minimum cost and maximum plan regularity (minimum structural eccentricity). A multi-objective ant colony algorithm is formulated to solve the combinatorial optimization problem. A numerical example is included to demonstrate the application of the present method and the robustness of the algorithm.     

An Evolutionary Lagrange Method For Mixed-Integer Constrained Optimization Problems

This study proposes a method for solving mixed-integer constrained optimization problems using an evolutionary Lagrange method. In this approach, an augmented Lagrange function is used to transform the mixed-integer constrained optimization problem into an unconstrained min—max problem with decision-variable minimization and Lagrange-multiplier maximization. The mixed-integer hybrid differential evolution (MIHDE) is introduced into the evolutionary min—max algorithm to accomplish the implementation of the evolutionary Lagrange method. MIHDE provides a mixed coding to denote genetic representations of teal and integer variables, and a rounding operation is used to guide the genetic evolution of integer variables. To fulfill global convergence, self-adaptation for penalty parameters is involved in the evolutionary min—max algorithm so that small penalty parameters can be used, not affecting the final search results. Some numerical experiments are tested to evacuate the performance of the proposed method. Numerical experiments demonstrate that the proposed method converges to better solutions than the conventional penalty function method     

带调整时间的多目标流水车间调度的优化算法

为高效地求解带调整时间的多目标流水车间调度问题,提出了一种多目标混合遗传算法,此算法依据基于Pareto优于关系的个体排序数和密度值计算适应度,保持解的多样性,并采用非劣解并行局部搜索策略,提高算法的搜索效率.此外,引入精英策略保证算法的收敛性,在进化过程中通过淘汰掉个别最差个体,进一步加快解的收敛速度.仿真结果表明,新算法能够有效地解决带调整时间的多目标流水车间调度问题.     

马氏过程的随机库存路径问题模型与算法

考虑到随机需求库存路径问题(Inventory Routing Problem,IRP)本身所具有的马尔可夫、随机等特性,从其现实意义出发,将IRP描述为一个马尔可夫决策过程(Markov decision process,MDP).在运用非线性背包问题的求解方法得到初始策略并构成直接配送线路的基础上,提出一种本地搜索算法对其进行优化.通过实例演算.结果表明了该算法的实用性和有效性.     

A hybrid heuristic for the multiple choice multidimensional knapsack problem

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.     

A new multi-objective evolutionary algorithm: neighbourhood exploring evolution strategy

This article proposes a new multi-objective evolutionary algorithm, called neighbourhood exploring evolution strategy (NEES). This approach incorporates the idea of neighbourhood exploration together with other techniques commonly used in the multi-objective evolutionary optimization literature (namely, non-dominated sorting and diversity preservation mechanisms). The main idea of the proposed approach was derived from a single-objective evolutionary algorithm, called the line-up competition algorithm (LCA), and it consists of assigning neighbourhoods of different sizes to different solutions. Within each neighbourhood, new solutions are generated using a (1+λ)-ES (evolution strategy). This scheme naturally balances the effect of local search (which is performed by the neighbourhood exploration mechanism) with that of the global search performed by the algorithm, and gradually impels the population to progress towards the true Pareto-optimal front of the problem to explore the extent of that front. Three versions of the proposal are studied: a (1+1)-NEES, a (1+2)-NEES and a (1+4)-NEES. Such approaches are validated on a set of standard test problems reported in the specialized literature. Simulation results indicate that, for continuous numerical optimization problems, the proposal (particularly the (1+1)-NEES) is competitive with respect to NSGA-II, which is an algorithm representative of the state-of-the-art in evolutionary multi-objective optimization. Moreover, all the versions of NEES improve on the results of NSGA-II when dealing with a discrete optimization problem. Although preliminary, such results might indicate a potential application area in which the proposed approach could be particularly useful.     

A pegging algorithm for separable continuous nonlinear knapsack problems with box constraints

This article proposes an efficient pegging algorithm for solving separable continuous nonlinear knapsack problems with box constraints. A well-known pegging algorithm for solving this problem is the Bitran–Hax algorithm, a preferred choice for large-scale problems. However, at each iteration, it must calculate an optimal dual variable and update all free primal variables, which is time consuming. The proposed algorithm checks the box constraints implicitly using the bounds on the Lagrange multiplier without explicitly calculating primal variables at each iteration as well as updating the dual solution in a more efficient manner. Results of computational experiments have shown that the proposed algorithm consistently outperforms the Bitran–Hax in all baseline testing and two real-time application models. The proposed algorithm shows significant potential for many other mathematical models in real-world applications with straightforward extensions.     

背包问题的混合粒子群优化算法

经典的粒子群是一个有效的寻找连续函数极值的方法，结合遗传算法的思想提出的混合粒子群算法来解决背包问题，经过比较测试，6种混合粒子群算法的效果都比较好，特别交叉策略A和变异策略C的混合粒子群算法是最好的且简单有效的算法，并成功地运用在投资问题中。对于目前还没有好的解法的组合优化问题，很容易地修改此算法就可解决     

An improved imperialist competitive algorithm for multi-objective optimization

This article proposes an improved imperialistic competitive algorithm to solve multi-objective optimization problems. The proposed multi-objective imperialistic competitive algorithm (MOICA) uses the elitist strategy, based on the mutation and crossover as in genetic algorithms, and the Pareto concept to store simultaneously optimal solutions of multiple conflicting functions. Three performance metrics are used to evaluate the performance of the new algorithm: convergence to the true Pareto-optimal set, solution diversity and robustness, characterized by the variance over 10 runs. To validate the efficiency of the proposed algorithm, several multi-objective standard test functions with true solutions are used. The obtained results show that the MOICA outperforms most of the methods available in the literature. The proposed algorithm can also handle multi-objective engineering design problems with high dimensions.     

Combining mutual information and stable matching strategy for dynamic evolutionary multi-objective optimization

It is reasonable to assume that the changing of the optimization environment is smooth when considering a dynamic multi-objective optimization problem. Learning techniques are widely used to explore the dependence structure to facilitate population re-initialization in evolutionary search paradigms. The aim of the learning techniques is to discover knowledge from history information, thereby to track the movement of the optimal front quickly through good initialization when a change occurs. In this article, a new learning strategy is proposed, where the main ideas are (1) to use mutual information to identify the relationship between previously found approximated solutions; (2) to use a stable matching mechanism strategy to associate previously found optimal solutions bijectively; and (3) to re-initialize the new population based on a kinematics model. Controlled experiments were carried out systematically on some widely used test problems. Comparison against several state-of-the-art dynamic multi-objective evolutionary algorithms showed comparable performance in favour of the developed algorithm.     

Modelling and a tabu search solution for the slab reallocation problem in the steel industry

This paper considers a slab reallocation problem arising from operations planning in the steel industry. The problem involves reallocating steel slabs to customer orders to improve the utilisation of slabs and the level of customer satisfaction. It can be viewed as an extension of a multiple knapsack problem. We firstly formulate the problem as an integer nonlinear programming (INLP) model. With variable replacement, the INLP model is then transformed into a mixed integer linear programming (MILP) model, which can be solved to optimality by MILP optimisers for very small instances. To obtain satisfactory solutions efficiently for practical-sized instances, a heuristic algorithm based on tabu search (TS) is proposed. The algorithm employs multiple neighbourhoods including swap, insertion and ejection chain in local search, and adopts solution space decomposition to speed up computation. In the ejection chain neighbourhood, a new and more effective search method is also proposed to take advantage of the structural properties of the problem. Computational experiments on real data from an advanced iron and steel company in China show that the algorithm generates very good results within a short time. Based on the model and solution approach, a decision support system has been developed and implemented in the company.     

MONSS: A multi-objective nonlinear simplex search approach

This article presents a novel methodology for dealing with continuous box-constrained multi-objective optimization problems (MOPs). The proposed algorithm adopts a nonlinear simplex search scheme in order to obtain multiple elements of the Pareto optimal set. The search is directed by a well-distributed set of weight vectors, each of which defines a scalarization problem that is solved by deforming a simplex according to the movements described by Nelder and Mead's method. Considering an MOP with n decision variables, the simplex is constructed using n+1 solutions which minimize different scalarization problems defined by n+1 neighbor weight vectors. All solutions found in the search are used to update a set of solutions considered to be the minima for each separate problem. In this way, the proposed algorithm collectively obtains multiple trade-offs among the different conflicting objectives, while maintaining a proper representation of the Pareto optimal front. In this article, it is shown that a well-designed strategy using just mathematical programming techniques can be competitive with respect to the state-of-the-art multi-objective evolutionary algorithms against which it was compared.     

Hybridization of ABC and PSO algorithms for improved solutions of RCPSP

A resource-constrained project scheduling problem (RCPSP) is one of the most famous intractable NP-hard problems in the operational research area in terms of its practical value and research significance. To effectively solve the RCPSP, we propose a hybrid approach by integrating artificial bee colony (ABC) and particle swarm optimization (PSO) algorithms. Moreover, a novel structure of ABC-PSO is devised based on embedded ABC-PSO (EABC-PSO) and sequential ABC-PSO (SABC-PSO) strategies. The EABC-PSO strategy mainly applies the PSO algorithm to update the process of the ABC algorithm while the SABC-PSO strategy demonstrates an approach in which computational results obtained from the ABC algorithm are further improved based on the PSO algorithm. In both strategies, bees in the ABC process are entitled to learning capacity from the best local and global solutions in terms of the PSO concept. Subsequently, the updates of solutions are premeditated with crossover and insert operators together with double justification methods. Computational results obtained from the tests on benchmark sets show that the proposed ABC-PSO algorithm is efficient in solving RCPSP problems, demonstrating clear advantages over the pure ABC algorithm, the PSO algorithm, and a number of listed heuristics.     

A nested column generation algorithm to the meta slab allocation problem in the steel making industry

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the ‘multi-stage multiple knapsack problem’ where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design ‘bins’, here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill.     

A Convex and Exact Approach to Discrete Constrained TV-L1 Image Approximation

We study the TV-L1 image approximation model from primal and dual perspective, based on a proposed equivalent convex formulations. More specifically, we apply a convex TV-L1 based approach to globally solve the discrete constrained optimization problem of image approximation, where the unknown image function $u(x)∈\{f_1 ,... , f_n\}$, $∀x ∈ Ω$. We show that the TV-L1 formulation does provide an exact convex relaxation model to the non-convex optimization problem considered. This result greatly extends recent studies of Chan et al., from the simplest binary constrained case to the general gray-value constrained case, through the proposed rounding scheme. In addition, we construct a fast multiplier-based algorithm based on the proposed primal-dual model, which properly avoids variability of the concerning TV-L1 energy function. Numerical experiments validate the theoretical results and show that the proposed algorithm is reliable and effective.     

An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem

This article presents an efficient heuristic placement algorithm, namely, a bidirectional heuristic placement, for solving the two-dimensional rectangular knapsack packing problem. The heuristic demonstrates ways to maximize space utilization by fitting the appropriate rectangle from both sides of the wall of the current residual space layer by layer. The iterative local search along with a shift strategy is developed and applied to the heuristic to balance the exploitation and exploration tasks in the solution space without the tuning of any parameters. The experimental results on many scales of packing problems show that this approach can produce high-quality solutions for most of the benchmark datasets, especially for large-scale problems, within a reasonable duration of computational time.     

Cooperative parallel adaptive neighbourhood search for the disjunctively constrained knapsack problem

This article investigates the use of parallel computing for solving the disjunctively constrained knapsack problem. The proposed parallel computing model can be viewed as a cooperative algorithm based on a multi-neighbourhood search. The cooperation system is composed of a team manager and a crowd of team members. The team members aim at applying their own search strategies to explore the solution space. The team manager collects the solutions from the members and shares the best one with them. The performance of the proposed method is evaluated on a group of benchmark data sets. The results obtained are compared to those reached by the best methods from the literature. The results show that the proposed method is able to provide the best solutions in most cases. In order to highlight the robustness of the proposed parallel computing model, a new set of large-scale instances is introduced. Encouraging results have been obtained.