Multi Objective Particle Swarm Optimization based Cooperative Agents with Automated Negotiation

2019·arXiv

Abstract

1 Introduction

Optimization problems have received appreciable attention over the past decade and presented as an active research field that is encountered in various fields of technology such as image processing [1], path planning [2] and handwriting recognition [3-8].

The optimization can be incorporated into other intelligent tools of soft computing such as the neural network [9,10] and the fuzzy system [11] to produce better and faster result. In fact, Swarm intelligence (SI) is considered as an adaptable concept for the optimization problem. One of the most dominant algorithms in SI is a particle swarm optimization (PSO). Although PSO has been widely used for solving many well-known numerical test problems, but it suffers from the premature convergence. Thereby, several strategies have been developed responding to this limitation, such as the distributed evolutionary (DE) [12,13]. Hence, with the DE, a parallel optimization process can be formed which offers the ability to resolve a high-dimensional problem. Frequency, the DE presented at the population level, in which the population is distributed within the search space. The DE increase the diversity of solutions, thereby solve the premature convergence. Due to the several issues that address the distributed sub-populations, such as the communications protocol, it becomes required to endow a novel system with the capability to communicate, cooperate and reach agreements within the different sub-populations. These trends have led to the incorporation of Multi-Agent System (MAS) [14] as a distributed model. MAS allows building a distributed PSO with greater ease and reliability. In this work, we investigate a new distributed MOPSO based cooperative agents (MOPSO-CA) to optimize MOP. The MAS is advantageously used to elaborate a new variant of distributed MOPSO. Additionally, applying the automated negotiation [15], in order to share the best knowledge among sub-populations. In this way, the good information obtained by each sub-population is exchanged among the sub-populations; thereby the diversity of the population is increased simultaneously.

main concepts of our approach. We present the related work in section 3. Section 4 details the purpose of our approach. The experimental result is discussed in section 5. Finally, the conclusion and future work are then summarized in section 6.

2 Theoretical Foundation

In this section, we briefly present the main concept that will be employed throughout this article. First, we need to define a multi-objective optimization problem (MOP) and its basic concept, then the MOPSO.

2.1 Introduction to Multi Objective Optimization Problem

A MOP has a number of objective functions, which are to be minimized or maximized simultaneously. Those objectives are often immeasurable and conflicting with each other. MOP typically contains a set of constraints, that any feasible solution must satisfy, including the set of the optimal solution [16]. Subsequently, MOP can be written mathematically as follow:

In order to define the concept of optimization, we introduce a few useful terminologies: Dominance relationship. A solution x dominates solution y, if x is no worse than y in all objectives, and x is strictly better than y in at least one objective.

Pareto optimal. Is a non-dominated solution, which are equally good when compared to other solutions, means there exists no other feasible solution, which would decrease some criterion without causing a simultaneous increase in at least one other criterion.

Pareto front. The plot of the objective functions whose non-dominated vectors are in the Pareto optimal set is called the Pareto.

Convergence. The Pareto-front, which is as close as to the true Pareto-front, is considered best. Ideally, the true Pareto-front should contain the best-known Pareto-front.

Diversity. Pareto-front should provide solutions, which are uniformly distributed and diversified across the Pareto-front.

2.2 Introduction to Multi Objective Particle Swarm Optimization

PSO is a population-based search algorithm introduced by Kennedy and Eberhart [17]. In PSO, each particle in the population is a solution to the problem. Instead, the particles are “flown” through hyper dimensional search space to search out a new optimal solution through two equations (2) and (3).

Where leader presents the global best solution in the population, the pbest position is the best personal solution of a given particle. Additionally, r1 and r2 are random values, W is the inertia weight, c1 is the cognitive learning factor and c2 is the social learning factor. In order to adopt the PSO for the optimization of MOP (MOPSO), a few modifications must be made under the original PSO. First, the aim is to discover a set of the optimal solution, not even one. Second, an external archive is kept, where all non-dom-inated solutions found at each iteration are saved in.

