Game-theoretic Evolutionary Algorithm Based on Behavioral Expectation and its Performance Analysis

ABSTRACT

Game theory has been widely recognized as an important tool in many fields, which provides general mathematical techniques for analyzing situations in which two or more individuals make decisions that will influence one another’s welfare. This paper presents a game-theoretic evolutionary algorithm based on behavioral expectation, which is a type of optimization approach based on game theory. A formulation to estimate the payoffs expectation is given, which is a mechanism of trying to master the player’s information so as to facilitate the player becoming the rational decision maker. GameEA has one population (players set), and generates new offspring only by the imitation operator and the belief learning operator. The imitation operator is used to learn strategies and actions from other players to improve its competitiveness and applies it into the future game, namely that one player updates its chromosome by strategically copying some segments of gene sequences from the competitor. Belief learning refers to models in which a player adjusts its own strategies, behavior or chromosome by analyzing current history information with respect to an improvement of solution quality. The experimental results on various classes of problems using real-valued representation show that GameEA outperforms not only the standard genetic algorithm (GA) but also other GAs having additional mechanisms of accuracy enhancement. Finally, we compare the convergence of GameEA with different numbers of players to determine whether this parameter has a significant effect on convergence. The statistical results show that at the 0.05 significance level, the number of players has a crucial impact on GameEA's performance. The results suggest that 50 or 100 players will provide good results with unimodal functions, while 200 players will provide good results for multimodal functions.

Introduction

Current studies address the excessive sensitivity of Evolutionary Algorithms (EAs) to control parameters, premature convergence and slow computation speed, but capturing historical information and providing a predictive adaptive response to evolution requires further study. Recent research suggests that predictive adaptive responses can lead to differential development among initially similar individuals as well as provide an increase in evolutionary fitness, which is an adaptive change in long-term behavior or development due to a triggering environmental stimulus. EAs employ a set of nature-inspired computational methodologies and approaches to solving complex real-world problems that cannot be perfectly addressed using mathematical or deterministic algorithms. Several approaches have been proposed to model the specific intelligent behaviors, such as Ant Colony Algorithm (Dorigo and Gambardella 1997) based on the behavior of ants searching for food; Firefly Algorithm, inspired by the flashing behavior of fireflies (Yang 2010); Fish Swarm Algorithm, inspired by the collective movement of fish and their various social behaviors (Li, Shao, and Qian 2002; Neshat et al. 2014); Artificial Bee Colony (Karaboga and Basturk 2007); Cuckoo Search (Yang and Deb 2009); Multi-objective evolutionary algorithm based on decision space partition (Yang et al. 2017); and Artificial Immune System (Woldemariam and Yen 2010). Some other types of algorithms, such as neural computation (Maass, Natschläger, and Markram 2002) or brainstorming algorithm (Shi 2011), are inspired from the advanced activities of the human brain, which focus on the intelligence of cell behaviors. Although these types of algorithms do not guarantee the detection of the optimum value for a problem, they are sufficiently flexible to solve different types of problems due to their qualities of global exploration and local exploitation. However, the previous studies concentrated on the simulated biologic behavior rule or biological mechanism.

Game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers (Ram et al. 2014). Generally speaking, the game typically involves several players, strategies or actions, orders, and payoffs, which are similar to evolutionary algorithms’ individuals, genetic operators (selection, crossover, and mutation), and fitness. Both of them are population-based evolutions. On the game, the strategy selection of players is based on the payoffs expectation, and there are several learning methods to improve the players’ chances of obtaining gains, such as reinforcement learning (Madani and Hooshyar 2014), belief learning (Spiliopoulos 2012), imitation (Friedman et al. 2015), directional learning (Nax and Perc 2015; Simon et al. 1999), and rule learning (Stahl 2000). The player makes a decision based on the understanding of the other players’ action, and the player will become increasingly smart naturally. If the player is a candidate solution, it is possible to find the global optimal solution as the game goes on. Evolution through natural selection is often understood to imply improvement and progress, and for studying frequency-dependent selection, game-theoretic arguments are more appropriate than optimization algorithms (Nowak and Sigmund 2004). Replicator and adaptive dynamics describe short- and long-term evolution in phenotype space and have found applications ranging from animal behavior and ecology to speciation, macroevolution, and human language. Evolutionary game theory is an essential component of a mathematical and computational approach to biology. Additionally, recent research (Rosenstrom et al. 2015) has suggested that predictive adaptive response can lead to differential development among initially similar individuals, and increase evolutionary fitness, which is an adaptive change in the long-term behavior or development due to an environmental exposure that triggers it. Meanwhile, there is evidence that using a learning strategy can win against the top entries from the Othello League without the explicit use of human knowledge (Szubert, Jaskowski, and Krawiec 2013). With the motivation of the above-mentioned facts, we try to investigate a novel computational algorithm – the game evolutionary algorithm – which is an optimization approach based on behavioral expectation.

The remainder of this paper is organized as follows. Section II presents some related works. Section III describes the fundamentals of our proposed algorithms. Section IV details the proposed algorithms’ procedures. Section V presents the comprehensive experiments and analysis. Additional experiments with different players’ size are conducted and analyzed in Section VI. Finally, Section VII concludes this paper and threads some future research issues.

Related works

