de.lmu.ifi.dbs.elki.algorithm.outlier.subspace

Class AggarwalYuEvolutionary.EvolutionarySearch

java.lang.Object

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

Enclosing class:

AggarwalYuEvolutionary<V extends NumberVector>

private class AggarwalYuEvolutionary.EvolutionarySearch
extends java.lang.Object

The inner class to handle the actual evolutionary computation.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field and Description
(package private) int	dbsize Database size.
(package private) int	dim Database dimensionality.
(package private) int	m m to use.
private java.util.Random	random random generator.
(package private) java.util.ArrayList<java.util.ArrayList<DBIDs>>	ranges Database ranges.

Constructor Summary

Constructors

Constructor and Description
EvolutionarySearch(Relation<V> relation, java.util.ArrayList<java.util.ArrayList<DBIDs>> ranges, int m, java.util.Random random) Constructor.

Method Summary

Modifier and Type	Method and Description
private boolean	checkConvergence(java.util.Collection<AggarwalYuEvolutionary.Individuum> pop) check the termination criterion.
private AggarwalYuEvolutionary.Individuum	combineRecursive(it.unimi.dsi.fastutil.ints.IntArrayList r, int i, short[] current, AggarwalYuEvolutionary.Individuum parent1, AggarwalYuEvolutionary.Individuum parent2) Recursive method to build all possible gene combinations using positions in r.
private java.util.ArrayList<AggarwalYuEvolutionary.Individuum>	crossoverOptimized(java.util.ArrayList<AggarwalYuEvolutionary.Individuum> population) method implements the crossover algorithm
private java.util.ArrayList<AggarwalYuEvolutionary.Individuum>	initialPopulation(int popsize) Produce an initial (random) population.
private AggarwalYuEvolutionary.Individuum	makeIndividuum(short[] gene) Make a new individuum helper, computing sparsity=fitness
private java.util.ArrayList<AggarwalYuEvolutionary.Individuum>	mutation(java.util.ArrayList<AggarwalYuEvolutionary.Individuum> population, double perc1, double perc2) Apply the mutation algorithm.
private Pair<AggarwalYuEvolutionary.Individuum,AggarwalYuEvolutionary.Individuum>	recombineOptimized(AggarwalYuEvolutionary.Individuum parent1, AggarwalYuEvolutionary.Individuum parent2) Recombination method.
private java.util.ArrayList<AggarwalYuEvolutionary.Individuum>	rouletteRankSelection(java.util.ArrayList<AggarwalYuEvolutionary.Individuum> population) Select surviving individuums weighted by rank.
Heap.UnorderedIter	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 java.util.ArrayList<java.util.ArrayList<DBIDs>> ranges

Database ranges.

m

final int m

m to use.

random

private final java.util.Random random

random generator.

Constructor Detail

EvolutionarySearch

public EvolutionarySearch(Relation<V> relation,
                          java.util.ArrayList<java.util.ArrayList<DBIDs>> ranges,
                          int m,
                          java.util.Random random)

Constructor.

Parameters:

relation - Database to use

ranges - DBID ranges to process

m - Population size

random - Random generator

Method Detail

run

public Heap.UnorderedIter run()

checkConvergence

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

check the termination criterion.

Parameters:

pop - Population

Returns:

Convergence

initialPopulation

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

Produce an initial (random) population.

Parameters:

popsize - Population size

Returns:

Sorted list of Individuums

rouletteRankSelection

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

Select surviving individuums weighted by rank. 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 - Population

Returns:

Survivors

mutation

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

Apply the mutation algorithm.

makeIndividuum

private AggarwalYuEvolutionary.Individuum makeIndividuum(short[] gene)

Make a new individuum helper, computing sparsity=fitness

Parameters:

gene - Gene to evaluate

Returns:

new individuum

crossoverOptimized

private java.util.ArrayList<AggarwalYuEvolutionary.Individuum> crossoverOptimized(java.util.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(it.unimi.dsi.fastutil.ints.IntArrayList r,
                                                           int i,
                                                           short[] 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