Abstract: Existing test problems for multi-objective optimization are mainly criticized for high computational complexity. In this study, we introduce a new non- dominated sorting algorithm based on Pareto optimal solutions which alleviates the problem of high computational complexity in NSGA-II. We use the Arena Principle in NSGA-II to retain the non-dominated solutions found during the evolutionary process. The main goal of this work is to keep the fast convergence exhibited by Arena Principle in global optimization when extending this heuristic to multi-objective optimization. The algorithm’s computational complexity is O(rmN). We adopt two standard test functions and simulation results show that the Arena Principle is able to find more useful and better spread of solutions.
INTRODUCTION
Over the past decade, a number of Pareto-based techniques have been suggested, such as MOGA (Fonseca and Fleming, 1993), NPGA (Horn et al., 1994) and NSGA (Srinivas and Deb, 1995), which demonstrated the capability to find multi-objective Pareto optimized solutions in a single run. With the new insights into the performance of evolutionary multi-objective optimization, many new elitist multi-objective evolutionary algorithms were proposed, such as SPEA (Zitzler and Thiele, 1998, 1999) and PAES (Knowles and Corne, 1999), NSGA-II (Deb et al., 2002) and PESA (Corne et al., 2000), which were being found to be useful in solving multi-objective optimization problems. However, lots of several types of MOEAs (Zitzler et al., 2000), developed for problems with a number of objectives, have difficulties to find a good pareto set approximation for higher dimensions, because of their high computational complexity, non-elitism approach and specifying a sharing parameter (Deb et al., 2002).
In this study, we address all of these issues and discuss the adequacy of these problems as real test problems. Based on these test solutions, we find that arena principle is able to get much better spread of solutions than NSGA-II (Deb et al., 2002). The results of this study are important for various reasons and should encourage readers to find more applications using Arena Principle.
ARENA PRINCIPLE EVOLUTIONARY ALGORITHM
Arena Principle (Zheng et al., 2007) is a pareto-based approaches algorithm. The population P is randomly initialized, where Nds denotes the set of non-dominated individuals of parent solutions. In order to sort P to level of non-dominated, each solution must be compared with every other individual in the population P to find if it is dominated. With the comparison going, the non-dominated solution is selected into Nds and removed from population P. With the implementation of this process, all the non-dominated individuals have been selected. When P is empty, the above procedure repeated.
The Arena Principle is outlined below:
nonsort_base_on_arena(RKt)
| (1) |
| (2) |
| (3) |
| • | If x™y, then Q = Q-y, go to Eq. 3 |
| • | If y™x, then x = y, Q = Q-y, RK = RK ∪ R, R =φ, go to Eq. 3 |
| • | Else R = R∪{y}, Q-Q-y, go to Eq. 3 |
| (4) |
| (5) |
| • | If |Q|>1, then go to Eq. 1 |
| • | Else Nds = Nds∪Q |
Every x in current population Q should be the host once and compare with every other individual in the population Q. On the assumption that S is the number of the non-dominated objectives in population Q (the size of Q is N), it needs to compare K times. Each comparison produces a non-dominated individual. After (N-1) comparisons, k1 dominated individuals removed from Q. When It comes to the next comparison, it should compare (N-k1-1) times and removes k2 dominated individuals. To continue this comparison, when we get K-th non-dominated solution, it should compare (N-k1-k2-…-kK-1-1) times. In all, it should remove (k1+k2+…+kK-1) =N-s individuals. The probability of seeking every non-dominated individual is the same. That is (N-S)/K non-dominated solutions selected at every comparison.
The computational complexity is:
= (KN- N-K)/2
= O(KN)
For multi-objective evolutionary algorithms, the average complexity is (mKN) (m is number of objectives, generally m<N). When the number of non-dominated solutions is small, the comparison times are relatively small and so the computational complexity. The following test result shows that non-dominated solutions’ proportion is generally about 70%.
MULTI-OBJECTIVE PARETO OPTIMAL SOLUTIONS BASED ON ARENA PRINCIPLE
Initialize the population P0 randomly, sort P0 based on Arena Principle to get the non-dominated set and then combine it with the offspring population which is generated by Binary tournament selection, recombination and mutation operators. In order to get Pareto optimal solutions using Arena Principle, we divide the population into two parts by the dominated and non-dominated relationship. After every calculation, we put the new non-dominated set into next calculation. In this study, compare to NSGA-II, we suggest two important differences: the way constructing non-dominated set, the crowding-distance computation. For each individual x, it just compares with other individuals to determine whether x is non-dominated. With the procedure going, dominated individuals removed from P0, non-dominated individuals are put into temporary set R, if the other individual y (yεP0) that y™x, then replace x and continue this comparison, while yåx where, xεr. After the completion of a comparison, the non-dominated individuals included in next offspring population Q0, It is not necessary to define the evolutionary generations in Arena Principle.
Multi-objective pareto optimal solutions based on arena principle:
| • | Rkt = Pt∪Qt |
| • | F = nonsort_base_on_arena(RKt) |
| • | if |Fi|<Num |
Comparison of the test results: We compare Arena Principle with NSGA-II on two test problems (Deb et al., 2006):
where, -4≤x1,x2,x3≤4B
where, -5≤x1,x2,x3≤5B
In the absence of certain restrictions on the evolutionary generation, we add a variable Num to determine whether the procedure continues. When the number of non-dominated individuals greater than Num, the procedure stops. During the experiment, the number of non-dominated individuals affected by coded bytes and the size of population. The greater the individual’s coded bytes, the size of the population, the greater the number of non-dominated individuals. Due to the factors of above two, Num should be set up in a reasonable range, if the Num is set smaller, we may not get the true Pareto optimal set, however, if it is set too large, it will waste plenty of computing time and affect the operation efficiency.
| Fig. 1: | The different proportion test results Based on Arena Principe:
(a) the result of non-dominated proportion of 40% for F1 using
Arena Principle, (b) the result of non-dominated proportion of 50% for F1
using Arena Principle, (c) the result of non-dominated proportion of 60%
for F1 using Arena Principle, (d) the result of non-dominated
proportion of 70% for F1 using Arena Principle, (e) the result
of non-dominated proportion of 80% for F1 using Arena Principle
and (f) the result of non-dominated proportion of 90% for F1
using Arena Principle |
| Table 1: | Comparison of test conditions |
Test 1: The proportion of non-dominated individuals: In this test, we use the test function F1, individual encoding of binary-coded, 8 bytes and the size of population is 100. The non-dominated proportion in the population is different in this test in Table 1. The test results during this period have been shown in Fig. 1a-f.
Figures 1a-f are tested based on the above conditions and different non-dominated proportions. All these obviously show that with the number of non-dominated individuals increasing, the non-dominated individuals tend to the true Pareto optimal front. In a relatively small non-dominated proportion, we get the poor Pareto optimal fronts, however, with the proportion increases; the obtained results are closer to the true Pareto font.
Beside, in order to get Num non-dominated individuals, it should check and compare every individual several times in a certain population. The greater the Num proportion in the population, the larger the comparison times.
Test 2: The comparison results with NSGA-II: For the test problems in this study, we use the parameters as below: individual encoding of binary-coded, uniform crossover, non-uniform mutation, the Num is 80, for NSGA-II, the evolutionary generation is 50.
In theory, the larger of population size, the better the results we obtained. In order to have a better understanding of how these algorithms are able to spread solutions over the non-dominated Pareto Front, we present the entire non-dominated front generated by Arena Principle and NSGA-II in the above two test problems. In the first test we use the data in Table 1, especially, the size of Arena Principle is 100; the NSGA-II is 200.
Figure 2 and 3 show that Arena Principle used in Pareto-based optimal solutions is able to find a much better distributions than NSGA-II on F1 with a much smaller population size.
Figure 4 and 5 show the non-dominated solutions obtained using Arena Principle and NSGA-II for F2.In F2, converging to the global Pareto optimal front is difficult. In this test, we use the parameters in the last row of Table 1. In Fig. 4 and 5, we also see a better distribution obtained using Arena Principle in NSGA-II than simple NSGA-II.
In all tests cases, we constitute a significant improvement over the simple NSGA-II as it distributes its population along the obtained front better than simple NSGA-II. It is very instructive, however, to see how the performance develops over time. For many problems, using Arena Principle in non-dominated sorting appears to be converging quicker which is probably due to its lower computational complexity. All the data show that, with the similar number of function evaluations, Arena Principle obtains larger range of solutions and more uniform.
| Fig. 2: | Non-dominated solutions obtained for F1 using Arena Principle |
| Fig. 3: | Non-dominated solutions obtained for F1 using NSGA-II |
| Fig. 4: | Non-dominated solutions for F2 obtained using Arena Principle |
| Fig. 5: | Non-dominated solutions for F2 obtained using NSGA-II |
CONCLUSIONS
We have proposed a computational fast multi-objective evolutionary algorithm based on non-dominated sorting approach. The process of construction of non-dominated set directly affects the running time and efficiency of the algorithm. In this study, we construct the non-dominated set based on Arena Principle and verify its correctness through the tests. We can see, it reduces the number of comparisons effectively, improves the computational efficiency and maintains the diversity of the population well.