Diversity Based on Entropy: A Novel Evaluation Criterion in Multi-objective Optimization Algorithm

Full Text (PDF, 1045KB), PP.113-124

Views: 0 Downloads: 0

Author(s)

Wang LinLin 1,* Chen Yunfang 2

1. College of Overseas Education, Nanjing University of Posts and Telecommunication, China, 210046

2. College of Computer, Nanjing University of Posts and Telecommunication, China, 210046

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2012.10.12

Received: 5 Nov. 2011 / Revised: 20 Mar. 2012 / Accepted: 12 Jun. 2012 / Published: 8 Sep. 2012

Index Terms

Diversity Performance, Entropy Metric, Multi-objective Evolutionary Algorithm, Multi-objective Immune Algorithm

Abstract

Quality assessment of Multi-objective Optimization algorithms has been a major concern in the scientific field during the last decades. The entropy metric is introduced and highlighted in computing the diversity of Multi-objective Optimization Algorithms. In this paper, the definition of the entropy metric and the approach of diversity measurement based on entropy are presented. This measurement is adopted to not only Multi-objective Evolutionary Algorithm but also Multi-objective Immune Algorithm. Besides, the key techniques of entropy metric, such as the appropriate principle of grid method, the reasonable parameter selection and the simplification of density function, are discussed and analyzed. Moreover, experimental results prove the validity and efficiency of the entropy metric. The computational effort of entropy increases at a linear rate with the number of points in the solution set, which is indeed superior to other quality indicators. Compared with Generational Distance, it is proved that the entropy metric have the capability of describing the diversity performance on a quantitative basis. Therefore, the entropy criterion can serve as a high-efficient diversity criterion of Multi-objective optimization algorithms.

Cite This Paper

Wang LinLin, Chen Yunfang, "Diversity Based on Entropy: A Novel Evaluation Criterion in Multi-objective Optimization Algorithm", International Journal of Intelligent Systems and Applications(IJISA), vol.4, no.10, pp.113-124, 2012. DOI:10.5815/ijisa.2012.10.12

Reference

[1]M. Laumanns, L. Thiele, K. Deb, and E. Zitzler, Combining convergence and diversity in evolutionary multi-objective optimization, Evolutionary Computing, vol. 10, no. 3, pp.263 - 282, 2002.

[2]Ali Farhang-Mehr, Shapour Azarm, On the entropy of multi-objective design optimization solution set. Proceedings of DETC’02 ASME 2002 Design Engineering Technical Conferences and Computer and Information in Engineering Conference.

[3]K.C. Tan, C.K. Goh, A.A. Mamun, E.Z. Ei, An evolutionary artificial immune system for multi-objective optimization. European Journal of Operational Research 187, 2008, 371–392.

[4]Ali Farhang-Mehr, Shapour Azarm, Diversity Assessment of Pareto Optimal Solution Sets: An Entropy Approach. :Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on 

[5]Zielinski, K., Laur, R., Variants of Differential Evolution for Multi-Objective Optimization, Computational Intelligence in Multicriteria Decision Making, IEEE Symposium on, p91 - 98, Volume: Issue:, 1-5 April 2007

[6]K. Deb, Multi-objective optimization, Springer, Berlin (2005), [chapter 10, p. 273–316]

[7]J.D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms. Proc. 1st ICGA(1985), pp. 93–100.

[8]Tadahiko Murata, Hisao Ishibuchi, Hideo Tanaka, 1996. Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering.Volume 30, Issue 4, September 1996, Pages 957-968

[9]K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, et al., M. Schoenauer, A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA-II, Parallel Problem Solving from Nature, pp.849-858, 2000. Springer.

[10]P. Baraldi, N. Pedroni, E. Zio. Application of a niched Pareto genetic algorithm for selecting features for nuclear transients classification. International Journal of Intelligent Systems 24:2, 118-151

[11]J. D. Knowles and D. W. Corne, Approximating the nondominated front using the Pareto archived evolution strategy, Evolution. Computation. vol. 8, pp.149 - 172 , 2000.

[12]David W. Corne , Nick R. Jerram , Joshua D. Knowles , Martin J. Oates , Martin J,2001. PESA-II: Region-based Selection in Evolutionary Multiobjective Optimization. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2001)

[13]Coello Coello, C.A., 2006. Evolutionary multi-objective optimization: a historical view of the field. Computational Intelligence Magazine, IEEE. p28 - 36

[14]V. Cutello , G. Narzisi and G. Nicosia A multi-objective evolutionary approach to the protein structure prediction problem, J. Royal So. Interface, vol. 3, p.139, 2006.

[15]Fabio Freschi and Maurizio Repetto. Multiobjective Optimization by a Modified Artificial Immune System Algorithm. Computer Science, 2005, Volume 3627/2005, 248-261

[16]Licheng Jiao, Maoguo Gong, Ronghua Shang, Haifeng Du and Bin Lu,2005. Clonal Selection with Immune Dominance and Anergy Based Multiobjective Optimization. Computer Science, 2005, Volume 3410/2005,474-48

[17]E Zitzler, M. laumanns and L. Thiele, SPEAII: Improving Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Networks Laboratory, Swiss Federation of Technology, Zurich, 2001.

[18]X. Li, J. Branke, and M. Kirley. Performance Measures and Particle Swarm Methods for Dynamic Multiobjective Optimization Problems. 2007 Genetic and Evolutionary Computation Conference, D. Thierens, Ed., vol. 1. London, UK: ACM Press, July 2007, p. 90

[19]J. Martin Bland, Douglas G. Altman, 2003.Statistical Methods for Assessing Agreement between Two Method of Clinical of Measurement. The lancet, 1986. Published by Elsevier Science Ltd.

[20]Sayin, S. Measuring the Quality of Discrete Representations of Efficient Sets in Multiple Objective Mathematical Programming. Mathematical Programming, 87, pp. 543-560.