3 Related Works

MOPSO is one of the dominant techniques to find the promised solutions much faster than the other algorithms. Instead, it suffers from the premature convergence. This problem tends to converge to local optima, such that problem led the MOPSO to fail to find the Pareto-optimal solutions. In order to solve this problem, it is obvious that the original algorithm has to be modified. One of the interesting methods that have the ability to overcome the problem of premature convergence is the distributed evolutionary (DE). The granularity of the DE may be at the population level. Since the distributed population based on the idea of dividing the entire population into sub-populations, each of which is processed by one processor. In fact, we summarize a few outputs.

A new version of MOPSO [18] adopts the Pareto ranking to dynamic subdivide the population. There are a few variants of hierarchical architecture are proposed in [19-21] that is proposed by Fdhila. Its main idea is to have a 2-levels that adopts a bidirectional dynamic exchange of particles between MOPSOs. Indeed, these variants improve its efficacy in many real applications such as the feature selection [22], the routing Pico-satellites problem [23], the grasp planning problem [24], the TSP problem [2], the Face Recognition [25]. The organization and communication between sub-pop-ulation play an important role in the DE. In fact, there are varieties of methods that attempt to address this deficiency. One of the most notable methods is the incorporation of MAS as a model of DE. Indeed, the MAS is adopted to model, manage and coordinate the process of optimization among different sub-population. Different methods are improved in [26-29] these methods applied the MAS as a model of DE, in which the MAS achieves the purpose of communication, organization and cooperation.

4 Description of the Proposed Approach

4.1 Motivation

The adaptation of MOPSO with DE makes evident the notion of using MAS could be the straightforward way to recover MOPSO in order to overcome the premature convergence. The hybridization between the MAS and the MOPSO algorithm could balance between the local exploitation and the global exploration. Indeed, we propose to use not one, but several sub-populations (each with a dynamic size). Each sub-popula-tion overfly within a specific region of the search space. In addition, it has its own set of particle and particle guides kept in the local archive. It is known that the use of disconnected sub-population led the algorithm unable to converge to the true Pareto front. This issue makes the using of a good strategy of communication is necessary. In this context, the automated negotiation (AN) is used. The AN used to ensure the changing information, considering that we are instead a decision conflict between agents, which are the optimal solution to be selected. In fact, the AN accurate the selection of global leader, since the solution is largely depends on the guiding points. In this way, the AN guarantees the set of Pareto optimal solution since each agent tends to exploit the subsearch space, while ensuring that an exploration is reached within the search space by sharing best knowledge (among sub-populations).

4.2 Main Process

The main process of our algorithm is illustrated in Figure 1. At the first stage, the population creates, initializes and updates its own particles. Additionally, the leaders set is generated and saved in the external archive. Once the initialization is completed, the Pareto ranking divides the population, as a result, a dynamic number of fronts (F0, F1..., Fn) are generated. Each of these fronts plays the role of the sub-population. These sub-populations distributed among agents. Then, for a maximum number of iterations, each agent performs the execution of MOPSO in its own sub-population, including the selection of gbest (global leader) (see Fig. 2) by the AN, the update of position and velocity and, finally, the local archive is updated too. However, as AN process we adopt a multi-lateral negotiation since we have k cooperative agents as negotiators. In this model, we assume that our domain has one issue (defining the best solution in order to share among sub-populations).

of MOPSO-CA algorithm

The general process of the negotiation process is as follows: once all agents attending the evolving process, a new negotiation session has begun, first, each agent sends a call for proposal CFP to other agents. Next, the agent responds to the CFP by making an offer (best local solution: based on the dominance operator). In the turn, the agent evaluates the incoming offer using the fitness function. Consequently, the accepted proposal is the offer which accepted by all agents. In result, the accepted proposal becomes the best global solution that used during the update position. Therefore, each particle of sub-population adjusts its trajectory according to its own experience (pbest), the experience of its neighbors (lbest), and the experience of best global solution among sub-pop-ulations (gbest). So the new equation for velocity is presented in equation (4).