Evolutionary Game Theory (Kontogiannis and Spirakis 2005) is the study of strategic interactions among large populations of agents who base their decisions on simple, myopic rules, which is to determine broad classes of decision procedures, which provide plausible descriptions of selfish behavior and include appealing forms of aggregate behavior. It seems very attractive to employ the game theory to improve the performance of some popular evolutionary algorithms. Game-theoretic differential evolution (GTDE)(Ganesan, Elamvazuthi, and Vasant 2015) was developed from differential evolution (DE) by employing cooperative and defective strategies. The defective strategy was used to reduce the influence of the child vector on the principal parent at each generation and to modify the relation to increase the degree of mutation for the child vector, whereas the cooperative strategy was used to reduce or increase the mutation factor of the child. Although the computation time of GTDE is double that of DE, the performance of GTDE was enhanced using knowledge from evolutionary game theory. Particle swarm optimizer based on evolutionary game (EGPSO) (Liu and Wang 2008) was developed by connecting game theory with the classical particle swarm optimization (PSO). The choosing strategies in evolutionary games were used to map particles who hold current optimal solution in PSO algorithm to players who aim to pursue maximum utility, and replicator dynamics were employed to model the behavior of particles, and a multi-start technique was used to surmount premature convergence. An evolutionary algorithm based on Nash dominance for equilibrium problems with equilibrium constraints (Koh 2012) was proposed by redefining selection criteria. The Nash dominance was used to find the Nash equilibrium, which is the largest label. The game-theoretic approach for designing evolutionary programming is characterized by a mixed strategy using Gaussian and Cauchy mutations (He and Yao 2005). Although the framework of the algorithm has no difference with the popular evolutionary programming, its mutation operation is very similar to the game strategy. With an ever-increasing complexity in design engineering problems, game strategies have been proposed as one of the key technologies to save CPU usage and produce high model quality due to their efficiency in design optimization (Lee et al. 2011; Periaux et al. 2001), in which game strategies are hybridized and coupled to multiobjective evolutionary algorithms (MOEA) to improve the quality of solutions.

Game theory is also increasingly used to solve complex problems. Considering the problem of spectrum trading, with multiple licensed users selling spectrum opportunities to multiple unlicensed users, a game-theoretic framework is proposed to investigate the network dynamics under different system parameter settings and under system perturbation (Niyato, Hossain, and Zhu 2009), which is designed for modeling the interactions among multiple primary users and multiple secondary users. The theory of evolutionary game is used to model the evolution and the dynamic behavior of secondary users, and a non-cooperative game is formulated to model the competition among the primary users. An evolutionary mechanism is designed by introducing the Nash equilibrium (Wei et al. 2010) based on a practical approximated solution with two steps for the quality of service constrained resource allocation problem. First, each player solves its optimal problem independently by using the proposed binary integer programming method. Second, a mechanism to change multiplexed strategies of the initial optimal solutions of different players is employed to minimize their efficiency losses. The author claims that the Nash equilibrium always exists if the resource allocation game has feasible solutions. Concentrating on the optimality of the wireless network, the evolutionary game framework allows an arbitrary number of mobiles that are involved in a local interaction to extend on the evolution of dynamics and the equilibrium (Jiang et al. 2015; Tembine et al. 2010). To explain the evolution of structured meaning-signal mappings on why the evolutionary dynamics is trapped in local maxima that do not reflect the structure of the meaning and signal spaces, a simple game theoretical model is used, which can show analytically that when individuals adopting the same communication code meet more frequently than individuals using different codes – a result of the spatial organization of the population – then advantageous linguistic innovations can spread and take over the population (Fontanari and Perlovsky 2008). The game theoretic trust model (Mejia et al. 2011) for the on-line distributed evolution of cooperation adapts effectively to environmental changes, but it relies on a bacterial-like algorithm to let the nodes quickly learn the appropriate cooperation behavior. A game-theoretic approach to partial clique enumeration(Bulo, Torsello, and Pelillo 2009) has proved its effectiveness, which can avoid extracting the same clique multiple times by casting the problem into a game-theoretic framework. Recently, a constant model hawk-dove game (Misra and Sarkar 2015) was designed to ensure prioritizing the local data-processing units in Wireless Body Area Networks during medical emergency situations. Aimed at obtaining the mechanism of behavior game, the game evolutionary model (Yang et al. 2016) employed to evaluate the payoffs expectation was established. Otherwise, the game theory has been used in many other fields like data mining (Qin et al. 2015) and knowledge discovery (Hausknecht et al. 2014).

Fundamental of GameEA

Origin of thought

Consider a serious study of the game theory. First, the players make a decision based on the information possessed and use this decision to gain optimal payoffs. Under non-cooperative gaming, John Nash proved that one player can gain worse payoffs except for employing the best strategy among the strategies set if the other participants do not change their decisions. It means a rational player will reach the consistency prediction by analyzing the information. Second, a repeated game is a massive form of a game, which is composed of some numbers of repetitions of some stage of the game. It reveals the idea that one person will have to take into account the impact of his current action on the future actions of other players. It can be proved that every strategy that has a payoff greater than the minimal payoff can be a Nash equilibrium, which is a very big set of strategies. The payoff is the evaluative criteria when the players chose which kind of strategy is to be used, and the payoff of a repeated game is a distinguished form of the one-shot game. Each stage of the repeated game gains payoffs, and if it is assigned to each turn of the game, it leads to a number of one-shot games. Thus, the repeated game’s payoffs are related to the used strategies and the current total payoffs. If there is a base game G (static game or dynamic game), T is the times of repeating game, and the game results can be observed before starting a new G, such kind of event is called a T-repeated game of G, marked as G(T). Usually, there is a presupposition that players act rationally and make decisions intelligently, but human behavior often deviates from absolute rationality and absolute intelligence, and this conception of learning leads to the game theory.

