J. Cent. South Univ. Technol. (2010) 17: 123-128

DOI: 10.1007/s11771-010-0020-8                                                                                                               

Fuzzy adaptive genetic algorithm based on auto-regulating fuzzy rules

YU Shou-yi(喻寿益), KUANG Su-qiong(邝溯琼)

School of Information Science and Engineering, Central South University, Changsha 410083, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2010

Abstract: There are defects such as the low convergence rate and premature phenomenon on the performance of simple genetic algorithms (SGA) as the values of crossover probability (P_c) and mutation probability (P_m) are fixed. To solve the problems, the fuzzy control method and the genetic algorithms were systematically integrated to create a kind of improved fuzzy adaptive genetic algorithm (FAGA) based on the auto-regulating fuzzy rules (ARFR-FAGA). By using the fuzzy control method, the values of P_c and P_m were adjusted according to the evolutional process, and the fuzzy rules were optimized by another genetic algorithm. Experimental results in solving the function optimization problems demonstrate that the convergence rate and solution quality of ARFR-FAGA exceed those of SGA, AGA and fuzzy adaptive genetic algorithm based on expertise (EFAGA) obviously in the global search.

Key words: adaptive genetic algorithm; fuzzy rules; auto-regulating; crossover probability adjustment

1 Introduction

The performance of genetic algorithm (GA), inspired by the concepts of natural selection and evolution, is obviously enslaved to the crossover probability P_c and mutation probability P_m [1-3]. For the values of P_c and P_m are invariable, there are problems as the low convergence rate and premature phenomenon in simple genetic algorithm (SGA) [4-6]. With view to solve these problems, adaptive genetic algorithm (AGA) was presented by SRINVIVAS and PATNIK [7], in which the values of P_c and P_m could be changed according to the fitness of the overall population. Though AGA has been proven to be able to obtain better performance than SGA for certain problems, it is inappropriate to adjust the control parameters P_c and P_m just according to the fixed rule. The rule to adjust P_c and P_m must be varied with optimization questions so as to find the optimal solution faster and more precisely. A great deal of studies show that there is much fuzzy information in tuning the values of P_c and P_m, thereby the fuzzy logic theory is used to adjust them [8-10].

So far, a lot of investigations on utilizing the fuzzy logic theory in adjusting GAs’ parameters have been carried out, and one of the most familiar methods is the fuzzy genetic algorithm (FGA) based on the expert knowledge. Though these modified genetic algorithms are helpful to avoid premature convergence and improve the performance of GA to some degree [11], there are still some deficiencies due to the fixed rule bases and expensive experiment cost of forming the fuzzy rules. To obtain more satisfying optimization results, how to modify the fuzzy rules along with the change of the inputs in order to control GAs’ parameters more efficiently is worthy to lucubrate. In this work, the fuzzy control method was integrated with the genetic algorithms to create a kind of fuzzy adaptive genetic algorithm based on the self-learning fuzzy rules (ARFR- FAGA). In ARFR-FAGA, the fuzzy control method was used to adjust P_c and P_m of GA and the fuzzy rules were optimized by another GA. It was a nested genetic algorithm which could adjust P_c and P_m with the evolutional process so as to improve the performance of GA further.

2 Principle of ARFR-FAGA

The fuzzy control method was applied in ARFR- FAGA to adjust P_c and P_m, and the fuzzy rules of the fuzzy controller were optimized with another genetic algorithm according to the evolutional process for different optimization problems.

As shown in Fig.1, ARFR-FAGA includes two genetic algorithms, one is the main genetic algorithm GA1, whose parameters are adjusted by fuzzy controller, the other is the genetic algorithm GA2 used to optimize the fuzzy rules. The fuzzy controller’s inputs are GA1’s performance measures, and its outputs are returned as new values of P_c and P_m. The fuzzy rule base optimized by GA2 is a combination of expert knowledge with on-line data information so as to realize dynamic parameter control of genetic algorithms.

Fig.1 Architecture of ARFR-FAGA

3 Optimization of fuzzy rules

The adaptability of ARFR-FAGA was derived from the updating fuzzy rules based on GA2. Generally, for a given problem, the key parts of the optimizing process were as follows:

(1) The coding method of fuzzy rules;

(2) Choosing an evaluation function;

(3) The steps of optimizing fuzzy rules.

3.1 Coding method of fuzzy rules

The two rule bases were constructed respectively to control P_c and P_m by decimal coding. Suppose there were two inputs and two outputs in the fuzzy controller, then the fuzzy rules can be coded as follows.

