Multi Objective Optimization with a New Evolutionary Algorithm

Nowadays, many optimization problems in various sciences include several conflicting objective functions (OFs) while desirable condition for all functions should be supplied. Since increasing desirability of one OF might not necessarily increase the desirability of others, selecting the best solution in multi objective problems (MOPs) has always been a challenge. Therefore, a set of solutions is assessed to supply desirable condition for all OFs, called Pareto, and Pareto front is the best one in each problem. Different solutions on a Pareto are not superior to each other based on their OF values. A set of non-dominant solutions (NDSs) can be available for decision makers by presenting the Pareto front for each MOP and they can select a solution among several possible ones considering the problem’s conditions.

Specific methods are used for solving MOPs. Complexities of optimization problems are ignored in some methods through simplification or linearization and several OFs are considered as a single function applying weight factors or priority structures (Huang et al. 2005; Stanimirović et al. 2011). Due to lack of information about conflicting objectives such as priority of them in different problems, it is impossible to find a unique solution as the best one applying simplifications for MOPs and that is how several specific optimization methods are developed (Yang et al. 2007; Barros et al. 2008; Niknam et al. 2011; Kourakosa and Mantogloub 2013). MOPs can be solved in two general categories: (Barros et al. 2008) preference-structure based (PSB) methods in which the problem is solved as a single objective problem (SOP) considering the importance degree of different OFs compared with each other; and (Deb 2002) best-pareto based (BPB) methods in which a set of optimum NDSs is determined for the problem.

Difficulties of the PSB methods have led to wide application of BPB methods. Evolutionary optimization algorithms (EOAs) such as genetic algorithm (GA) (Deb 2002), ant colony optimization (ACO) algorithm (Rada-Vilela et al. 2013), particle swarm optimization (PSO) algorithm (Reyes-Sierra and Coello Coello 2006) and so forth, find a set of possible solutions instead of one solution for the problem in each run. Therefore, they are more efficient in solving MOPs and their required computational time can be controlled. Since EOAs usually consider a separate set of possible solutions for optimizing each OF, a set of solutions can be determined out of combined sets in each run which are located on the nearest Pareto to the Pareto front. So, each function is optimized in relevant set of solutions. To consider impacts of each function’s optimization on the other functions, some solutions of different sets are relocated with each other in each iteration to simultaneously optimize all OFs. Finally, a set of optimum solutions is obtained in which all OFs become near to their optimum condition as much as possible.

Comprehensive evolutionary algorithm (CEA) is a new EOA that can solve SOPs and MOPs with a unique structure. In the general process of developing CEA, a set of initial solutions is considered for each OF which is optimized based on three processes of selection, generation, and replacement. These processes are consecutively done for specific times to achieve the desirable condition for all OFs which means obtaining the best Pareto for the problem. CEA can present a Pareto with high density (including more possible solutions) and the best dispersion in the objective space of the problem. Also, this algorithm can achieve the global optimum solution of some functions and such solutions on the obtained final Pareto shows high capabilities of CEA in solving MOPs. In addition, CEA is able to implicitly analyze the sensitivity of the results to some parameters based on the problem condition as one of the main novelty of this algorithm. In this study, performance of CEA is assessed for solving several mathematical problems and a reservoir operation problem.

Two main factors in optimization are: (Barros et al. 2008) OF as a scale for evaluating the problem qualification; and (Deb 2002) constraints as conditions for evaluating the desirability of OF for different situations in the problem. Evaluated OF according to the problem constraints is called fitness function and the desirable conditions in each problem are defined based on satisfying all constraints.

CEA can present a near to optimum solution for SOPs and the best set of NDSs (the best Pareto) for MOPs. Flowchart of the CEA for MOPs is shown in Fig. 1. According to this figure, some information is necessary about algorithm parameters and simulation model of the problem. The appropriate values for some parameters are determined either by the user or by CEA, considering the problem’s conditions. Considering CEA’s capability for implicitly sensitivity analysis compared to other EOAs, only algorithmic parameters defined by the user require sensitivity analysis. In multi objective optimization with CEA, several sets of possible solutions are considered and each OF is evaluated in one of these sets while other functions are assessed in other sets simultaneously in an iterative process to create final NDS set. Three processes of selection, generation and replacement based on different operators, are followed in each iteration. In CEA a wide range of selection and generation operators is considered which can be selectively activated by the user in optimization process. In other words, different selection and generation operators are applied in CEA to solve optimization problems based on user choices.

