Solving reliability redundancy allocation problems using an artificial bee colony algorithm

This paper proposed a penalty guided artificial bee colony algorithm (ABC) to solve the reliability redundancy allocation problem (RAP). The redundancy allocation problem involves setting reliability objectives for components or subsystems in order to meet the resource consumption constraint, e.g. the total cost. RAP has been an active area of research for the past four decades. The difficulty that one is confronted with the RAP is the maintenance of feasibility with respect to three nonlinear constraints, namely, cost, weight and volume related constraints. In this paper nonlinearly mixed-integer reliability design problems are investigated where both the number of redundancy components and the corresponding component reliability in each subsystem are to be decided simultaneously so as to maximize the reliability of the system. The reliability design problems have been studied in the literature for decades, usually using mathematical programming or heuristic optimization approaches. To the best of our knowledge the ABC algorithm can search over promising feasible and infeasible regions to find the feasible optimal/near-optimal solution effectively and efficiently; numerical examples indicate that the proposed approach performs well with the reliability redundant allocation design problems considered in this paper and computational results compare favorably with previously-developed algorithms in the literature.     

Penalty guided bees search for redundancy allocation problems with a mix of components in series–parallel systems

This paper uses a penalty guided strategy based on an artificial bee colony algorithm (PGBC) to solve the redundancy allocation problem (RAP) in reliability series–parallel systems. The penalty strategy was designed to eliminate the equalities in constraints and formulate new objective operators which guarantee feasibility within a reasonable execution time. The PGBC is used to deal with two kinds of RAPs with a mix of components. In the first example, the RAPs are designed to find the appropriate mix of components and redundancies within a system in order to either minimize the cost in the context of a minimum level of reliability, or maximize reliability subject to a maximum cost and weight. The second example involves RAPs of multi-state series–parallel reliability structures, wherein each subsystem can consist of a maximum of two types of redundant components. The objective is to minimize the total investment cost of system design while satisfying system reliability constraints and the consumer load demands. There are five multi-state system design problems which have been solved for illustration in this example. The experimental results show that the PGBC can significantly outperform other existing methods in the literature with less cost, higher reliability, and a significantly shorter computational time.     

A heuristic algorithm based on Monte Carlo methods for the Rural Postman Problem

In Routing Problems the aim is to determine a minimum cost traversal over a graph satisfying some specified constraints. Most of them are NP-hard problems and many different heuristic solution algorithms have been proposed. The name Monte Carlo, MC, applies to a set of heuristic procedures with the common feature of using random numbers to simulate a given process. MC approach has not been applied to the framework of Routing Problems in the literature. The purpose of this paper is to demonstrate that MC methods could be useful in implementing heuristic algorithms for Routing Problems. In particular, we design an efficient MC heuristic algorithm for the well known Rural Postman Problem (RPP), for which we have a set of instances with known optimal solution taken from the literature.The Rural Postman Problem (RPP) consists of finding a minimum cost traversal of a specified arc subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing Problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

Variable neighborhood search for multi-objective resource allocation problems

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives—minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1_R, the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems.     

A new weighted pathfinding algorithms to reduce the search time on grid maps

Artificial Intelligence (AI) techniques are utilized widely in the field of Expert Systems (ES) - as applied to robotics, video games self-driving vehicles and so on. Pathfinding algorithms are a class of heuristic algorithms based on AI techniques which are used in ES as decision making functions for the purpose of solving problems that would otherwise require human competence or expertise. ES fields that use pathfinding algorithms and operate in real-time face many challenges: for example time constraints, optimality and memory overhead for storing the paths which are found. For these algorithms to work, appropriate problem-specific maps must be constructed. In relation to this, the uniform-cost grid set-up is the most appropriate for ES applications. In this method, each node in a graph is represented as a tile, and the weight “between” tiles is set at a constant value, usually this is set to 1. In the state-of-the-art heuristic algorithms used with this data structure, multiplying the heuristic function by a weight greater than one is well-known technique. In this paper, we present three new techniques using various weights to accelerate heuristic search of grid maps. The first such technique is based on the iteration of a heuristic search algorithm associated with weight-set w. The second technique is based on the length between the start node and goal node, which is then associated with w. The last technique is based on the travel cost and is associated with a weight-set α. These techniques are applicable to a wide class of heuristic search algorithms. Therefore, we implement them, here, within the A*, the Bidirectional A* (Bi-A*) and Jump Point Search (JPS) algorithms; thus obtaining a family of new algorithms. Furthermore, it is seen that the use of these new algorithms results in significant improvements over current search algorithms. We evaluate them in path-planning benchmarks and show the amended JPS technique's greater stability, across weight values, over the other two techniques. However, it is also shown that this technique yields poor results in terms of cost solution.     