(1) Divide each fuzzy variables into seven linguistic values: NB(very_small), NM(small), NS(smaller), Z(medium), PS(larger), PM(large), PB(very_large), and the counterparts of the seven linguistic values in turn were 0, 1, 2, 3, 4, 5, and 6.

(2) Any rule base of P_c or P_m can be expressed in a numerical form, as shown in Table 1.

Table 1 Numerical rule base (P_c or P_m)

(3) Stretch Table 1 in accordance with the order from the top down and from left to right, and the united coding of the fuzzy rules shown in Table 1 was: 6655443, 6554432, 5544322, 5443221, 4432211, 4322110, 3221100, 6655443, 6554432, 5544322, 5443221, 4432211, 4322110, 3221100, where the anterior seven character strings were the fuzzy rules of P_c, and the after seven character strings were the fuzzy rules of P_m. The overall string represented an individual which included (7×7)×2=98 items of fuzzy rules.

3.2 Choosing evaluation function

It is difficult to express the relationship between the constantly changing fitness and values of P_c or P_m with a function; this multiplies the difficulty of choosing an evaluation function to determine the optimal rules [12- 13]. Fortunately, the GA1’s fitness function could be a means to evaluate the optimal rules indirectly. Its principle is that the suitable parameters P_c and P_m will result in the optimization result of GA1 and the optimal fuzzy rules should reason out these suitable parameters. With the principle, the individual of GA2 can be selected to obtain the maximum fitness of GA1 as the best individual, which represents the optimal fuzzy rules. More detailed discussion of optimizing fuzzy rules is as follows.

3.3 Steps of optimizing fuzzy rules

The steps of optimizing fuzzy rules are shown in Fig.2.

Fig.2 Steps of optimizing fuzzy rules

3.3.1 Initialization

Code according to section 3.1 and generate an initial population of the fuzzy rules with size R, then set the initial crossover probability P_c and mutation probability P_m of GA1, the maximum generation number and the fixed crossover probability P_c2 and mutation probability P_m2 of GA2.

3.3.2 Fuzzy reasoning and genetic operations of GA1

Select each individual in turn from the population of the fuzzy rules to seek for the relevant values of P_c and P_m through the fuzzy reasoning, and then apply each value of P_c and P_m to genetic operations of GA1. When the population size of the fuzzy rules was R, there would be R new population and a maximum fitness of the evaluation function for GA1 was obtained correspondingly. So the individual reasoning out the maximum fitness was the best individual of the current population of the fuzzy rules.

3.3.3 Reservation of optimal rules

If the current maximum fitness (f_max) was bigger than the maximum fitness last time (f_lastmax), then the current optimal rules were reserved, and let f_max assign f_lastmax, otherwise the optimal rules at last time still were reserved as the best individual. The best individual reserved in each generation was regarded as one individual of the offspring without the genetic operations.

3.3.4 Genetic operations of GA2

The other individuals except the best individual obtained in section 3.3.3 were used into genetic operations of GA2, which included fitness proportional selection, one-point crossover with the fixed crossover probability and simple mutation with the fixed mutation probability.

3.3.5 Termination condition

If the generation number was less than the maximum generation number pre-established, then the above steps were repeated. Otherwise, exit the iterative and reserve the optimal rules found in the overall evolutional process.

4 Numerical example

4.1 Test functions

The efficiency and performance of the proposed algorithm was studied via simulation. More than ten representative functions were investigated in simulation experiments. Because of space limitations, the results of six representative functions such as the multiple hump function, Schaffer function-6 and Rosenbrock function were listed as follows.

(1) Multiple hump function

F₁(x)=x+10sin(5x)+7cos(4x), 0≤x≤9             (1)

It is apt to get into local convergence for there are multiple humps in each specific range. In the range of [0, 9] its theoretical maximum is 24.855 4. A diagram of the function characteristic is shown in Fig.3.

Fig.3 Characteristic of F₁(x)

(2) Schaffer function-6 [14]

-10≤x₁, x₂≤10                    (2)

It is hard to optimize for its highest peak is inconspicuous and located in a small area. Its maximum is 1 within [-10, 10] theoretically. But there are two local maximum values around the optimal solution, and all of them are very close to 1. This function is so deceptive that the ordinary algorithm is impossible to find its maximum value. The geometric characteristic is shown in Fig.4.

Fig.4 Characteristic of F₂(x₁, x₂)

(3) Rosenbrock function [15]

-2.048≤x₁, x₂≤2.048                  (3)