Fig. 2. Negotiation protocol

5 Experimental studies

In order to know how important MOPSO-CA was, we compared it against two algorithms that taken from the literature [30] of MOP’s algorithms namely: Non-dominated Sorting Genetic Algorithm II (NSGAII), and Optimized Multiobjective Particle Swarm Optimization (OMOPSO). The benchmarks were explored in our experiment are DTLZ family (DTLZ5 and DTLZ6) and UF family (UF1, UF2, UF3 and UF10), which have sufficient complexity to evaluate the algorithm’s performance, in terms of solution diversity and convergence rate.

5.1 Performance Metric

Several performance evaluations are available to compare the performance of the presented approach. In the present context, we choose the following three metrics [31]: Spread (SP), Inverted Generational Distance (IGD) and Hypervolume (HV) which used to evaluate the diversity, the convergence and the both (convergence and diversity) respectively.

5.2 Experimental setting

To evaluate the performance of the comparative algorithms, 30 runs of each algorithm for each test function are performed; a population with 200 individuals is fixed, and the archive size is set to 100. Further, the parameters of different algorithms detailed as the following, for MOPSO-CA and MOPSO, an acceleration coefficients c1, c2 = Rand (1.5, 2.0), and inertia weight w = Rand (0.1, 0.5). For NSGAII the max evaluations = 25000 and crossover probability = 0.9.

5.3 Experimental results

In this section, we analyze the results obtained by the algorithms. Derivatives figures (Fig.3 to Fig.6) show the graphical results generated by the comparative algorithms. (see Fig.3 and Fig.4) show the Pareto front produced by the comparative algorithms for DTLZ5 and UF10 respectively; clearly, we can conclude that NSGAII, OMOPSO and MOPSO-CA cover the entire true Pareto front of DTLZ5 on one hand. On the other hand, we can see that only the MOPSO-CA may cover the true Pareto front of UF10.

Pareto fronts obtained by the algorithms for

Pareto fronts obtained by the algorithms for

For more precise the accuracy of the solution, statistical values are provided in Table 1. From these values, it can be seen, that the average performance of MOPSO-CA is better than NSGAII and OMOPSO with respect to the HV metric.

Table 1. Performance metrics (Mean value) for the different test functions

Regarding the SP metric, we can conclude that MOPSO-CA has the better spread of solutions for UF1, UF3, UF10, DTLZ5 and DTLZ6. On the other hand, the OMOPSO has the best SP value for UF2. Regarding the IGD metric, we can conclude that MOPSO-CA is relatively better than other algorithms for UF1, UF3, UF10, DTLZ5 and DTLZ6, since MOPSO-CA have the minimum IGD values. On the other hand, OMOPSO was the best for UF2. Hence, to have a deep dissection of the MOPSO-CA, the HV values for UF1 and UF2, DTLZ5 and DTLZ6 were plotted (see Fig.5).

Fig. 5. Performance (HV) over DTLZ5, DTLZ6, UF1 and UF2 problem

Graphically, it is intuitive that MOPSO-CA can achieve the best tradeoff between convergence and diversity (the higher value, the better performance for HV) with respect to other algorithms. Meanwhile, according to the HV values, we can conclude that MOPSO-CA gets better performance of different test function. Clearly, our MOPSOCA produces the best trade-off between the convergence and diversity, within the tested problems.

6 Conclusion and Future Work

In this paper, the MOPSO-CA algorithm proposed to solve MOP. In this algorithm, the sub-populations, Pareto ranking, MAS and automated negotiation are used. MAS improve the performance of distributed MOPSO but strategies for communication between agents are very important. Thus, the efficiency of synchronous knowledge (most successful solution) exchange strategies has been achieved by using the automated negotiation. Through experiments, it can be concluded that MOPSO-CA can outstanding performances in terms of convergence and diversity qualities. As a future work, we will explore more the feature of MAS to increase the intelligence level of particles. In addition, our proposed approach can be incorporated in many real-world problems.

