Изучение эффективности эволюционных алгоритмов машинного обучения на примере адаптивного поведения интеллектуальных агентов в замкнутой среде

23. Деревья решений и алгоритмы их построения [Электронный ресурс]. - Режим доступа: http://datareview.info/article/derevya-resheniy-i-algoritmyi-ih-postroeniya/.

24. Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд. - СПб: Питер, 2013. - С. 444-459. -ISBN 978-5-459-00717-6.

25. Еремин Д.М., Гарцеев И.Б. Искусственные нейронные сети в интеллектуальных системах управления. - М.: МИРЭА, 2004. - 75 с. - ISBN 5-7339-0423-2.

26. Ali Hadidi, Sina Kazemzadeh Azad, Saeid Kazemzadeh Azad, Structural optimization using artificial bee colony algorithm, 2nd International Conference on Engineering Optimization, 2010, September 6-9, Lisbon, Portugal.

27. Лагодюк Ю. Эволюция агентов управляемых нейронной сетью [Электронный ресурс]. - Режим доступа: https://habrahabr.ru/post/168067/

28. Петров А.П. О возможностях перцептрона // Известия АН СССР, Техническая кибернетика. - 1964. - № 6.

29. Pham, D.T.; Castellani, M. (2009). "The Bees Algorithm - Modelling Foraging Behaviour to Solve Continuous Optimisation Problems". Proc. ImechE, Part C223 (12): 2919-2938.

30. Smed and Hakonen (2006). Algorithms and Networking for Computer Games. John Wiley & Sons. ISBN 0-470-01812-7.

31. Шампандар, Д.А. Искуственный интеллект в компьютерных играх / Д.А. Шампандар. - М.: Вильямс, 2007. - 768 с.



Приложение №1

Рис. Дерево основных классов программы



Приложение №2

ArtificialBeeColony.java

