de.lmu.ifi.dbs.elki.algorithm.outlier
Class AggarwalYuEvolutionary.EvolutionarySearch

java.lang.Object
  de.lmu.ifi.dbs.elki.algorithm.outlier.AggarwalYuEvolutionary.EvolutionarySearch

Enclosing class:

AggarwalYuEvolutionary<V extends NumberVector<?,?>>

private class AggarwalYuEvolutionary.EvolutionarySearch
extends Object

The inner class to handle the actual evolutionary computation.

Field Summary

(package private) int	dbsize Database size
(package private) int	dim Database dimensionality
(package private) int	m m to use.
private Random	random random generator
(package private) ArrayList<ArrayList<DBIDs>>	ranges Database ranges

Constructor Summary

AggarwalYuEvolutionary.EvolutionarySearch(Relation<V> database, ArrayList<ArrayList<DBIDs>> ranges, int m, Long seed)
Constructor.

Method Summary

private boolean	checkConvergence(Collection<AggarwalYuEvolutionary.Individuum> pop) check the termination criterion
private AggarwalYuEvolutionary.Individuum	combineRecursive(ArrayList<Integer> r, int i, int[] current, AggarwalYuEvolutionary.Individuum parent1, AggarwalYuEvolutionary.Individuum parent2) Recursive method to build all possible gene combinations using positions in r.
private ArrayList<AggarwalYuEvolutionary.Individuum>	crossoverOptimized(ArrayList<AggarwalYuEvolutionary.Individuum> population) method implements the crossover algorithm
private ArrayList<AggarwalYuEvolutionary.Individuum>	initialPopulation(int popsize) Produce an initial (random) population.
private AggarwalYuEvolutionary.Individuum	makeIndividuum(int[] gene) Make a new individuum helper, computing sparsity=fitness
private ArrayList<AggarwalYuEvolutionary.Individuum>	mutation(ArrayList<AggarwalYuEvolutionary.Individuum> population, double perc1, double perc2) method implements the mutation algorithm
private Pair<AggarwalYuEvolutionary.Individuum,AggarwalYuEvolutionary.Individuum>	recombineOptimized(AggarwalYuEvolutionary.Individuum parent1, AggarwalYuEvolutionary.Individuum parent2) Recombination method.
private ArrayList<AggarwalYuEvolutionary.Individuum>	rouletteRankSelection(ArrayList<AggarwalYuEvolutionary.Individuum> population) the selection criterion for the genetic algorithm: roulette wheel mechanism: where the probability of sampling an individual of the population was proportional to p - r(i), where p is the size of population and r(i) the rank of i-th individual
Collection<AggarwalYuEvolutionary.Individuum>	run()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

dbsize

final int dbsize

Database size

dim

final int dim

Database dimensionality

ranges

final ArrayList<ArrayList<DBIDs>> ranges

Database ranges

m

final int m

m to use.

random

private final Random random

random generator

Constructor Detail

AggarwalYuEvolutionary.EvolutionarySearch

public AggarwalYuEvolutionary.EvolutionarySearch(Relation<V> database,
                                                 ArrayList<ArrayList<DBIDs>> ranges,
                                                 int m,
                                                 Long seed)

Constructor.

Parameters:

database - Database to use

m - Population size

seed - Random generator seed

Method Detail

run

public Collection<AggarwalYuEvolutionary.Individuum> run()

checkConvergence

private boolean checkConvergence(Collection<AggarwalYuEvolutionary.Individuum> pop)

check the termination criterion

initialPopulation

private ArrayList<AggarwalYuEvolutionary.Individuum> initialPopulation(int popsize)

Produce an initial (random) population.

Parameters:

popsize - Population size

Returns:

Sorted list of Individuums

rouletteRankSelection

private ArrayList<AggarwalYuEvolutionary.Individuum> rouletteRankSelection(ArrayList<AggarwalYuEvolutionary.Individuum> population)

the selection criterion for the genetic algorithm:
roulette wheel mechanism:
where the probability of sampling an individual of the population was proportional to p - r(i), where p is the size of population and r(i) the rank of i-th individual

Parameters:

population -

mutation

private ArrayList<AggarwalYuEvolutionary.Individuum> mutation(ArrayList<AggarwalYuEvolutionary.Individuum> population,
                                                              double perc1,
                                                              double perc2)

method implements the mutation algorithm

makeIndividuum

private AggarwalYuEvolutionary.Individuum makeIndividuum(int[] gene)

Make a new individuum helper, computing sparsity=fitness

Parameters:

gene - Gene to evaluate

Returns:

new individuum

crossoverOptimized

private ArrayList<AggarwalYuEvolutionary.Individuum> crossoverOptimized(ArrayList<AggarwalYuEvolutionary.Individuum> population)

method implements the crossover algorithm

recombineOptimized

private Pair<AggarwalYuEvolutionary.Individuum,AggarwalYuEvolutionary.Individuum> recombineOptimized(AggarwalYuEvolutionary.Individuum parent1,
                                                                                                     AggarwalYuEvolutionary.Individuum parent2)

Recombination method.

Parameters:

parent1 - First parent

parent2 - Second parent

Returns:

recombined children

combineRecursive

private AggarwalYuEvolutionary.Individuum combineRecursive(ArrayList<Integer> r,
                                                           int i,
                                                           int[] current,
                                                           AggarwalYuEvolutionary.Individuum parent1,
                                                           AggarwalYuEvolutionary.Individuum parent2)

Recursive method to build all possible gene combinations using positions in r.

Parameters:

r - valid positions to use

i - Offset in r to start at.

current - Current gene

parent1 - First parent

parent2 - Second parent

Returns:

best gene combination