In short, rationality and intelligent players can have an insight into the optimal strategies by grabbing and analyzing perfect information so as to gain the highest payoffs. Moreover, all participants’ final payoffs are related to stage gains in a repeated game. participants can scan historical stage information, and choose a suitable decision strategy, which can be varying equilibrium strategies for long-term interests. Additionally, in practice, learning is an important approach to gain a competitive edge when the player is lacking in rationality and intelligence. Based on these facts, we propose a new computational intelligent algorithm based on the game theory.

Model of game evolution

In an extensive form, a repeated game can be presented as a game with complete but imperfect information using the so-called Harsanyi Transformation (Hu and Stuart 2002). This transformation introduces to the game the notion of nature’s choice. Hence, when a challenger competes with opponents, the opponents are considered a part of nature; therefore, the challenger is subject to nature’s choice. Actually, the challenger doesn’t know what nature’s move was; he/she only knows the probability distribution under the various options and the winner’s payoffs are known to every player. In traditional consideration, the player’s action or strategy is the most important factor, but with nature’s choice we can find some difference. First, the player’s stable payoffs constitute winning the opponent and the other challenger. Second, if the player accepts the game, irrespective of whether it is lost or won, he/she can learn something from the opponent, which will indirectly influence future competition. Third, if the player gives up competing, he/she can improve by self-training. Let w₁ and w₂ stand for the payoffs from fighting with nature’s choice and the gains from self-training, respectively; then nature has a probability of p to choose a weaker rival, thereby providing a stronger opponent with a probability of 1-p. That nature’s choice has the probability p of selecting a weaker opponent results in different performances for different challengers and even for a homogenous challenger at different stages; thus, the payoffs w₁ and w₂ are indeterminate and are not calculated in the simplified matrix of payoffs.

When the challenger is not sure about the competitiveness of the competitor, the best way is using the mathematical expectation to estimate the payoff for a risk preference player. If the challenger decides to fight with nature’s choice, its expectation payoffs can be presented as (1-p)×w₁ + p×(w₁ +1); otherwise, if the challenger gives up the competition, the expectation payoffs can be calculated by using (1-p)×w₂ + p×w₂. Thus, the total expectation payoffs E can be calculated using (1), and by substituting w = w₂-w₁ into Equation (1), we can get Equation (2).

(1)

(2)

We use Equation (2) as the criterion of one challenger, namely that if E ≤0, then the challenger gives up the competition; otherwise, if E >0, then the challenger has to fight with a random selected sample (nature’s choice).

Learning strategies

The traditional game theory does not discuss how to achieve equilibrium. In equilibrium reasoning, it is assumed that participants either are rational enough or can approximate equilibrium by learning (Colman 2003). Considering that a perfectly rational player exists only in ideal state, learning is very important for the player in the wrestling model. In our research, we design some learning strategies for the wrestling model, which includes imitation and belief learning. Imitation means learning strategies and actions from other players to improve one’s competitiveness and then apply it to the next game, namely that one player updates his/her own chromosome by copying some segments of the gene sequences from the opponents, which are characterized by positive feedback. In the context of learning in games, belief learning refers to models in which players are engaged in a repeated game and each player adjusts his/her own strategies, behavior, or chromosome by analyzing current history information with respect to an improvement of payoffs and competitiveness against the next-period opponent behavior.

Proposed algorithm: GameEA

Framework of proposed algorithm

For the convenience of description, we define some symbols shown in Table 1. Figure 1 presents the general framework of GameEA. At the beginning, the initialization procedure generates N initial players and initializes each player’s active and passive payoff of game. Within the main loop, in case the given evolution generation is not met, for each player as a challenger, choose an opponent for the challenger, and the challenger makes a decision by carefully checking the selected player, then the imitation or the belief learning procedure is employed for offspring generation. Then the offspring is used to update the so-called best solution. GameEA has only one population (players set), and generates new offspring only by the imitation operator between the challenger and the opponent and the belief learning operator by self-training strategies. In the following paragraphs, the implementation details of each component in GameEA will be detailed.

Table 1. Definition of symbols.

Symbol	Meaning	Symbol	Meaning
Tmax	Maximum of game generation	N	Size of players/population
W1	Payoffs weight	W2	Losses weight
P1,	Imitation probability	P2	Learning probability
P3	Speculative probability	n	Dimension of problem
t	tth game generation	Ha	Total number of speculations
Hs	Total number of successful speculations	Ii	ith player/individual
Ii^a	Active payoff of game of Ii	Ii^p	Passive payoff of game of Ii
Ii°^bj	Objectives of Ii	Ii^v	Total payoffs of Ii

Initialization

The initialization procedure of GameEA includes the following three aspects: the decision space and the objective function; the initialization of players of set I; and the passive and active payoffs of each player that are assigned to zero. For the function optimization problems, the initial players in set I are randomly sampled form the decision space Rⁿ via a uniform distribution using real-valued representation, and each player’s objective value is calculated by using the objective function.

Imitation operator

According to the Harsanyi Transformation, nature should perform its duty – provide a choice before applying the imitation procedure – which relates to line 6 of Figure 1. Equations (2) and (3) are used to calculate the expectation payoffs of I_i:

(3)

where μ =random(). Considering that the players are not intelligent enough with zero total payoffs at the beginning like the human origins stage, we let the player imitate the selected player with probability P₁, which is a very big number just like 0.9 and allowed the chromosome to remain unchanged, namely that the weak challenger I_i has to compete with the selected I_j, and then imitate some useful information from others by using operator imitation (I_i, I_j), but it has the probability of doing nothing at the current turn of the game to survive some schema. This is special strategy whereby various genes can either change or remain unchanged when the player does not know much about others.