public class ArtificialBeeColony {

public int MAX_LENGTH; /*

* The number of parameters of the problem to be

* optimized

*/

public int FOOD_NUMBER; /*

* The number of food sources equals the half of the

* colony size

*/

public int MAX_EPOCH; /*

* The number of cycles for foraging {a stopping

* criteria}

*/

HashMap<String, Double> decision;

public Random rand;

public ArrayList<FoodForBees> foodSources;

public FoodForBees gBest;

public int epoch;

AgentsEnvironment environment;

ABCDrivenAgent currAgent;

public ArtificialBeeColony(int n) {

FOOD_NUMBER = n;

MAX_EPOCH = 5;

gBest = null;

epoch = 0;

decision = new HashMap<String, Double>();

environment = null;

currAgent = null;

}

public void setEnvironment(AgentsEnvironment e) {

this.environment = e;

}

public void setCurrentAgent(ABCDrivenAgent agent) {

this.currAgent = agent;

}

public HashMap<String, Double> optimizeDirection() {

foodSources = new ArrayList<FoodForBees>();

HashMap<String, Double> output = new HashMap<String, Double>();

rand = new Random();

boolean done = false;

boolean noSolution = false;

epoch = 0;

initialize();

memorizeBestFoodSource();

while (!done) {

if (epoch < MAX_EPOCH) {

if (gBest.getConflicts() == 0) { // if min time exists

done = true;

break;

}

sendEmployedBees();

getFitness();

calculateProbabilities();

sendOnlookerBees();

memorizeBestFoodSource();

sendScoutBees();

epoch++;

// This is here simply to show the runtime status.

//System.out.println("Epoch: " + epoch);

} else {

done = true;

}

}

if (epoch == MAX_EPOCH) {

//System.out.println("No Solution found");

done = false;

noSolution = true;

}

if (noSolution) {

Random random = new Random();

double deltaAngle = random.nextDouble() * 2 * Math.PI;

double deltaSpeed = random.nextDouble() * 4;

output.put("Speed", deltaSpeed);

output.put("Angle", deltaAngle);

return output;

} else {

return gBest.getDecision(); // return speed and dir

}

}

public void initialize() {

if ((environment!= null) && (currAgent!= null)) {

ArrayList<Food> allfood = new ArrayList<Food>();

for (Food currFood: environment.filter(Food.class)) {

allfood.add(currFood);

}

for (int i = 0; i < FOOD_NUMBER; i++) {

FoodForBees newHoney = new FoodForBees(FOOD_NUMBER, environment, currAgent);

foodSources.add(newHoney);

foodSources.get(i).setFood(allfood.get(i));

foodSources.get(i).setNearestEnemy(calculateNearestEnemy(environment, allfood.get(i)));

foodSources.get(i).calculateConflicts(); //

}

} else {

System.out.println("model is not initialized!");

}

}

private Agent calculateNearestEnemy(AgentsEnvironment env, Food f) {

Agent nearestAgent = null;

double nearestAgentDist = Double.MAX_VALUE;

for (Agent agent: environment.filter(Agent.class)) {

double currEnemyDist = distanceTo(agent, f);

if (currEnemyDist <= nearestAgentDist) {

nearestAgent = agent;

nearestAgentDist = currEnemyDist;

}

}

return nearestAgent;

}

protected double distanceTo(AbstractAgent food, AbstractAgent agent) {

return module(agent.getX() - food.getX(), agent.getY() - food.getY());

}

protected double module(double vx1, double vy1) {

return Math.sqrt((vx1 * vx1) + (vy1 * vy1));

}

public int getRandomNumber(int low, int high) {

return (int) Math.round((high - low) * rand.nextDouble() + low);

}

public void memorizeBestFoodSource() {

gBest = Collections.min(foodSources);

}

public void sendEmployedBees() {

int neighborBeeIndex = 0;

FoodForBees currentBee = null;

FoodForBees neighborBee = null;

for (int i = 0; i < FOOD_NUMBER; i++) {

// A randomly chosen solution is used in producing a mutant solution

// of the solution i

neighborBeeIndex = getExclusiveRandomNumber(FOOD_NUMBER - 1, i);

currentBee = foodSources.get(i);

neighborBee = foodSources.get(neighborBeeIndex);

sendToWork(currentBee, neighborBee);

}

}

public int getExclusiveRandomNumber(int high, int except) {

boolean done = false;

int getRand = 0;

while (!done) {

getRand = rand.nextInt(high);

if (getRand!= except) {

done = true;

}

}

return getRand;

}

public void sendToWork(FoodForBees currentBee, FoodForBees neighborBee) {

double currConflict = currentBee.getConflicts();

double neightborSpeed = 0;

double currentSpeed = currentBee.getSpeed();

double newSpeed = 0;

if (currConflict!= 2) { // we see food and have angle for it, need just

// to mutate speed

if (neighborBee.getNearestEnemy()!= null) {

neightborSpeed = neighborBee.getNearestEnemy().getSpeed();

if (neightborSpeed!= 0) {

newSpeed = currentSpeed + (2 * neightborSpeed * rand.nextDouble());

} else {

newSpeed = currentSpeed + (0.5 * rand.nextDouble());

}

} else {

System.out.println("error during..");

}

if (newSpeed > 4.0) {

newSpeed = 4.0;

}

if (newSpeed < -4.0) {

newSpeed = -4.0;

}

if (newSpeed!= 0) {

currentBee.getCurrAgent().setSpeed(newSpeed);

currentBee.calculateConflicts();

int newConflicts = currentBee.getConflicts();

if (currConflict <= newConflicts) {

// no improvement

currentBee.getCurrAgent().setSpeed(currentSpeed);

currentBee.calculateConflicts();

currentBee.setTrials(currentBee.getTrials() + 1);

} else {

currentBee.setTrials(0);

}

} else {

currentBee.setTrials(currentBee.getTrials() + 1);

// no speed

}

} else {

// we dont see this food, no worth trying until we change the angle

currentBee.setTrials(currentBee.getTrials() + 1);

//System.out.println("dont see food");

}

}

public void getFitness() {

// calculate best scores

// Lowest errors = 100 %, Highest errors = 0 %

FoodForBees thisFood = null;

double bestScore = 0.0;

double worstScore = 0.0;

// The worst score would be the one with the highest energy, best would

// be lowest.

worstScore = Collections.max(foodSources).getConflicts();

// Convert to a weighted percentage.

bestScore = worstScore - Collections.min(foodSources).getConflicts();

for (int i = 0; i < FOOD_NUMBER; i++) {

thisFood = foodSources.get(i);

thisFood.setFitness((worstScore - thisFood.getConflicts()) * 100.0 / bestScore);

}

//System.out.println("getting fitness");

}

public void calculateProbabilities() {

// calculate probability that this food will be chosen to go

FoodForBees thisFood = null;

double maxfit = foodSources.get(0).getFitness();

for (int i = 1; i < FOOD_NUMBER; i++) {

thisFood = foodSources.get(i);

if (thisFood.getFitness() > maxfit) {

maxfit = thisFood.getFitness();

}

}

for (int j = 0; j < FOOD_NUMBER; j++) {

thisFood = foodSources.get(j);

thisFood.setSelectionProbability((0.9 * (thisFood.getFitness() / maxfit)) + 0.1);

}

//System.out.println("calc probs");

}

/*

* Sends the onlooker bees to optimize the solution. Onlooker bees work on

* the best solutions from the employed bees. best solutions have high

* selection probability.

*

*/

public void sendOnlookerBees() {

// check solution and optimize it

int i = 0;

int neighborBeeIndex = 0;

FoodForBees currentBee = null;

FoodForBees neighborBee = null;

//System.out.println("onlookerzz");

for (int j = 0; j < FOOD_NUMBER; j++) {

currentBee = foodSources.get(j);

if (currentBee.getSelectionProbability() < 0.7) {

neighborBeeIndex = getExclusiveRandomNumber(FOOD_NUMBER - 1, i);

neighborBee = foodSources.get(neighborBeeIndex);

//System.out.println("onlooker");

sendToWork(currentBee, neighborBee);

i++;

}

}

}

/*

* Finds food sources which have been abandoned/reached the limit. Scout

* bees will generate a totally random solution from the existing and it

* will also reset its trials back to zero.

*

*/

public void sendScoutBees() {

FoodForBees currentBee = null;

for (int i = 0; i < FOOD_NUMBER; i++) {

currentBee = foodSources.get(i);

if (currentBee.getTrials() > 0) {

//System.out.println("sending scout");

Random random = new Random();

double deltaAngle = random.nextDouble() * 2 * Math.PI;

double deltaSpeed = random.nextDouble() * 4;

currentBee.getCurrAgent().setAngle(deltaAngle);

currentBee.getCurrAgent().setSpeed(deltaSpeed);

currentBee.calculateConflicts();

currentBee.setTrials(0);

}

}

}

}