Defined number of solutions are selected or generated in each set by activated operators for selection or generation processes. Therefore, each operator can have a share in optimizing each OF in each problem. The operator’s share shows the percent of total number of solutions in each set which are produced by that operator. So, in the beginning of optimization, a set of initial solutions is simultaneously generated for each OF considering allowable range for decision variables. The fitness function of each solution is calculated after simulating the problem for each set. There could be some solutions that do not satisfy at least one constraint of the problem, called infeasible solutions. These solutions could be removed from the set, modified to become feasible solutions, or taken a value corresponding to the amount of violation from constraints named penalty value. The latter is considered in CEA. Then, the algorithm starts the iterative optimization process (in the Fig. 1, parameter It counts number of iterations). In the first iteration, all sets of different OFs are integrated to achieve an initial set of NDSs. After that, in other iterations, first sets of solutions for different OFs are integrated and initial set of NDSs for the current iteration is defined. Then, initial set and final set of NDSs, respectively obtained at the end of the current and previous iterations, are integrated and a final set of NDSs is defined at the end of the current iteration. The final set of NDSs at the end of each iteration would be considered as the final Pareto for the MOP at the end of each iteration. The distance of the obtained Pareto at the end of each iteration from a base point (usually the origin of coordinate) is considered as a scale to identify the best Pareto for each problem.

If the defined stopping criteria for the problem is satisfied, the final best Pareto would be presented as the solution of the problem. The stopping criteria can be defined in different forms. In CEA, two criteria including number of algorithm iterations and the least difference (according to the computational precision defined by the user) between the obtained Paretos’ distance in several consecutive iterations are simultaneously considered as the stopping criteria. The number of consecutive iterations for assessing the stopping criteria is determined through implicit sensitivity analysis by the algorithm. If the stopping criteria is not satisfied, the optimization process would continue based on selecting the best solution for each set from the final Pareto, obtained at the end of the current iteration. Selection process is done based on fitness functions in which in each iteration, numbers of superior solutions in each set are selected. Two types of generation processes, crossover and mutation, are considered in CEA to produce new solutions for the next iteration (based on selected solutions through selection process) considering the share of each operator. At the end, there are new sets of solutions for each OF and their fitness function needs to be calculated. Then, performance of various selection and generation operators is evaluated and the share of each operator is modified according to its performance, enabling the algorithm to directly evaluate the impact of different operators through optimization process and identify the efficient operators in each problem. In other words, CEA does an implicit sensitivity analysis for activated selection and generation operators. Also, impact (share) of operators with undesirable performance is reduced at the end of each iteration to keep the algorithm move forward with higher quality and speed.

In multi objective algorithms which consider a separate set of solutions for each OF, applying a technique to influence each function by current optimum situation of other functions is necessary. It leads to optimize all OFs at the same time. So, at the end of each iteration, final best Pareto is sorted for each OF and numbers of best solutions (in the first ranks) are moved to all sets of solutions except the set of solution related to the considered OF. Finally, there will be a new set of solutions for each OF and the next iteration of the algorithm can be started.

Several operators for selection and generation processes are considered in CEA to make it more comprehensive than other evolutionary algorithms. Four operators of roulette wheel (Lipowski and Lipowska 2012), tournament (Miller and Goldberg 1995), random, and Boltzmann (Lee 2003) are considered as selection operators. In roulette wheel operator, solution with the best (worst) fitness function would have highest (lowest, not zero) selection probability. In tournament operator in CEA, solutions that are not selected in each iteration, can be evaluated again in the next iteration. In random operators, selecting solutions with less desirability is possible and it may reduce the convergence speed of the algorithm. Although, undesired impact of this situation is moderated due to implicit sensitivity analysis of the operators in CEA. Boltzmann operator generates a new solution in the allowable range of decision variables. If the new solution is better than the best solution of the current iteration based on the fitness function, it will be selected as a superior solution for the next iteration.

Possible solutions in each iteration are generated by two kinds of operators in CEA, twenty-four types of crossover operators (classified into three categories of one-point cut, two-point cut, and full crossover) and five types of mutation operators. A row of decision variables is considered as a possible solution in CEA. Thus, in one and two-point cut crossovers, the structure of a solution is broken from one and two points, respectively. Also, there is no break point in full crossover operators and various types of mutation operators. For all crossover operators, one or two new solutions are generated based on two selected solutions while in all mutation operators, only a new solution is generated based on one selected solution. Having different new solutions through all generation operators provides opportunity to extend evaluating the decision space in each problem. If allowable range for decision variables is not satisfied in some types of crossover and mutation operators, a random value for related decision variable will be generated in the allowable range and replaced with its invalid value in the new solution.

CEA is validated through solving several mathematical optimization problems and comparing the results with non-dominated sorting genetic algorithm II (NSGA-II) in MATLAB R2012b using a Core i5 computer with CPU of 2.67 GHz and 4.00 GB RAM.

