Interactive preferences in multiobjective ant colony optimisation for assembly line balancing

Soft Computing - Tập 19 - Trang 2891-2903 - 2014
Manuel Chica1, Óscar Cordón1,2, Sergio Damas1, Joaquín Bautista3
1European Centre for Soft Computing, Mieres, Spain
2DECSAI and CITIC-UGR, University of Granada, Granada, Spain
3Universitat Politècnica de Catalunya, Barcelona, Spain

Tóm tắt

In this contribution, we propose an interactive multicriteria optimisation framework for the time and space assembly line balancing problem. The framework allows decision maker interaction by means of reference points to obtain the most interesting non-dominated solutions. The principal components of the framework are the $$g$$ -dominance preference scheme and a state-of-the-art memetic multiobjective ant colony optimisation approach. In addition, the framework includes a novel adaptive multi-colony mechanism to be able to handle the preferences in an interactive way. Results show how the multiobjective framework can interactively obtain the most useful solutions with higher convergence than previous a priori methods. The experimentation also makes use of original data of the Nissan Pathfinder engine and practical bounds to define industrially feasible solutions in a set of scenarios. By solving the problem in these scenarios, we show the search guidance advantages of using an interactive multiobjective ant colony optimisation method.

Tài liệu tham khảo

Barán B, Schaerer M (2003) A multiobjective ant colony system for vehicle routing problem with time windows. In: 21st IASTED international conference, Innsbruck, pp 97–102 Battaïa O, Dolgui A (2013) A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ 142(2):259–277 Bautista J, Pereira J (2007) Ant algorithms for a time and space constrained assembly line balancing problem. Eur J Oper Res 177(3):2016–2032 Baybars I (1986) A survey of exact algorithms for the simple assembly line balancing problem. Manag Sci 32(8):909–932 Said Ben L, Bechikh S, Ghédira K (2010) The r-dominance: a new dominance relation for interactive evolutionary multicriteria decision making. IEEE Trans Evol Comput 14(5):801–818 Boysen N, Fliedner M, Scholl A (2007) A classification of assembly line balancing problems. Eur J Oper Res 183(2):674–693 Branke J, Deb K, Miettinen K, Slowinski R (eds) (2008) Multiobjective optimization, interactive and evolutionary approaches. Lecture notes in computer science, vol 5252. Springer, Berlin Chica M, Cordón O, Damas S (2011) An advanced multi-objective genetic algorithm design for the time and space assembly line balancing problem. Comput Ind Eng 61(1):103–117 Chica M, Cordón O, Damas S, Bautista J (2010) Multiobjective, constructive heuristics for the 1/3 variant of the time and space assembly line balancing problem: ACO and random greedy search. Inf Sci 180:3465–3487 Chica M, Cordón O, Damas S, Bautista J (2010) A multiobjective GRASP for the 1/3 variant of the time and space assembly line balancing problem. Trends Appl Intell Syst Lect Notes Artif Intell 6098:656–665 Chica M, Cordón O, Damas S, Bautista J (2011) Including different kinds of preferences in a multi-objective ant algorithm for time and space assembly line balancing on different nissan scenarios. Exp Syst Appl 38:709–720 Chica M, Cordón O, Damas S, Bautista J (2012) Multiobjective memetic algorithms for time and space assembly line balancing. Eng Appl Artif Intell 25(2):254–273 Chica M, Cordón O, Damas S, Bautista J (2013) A robustness information and visualization model for time and space assembly line balancing under uncertain demand. Int J Prod Econ 145:761–772 Coello CA, Lamont GB, Van Veldhuizen DA (2007) Evolutionary algorithms for solving multi-objective problems, 2nd edn. Springer, Berlin Deb K (1999) Solving goal programming problems using multi-objective genetic algorithms. In: IEEE congress on evolutionary computation (CEC 99). Washington (USA), pp 77–84 Deb K, Sinha A, Korhonen PJ, Wallenius J (2010) An interactive evolutionary multiobjective optimization method based on progressively approximated value functions. IEEE Trans Evol Comput 14(5):723–739 Dorigo M, Gambardella L (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66 Figueira JR, Liefooghe A, Talbi EG, Wierzbicki AP (2010) A parallel multiple reference point approach for multi-objective optimization. Eur J Oper Res 205(2):390–400 Fonseca CM, Fleming PJ (1996) On the performance assessment and comparison of stochastic multiobjective optimizers. In: Proceedings of the 4th international conference on parallel problem solving from nature (PPSN). Lecture notes in computer science, vol 1141. Berlin, Germany, pp 584–593 Gandibleux X, Freville A (2000) Tabu search based procedure for solving the 0–1 multiobjective knapsack problem: the two objectives case. J Heurist 6(3):361–383 Greiner D, Galván B, Emperador JM, Méndez M, Winter G (2011) Introducing reference point using g-dominance in optimum design considering uncertainties: an application in structural engineering. In: Evolutionary multi-criteria optimization. Lecture notes in computer science, vol 6576. Springer, Berlin, pp 389–403 Iredi S, Merkle D, Middendorf M (2001) Bi-criterion optimization with multi colony ant algorithms. In: First intl. conference on evolutionary multi-criterion optimization (EMO’01). Springer, Berlin, pp 359–372 Jaszkiewicz A (2002) Genetic local search for multiple objective combinatorial optimization. Eur J Oper Res 137(1):50–71 Kamalian R, Takagi H, Agonino AM (2004) Optimized design of MEMS by evolutionary multi-objective optimization with interactive evolutionary computation. Springer, Berlin, pp 1030–1041 Molina J, Santana LV, Hernández-Díaz AG, Coello CA, Caballero R (2009) g-dominance: reference point based dominance for multiobjective metaheuristics. Eur J Oper Res 197(2):17–24 Phelps S, Koksalan M (2003) An interactive evolutionary metaheuristic for multiobjective combinatorial optimization. Manag Sci 49(12):1726–1738 Rada-Vilela J, Chica M, Cordón O, Damas S (2013) A comparative study of multi-objective ant colony optimization algorithms for the time and space assembly line balancing problem. Appl Soft Comput 13(11):4370–4382 Rodríguez B, Molina J, Pérez F, Caballero R (2012) Interactive design of personalised tourism routes. Tour Manag 33(4):926–940 Scholl A, Becker C (2006) State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur J Oper Res 168(3):666–693 Scholl A, Klein C (1999) Balancing assembly lines effectively—a computational comparison. Eur J Oper Res 114(1):50–58 Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117–132