The calculation of payoffs expectation (line 9 of Figure 1) is very significant, which is a mechanism of trying to master the other’s information because the total payoffs indicate one’s historic strategies. Such a mechanism allows the player become more rational, and helps the player make a rational decision. It seems that players often form an aspiration based on their experiences with different actions and opponents, and payoff rewards are reinforcing or deterring depending on who they are compared to, and that decision makers adjust their aspirations as they gain experience (Borgers and Sarin 1997).

Figure 2 shows the general procedure of imitation. The objective value comparison between the pair of players (line 1 of Figure 2) is the basis of the historic performance, but the comparison result impacts both the active and passive payoffs. We use a temporary variable to breed new individuals based on some imitation strategies according to the historic action, and the offspring replaces its parent only when the offspring is better than its parent so as to facilitate global convergence.

Figure 1. General framework of GameEA.

In the real word, if one person feels that some others have competitive skills, perhaps he/she will try to learn such skills, but if they do not have that, the final decision is effected by the attraction of the skills and the subjective initiative. Inspired by that, we use a random value, i.e. random(), to present the degree of subjective initiative and the ratio of succeed imitation number (H_a+1) and the total number of imitations (2H_s+1). If random()*(H_a+1)/(2H_s+1)<P₃, it means that all conditions indicate that the players need to improve themselves by speculatively leaning from others.

In practice, different imitation strategies can be implemented according to the characteristics of the problem. For the function optimization problems, if r₁ =rand(0,n-1), r₂ =rand(0,n-1), and β =random(), then if β <0.5 then, otherwise, so we use the following strategy to implement I_i speculatively learning from I_j (line 5 of Figure 2): I_p.gen[r₂] = 0.5(1-τ) I_i.gen[r₂] + (1 +τ) I_j.gen[r₁], then if the value of I_p.gen[r₂] is out of range, assign the required random value to I_p.gen[r₂]. We then implement that I_i strategically copies a segment of genes from I_j by I_p.gen[r₁] = 0.5(1-τ) I_i.gen[r₁] + (1 +τ) I_j.gen[r₁], and if the value of I_p.gen[r₁] is out of the decision space, assign the required random value to I_p.gen[r₁].

Belief learning operator

As mentioned above, belief learning refers to models in which each player adjusts its own strategies with respect to an improvement of payoffs and competitiveness against the next-period opponent behavior. That means the player convinces that one strategy will facilitate positive feedback, and insists on employing the strategy to train itself with the expectation of improving the future competitiveness. Generally, this kind of self-training is associated with training methods and duration, and decision makers are usually not completely committed to just one set of ideas, or to just one way of behaving, and the real story is that several systems of ideas, or several possible ways of behaving are present in their minds simultaneously. Which of these predominate, and which are given less attention, depends on the experiences of the individual (Borgers and Sarin 1997). Thus, we let the operator perform under a given probability P₂. If the belief learning is expected to run many times, assign P₂ a bigger value, otherwise P₂ is set to a small one. Different belief learning strategies can be designed for difference problems. If some characteristic of the solution need to be emphasized, the preferential knowledge can be used to specify a belief learning algorithm. Some local optimization methods can also be added into this section. It is very convenient for people to implement what they think of. Figure 3 is a kind of belief learning procedure for real-valued presentation problems. The offspring replaces its parent only when the offspring is better than its parent so as to implement the elitist conservation strategy.

Figure 2. General framework of the imitation operator.

In particular, the belief learning operator is different from the belief space of a cultural algorithm (Reynolds 1999), which is divided into distinct categories representing different domains of knowledge that the population has of the search space. The belief space is updated after each iteration by the best individuals of the population.

Update players set

We believe the existence of the parent is justified and competitive; we infer the offspring has the capability to survive if the offspring is stronger or better than its parents. Based on this, the GameEA uses a simple strategy to update the players’ set, which is that the offspring replaces its parent and inherits the parent’s fortune like the payoffs and behavior only when the offspring is better than its parent so as to implement the elitist conservation strategy and to facilitate global convergence. For each repeat loop (lines 5–12 of Figure 1), the new player does not shy away from other players’ challenges; the game is all around for all players regardless of whether the individual is experienced or inexperienced.

Performance comparison and experimental results

Test problems

In order to check the performance, C++ language was employed to implement GameEA. Our programming platform is the.net, and the PC is configured to AMD Phenom ™ II X4 810 CPU (2.59 GHz), 2 GB of RAM. We also have chosen four kinds of algorithms: Standard Genetic Algorithm (StGA)(Holland 1975), Island-model Genetic Algorithms (IMGA) (Alba and Tomassini 2002), finding multimodal solutions using restricted tournament selection (RTS)(Harik 1995), and Dual-Population Genetic Algorithm for adaptive diversity control (Park and Ryu 2010), which are famous for their distinguished performances with different characteristics and were used for comparing the performances. IMGA is a typical example of multi-population GAs, evolves two or more subpopulations, and uses periodic migration for the exchange of information between the subpopulations. RTS employs a crowding method, which is somewhat different from the standard crowding. DPGA employs two populations, in which the main population evolves to find a good solution to the given problem and the reserve population evolves to provide controlled diversity to the main population.

To focus on the searching accuracy and stability, 13 benchmark functions f₁–f₁₃ shown in Table 2 have been considered in our experiments on real-valued representation, which are widely adopted for comparing the capabilities of evolutionary algorithms. The functions f₁–f₇ are uni-modal distribution function with one peak within the entire given domain, and the functions f₈–f₁₃ are multimodal functions with a number of local optima in the searching space. The column n in Table 2 indicates the dimensions used.

