Fitness inheritance for noisy evolutionary multi-objective o

The A rti?cial L ife and A daptive R obotics Laboratory

ALAR Technical Report Series

Fitness Inheritance For Noisy Evolutionary Multi-Objective

Optimization

Lam T.Bui,Hussein A.Abbass,Daryl Essam

TR-ALAR-200504008

The Arti?cial Life and Adaptive Robotics Laboratory

School of Information Technology and Electrical Engineering

University of New South Wales

Northcott Drive,Campbell,Canberra,ACT2600

Australia

Tel:+62262688158Fax:+61262688581

Fitness Inheritance For Noisy Evolutionary

Multi-Objective Optimization

Lam T.Bui,Hussein A.Abbass,Daryl Essam

School of ITEE,University of New South Wales@Australian Defence Force Academy

NorthCott Drive,Canberra

ACT,Australia,2600

Email:{l.bui,h.abbass,d.essam}@3bf42e86b9d528ea81c779c7.au

Abstract

This paper compares the performance of anti-noise methods,particularly probabilistic and re-sampling methods, using NSGA2.It then proposes a computationally less expensive approach to counteracting noise using re-sampling and?tness inheritance.Six problems with different dif?culties are used to test the methods.The results indicate that the probabilistic approach has better convergence to the Pareto optimal front,but it looses diversity quickly.

However,methods based on re-sampling are more robust against noise but they are computationally very expensive to use.The proposed?tness inheritance approach is very competitive to re-sampling methods with much lower computational cost.

Categories and Subject Descriptors:B.X.X[Evolutionary Multiobjective Optimization]:

General Terms:Algorithms,Performance.

Keywords:Evolutionary multiobjective optimization,noise,probabilistic model,?tness inheritance.

I.I NTRODUCTION

Evolutionary algorithms(EAs),particulary genetic algorithms(GA),are known to be robust in the presence of noise[1],[5].Population based methods are generally known to be robust in the single objective case against noise since the average performance of the population acts as a?lter for noise.However,in the case of evolutionary multi-objective optimization algorithms(EMOs),the aim is to obtain a Pareto set of non-dominated solutions, which makes it harder to?lter the noise.So far,comparisons of performance in EMO have been undertaken in the presence of many types of problem dif?culties,such as:convexity,non-convexity,or discontinuity.However, not much work has been done in the area of noisy landscapes.In real life black–box optimization problems,the existence of noise during evaluation is inevitable.Sources of noise can vary from noise in the sensors,actuators, or because of the stochasticity pertaining in some problems such as multi–agent simulations.

The research presented in this paper aims to compare a number of approaches to overcome noise during objective evaluation.In particular,we compare two re–sampling techniques and a probabilistic approach proposed by Hughes (2001).We then propose a?tness inheritance technique to reduce the calculation time.NSGA2is used as a standard EMO algorithm.

The paper is divided into six sections.A review of the EMO literature,noise,and performance metrics is given in section II.A description of the methods is given in the third section.Section four presents the speci?cations of the experiments.The results of the experiments are analyzed and discussed in the?fth section then conclusions are drawn in the last section.

II.B ACKGROUND

A.EMOs

Similar to other optimization algorithms,EMOs are used to?nd at least one feasible solution for a particular problem[3].In contrast to single objective optimization,they are associated with con?icting multi–objective functions,de?ning a multi–dimensional?tness landscape.With EMOs,multiple solutions are usually expected after any iteration.As a result,this is expected to ideally lead to a population of ef?cient solutions when the termination

condition is satis?ed.It thus offers decision makers more options from which to choose the best solution according to some preference information.

EMOs have to overcome two major problems[10].The?rst problem is how to get as close as possible to the Pareto optimal front(POF).Each solution of the POF is a Pareto solution,where no other feasible solution in the search space is better than the former when evaluated on all objective functions.The second problem is how to keep diversity among solutions in the obtained set.These two problems become common criteria for most current comparison measures.

To date,many EMOs have been developed.Generally speaking,they can be classi?ed into two broad categories: non–elitism and elitism.With the elitism approach,EMOs employ an external set to store the best solutions in each generation.This set will then be a part of the next generation.With this method,the best individuals in each generation are always preserved,and this helps the algorithm to get as close as possible to the POF.NSGA2[3] and SPEA2[10]are examples of this approach.In contrast,the non elitism approach has no concept of elitism when it selects individuals for reproduction[10].Examples of this approach include VEGA[8]and NSGA[3].

B.Noise

When EMOs are applied to real life problems,noise in the evaluation cannot be avoided.When noise exists, it makes the evolving process slow and affects the solution’s quality.Generally,noise comes from many different sources,such as:data inputting or sampling[7].However,this paper focuses on an important form of noise:noise in the objective function evaluation.The way noise in?uences the?tness value is varied.We use additive noise. This noise can be seen as additional values randomly added to or subtracted from the real?tness value.Since the noisy?tness value is used for selection,it can mislead the algorithm to inferior results;bad solutions might be kept for t …… 此处隐藏：25888字，全部文档内容请下载后查看。喜欢就下载吧 ……