A comparative study of heuristic algorithms on Economic Lot Scheduling Problem

The Economic Lot Scheduling Problem (ELSP) has been well-researched for more than 40 years. As the ELSP has been generally seen as NP-hard, researchers have focused on the development of efficient heuristic approaches. In this paper, we consider the time-varying lot size approach to solve the ELSP. A computational study of the existing solution algorithms, Dobson’s heuristic, Hybrid Genetic algorithm, Neighborhood Search heuristics, Tabu Search and the newly proposed Simulated Annealing algorithm are presented. The reviewed methods are first tested on two well-known problems, those of Bomberger’s [Bomberger, E. E. (1966). A dynamic programming approach to a lot size scheduling problem. Management Science 12, 778–784] and Mallya’s [Mallya, R (1992). Multi-product scheduling on a single machine: A case study. OMEGA: International Journal of Management Science 20, 529–534] problems. We show the Simulated Annealing algorithm finds the best known solution to these problems. A similar comparison study is performed on various problem sets previously suggested in the literature. The results show that the Simulated Annealing algorithm outperforms Dobson’s heuristic, Hybrid Genetic algorithm and Neighborhood search heuristics on these problem sets. The Simulated Annealing algorithm also shows faster convergence than the best known Tabu Search algorithm, yet results in solutions of a similar quality. Finally, we report the results of the design of experiment study which compares the robustness of the mentioned meta-heuristic techniques.     

多因素问题的启发式搜索算法MFRA

本文新定义了一类多因素启妇式搜索问题，提出了适于此类问题求解的启发式搜索算法ＭＦＲＡ。文中研究了算法ＭＦＲＡ的可采纳性质，单调限制性质和比较性质等。基于算法ＩＤＡ的思想，提出了ＭＦＲＡ的改进算法ＭＦＲＡ－ＩＤＡ，这一算法具有线性存储空间这一重要特性。     

A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors

We give a class of heuristic algorithms for minimum weight perfect matching on a complete edge-weighted graph K(V) satisfying the triangle inequality, where V is a set of an even number, n, of vertices. This class is a generalization of the Onethird heuristics, the hypergreedy heuristic, and it possibly employs any given exact or approximate perfect matching algorithm as an auxiliary heuristic to an appropriate subgraph of K(V). In particular, by using the heuristic of Gabow et al. [3] as its auxiliary heuristic, our algorithm can obtain a solution whose weight is at most times the weight of the optimal solution in time, or a solution with an error of in O(n ² ) time. Received July 21, 1994; revised November 28, 1995.     

Improving an Algorithm for Approximate Pattern Matching

We study a recent algorithm for fast on-line approximate string matching. This is the problem of searching a pattern in a text allowing errors in the pattern or in the text. The algorithm is based on a very fast kernel which is able to search short patterns using a nondeterministic finite automaton, which is simulated using bit-parallelism. A number of techniques to extend this kernel for longer patterns are presented in that work. However, the techniques can be integrated in many ways and the optimal interplay among them is by no means obvious. The solution to this problem starts at a very low level, by obtaining basic probabilistic information about the problem which was not previously known, and ends integrating analytical results with empirical data to obtain the optimal heuristic. The conclusions obtained via analysis are experimentally confirmed. We also improve many of the techniques and obtain a combined heuristic which is faster than the original work. This work shows an excellent example of a complex and theoretical analysis of algorithms used for design and for practical algorithm engineering, instead of the common practice of first designing an algorithm and then analyzing it. Received March 31, 1998; revised November 18, 1998.     