Table 2. Test functions used for the experiments.

No.	Name	n	Function	Range
f1	Sphere	30		xi∈[−100,100]
f2	Schwefel 2.22	30		xi∈[−10,10]
f3	Schwefel 2.21	30		xi∈[−100,100]
f4	Rosenbrock	30		xi∈[−30,30]
f5	Step	30		xi∈[−100,100]
f6	Noisy Quartic	30		xi∈[−1.28,1.28]
F7	Goldstein-price	2		xi∈[−2,2]
F8	Branin	2		x1∈[−5,10] x2∈[0,15]
F9	Six-hump camelback	2		xi∈[−5,5] ^n
f10	Rastrigin	30		xi∈[−5.12,5.12]
f11	Griewank	30		xi∈[−600,600]
f12	Schwefel 2.26	30		xi∈[−500,500]
f13	Ackley	30		xi∈[−32,32]

Experimental setup

Specifically, we continue to use the parameters and strategies that StGA, IMGA, RTS, and DPGA have used. IMGA has multiple subpopulations, each of which evolves separately. RTS uses a crowding method, which is somewhat different from the standard crowding, which selects parents randomly and lets the latest offspring replace the most similar one by using a specific strategy. DPGA also uses an additional population as a reservoir of diversity. Additional details of these algorithms can be found in other studies (Alba and Tomassini 2002; Harik 1995; Holland 1975; Park and Ryu 2010).

The players size N is set to 50 for GameEA, the payoffs weight W₁, losses weight W₂, learning probability P₁, mutation probability P₂, and the speculative probability P₃ are set to 0.9, 0.01, 0.9, 0.1, and 0.1, respectively. For each function, the maximum iteration of GameEA is a set of homogeneous iterations with the compared algorithm. For example, the parent size and the offspring size for DPGA are, respectively, set to 50 and 100 for function f₁, and the iterations are set to 1500, then its maximum iteration is 225000, so the maximum generation is set to 4500 with the players’ size of 50. Table 3 summarizes the generations used for each function, which are indicated in the Maximum generation column of the table. The following sections present the statistical experimental results obtained for the functions mentioned above.

Table 3. Fifty independent experimental statistics results based on StGA, IMGA, RTS, DPGA, and GameEA using real-valued representation on functions f₁–f_13.

	Maximum generation	Optimum solution	StGA		IMGA		RTS		DPGA		GameEA		t-Test(GameEA Versus)
			avg	stdev	avg	stdev	avg	stdev	avg	stdev	avg	stdev	StGA	IMGA	RTS	DPGA
f1	1500	0	6.12E-34	1.27E-38	2.04E-34	5.23E-34	7.90E -43	1.74E-42	1.47E-52	4.17E-52	4.33E-96	2.79E-95	+	+	+	+
f2	2000	0	3.32E-29	1.78E-28	6.40E-32	1.36E-31	7.18E-37	6.19E-37	5.19E-45	7.90E-45	1.52E-66	4.61E-66	+	+	+	+
f3	5000	0	7.00E-15	1.37E-14	4.28E-06	3.64E-06	1.54E-05	1.91E-05	3.12E-09	1.18E-08	7.85E-04	2.26E-03	–	–	–	–
f4	20000	0	5.454	3.662	5.554	4.522	1.391	1.211	3.047	3.558	0.0374	0.264	+	+	+	+
f5	1500	0	0	0	0	0	0	0	0	0	0	0	≈	≈	≈	≈
f6	3000	0	1.37E-02	3.24E-03	7.52E-03	2.24E-03	1.82E-03	4.56E-04	1.46E-02	3.93E-03	7.66E-03	1.82E-03	+	≈	≈	+
f7	100	3	3	0	3	0	3	0	3	0	3	0	≈	≈	≈	≈
f8	100	0.398	0.398	0	0.398	0	0.398	0	0.398	0	0.398	0	≈	≈	≈	≈
f9	100	−1.032	−1.032	0	−1.032	0	−1.032	0	−1.032	0	−1.032	0	≈	≈	≈	≈
f10	5000	0	11.809	2.369	0.358	0.746	0	0	0	0	0	0	+	+	≈	≈
f11	2000	0	1.63E-03	3.91E-03	3.54E-03	7.73E-03	2.07E-03	5.31E-03	1.28E-03	3.31E-03	0	0	+	+	+	+
f12	9000	−12569.4866	−11195.1	284.5	−12008.1	284.9	−12443.9	142.4	−12550.5	43.9	−12569.4866	0	+	+	+	+
f13	1500	0	3.55E-15	0	4.69E-15	1.67E-15	5.26E-15	1.79E-15	3.55E-15	0	6.84E-16	1.30E-15	+	+	+	+

Experimental results analysis

For each test problem, 50 independent experiments were executed and the averaged results are shown in Table 3. The avg and stdev columns stand for the average and standard deviation of the results, respectively. Table 3 also provides the results of the t-test at the confidence level of 5% between GameEA and each of the other algorithms. To facilitate this description, we use “+” to indicate that GameEA is significantly better than the compared algorithm, “–” represents that GameEA is obviously worse than the other four algorithms, and “≈” indicates that there are no statistically significant differences between GameEA and the compared algorithms.

For the uni-modal functions f₁, f₂, and f₄, GameEA obtains the best results with an average result of 4.33E-96, 1.52E-66, and 0.0374, respectively. The DPGA shows the second best results, with an average result of 1.47E-52 for function f₁, and the RTS is the third on the list. The StGA convergence accuracy is slightly worse than IMGA for functions f₁ and f₂, but IMGA is worse than StGA for function f₄. For the function f₄, RTS with an average of 1.391 comes second, but GameEA’s average is less than 3% of RTS. For the function f₆, GameEA is significantly better than StGA and DPGA. GameEA is similar to IMGA and RTS, but it holds a smaller standard deviation. For the functions f₅ and f₇, all the above-mentioned algorithms converge to the global minimum.