Performance of CEA in water resources management problems is evaluated considering a multi objective monthly operation of a reservoir for one year. Data of reservoir 1 in Seifollahi-Aghmiuni et al. (2015) is used here (Fig. 7a). Two operation objectives are considered for this reservoir with the minimum (Smin) and maximum (Smax) storage capacities of 400 × 10⁶ and 3000 × 10⁶ m³, respectively in which 2% of the stored water is seepage from the lake in each time interval. These objectives include generating hydropower energy in a powerhouse with 650 × 10⁶ watt installation capacity (Power Plant Capacity-PPC), 96% efficiency and 35% plant factor (solid arrow in Fig. 7a) and supplying one urban site (round dot arrow in Fig. 7a) through release from two separate outlets in different elevations for each objective. About 9% of delivered water to the urban site and all of the delivered water to the powerhouse are considered as return flows (long dash arrows in Fig. 7a). General information and water outlets’ characteristics for this problem are presented in Table 2. OFs for optimization are considered as below:in which, F_Power and F_Demand = OFs of hydropower generation and urban site supplement, respectively; PT_t = generated power in the powerhouse in each time interval t (10⁶ watt); Rw_{j, t} = volume of released water from outlet j in time interval t for supplying the urban site (10⁶ m³); De_t = volume of urban demand in time interval t (10⁶ m³); t and j = variables which show the number of considered time interval and water outlet, respectively. These two OFs are solved by CEA for 400 iterations and 252 initial solutions and the final Pareto is shown in Fig. 7b. The obtained Pareto has logical shape in the objective space and CEA could achieve a correct form of the final Pareto for optimizing two OFs in a water management problem. The average Euclidean distance of the Pareto in Fig. 7b from the origin is equal to 0.819 considering the number of existing points on this Pareto (548 NDSs).

Each NDS on the final Pareto includes a series of optimum values for decision variables. Thus, the range of values for decision variables of the reservoir operation problem is also shown in Fig. 7. In this problem, the volume of release from the reservoir for generating hydropower and supplying the urban site as the first and second operation priorities respectively, is considered as decision variable. Figure 7c shows that generated power in the powerhouse is changing with a wide range and its average is usually near to its lower bound. It could be because the level of the stored water is below the elevation of at least one of the related outlets to the powerhouse (Fig. 7d) due to the less volume of inflow to the reservoir and it makes releasing water from that outlet impossible. Thus, the real capacity of water discharge from the reservoir for generating hydropower decreases and the powerhouse cannot generate electricity with its installation capacity. Based on Fig. 7e, the average of release for supplying the urban site is near to the urban demand except in hot and dry seasons. Thus, the reservoir has better performance in supplying the urban site compared to generating energy. Water storage in the reservoir also changes in its allowable range (Fig. 7f).

The share of different selection and generation operators in CEA for optimizing F_Power and F_Demand in the best run (run 1) is presented in Fig. 8. Table 3 shows statistics of different runs of CEA. It should be mentioned that only some types of crossover operator (5 types of one-point cut, 5 types of two-point cut and 3 types of full crossover) are randomly activated for solving this problem. According to Fig. 8, Boltzmann and roulette wheel operators have the most share in optimizing F_Power and F_Demand, respectively. Also, for optimizing F_Power, one of the full crossover (type 22nd) and type 2 of mutation operators, and for optimizing F_Demand one of the two-point cut crossover (type 18th) and type 5 of mutation operators have the best performance.

In this research a comprehensive evolutionary algorithm (CEA) was presented for the first time which can optimize SOPs and MOPs applying a unique structure. Many parameters of this algorithm did not need sensitivity analysis and their suitable values were implicitly determined based on the problem characteristics during the optimization by CEA. This was one of the major capabilities of CEA compared with other EOAs. General structure of CEA was developed in a multi colony form and different OFs were optimized in separate colonies by this algorithm, simultaneously. Also, CEA could solve SOPs in a single colony form. Thus, CEA could be used for solving any type of optimization problem without any need of recoding while other EOAs require some changes in their coding to solve different problems.

In this research, performance of CEA was assessed compared to NSGA-II in solving several mathematical problems. The extension and density of Pareto of CEA in all problems was more than the obtained Pareto from NSGA-II. Also, they were closer to the origin of coordinate than Pareto of NSGA-II. These two factors are important in solving MOPs. Despite that the convergence speed to the final solutions in CEA was less than NSGA-II, obtained results from CEA were more desirable than NSGA-II which shows its capabilities as a new EOA. The less standard deviation of obtained results from CEA in different runs indicates high reliability and accuracy of this algorithm in solving MOPs (the standard deviation of Euclidean distance of final Pareto from the origin was about 0.088, 0.064 and 0.000001 for DEB, Kita and DTLZ2 problems, respectively). Selection and generation operators made different improvements in the results of each problem during the optimization process which shows the necessity of applying various types of these operators in EOAs. Thus, CEA included a great extent of various types for selection and generation operators and could efficiently use them based on their performance in each problem. Also, the performance of CEA was assessed in solving a reservoir operation problem (maximizing reliability of generating hydropower energy and urban supplement) which resulted logical and acceptable performance for these kind of management problems.