FoodForBees.java

public class FoodForBees implements Comparable<FoodForBees> {

// solutions

// all food on the map + nearest enemy position: x, y, cos

// getters, setters for all parameters + functions to calculate distances

// and positions of nearest enemies

protected static final double maxAgentsDistance = 5;

public int FOOD_SIZE;

private int trials;

private double fitness;

private double selectionProbability;

private int conflicts; // conflicts

private double speed;

private AgentsEnvironment environment;

public ABCDrivenAgent currentAgent;

private Agent nearestEnemy;

private Food currFood;

private double foodCos;

public FoodForBees(int size, AgentsEnvironment e, ABCDrivenAgent currAgent) {

this.environment = e;

this.currentAgent = currAgent;

this.FOOD_SIZE = size;

this.conflicts = 0;

this.trials = 0;

this.fitness = 0.0;

this.selectionProbability = 0.0;

this.speed = 0.0;

this.foodCos = 0.0;

currFood = null;

nearestEnemy = null;

}

@Override

public int compareTo(FoodForBees o) {

return this.conflicts - o.getConflicts();

}

public Food getFood() {

return this.currFood;

}

public void setFood(Food f) {

this.currFood = f;

}

public Agent getNearestEnemy() {

return this.nearestEnemy;

}

public void setNearestEnemy(Agent en) {

this.nearestEnemy = en;

}

public int getConflicts() {

return this.conflicts;

}

public double getSpeed() {

return this.speed;

}

public void setConflicts(int t) {

this.conflicts = t;

}

public ABCDrivenAgent getCurrAgent() {

return this.currentAgent;

}

public void setCurrAgent(ABCDrivenAgent t) {

this.currentAgent = t;

}

public AgentsEnvironment getEnvironment() {

return this.environment;

}

public void setEnvironment(AgentsEnvironment env) {

this.environment = env;

}

public double getFoodCos() {

return this.foodCos;

}

public HashMap<String, Double> getDecision() {

HashMap<String, Double> output = new HashMap<String, Double>();

double out_speed = this.speed;

double out_angle = this.foodCos;

output.put("Speed", out_speed);

output.put("Angle", out_angle);

return output;

}

public void calculateConflicts() {

int currConflict = 0;

if (this.currentAgent.inSight(this.currFood)) {

double rx = this.currentAgent.getRx();

double ry = this.currentAgent.getRy();

double x = this.currentAgent.getX();

double y = this.currentAgent.getY();

double foodDirectionVectorX = currFood.getX() - x;

double foodDirectionVectorY = currFood.getY() - y;

double foodDirectionCosTeta = Math

.signum(pseudoScalarProduct(rx, ry, foodDirectionVectorX, foodDirectionVectorY))

* this.cosTeta(rx, ry, foodDirectionVectorX, foodDirectionVectorY);

this.foodCos = foodDirectionCosTeta;

if (this.nearestEnemy.inSight(this.currFood)) {

if (canReachFood(this.currentAgent, this.nearestEnemy, this.currFood)) {

currConflict += 1;

}

}

} else {

currConflict += 2;

this.foodCos = -2;

}

this.conflicts = currConflict;

this.speed = this.currentAgent.getSpeed();

if (this.speed == 0){

System.out.println("zero");

}

}

protected double pseudoScalarProduct(double vx1, double vy1, double vx2, double vy2) {

return (vx1 * vy2) - (vy1 * vx2);

}

protected double cosTeta(double vx1, double vy1, double vx2, double vy2) {

double v1 = this.module(vx1, vy1);

double v2 = this.module(vx2, vy2);

if (v1 == 0) {

v1 = 1E-5;

}

if (v2 == 0) {

v2 = 1E-5;

}

double ret = ((vx1 * vx2) + (vy1 * vy2)) / (v1 * v2);

return ret;

}

protected double module(double vx1, double vy1) {

return Math.sqrt((vx1 * vx1) + (vy1 * vy1));

}

private boolean canReachFood(ABCDrivenAgent currentAgent, Agent nearestAgent, Food food) {

if ((currentAgent.distanceTo(food) / currentAgent.getSpeed()) <= (nearestAgent.distanceTo(food)

/ nearestAgent.getSpeed())) {

// if your time is better, other agent cant reach food

return false;

} else {

return true;

}

}

public int getTrials() {

return trials;

}

public void setTrials(int trials) {

this.trials = trials;

}

public double getFitness() {

return fitness;

}

public void setFitness(double mFitness) {

this.fitness = mFitness;

}

public double getSelectionProbability() {

return selectionProbability;

}

public void setSelectionProbability(double mSelectionProbability) {

this.selectionProbability = mSelectionProbability;

}

}