To make a careful observation of the results on the highly multimodal functions f₈–f₁₃, which have a number of local optima, all the algorithms converge to the global minimum on functions f₈ and f₉. RTS, DPGA, and GameEA show no significant differences with the convergence of global optima in each independent trial on function f₁₀, which means all the algorithms are capable of solving such problems.

GameEA is the best, with the best stability convergence in 50 independent trials for functions f₁₁–f₁₃, which shows good search-ability, stability, and robustness. It is a remarkable fact that StGA and DPGA did not converge to global optimal solution with the same standard deviation of zero in all the trials for function f₁₃, which indicates that those algorithms have been stalled at the local optimal points, whereas GameEA escapes and continually evolves to the global minimum. We also determined the final solutions of GameEA about f₁₃; although its averages of optimum are not perfect, we found that there were 39 parts in 50 to obtain the global optimum.

For function f₃, GameEA is obviously worse than the other four algorithms. When we studied the 50 experimental outputs, it was found that the best solution is set to 4.43E-12 and the worst optimum is set to 0.0122, which means that the final results share a large span, which leads to a poor average and standard deviation. We expand the generations up to 20000 in order to check the sustainability of GameEA, and GameEA reported an average of 1.008E-15 with a standard deviation of 2.5E-12. The statistics results based on 50 independent trials obtained by GameEA for function f₃ are shown in Figure 4. According to the average best-so-far curve shown in Figure 4(a), GameEA can escape from the local optima and keep improving the precision, namely that the best-to-so-far is improved continually along with the increase of the evolution, which partially indicates that the GameEA has a predominance sustainability of evolution.

Figure 3. Pseudo-code for the belief learning operator for the real-valued presentation.

Figure 4. Statistics results based on 50 independent runs obtained by GameEA for function f_3.

Figure 5. Average best-so-far curves for functions during evolution.

To observe the evolution of the best-so-far optimal solution, we have checked the tendency of averages of uni-modal function f₄ and multimodal function f₁₂, and its average best-so-far curves for those functions are shown in Figure 5 (the data of compared algorithms is from Park and Ryu (2010)). For uni-modal function f₄, GameEA shows the fastest convergence and provides the best results at the very early evolution, followed by RTS and then DPGA; however, it also indicates the risk of getting stuck in local optima and cannot escape from them. For uni-modal function f₁₂, GameEA is the champion and DPGA comes next, although the convergence curves of all the algorithms are not that different at the last stage.

In conclusion, the summarized results of statistical significance testing to compare GameEA with each of the other four algorithms are shown in Table 4. GameEA performs better than the other algorithms for all of the multimodal problems. For the uni-modal functions, GameEA loses only one time against StGA, IMGA, RTS, and DPGA. It can be concluded that GameEA has better performance, such as the stability, robustness, and accuracy of solution, compared with algorithms on function optimization problems.

Table 4. Summary of statistically significance testing.

problems	StGA		IMGA		RTS		DPGA
	+	−	+	−	+	−	+	−
Unimodal functions (f1–f7)	4	1	3	1	3	1	4	1
Multimodal functions (f8–f13)	4	0	4	0	3	0	3	0
total	8	1	7	1	6	1	7	1

Additional experiments with different players’ size

This section compares the convergence of GameEA with different players’ size to understand whether this parameter has significant effect on the convergence. The experimental settings are the same as the previous section, except the players size N and the maximum generation. The generation is set to 3E+6, and the N is set to 20, 50, 100, 200, 300, and 500, respectively. In this experiment, we focus only on the players’ size as the factor relating to the convergence of GameEA, which is considered as six levels of the factor. Thirty independent trials were executed, and Table 5 shows the experimental results of GameEA with different players’ size. Objectively, even given the same inputs and parameters, due to the random factors (game randomness, random number, etc.), GameEA might converge to different solutions for one problem. To conclude whether the algorithm has performance differences of searching for the perfect solution between different population sizes is to distinguish what is the primary factor leading to the differences between the different parameters and the random error. This problem can boil down to a question that whether the six kinds of samples have the same distribution, namely to check whether the normal population means are equal among the observation groups with the same variance. Analysis of variance (ANOVA) (Anscombe 1948) was used to analyze the differences among group means.

Table 5. Experimental results of GameEA with different players size.

No.	N = 20				N = 50				N = 300
	avg	stdev	gen-avg	time/s	avg	stdev	gen-avg	time/s	avg	stdev	gen-avg	time/s
