SMCB-E-08102005-0551.R2 An Organizational Evolutionary Algorithm for Numerical Optimization Jing Liu,Member,IEEE Weicai Zhong,Member,IEEE and Licheng Jiao,Senior Member,IEEE Abstract-Taking inspiration from the interacting process I.INTRODUCTION among organizations in human societies,this paper designs a kind of structured population and corresponding evolutionary VOLUTIONARY algorithms (EAs)[1],based on an operators to form a novel algorithm,Organizational Evolutionary analogy to natural evolution,have recently gained Algorithm(OEA),for solving both unconstrained and constrained increasing interest.They are suitable for solving complex or optimization problems.In OEA,a population consists of ill-defined problems and have been successfully applied to the organizations,and an organization consists of individuals.All fields of numerical optimization,constraint satisfaction evolutionary operators are designed to simulate the interaction problems,data mining,neural networks,and many other among organizations.In experiments,15 unconstrained functions, 13 constrained functions,and 4 engineering design problems are engineering problems [2]-[10].Numerical optimization used to validate the performance of OEA,and thorough problems arise in almost every field of science,engineering,and comparisons are made between OEA and existing approaches.The business,and usually can be divided into two types,namely, results show that OEA obtains good performances in both the unconstrained optimization problems(UCOPs)and constrained solution quality and the computational cost.Moreover,for the optimization problems(COPs).The COPs usually are named as constrained problems,the good performances are obtained by only the general nonlinear programming problems.This paper incorporating two simple constraints handling techniques into OEA.Furthermore,systematic analyses have been made on all proposes a new EA for solving both UCOPs and COPs. parameters of OEA.The results show that OEA is quite robust A.Proposed Approach and easy to use. Traditionally,populations in EAs are simple non-ordered sets Index Terms-Evolutionary algorithms, organization. of individuals.Those individuals that will generate offspring are numerical optimization,constrained optimization problems. usually selected from all individuals according to their fitness. So the global fitness distribution of a population must be NOTATION LIST determined.The main consequence of this design is that the x) Objective function gene-flow inside the population is much higher compared to a 以x) Objective function with penalty term for real world situation,which often leads to premature genetic constrained optimization problems convergence.In fact,the real natural selection only occurs in a S Search space local environment,and each individual can only interact with 父 Feasible region those around it.That is,in some phase,the natural evolution is Dimension of the search space just a kind of local phenomenon.The information can be shared x,y,z,r,q Real-valued vectors in the search space globally only after a process of diffusion.Therefore,several Xp yo Zb ro q The ith Components in the vectors x,y,z,r,g studies tackled this problem by developing structured X Vector of the lower bound of the search space populations,such as cellular genetic algorithms [11], The ith Component in the vectorx multinational evolutionary algorithms [12],patchwork models 心 Vector of the upper bound of the search space [13],MAGA [7],MAEA-CSPs [8],and so on. 刻 In economics,R.H.Coase explained the sizing and formation The ith Component in the vector of organizations from the framework of transaction costs [14] g(x) Constraints The basic idea is that the organization exists because it reduces Number of constrains the overhead transaction costs associated with exchanging P Population in the tth generation goods and services.This concept was introduced to the learning classifiers based on genetic algorithms by Wilcox in 1995 [15] which put emphasis on inventing an autonomous mechanism using transaction costs for forming appropriately sized organizations within a classifier.Actually,in the real world situation,to achieve their purposes,organizations will compete Manuscript received August 10,2005.This work is supported by the National Natural Science Foundation of China under Grant 60502043. or cooperate with others so that they can gain more resources The authors are with the Institute of Intelligent Information Processing, As a result,the resources will be reasonably distributed among Xidian University,Xi'an,710071,China.(neouma@163.com)
SMCB-E-08102005-0551.R2 1 Abstract—Taking inspiration from the interacting process among organizations in human societies, this paper designs a kind of structured population and corresponding evolutionary operators to form a novel algorithm, Organizational Evolutionary Algorithm (OEA), for solving both unconstrained and constrained optimization problems. In OEA, a population consists of organizations, and an organization consists of individuals. All evolutionary operators are designed to simulate the interaction among organizations. In experiments, 15 unconstrained functions, 13 constrained functions, and 4 engineering design problems are used to validate the performance of OEA, and thorough comparisons are made between OEA and existing approaches. The results show that OEA obtains good performances in both the solution quality and the computational cost. Moreover, for the constrained problems, the good performances are obtained by only incorporating two simple constraints handling techniques into OEA. Furthermore, systematic analyses have been made on all parameters of OEA. The results show that OEA is quite robust and easy to use. Index Terms—Evolutionary algorithms, organization, numerical optimization, constrained optimization problems. NOTATION LIST f(x) Objective function ψ(x) Objective function with penalty term for constrained optimization problems S Search space F Feasible region n Dimension of the search space x, y, z, r, q Real-valued vectors in the search space xi, yi, zi, ri, qi The ith Components in the vectors x, y, z, r, q x Vector of the lower bound of the search space i x The ith Component in the vector x x Vector of the upper bound of the search space i x The ith Component in the vector x g(x) Constraints m Number of constrains Pt Population in the tth generation Manuscript received August 10, 2005. This work is supported by the National Natural Science Foundation of China under Grant 60502043. The authors are with the Institute of Intelligent Information Processing, Xidian University, Xi’an, 710071, China. (neouma@163.com) I. INTRODUCTION VOLUTIONARY algorithms (EAs) [1], based on an analogy to natural evolution, have recently gained increasing interest. They are suitable for solving complex or ill-defined problems and have been successfully applied to the fields of numerical optimization, constraint satisfaction problems, data mining, neural networks, and many other engineering problems [2]-[10]. Numerical optimization problems arise in almost every field of science, engineering, and business, and usually can be divided into two types, namely, unconstrained optimization problems (UCOPs) and constrained optimization problems (COPs). The COPs usually are named as the general nonlinear programming problems. This paper proposes a new EA for solving both UCOPs and COPs. A. Proposed Approach Traditionally, populations in EAs are simple non-ordered sets of individuals. Those individuals that will generate offspring are usually selected from all individuals according to their fitness. So the global fitness distribution of a population must be determined. The main consequence of this design is that the gene-flow inside the population is much higher compared to a real world situation, which often leads to premature genetic convergence. In fact, the real natural selection only occurs in a local environment, and each individual can only interact with those around it. That is, in some phase, the natural evolution is just a kind of local phenomenon. The information can be shared globally only after a process of diffusion. Therefore, several studies tackled this problem by developing structured populations, such as cellular genetic algorithms [11], multinational evolutionary algorithms [12], patchwork models [13], MAGA [7], MAEA-CSPs [8], and so on. In economics, R. H. Coase explained the sizing and formation of organizations from the framework of transaction costs [14]. The basic idea is that the organization exists because it reduces the overhead transaction costs associated with exchanging goods and services. This concept was introduced to the learning classifiers based on genetic algorithms by Wilcox in 1995 [15], which put emphasis on inventing an autonomous mechanism using transaction costs for forming appropriately sized organizations within a classifier. Actually, in the real world situation, to achieve their purposes, organizations will compete or cooperate with others so that they can gain more resources. As a result, the resources will be reasonably distributed among An Organizational Evolutionary Algorithm for Numerical Optimization Jing Liu, Member, IEEE Weicai Zhong, Member, IEEE and Licheng Jiao, Senior Member, IEEE E
SMCB-E-08102005-0551.R2 2 all organizations little by little.This process plays an important First,the number of the subpopulations and the size of each role in human societies.We think such a process can be viewed subpopulation of CGP-EAs are fixed during the evolutionary as a kind of optimization,and is an interesting new idea for process,whereas the number of organizations and the size of designing EAs. each organization of OEA change from generation to generation Taking inspiration from the aforementioned process,this Second,the main interaction among subpopulations is copying paper proposes a new framework for evolutionary optimization. better-performing or random individuals to neighboring named as Organizational Evolutionary Algorithm (OEA).In subpopulations at regular intervals.Whereas the interaction OEA,organizations are composed of members,and a among organizations is realized by the evolutionary operators. population is composed of organizations,so that a structured That is,OEA can be viewed as using additional operators in the population results.On the basis of such a structured population, migration process.Third,each subpopulation runs a local EA, all evolutionary operations are performed on organizations. while no evolutionary operations occur within the organizations Therefore,three evolutionary operators are developed for in the current form of OEA. organizations.These operators are composed of several However,from another viewpoint,OEA can be really viewed crossover and mutation operations in common use so as to prove as a kind of CGP-EA.Since CGP-EAs are just parallel the effectiveness of the new framework.The experimental techniques,they often present the same problem as traditional results on 15 UCOPs,13 COPs,and 4 well-studied engineering EAs.But OEA takes inspiration from simulating the interacting design problems show that OEA obtains good results. process among organizations in human societies,and the Being different from [15],OEA does not put emphasis on experimental results show that OEA obtains good performances forming the appropriately sized organizations,but on simulating for both UCOPs and COPs in a wide range of benchmark the interaction among organizations.Therefore,in OEA,all functions.Therefore,OEA can be viewed as a successful evolutionary operators are not directly performed on individuals development of CGP-EAs. but on organizations instead.As a result,there is no global Since EAs are unconstrained search techniques, selection at all,so the global fitness distribution is not required incorporating constraints into the fitness function of an EA is An organization interacts with others so that the information can still an open research area.There is a considerable amount of be diffused.Obviously,such a kind of population is more research regarding mechanisms that allow EAs to deal with similar to the real evolutionary mechanism in nature than the constraints. traditional population. The most common constraints handling methods in EAs is to In [10],we propose organizational coevolutionary algorithm use penalties.In these methods,a penalty term is added to the for classification (OCEC).But the organizations in OCEC are objective function.The penalty can be static,which is only different from the ones in OEA.OCEC is developed for solving related to the degree of constraint violation,or dynamic,which classification problems in data mining.Although both the is related to both the degree of constraint violation and the organizations in OCEC and in OEA are composed of members, generation number.The weakness of penalty methods is that the members in OCEC stand for the examples in the training set they often require several parameters.There also has some while the members in OEA stand for the real-valued vectors in literature proposing self-adaptive penalty methods,such as [17] the search space.Moreover,the fitness in OCEC is designed to used a two-stage penalty to measure the infeasibility,and no manifest the different importance of the attributes,while the parameter was used.Due to the simplicity and ease of fitness in OEA is the value of the objective functions.Of course. implementation,penalty methods are the most common their similarity is that both OCEC and OEA simulate the methods used in solving real world problems.Therefore,we interaction among organizations. incorporate a simplified version of the static penalty method B.Related Work into OEA,which only uses one parameter. The use of rules based on feasibility is another class of Some aspects of OEA are similar to the existing approaches. constraints handling method.Reference [18]used three simple The first is an analogy between OEA and similar EAs.The rules to deal with the constraints,and incorporated these rules second is the constraints handling techniques.In this subsection. into the self-adaptation mechanism of an evolution strategy we would like to briefly discuss the similarities and differences Since this method is proved to be effective in solving a wide between OEA and the existing approaches in these aspects. range of COPs,and no parameter is used,we also incorporate Since the organizations in OEA consist of members,and the the three rules into OEA,and make a comparison between OEA members are similar to the individuals used in traditional EAs. and SMES [18]in Subsection IV.C. one might argue that the organizations are similar to the Reference [19]introduced a stochastic ranking method in subpopulations in coarse-grained parallel EAs(CGP-EAs)or which the objective function values are used for ranking the multi-island EAs[16].CGP-EAs are a kind of distributed EA, solutions in the infeasible region of the search space.A and are a parallel implementation of EAs.In CGP-EAs, probability parameter is used to determine the likelihood of two evolution occurs in multiple parallel subpopulations,each individuals in the infeasible space being compared with each running a local EA,evolving independently with occasional other.This method is also proved to be effective in solving a migrations"of selected individuals among subpopulations. wide range of COPs,so a comparison is made between OEA There are several differences between OEA and CGP-EAs
SMCB-E-08102005-0551.R2 2 all organizations little by little. This process plays an important role in human societies. We think such a process can be viewed as a kind of optimization, and is an interesting new idea for designing EAs. Taking inspiration from the aforementioned process, this paper proposes a new framework for evolutionary optimization, named as Organizational Evolutionary Algorithm (OEA). In OEA, organizations are composed of members, and a population is composed of organizations, so that a structured population results. On the basis of such a structured population, all evolutionary operations are performed on organizations. Therefore, three evolutionary operators are developed for organizations. These operators are composed of several crossover and mutation operations in common use so as to prove the effectiveness of the new framework. The experimental results on 15 UCOPs, 13 COPs, and 4 well-studied engineering design problems show that OEA obtains good results. Being different from [15], OEA does not put emphasis on forming the appropriately sized organizations, but on simulating the interaction among organizations. Therefore, in OEA, all evolutionary operators are not directly performed on individuals, but on organizations instead. As a result, there is no global selection at all, so the global fitness distribution is not required. An organization interacts with others so that the information can be diffused. Obviously, such a kind of population is more similar to the real evolutionary mechanism in nature than the traditional population. In [10], we propose organizational coevolutionary algorithm for classification (OCEC). But the organizations in OCEC are different from the ones in OEA. OCEC is developed for solving classification problems in data mining. Although both the organizations in OCEC and in OEA are composed of members, the members in OCEC stand for the examples in the training set while the members in OEA stand for the real-valued vectors in the search space. Moreover, the fitness in OCEC is designed to manifest the different importance of the attributes, while the fitness in OEA is the value of the objective functions. Of course, their similarity is that both OCEC and OEA simulate the interaction among organizations. B. Related Work Some aspects of OEA are similar to the existing approaches. The first is an analogy between OEA and similar EAs. The second is the constraints handling techniques. In this subsection, we would like to briefly discuss the similarities and differences between OEA and the existing approaches in these aspects. Since the organizations in OEA consist of members, and the members are similar to the individuals used in traditional EAs, one might argue that the organizations are similar to the subpopulations in coarse-grained parallel EAs (CGP-EAs) or multi-island EAs [16]. CGP-EAs are a kind of distributed EA, and are a parallel implementation of EAs. In CGP-EAs, evolution occurs in multiple parallel subpopulations, each running a local EA, evolving independently with occasional “migrations” of selected individuals among subpopulations. There are several differences between OEA and CGP-EAs. First, the number of the subpopulations and the size of each subpopulation of CGP-EAs are fixed during the evolutionary process, whereas the number of organizations and the size of each organization of OEA change from generation to generation. Second, the main interaction among subpopulations is copying better-performing or random individuals to neighboring subpopulations at regular intervals. Whereas the interaction among organizations is realized by the evolutionary operators. That is, OEA can be viewed as using additional operators in the migration process. Third, each subpopulation runs a local EA, while no evolutionary operations occur within the organizations in the current form of OEA. However, from another viewpoint, OEA can be really viewed as a kind of CGP-EA. Since CGP-EAs are just parallel techniques, they often present the same problem as traditional EAs. But OEA takes inspiration from simulating the interacting process among organizations in human societies, and the experimental results show that OEA obtains good performances for both UCOPs and COPs in a wide range of benchmark functions. Therefore, OEA can be viewed as a successful development of CGP-EAs. Since EAs are unconstrained search techniques, incorporating constraints into the fitness function of an EA is still an open research area. There is a considerable amount of research regarding mechanisms that allow EAs to deal with constraints. The most common constraints handling methods in EAs is to use penalties. In these methods, a penalty term is added to the objective function. The penalty can be static, which is only related to the degree of constraint violation, or dynamic, which is related to both the degree of constraint violation and the generation number. The weakness of penalty methods is that they often require several parameters. There also has some literature proposing self-adaptive penalty methods, such as [17] used a two-stage penalty to measure the infeasibility, and no parameter was used. Due to the simplicity and ease of implementation, penalty methods are the most common methods used in solving real world problems. Therefore, we incorporate a simplified version of the static penalty method into OEA, which only uses one parameter. The use of rules based on feasibility is another class of constraints handling method. Reference [18] used three simple rules to deal with the constraints, and incorporated these rules into the self-adaptation mechanism of an evolution strategy. Since this method is proved to be effective in solving a wide range of COPs, and no parameter is used, we also incorporate the three rules into OEA, and make a comparison between OEA and SMES [18] in Subsection IV.C. Reference [19] introduced a stochastic ranking method in which the objective function values are used for ranking the solutions in the infeasible region of the search space. A probability parameter is used to determine the likelihood of two individuals in the infeasible space being compared with each other. This method is also proved to be effective in solving a wide range of COPs, so a comparison is made between OEA
SMCB-E-08102005-0551.R2 and this method in Subsection IV.B. feasible solution wins; Reference [20]used the Pareto ranking to deal with 3)If both solutions are infeasible,the one with the smaller constraints.Although this method can reduce the number of sum of constraint violation is preferred. additional inputs required for constraints handling,the This technique is non problem-dependent,and no parameter computational time involved in nondominated sorting was needs to be tuned.In the following text,this technique is labeled increased.Reference [20]used four well-studied engineering as CHc. design problems to evaluate the performance of the proposed C.Organization Definition method,so a comparison is also made between OEA and SCA 20]in Subsection IV.D. In OEA.an organization consists of several members,and a There are many other constraints handling methods making member is a solution of the objective function.Since a UCOP use of different techniques,such as GENOCOP [21], can be viewed as a COP satisfying the constraints,we define GENOCOP II [22],GENOCOP III [23],microgenetic Member for both problems as follows, algorithm [24],varying fitness functions [25],homomorphous Definition 1:A Member is a real-valued vector that belongs mappings method [26],coevolutionary augmented Lagrangian to the search space,namely,Membere S.There are two method [27],the methods based on multiobjective algorithms measures,Memberf and Member',to evaluate the member's [28],[29],and so on.More detailed descriptions about quality.Member denotes the fitness and constraints handling in EAs were given in [30],[31]. [-f(Member)for UCOPs Member" -f(Member)for COPs with CHc (5) II.ORGANIZATIONAL EVOLUTIONARY ALGORITHM -(Member)for COPs with CHp Member denotes the sum of constraint violation and A.Problem Definition A UCOP can be formulated as solving the objective function for UCOPs minimize fx),1 ...,x)eS (1) Member ={0 for COPs with CHp where SCR"defines the search space which is an n-dimensional maxg(Member)for COPs with CHe space bounded by the parametric constraints x,sx,x,,i=1, (6) 2,,n.Thus,S=[s,,where=(s,玉，，x)and Thus,the purpose of OEA is maximizing Member.When comparing the qualities of two members,both Memberf and 天=（瓦，x32,,n) Member'should be considered.So the members are compared A COP can be formulated as solving the objective function according to Definition 2. minimize f(x),x=(x,x,,x)esF (2) Definition 2:If two members,Member and Memberz, where S is the same with that of(1),and the feasible region Fis satisfy (7)or(8)or(9),then Member is better than Member2, and labeled as Member Member,. F={x∈R"g,(x)≤0，j=1,2,…,m (3) (Member"=0)and(Member:=0)and(Member>Member) where gx),/=1,2,...,m are constraints. (7) B.Constraints Handling (Member'=o）and（Member,>0j (8) The main purpose of this paper is to propose OEA and (Member>0)and(Member >0)and(Member<Member) illustrate the effectiveness of OEA's search ability,so two kinds (9) of simple constraints handling techniques are used. Definition 2 realizes the three rules of CHc.By Definitions 1 The first technique uses a simplified version of the static penalty method [32],that is,COPs are transformed into UCOPs and 2,OEA can use a uniform framework to deal with both by adding a very simple penalty term in(4) UCOPs and COPs with the two different constraints handling techniques.On the basis of Definitions 1 and 2,an w(x)=f(x)+max(0.g(x) (4) Organization is defined as follows, where AeR is a penalty coefficient and needs to be tuned for Definition 3:An Organization,org,is a set of members,and different problems.In the following text,this technique is the best member is called Leader,which is labeled as Leader labeled as CHp. that is,an organization and the leader satisfy (10)and(11), The second technique has been widely used in EAs for COPs where lorg indicates the cardinality of org. [18],[33],[34],and has been also extended to multiobjective (org={Member,Member,,Member》and(org≠) optimization problems [35],[36],[37].This technique uses a (10) comparison mechanism based on the following rules, VMembere org,LeaderMember (11) 1)Between two feasible solutions,the one with the larger fitness value wins; When two organizations are compared,only the two leaders are 2)If one solution is feasible and the other is infeasible.the considered.Namely,org is better than org2 if
SMCB-E-08102005-0551.R2 3 and this method in Subsection IV.B. Reference [20] used the Pareto ranking to deal with constraints. Although this method can reduce the number of additional inputs required for constraints handling, the computational time involved in nondominated sorting was increased. Reference [20] used four well-studied engineering design problems to evaluate the performance of the proposed method, so a comparison is also made between OEA and SCA [20] in Subsection IV.D. There are many other constraints handling methods making use of different techniques, such as GENOCOP [21], GENOCOP II [22], GENOCOP III [23], microgenetic algorithm [24], varying fitness functions [25], homomorphous mappings method [26], coevolutionary augmented Lagrangian method [27], the methods based on multiobjective algorithms [28], [29], and so on. More detailed descriptions about constraints handling in EAs were given in [30], [31]. II. ORGANIZATIONAL EVOLUTIONARY ALGORITHM A. Problem Definition A UCOP can be formulated as solving the objective function minimize f(x), x=(x1, x2, …, xn)∈S (1) where S⊆Rn defines the search space which is an n-dimensional space bounded by the parametric constraints iii xxx ≤ ≤ , i=1, 2, …, n. Thus, S = [ ] x x , , where 1 2 ( , , ..., ) n x = xx x and 1 2 ( , , ..., ) n x = xx x . A COP can be formulated as solving the objective function minimize ( ), ( , , , ) 1 2 n f xx x x x = ∈ ∩ S F (2) where S is the same with that of (1), and the feasible region F is { ( ) 0, 1, 2, , } n j F R =∈ ≤ = x x g j m (3) where gj(x), j=1, 2, …, m are constraints. B. Constraints Handling The main purpose of this paper is to propose OEA and illustrate the effectiveness of OEA’s search ability, so two kinds of simple constraints handling techniques are used. The first technique uses a simplified version of the static penalty method [32], that is, COPs are transformed into UCOPs by adding a very simple penalty term in (4) { } 1 ( ) ( ) max 0, ( ) m j j ψ fA g = xx x = + ∑ (4) where A∈R is a penalty coefficient and needs to be tuned for different problems. In the following text, this technique is labeled as CHp. The second technique has been widely used in EAs for COPs [18], [33], [34], and has been also extended to multiobjective optimization problems [35], [36], [37]. This technique uses a comparison mechanism based on the following rules, 1) Between two feasible solutions, the one with the larger fitness value wins; 2) If one solution is feasible and the other is infeasible, the feasible solution wins; 3) If both solutions are infeasible, the one with the smaller sum of constraint violation is preferred. This technique is non problem-dependent, and no parameter needs to be tuned. In the following text, this technique is labeled as CHc. C. Organization Definition In OEA, an organization consists of several members, and a member is a solution of the objective function. Since a UCOP can be viewed as a COP satisfying the constraints, we define Member for both problems as follows, Definition 1: A Member is a real-valued vector that belongs to the search space, namely, Member∈S. There are two measures, MemberF and MemberV , to evaluate the member’s quality. MemberF denotes the fitness and ( ) for UCOPs ( ) for COPs with CHc ( ) for COPs with CHp F f f ψ − = − − Member Member Member Member (5) MemberV denotes the sum of constraint violation and { } 1 0 for UCOPs 0 for COPs with CHp max 0, ( ) for COPs with CHc V m j j g = = ∑ Member Member (6) Thus, the purpose of OEA is maximizing MemberF . When comparing the qualities of two members, both MemberF and MemberV should be considered. So the members are compared according to Definition 2. Definition 2: If two members, Member1 and Member2, satisfy (7) or (8) or (9), then Member1 is better than Member2, and labeled as Member Member 1 2 . 1 2 12 ( =0)and( 0)and( ) V V FF Member Member Member Member = > (7) ( )( ) 1 2 =0 and 0 V V Member Member > (8) 1 2 12 ( >0)and( 0)and( ) V V VV Member Member Member Member > < (9) Definition 2 realizes the three rules of CHc. By Definitions 1 and 2, OEA can use a uniform framework to deal with both UCOPs and COPs with the two different constraints handling techniques. On the basis of Definitions 1 and 2, an Organization is defined as follows, Definition 3: An Organization, org, is a set of members, and the best member is called Leader, which is labeled as Leaderorg, that is, an organization and the leader satisfy (10) and (11), where |org| indicates the cardinality of org. ( ) org org = ≠∅ {Member Member Member 1 2 || , , ..., and org } ( ) (10) , org ∀ ∈ Member Leader Member org ≺ (11) When two organizations are compared, only the two leaders are considered. Namely, org1 is better than org2 if
SMCB-E-08102005-0551.R2 Leader Leaderr,and labeled as orgorg2 (AnStr1);otherwise they are generated by Annexing Strategy 2 (AnStr2).The subscript j in U(0,1)indicates that the random D.Evolutionary Operators for Organications number is generated anew for each value of /and AnStrl and In the real world situation,there is a severe competition AnStr2 are given by(13)and(14),respectively.Given that the among organizations,and the strong ones always annex the leader of orgpl is (x1,x2,...,x)and new members are r(,, weak ones.In OEA,the strength of an organization manifests in 52,…,5j户1,2，，N the fitness of the leader.So the purpose of each organization is In AnStr1,rj=1,2,...,N are determined by (13), to increase the leader's fitness as much as possible.To achieve B<X this purpose,each organization must interact with others.On the B>k, B=xx+ax(xx-yix) (13) basis of such interactions,three evolutionary operators are B.otherwise k=12,,n designed,that is,the splitting operator,the annexing operator, and the cooperating operator. where is a uniformly distributed random number over [0,1], Splitting operator:In human societies,an organization and is generated anew for each value of k. whose size is too large usually is split into several small In AnStr2,rj=1,2,...,N are determined by (14), organizations so that they can be easily managed.In OEA,if 4+×(-4)B(0,1)< most of the members belong to the same organization,the ,k=1,2,,n(14) otherwise evolutionary operations would be disabled.So when the size of an organization exceeds a limit,this organization must be split. where a and B are uniformly distributed random numbers over Let Maxos be the parameter controlling the maximum size of an [0,1],and B is generated anew for each value of k. organization,and Maxos1.If a parent organization,orgp After rj=1,2,...N are generated,,2,...,N are satisfies(12),then orgp will be split into two child organizations, determined by(15), orgel and org. r Dyi (orgMaxs)or(org Maxas)and (( ZM= (y,>r,)and{0,(0,)<exp(gy-y5)}(15) (12) otherwise where U(,)is a uniform random number generator,and No is As can be seen,when r is better thany gets into orge so as the number of organizations in the whole population.To keep to improve the quality of orge When r,is worse thany in order the randomicity and a small difference between the sizes of to maintain the diversity,gets into org with a probability.For org and org to members are first randomly more clarity.Fig.2 illustrates the operations in this operator. selected from orgp to form orge,and the remainder forms org2. orge has (M+N)members,where Member,i=1,2,...,M,come For more clarity,Fig.1 illustrates the operations in this operator. from orgpl and Member i=M+1,M+2,...,M+N are generated As can be seen,without loss of generality,let the ith member is by the leader of orgpl and the members of orgp2 together.After orge is generated,the leader is also selected.In this case,the the best,and Mbe a random integer between and leader is the ith member (the leader of orgpl),or the best Therefore,the ith member is the Leader of orgp Mmembers are member among Member,Memberv2,...,and MemberM-N. randomly selected from orgp to form orgel,and the other Cooperating operator:This operator realizes the lorgp-M members form orge2.After orgel and orge2 are cooperation between two organizations.The leaders of the generated,the best members in orge and org are selected to be organizations interact with each other to generate two new their leaders,that is,the jth member in orge and the kth member members.Then,in each organization,a member being worse in orge2 are selected. than the new member is replaced. Annexing operator:This operator realizes the competition Two parent organizations,orgp=1,x2,...,x and between two organizations.The better organization is the orgp=2,,),are randomly selected from the current winner,and the other is the loser.The winner will annex the generation.They will cooperate with each other to generate two loser to form a larger organization.The members of the winner child organizations,orge and org2.Let CSe(0,1)be a can directly go into the new organization while those of the loser predefined parameter.Then,if U(0,1)<CS,orgel and org2 are must die.But the members of the loser maybe still have useful generated by Cooperating Strategy 1(CoStr1);otherwise they information,so they interact with the leader of the winner to are generated by Cooperating Strategy 2 (CoStr2),where generate new members. CoStrl and CoStr2 are given by (16)and(17),respectively. Two parent organizations,orgp=2,and Given that the leader of orgpl is (x,x2..,),the leader of orgp2=1,2,...,yN),are randomly selected from the current orgp2 is (v1,y2,...,y),and two new members are q=(q,q2,.., generation.Without loss of generality,let orgplD orgp2.Thus,q)and r=(r,2,...m). orgp will annex orgp2 to generate a child organization,org=, In CoStrl,g and r are determined by (16), 22,....ZM Z,ZM2,....ZMN).Where i=1,2,...,M.Let ASE(0,1)be a predefined parameter.Then,if U(0,1)<AS, g4=0×+(1-X4,k=l,2,n (16) =M+1,M+2,...,M+N are generated by Annexing Strategy 1 =(1-a)xx+×y
SMCB-E-08102005-0551.R2 4 1 2 Leader Leader org org , and labeled as org1org2. D. Evolutionary Operators for Organizations In the real world situation, there is a severe competition among organizations, and the strong ones always annex the weak ones. In OEA, the strength of an organization manifests in the fitness of the leader. So the purpose of each organization is to increase the leader’s fitness as much as possible. To achieve this purpose, each organization must interact with others. On the basis of such interactions, three evolutionary operators are designed, that is, the splitting operator, the annexing operator, and the cooperating operator. Splitting operator: In human societies, an organization whose size is too large usually is split into several small organizations so that they can be easily managed. In OEA, if most of the members belong to the same organization, the evolutionary operations would be disabled. So when the size of an organization exceeds a limit, this organization must be split. Let MaxOS be the parameter controlling the maximum size of an organization, and MaxOS>1. If a parent organization, orgp, satisfies (12), then orgp will be split into two child organizations, orgc1 and orgc2. ( ) ( ) () | | or | | and 0,1 { ( ) o } org OS OS N org Max org Max U >≤ < (12) where U(⋅, ⋅) is a uniform random number generator, and No is the number of organizations in the whole population. To keep the randomicity and a small difference between the sizes of orgc1 and orgc2, | | 3 p org to 2| | 3 p org members are first randomly selected from orgp to form orgc1, and the remainder forms orgc2. For more clarity, Fig.1 illustrates the operations in this operator. As can be seen, without loss of generality, let the ith member is the best, and M be a random integer between | | 3 p org and 2| | 3 p org . Therefore, the ith member is the Leader of orgp, M members are randomly selected from orgp to form orgc1, and the other |orgp-M| members form orgc2. After orgc1 and orgc2 are generated, the best members in orgc1 and orgc2 are selected to be their leaders, that is, the jth member in orgc1 and the kth member in orgc2 are selected. Annexing operator: This operator realizes the competition between two organizations. The better organization is the winner, and the other is the loser. The winner will annex the loser to form a larger organization. The members of the winner can directly go into the new organization while those of the loser must die. But the members of the loser maybe still have useful information, so they interact with the leader of the winner to generate new members. Two parent organizations, orgp1={x1, x2, …, xM} and orgp2={y1, y2, …, yN}, are randomly selected from the current generation. Without loss of generality, let orgp1orgp2. Thus, orgp1 will annex orgp2 to generate a child organization, orgc={z1, z2, …, zM, zM+1, zM+2, …, zM+N}. Where zi=xi, i=1, 2, …, M. Let AS∈(0, 1) be a predefined parameter. Then, if Uj(0,1)<AS, zj, j=M+1, M+2, …, M+N are generated by Annexing Strategy 1 (AnStr1); otherwise they are generated by Annexing Strategy 2 (AnStr2). The subscript j in Uj(0,1) indicates that the random number is generated anew for each value of j, and AnStr1 and AnStr2 are given by (13) and (14), respectively. Given that the leader of orgp1 is (x1, x2, …, xn) and new members are rj=(rj,1, rj,2, …, rj,n), j=1, 2, …, N. In AnStr1, rj , j=1, 2, …, N are determined by (13), ( ) , , , 1, 2, ..., otherwise k kk k k k k jk jk k k k k x x x xy rx x k n β β α β β < =+× − = > = (13) where αk is a uniformly distributed random number over [0, 1], and is generated anew for each value of k. In AnStr2, rj , j=1, 2, …, N are determined by (14), ( ) () 1 , 0,1 , 1, 2, ..., otherwise k kk k n j k k x xx r kn x +× − < α β = = (14) where α and βk are uniformly distributed random numbers over [0, 1], and βk is generated anew for each value of k. After rj, j=1, 2, …, N are generated, zj+M, j=1, 2, …, N are determined by (15), ( ) { } ( ) ( ) and 0, 1 exp otherwise j jj F F jM j j j j j j j + U = <− r ry z r yr r y y (15) As can be seen, when rj is better than yj, rj gets into orgc so as to improve the quality of orgc. When rj is worse than yj, in order to maintain the diversity, rj gets into orgc with a probability. For more clarity, Fig.2 illustrates the operations in this operator. orgc has (M+N) members, where Memberi, i=1, 2, …, M, come from orgp1 and Memberi, i=M+1, M+2, …, M+N are generated by the leader of orgp1 and the members of orgp2 together. After orgc is generated, the leader is also selected. In this case, the leader is the ith member (the leader of orgp1), or the best member among MemberM+1, MemberM+2, …, and MemberM+N. Cooperating operator: This operator realizes the cooperation between two organizations. The leaders of the organizations interact with each other to generate two new members. Then, in each organization, a member being worse than the new member is replaced. Two parent organizations, orgp1={x1, x2, …, xM} and orgp2={y1, y2, …, yN}, are randomly selected from the current generation. They will cooperate with each other to generate two child organizations, orgc1 and orgc2. Let CS∈(0, 1) be a predefined parameter. Then, if U(0, 1)<CS, orgc1 and orgc2 are generated by Cooperating Strategy 1 (CoStr1); otherwise they are generated by Cooperating Strategy 2 (CoStr2), where CoStr1 and CoStr2 are given by (16) and (17), respectively. Given that the leader of orgp1 is (x1, x2, …, xn), the leader of orgp2 is (y1, y2, …, yn), and two new members are q=(q1, q2, …, qn) and r=(r1, r2, …, rn). In CoStr1, q and r are determined by (16), ( ) ( ) 1 , 1, 2, ..., 1 k kk k k k k k kk qx y k n r xy α α α α = × +− × = =− ×+ × (16)
SMCB-E-08102005-0551.R2 where a is the same with that of(13). generation.Finally,the best member in the whole population is In CoStr2,g and r are determined by (17), output as the result.The details are shown in ALGORITHM 1. 9=(,X2,…,X,,1,…,,1X+2…,X ALGORITHM 1 Organizational Evolutionary r=（,2,…,y-1,X,x+,…,X2,%2,yn2,…,yn Algorithm 01:begin (17) 02: Initializing population Po with No where 1<i<n,1<iz<n,and i<i. organizations,and each organization After g and rare generated,orge and org are determined by has one member; (18)and(19),respectively, 03: t←-0； [{x,x2,,,,x41x42,…,xw} 04: while (the termination criteria are not reached)do orge= 3x,∈ogp1,qP (18) 05: begin orgp otherwise 06: For each organization in Pt,if it satisfies (12),performing the {,h,,yy4y2,,w splitting operator on it,deleting 0r8e2= y,∈or82,rPy (19) it from P,and adding the child organizations into P1i 0r8p2 otherwise 07: while(the number of organizations For more clarity,Fig.3 illustrates the operations in this in P:is greater than 1)do 08: operator.The number of members oforge and org2 is the same begin 09: Randomly selecting two parent with that of orgp and orgp2,respectively.The kth member in organizations,orgpl and orgp2, orge and the lth member in org2 are determined by the leaders from P:i of orgpl and orgp2 together,and the others are the same with 10: Performing the annexing operator those of orgp and orgp2.After orge and orge are generated, or the cooperating operator on their leaders are also selected.In this case,the leader of orge is orgpl and orgp2 with the same Members or the leader of orgp,and the leader of org is probability; Member or the leader of orgp2. 11: Deleting orgpl and orgp2 from Pe, In fact,AnStrl is the heuristic crossover [38],AnStr2 is a and adding the child kind of mutation.CoStrl is the arithmetical crossover,and organizations into Pi; 12: end; CoStr2 is the discrete crossover [31].The three operators play different roles in OEA.The splitting operator restricts the size 13: Moving the organization in P:to of an organization and makes some organizations directly go Pu1i 14: t←-t+1； into the next generation.This manner is in favor of maintaining 15: end; the diversity of the population.Both AnStrl and AnStr2 make 16: Output the best member in P; use of the information of a leader,and are of the ability in local 17:end. search.On the other hand.since the leader is the best in an organization,the annexing operator can search around each In the initialization,each organization has only one member, leader.This is equivalent to performing a hill-climbing operator. and the population has total No organizations.During the As a result,the annexing operator can give more chances to the evolutionary process,under the effects of the annexing operator promising members.The cooperating operator improves the and the splitting operator,the organizations with only one qualities of the members by increasing the interaction between member grow to the ones with multiple members.Although the two leaders,so it is equivalent to performing a global search. number of organizations varies from generation to generation, E.Implementation ofOEA the number of members in the whole population remains In OEA,the population consists of organizations,and the constant. above three operators must be reasonably performed on organizations so as to obtain high quality members.In OEA,the size of each organization in the population is first checked in III.EXPERIMENTAL STUDIES ON UNCONSTRAINED each generation.If the size ofan organization satisfies(12),then OPTIMIZATION PROBLEMS the splitting operator is performed on this organization.Next, In this section,15 benchmark functions(F01-F15)are used to two parent organizations are randomly selected from the test the performance of OEA in solving UCOPs.F01-F13 are population,and the annexing operator or the cooperating fif in [39]and F14,F15 areff in [40].The problem operator are performed on them with the same probability.This dimension is set to 30 for F01-F13 and 100 for F14 and F15.In process is continued until the number of organizations in the this manner,these functions have so many local minima that population is less than 2.The population evolves generation by they are challenging enough for performance evaluation
SMCB-E-08102005-0551.R2 5 where αk is the same with that of (13). In CoStr2, q and r are determined by (17), ( ) ( ) 1 11 22 2 1 11 2 2 2 12 1 1 1 2 12 1 1 1 2 , , , , , , , , , , , , , , , , , , , , , , i ii ii i n i ii i i i n xx x y y y x x x yy y x x x y y y − + ++ − + ++ = = q r (17) where 1<i1<n, 1<i2<n, and i1<i2. After q and r are generated, orgc1 and orgc2 are determined by (18) and (19), respectively, { } 12 1 1 2 1 1 1 , , , , , , , , , otherwise i ii M c ip i p org org org − ++ = ∃∈ ≺ x x x qx x x x qx (18) { 12 1 1 2 } 2 2 2 , , , , , , , , , otherwise j jj N c jp j p org org org − ++ = ∃∈ ≺ y y y ry y y y ry (19) For more clarity, Fig.3 illustrates the operations in this operator. The number of members of orgc1 and orgc2 is the same with that of orgp1 and orgp2, respectively. The kth member in orgc1 and the lth member in orgc2 are determined by the leaders of orgp1 and orgp2 together, and the others are the same with those of orgp1 and orgp2. After orgc1 and orgc2 are generated, their leaders are also selected. In this case, the leader of orgc1 is Memberk or the leader of orgp1, and the leader of orgc2 is Memberl or the leader of orgp2. In fact, AnStr1 is the heuristic crossover [38], AnStr2 is a kind of mutation, CoStr1 is the arithmetical crossover, and CoStr2 is the discrete crossover [31]. The three operators play different roles in OEA. The splitting operator restricts the size of an organization and makes some organizations directly go into the next generation. This manner is in favor of maintaining the diversity of the population. Both AnStr1 and AnStr2 make use of the information of a leader, and are of the ability in local search. On the other hand, since the leader is the best in an organization, the annexing operator can search around each leader. This is equivalent to performing a hill-climbing operator. As a result, the annexing operator can give more chances to the promising members. The cooperating operator improves the qualities of the members by increasing the interaction between two leaders, so it is equivalent to performing a global search. E. Implementation of OEA In OEA, the population consists of organizations, and the above three operators must be reasonably performed on organizations so as to obtain high quality members. In OEA, the size of each organization in the population is first checked in each generation. If the size of an organization satisfies (12), then the splitting operator is performed on this organization. Next, two parent organizations are randomly selected from the population, and the annexing operator or the cooperating operator are performed on them with the same probability. This process is continued until the number of organizations in the population is less than 2. The population evolves generation by generation. Finally, the best member in the whole population is output as the result. The details are shown in ALGORITHM 1. ALGORITHM 1 Organizational Evolutionary Algorithm 01: begin 02: Initializing population P0 with No organizations, and each organization has one member; 03: t←0; 04: while (the termination criteria are not reached) do 05: begin 06: For each organization in Pt, if it satisfies (12), performing the splitting operator on it, deleting it from Pt, and adding the child organizations into Pt+1; 07: while(the number of organizations in Pt is greater than 1)do 08: begin 09: Randomly selecting two parent organizations, orgp1 and orgp2, from Pt; 10: Performing the annexing operator or the cooperating operator on orgp1 and orgp2 with the same probability; 11: Deleting orgp1 and orgp2 from Pt, and adding the child organizations into Pt+1; 12: end; 13: Moving the organization in Pt to Pt+1; 14: t←t+1; 15: end; 16: Output the best member in Pt; 17: end. In the initialization, each organization has only one member, and the population has total No organizations. During the evolutionary process, under the effects of the annexing operator and the splitting operator, the organizations with only one member grow to the ones with multiple members. Although the number of organizations varies from generation to generation, the number of members in the whole population remains constant. III. EXPERIMENTAL STUDIES ON UNCONSTRAINED OPTIMIZATION PROBLEMS In this section, 15 benchmark functions (F01-F15) are used to test the performance of OEA in solving UCOPs. F01-F13 are f1-f13 in [39] and F14, F15 are f7, f9 in [40]. The problem dimension is set to 30 for F01-F13 and 100 for F14 and F15. In this manner, these functions have so many local minima that they are challenging enough for performance evaluation