Acknowledgement. The research leading to these results has received funding from the Ministry of Higher Education and Scientific Research of Tunisia under the grant agreement number LR11ES48.

References

1. Ghamisi, P., Couceiro M.S., Martins, F.M. L., Benediktsson, J.A: Multilevel Image Segmentation Based on Fractional-Order Darwinian Particle Swarm Optimization. IEEE Transactions on Geoscience and Remote Sensing 52(5), 2382-2394 (2014).

2. Fdhila, R., Elloumi, W., Hamdani, T. M.: Distributed MOPSO with dynamic pareto front driven population analysis for TSP problem. In: the 6th International Conference Soft Computing and Pattern Recognition, pp. 294-299. IEEE, Tunis, Tunisia (2014).

3. Ben Moussa, S., Zahour, A., Benabdelhafid, A., Alimi, M.A.: New features using fractal multi-dimensions for generalized Arabic font recognition. Pattern Recognition Letters, 31(5), 361-371 (2010).

4. Bezine, H., Alimi, M.A., Derbel, N.: Handwriting trajectory movements controlled by a bêta-elliptic model. In: 7th International Conference on Document Analysis and Recognition, pp. 1228-1232. IEEE, Edinburgh, UK, UK (2003).

5. Alimi, M.A.: Evolutionary computation for the recognition of on-line cursive handwriting. IETE Journal of Research, 48(5), 385-396 (2002).

6. Boubaker, H., Kherallah, M., Alimi, M.A.: New algorithm of straight or curved baseline detection for short arabic handwritten writing. In: 10th International Conference on Document Analysis and Recognition, pp. 778-782. IEEE, Barcelona, Spain (2009).

7. Slimane, F., Kanoun, S., Hennebert, J., Alimi, M.A., Ingold, R.: A study on font-family and font-size recognition applied to Arabic word images at ultra-low resolution. Pattern Recognition Letters 34(2), 209-218 (2013).

8. Elbaati, A., Boubaker, H., Kherallah, M., Alimi, M.A., Ennaji, A., Abed, H.E.: Arabic handwriting recognition using restored stroke chronology. In: 10th International Conference on Document Analysis and Recognition, pp. 411-415. IEEE, Barcelona, Spain (2009).

9. Dhahri, H., Alimi, M.A.: The modified differential evolution and the RBF (MDE-RBF) neural network for time series prediction. In: IEEE International Conference on Neural Networks -Conference Proceedings, pp. 2938- 2943. IEEE, Vancouver, BC, Canada (2006).

10. Bouaziz, S., Dhahri, H., Alimi, M.A. & Abraham, A.: A hybrid learning algorithm for evolving Flexible Beta Basis Function Neural Tree Model. Neurocomputing 117, 107-117 (2013).

11. Baccour, L., Alimi, M.A., John, R.I.: Similarity measures for intuitionistic fuzzy sets: State of the art. Journal of Intelligent and Fuzzy Systems 24(1), 37-49 (2013).

12. Bahareh, N., Mohd, Z., Ahmad, N., Mohammad, N.R, Salwani A.: A survey: Particle Swarm Optimization based algorithms to solve premature convergence problem. Journal of Computer Science 10(9), 1758-1765 (2014).

13. Gong, Y.-J., et al.: Distributed evolutionary algorithms and their models: A survey of the state-of-the-art. Applied Soft Computing 34, 286–300 (2015).

14. Wooldridge, M.: An Introduction to Multiagent System. 2nd edn. John Wiley and Sons Ltd, Chichester, United Kingdom (2009).

15. Jennings, N. R., Faratin, P., Lomuscio, A. R., Parsons, S., Sierra, C., Wooldridge, M.: Automated Negotiation: Prospects, Methods and Challenges. International Journal of Group Decision and Negotiation 10(2), 199-215 (2001).