f1	0	0	21087	0.2256	0	0	18139	1.0023	1.27E-156	0	6666	4.8285
f2	1.56E-226	0	82369	5.0376	3.79E-211	0	39991	7.2957	1.05E-80	1.02E-80	6666	7.3454
f3	3.68E-14	8.63E-14	99982	6.4724	2.62E-07	1.11E-06	39981	6.3858	4.24E-05	2.64E-05	6652	6.3976
f4	0.680864	1.73E+00	87961	11.1543	0.036319	1.96E-01	35575	11.3292	0.000841	4.44E-04	6621	14.2034
f5	0	0	309	0.0001	0	0	256	0.0004	0	0	222	0.0106
f6	9.05E-04	3.60E-04	84979	7.1923	1.60E-03	4.72E-04	35801	7.958	6.40E-03	1.35E-03	6103	8.3175
f7	7.194243	1.55E+01	17011	0.1114	3	5.11E-12	10606	0.2626	3	0	1827	0.2851
f8	0.397887	2.26E-16	17457	0.114	0.397887	2.26E-16	6376	0.092	0.397887	2.26E-16	1555	0.1999
f9	−1.031628	4.52E-16	2632	0.003	−1.031628	4.52E-16	616	0.001	−1.031628	4.52E-16	410	0.0162
f10	0	0	1017	0.0008	0	0	861	0.0034	0	0	782	0.0997
f11	0	0	3989	0.0133	0	0	999	0.0051	0	0	883	0.1453
f12	−1.26E+04	5.55E-12	3979	0.0148	−1.26E+04	5.55E-12	3877	0.0876	−1.26E+04	5.55E-12	3720	2.8881
f13	9.33E-16	2.10E-30	1538	0.0018	8.29E-16	1.96E-30	1300	0.0079	1.04E-16	3.22E-31	1186	0.2339
No.	N = 100				N = 200				N = 500
	avg	stdev	gen-avg	time/s	avg	stdev	gen-avg	time/s	avg	stdev	gen-avg	time/s
f1	0	0	17195	3.5933	2.21E-215	0	9998	4.9305	7.63E-97	9.93E-97	3999	4.8131
f2	1.33E-171	0	19996	7.3231	3.66E-111	1.69E-110	9999	7.3424	7.95E-50	5.29E-50	3999	7.2306
f3	1.13E-05	5.33E-05	19985	6.3918	8.40E-08	8.96E-08	9985	6.4471	9.53E-03	2.60E-03	3987	6.3436
f4	0.000036	1.48E-04	19685	13.8408	0.000191	1.25E-04	9766	13.899	0.00551	1.92E-03	3972	14.3059
f5	0	0	237	0.0013	0	0	228	0.005	0	0	218	0.0285
f6	2.54E-03	7.44E-04	18020	8.3217	4.65E-03	1.03E-03	9120	8.242	9.98E-03	1.96E-03	3654	8.297
f7	3	8.76E-12	6824	0.4408	3	0	2486	0.2408	3	0	1285	0.3906
f8	0.397887	2.26E-16	2759	0.0747	0.397887	2.26E-16	1781	0.1158	0.397887	2.26E-16	1286	0.3787
f9	−1.031628	4.52E-16	529	0.003	−1.031628	4.52E-16	366	0.0057	−1.031628	4.52E-16	405	0.0441
f10	0	0	809	0.0118	0	0	788	0.0452	0	0	772	0.2683
f11	0	0	937	0.0182	0	0	901	0.0681	0	0	875	0.3985
f12	−1.26E+04	5.55E-12	3754	0.3414	−1.26E+04	5.55E-12	3667	1.2487	−1.26E+04	5.55E-12	3664	7.8013
f13	4.14E-16	1.16E-30	1239	0.0309	0	0	1188	0.1039	0	0	1182	0.6433

Experiments and analysis

Table 6 shows the results of the homogeneity test of variances and one-sample Kolmogorov–Smirnov for Rosenbrock function with different parameters. The Levene statistic is 20.046, the degrees of freedom df1 and df2 are 5 and 174, respectively, and the two-tailed significance probability is 0.0001. The tests show that the overall sample meets the requirements of homogeneity of variance. Obviously, Table 6(b) provides evidence of the normality of each group of data. Using the same method, it can be proved that the data of the other test problems also meet the requirements of ANOVA, and hence the other detailed data are omitted.

Table 6. Results of homogeneity test of variances and one-sample Kolmogorov–Smirnov for function Rosenbrock with different parameters.

(a) Test of Homogeneity of variances
Levene Statistic	df1	df2	Sig.
20.046	5	174	0.0001
(b) One-sample Kolmogorov–Smirnov test
		Sample Size	180
Normal Parameters^a,b		Mean	−9.987E-1
		Std. Deviation	2.5003E-3
Most Extreme Differences		Absolute	0.443
		Positive	0.443
		Negative	−0.299
		Kolmogorov-Smirnov Z	5.946
		Asymp. Sig. (2-tailed)	0.0001

^aTest distribution is Normal. b. Calculated from data.

We assume that this is a null hypothesis H₀, namely that the convergence accuracy has no significant difference with different population size N on the significance level of 0.05 (α =0.05). Table 7 shows the results of ANOVA and the homogeneous subset for different groups of data obtained by GameEA with different parameters. ANOVA gives an overall test for the difference between the means of six groups. According to the principle, the within-groups only indicate the stochastic error caused by random variation, and the between-groups reflect both stochastic error and systematic error. If the population/players size has no effect on the convergence, the between-groups contain only random errors among the tested six groups, and then the ratio of between-groups and within-groups approximates 1. Otherwise, the between-groups contain not only random variance but also systematic error, yet it is obvious that the ratio of between-groups and within-groups is greater than 1, which implies the population size has a significant impact on the final results when this ratio reached a certain level.

Table 7. Summary of ANOVA and a homogeneous subset for six group data obtained by GameEA with different parameters.

		Sum of Squares	df	Mean Square	F	Fα
(a)f4:Rosenbrock
Between Groups		11.329	5	2.266	4.474	0.001
Within Groups		88.122	174	0.506
Total		99.450	179
Homogeneous subset (Duncan^a)
Group	Subset for α= 0.05
	1			2
100	3.5981E-5
200	1.9145E-4
300	8.4040E-4
500	5.5087E-3
50	3.6319E-2
20				6.8086E-1
Fα	0.864			1.000
(b) f3: Schwefel 2.21
Between Groups		2.26E-3	5	4.53E-4	402.593	1.3E-93
Within Groups		1.96E-4	174	1.13E-6
Total		2.46E-3	179
	1		2