ABCDrivenAgent.java

public class ABCDrivenAgent extends Agent {

protected static final double maxAgentsDistance = 5;

private int eatenFoodCount = 0;

private ArtificialBeeColony ABC;

public ABCDrivenAgent(double x, double y, double angle, int food) {

super(x, y, angle);

ABC = new ArtificialBeeColony(food);

initializeRandomSpeed(); // random direction for start speed + cos

}

public synchronized void interact(AgentsEnvironment env) {

Map<String, Double> output = new HashMap<String, Double>();

ABC.setEnvironment(env);

ABC.setCurrentAgent(this);

output = ABC.optimizeDirection();

double deltaAngle = output.get("Angle");

double deltaSpeed = output.get("Speed");

if (deltaSpeed == 0){

System.out.println("speed is zero");

}

deltaSpeed = this.avoidNaNAndInfinity(deltaSpeed);

deltaAngle = this.avoidNaNAndInfinity(deltaAngle);

double newSpeed = this.normalizeSpeed(this.getSpeed() + deltaSpeed);

double newAngle = this.getAngle() + this.normalizeDeltaAngle(deltaAngle);

if (newSpeed == 0) {

Random rand = new Random();

newSpeed = rand.nextDouble() * 4;

}

this.setAngle(newAngle);

this.setSpeed(newSpeed);

this.move();

}

public void initializeRandomSpeed() {

Random rand = new Random();

double randomSpeed = rand.nextDouble() * 4;

this.setSpeed(randomSpeed);

}

}

