Optimization Algorithm’s Problems: Comparison Study
https://doi.org/10.24017/science.2017.3.15
Abstract views: 1067 / PDF downloads: 897Abstract
Currently, in various fields and disciplines problem optimization are used commonly. In this concern, we have to define solutions which are two known concepts optimal or near optimal optimization problems in regards to some objects. Usually, it is surely difficult to sort problems out in only one step, but some processes can be followed by us which people usually call it problem solving. Frequently, the solution process is split into various steps which are accomplishing one after the other. Therefore, in this paper we consider some algorithms that help us to sort out problems, for exemplify, finding the shortest path, minimum spanning tree, maximum network flows and maximum matching. More importantly, the algorithm comparison will be presented. Additionally, the limitation of each algorithm. The last but not the least, the future research in this area will be approached.
Keywords:
Algorithm, problem solving, shortest path, minimum spanning tree, network flows.
References
[1]. R. Kümmerle, G. Grisetti, H. Strasdat, K. Konolige and W. Burgard, "G2o: A general framework for graph optimization," 2011 IEEE International Conference on Robotics and Automation, Shanghai, 2011, pp. 3607-3613.
[2]. G. S. Halford, R. Baker, J. E. McCredden, and J. D. Bain, "How Many Variables Can Humans Process?," Psychological Science, vol. 16, no. 1, pp. 70-76, Jan. 2005.
https://doi.org/10.1111/j.0956-7976.2005.00782.x
[3]. X.-S. Yang, "Flower Pollination Algorithm for Global Optimization," in Unconventional Computation and Natural Computation, 2012, pp. 240-249.
https://doi.org/10.1007/978-3-642-32894-7_27
[4]. R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
[5]. A. V. Goldberg, "Recent developments in maximum flow algorithms," in Algorithm Theory - SWAT'98, 1998, pp. 1-10.
https://doi.org/10.1007/BFb0054350
[6]. B. Korte and J. Vygen, Combinatorial Optimization, 1st ed. Berlin: Springer Berlin, 2014.
[7]. A. Alazzam and H. W., "A New Optimization Algorithm For Combinatorial Problems", International Journal of Advanced Research in Artificial Intelligence, vol. 2, no. 5, 2013.
https://doi.org/10.14569/IJARAI.2013.020510
[8]. X.-S. Yang, M. Karamanoglu, and X. He, "Multi-objective Flower Algorithm for Optimization," Procedia Computer Science, vol. 18, pp. 861-868, Jan. 2013.
https://doi.org/10.1016/j.procs.2013.05.251
[9]. Xin?She Yang and Amir Hossein Gandomi, "Bat algorithm: a novel approach for global engineering optimization," Engineering Computations, vol. 29, no. 5, pp. 464-483, Jul. 2012.
https://doi.org/10.1108/02644401211235834
[10]. Y.-Q. Cheng, V. Wu, R. Collins, A. R. Hanson, and E. M. Riseman, "Maximum-weight bipartite matching technique and its application in image feature matching," 1996, vol. 2727, pp. 453-462.
https://doi.org/10.1117/12.233261
[11]. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to algorithms, 1st ed. Cambridge, Massachusetts: The MIT Press, 2014.
[12]. T. Weise, R. Chiong, and K. Tang, "Evolutionary Optimization: Pitfalls and Booby Traps," J. Comput. Sci. Technol., vol. 27, no. 5, pp. 907-936, Sep. 2012
https://doi.org/10.1007/s11390-012-1274-4
[13].T. Weise et al., "Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem," in IEEE Computational Intelligence Magazine, vol. 9, no. 3, pp. 40-52, Aug. 2014.
https://doi.org/10.1109/MCI.2014.2326101
[14]. T. Weise and K. Tang, "Evolving Distributed Algorithms With Genetic Programming," in IEEE Transactions on Evolutionary Computation, vol. 16, no. 2, pp. 242-265, April 2012.
https://doi.org/10.1109/TEVC.2011.2112666
[15]. T. Weise, M. Wan, P. Wang, K. Tang, A. Devert and X. Yao, "Frequency Fitness Assignment," in IEEE Transactions on Evolutionary Computation, vol. 18, no. 2, pp. 226-243, April 2014.
https://doi.org/10.1109/TEVC.2013.2251885
[16]. K. Weicker, Evolutionary algorithms and dynamic optimization problems, 1st ed. Osnabru?ck: Der AndereVerl., 2003.
[17]. A. Singh, "An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem," Applied Soft Computing, vol. 9, no. 2, pp. 625-631, Mar. 2009.
https://doi.org/10.1016/j.asoc.2008.09.001
[18]. F. Ortega and L. A. Wolsey, "A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem," Networks, vol. 41, no. 3, pp. 143-158, May 2003.
https://doi.org/10.1002/net.10068
[19]. D. S. Hochbaum, "The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem," Operations Research, vol. 56, no. 4, pp. 992-1009, Aug. 2008.
https://doi.org/10.1287/opre.1080.0524
[20]. J. M. Drake and D. M. Lodge, "Global hot spots of biological invasions: evaluating options for ballast-water management," Proceedings of the Royal Society of London B: Biological Sciences, vol. 271, no. 1539, pp. 575-580, Mar. 2004.
https://doi.org/10.1098/rspb.2003.2629
[21]. V. Vineet and P. J. Narayanan, "CUDA cuts: Fast graph cuts on the GPU," 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, Anchorage, AK, 2008, pp. 1-8.
https://doi.org/10.1109/CVPRW.2008.4563095
[22]. G. Menichetti, L. Dall'Asta, and G. Bianconi, "Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes," Phys. Rev. Lett., vol. 113, no. 7, p. 078701, Aug. 2014.
https://doi.org/10.1103/PhysRevLett.113.078701
[23]. S. Szeider, "Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable," Journal of Computer and System Sciences, vol. 69, no. 4, pp. 656-674, Dec. 2004.
https://doi.org/10.1016/j.jcss.2004.04.009
[24]. C.-G. Quimper, A. López-Ortiz, P. van Beek, and A. Golynski, "Improved Algorithms for the Global Cardinality Constraint," in Principles and Practice of Constraint Programming - CP 2004, 2004, pp. 542-556.
https://doi.org/10.1007/978-3-540-30201-8_40
[25]. N. Blum, A simplified realization of the Hopcroft Karp approach to maximum matching in general graphs, 1st ed. Bonn: Inst. fu?rInformatik, 1999.
[26]. V. Kolmogorov, "Blossom V: a new implementation of a minimum cost perfect matching algorithm," Math. Prog. Comp., vol. 1, no. 1, pp. 43-67, Jul. 2009.
https://doi.org/10.1007/s12532-009-0002-8
[27]. G. Bebek, V. Patel, and M. R. Chance, "PETALS: Proteomic Evaluation and Topological Analysis of a mutated Locus' Signaling," BMC Bioinformatics, vol. 11, p. 596, 2010.
https://doi.org/10.1186/1471-2105-11-596
[2]. G. S. Halford, R. Baker, J. E. McCredden, and J. D. Bain, "How Many Variables Can Humans Process?," Psychological Science, vol. 16, no. 1, pp. 70-76, Jan. 2005.
https://doi.org/10.1111/j.0956-7976.2005.00782.x
[3]. X.-S. Yang, "Flower Pollination Algorithm for Global Optimization," in Unconventional Computation and Natural Computation, 2012, pp. 240-249.
https://doi.org/10.1007/978-3-642-32894-7_27
[4]. R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
[5]. A. V. Goldberg, "Recent developments in maximum flow algorithms," in Algorithm Theory - SWAT'98, 1998, pp. 1-10.
https://doi.org/10.1007/BFb0054350
[6]. B. Korte and J. Vygen, Combinatorial Optimization, 1st ed. Berlin: Springer Berlin, 2014.
[7]. A. Alazzam and H. W., "A New Optimization Algorithm For Combinatorial Problems", International Journal of Advanced Research in Artificial Intelligence, vol. 2, no. 5, 2013.
https://doi.org/10.14569/IJARAI.2013.020510
[8]. X.-S. Yang, M. Karamanoglu, and X. He, "Multi-objective Flower Algorithm for Optimization," Procedia Computer Science, vol. 18, pp. 861-868, Jan. 2013.
https://doi.org/10.1016/j.procs.2013.05.251
[9]. Xin?She Yang and Amir Hossein Gandomi, "Bat algorithm: a novel approach for global engineering optimization," Engineering Computations, vol. 29, no. 5, pp. 464-483, Jul. 2012.
https://doi.org/10.1108/02644401211235834
[10]. Y.-Q. Cheng, V. Wu, R. Collins, A. R. Hanson, and E. M. Riseman, "Maximum-weight bipartite matching technique and its application in image feature matching," 1996, vol. 2727, pp. 453-462.
https://doi.org/10.1117/12.233261
[11]. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to algorithms, 1st ed. Cambridge, Massachusetts: The MIT Press, 2014.
[12]. T. Weise, R. Chiong, and K. Tang, "Evolutionary Optimization: Pitfalls and Booby Traps," J. Comput. Sci. Technol., vol. 27, no. 5, pp. 907-936, Sep. 2012
https://doi.org/10.1007/s11390-012-1274-4
[13].T. Weise et al., "Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem," in IEEE Computational Intelligence Magazine, vol. 9, no. 3, pp. 40-52, Aug. 2014.
https://doi.org/10.1109/MCI.2014.2326101
[14]. T. Weise and K. Tang, "Evolving Distributed Algorithms With Genetic Programming," in IEEE Transactions on Evolutionary Computation, vol. 16, no. 2, pp. 242-265, April 2012.
https://doi.org/10.1109/TEVC.2011.2112666
[15]. T. Weise, M. Wan, P. Wang, K. Tang, A. Devert and X. Yao, "Frequency Fitness Assignment," in IEEE Transactions on Evolutionary Computation, vol. 18, no. 2, pp. 226-243, April 2014.
https://doi.org/10.1109/TEVC.2013.2251885
[16]. K. Weicker, Evolutionary algorithms and dynamic optimization problems, 1st ed. Osnabru?ck: Der AndereVerl., 2003.
[17]. A. Singh, "An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem," Applied Soft Computing, vol. 9, no. 2, pp. 625-631, Mar. 2009.
https://doi.org/10.1016/j.asoc.2008.09.001
[18]. F. Ortega and L. A. Wolsey, "A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem," Networks, vol. 41, no. 3, pp. 143-158, May 2003.
https://doi.org/10.1002/net.10068
[19]. D. S. Hochbaum, "The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem," Operations Research, vol. 56, no. 4, pp. 992-1009, Aug. 2008.
https://doi.org/10.1287/opre.1080.0524
[20]. J. M. Drake and D. M. Lodge, "Global hot spots of biological invasions: evaluating options for ballast-water management," Proceedings of the Royal Society of London B: Biological Sciences, vol. 271, no. 1539, pp. 575-580, Mar. 2004.
https://doi.org/10.1098/rspb.2003.2629
[21]. V. Vineet and P. J. Narayanan, "CUDA cuts: Fast graph cuts on the GPU," 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, Anchorage, AK, 2008, pp. 1-8.
https://doi.org/10.1109/CVPRW.2008.4563095
[22]. G. Menichetti, L. Dall'Asta, and G. Bianconi, "Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes," Phys. Rev. Lett., vol. 113, no. 7, p. 078701, Aug. 2014.
https://doi.org/10.1103/PhysRevLett.113.078701
[23]. S. Szeider, "Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable," Journal of Computer and System Sciences, vol. 69, no. 4, pp. 656-674, Dec. 2004.
https://doi.org/10.1016/j.jcss.2004.04.009
[24]. C.-G. Quimper, A. López-Ortiz, P. van Beek, and A. Golynski, "Improved Algorithms for the Global Cardinality Constraint," in Principles and Practice of Constraint Programming - CP 2004, 2004, pp. 542-556.
https://doi.org/10.1007/978-3-540-30201-8_40
[25]. N. Blum, A simplified realization of the Hopcroft Karp approach to maximum matching in general graphs, 1st ed. Bonn: Inst. fu?rInformatik, 1999.
[26]. V. Kolmogorov, "Blossom V: a new implementation of a minimum cost perfect matching algorithm," Math. Prog. Comp., vol. 1, no. 1, pp. 43-67, Jul. 2009.
https://doi.org/10.1007/s12532-009-0002-8
[27]. G. Bebek, V. Patel, and M. R. Chance, "PETALS: Proteomic Evaluation and Topological Analysis of a mutated Locus' Signaling," BMC Bioinformatics, vol. 11, p. 596, 2010.
https://doi.org/10.1186/1471-2105-11-596
Downloads
How to Cite
[1]
R. M. Nabi, R. Azad, S. Saeed, and R. M. Nabi, “Optimization Algorithm’s Problems: Comparison Study”, KJAR, vol. 2, no. 3, pp. 25–31, Aug. 2017, doi: 10.24017/science.2017.3.15.
Published
27-08-2017
Issue
Section
Pure and Applied Science
