key: cord-0058867-ffafybin authors: Lucca, Natiele; Schepke, Claudio title: A New Library of Bio-Inspired Algorithms date: 2020-08-24 journal: Computational Science and Its Applications - ICCSA 2020 DOI: 10.1007/978-3-030-58799-4_35 sha: 6730c8c5fc1082ff3dbde6cc030ccce2046bc93c doc_id: 58867 cord_uid: ffafybin Real engineering, science, and economics problems cannot be ever solved exactly due to the high computation time to find the optimal solution. One way to solve such problems is to apply bio-inspired algorithms, to minimize the time to search for potential solutions. Bio-inspired algorithms are based on the collective behavior of social organisms and are used to solve optimization problems. This article presents a new library of bio-inspired algorithms. The library offers the implementation of some algorithms, being easily extensible through interfaces. An evaluation was made using 7 test functions applied to each of the implemented algorithms. The tests have shown that the ABC algorithm obtained the best convergence results in 5 tests and the ACO algorithm in 2 tests. The resolution of a problem may not be achieved exactly due to the complexity given by a large number of variables and/or potential solutions. An algorithm that describes a problem sequentially may require a large processing capacity to find the optimal solution, that is, the best solution to the problem [12] . The time required for exact and sequential computing can vary from hours to years, which highlights the importance of approaches and techniques that optimize the execution of algorithms [8] . The problems mentioned above can be identified in several research areas, for example, in simulations of real activities involving engineering, science, and economics. Traveling salesman and vehicle routing are examples of classic problems. In this context, bio-inspired algorithms are an strategy to reduce the execution time, so that the solution is improved. These algorithms apply swarm intelligence or colony intelligence, or collective intelligence, which simulate the collective behavior of self-organized, distributed, autonomous, flexible, and dynamic systems [9] . The elements that integrate the swarm or colony can optimize a global objective through the collaborative search in space following specific rules [7] . According to [6] , algorithms of flocks of birds and the colony of social insects, such as ants and bees, are known examples in the literature. This article features a new library 1 for problem-solving using bio-inspired algorithms. The library implements the classic algorithms: Particle Swarm Optimization (PSO); Artificial Bee Colony (ABC); and Ant Colony Optimization (ACO), in addition to being extensible to other algorithms through interfaces created in C++ language. The purpose of this article is to evaluate the functioning of the proposed bioinspired algorithm library through test cases. With this, we want to measure the quality of convergence of numerical solutions. The contribution of this article is (a) to provide a new extensible library of bio-inspired algorithms; (b) evaluate the quality of the solutions. The paper is organized as follows. Section 2 presents the related works in a systematic way. Section 4 describes the development and testing methodology used to carry out this work. In the Sect. 5 the results are presented. Finally, in Sect. 6, the final considerations about the work are highlighted. A set of 25 optimization libraries available in the literature are present in [10] . The authors perform a comparative analysis, identifying the strengths and weaknesses of each library. The article looks at possible shortcomings and possibilities for future work since it seeks to provide complete material on the optimization tools. Of the tools evaluated, only six have bio-inspired implementations: ECJ 2 , EvA2 3 , FOM 4 , ParadisEO 5 , MALLBA 6 , and Opt4 7 . In addition to these libraries, we also found new implementations: PaGMO 8 and PyGMO 9 libraries. Table 1 characterizes the libraries of bio-inspired algorithms found in the literature. For each library, the following were identified: the programming language, the algorithms implemented, and whether licenses are required. All libraries have some selected algorithms implemented and the mostly use open source license. In our work, we propose a library implemented in C++ that provides the implementations of the PSO, ABC, and ACO algorithms, in addition to enabling the extension of new classes of bio-inspired algorithms. Swarm intelligence is a research area that explores the characteristics of swarms in the face of the way they seek food and interact. This approach allows real problems in different areas to be solved [6] . The Artificial Bee Colony (ABC) algorithm simulates the behavior of bees in collecting nectar. The colony is formed by three groups of bees: employed bees who explore and seek food sources that are possible solutions to the problem; onlooker bees that are recruited by the employed according to the quality of the source found; and scout bees that are employed bees that have found a bad source and abandoned them. The Ant Colony algorithm was proposed by [4] and inspired by the behavior of ants in the search for food. Ants leave the anthill in search of food sources, that is, they explore the search space by releasing pheromone along the way. During a certain period of time the ants search for a source of food, but those that find a source closer to the anthill concentrate a greater amount of pheromone, as they travel the path more than once. Therefore, the more chemistry a trail is, that is, the higher the concentration of pheromone, the more ants will be attracted to it. Thus, most ants tend to follow the same path [9] . The Particle Swarm optimization algorithm (PSO) was modeled after the social behavior of the flock of birds [5] . In PSO, the population of individuals or particles is grouped into a cluster (set of solutions). These particles simulate the behavior of birds through self-learning (cognitive component) and flock learning (social component), that is, they imitate their own success and that of neighboring individuals. From this behavior the particles can define new positions that direct them towards optimal solutions. Other examples of algorithms in this area of bio-inspired computing are the Genetic Algorithms (GS), Differential Evolution (DE), Simulated Annealing (SA), Evolution Strategies (ES) and Bee colonies Optimization (BCO). In this section, we present the methodological aspects related to the development, tests, and execution of the library. The bio-inspired library was developed in the C++ programming language, to facilitate programming and have resources that allow solving problems efficiently. This language is oriented to objects so it allows abstraction, encapsulation, inheritance, and polymorphism, which is essential for good code generation practices. The language also offers libraries for manipulating vectors and matrices and for generating random values. These contribute to the implementation of swarm intelligence algorithms. The bio-inspired computation algorithms selected for this study belong to the swarm intelligence class, thus simulating the behavior of agents before the colony. The ABC, ACO, and PSO algorithms were chosen, as they have desirable characteristics for the optimization of problems that cannot be solved or solved in polynomial time. The source code of the ABC, ACO and PSO algorithms is organized in 3 directories: include, main and src. The first directory contains the files of extension hpp, that is, the header files that define the classes and methods. The main directory contains the execution initialization file, the implementation of the benchmark equations used in the tests, and an auxiliary file that contains the methods for executing. The src directory contains the implemented source codes. In addition to the directories, the library also contains a script for executing the tests, called run.sh and a file README, a text document with information and usage details for the library. The Table 2 shows the related file structure for each algorithm. To use the library, the user must instantiate an object that corresponds to the class of the chosen algorithm. To validate the implementation, it is necessary to verify the characteristics of the algorithm through tests. In this work, the tests were done by functions that have different properties, to ensure that the tested algorithm can or cannot solve certain types of optimization efficiently [13] . The quality of the optimization functions can be assessed by the properties: unimodal and multimodal; twodimensional and N-dimensional; continuous and non-continuous; and convex, and non-convex [13] . A function that has only one optimal location is called a unimodal and functions with two or more optimal locations are called multimodal. Functions over two-dimensional space are classified as two-dimensional. The other functions are classified in this work as multidimensional or N-dimensional. A function is continuous when all points p in your domain D follow Eq. 1. A function is convex when the secant line joining two points is above the graph or if any point m ∈ D follows Eq. 2. Thus, to test the algorithms implemented in the bio-inspired library, a benchmark was developed as a base application composed of seven test functions. They are: Alpine, Booth, Easom, Griewank, Rastrigin, Rosenbrock and Sphere. These functions are presented in Table 3 . The characteristics of the functions such as agent size, search space, maximum number of iterations and minimum global were established according to [2, 9] , being described in Table 4 . All the minimization functions used in the tests are continuous. The final results comprise the average of 30 executions, as adopted in the work of [3] . An execution comprises the generation of the input files and execution. Input files are generated using the runDetails method. This method creates a folder called Inputs, which stores the input files generated during the method's execution. Then the sequential version is executed by the run method, and the population and the other random values of the code are initialized with the values of the files previously generated in the runDetails method. The run method return the best solution found by the algorithm and the execution time in seconds. The tests were performed on a workstation composed of 2 Intel R Xeon R Silver 4116 processors CPU. Each processor has 12 physical cores (24 threads) operating at the standard 2.1 GHz frequency and 3 GHz turbo frequency. The Table 3 . Benchmark functions [2] Benchmark Function Graphic main memory (RAM) is 96 GB in size and DDR4 technology. The operating system is Linux Debian kernel version 4.19.0-8 using GNU GCC 9.3 compiler with -O3 optimization flag and standard c++11. Test launches are automated through instructions in shell script. This language allows the creation of folders to store the output files of each test and the creation of loops on a command line, allowing the launch of 30 repetitions on each step of the execution. The language also makes it possible to redirect the output of methods to a file. In this way, the results of the executions are stored in a file of type .csv, with the name of the function, where each line of the file corresponds to the solution and the measured execution time. According to the studies of [1, 11] the number of agents responsible for determining the optimal global of a function corresponds to the range of 20 to 60 agents. Thus, the functions were tested for a population of 10 to 100 agents, varying from 10 to 10 units. Table 5 respectively show the results obtained in the tests for the PSO, ABC, and ACO algorithms, applying each of the 7 test functions and varying the size of the population. The tables show the numerical average of the solutions and average execution time in seconds. As shown in Table 4 , all tests have a global minimum value to be found equal to 0, with the exception of Easom, which has a minimum value of −1. Therefore, it is expected that the algorithms reach this value as the closest possible. Most of the algorithms evaluated obtained optimal solutions for the test functions analyzed, especially the ABC algorithm. However, the functions Rastrigin and Rosenbrock obtained, on average, less precise solutions, even using a larger number of iterations, as they are complex functions, since they have greater dimensionality. For the Alpine function, the ABC provided the best solution of all algorithms and ACO has close results to them. However, PSO has the best execution time for all populations evaluated and ABC has close results to them. ACO has the worst execution time. In Booth function tests, ABC has the best solution. PSO and ACO are close results with each other. PSO has the best execution time, followed by ABC and ACO, respectively. In the Easom function, all algorithms present results close to the ideal −1. However, ABC found the exact result in 7 population sizes. PSO achieved the best execution time. In Alpine, Booth, and Easom, the best execution time results for PSO are around two times faster than ABC, and ACO a dozen more than ABC. ACO presented the best solution for the Griewank function, reaching the exact solution in 8 of the 10 population size evaluated. PSO appearing to be stuck in a local minimum, presenting the worst solution. The best execution time for Griewank was obtained by the ABC algorithm and ACO the worst. In the Rastrigin and Rosenbrock function none of the algorithms achieved the exact results. However, the ABC algorithm presents the best solution in both functions. In Rastrigin ACO and PSO are close results. In terms of performance, ABC has also the best execution time for both cases. In the Sphere test, the ACO achieved results close to the exact solution. However, the best execution time was obtained for the PSO algorithm. When the solution was evaluated, the ABC algorithm obtained the best solutions for five of the algorithms: Alpine, Booth, Easom, Rastrigin and Rosenbrock, while the algorithm ACO obtained the best solutions for the Griewank and Sphere algorithms. PSO resulted in worse solutions than the ABC and ACO algorithms. The PSO algorithm was more efficient in terms of performance for the Alpine, Booth, Easom, and Sphere algorithms, while the ABC algorithm obtained the better performance rates for the Griewank and Rastrigin and Rosenbrock algorithms. The ACO algorithm obtained the lowest performance when compared to the other algorithms. The bio-inspired algorithms correspond to a range of efficient strategies for solving problems in several areas, from simple data analysis to complex problems such as distributed power generation or engineering simulations. The contribution of this work was to provide a library that allows the use of bio-inspired algorithms to solve problems. In this article, the numerical evaluation and performance of the proposed library were assessed. Tests of the PSO, ABC, and ACO algorithms were performed using 7 functions and 10 different population sizes for each function. The ABC algorithm was the best in most cases to find the optimal solution and with less execution time in other cases. As future work, it is intended to include new bio-inspired algorithms to the library. We also want to validate it by testing the algorithms on a real problem, such as that of distributed energy production. We also expect to reduce the execution time in a new version of the library using parallelization techniques. Particle swarm optimization based Diophantine equation solver BenchmarkFcns toolbox: a collection of benchmark functions for optimization Otimização de funções multimodais via técnica de inteligência computacional baseada em colônia de vaga-lumes Ant colony optimization Computational Intelligence: An Introduction A comprehensive survey: artificial bee colony (ABC) algorithm and applications Swarm Intelligence All the needles in a haystack: can exhaustive search overcome combinatorial chaos? Fundamentos de Otimização por Inteligência de enxames: Uma Visão Geral Hybrid metaheuristics and multi-agent systems for solving optimization problems: a review of frameworks and a comparative analysis Mathematicle modelling and applications of particle swarm optimization Parallel Programming-Techniques and Applications using Networked Workstations and Parallel Computers Test problems in optimization