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