Муравьиный алгоритм (Задание 5)

Expert Systems with Applications 38 (2011) 3640–3646Contents lists available at ScienceDirectExpert Systems with Applicationsjournal homepage: www.elsevier.com/locate/eswaReliability optimization of a series system with multiple-choice and budgetconstraints using an efficient ant colony approachFardin Ahmadizar a,⇑, Hiresh Soltanpanah babDepartment of Industrial Engineering, University of Kurdistan, Pasdaran Boulvard, Sanandaj, IranDepartment of Industrial Engineering, Islamic Azad University, Sanandaj Branch, Sanandaj, Irana r t i c l ei n f oKeywords:Series systemReliability optimizationMultiple-choiceBudget constraintAnt colony optimizationFuzzy setsa b s t r a c tThis paper deals with a reliability optimization problem for a series system with multiple-choice andbudget constraints. The objective is to choose one technology for each subsystem in order to maximizethe reliability of the whole system subject to the available budget.

This problem is NP-hard and couldbe formulated as a binary integer programming problem with a nonlinear objective function. In thispaper, an efficient ant colony optimization (ACO) approach is developed for the problem. In the approach,a solution is generated by an ant based on both pheromone trails modified by previous ants and heuristicinformation considered as a fuzzy set. Constructed solutions are not guaranteed to be feasible; consequently, applying an appropriate procedure, an infeasible solution is replaced by a feasible one. Then, feasible solutions are improved by a local search. The proposed approach is compared with the existingmetaheuristic available in the literature.

Computational results demonstrate that the approach servesto be a better performance for large problems.Ó 2010 Elsevier Ltd. All rights reserved.1. IntroductionReliability is a significant design measure in many industrialenvironments such as telecommunication systems and manufacturing facilities. The design of such hardware systems, called reliability optimization problem, can usually be based on eithermaximizing reliability, availability and performance, or minimizing cost. Reliability optimization of a series system has alwaysbeen a critical matter. Subsystems of a series system are functionally organized such that any failure of each subsystem will causethe failure of the whole system.

One of the strategies for increasingthe system reliability of these sorts of systems is to use extra unitsin each subsystem in parallel. In this problem, reliability optimization is concerned with determining the optimal number of redundant units for one component employed in each subsystem. Manyalgorithms have been developed over the years to solve redundancy allocation problem (e.g. see Chen, 2006; Coit & Smith,1996; Hsieh, 2003; Ramirez-Marquez & Coit, 2004; Ruan & Sun,2006; Sung & Lee, 1994; Tavakkoli-Moghaddam et al., 2008; Yeh,2009; You & Chen, 2005; Zhao & Liu, 2004; Zhao et al., 2007) andin some cases, reliability optimization is concerned with the designof k-out-of-n systems (e.g.

see Tan, 2003; Yeh, 2004, 2006). As it isoften desired to consider the practical design issue of handling a⇑ Corresponding author. Tel./fax: +98 871 6660073.E-mail addresses: f.ahmadizar@uok.ac.ir (F. Ahmadizar), heresh@iausdj.ac.ir(H. Soltanpanah).0957-4174/$ - see front matter Ó 2010 Elsevier Ltd. All rights reserved.doi:10.1016/j.eswa.2010.09.018variety of different component types, this paper deals with a reliability optimization problem with multiple-choice constraintswhich has not received enough attention.We consider a series system such that the reliability of thewhole system should be maximized subject to multiple-choiceand budget constraints.

For each subsystem, a range of technologies is available among which only one must be chosen. If thereis no constraint in the budget, then the most reliable technologieswould be the most favorable. But, the available budget usually islimited and as the more reliable, the more expensive, a strategyis required to identify the optimal combination of technologies.This problem is called the reliability optimization of a series system with multiple-choice and budget constraints. The problem isformulated as a binary integer programming problem with a nonlinear objective function (Ait-Kadi & Nourelfath, 2001; Sung & Cho,2000), which is equivalent to a knapsack problem with multiplechoice constraints, so that it belongs to the NP-hard class of problems (Garey & Johnson, 1979). Some exact algorithms have beendeveloped to solve such knapsack problems with multiple-choiceconstraints (Nauss, 1978; Sinha & Zoltners, 1979) or the reliabilityproblem (Sung & Cho, 2000) which are not efficient for large industrial problems because they require a very large amount of computation time to obtain the optimal solution.