DecisionTree.java

public class DecisionTree {

/**

* Contains the set of available attributes.

*/

private LinkedHashSet<String> attributes;

/**

* Maps a attribute name to a set of possible decisions for that attribute.

*/

private Map<String, Set<String> > decisions;

private boolean decisionsSpecified;

/**

* Contains the examples to be processed into a decision tree.

*

* The 'attributes' and 'decisions' member variables should be updated

* prior to adding examples that refer to new attributes or decisions.

*/

private Examples examples;

/**

* Indicates if the provided data has been processed into a decision tree.

*

* This value is initially false, and is reset any time additional data is

* provided.

*/

private boolean compiled;

/**

* Contains the top-most attribute of the decision tree.

*

* For a tree where the decision requires no attributes,

* the rootAttribute yields a boolean classification.

*

*/

private Attribute rootAttribute;

private Algorithm algorithm;

public DecisionTree() {

algorithm = null;

examples = new Examples();

attributes = new LinkedHashSet<String>();

decisions = new HashMap<String, Set<String> >();

decisionsSpecified = false;

}

private void setDefaultAlgorithm() {

if (algorithm == null)

setAlgorithm(new ID3Algorithm(examples));

}

public void setAlgorithm(Algorithm algorithm) {

this.algorithm = algorithm;

}

/**

* Saves the array of attribute names in an insertion ordered set.

*

* The ordering of attribute names is used when addExamples is called to

* determine which values correspond with which names.

*

*/

public DecisionTree setAttributes(String []attributeNames) {

compiled = false;

decisions.clear();

decisionsSpecified = false;

attributes.clear();

for (int i = 0; i < attributeNames.length; i++)

attributes.add(attributeNames [i]);

return this;

}

/**

*/

public DecisionTree setDecisions(String attributeName, String []decisions) {

if (!attributes.contains(attributeName)) {

// TODO some kind of warning or something

return this;

}

compiled = false;

decisionsSpecified = true;

Set<String> decisionsSet = new HashSet<String>();

for (int i = 0; i < decisions.length; i++)

decisionsSet.add(decisions [i]);

this.decisions.put(attributeName, decisionsSet);

return this;

}

/**

*/

public DecisionTree addExample(String []attributeValues, boolean classification) throws UnknownDecisionException {

String []attributes = this.attributes.toArray(new String [0]);

if (decisionsSpecified)

for (int i = 0; i < attributeValues.length; i++)

if (!decisions.get(attributes [i]).contains(attributeValues [i])) {

throw new UnknownDecisionException(attributes [i], attributeValues [i]);

}

compiled = false;

examples.add(attributes, attributeValues, classification);

return this;

}

public DecisionTree addExample(Map<String, String> attributes, boolean classification) throws UnknownDecisionException {

compiled = false;

examples.add(attributes, classification);

return this;

}

public boolean apply(Map<String, String> data) throws BadDecisionException {

compile();

return rootAttribute.apply(data);

}

private Attribute compileWalk(Attribute current, Map<String, String> chosenAttributes, Set<String> usedAttributes) {

// if the current attribute is a leaf, then there are no decisions and thus no

// further attributes to find.

if (current.isLeaf())

return current;

// get decisions for the current attribute (from this.decisions)

String attributeName = current.getName();

// remove this attribute from all further consideration

usedAttributes.add(attributeName);

for (String decisionName: decisions.get(attributeName)) {

// overwrite the attribute decision for each value considered

chosenAttributes.put(attributeName, decisionName);

// find the next attribute to choose for the considered decision

// build the subtree from this new attribute, pre-order

// insert the newly-built subtree into the open decision slot

current.addDecision(decisionName, compileWalk(algorithm.nextAttribute(chosenAttributes, usedAttributes), chosenAttributes, usedAttributes));

}

// remove the attribute decision before we walk back up the tree.

chosenAttributes.remove(attributeName);

// return the subtree so that it can be inserted into the parent tree.

return current;

}

public void compile() {

// skip compilation if already done.

if (compiled)

return;

// if no algorithm is set beforehand, select the default one.

setDefaultAlgorithm();

Map<String, String> chosenAttributes = new HashMap<String, String>();

Set<String> usedAttributes = new HashSet<String>();

if (!decisionsSpecified)

decisions = examples.extractDecisions();

// find the root attribute (either leaf or non)

// walk the tree, adding attributes as needed under each decision

// save the original attribute as the root attribute.

rootAttribute = compileWalk(algorithm.nextAttribute(chosenAttributes, usedAttributes), chosenAttributes, usedAttributes);

compiled = true;

}

public String toString() {

compile();

if (rootAttribute!= null)

return rootAttribute.toString();

else

return "";

}

public Attribute getRoot() {

return rootAttribute;

}

}

