×

zbMATH — the first resource for mathematics

Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization. (English) Zbl 1159.90482
Summary: Although recent studies have shown that evolutionary algorithms are effective tools for solving multi-objective optimization problems, their performances are often bottlenecked by the suitability of the evolutionary operators with respect to the optimization problem at hand and their corresponding parametric settings. To adapt the search dynamic of evolutionary operation in multi-objective optimization, this paper proposes an adaptive variation operator that exploits the chromosomal structure of binary representation and synergizes the function of crossover and mutation. The overall search ability is deterministically tuned online to maintain a balance between extensive exploration and local fine-tuning at different stages of the evolutionary search. Also, the coordination between the two variation operators is achieved by means of an adaptive control that ensures an efficient exchange of information between the different chromosomal sub-structures throughout the evolutionary search. Extensive comparative studies with several representative variation operators are performed on different benchmark problems and significant algorithmic performance improvements in terms of proximity, uniformity and diversity are obtained with the incorporation of the proposed adaptive variation operator into the evolutionary multi-objective optimization process.

MSC:
90C29 Multi-objective and goal programming
Software:
SPEA2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbass, H.A., 2002. The self-adaptive Pareto differential evolution algorithm. In: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 1, pp. 831-836.
[2] Bäck, T., 1993. Optimal mutation rates in genetic search. In: Proceedings of the fifth International Conference on Genetic Algorithms, pp. 2-8.
[3] Bäck, T., Evolutionary algorithms in theory and practice, (1996), Oxford University Press New York · Zbl 0877.68060
[4] Bäck, T., Mutation parameters, (), E1.2.1-E1.2.7
[5] Bäck, T., Schütz, M., 1996. Intelligent mutation rate control in canonical genetic algorithms. In: Proceedings of the International Symposium on Methodologies for Intelligent Systems, pp. 158-167.
[6] Bambha, N.K.; Bhattacharyya, S.S.; Teich, J.; Zitzler, E., Systematic integration of parameterized local search in evolutionary algorithms, IEEE transactions on evolutionary computation, 8, 2, 137-155, (2004)
[7] Chen, Q.; Guan, S., Incremental multiple objective genetic algorithms, IEEE transactions on systems, man and cybernetics, part B: cybernetics, 34, 3, 1325-1334, (2004)
[8] Davis, L., 1989. Adapting operator probabilities in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 61-69.
[9] Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), John Wiley & Sons New York · Zbl 0970.90091
[10] Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6, 2, 182-197, (2002)
[11] Farhang-Mehr, A., Azarm, S., 2002. Diversity assessment of Pareto optimal solution sets: An entropy approach. In: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 1, pp. 723-728.
[12] Fogarty, T., 1989. Varying the probability of mutation in the genetic algorithm. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 104-109.
[13] Fonseca, C.M.; Fleming, P.J., Multi-objective optimization and multiple constraint handling with evolutionary algorithms – part I: A unified formulation, IEEE transactions on system, man and cybernetics-part A: system and humans, 28, 1, 26-37, (1998)
[14] Fonseca, C.M.; Fleming, P.J., Multi-objective optimization and multiple constraint handling with evolutionary algorithms-part II: application example, IEEE transactions on systems, man and cybernetics, part A: systems and humans, 28, 38-47, (1998)
[15] Goldberg, D.E., Deb, K., Thierens, D., 1991. Towards a better understand of mixing in genetic algorithms. In: Proceedings of the fourth International Conference on Genetic Algorithms, pp. 190-195.
[16] Hesser, J., Männer, R., 1991. Toward an optimal mutation probability for genetic algorithms. In: Proceedings of the First International Conference on Parallel Problem Solving from Nature (PPSN I), pp. 23-32.
[17] Hinterding, R., Michalewicz, Z., Eiben, A.E., 1997. Adaptation in evolutionary computation: A survey. In: Proceedings of the Fourth IEEE International Conference on Evolutionary Computation, pp. 65-69.
[18] Janikow, C.Z., Michalewicz, Z., 1991. An experimental comparison of binary and floating point representations in genetic algorithms. In: Proceedings of the 4th International Conference on Genetic Algorithms, pp. 151-157.
[19] Knowles, J.D., Corne, D.W., 2002. On metrics for comparing nondominated sets. In: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 1, pp. 723-728.
[20] Kursawe, F., 1990. A variant of evolution strategies for vector optimization. In: Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature, vol. 496, pp. 193-197.
[21] Laumanns, M., Rudolph, G., Schwefel, H.P., Mutation control and convergence in evolutionary multi-objective optimization. In: Proceedings of the seventh International Mendel Conference on Soft Computing, pp. 24-29.
[22] Raidl, G.R.; Gottlieb, J., Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: A case study for the multidimensional knapsack problem, Evolutionary computation, 13, 4, 441-475, (2005)
[23] Rechenberg, R., Evolutionsstrategie: opimierunf technischer syseme nach prinzipien der biologischen evolution, (1973), Frommann-Holzboog Stuttgart
[24] Schaffer, J.D., 1985. Multiple-objective optimization using genetic algorithm. In: Proceedings of the First International Conference on Genetic Algorithms, pp. 93-100.
[25] Schaffer, J.D., Morishima, A. An adaptive crossover distribution mechanism for genetic algorithms. In: Proceedings of the Second International Conference on Genetic Algorithms, pp. 36-40.
[26] Spears, W.M., William, M., 1995. Adapting crossover in evolutionary algorithms. In: Proceedings of the Evolutionary Programming Conference, pp. 367-384.
[27] Srinivas, M.; Patnaik, L.M., Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE transactions on systems, man and cybernetics, 24, 4, 17-26, (1994)
[28] Tan, K.C.; Lee, T.H.; Khor, E.F., Evolutionary algorithm with dynamic population size and local exploration for multi-objective optimization, IEEE transactions on evolutionary computation, 5, 6, 565-588, (2001)
[29] Tan, K.C.; Goh, C.K.; Yang, Y.J.; Lee, T.H., Evolving better population distribution and exploration in evolutionary multi-objective optimization, European journal of operations research, 171, 2, 463-495, (2006) · Zbl 1090.90110
[30] Vekaria, K., Clack, C., 1998. Selective crossover in genetic algorithms: An empirical study. In: Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature (PPSN V), pp. 438-447.
[31] Veldhuizen, D.A.V., 1999. Multi-objective evolutionary algorithms: Classifications, analyses, and new innovations. PhD Thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering. Air Force Institute of Technology, Wright-Patterson AFB, OH.
[32] White, T., Oppacher, F., 1994. Adaptive crossover using automata. In: Proceedings of the Third Conference on Parallel Problem Solving from Nature (PPSN III), pp. 229-238.
[33] Wolpert, D.H.; Macready, W.G., No free lunch theorems for optimization, IEEE transactions on evolutionary computation, 1, 1, 67-82, (1997)
[34] Yang, S., 2002. Adaptive crossover in genetic algorithms using statistics mechanism. In: Proceedings of the Eighth International Conference on Artificial Life, pp. 182-185.
[35] Zitzler, E.; Thiele, L., Multi-objective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE transactions on evolutionary computation, 3, 4, 257-271, (1999)
[36] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multi-objective evolutionary algorithms: empirical results, Evolutionary computation, 8, 2, 173-195, (2000)
[37] Zitzler, E., Laumanns, M., Thiele, L., 2001. SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Switzerland.
[38] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C.M.; Fonseca, V.G., Performance assessment of multi-objective optimizers: an analysis and review, IEEE transactions on evolutionary computation, 7, 2, 117-132, (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.