LOCAL++: A C++ framework for local search algorithms

Local search is an emerging paradigm for combinatorial search which has recently been shown to be very effective for a large number of combinatorial problems. It is based on the idea of navigating the search space by iteratively stepping from one solution to one of its neighbors, which are obtained by applying a simple local change to it. In this paper we present LOCAL++, an object‐oriented framework to be used as a general tool for the development and implementation of local search algorithms in C++. The framework comprises a hierarchy of abstract template classes, one for each local search technique taken into account (i.e. hill‐climbing, simulated annealing and tabu search). Each class specifies and implements the invariant part of the algorithm built according to the technique, and is supposed to be specialized by a concrete class once a given search problem is considered, so as to implement the problem‐dependent part of the algorithm. LOCAL++ comprises also a set of abstract classes for creating new techniques by combining different search techniques and different neighborhood relations. The architecture of LOCAL++ provides a principled modularization for the solution of combinatorial search problems, and helps the designer deriving a neat conceptual scheme of the application, thus facilitating the development and debugging phases. LOCAL++ proved to be flexible enough for the implementation of the algorithms solving various scheduling problems. Copyright © 2000 John Wiley & Sons, Ltd.     

A knowledge-based archive multi-objective simulated annealing algorithm to optimize series–parallel system with choice of redundancy strategies

Redundancy allocation problem (RAP) is one of the best-developed problems in reliability engineering studies. This problem follows to optimize the reliability of a system containing s sub-systems under different constraints, including cost, weight, and volume restrictions using redundant components for each sub-system. Various solving methodologies have been used to optimize this problem, including exact, heuristic, and meta-heuristic algorithms. In this paper, an efficient multi-objective meta-heuristic algorithm based on simulated annealing (SA) is developed to solve multi-objective RAP (MORAP). This algorithm is knowledge-based archive multi-objective simulated annealing (KBAMOSA). KBAMOSA applies a memory matrix to reinforce the neighborhood structure to achieve better quality solutions. The results analysis and comparisons demonstrate the performance of the proposed algorithm for solving MORAP.     

Fast and robust techniques for the euclidean p-median problem with uniform weights

We discuss new solution techniques for the p-median problem, with the goal being to improve the solution time and quality of current techniques. In particular, we hybridize the discrete Lloyd algorithm and the vertex substitution heuristic. We also compare three starting point techniques and present a new solution method that provides consistently good results when appropriately initialized.     

相接行凸约束网络的快速识别算法

约束网络为计算机科学中的许多问题提供了一种有效的表示方法.一般而言,约束满足问题是NP完全的.然而,许多实际问题通常对约束的结构或形式施加了特殊的限制,从而能够高效地加以解决.迄今,为了识别易处理约束类,人们对特殊的约束或约束网络方面进行了许多研究.相接行凸(connected row-convex,简称CRC)约束网络是Deville等人提出的一类易处理问题.为了给该类问题寻求有效的快速识别算法,在CRC约束网络相关工作基础上,提出了CRC约束矩阵的标准型.在分析CRC约束矩阵的标准型性质的基础上,利用行凸(row-convex,简称RC)约束网络的判定,结合PQ树(由P节点和Q节点构成的树)的性质和矩阵的索引表示法,给出了CRC约束网络的快速识别算法.该算法的时间复杂度为O(n³d²),其中,n为约束网络涉及的变量数,d为各变量的定义域中最大定义域的大小.该时间复杂度达到该类问题的最佳时间复杂度,从而为实际的CRC约束满足问题的求解提供了可行的方法.     

A subgradient procedure for the solution of minimax location problems

