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