ID3Algorithm.java

package com.hse12pi.decisiontree;

import java.util.*;

public class ID3Algorithm implements Algorithm {

private Examples examples;

public ID3Algorithm(Examples examples) {

this.examples = examples;

}

/**

* Returns the next attribute to be chosen.

*

* chosenAttributes represents the decision path from the root attribute

* to the node under consideration. usedAttributes is the set of all

* attributes that have been incorporated into the tree prior to this

* call to nextAttribute(), even if the attributes were not used in the path

* to the node under consideration.

*

* Results are undefined if examples.count() == 0.

*/

public Attribute nextAttribute(Map<String, String> chosenAttributes, Set<String> usedAttributes) {

double currentGain = 0.0, bestGain = 0.0;

String bestAttribute = "";

/*

* If there are no positive examples for the already chosen attributes,

* then return a false classifier leaf. If no negative examples,

* then return a true classifier leaf.

*/

if (examples.countPositive(chosenAttributes) == 0)

return new Attribute(false);

else if (examples.countNegative(chosenAttributes) == 0)

return new Attribute(true);

System.out.println("Choosing attribute out of " + remainingAttributes(usedAttributes).size() +" remaining attributes.");

System.out.println("Already chosen attributes/decisions are " + chosenAttributes);

for (String attribute: remainingAttributes(usedAttributes)) {

// for each remaining attribute, determine the information gain of using it

// to choose among the examples selected by the chosenAttributes

// if none give any information gain, return a leaf attribute,

// otherwise return the found attribute as a non-leaf attribute

currentGain = informationGain(attribute, chosenAttributes);

System.out.println("Evaluating attribute " +attribute +" information gain is " + currentGain);

if (currentGain > bestGain) {

bestAttribute = attribute;

bestGain = currentGain;

}

}

// If no attribute gives information gain, generate leaf attribute.

// Leaf is true if there are any true classifiers.

// If there is at least one negative example, then the information gain

// would be greater than 0.

if (bestGain == 0.0) {

boolean classifier = examples.countPositive(chosenAttributes) > 0;

System.out.println("Creating new leaf attribute with classifier" + classifier);

return new Attribute(classifier);

} else {

System.out.println("Creating new non-leaf attribute" +bestAttribute);

return new Attribute(bestAttribute);

}

}

private Set<String> remainingAttributes(Set<String> usedAttributes) {

Set<String> result = examples.extractAttributes();

result.removeAll(usedAttributes);

return result;

}

private double entropy(Map<String, String> specifiedAttributes) {

double totalExamples = examples.count();

double positiveExamples = examples.countPositive(specifiedAttributes);

double negativeExamples = examples.countNegative(specifiedAttributes);

return -nlog2(positiveExamples / totalExamples) -

nlog2(negativeExamples / totalExamples);

}

private double entropy(String attribute, String decision, Map<String, String> specifiedAttributes) {

double totalExamples = examples.count(attribute, decision, specifiedAttributes);

double positiveExamples = examples.countPositive(attribute, decision, specifiedAttributes);

double negativeExamples = examples.countNegative(attribute, decision, specifiedAttributes);

return -nlog2(positiveExamples / totalExamples) -

nlog2(negativeExamples / totalExamples);

}

private double informationGain(String attribute, Map<String, String> specifiedAttributes) {

double sum = entropy(specifiedAttributes);

double examplesCount = examples.count(specifiedAttributes);

if (examplesCount == 0)

return sum;

Map<String, Set<String> > decisions = examples.extractDecisions();

for (String decision: decisions.get(attribute)) {

double entropyPart = entropy(attribute, decision, specifiedAttributes);

double decisionCount = examples.countDecisions(attribute, decision);

sum += -(decisionCount / examplesCount) * entropyPart;

}

return sum;

}

private double nlog2(double value) {

if (value == 0)

return 0;

return value * Math.log(value) / Math.log(2);

}

}