Therefore, the use ofheuristics or metaheuristics is appeared to be necessary to attainoptimal or nearly optimal solutions in a little time. Nourelfathand Nahas (2003) have proposed a heuristic approach based onthe Hopfield model of neural networks. The approach applies aF. Ahmadizar, H. Soltanpanah / Expert Systems with Applications 38 (2011) 3640–3646new model of Hopfield networks, where neurons take quantizedvalues rather than just binary or continuous values.

This heuristicis quickly able to obtain optimal or nearly optimal solutions ofsmall problems. The first modern metaheuristic (and the onlyone based on our knowledge) has been proposed by Nahas andNourelfath (2005) to solve the problem. In this algorithm, whichis an ant system, called AS, a penalty treated in the pheromonetrails update is employed for infeasible solutions concerning tothe budget constraint. The penalties are proportional to theamount of budget violations. Also, a local search is applied to improve constructed solutions. The AS approach is quickly able to obtain optimal or nearly optimal solutions of large problems.In this paper, we develop an efficient ant colony system, calledACS, for the problem. Ant colony optimization (ACO) (Dorigo, 1992;Dorigo et al., 1996; Dorigo & Stutzle, 2003) is a metaheuristicdeveloped for solving discrete optimization problems.

An ACOalgorithm is a population-based approach based on the behaviorof real ant colonies using pheromones as a communication medium. Real ants are capable of finding the shortest path from theirnest to a food source without using visual cues. In the ACS approach, a solution is generated by applying a pseudo-stochasticrule based on a combination of the previous solutions results andthe knowledge related to the problem as two fuzzy sets.

The unfeasibility of constructed solutions is removed by replacing an infeasible solution by a feasible one based on a neighborhood searchprocedure. Each solution is then improved by an interesting localsearch. A set of large problems is used for evaluating the proposedapproach.The remainder of the paper is organized as follows. The nextsection gives the problem statement as a binary integer programming problem with a nonlinear objective function. The proposedant colony approach is described in Section 3.

Section 4 providescomputational experiments and finally, concluding remarks are given in Section 5.2. Problem formulationConsider a series system that includes S different subsystems.For subsystem i, there exist Ni available technologies with differentcharacteristics such as cost and reliability. Let Cij and Rij be, respectively, the cost and reliability of subsystem i when technology j isused. Total available amount of budget is B. The optimization problem is to choose only one technology for each subsystem to maximize reliability of the whole system (Rsys) subject to the availablebudget. In order to formulate the problem in mathematical expression, decision variable xij is addressed as follows:xij ¼1;3.

Proposed ant colony approachIn this paper, an ant colony system (Dorigo & Gambardella,1997a, 1997b) based approach is developed for solving the reliability problem under consideration. To apply an ACO metaheuristic to acombinatorial optimization problem, it is appropriate to representthe problem by a graph G ¼ ðN; EÞ, where N and E are, respectively,the nodes and edges. To represent the problem as such a graph,two types of nodes are introduced: the set of nodes N1 containingone element for each subsystem and the set of nodes N2 containingone element for each technology.

Furthermore, the edges E connectsubsystems to their available technologies, that is, each node in N1 isconnected to each of the corresponding nodes in N2 by an edge. In theproposed approach, an ant starts from the first subsystem andchooses (moves to) one of the available technologies for this subsystem. Then, the ant iteratively moves to the next subsystem andchooses a technology. At each step, a technology is chosen by applying a transition rule so-called pseudo-random proportional rule.Note that the generated solution may be infeasible; because constraints (2) and (3) are guaranteed during the construction process,but the total cost of the chosen technologies may be greater than B.3.1.

General structure of the approachThe general structure of the approach can be represented as follows (the next sections provide the details).Algorithm 1Step 1. The pheromone trails and the parameters are set.Step 2. The following procedures are iterated Max_iter (aninteger parameter) times:Step 2.1. The following actions are iterated Ant_size (aninteger parameter) times:A.