Abstract

As humanity and civilization progresses, newer class of challenging real-world problems continue to materialize, drawing the research community into developing newer algorithms. The Socio-cultural algorithms demonstrate a human individuals’ inclination to either cooperate or compete in his struggle to survive and exist. Some of these simulate a sociopolitical setup where electoral parties are formed comprising of party leaders and/or the voters/candidates, while other algorithms include functions or operators to simulate the idea that weaker societies gradually perish and the competitive, aggressive colonies or individuals survive in the long run. Some algorithms mimic the team competitiveness across sports teams, where contesting behavior leads to better performing team and team players. Other optimizers simulate a social framework where individuals (or agents) interact with each other in a particular social setup. Such a social setup in real life may be a family, educational organizations, group learning environments, etc. All the algorithms of SA class are grouped under the common umbrella of optimization algorithms which seek inspiration from social interactions in humans. There are numerous other social setups that researchers can get inspired from to build novel techniques or improve the performance of existing algorithms. This knowledge will help engineers and researchers to solve real-world problems using SAs. This work is a summary of the major SAs aimed to give a brief overview of all these algorithms with their advantages, limitations and applications solved till date, so as to provide a succinct, yet comprehensive, outline of these techniques.

1. Introduction

Nature has evolved over billions of years, providing a rich source of inspiration for researchers to develop a wide range of algorithms. Genetic algorithm, Particle-swarm optimization, Ant and Bee algorithms, Firefly algorithm, Cuckoo Search, Bat algorithm, Flower algorithm, Harmony Search and other nature-based algorithms have been in discussion for quite some time now [1], [2]. Analogous to these algorithms, social and cultural algorithms are also metaheuristic in nature, i.e. independent of problem to be solved, and are inspired by the natural inclination of humans to learn from another. As most of the algorithms in this sub-branch of nature inspire methodologies are new and are still evolving, there is promising scope of work in this domain. This Compendium reviews the book “Socio-cultural Inspired Metaheuristics” of Studies in Computational Intelligence by the Springer publications [3] and other research papers based on different social or cultural algorithms. This review shall provide an insight on this emerging area of optimization algorithms and hope that this source of information motivates other researchers to mature this area of optimizers further to solve real-world problems.

The Social Algorithms (SA) is a class of novel optimization techniques, a sub branch of the well-known Evolutionary Algorithms which in turn comes under the class of Nature-inspired optimization algorithms. Figure 1 shows the brief classification of Nature-inspired algorithms.

The SA class of algorithms is based on the human behaviour during social and cultural interactions. Human beings have the innate proclivity of competitive behaviour with other humans. Every human agent tries to improve its own behaviour in the course of achieving the shared goal through interactions in the due course of time. This proves to be a strength to evolve faster through interactions in the social setup than merely through biological evolution based on inheritance alone. This tendency observed in humans serves as a motivation for socio-inspired optimization algorithms where the agents in the optimizer algorithm work toward achieving some shared goals.

The remainder of this report is organized as follows:

Section 2 explains the classification of Socio Algorithms, Section 3 elucidates each of the above mentioned algorithms, Section 4 concludes the report with a brief summary and future directions and lastly Section 5 consists of the references.

1. Classification of Socio Algorithms

The SA class can be broadly classified according to the human behaviour they are trying to emulate. This classification is shown in Figure 2. The socio-cultural interaction based algorithms try to mimic certain social setups like family, group of friends, colleagues working together on a project, educational organizations, etc. Such interactions are cooperative in nature, where the individuals help each other to learn and improve their performance in doing the task. Whereas, the socio-political ideology based algorithms are based on competitive behavior of people where in the leaders try to persuade the voters to vote. The people may be associated with certain political party if their ideologies match to that of the party. The candidate or the party which gains maximum support, and hence maximum votes, wins the election. The sports competition based algorithms imitate the dynamics of intra-team and inter-team competitive sportsmanship. Every member of the team is strived to maximize their team’s score and win the match. The human colonization and imperialism is modeled in the colonization based algorithms which focus on acquiring more influence and expand their territory. Empires try to annex colonies of other empires and gain strength. The weaker empires gradually perish and only the strong ones survive. This behavior based classification of SA makes it easy to understand the inspiration of each algorithm. Following section of the report will throw light upon each and every algorithm, their characteristics and comparison with the rest.

1.1. Socio-Cultural interaction based SA

1.1.1. Cohort Intelligence (CI)

Introduction:

The CI algorithm [6] is a methodology inspired from the self-supervised learning behavior of candidates in a cohort. A cohort is a group of candidates with a common inherent goal and can interact with other candidates in a cohort. Every candidate tries to follow the behavior of some other candidate and improves its own behavior accordingly. Thus the overall performance of the cohort is improved. After a certain number of learning attempts, if the performance of the cohort attains saturation, that is the behavior of the candidates is difficult to be distinguished, the cohort is said to have achieved a convergence and this convergence becomes successful when for multiple times a similar convergence is observed.

Experiments & Applications:

