Chapter 9 - Simulatons

Report
Chapter 9 - Simulations
Bruce Chittenden
Supercomputers www.top500.org
Foxes and Rabbits
Exercise 9.1
Rabbits thin out where the
Foxes are in the Field
Exercise 9.2
When the Rabbit population
decreases to below a certain
threshold, the Foxes go extinct
As the Rabbit
population
increases the
Fox population
increases
Exercise 9.3 (First Run)
Exercise 9.3 (Second Run)
Exercise 9.3 (Third Run)
Exercise 9.3 (Fourth Run)
Exercise 9.3 (Fifth Run)
Exercise 9.3 (Sixth Run)
Exercise 9.3 (Seventh Run)
Exercise 9.3 (Eighth Run)
Exercise 9.3 (Ninth Run)
Exercise 9.3 (Tenth Run)
Exercise 9.3
Act
Steps
Rabbits
Foxes
1
2
3
4
5
6
7
8
9
10
679
219
199
441
130
240
748
72
471
432
187
160
204
0
2
274
0
33
119
0
0
0
0
52
0
0
10
0
0
66
Total
Average
3,631
363.1
979
128
Rabbit
Survival
Foxes
Survival
679
219
199
441
130
240
748
72
471
432
540.3
287.1
Exercise 9.4
Height and Width of the Field
public class Field extends World
{
// Constants representing configuration information for the simulation.
// The default width for the grid.
private static final int WIDTH = 40;
// The default depth of the grid.
private static final int HEIGHT = 30;
// The probability that a fox will be created in any given grid position (in percent).
private static final int FOX_CREATION_PROBABILITY = 2;
// The probability that a rabbit will be created in any given grid position (in percent).
private static final int RABBIT_CREATION_PROBABILITY = 8;
// The current step of the simulation.
private int step = 0;
Exercise 9.4
Changed the Field to be 80 by 60
or 400% of the Original Size
public class Field extends World
{
// Constants representing configuration information for the simulation.
// The default width for the grid.
private static final int WIDTH = 80;
// The default depth of the grid.
private static final int HEIGHT = 60;
// The probability that a fox will be created in any given grid position (in percent).
private static final int FOX_CREATION_PROBABILITY = 2;
// The probability that a rabbit will be created in any given grid position (in percent).
private static final int RABBIT_CREATION_PROBABILITY = 8;
// The current step of the simulation.
private int step = 0;
Exercise 9.4
Ran a Long Time
Exercise 9.4
Changed the Field to be 20 by 15
or 25% of the Original Size
public class Field extends World
{
// Constants representing configuration information for the simulation.
// The default width for the grid.
private static final int WIDTH = 20;
// The default depth of the grid.
private static final int HEIGHT = 15;
// The probability that a fox will be created in any given grid position (in percent).
private static final int FOX_CREATION_PROBABILITY = 2;
// The probability that a rabbit will be created in any given grid position (in percent).
private static final int RABBIT_CREATION_PROBABILITY = 8;
// The current step of the simulation.
private int step = 0;
Exercise 9.4
With 25% of the Space the
Species Went Extinct Very
Quickly
Exercise 9.5
Increase the Size of the Area from
30 x 40 or 1200 sq units to
35 x 45 or 1575 sq units
public class Field extends World
{
// Constants representing configuration information for the simulation.
// The default width for the grid.
private static final int WIDTH = 45;
// The default depth of the grid.
private static final int HEIGHT = 35;
// The probability that a fox will be created in any given grid position (in percent).
private static final int FOX_CREATION_PROBABILITY = 2;
// The probability that a rabbit will be created in any given grid position (in percent).
private static final int RABBIT_CREATION_PROBABILITY = 8;
// The current step of the simulation.
private int step = 0;
Exercise 9.5
Establish a Baseline
Exercise 9.5
Double the change of Breeding
from 12 to 25
public class Rabbit extends Animal
{
// Characteristics shared by all rabbits (static fields).
// The age at which a rabbit can start to breed.
private static final int BREEDING_AGE = 5;
// The age to which a rabbit can live.
private static final int MAX_AGE = 50;
// The likelihood of a rabbit breeding (in percent).
private static final double BREEDING_PROBABILITY = 25;
// The maximum number of births.
private static final int MAX_LITTER_SIZE = 5;
Exercise 9.5
Did not seem to make a
lot of difference
Exercise 9.6
public class Fox extends Animal
{
// Characteristics shared by all foxes (static fields).
Double Rabbit Food
// The age at which a fox can start to breed.
Value for 6 to 12
private static final int BREEDING_AGE = 10;
// The age to which a fox can live.
private static final int MAX_AGE = 150;
// The likelihood of a fox breeding (in percent).
private static final int BREEDING_PROBABILITY = 8;
// The maximum number of births.
private static final int MAX_LITTER_SIZE = 3;
// The food value of a single rabbit. In effect, this is the
// number of steps a fox can go before it has to eat again.
private static final int RABBIT_FOOD_VALUE = 6;
Exercise 9.6
Fox Population Seems
to Do Very Well
Exercise 9.7
public class Fox extends Animal
{
// Characteristics shared by all foxes (static fields).
Changed MAX_AGE
from 150 to 100
Changed BREEDING_PROBABLY
from 8 to 5
Changed BREEDING_AGE
from 10 to 20
// The age at which a fox can start to breed.
private static final int BREEDING_AGE = 20;
// The age to which a fox can live.
private static final int MAX_AGE = 100;
// The likelihood of a fox breeding (in percent).
private static final int BREEDING_PROBABILITY = 5;
// The maximum number of births.
private static final int MAX_LITTER_SIZE = 3;
// The food value of a single rabbit. In effect, this is the
// number of steps a fox can go before it has to eat again.
private static final int RABBIT_FOOD_VALUE = 12;
Exercise 9.7
9.2 Ants
Exercise 9.8
Nothing Happens
Exercise 9.9
import greenfoot.*; // (World, Actor, GreenfootImage, and Greenfoot)
/*
* An ant that collects food.
*
* @author Michael Kolling
Nothing in the act Method
* @version 0.1
*/
public class Ant extends Creature
{
/**
* Create an ant with a given home hill. The initial speed is zero (not moving).
*/
public Ant(AntHill home)
{
setHomeHill(home);
}
/*
* Do what an ant's gotta do.
*/
public void act()
{
}
}
Exercise 9.10
Exercise 9.11
/*
* Act: If there are still ants left inside, see whether one should come out.
*/
Ants do not move and 10% of the time when
public void act()
the act Method is called another Ant is created
{
at exactly the location of the Ant Hill up to the
if(ants < maxAnts)
Maximum number of ants
{
if(Greenfoot.getRandomNumber(100) < 10)
{
getWorld().addObject(new Ant(this), getX(), getY());
ants++;
}
}
}
Exercise 9.12
public class Ant extends Creature
{
/*
* Create an ant with a given home hill. The initial speed is zero (not moving).
*/
public Ant(AntHill home)
{
setHomeHill(home);
}
Add the randomWalk Method
/*
* Do what an ant's gotta do.
*/
public void act()
{
randomWalk();
}
}
to the Ants act Method
Exercise 9.12
9.3 Collecting Food
Crumbs with Even Distribution
Crumbs with Gaussian Distribution
Exercise 9.13
New subclass Food
Exercise 9.13
import greenfoot.*; // (World, Actor, GreenfootImage, Greenfoot and MouseInfo)
/*
* Write a description of class Food here.
*
* @author (your name)
* @version (a version number or a date)
*/
public class Food extends Actor
{
/*
* Act - do whatever the Food wants to do. This method is called whenever
* the 'Act' or 'Run' button gets pressed in the environment.
*/
public void act()
{
// Add your action code here.
}
}
Exercise 9.14
public class Food extends Actor
{
private int crumbs = 100; // number of bits of food in this pile
/*
* Act - do whatever the Food wants to do. This method is called whenever
* the 'Act' or 'Run' button gets pressed in the environment.
*/
public void act()
{
Number of Crumbs
// Add your action code here.
initialized to 100
}
}
Exercise 9.15
/*
* Update the image
*/
private void updateImage()
{
GreenfootImage image = new GreenfootImage(SIZE, SIZE);
for (int i = 0; i < crumbs; i++) {
int x = randomCoord();
int y = randomCoord();
image.setColorAt(x, y, color1);
image.setColorAt(x + 1, y, color2);
image.setColorAt(x, y + 1, color2);
image.setColorAt(x + 1, y + 1, color3);
}
setImage(image);
}
Exercise 9.15
/*
* Returns a random number relative to the size of the food pile.
*/
private int randomCoord()
{
int val = Greenfoot.getRandomNumber(SIZE);
if (val < 0)
return 0;
if (val > SIZE - 2)
return SIZE - 2;
else
return val;
}
Greenfoot.getRandomNumber()
Exercise 9.15
Even Distribution of the
Random Number Produces a
Square Food Pile
Exercise 9.16
Exercise 9.16
Exercise 9.17
/*
* Returns a random number relative to the size of the food pile.
*/
private int randomCoord()
{
int val = HALFSIZE + (int) (new Random().nextGaussian() * (HALFSIZE / 2));
if (val < 0)
return 0;
if (val > SIZE - 2)
return SIZE - 2;
else
return val;
}
Random().nextGaussian()
Exercise 9.17
Normal Distribution (Gaussian
Distribution) of the Random Number
Produces a Better Looking Food Pile
Random Distributions
If we need random behavior in our program it is sometime
important to think about what type of distribution we need.
Uniform Distribution Greenfoot.getRandomNumber(int range)
Normal Distribution
new Random().nextGaussian()
Exercise 9.18
/*
* Remove some food from this pile of food.
*/
public void takeSome()
{
crumbs = crumbs - 3;
if (crumbs <= 0) {
getWorld().removeObject(this);
}
else {
updateImage();
}
}
Exercise 9.18
Interactively Remove Food from the
Food Pile Until it is All Gone
Exercise 9.18
Continue Until the Food is All Gone.
Then Verify That the Food Pile is
Removed from the World
Exercise 9.18
Ant Behavior
If (carrying food)
{
walk towards home;
check whether we are home;
}
else
{
search for food;
}
Exercise 9.19
/*
* Walk around in search of food.
*/
private void searchForFood()
To Verify This Code is Working Place a
{
Call to the stop() Method if an Ant
randomWalk();
Finds a Food Pile
checkFood();
}
/*
* Is there any food here where we are? If so, take some!.
*/
public void checkFood()
{
Food food = (Food) getOneIntersectingObject(Food.class);
if (food != null) {
Greenfoot.stop();
}
}
Exercise 9.19
Exercise 9.20
/*
* Is there any food here where we are? If so, take some!.
*/
public void checkFood()
{
Food food = (Food) getOneIntersectingObject(Food.class);
if (food != null) {
takeFood(food);
}
}
/*
* Take some food from a fool pile.
*/
private void takeFood(Food food)
{
carryingFood = true;
food.takeSome();
setImage("ant-with-food.gif");
}
Exercise 9.20
Ants Just Wonder
Around Even When
Carrying Food
Exercise 9.21
/*
* Do what an ant's gotta do.
*/
public void act()
{
if (carryingFood)
{
walkTowardsHome();
}
else
{
searchForFood();
}
}
Exercise 9.21
The Ants All Go Home When
They Are Carrying Food, But
They Never Come Back Out
Exercise 9.22
/*
* Record that we have collected another bit of food.
*/
public void countFood()
{
// if we have no food counter yet (first time) -- create it
if(foodCounter == null)
{
foodCounter = new Counter("Food: ");
int x = getX();
int y = getY() + getImage().getWidth()/2 + 8;
getWorld().addObject(foodCounter, x, y);
}
foodCounter.increment();
}
Exercise 9.22
9.4 Setting Up the World
We need to create some initialization code that
creates some Ant Hills and food automatically.
Exercise 9.23
/*
* Create a new world. It will be initialized with a few ant hills
* and food sources
Initialize the Ant’s World
*/
public AntWorld()
{
super(SIZE, SIZE, 1);
createAntHills();
createFoodPiles();
}
Exercise 9.23
/*
* Create world contents: two ant hills and food.
*/
public void createAntHills()
{
removeObjects(getObjects(null)); // remove all existing objects
addObject(new AntHill(40), 546, 356);
addObject(new AntHill(40), 95, 267);
}
Exercise 9.23
/*
* Create some food piles.
*/
public void createFoodPiles()
{
addObject(new Food(), 80, 71);
addObject(new Food(), 291, 56);
addObject(new Food(), 516, 212);
addObject(new Food(), 311, 269);
addObject(new Food(), 318, 299);
addObject(new Food(), 315, 331);
addObject(new Food(), 141, 425);
addObject(new Food(), 378, 547);
addObject(new Food(), 566, 529);
}
Exercise 9.23
9.5 Adding Pheromones
Each pheromone object is a small drop of a chemical that
the ants leave on the ground. This drop will evaporate
fairly quickly and then disappear. Ants drop pheromones
while they are walking back home from a food source.
When other ants smell the drops on pheromone, they
can then turn away from their home hill and walk in the
direction toward the food.
Exercise 9.24
import greenfoot.*; // (World, Actor, GreenfootImage, Greenfoot and MouseInfo)
/*
* Write a description of class Pheromone here.
*
* @author (your name)
* @version (a version number or a date)
*/
public class Pheromone extends Actor
{
/*
* Act - do whatever the Pheromone wants to do. This method is called whenever
* the 'Act' or 'Run' button gets pressed in the environment.
*/
public void act()
{
// Add your action code here.
}
}
Exercise 9.24
Exercise 9.25
/*
* Make the image.
*/
private void updateImage()
{
GreenfootImage image = new GreenfootImage(65, 65);
image.setColor(new Color(255, 255, 255, 60));
image.fillOval(0, 0, 65, 65);
image.setColor(Color.DARK_GRAY);
image.fillRect(32, 32, 2, 2); // small dot in the middle
setImage(image);
}
Exercise 9.25
Manually Tested with
new Pheromone()
Exercise 9.26
/*
* Act - do whatever the Pheromone wants to do. This method is called whenever
* the 'Act' or 'Run' button gets pressed in the environment.
*/
Decrease the Intensity on
public void act()
Each Act Cycle and When
{
the Intensity Reaches 0
intensity -= 1;
Remove it from the World
if (intensity <= 0)
getWorld().removeObject(this);
else
updateImage();
}
Exercise 9.27
/*
* Make the image. The size and transparency are proportional to the intensity.
*/
private void updateImage()
Modify updateImage() so
{
that it Uses Intensity
int size = intensity / 3 + 5;
GreenfootImage image = new GreenfootImage(size + 1, size + 1);
int alpha = intensity / 3;
image.setColor(new Color(255, 255, 255, alpha));
image.fillOval(0, 0, size, size);
image.setColor(Color.DARK_GRAY);
image.fillRect(size / 2, size / 2, 2, 2); // small dot in the middle
setImage(image);
}
Exercise 9.28
Manually Added a new Pheromone to
the World Every 10 Act Cycles to Verify
it was Decreasing in Size and Intensity
Exercise 9.29
/*
* Do what an ant's gotta do.
*/
public void act()
{
if (carryingFood)
{
walkTowardsHome();
handlePheromoneDrop();
checkHome();
}
else
{
searchForFood();
}
}
Exercise 9.29
/*
* Drop pheromone.
*/
private void handlePheromoneDrop()
{
Pheromone ph = new Pheromone();
getWorld().addObject (ph, getX(), getY());
}
Exercise 9.29
Dropping Pheromone
on Every Act Cycle
Exercise 9.30
public class Ant extends Creature
{
/** Every how many steps can we place a pheromone drop. */
private static final int MAX_PH_LEVEL = 18;
/** Indicate whether we have any food with us. */
private boolean carryingFood = false;
/** How much pheromone do we have right now. */
private int pheromoneLevel = MAX_PH_LEVEL;
Exercise 9.30
/*
* Check whether we can drop some pheromone yet. If we can, do it.
*/
Drop Pheromone on
private void handlePheromoneDrop()
Every 18th Act Cycle
{
if (pheromoneLevel == MAX_PH_LEVEL)
{
Pheromone ph = new Pheromone();
getWorld().addObject(ph, getX(), getY());
pheromoneLevel = 0;
}
else
{
pheromoneLevel++;
}
}
Exercise 9.30
Pseudo Code
if (we recently found a drop of pheromone)
{
walk away from home;
}
else if (we smell pheromone now)
{
walk toward the center of the pheromone drop;
if (we are at the pheromone drop center)
{
note that we found pheromone;
}
}
else
{
walk randomly;
}
check for food;
Implementation of Pseudo Code
private void searchForFood()
{
if (foundLastPheromone > 0) // if we can still remember...
{
foundLastPheromone--;
walkAwayFromHome();
}
else if (smellPheromone())
{
walkTowardsPheromone();
}
else
{
randomWalk();
}
checkFood();
}
Exercise 9.31
9.6 Path Forming
One interesting aspect of this scenario is that there is no
code anywhere in the project that talks about forming
paths. The behavior of the individual ants is quite simple
if you have food go home;
if you smell pheromones go away;
otherwise go around;
However, together the ants display some fairly
sophisticated behavior. They form stable paths, refreshing
the pheromones as they evaporate, and efficiently
transport food back to their ant hill.
Exercise 9.32
In computer science and operations research, the ant
colony optimization algorithm (ACO) is a probabilistic
technique for solving computational problems which can be
reduced to finding good paths through graphs.
This algorithm is a member of ant colony algorithms family,
in swarm intelligence methods, and it constitutes some
metaheuristic optimizations. Initially proposed by Marco
Dorigo in 1992 in his PhD thesis, the first algorithm was
aiming to search for an optimal path in a graph, based on
the behavior of ants seeking a path between their colony
and a source of food. The original idea has since diversified
to solve a wider class of numerical problems, and as a
result, several problems have emerged, drawing on various
aspects of the behavior of ants.
Exercise 9.33
/*
* Check whether we can drop some pheromone yet. If we can, do it.
*/
Reduced by a Quarter,
private void handlePheromoneDrop()
The Time Between Drops
{
is Multiplied by 4
if (pheromoneLevel == MAX_PH_LEVEL * 4)
{
Pheromone ph = new Pheromone();
getWorld().addObject(ph, getX(), getY());
pheromoneLevel = 0;
}
else
{
pheromoneLevel++;
}
}
Exercise 9.33
The Trails are
Not as Good
Exercise 9.34
public class Ant extends Creature
{
/** Every how many steps can we place a pheromone drop. */
private static final int MAX_PH_LEVEL = 18;
/** How long do we keep direction after finding pheromones. */
private static final int PH_TIME = 10;
/** Indicate whether we have any food with us. */
private boolean carryingFood = false;
Changed from 30 to 10
/** How much pheromone do we have right now. */
private int pheromoneLevel = MAX_PH_LEVEL;
/** How well do we remember the last pheromone - larger number: more recent */
private int foundLastPheromone = 0;
Exercise 9.34
The Ants Seem to
be Confused
9.7 Summary
Simulations are an interesting type of
application. Many simulations are used in real
life for many purposes, such as weather
forecasting, traffic planning, environment impact
studies, physics research, and many more.
Concept Summary

similar documents