GeneticAlgorithm.java

package com.hse12pi.geneticApproach.geneticAlgorithm;

public class GeneticAlgorithm<C extends Chromosome<C>, T extends Comparable<T" {

private static final int ALL_PARENTAL_CHROMOSOMES = Integer.MAX_VALUE;

private class ChromosomesComparator implements Comparator<C> {

private final Map<C, T> cache = new WeakHashMap<C, T>();

@Override

public int compare(C chr1, C chr2) {

T fit1 = this.fit(chr1);

T fit2 = this.fit(chr2);

int ret = fit1.compareTo(fit2);

return ret;

}

public T fit(C chr) {

T fit = this.cache.get(chr);

if (fit == null) {

fit = GeneticAlgorithm.this.fitnessFunc.calculate(chr);

this.cache.put(chr, fit);

}

return fit;

};

public void clearCache() {

this.cache.clear();

}

}

private final ChromosomesComparator chromosomesComparator;

private final Fitness<C, T> fitnessFunc;

private Population<C> population;

// number of parental chromosomes, which survive (and move to new

// population)

private int parentChromosomesSurviveCount = ALL_PARENTAL_CHROMOSOMES;

private int iteration = 0;

public GeneticAlgorithm(Population<C> population, Fitness<C, T> fitnessFunc) {

this.population = population;

this.fitnessFunc = fitnessFunc;

this.chromosomesComparator = new ChromosomesComparator();

this.population.sortPopulationByFitness(this.chromosomesComparator);

}

public void evolve() {

int parentPopulationSize = this.population.getSize();

Population<C> newPopulation = new Population<C>();

for (int i = 0; (i < parentPopulationSize) && (i < this.parentChromosomesSurviveCount); i++) {

newPopulation.addChromosome(this.population.getChromosomeByIndex(i));

}

for (int i = 0; i < parentPopulationSize; i++) {

C chromosome = this.population.getChromosomeByIndex(i);

C mutated = chromosome.mutate();

C otherChromosome = this.population.getRandomChromosome();

List<C> crossovered = chromosome.crossover(otherChromosome);

newPopulation.addChromosome(mutated);

for (C c: crossovered) {

newPopulation.addChromosome(c);

}

}

newPopulation.sortPopulationByFitness(this.chromosomesComparator);

newPopulation.trim(parentPopulationSize);

this.population = newPopulation;

}

/*public void evolve(int count) {

this.terminate = false;

for (int i = 0; i < count; i++) {

if (this.terminate) {

break;

}

this.evolve();

this.iteration = i;

for (IterartionListener<C, T> l: this.iterationListeners) {

l.update(this);

}

}

}*/

public int getIteration() {

return this.iteration;

}

public Population<C> getPopulation() {

return this.population;

}

public C getBest() {

return this.population.getChromosomeByIndex(0);

}

public C getWorst() {

return this.population.getChromosomeByIndex(this.population.getSize() - 1);

}

public void setParentChromosomesSurviveCount(int parentChromosomesCount) {

this.parentChromosomesSurviveCount = parentChromosomesCount;

}

public int getParentChromosomesSurviveCount() {

return this.parentChromosomesSurviveCount;

}

public T fitness(C chromosome) {

return this.chromosomesComparator.fit(chromosome);

}

public void clearCache() {

this.chromosomesComparator.clearCache();

}

}

Размещено на Allbest.ru

...