Archive-based Genetic Algorithm For Multi-objective Optimization And Its Convergence Analysis

In this paper a new strategy for solving multi-objective optimizationproblems by genetic algorithm is proposed----Archival-based geneticalgorithm for multi-objective numerical optimization problems. We find it'seffective to search proximate Pareto-optimal front by observing three testproblems. Later we proved its convergence. The multi-objective optimization problems in this paper can be stated as min f (x) = ( f1(x), f2(x),? fq(x))T s.t x = (x1, x2,?, xn)Τ ∈ Rn ai ≤ xi ≤ bi,i =1,2,?,n . Some definitions of genetic algorithm for multi-objective optimizationproblems are given below. Definition 1(dominance) Given two individuals X ,Y in ?population X (t) ,if fi(x) ≤ fi(y),for everyi∈{1,2,?,n}, and fj (x) < fj (y) ,there exists at least a j ∈{1,2,?,n}then we say that X dominates Y ,or Y is dominated by X . ? Definition 2(non-dominated individual)Given a population X (t) , we say ? ?individual X ∈ X (t) is a non-dominated individual in population X (t) ,if there ?does not exist individual Y ∈ X (t) ,such that Y dominate X . Definition 3(Pareto rank)Let the number of individuals who ?dominate Xi in the population X (t) is pi ,then we define the Pareto rank of (t)individual Xi as 1+ pi ,denoted by rank(Xi,t) . And the non-dominated (t)individual is defined as 1. 38? Definition 4( Archive) An archive is an external set A(t) ,separatefrom the process of evolution ,to store the present non-dominated individuals ? ?E(t) and their function values f (E(t)) . That is to say ? ? ? ?A(t) = E(t) ∪ f (E(t)) .Furthermore, we call{A(t)}t∞ =1the sequence of archive. We define individual fitness by Pareto rank. And we divide the roulettewheel correspond to their fitness. Complete arithmetic crossover operatorand hybrid mutation operator (bound mutation and initial mutation) are usedin this paper .All these operators are designed on the basis of the currentgenetic operators. The main idea of improving these operators is to make fulluse of the information provided by multi-objective numerical optimization. ? An archive is an external set A(t) , separate from the process of ?evolution, to store the present non-dominated individuals E(t) and their ? ? ? ?function values f (E(t)) . That is to say A(t) = E(t) ∪ f (E(t)) .Furthermore, we ?call{A(t)}t ∞ =1the sequence of archive. Archive operator is an important strategy in our algorithm .Its ?foundational idea is to store an external set A(t) outside of the process ofevolution. The approach can be stated as the following in detail. (1) Select the non-dominated individuals X ? in current population ?X (t) . (2) Compare X ? with the individuals in the archive: if X ? isdominated by some individual in the archive, then it cannot be stored inthe archive and is discarded; if X ? dominates some individual in the archive, ?then X ? is stored in A(t) ,and those who are dominated by X ? is removed;if X ? has no dominance-relationship with individuals in the archive, then ?X ? is stored in A(t) . Thus, the individuals in the archive maintain theirnon-dominated position in the process of evolution.