Rosenbrock function is a continuous and nonlinear function though there is only one peak. It is morbid with the optimum located in a steep parabolic valley with a flat bottom where  so it is easy to find the local maximum. Its minimum is 0 in the range of [-2.048, 2.048]. The geometric characteristic is shown in Fig.5.

Fig.5 Characteristic of f₃(x₁, x₂)

To transform Rosenbrock function into a maximization problem, the test function was considered as

 -2.048≤x₁, x₂≤2.048  (4)

Then the global optimal solution of F₃(x₁, x₂) is 1 when f₃(x₁, x₂) locates in the minimum.

(4) Spherical function [15]

 -40≤x_i≤60                    (5)

Spherical function is the typical representative of continuous and unimodal functions. There is a global minimum value of 0 at (0, …, 0). The geometric characteristic is shown in Fig.6.

Fig.6 Characteristic of f₄(x₁, x₂)

To transform Spherical function into a maximization problem, the test function was considered as

 -40≤x_i≤60                (6)

Then the global optimal solution of F₄(x₁, x₂) is 1 when f₄(x₁, x₂) locates in the minimum.

(5) Schwefel function [15]

 -512≤x_i≤511         (7)

There are many local peaks which are far from the global minimum of this function, so it is easy to find local optimal in evolution process. There is a global minimum value of -4 189.828 9 at (420.968 7, …,  420.968 7). The geometric characteristic is shown in Fig.7.

Fig.7 Characteristic of f₅(x)

To transform Schwefel function into a maximization problem, the test function was considered as

F₅(x)=-f₅(x), -512≤x_i≤511                    (8)

Then the global optimal solution of F₅(x) is 4 189.828 9 when f₅(x) locates in the minimum.

(6) Goldstein-Price function [16]

  -2≤x₁, x₂≤2                (9)

There is only one global minimum value and three local peaks in the range of [-2, 2], and the global minimum value is f₆(0, -1)=3. The geometric charac- teristic is shown in Fig.8.

Fig.8 Characteristic of f₆(x₁, x₂)

To transform Goldstein-Price function into a maximization problem, the test function was considered as

 -2≤x₁, x₂≤2        (10)

Then the global optimal solution of F₆(x₁, x₂) is 0.25 when f₆(x₁, x₂) locates in the minimum.

4.2 Simulation results

The ARFR-FAGA was compared with SGA, AGA  and EFAGA in solving the function optimization problems when the other conditions of each algorithm were the same expect the values of P_c and P_m. The experiments were carried out using the following parameters: the overall population size was 80 individuals, the maximum generation number was 150, and the genetic operators were fitness proportional selection, one-point crossover and simple mutation. The values of P_c and P_m were fixed in SGA: P_c=0.6, P_m=0.001 and variable in AGA, EFAGA and ARFR-FAGA although their adjusting methods were different in the two algorithms. In AGA, P_c and P_m were determined by the following equations [7]:

           (11)

       (12)

where f_max refers to the maximum fitness of each generation, f_avg refers to the average fitness of each generation, f_c refers to the larger fitness of the two crossover individuals, and f_m refers to the fitness of the mutation individual. In EFAGA and ARFR-FAGA, P_c and P_m were adjusted by the fuzzy controller, but the determinations of the fuzzy rules of the two algorithms are different. In EFAGA, the fuzzy rules were pre- established according to the expertise, and the fuzzy rules of ARFA-FAGA were changed in terms of the evolutional process.

All the algorithms were executed 100 times and obtained the average values, as shown in Table 2.

Table 2 Simulation results of different functions

The results in Table 2 show that the ARFR- FAGA is more effective than SGA, AGA and EFAGA for any optimization problem. Compared with SGA, AGA and EFAGA, the average convergent generations are obviously decreased and the average values of the best are closer to the theoretical values, that is to say, the ARFR-FAGA is better to avoid premature convergence and obtain high-performance of GA. Though AGA is helpful to overcome the drawbacks of SGA for certain optimization problems such as the Schaffer function, it is possibly not suitable for optimization problems because its tuning rules of P_c and P_m are invariable, such as Rosenbrock function and Schwefel function. AGA and EFAGA can hardly find the global optimal for the problems that are easy to fall into the local optimal for their invariable tuning rules cannot fit for all the problems. As illustration, the performance of AGA is only slightly improved compared with SGA on the optimization of F₁(x), but the ARFR-FAGA can solve any complicated problems preferably due to its adaptability of parameter tuning. All experimental results demonstrate that the performance of the ARFR-FAGA is better than those of SGA, AGA and EFAGA in the function optimization problems.

5 Conclusions