The proposal of CI was validated by solving four test problems: Sphere, Rosenbrock, Ackley and Griewank; whose results proved to be successful with reasonable computational cost. CI has been also applied to solve combinatorial problems: A new variant of assignment problem, Sea Cargo Mix problem, Selection of cross border shippers problem, 0-1 Knapsack problem and Traveling salesman problem [23], [24], [25]. The approach was even found to perform better than some of contemporary approaches. The recent developments in CI include applications in data science like Hybrid data clustering [26] and Feature selection and SVM model selection [27]. Mechanical engineering applications like in mechanical component design using constrained CI [28] and design and optimization of shell-and-tube heat exchanger [29]. CI has also successfully been applied in Image steganography [30], [31] and in Search and rescue application of swarm robotics [32].

In all the above applications, the CI methodology was validated and the nature of the cohort candidates was successfully demonstrated along with their ability to learn and improve qualities which further improved their individual behavior.

Limitations:

A limitation of CI is that the algorithm uses a sampling interval reduction factor r, for fine tuning and governance of the computational performance, which is not self-adaptive. The rate of convergence and the quality of solution is dependent on number of candidates and number of variations. These parameters are chosen empirically after multiple preliminary trials. It was also observed that the initial guess may affect the computational time, if the initial guess was closer to the feasible solution then there are more chances to reach the solution faster.

CEA [8] is a population based algorithm inspired from the basic idea that a population will survive and evolve due to the perpetual nature of its culture. The complex transitions in the culture is a result of the collaborative efforts of all individuals because of the different social influences. Competition begets the best species in following generations, hence a global optimal is reached. In CEA, new cultural species are generated using four modes [33]: group consensus, individual learning, innovative learning and self-improvement. Figure 4 shows these modes and their sub modes. In group consensus mode the decision that is in the best interest of the entire group is chosen. In individual learning mode the less competitive cultures merge characteristics from more progressive cultures into their own. In innovative learning mode the evolving cultural species adopts characteristics from other cultures to diversify into new evolution. The self-improvement mode uses the self-introspection method of improvement of species.

Experiments & Applications:

The authors tested this algorithm using 7 benchmark functions with 100 variables: Sphere, Quadratic, Rosenbrock, Ackley, Griewank, Rastrigrin and Shwefel. The results were observed to be comparable with other contemporary approaches. CEA was also applied to two different reliability engineering problems: serial parallel system design and bridge system design. CEA achieved an exact solution for the first problem and for the second, it performed superior than other approaches.

1.1.2. Expectation Algorithm (ExA)

Introduction:

The ExA [11] is a social algorithm that models the behavior of individuals in a society. An individual cannot predict the behavior of other individuals in the society, it can only be expected. The expected behavior is calculated based on the current behavior of individuals and is used to find the best strategy. The society evolves because of such expectations and reactions towards them. The algorithm considers the value of a variable as the behavior of an individual. In every iteration the multi-variable problem is converted into single-variable as all the expected behaviors are treated as constants. Steepest descent method is used to minimize the single variable. A convergence is reached when no change is observed in the values, for a significant number of iterations, and the algorithm terminates. Figure 5 shows the flowchart of ExA.

ExA has been validated using 50 unconstrained test problems and its performance was compared with other algorithms like Artificial Bee Colony (ABC) [34], Backtracking Search Optimization (BSO) [35], Comprehensive Learning Particle Swarm Optimization (CLPSO) [36], Covariance Matrix Adaptation Evolution Strategy (CMAES) [37], Ideology Algorithm [12], Multi-Cohort Intelligence algorithm (Multi-CI) [38] and Self-adaptive Differential Evolution Algorithm (SDEA) [39]. It was observed that ExA performed better than most of these algorithms except BSO and Multi-CI.

Limitations:

ExA needs to be modified to solve constrained problems and problems closer to the real-world which are inherently constrained. Combinatorial problems are yet to be solved using ExA.

The SGO algorithm [17] is a population-based algorithm which mimics the human behavior while facing daily life challenges in a group. It has been observed that the problem solving capability of humans is more effective when done in a group (team effort) rather than individually. Every person in the group already possesses some own level of knowledge of handling the task. The SGO algorithm has two phases which run iteratively until the required termination condition. The person who is the most knowledgeable (best fitness) propagates knowledge to other members of the group and in turn improves their knowledge level. This is known as the improvement phase. The second phase is the acquiring phase where the group members interact with other members along with the best one at that time and try to enhance themselves. Thus, the members try to learn and acquire the missing traits through influences from other members in a social setup. The flowchart of SGO algorithm is shown in figure 6.

SGO is easy to comprehend and implement too. It has been applied to 25 standard numerical benchmark problems belonging to following categories: unimodal, multimodal, regular, irregular, non-separable and multidimensional. The performance of SGO was compared with other techniques like: ABC [34], Differential Evolution (DE) [40], Genetic Algorithm [41], Particle Swarm Optimization (PSO) [42] and TLBO [21]. The results showed that SGO method had a better computational costs than the rest. Though this method was developed very recently, it has already been used for many real-life applications like to solve data clustering problems [43], resource allocation and task scheduling in cloud environment [44], ischemic stroke segmentation by MRI [45], dermoscopic image evaluation for detection of melanoma [46], transformer fault diagnosis [47] and antenna array synthesis [48].