The Differential Evolution (DE) is a widely used bioinspired optimization algorithm developed by Storn and Price. It is popular for its simplicity and robustness. This algorithm was primarily designed for real-valued problems and continuous functions, but several modified versions optimizing both integer and discrete-valued problems have been developed. The discrete-coded DE has been mostly used for combinatorial problems in a set of enumerative variants. However, the DE has a great potential in the spatial data analysis and pattern recognition. This paper formulates the problem as a search of a combination of distinct vertices which meet the specified conditions. It proposes a novel approach called the Multidimensional Discrete Differential Evolution (MDDE) applying the principle of the discrete-coded DE in discrete point clouds (PCs). The paper examines the local searching abilities of the MDDE and its convergence to the global optimum in the PCs. The multidimensional discrete vertices cannot be simply ordered to get a convenient course of the discrete data, which is crucial for good convergence of a population. A novel mutation operator utilizing linear ordering of spatial data based on the space filling curves is introduced. The algorithm is tested on several spatial datasets and optimization problems. The experiments show that the MDDE is an efficient and fast method for discrete optimizations in the multidimensional point clouds.

Department of Computer Science and National Supercomputing Center VŠB Technical University of Ostrava Ostrava Czech Republic

Zobrazit více v PubMed

Harrison A., Newman P. High quality 3D laser ranging under general vehicle motion. Proceedings of the 2008 IEEE International Conference on Robotics and Automation (ICRA '08); May 2008; Pasadena, Calif, USA. pp. 7–12. DOI

Uher V., Gajdoš P., Ježowicz T., Snášel V. Innovations in Bio-Inspired Computing and Applications: Proceedings of the 6th International Conference on Innovations in Bio-Inspired Computing and Applications (IBICA 2015) held in Kochi, India during December 16–18, 2015. Vol. 424. Berlin, Germany: Springer; 2016. Application of hexagonal coordinate systems for searching the K-NN in 2D space; pp. 209–220. (Advances in Intelligent Systems and Computing). DOI

Núñez P., Vázquez-Martín R., del Toro J. C., Bandera A., Sandoval F. Feature extraction from laser scan data based on curvature estimation for mobile robotics. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '06); May 2006; Orlando, Fla, USA. IEEE; pp. 1167–1172. DOI

Qing A. Differential Evolution: Fundamentals and Applications in Electrical Engineering. New York, NY, USA: John Wiley & Sons; 2009.

Mo H., Li Z. Bio-geography based differential evolution for robot path planning. Proceedings of the IEEE International Conference on Information and Automation (ICIA '12); June 2012; Shenyang, China. IEEE; pp. 1–6. DOI

Ugolotti R., Cagnoni S. Differential evolution based human body pose estimation from point clouds. Proceedings of the 2013 15th Annual Conference Genetic and Evolutionary Computation (GECCO '13); July 2013; Amsterdam, The Netherlands. ACM; pp. 1389–1396. DOI

Cuevas E., Zaldivar D., Pérez-Cisneros M., Ramírez-Ortegón M. Circle detection using discrete differential evolution optimization. Pattern Analysis and Applications. 2011;14(1):93–107. doi: 10.1007/s10044-010-0183-9. DOI

Storn R., Price K. Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. 1997;11(4):341–359. doi: 10.1023/a:1008202821328. DOI

Onwubolu G. C., Davendra D. Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization. 1st. Berlin, Germany: Springer Publishing Company, Incorporated; 2009.

Balamurugan R., Subramanian S. Hybrid integer coded differential evolution—dynamic programming approach for economic load dispatch with multiple fuel options. Energy Conversion and Management. 2008;49(4):608–614. doi: 10.1016/j.enconman.2007.07.039. DOI

Uyar A. Ş., Türkay B., Keleş A. A novel differential evolution application to short-term electrical power generation scheduling. International Journal of Electrical Power and Energy Systems. 2011;33(6):1236–1242. doi: 10.1016/j.ijepes.2011.01.036. DOI

Deng C.-S., Zhao B.-Y., Deng A.-Y., Liang C.-Y. Hybrid-coding Binary Differential Evolution algorithm with application to 0-1 knapsack problems. Proceedings of the International Conference on Computer Science and Software Engineering (CSSE '08); December 2008; pp. 317–320. DOI

Fatih Tasgetiren M., Suganthan P. N., Pan Q.-K. An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem. Applied Mathematics and Computation. 2010;215(9):3356–3368. doi: 10.1016/j.amc.2009.10.027. DOI

Tasgetiren M. F., Pan Q.-K., Liang Y.-C. A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers and Operations Research. 2009;36(6):1900–1915. doi: 10.1016/j.cor.2008.06.007. DOI

Zhang J., Wu Y., Guo Y., Wang B., Wang H., Liu H. A hybrid harmony search algorithm with differential evolution for day-ahead scheduling problem of a microgrid with consideration of power flow constraints. Applied Energy. 2016;183:791–804. doi: 10.1016/j.apenergy.2016.09.035. DOI

Sivasubramani S., Swarup K. S. Multiagent based differential evolution approach to optimal power flow. Applied Soft Computing Journal. 2012;12(2):735–740. doi: 10.1016/j.asoc.2011.09.016. DOI

Yan P., Wang G., Che A., Li Y. Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance. Computers & Operations Research. 2016;76:155–166. doi: 10.1016/j.cor.2016.06.011. DOI

Ma K., Yan P., Dai W. A hybrid discrete differential evolution algorithm for dynamic scheduling in robotic cells. Proceedings of the 13th International Conference on Service Systems and Service Management (ICSSSM '16); June 2016; Kunming, China. DOI

Do D. T., Lee S., Lee J. A modified differential evolution algorithm for tensegrity structures. Composite Structures. 2016;158:11–19. doi: 10.1016/j.compstruct.2016.08.039. DOI

Zhang H., Yan Q., Liu Y., Jiang Z. An integer-coded differential evolution algorithm for simple assembly line balancing problem of type 2. Assembly Automation. 2016;36(3):246–261. doi: 10.1108/AA-11-2015-089. DOI

Chakraborty J., Konar A., Chakraborty U. K., Jain L. C. Distributed cooperative multi-robot path planning using differential evolution. Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC '08); June 2008; Hong Kong. IEEE World Congress on Computational Intelligence; pp. 718–725. DOI

Coelho L. D. S., Nedjah N., Mourelle L. D. M. Differential Evolution Approach Using Chaotic Sequences Applied to Planning of Mobile Robot in a Static Environment with Obstacles. Berlin, Germany: Springer; 2007. Mobile robots: the evolutionary approach; pp. 3–22.

Lichtblau D. Differential evolution in discrete optimization. International Journal of Swarm Intelligence and Evolutionary Computation. 2012;1:10. doi: 10.4303/ijsiec/z110301. DOI

Das S., Suganthan P. N. Differential evolution: a survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation. 2011;15(1):4–31. doi: 10.1109/tevc.2010.2059031. DOI

Zhang Y., Wang S., Ji G. A comprehensive survey on particle swarm optimization algorithm and its applications. Mathematical Problems in Engineering. 2015;2015:38. doi: 10.1155/2015/931256.931256 DOI

Liao T. W. Two hybrid differential evolution algorithms for engineering design optimization. Applied Soft Computing Journal. 2010;10(4):1188–1199. doi: 10.1016/j.asoc.2010.05.007. DOI

Lampinen J., Zelinka I. Mixed integer-discrete-continuous optimization by differential evolution. Proceedings of the 5th International Conference on Soft Computing; 1999; pp. 77–81.

Lampinen J., Zelinka I. Mixed integer-discrete-continuous optimization by differential evolution—part 2: a practical example. Proceedings of the 5th International Mendel Conference on Soft Computing (MENDEL '99); June 1999; Brno, Czech Republic. Brno University of Technology; pp. 77–81.

Davendra D., Onwubolu G. Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization. Berlin, Germany: Springer; 2009. Forward backward transformation; pp. 35–80.

Gajdoš P., Zelinka I. On the influence of different number generators on results of the symbolic regression. Soft Computing. 2014;18(4):641–650. doi: 10.1007/s00500-013-1172-x. DOI

Yuan X., Su A., Nie H., Yuan Y., Wang L. Application of enhanced discrete differential evolution approach to unit commitment problem. Energy Conversion and Management. 2009;50(9):2449–2456. doi: 10.1016/j.enconman.2009.05.033. DOI

Angira R., Babu B. V. Optimization of process synthesis and design problems: a modified differential evolution approach. Chemical Engineering Science. 2006;61(14):4707–4721. doi: 10.1016/j.ces.2006.03.004. DOI

Schmidt H., Thierauf G. A combined heuristic optimization technique. Advances in Engineering Software. 2005;36(1):11–19. doi: 10.1016/j.advengsoft.2003.12.001. DOI

Fatih Tasgetiren M., Ke Pan Q., Suganthan P., Liang Y.-C. A discrete differential evolution algorithm for the no-wait flowshop scheduling problem with total flowtime criterion. Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling (SCIS '07); April 2007; pp. 251–258.

Datta D., Figueira J. R. A real-integer-discrete-coded differential evolution. Applied Soft Computing Journal. 2013;13(9):3884–3893. doi: 10.1016/j.asoc.2013.05.001. DOI

Ugolotti R., Micconi G., Aleotti J., Cagnoni S. Applications of Evolutionary Computation: 17th European Conference, EvoApplications 2014, Granada, Spain, April 23–25, 2014, Revised Selected Papers. Berlin, Germany: Springer; 2014. GPU-based point cloud recognition using evolutionary algorithms; pp. 489–500.

Das S., Abraham A., Konar A. Automatic clustering using an improved differential evolution algorithm. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans. 2008;38(1):218–237. doi: 10.1109/tsmca.2007.909595. DOI

Fraga L. G., Coello Coello C. A. A review of applications of evolutionary algorithms in pattern recognition. In: Wang P. S. P., editor. Pattern Recognition, Machine Intelligence and Biometrics. Berlin, Germany: Springer; 2011. pp. 3–28.

Corrochano E., Eklundh J. Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications: 14th Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, México, November 15–18, 2009. Proceedings. Vol. 5856. Berlin, Germany: Springer; 2009. (Image Processing, Computer Vision, Pattern Recognition, and Graphics).

Ugolotti R., Nashed Y. S. G., Mesejo P., Ivekovič S., Mussi L., Cagnoni S. Particle swarm optimization and differential evolution for model-based object detection. Applied Soft Computing. 2013;13(6):3092–3150. doi: 10.1016/j.asoc.2012.11.027. DOI

Cuevas E., González M., Zaldívar D., Pérez-Cisneros M. Multi-ellipses detection on images inspired by collective animal behavior. Neural Computing and Applications. 2014;24(5):1019–1033. doi: 10.1007/s00521-012-1332-4. DOI

Chandar K. P., Savithri T. S. 3D face model estimation based on similarity transform using differential evolution optimization. Procedia Computer Science. 2015;54:621–630. doi: 10.1016/j.procs.2015.06.072. DOI

Storn R., Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. 1995

Mezura-Montes E., Velázquez-Reyes J., Coello Coello C. A. A comparative study of differential evolution variants for global optimization. Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference (GECCO '06); July 2006; Seattle, Wash, USA. ACM; pp. 485–492.

Koziel S., Michalewicz Z. Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization. Evolutionary Computation. 1999;7(1):19–44. doi: 10.1162/evco.1999.7.1.19. PubMed DOI

Gao Y., Sun Y., Wu J. Difference-genetic co-evolutionary algorithm for nonlinear mixed integer programming problems. Journal of Nonlinear Science and Its Applications. 2016;9(3):1261–1284.

Butz A. R. Convergence with Hilbert's space filling curve. Journal of Computer and System Sciences. 1969;3(2):128–146. doi: 10.1016/s0022-0000(69)80010-3. DOI

Breinholt G., Schierz C. Algorithm 781: generating Hilbert's space-filling curve by recursion. ACM Transactions on Mathematical Software. 1998;24(2):184–189. doi: 10.1145/290200.290219. DOI

Lawder J. K., King P. J. H. Advances in Databases: 17th British National Conference on Databases, BNCOD 17 Exeter, UK, July 3–5, 2000 Proceedings. Berlin, Germany: Springer; 2000. (Lecture Notes in Computer Science).

Skilling J. Programming the hilbert curve. Proceedings of the Bayesian Inference and Maximum Entropy Methods; 2004; Jackson Hole, Wyo, USA. pp. 381–387. DOI

Skopal T., Krátký M., Pokorný J., Snášel V. A new range query algorithm for universal B-trees. Information Systems. 2006;31(6):489–511. doi: 10.1016/j.is.2004.12.001. DOI

Eberly D. Distance between point and line, ray, or line segment. April 2016, http://www.geometrictools.com/Source/Distance3D.html.

Yang X.-S., editor. Nature-Inspired Optimization Algorithms. Oxford, UK: Elsevier; 2014. Appendix a—test function benchmarks for global optimization.

Fischer K., Gärtner B., Kutz M. Fast smallest-enclosing-ball computation in high dimensions. In: Di Battista G., Zwick U., editors. Algorithms—ESA 2003. Vol. 2832. Berlin, Germany: Springer; 2003. pp. 630–641. (Lecture Notes in Computer Science). DOI

The stanford 3d scanning repository, 2016, http://graphics.stanford.edu/data/3Dscanrep/