16. Deb, K., Multi-objective Optimization. In: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, pp. 403-450. Springer, US (2014).

17. Reyes-Sierra, M., Coello Coello, C.A.: Multi-Objective Particle Swarm Optimizers:A Survey of the State-of-the-Art. International Journal of Computational Intelligence Research 2(3), 287–308 (2006).

18. Fdhila, R., Hamdani. T., Alimi. M.A.: A new distributed approach for MOPSO based on population Pareto fronts analysis and Dynamic. In: Systems Man and Cybernetics, pp. 947-954. IEEE, Istanbul, (2010).

19. Fdhila, R., Hamdani, T. M., Alimi , M.A.: A new hierarchical approach for MOPSO based on Dynamic subdivision of the population using Pareto fronts. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 947-954. IEEE, Istanbul, Turkey (2010).

20. Fdhila, R., Hamdani, T. M., Alimi, M.A.: Optimization algorithms, benchmarks and performance measures: From static to dynamic environment. In: the 15th International Conference on Intelligent Systems Design and Applications, pp. 597-603. IEEE, Marrakech, Morocco (2015).

21. Fdhila, R., Hamdani, T.M., Alimi , M.A.: Population-based Distribution of MOPSO with Continuous Flying Pareto Fronts Particles. Journal of Information Processing Systems, (2016).

22. Fdhila, R., Hamdani, T. M., & Alimi, M.A. : Distributed mopso with a new population subdivision technique for the feature selection. In: the 5th International Symposium Computational Intelligence and Intelligent Informatics, pp. 81-86. IEEE, Floriana, Malta (2011).

23. Fdhila, R., Hamdani, T. M., Alimi, M.A.: A multi objective particles swarm optimization algorithm for solving the routing pico-satellites problem. In: Systems, Man, and Cybernetics, pp. 1402-1407. IEEE, Seoul, South Korea (2012).

24. Fdhila, R., Walha, C., Hamdani, T. M., Alimi, M.A.: Hierarchical design for distributed mopso using sub-swarms based on a population pareto fronts analysis for the grasp planning problem. In: the 13th International Conference on Hybrid Intelligent Systems, pp. 203-208). IEEE, Gammarth, Tunisia (2013).

25. Fdhila, R., Ouarda, W., Alimi, M.A., Abraham, A.: A New Scheme for Face Recognition System Using a New 2-Level Parallelized Hierarchical Multi Objective Particle Swarm Opti- mization algorithm. Journal of Information Assurance and Security 11(6), 385-394 (2016).

26. Kouka, N., Fdhila, R., Alimi, M.A.: A new architecture based distributed agents using PSO for multi objective optimization. In: 13th International Conference on Applied Computing, (2016).

27. Ilie, S., Bădică, C.: Multi-agent approach to distributed ant colony optimization. Science of Computer Programming 78(6), 762-774 (2013).

28. Takano, R., Yamazaki, D., Ichikawa,Y., Hattori, K., Takadama, K.: Multiagent-based ABC algorithm for Autonomous Rescue Agent Cooperation. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 585-590. IEEE, San Diego, CA, USA (2014).

29. Yingchun, C., Wei, W.: MAS-Based Distributed Particle Swarm Optimization. In: 8th International Conference on Wireless Communications, Networking and Mobile Computing, pp. 1-4. IEEE, Shanghai, China (2012).

30. Godinez, A.C., Espinosa, L.E.M., Montes, E.M.: An Experimental Comparison of MultiObjective Algorithms: NSGA-II and OMOPSO. In: Conference Electronics, Robotics and Automotive Mechanics, pp. 28-33. IEEE, Morelos, Mexico (2010).

31. Zhang, Q., Zhou, A., Zhao, S., Suganthan, P. N., Tiwari, S.: Multiobjective optimization Test Instances for the CEC 2009 Special Session and Competition. Technical Report, CES-487 (2009).

Designed for Accessibility and to further Open Science