Unconstrained planar minimax location problems are typically convex but not everywhere differentiable, thus precluding their solution by gradient techniques. We employ subgradients, which always exist, to the solution of some planar minimax location problems. A heuristic subgradient algorithm is presented for the solution of minimax location problems involving Euclidean and rectilinear distances. An attractive feature of the method is the ease of implementation on any size computer. We give a computational comparison of the algorithm with existing methods.     

An AHP based heuristic DPSO algorithm for generating multi criteria production–distribution plan

Multi-criteria integrated production–distribution problems were solved by many researchers using different optimization techniques. A novel analytic hierarchy process (AHP) based heuristic discrete particle swarm optimization (DPSO) algorithm is proposed in this research for solving difficult production–distribution problems. A bearing manufacturing industry's case is considered in this paper and the mathematical model is formulated as mixed integer linear programming (MILP) problem considering multi-period, multi-product and multi-plant scenarios. The three major objectives considered are total cost reduction, minimization of change in labor levels and percentage under-utilization. The results of the AHP based heuristic DPSO algorithm are compared with the branch and bound algorithm results generated using LINGO software. The approach gives good near optimal solutions. In addition to the bearing manufacturing industry dataset, two other test datasets are also solved.     

A comparative analysis of information acquisition mechanisms fordiscrete resource allocation

Discrete resource allocation problems (RAPs) deal with making decisions that result in an optimal deployment of indivisible scarce resources among a group of agents so as to achieve the maximum aggregate utility. One prerequisite for solving the discrete RAP is that the decision maker be cognizant of the individual utility functions for the agents involved. When an agent's preference information is not available, the decision maker needs to gather such information through an inquiry process. The information acquisition process entails its own costs such as communication costs and computation costs. In this paper, three different information inference mechanisms merging, ranking, and entropy - are proposed and compared for the information acquisition process in the discrete RAP. It is found that the merging mechanism results in the least computation costs for the decision maker while the entropy mechanism incurs the least communication costs     

A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem

A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.     

Retrospective adaptive prefetching for interactive Web GIS applications

A major task of a Web GIS (Geographic Information Systems) system is to transfer map data to client applications over the Internet, which may be too costly. To improve this inefficient process, various solutions are available. Caching the responses of the requests on the client side is the most commonly implemented solution. However, this method may not be adequate by itself. Besides caching the responses, predicting the next possible requests from a client and updating the cache with responses for those requests together provide a remarkable performance improvement. This procedure is called “prefetching” and makes caching mechanisms more effective and efficient. This paper proposes an efficient prefetching algorithm called Retrospective Adaptive Prefetch (RAP), which is constructed over a heuristic method that considers the former actions of a given user. The algorithm reduces the user-perceived response time and improves user navigation efficiency. Additionally, it adjusts the cache size automatically, based on the memory size of the client’s machine. RAP is compared with four other prefetching algorithms. The experiments show that RAP provides better performance enhancements than the other methods.     

Evolutionary algorithms,simulated annealing and tabu search: a comparative study

Evolutionary algorithms, simulated annealing (SA), and tabu search (TS) are general iterative algorithms for combinatorial optimization. The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species. Most widely known algorithms of this category are genetic algorithms (GA). GA, SA, and TS have been found to be very effective and robust in solving numerous problems from a wide range of application domains. Furthermore, they are even suitable for ill-posed problems where some of the parameters are not known before hand. These properties are lacking in all traditional optimization techniques. In this paper we perform a comparative study among GA, SA, and TS. These algorithms have many similarities, but they also possess distinctive features, mainly in their strategies for searching the solution state space. The three heuristics are applied on the same optimization problem and compared with respect to (1) quality of the best solution identified by each heuristic, (2) progress of the search from initial solution(s) until stopping criteria are met, (3) the progress of the cost of the best solution as a function of time (iteration count), and (4) the number of solutions found at successive intervals of the cost function. The benchmark problem used is the floorplanning of very large scale integrated (VLSI) circuits. This is a hard multi-criteria optimization problem. Fuzzy logic is used to combine all objective criteria into a single fuzzy evaluation (cost) function, which is then used to rate competing solutions.