Abstract: The aim of present study is to introduce a heuristic optimization method which is inspired from competitions in social behaviors. Competitive behaviors could be observed in large number of situations of human social life. Particularly we propose a global optimization algorithm which is stochastic, iterative and population-based like genetic algorithms and particle swarm optimization. In this method, the intra and inter group competitions among parties in a parliament, trying to take the control of the parliament are simulated. Performance of this method for function optimization over some benchmark multi-dimensional functions, of which global and local minimums are known, is compared with traditional genetic algorithms.
INTRODUCTION
Global optimization is the task of finding a solution set of an objective function in which it takes its smallest value, the global minimum. From a computational complexity point of view, finding the global minimum of a function is a NP-hard problem, which means that there is in general no algorithm for solving it in polynomial time. Global optimization is a stronger version of the local optimization, in sense that instead of searching for a locally improvable feasible point, it looks for the best point in the search space. In many practical engineering applications finding the globally best point is desirable but not critical, since any sufficiently suboptimal solution which satisfies a specific criterion is acceptable. It is also possible to manually improve it further without optimization in some cases. For such problems there is a little harm in doing an incomplete search (Dekkers and Aarts, 1991).
Global search techniques become more important when only function values are available at hand (not derivatives), that’s why they are called direct optimization techniques. Because direct search methods do not use derivative information, they are usually slow and need too many function evaluations to converge. Instead, these methods are very flexible and the only thing they need is the value of the objective function at search points. That makes them applicable to a wide variety of practical problems where values could be calculated with small cost.
Researchers in different fields have got many inspirations from the solutions that nature has evolved for hard problems. An interesting such area is optimization. Taking advantage of evolutionary approach nature has selected, genetic algorithms and its variants has been suggested for optimization. Modeling animal behaviors has resulted to particle swarm (Kennedy and Eberhart, 1995; Schutte and Groenwold, 2001; Trelea, 2003) and ant colony optimization algorithms (Dorigo et al., 1996; Bonabeau et al., 2000). Recently simulating social behaviors of humans has leaded to some solutions in engineering (Sharples, 2002; Ray and Liew, 2003; Akhtar et al., 2002).
The aim in this study is to introduce a new optimization method inspired from human social behavior in political situations. As we are going to compare our method with genetic algorithms a brief introduction to it is presented as follows.
Genetic Algorithms (GA) were first introduced in (Holland, 1975). It takes the essence of biological evolution by activating mutation and crossing-over among candidates. GA is a stochastic, incomplete, iterative and population-based global optimization method. In each iteration of GA, a competitive selection weeds out poor solutions. Solutions with high fitness are then recombined with other solutions by swapping their parts. A mutation operation is also applied over solutions by making a small change at a single element. Recombination and mutation are used to generate new solutions that are biased towards regions of the space for which good solutions have already been experienced.
Competitions among political groups (usually political parties) during head elections in a parliament have been our main inspiration source for formulating a new method for global optimization in this study. All individuals of the population are clustered randomly into some groups. Members of a party fall into two categories: regular members and candidate members. Parliamentary head candidates compete in each group to become the final candidate of that group. A final candidate then must compete in the next round with candidates of other groups for parliament head position. Intra-party and inter-party competitions guide the algorithm to converge to the global minimum of the objective function. We have overridden some real life details purposely for simplicity. For example in parliamentary system of some countries people vote for candidates both within a group and among groups. This algorithm has some similarities with competitions during athletic championships in which athletics are grouped into teams and they play against each other to ascend from their teams and then play with winners of other teams in the next round. But obviously our method has certain differences. As it can be seen it is also somehow similar to competitions among parties during presidential campaign.
PARLIAMENTARY POLITICAL COMPETITIONS
It is a common incident and is repeatedly observed in different aspects of human life that people tend to form social groups. In sociology, a group is usually defined as a collection of humans or animals, who share certain characteristics, interact with one another, accept expectations and obligations as members of the group and share a common identity. Using this definition, society appears as a large group. Characteristics that members in the group may share include, interests, values, ethnic and linguistic background and kinship ties. Two types of relationships exist within a group and among groups: competition and cooperation. Members of a group (human social group) have different capabilities making each one suitable for a certain task. Because each member has a collection of needs and capabilities, it forms a potential for them to cooperate. At the same time they compete to earn higher fraction of group resources. In competition among groups, they compete to get better situations and take the superiority over others to attain the limited sources of their living environment (Flinn et al., 2005). Although many patterns of such behaviors are observable in human social life, we constrain ourselves to a specific competition-cooperation behavior during parliamentary elections.
A parliamentary system, also known as parliamentarianism is a system of government in which the power to make and execute laws is held by a parliament. Members of the parliament are elected in general elections by people. People usually vote in favor of parties. Members of a parliament belong to political parties. They support their parties in parliamentary votes. Clustering members of the parliament into clusters based on the party they belong, results to competitions among parties in trying to gain superiority over other parties. Almost in all democratic countries, political parties form the population of parliaments (Shourie, 2007).
There are basically two systems in parliamentary elections: the Majority Election System and the Proportional Representation System. In the majority election system, only one Member of Parliament is elected per constituency. In the proportional representation system several members of parliament are elected per constituency. Basically every political party presents a list of candidates and voters can select a list that is they vote for a political party. Parties are assigned parliamentary seats proportionally to the number of votes they get.
Political parties, either in the parliament or out of it, have members with different levels of power. Those main people of a party try to make good impacts over other regular members with less power. They do that to benefit from their support and vote during election, etc. Therefore, important members (candidates) of parties are engaged in competitions and try to find supporters among regular members. On the other hand, regular members have tendency toward more capable persons and usually vote for people they believe at. This is an active process and regular members with high capability replace previous candidates. These competitions are among individuals within parties. Another kind of competition is at the level of parties. Political parties compete for gaining more power. Two main goals that parties try to achieve are greater number seats in the parliament and taking the control of government.
As an example, in the United Kingdom, parliament consists of the House of Commons, the House of Lords and the Monarch. Three major political parties are: Labor, Conservative and Liberal Democrat. The leader of a Party that wins more than half the seats or less than half but can count on support of smaller parties to achieve enough support to pass law is invited by the Queen to form a government.
PARLIAMENTARY OPTIMIZATION ALGORITHM (POA)
Optimization process in our algorithm is started by first creating a population of individuals. These individuals are assumed to be the members of the parliament. In the next step, population is divided into some political groups (parties) and a fixed number of members with highest fitness are selected as group candidates (leaders).
After partitioning the population, intra-group competition is started. In intra-group competition a regular members get biased toward candidates in proportion to their fitness. It is motivated from the fact that a regular member is usually under impact of superior members. This observation is modeled here as a weighted average of vectors from a regular member to candidates. This causes the evolutionary process search for potential points in search space and provides an exploratory mechanism. At the end of intra-party competition a few candidates with highest fitness are regarded as final candidates of the group. They compete with candidates of other groups in next stage. Both candidates and regular members of a group are important in determining total power of a group. A linear combination of mean power of candidates and mean power of regular members is considered as the total fitness of a group. As in parliamentary system of some countries no voting mechanism is assumed. Actually, the biasness mechanism could somehow be considered as implicit voting.
Inter-group competition begins just after intra-group competitions ends. Political groups within the parliament perform competition with other groups to impose them their own candidate. In our method, the role of groups is still preserved after introducing a candidate. Each group not being able to compete with others becomes weaker and loses its chance to take the parliament head position.
Groups with a negligible fitness gradually lose their power and ultimately collapse. On the other hand, stronger groups become progressively more powerful and consequently earn higher chance to win the competition. Powerful groups sometimes agree to join and merge into one (at least at on some special occasions) to increase their wining chance. This gives the search mechanism chance to look on more promising areas therefore offers a mechanism for exploitation. The tendency of regular members of a group toward their group candidates along with affinity of powerful groups to join and also collapse mechanism drives convergence to a state in which there exists just one group in the parliament. In contrast to what happens in real world, when algorithm converges, regular members have near the same or equal power as the candidate which is now the head. A step by step description of the algorithm is summarized as follows:
| • | Initialize the population. | |
| • | Partition population into some groups. | |
| • | Pick θ highly fitted individuals as candidates of each group. | |
| • | Intra-group competition | |
| • | Bias regular members toward candidates of the group. | |
| • | Reassign new candidates. | |
| • | Compute power of each group. | |
| • | Inter-group competition. | |
| • | Pick λ most powerful groups and merge them with probability Pm. | |
| • | Remove γ weak groups with probability Pd. | |
| • | If stopping condition not met go to 3. | |
| • | Report the best candidate as the solution of the optimization problem. | |
Population initialization: A population of initial solutions with size N is being dispread over the d-dimensional problem space at random positions. Each individual of the population is coded as a d-dimensional continuous vector:
| (1) |
Each individual could be either a regular member or candidate of a given group. A fitness function f is used to calculate the strength of an individual.
Population partitioning: In order to form initial groups, population is portioned into M divisions. Each group contains L individuals. N, M and L are positive integers and are selected in such a way to satisfy the following equation:
| (2) |
Top θ<L/3 candidates with high fitness are then considered as candidates of each group. At this point all groups have the same number of members, but in the course of running the algorithm groups might earn different number of individuals because of merge and collapse mechanisms. Figure 1 shown the initial state of the population partitioned into three groups, each with five candidates.
Intra-group competition: Regular members of a group get biased toward candidates after interactions take place between candidates and regular members. This biasness is assumed here to be linearly proportional to weighted average of vectors connecting a member to candidates. Each candidate is weighted to the extent of its candidate fitness as shown in Eq. 3.
| (3) |
In above formula, η is a random number between 0.5 and 2 and allows the algorithm to search in a local search area around candidates.
| Fig. 1: | Population partitions at first iteration, black symbols represent candidates |
| Fig. 2: | Biasing a member toward candidates |
| Fig. 3: | Merging two groups into one group |
Another alternative mechanism is to use large values of η at first iterations and the gradually reduce it, perhaps by analyzing variance. Figure 2 shows biasing mechanism.
A regular member is allowed to change, only if it takes a higher fitness value. After biasing, regular members might have higher fitness values than candidates. In such cases, a reassignment of candidates is done. Let Qi = [Q1, Q2, …, Qθ] be the vector of candidates and Ri = [Rθ+1, Rθ+2, …, RL] the remaining regular members of the i-th group, power of this group is calculates as:
| (4) |
Inter-group competition: Stronger groups sometimes, join and merge to one group in order to amplify their power. To perform merging, a random number is generated and if it is smaller than Pm, λ most powerful groups are picked and merged into one. During the course of running algorithm, weak groups are removed to save computation power and reduce function evaluations. Like merging, a random number is generated and if it is smaller than Pd, γ groups with minimum power are eliminated (Fig. 3).
Stopping condition: At the end of algorithm, a group wins the competitions and its best member (candidate with maximum fitness) in considered as the solution of the optimization problem. Two stopping conditions are possible. Algorithm terminates if either maximum number of iterations is reached or during some successive iterations no significant enhancement in fitness is observed.
SIMULATION STUDIES
Several experiments are conducted in this section to demonstrate success of the proposed algorithm. Specifically, capability of the algorithm in finding global minimum of three benchmark functions 'Sphere', 'Rastrigin' and 'Ackley' is investigated. Plots of these functions in two dimensions are shown in Fig. 4 Efficiency of the parliamentary optimization algorithms is also compared with traditional genetic algorithm over these problems. To do experimentation with genetic algorithm, GA toolbox provided with MATLAB® was used. Table 1 shows POA parameter values for minimizing optimization functions. In order to do a fair comparison with GA, initial conditions and number of initial individuals were identical in simulations.
Sphere function: Equation five defines the sphere function in n dimensions. Dynamics of individual behaviors of the best group around the point with the best fitness is shown in top part of Fig. 5. It can be observed that individuals move toward the optimal point from initialization area. In their progress towards the optimal point, individuals are biased toward the candidates of groups. This process gradually moves the points toward the global minimum. The minimum value of the sphere function discovered by POA was y = 7.89 e -11 at the point x = [-0.1413e-3, -0.0662e-3]. It is known that the optimal value of this function is zero for the point [0, 0] in the x-y plane. Minimum, maximum and average of individuals in population as well as fitness variance is plotted in Fig. 5. Compared with GA, our methods showed significance enhancement o 100 iterations.
| (5) |
| Table 1: | POA parameter values for mimization of three optimization problems |
| Fig. 4: | Plot of functions used in simulations. Black vertical bar points to minimum |
| Fig. 5: | From top to bottom: Convergence of the population toward the
optimal point over Sphere function. Minimum, mean and maximum fitness are
plotted for each generation over entire population. High variance in first
iterations decreases at algorithm converges to the solution. Performance
of GA over sphere function is significantly worse than POA |
| Fig. 6: | Performance of POA and GA over Rastrigin function is shown
in this figure. Note that GA has fall into local minima |
| Fig. 7: | POA is compared with GA over 10-dimensional Ackley function.
Again GA has fall into local minima. Gradual increase in variance is because
of local minima in function |
Rastrigin function: We address another challenging optimization problem, which is minimization of Rastrigin function to demonstrate the effectiveness the POA. Figure 4 clearly shows that the Rastrigin function has numerous local minima. However, it has just one global minimum, at the point [0, 0] in the x-y plane, as indicated by the vertical line in the plot, where the value of the function is zero. Rastrigin function is defined as below:
| (6) |
Performance of POA and GA over Rastrigin function is shown in Fig. 6. POA reached absolute zero (in MATLAB) after 293 iterations. Algorithm stopped after no change was seen over fitness landscape. Again in comparison with GA a significant improvement was achieved.
Ackley function: Ackley function is a challenging and favorite benchmark problem for optimization algorithms shown in Eq. 7. It could be observed from Fig. 4 that the function has only one global minima at [0, 0] in x-y plane with also numerous local minima. In this experiment we aimed to compare the efficiency of POA with GA over a high dimensional optimization problem. Results over this function are shown in Fig. 7.
| (7) |
CONCLUSIONS
In this research, we introduced a new global optimization algorithm which is inspired from competitions among political parties trying to take the control of the parliament. Although we have bypassed some of the details of these competitions, proposed algorithm still has acceptable efficiency.
An initial population is created at the first step. It is then partitioned into some political groups. Each member of a given group is either a regular member or a superior member (candidate) of that group. Intra-group competition is the attempt of superior members to get the support of regular members. Regular members fluctuate with their bias toward superior members based on their achievements. In inter-group competition, political groups engage in competition and cooperation behaviors to win a good situation. This cooperation is modeled in this study as merging those more powerful groups to one bigger more powerful one. Some weak groups which have no positive effect on search process are removed. That way, stronger groups become gradually more powerful while weaker ones become weaker and finally collapse.
At the end of these competitions, the most superior of the most powerful party becomes the leader or the head of the parliament and is considered as the solution of the optimization problem.
Several numerical simulations are carried out to investigate the convergence of POA over three benchmark optimization problems. Results show significant enhancement over staged genetic algorithm over three problems.
As it can be from simulations our proposed optimization algorithm captures important essences of political competitions fairly well and is capable to find desired minima very fast in comparison with other stochastic search algorithms. As an optimization algorithm, it has the additional desirable properties of capability to deal with complex and non-differentiable objective functions and escapes from local optima.
Through investigation of algorithm parameters, comparison with other optimization techniques like particle swarm and ant colony optimization as well as experimenting with a rich repertoire of high dimensional benchmark problems are the areas authors suggest for future works.