A Min-Max Strategy to Aid Decision Making in a Bi-Objective Discrete Optimization Problem Using an Improved Ant Colony Algorithm — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
A Min-Max Strategy to Aid Decision Making in a Bi-Objective Discrete Optimization Problem Using an Improved Ant Colony Algorithm
Department of Mathematics, Faculty of Mathematical Sciences, University for Development Studies, Navrongo, Ghana
,
Department of Mathematics, Faculty of Mathematical Sciences, University for Development Studies, Navrongo, Ghana
,
Department of Mathematics, Faculty of Mathematical Sciences, University for Development Studies, Navrongo, Ghana
1 Department of Mathematics, Faculty of Mathematical Sciences, University for Development Studies, Navrongo, Ghana
2 Department of Mathematics, Faculty of Mathematical Sciences, University for Development Studies, Navrongo, Ghana
3 Department of Mathematics, Faculty of Mathematical Sciences, University for Development Studies, Navrongo, Ghana
A multi-objective optimization problem has two or more objectives to be minimized or maximized simultaneously. It is usually difficult to arrive at a solution that optimizes every objective. Therefore, the best way of dealing with the problem is to obtain a set of good solutions for the decision maker to select the one that best serves his/her interest. In this paper, a ratio min-max strategy is incorporated (after Pareto optimal solutions are obtained) under a weighted sum scalarization of the objectives to aid the process of identifying a best compromise solution. The bi-objective discrete optimization problem which has distance and social cost (in rail construction, say) as the criteria was solved by an improved Ant Colony System algorithm developed by the authors. The model and methodology were applied to hypothetical networks of fourteen nodes and twenty edges, and another with twenty nodes and ninety-seven edges as test cases. Pareto optimal solutions and their maximum margins of error were obtained for the problems to assist in decision making. The proposed model and method is user-friendly and provides the decision maker with information on the quality of each of the Pareto optimal solutions obtained, thus facilitating decision making.
Malti, B., Shikha, A. and Sanjay, S. (2012) Survey of Meta-Heuristic Algorithms for Combinatorial Optimization. Journal of Computer Applications, 58, 21-31. https://doi.org/10.5120/9391-3813
Castro-Gutierrez, J. (2012) Multi-Objective Tools for the Vehicle Routing Problem with Time Windows.
Kparib, D.Y., Twum, S.B. and Boah, D.K. (2018) An Improved Ant Colony System Algorithm for Solving Shortest Path Network Problems. International Journal of Science and Research, 7, 1123-1127.
Zeinab, B. and Elhan, S. (2015) The New Hybrid COAW Method for Solving Multi-Objective Optimization. International Journal in Foundations of Computer and Technology, 5, 15-22. https://doi.org/10.5121/ijfcst.2015.5602
Miettinen, K. (1998) Nonlinear Multi-Objective Optimization. International Series in Operations Research and Management Science, Kluwer Academic Publishing Group, Dordrecht. https://doi.org/10.1007/978-1-4615-5563-6
Taboada, H.A., Baheranwala, F. and Coit, D.W. (2007) Practical Solutions for Multi-Objective Optimization: An Application to System Reliability Design Problems. Reliability Engineering and System Safety, 92, 314-322. https://doi.org/10.1016/j.ress.2006.04.014
Ehrgott, M. (2005) Multi-Criteria Optimization. Springer, Berlin, Heidelberg.
Eskelinen, P., Miettinen, K., Klamroth, K. and Hakanen (2008) Pareto Navigator for Interactive Nonlinear Multi-Objective Optimization. Springer-Verlag, Berlin.
Manuel, L.I. and Stutzle, T. (2012) The Automatic Design of Multi-Objective Ant Colony Optimization Algorithms. IRIDIA-Technical Report Series, Technical Report No. TR/IRIDIA/2011-003.
Orths, A., Schmitt, A., Styczyuskiz, A. and Verstege, J. (2001) Multi-Criteria Optimization Methods for Planning and Operation of Electrical Energy System. Electrical Engineering, 83, 251-258. https://doi.org/10.1007/s002020100085
Schmitt, A. and Verstage, J.F. (2001) A Multi-Criteria Optimization of Ancillary Services with Pareto-Based Evolutionary Strategies. Proceeding of IEEE Porto Power Conference, Porto, 10-15 September 2001, 70-78.
Fonseca, C.M. and Fleming, P.J. (1995) An Overview of Evolutionary Algorithms in Multi-Objective Optimization. Evolutionary Computing, 3, 1-16. https://doi.org/10.1162/evco.1995.3.1.1
French, S. (1984) Interactive Multi-Objective Programming, Its Aims, Applications and Demands. Journal of Operations Research Society, 35, 827-834. https://doi.org/10.1057/jors.1984.165
Marler, R.T. and Arora, J.S. (2004) Survey of Multi-Objective Optimization Methods for Engineering. Structural Multi-Disciplinary Optimization, 26, 369-395. https://doi.org/10.1007/s00158-003-0368-6
Collette, Y. and Siarry, P. (2009) Multi-Objective Optimization: Principles and Case Studies (Decision Engineering). Springer-Verlag, Berlin.
Stadler (1988) Multi-Criteria Optimization in Engineering and the Sciences. Kluwer Academic Publishing Group, Dordrecht. https://doi.org/10.1007/978-1-4899-3734-6
Johan, A. (2000) A Survey of Multi-Objective Optimization in Engineering Design. Technical Report L/THIK-R-109, Department of Mechanical Engineering, Linkoping University, Linkoping.
Giagkiozis, I. and Fleminng, P.J. (2015) Methods for Multi-Objective Optimization: An Analysis. Information Sciences, 293, 338-350. https://doi.org/10.1016/j.ins.2014.08.071 http://www.elsevier.com/locate/ins
Kim, I.Y. and de Weck, O.L. (2005) Adaptive Weighted Sum Method for Bi-Objective Optimization. Structural and Multidisciplinary Optimization, 29, 149-158. https://doi.org/10.1007/s00158-004-0465-1
Alaa, S., Abdel, K.B., Mohamed, A. and Noor, K. (2012) Multi-Objective Evolutionary Computation Solution for Chocolate Production System Using Pareto Method. International Journal of Computer Science, 9, 75-83.
Subhamoy, C. and Sugata (2015) An Elitist Simulated Annealing Algorithm for Solving Multi-Objective Optimization Problems in Internet of Design. International Journal Advanced Network and Applications, 7, 2784-2789.
Mausser, H. (2006) Normalization and Other Topics in Multi-Objective Optimization. Proceedings of the Fields—MITACS Industrial Problems Workshop, Toronto, 1 August 2006, 89-101.
Wilfried, J. and Blum, C. (2014) Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts. Algorithms, 7, 166-185. https://doi.org/10.3390/a7010166
Caramia, M. and Dell’Olmo, P. (2008) Multi-Objective Management in Freight Logistics Increasing Capacity, Services Level and Safety with Optimization Algorithms. Springer, Berlin. http://www.springer.com/978-1-84800-381-1
Janina, A.K. (2005) The Ant Colony Algorithms for Rule Induction. AIML Conference, Cairo, 19-21 December 2005, 50-55. http://www.icgst.com
Gulben, C. and Orhan, Y. (2015) An Improved Ant Colony Optimization Algorithm for Construction Site Layout Problems. Journal of Building Construction and Planning Research, 3, 221-232. https://doi.org/10.4236/jbcpr.2015.34022
Dhiman, P. and Hooda, R. (2014) An Enhanced Ant Colony Optimization Based Image Edge Detection. International Journal of Advanced Research in Computer Science and Software Engineering, 4, 923-933.
Deneubourg, J.L., Aron, S., Goss, S. and Pasteels, M. (1990) The Self-Organising Exploratory Patterns of the Argentine Ants. Journal of Insects Behaviour, 3, 159-168. https://doi.org/10.1007/BF01417909
Rojee, P., Eiichi, T. and Tadashi, Y. (2010) Optimization of Vehicle Routing and Scheduling Problem Time Window Constraints in Hazardous Material Transportation. Journal of the Eastern Asia Society for Transportation Studies, 8, 790-803.
Anuj, K.G., Harsh, S. and Verma, K. (2012) MANET Routing Protocols Based on Ant Colony Optimization. International Journal of Modelling and Optimization, 2, 42.
Zaninudin, Z. and Paputungan, T.V. (2013) A Hybrid Optimization Algorithm Based on Genetic Algorithm and Ant Colony Optimization. International Journal of Artificial Intelligence and Applications, 4, 63-75. https://doi.org/10.5121/ijaia.2013.4505
Dorigo (1992) Optimization Learning and Natural Algorithms. Unpublished PhD Thesis, Dipartimento di Eletronica, Politecnico di Milano, Milano.
Stutzle, T. and Hoos, H. (1997) Max-Min Ant System and Local Search for the Travelling Salesman Problem. In: IEEE International Conference on Evolutionary Computation, IEEE Press, Piscataway, 309-314.
Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System, a Cooperative Learning Approach to the Travelling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66. https://doi.org/10.1109/4235.585892
Aniruth, S., Pratik, P. and Dinesh, B. (2009) Ant Colony Optimization Algorithms: Introduction and Beyond. Artificial Intelligence Seminar, Bombay, 5-10 August, 2009, 1-41.
Majid, Y.K. and Mohammad, S. (2011) An Optimization Algorithm for Capacitated Vehicle Routing Problem Based on Ant Colony System. Australian Journal of Basic and Applied Sciences, 5, 2729-2737.