The Bacterial Foraging Algorithm (BFOA) is a well-known swarm collective intelligence algorithm used to solve a variety of constraint optimization problems with wide success. Despite its universality, implementing the BFOA may be complex due to the calibration of multiple parameters. Moreover, the Two-Swim Modified Bacterial Foraging Optimization Algorithm (TS-MBFOA) is a state-of-the-art modification of the BFOA which may lead to solutions close to the optimal but with more parameters than the original BFOA. That is why in this paper we present the design using the Unified Modeling Language (UML) and the implementation in the MATLAB platform of a front-end for the TS-MBFOA algorithm to calibrate the algorithm parameters faster and with no need for editing lines of code. To test our proposal, we solve a numerical optimization problem with constraints known as tension/compression spring, where 30 independent executions were conducted using the TS-MBFOA and then compared with an earlier version called MBFOA. The runtime configuration and the parameter tuning were fluent using our front-end, and the TS-MBFOA obtained the better results. To date, there is no other user-friendly implementation of this specific algorithm in an open-source code, and the front-end is flexible enough to include other numerical optimization problems with minimal effort.
There are optimization problems considered complex due to their high dimensionality and their dynamic nature. An optimization problem is also known as a general non-linear programming problem and can be defined as:
Minimize or Maximize
Subject to:
In this definition,
These types of optimization problems are complex, and although they can be solved by mathematical programming, they can be complicated to implement. Currently, metaheuristics are efficient methods that allow to solve optimization problems with or without constraints, combinatorial or numerical, in an approximate way. That is, they generate one or more feasible solutions close to the optimum in reasonable times.
Some of these techniques emulate natural or evolutionary processes (grouped into the called bio-inspired algorithms), which are part of the bio-inspired computation field [
According to the natural phenomenon base of their design, bio-inspired algorithms are classified into two groups: Evolutionary Algorithms (EAs) who operate emulating the natural evolution process and the survival of the fittest [
Among CIAs we have the Bacterial Foraging Optimization Algorithm (BFOA) [
The natural process of BFOA is based on the fact that each bacterium tries to maximize its own energy obtained per unit of time used in the foraging process while it also evades harmful substances. Moreover, bacteria can communicate with each other by segregating substances. These characteristics are represented in four main processes in the BFOA: chemotaxis (swim-tumble), swarming, reproduction, and elimination-dispersion. Bacteria are potential solutions to the problem, and their location represents the values of the decision variables of the problem. Bacteria can move (generate new solutions) through the chemotaxis cycle, a movement is also generated by attracting solutions in promising areas to other solutions in the search space, reproduction of the best solutions is allowed, and those bacteria located in areas of poor quality are finally removed from the swarm.
The Modified Bacteria Foraging Optimization Algorithm (MBFOA) is a BFOA based algorithm. The modifications of the BFOA include a reduction in the parameters of the original BFOA by grouping in a generational cycle the four basic processes of the algorithm (initially an independent loop) and a mechanism for handling constraints based on feasibility rules [
In order to improve the performance of MBFOA to solve CNOPs, the Improved Modified Bacterial Foraging Optimization Algorithm (IMBFOA) was proposed. IMBFOA implements a skew mechanism to create the initial population, two swim operators, dynamic step sizes, and the Sequential Quadratic Programming (SQP) local search engine. This search engine aims to bring or introduce bacteria into the feasible region or take bacteria out of a local optimum and move them to another place within the feasible region [
Finally, the most recent adaptation is the Two-Swim Modified Bacterial Foraging Optimization Algorithm (TS-MBFOA), where two swims are added in the chemotaxis process: the first is the original swim (except for the step size, which is randomized), and the second swim includes the mutation operator used in evolutionary algorithms. Both swims are included with the objective of improving the exploration and exploitation capabilities of the algorithm [
Swarm intelligence algorithms and even evolutionary algorithms are widely used among the scientific community. However, in most cases only their pseudocodes or source codes are distributed. Coding, implementing and executing a metaheuristic algorithm may be a difficult task for end users unfamiliar with complex algorithms in programming languages. Specifically, the algorithm based on the foraging of bacteria is one of the popular ones in solving constraint numerical optimization problems. However, it is not common to find in the state of the art or specialized literature a graphical user interface that may allow end users to calibrate the algorithm parameters, run it, and view its results on some known test problems, all of this without need to edit lines of code.
A front-end for the TS-MBFOA may help the end-user perform the optimal calibration of parameters with minimum effort and time. In the context of human-computer interaction, a front-end consists of a software interface (such as a user interface, UI) designed to enable user-friendly interaction with a computer. That is why the implementation of the algorithm plus the UI is of the utmost importance for those who have the need to use the algorithm. Also, since the UI isolates the source code from the end user, he/she does not need of programming knowledge to interact directly with the calibration of the parameters and, therefore, in the execution of the algorithm.
In the specialized literature, there are several proposals developing UIs for the implementation of BFOA in particular problems; some of these are described below.
In [
In another work, BFOA has been implemented for planning route strategies for ships to avoid collisions. The UI has general-purpose components to facilitate the adjustment of the problem parameters: navigation direction, speed, longitude, and latitude. Also, this proposal displays a list showing a series of results and a graph corresponding to the possible collision [
A BFOA-based factorial order controller for a multi-area automatic generation control system with capacitive energy storage was proposed in [
In another work, BFOA was applied for the comparative analysis of the double watermark technique based on safe medical images [
To improve the recognition rate of a fingerprint verification system, BFOA was implemented along with a UI developed in MATLAB 7.11 in [
In [
In another work, BFOA was adapted for to optimize of multiple objectives to treat a medical image using a watermark and thus avoid damaging it. The proposal presents a UI that allows the user to manipulate the image easily [
In a previous work, we implemented TS-MBFOA for menu planning generating healthy menus. A UI was designed in language M under MATLAB R2009b, where the end-user inputs the personal data, and the healthy menu is automatically generated [
According to the revised proposals that implement BFOA with the help of a graphical interface, it is noticed that the typical development platform is MATLAB. All authors use the UI to enter the input data for the problem to be solved and show the results in graphs and tables that MATLAB can generate. In none of the cases reviewed, the UI is used to introduce and calibrate the algorithm input parameters. Furthermore, neither the performance of the algorithm is displayed using no performance metrics or graphs such as convergence. Finally, none of the proposals allow configuring a custom problem to be solved.
That is why the main objective of this article is to present the design and development of a front-end for the efficient adjustment of parameters of the TS-MBFOA in solving CNOPs.
TS-MBFOA is an algorithm derived from MBFOA, and adaptation of BFOA proposed specifically to solve CNOPs [
In the chemotaxis process, two swims are interspersed; in each cycle, only one of exploitation or exploration swims is performed. The process begins with the exploitation swim (classic swim). However, a bacterium will not necessarily intersperse exploration and exploitation when swimming, since if the new position of a given swim,
The exploration swim operator uses the mutation between bacteria and is calculated using:
The exploitation swim operator is calculated using:
In the middle loop of the chemotaxis process, the swarming operator defined in
In the reproduction process, bacteria are ordered according to the constraint-handling technique based on the feasibility rules, eliminating the worst bacteria
In the elimination-dispersion process, the worst bacterium of the population
Although a bias mechanism is used in the original TS-MBFOA proposal to generate the initial random population and a local search engine, this paper does not use these mechanisms to reduce computational cost. The pseudocode of TS-MBFOA is presented in Algorithm
Like all metaheuristic algorithms, TS-MBFOA has user-defined parameters (
Some algorithms are sensitive to their parameters, and this complicates the calibration. It is worth mentioning that the values of a parameter can be an integer or a real number. Usually, the authors of an algorithm mention the range values recommended for each parameter to solve a particular problem giving only an idea of the possible values that we can use.
The main goal of this work is to implement the TS-BFOA along with a front-end to be used by any researcher or academic interested in bacterial foraging algorithms. After the analysis phase, we create the corresponding design diagrams, implement the algorithm, and finally develop the UI. The development environment used was MATLAB R2018a.
To code TS-MBFOA and the front-end, a modular programming paradigm has been used to separate each individual process of the algorithm into independent modules to have clean programming of each process implementing functions and procedures.
We designed the prototype using the UML (Unified Modeling Language), a tool that captures the idea of a system through a set of symbols and diagrams [
To develop the TS-MBFOA front-end, we designed an activity diagram (
The activity diagram in
Modular programming provides many advantages, e.g., simplifying the design, decreasing the coding complexity, saving programming time (as it promotes the reusability of the code), favors teamwork, ease of debugging, testing, maintenance, and structuring of specific libraries. Moreover, this technique allows designing the solution of a problem based on modularization or segmentation, given a top-down approach [
This modularization or segmentation, in turn, can be repeatedly divided into smaller problems until the problems are easily solved. Each subproblem is desirable to be independent of the others and is called a module. The original problem is solved within the main program (also called driver or main) and subproblems (modules) through subprograms: procedures and functions [
An easy-to-understand programming language due to its practical syntax is the M language. This high-level language allows users to group frequently used sentences within a program that can be invoked later.
In this work, each of the processes of the TS-MBFOA algorithm is modulated for a quick understanding and easy adaptation, as shown in the package diagram in
The TS-MBFOA UI consists of two windows. The first window is for the calibration of parameters, information regarding the state of execution of the algorithm, and an option for data visualization. In the second window, results are presented.
• File menu: includes options to run a new execution, load a previous configuration and show general information of the front-end.
• Action buttons: the first button allows to save the configuration, the second one to start the algorithm's execution, the third button stops the current execution, and the fourth one is enabled when the execution ends and displays the second UI.
• Run settings: the left panel allows the user to name the test, choose the optimization problem, and set the number of iterations.
• Parameter calibration: this is the main panel and allows the user to set the number of bacteria (
• Process: the right panel shows the execution time of the algorithm.
• General configuration: shows the configuration and calibration of parameters for this execution.
• Results: this table shows the best solution found in each of the executions of the algorithm. Each solution shows the value of the variables along with the value of the objective function and the Constraint Violation Sum (CVS).
• Statistics: this panel presents the basic statistics such as: better, average, median, standard deviation, and worse value of the set of solutions in the Final results table. In addition, performance measures of the algorithm are presented, such as the feasibility rate, success rate, and successful performance [
• TS-MBFOA convergence: this graph shows the algorithm's convergence for the median value of the set of solutions. It is helpful to show the behavior of the algorithm.
• Export data: it allows to export results to a spreadsheet file.
The sequence diagram in
To test our front-end, we chose the CNOP known as the Tension/Compression Spring. For this specific problem, the best optimal value known in the state of the art is
We use MATLAB R2018b to conduct the test on a laptop with an Intel(R) Core i5 CPU@1.60 GHz processor, 8GB RAM, and 64-bit Windows 10 Operating System.
In the Tension/compression spring problem, the aim is to minimize the weight of a tension/compression spring (see
Minimize
Subject to:
The values of the TS-MBFOA parameters were bacteria (
Execution | Objective function | CVS | |||
---|---|---|---|---|---|
1 | 0.05159355 | 0.354262808 | 11.45072579 | 0.012684172 | 0 |
2 | 0.051786794 | 0.358909182 | 11.16852188 | 0.012675341 | 0 |
3 | 0.051640217 | 0.355334913 | 11.3815166 | 0.012680002 | 0 |
4 | 0.051857122 | 0.360755332 | 11.06220495 | 0.012672027 | 0 |
5 | 0.051181677 | 0.344562216 | 12.04584449 | 0.012677819 | 0 |
6 | 0.052105666 | 0.366772323 | 10.72887345 | 0.012675247 | 0 |
7 | 0.051293545 | 0.347208325 | 11.87874667 | 0.01267844 | 0 |
8 | 0.05228548 | 0.371232593 | 10.49086951 | 0.012676547 | 0 |
9 | 0.052045112 | 0.365289794 | 10.80590612 | 0.012670908 | 0 |
10 | 0.051899988 | 0.361746188 | 11.00524483 | 0.012672346 | 0 |
11 | 0.051441315 | 0.350758459 | 11.66735785 | 0.01268577 | 0 |
12 | 0.050529402 | 0.329409603 | 13.09886078 | 0.012698977 | 0 |
13 | 0.051851305 | 0.3605402 | 11.0830362 | 0.012681821 | 0 |
14 | 0.052165838 | 0.368170226 | 10.65591939 | 0.012679868 | 0 |
15 | 0.051410685 | 0.349908547 | 11.71354152 | 0.012682678 | 0 |
16 | 0.051495748 | 0.352057005 | 11.57182113 | 0.012670503 | 0 |
17 | 0.05188893 | 0.361519328 | 11.01850154 | 0.012671906 | 0 |
18 | 0.051572206 | 0.353298073 | 11.51576413 | 0.01270028 | 0 |
19 | 0.051482455 | 0.35166946 | 11.59573971 | 0.012672316 | 0 |
20 | 0.052102824 | 0.366748404 | 10.73141089 | 0.012675564 | 0 |
21 | 0.051537198 | 0.352957725 | 11.52150867 | 0.012676211 | 0 |
22 | 0.051303914 | 0.347267461 | 11.89056339 | 0.012696527 | 0 |
23 | 0.051661798 | 0.355817323 | 11.35260489 | 0.012680376 | 0 |
25 | 0.051829914 | 0.360030313 | 11.10680496 | 0.012676427 | 0 |
26 | 0.05183748 | 0.360125193 | 11.10733648 | 0.012683985 | 0 |
27 | 0.052329575 | 0.3722629 | 10.43538845 | 0.012676622 | 0 |
28 | 0.051862921 | 0.360491736 | 11.08950218 | 0.012692068 | 0 |
29 | 0.05161278 | 0.354869607 | 11.40594547 | 0.012673039 | 0 |
30 | 0.051589159 | 0.354117397 | 11.46248283 | 0.012687888 | 0 |
The best solution found, and the basic statistical values of all the 30 independent executions are presented in
Metric | Value |
---|---|
Best solution | 0.0126684 |
Average | 0.0126798 |
Median | 0.0126772 |
Worst solution | 0.0127003 |
Std. Dev. | 8.4E-07 |
Feasible rate | 100% |
Success rate | 100% |
Success performance | 15314 |
The convergence of an algorithm occurs when a solution remains unchanged for a number of iterations until the end of the algorithm execution. This solution can be feasible or not feasible, a local or global optimum.
Execution | TS-MBFOA | MBFOA |
---|---|---|
1 | 0.012684172 | 0.01630937 |
2 | 0.012675341 | 0.01365103 |
3 | 0.012680002 | 0.01504151 |
4 | 0.012672027 | 0.01393995 |
5 | 0.012677819 | 0.01502329 |
6 | 0.012675247 | 0.01419695 |
7 | 0.01267844 | 0.01452018 |
8 | 0.012676547 | 0.01652729 |
9 | 0.012670908 | 0.01674499 |
10 | 0.012672346 | 0.01616278 |
11 | 0.01268577 | 0.0148695 |
12 | 0.012698977 | 0.0151396 |
13 | 0.012681821 | 0.01600057 |
14 | 0.012679868 | 0.01498494 |
15 | 0.012682678 | 0.01339251 |
16 | 0.012670503 | 0.01593207 |
17 | 0.012671906 | 0.01429101 |
18 | 0.01270028 | 0.01675205 |
19 | 0.012672316 | 0.01897264 |
20 | 0.012675564 | 0.0147699 |
21 | 0.012676211 | 0.01474724 |
22 | 0.012696527 | 0.01395306 |
23 | 0.012680376 | 0.01699236 |
24 | 0.012668448 | 0.01425301 |
25 | 0.012676427 | 0.01466751 |
26 | 0.012683985 | 0.01499838 |
27 | 0.012676622 | 0.01687673 |
28 | 0.012692068 | 0.01372426 |
29 | 0.012673039 | 0.01485669 |
30 | 0.012687888 | 0.01494201 |
Metric | TS-MBFOA | MBFOA | |
---|---|---|---|
Best solution | 0.0126684 | 0.01630937 | |
Average | 0.0126798 | 0.01524111 | |
Median | 0.0126772 | 0.0148695 | |
Worst solution | 8.4E-07 | 0.00125107 | |
Std. Dev. | 0.0127003 | 0.01897264 |
The Wilcoxon Signed-Rank test was configured with a significance level of 0.05 using an online calculator [
In general, TS-MBFOA performed better than MBFOA. In addition, the UI allows the end-user to configure, calibrate parameters, and view the algorithm results with no additional effort.
This paper proposes an intuitive implementation of the TS-MBFOA along with a front-end for the easy solution of constraints numerical optimization problems. The main objective is to make the algorithm more straightforward in terms of parameter calibration and visualization of results. In the literature, the solutions based on the BFOA only show the algorithm's pseudocode or the code released in some programming language. However, there is no visual tool that allows to use of the algorithm in a fast way and to implement it in any problem.
The TS-MBFOA was developed following the previously designed UML diagrams. The front-end consists of two windows. In the first one, the end-user can configure the execution and calibrate the algorithm parameters. In the second one, results obtained by the algorithm are displayed in graphs and tables, in addition to exporting results to a spreadsheet file. The main advantages of our proposal to the end-user are the saving of time and effort in the calibration of parameters, the control and order of the executions to be conducted, and a clear and well-distributed display of the results.
The UI and the implementation of the TS-MBFOA were tested in solving the Tension/compression spring problem in 30 independent runs. We also compare the performance of the TS-MBFOA against the MBFOA using basic statistics and the Wilcoxon Signed Rank Test. MBFOA turned out to be the best algorithm. Our front-end is open-source software freely available at
Future work is intended to provide an open-source graphical interface for recent swarm intelligence algorithms found in the specialized literature, such as those based on the Monarch butterfly, Earthworm, Elephant herding, Moth search, Slime mould, or Harris hawks, to name a few.
To CONACYT (Ministry of Science in México) for supporting the National System of Researchers.