Package elki.outlier.subspace

Class AggarwalYuEvolutionary.EvolutionarySearch

java.lang.Object

elki.outlier.subspace.AggarwalYuEvolutionary.EvolutionarySearch

Enclosing class:

AggarwalYuEvolutionary

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	Description
(package private) int	dbsize	Database size.
(package private) int	dim	Database dimensionality.
private java.util.Random	random	random generator.
(package private) java.util.ArrayList<java.util.ArrayList<DBIDs>>	ranges	Database ranges.

Constructor Summary

Constructors

Constructor	Description
EvolutionarySearch(Relation<? extends NumberVector> relation, java.util.ArrayList<java.util.ArrayList<DBIDs>> ranges, java.util.Random random)	Constructor.

Method Summary

Modifier and Type	Method	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()	Run the evolutionary search.

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.

random

private final java.util.Random random

random generator.

Constructor Detail

EvolutionarySearch

public EvolutionarySearch(Relation<? extends NumberVector> relation,
                          java.util.ArrayList<java.util.ArrayList<DBIDs>> ranges,
                          java.util.Random random)

Constructor.

Parameters:

relation - Database to use

ranges - DBID ranges to process

random - Random generator

Method Detail

run

public Heap.UnorderedIter run()

Run the evolutionary search.

Returns:

Iterator of best results

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