(1) A kind of fuzzy adaptive genetic algorithm ARFR-FAGA is introduced based on the self-learning fuzzy rules, which systematically integrates fuzzy control method with genetic algorithms. Fuzzy control method is utilized to adjust GAs’ parameters such as P_c and P_m, and the fuzzy rules are optimized by another genetic algorithm so that the fuzzy rules are appropriate with the change of the fitness.

(2) Experimental results demonstrate that the ARFR-FAGA can not only search faster and prevent the premature convergence more effectively than SGA and AGA in solving the function optimization problems, but also be suitable for optimization problems. In other words, ARFR-FAGA has stronger adaptability to obtain and maintain high-performance.

References

[1] CHEN Guo-liang, WANG Xu-fa, ZHUANG Zhen-quan. Genetic algorithms and applications [M]. Beijing: Posts and Telecom Press, 1999. (in Chinese)

[2] FANG Lei, ZHANG Huan-chun, JIANG Ya-zhi. A new fuzzy adaptive genetic algorithm [J]. Journal of Electronic Science and Technology of China, 2005, 3(1): 57-59, 71.

[3] LI Shu-gang, WU Zhi-ming, PANG Xiao-hong. A fuzzy rule based genetic algorithm and its application in FMS [J]. High Technology Letters, 2005, 11(1): 56-60.

[4] VASCONCELOS J A, RAMREZ J A, TAKAHASHI R H C, SAIDANHA R R. Improvements in genetic algorithms [J]. IEEE Transactions on Magnetics, 2001, 37(5): 3414-3417.

[5] LUO Jian-xu, SHAO Hui-he. A neurofuzzy system based on rough set theory and genetic algorithm [J]. Journal of Harbin Institute of Technology: New Series, 2005, 12(3): 278-282.

[6] WANG Xin, YANG Chun-hua, QIN Bin, GUI Wei-hua. Parameter selection of support vector regression based on hybrid optimization algorithm and its application [J]. Journal of Control Theory and Applications, 2005, 3(4): 371-376.

[7] SRINVIVAS M, PATNIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms [J]. IEEE Transactions on Systems, Man and Cybernetics, 1994, 24(4): 656-667.

[8] XI Ping-yuan, WANG Bing, SHENTU Liu-fang, HU Heng-yin. Fuzzy optimization of an elevator mechanism applying the genetic algorithm and neural networks [J]. International Journal of Plant Engineering and Management, 2005, 10(10): 236-240.

[9] TONG Xiao-hua, WU Song-chun, WU Su-qing, LIU Da-jie. A novel vehicle navigation map matching algorithm based on fuzzy logic and its application [J]. Journal of Central South University of Technology, 2005, 12(2): 214-219.

[10] LIU Bo, WANG Yong, WANG Hong-jian. Using genetic algorithm based fuzzy adaptive resonance theory for clustering analysis [J]. Journal of Harbin Engineering University, 2006, 27(S): 547-551.

[11] PARMOD K, CHANDNA V K, THOMAS M S. Fuzzy-genetic algorithm for pre-processing data at the RTU [J]. IEEE Transactions on Power Systems, 2004, 19(2): 718-723.

[12] WANG Ke-jun. A new fuzzy genetic algorithm based on population diversity [C]// Proceedings of 2001 IEEE International Symposium on Computational Intelligence in Robotics and Automation. Banff, Alberta, Canada, 2001: 108-112.

[13] LI Fa-chao, SU Lian-qing, RAN Hai-chao. The fuzzy genetic algorithm based on rule [C]// Proceeding of Fourth International Conference on Machine Learning and Cybernetics. Guangzhou, 2005: 2454-2459.

[14] LIU Xi-chun, YU Shou-yi. A genetic algorithm with fast local adjustment [J]. Chinese Journal of Computers, 2006, 29(1): 100-105. (in Chinese)

[15] GUO Guan-qi. Analysis and suppressing methods of genetic drift in evolutionary computation [D]. Changsha: School of Information Science and Engineering, Central South University, 2003: 93-95. (in Chinese)

[16] LI Ming. The study on improved genetic algorithm and its application in optimization questions [D]. Changchun: School of Mathematics, Jilin University, 2004: 17. (in Chinese)

Foundation item: Project(60574030) supported by the National Natural Science Foundation of China; Key Project(60634020) supported by the National Natural Science Foundation of China

Received date: 2009-03-17; Accepted date: 2009-05-26

Corresponding author: YU Shou-yi, PhD, Professor; Tel: +86-731-88836739; E-mail: s­_yushouyi@sina.com

(Edited by YANG You-ping)