20	3.6772E-14
200	8.3989E-8
50	2.6248E-7
100	1.1265E-5
300	4.2420E-5
500			9.5290E-3
Fα	0.893		1.000
(c) f6: Noisy Quartic
Between Groups		1.76E-3	5	3.52E-4	276.416	8.7E-81
Within Groups		2.22E-4	174	1.27E-6
Total		1.98E-3	179
	1	2	3	4	5	6
20	9.053E-4
50		1.598E-3
100			2.545E-3
200				4.649E-3
300					6.398E-3
500						9.981E-3
Fα	1.000	1.000	1.000	1.000	1.000	1.000
(d) f14: Ackley
Between Groups		2.62E-29	5	5.24E-30	5.684	7.0E-5
Within Groups		1.61E-28	174	9.23E-31
Total		1.87E-28	179
	1		2		3
200	0
500	0
300	1.0367E-16
100	4.147E-16		4.147E-16
50			8.293E-16		8.293E-16
20					9.330E-16
Fα	0.130		0.096		0.676

^aUses Harmonic Mean Sample Size = 30.

As can be seen in Table 7, the observed value of F is found by dividing the between-group variance by the within-group variance, and all F > F_α=0.05, the null hypothesis H₀ is rejected, which means the convergence accuracy has significant difference with different population size N on the significance level of 0.05. Moreover, the multiple comparisons of homogeneous subset means is another kind of expression of the multiple comparison of group means, and there is no significant difference among the data sets belonging to the same homogeneous subset. In Table 7(a) there are two homogeneous subsets, the probability of the hypothesis – that the group means are equal when the population sizes are set to 50, 100, 200, 300, and 500 on the significance levelα – is 0.864 for the first subset, and this probability is bigger than α =0.05, so that the hypothesis is rejected, which means the group balance variance is good; and the other subset only has one group data, and there is no possibility of discussing its balance. It can be concluded the population size belonging to the two homogeneous subsets have significant impact on GameEA’s convergence. So to consider this conclusion, we can infer that the population size N corresponding to the first homogeneous subset is more suitable for GameEA to solve the function f₄. Similarly, the population size belonging to the set of {20, 50, 100, 200, and 300} will lead GameEA to improve the performance for function f₃. For function f₆, the experiment data were divided into six homogeneous subsets on the significant level 0.05, and the average variance increases with the increase of the value of N, which indicates the average convergence accuracy decreases with the increase of N. We modified the significance level to 0.01, and then those groups with N =20 or 50 or 100 remain at the same homogeneous subset. Based on the observed factors, we make a conclusion: GameEA with the population size N =50 or 100 will give more satisfactory performance when adopting it to optimize the uni-modal function problem.

For multimodal function f₁₄, there are three homogeneous subsets, namely {N|200, 500, 300, and 100}, {N|100, 50}, and {N|50, 20}. The observed value of F_α of each subset is 0.13, 0.96, and 0.676, respectively. Taking this into consideration and referring to Table 5, it can be suggested that GameEA will show predominance performance for the multimodal function optimization when its population size is N =200.

Summary of the analysis

According the statistical analysis results, under the significance level α =0.05, players size has a crucial impact on the performance of GameEA. The size affects the convergence accuracy, capability of solving the deceptive problems, and the exploration ability of insight into the global optimal solution. If the size is too small, there will not be enough schemas to be exploited (Dejong and Spears 1991), resulting into a premature; if the population size is too large, it may require unnecessary large computational resources and result in an extremely long running time. When employing GameEA to solve problems, setting the players’ size depends on the complexity of the problem. It is suggested that the players’ size is set to 50 or 100 for uni-modal function and to 200 for multimodal function.

Conclusion

Development of GameEA was motivated by studies that attempt to develop simpler and more efficient game evolutionary algorithms. Unlike many search algorithms, GameEA has a payoff expectation mechanism, and the player makes a decision by evaluating the payoff expectation. Moreover, GameEA’s strategy for generating a trial population includes Imitation and Belief learning operators. According to the GameEA’s eliting conservation strategy for updating the players set, the offspring replaces its parent and inherits the parents’ information only when the offspring is better than its parent. Experiments have been conducted on various benchmark functions (unimodal functions and multimodal function). We have compared the performance of the GameEA with that of StGA, IMGA, RTS, and DPGA. We have also analyzed some additional experiments to determine the influence of player size on evolution. In future work, we will conduct experiments with more intensive problems, including multi-objective optimization problems involving more complicated applications.

Funding

The authors would like to thank the financial support provided by the National Natural Science Foundation of China under Grants 61640209 and 51475097, Foundation for Distinguished Young Talents of Guizhou Province under Grant QKHRZ[2015]13, Science and Technology Foundation of Guizhou Province under Grants JZ[2014]2004, JZ[2014]2001, ZDZX[2013]6020, LH[2016]7433, ZDZX[2014]6021, and National Key Technology Support Program of China under Grant 2012BAH62F00.

Additional information

Funding

The authors would like to thank the financial support provided by the National Natural Science Foundation of China under Grants 61640209 and 51475097, Foundation for Distinguished Young Talents of Guizhou Province under Grant QKHRZ[2015]13, Science and Technology Foundation of Guizhou Province under Grants JZ[2014]2004, JZ[2014]2001, ZDZX[2013]6020, LH[2016]7433, ZDZX[2014]6021, and National Key Technology Support Program of China under Grant 2012BAH62F00.