Transcript compmodels-20041130

Introduction to
Computational Modeling of Social Systems
A hand-crafted agent-based model
Prof. Lars-Erik Cederman
Center for Comparative and International Studies (CIS)
Seilergraben 49, Room G.2, [email protected]
Nils Weidmann, CIS Room E.3 [email protected]
http://www.icr.ethz.ch/teaching/compmodels
Lecture, November 30, 2004
Today’s agenda
• Implementation of the Schelling model from scratch
– Ingredients and pseudocode notation
– Designing the classes
– Java implementation
• Elevator project
• Homework B
2
A „Self-Forming Neighborhood Model“
(Schelling, 1978)
3
• The model‘s building blocks:
– „roll of pennies“
– „roll of dimes“
» the agents
– „sheet of squared paper“
» the grid
• Movement of coins:
– if there are too many unlike neighbors,
– move to another location
pp. 147ff
Open questions: Model layout
4
• What is the size of the grid?
– 8x8 squares
• How many agents are there?
– 45 agents
• What is the agent configuration we start with?
– Distribute agents randomly over the grid
Parameters!
Open questions:
Agent movement
5
• What agent should be moved?
– Always choose random agent
• Definition of an agent‘s „neighborhood“
– The agents sitting on the eight surrounding
squares
• How many foreign agents will be tolerated
in one‘s neighborhood?
Parameter!
#neighbors
min
#alike
0
0
1,2
1
3,4,5
2
6,7,8
3
Java classes needed
• Model class
–
–
–
–
stores model parameters: dimension, colorRatio, populationRatio
keeps track of all agents in the game
initializes the model
runs the main simulation loop
• Agent class
– stores its color and position on the grid
– knows if it is content at the current position
– knows how to move
• Grid class
– stores the position of the agents
– can insert and remove agents
– can compute statistics about one‘s neighbors
6
Model class: Specification
7
Sets the percentage of
populated cells
Sets the percentage of
black agents
Grid class: Specification
This is where the agents
are stored
Computes the number of
black and white neighbors for
a given cell
8
Abstract class Agent
Abstract method: no
implementation!
9
PickyAgent and Position
Implementation of move()
10
The complete model
Association!
11
Extension!
Some interesting methods
12
Grid.getNeighborStats(..)
public int[] getNeighborStats(Position p) {
int[] stats = {0,0};
for (int i=Math.max(0,p.x-1); i<=Math.min(dimension-1, p.x+1); i++) {
for (int j=Math.max(0,p.y-1);j<=Math.min(dimension-1, p.y+1); j++) {
if (grid[i][j] != null) {
stats[grid[i][j].color]++;
}
}
}
return stats;
}
13
Grid.getFreePositions()
public ArrayList getFreePositions() {
ArrayList list = new ArrayList();
for (int i=0; i<dimension; i++) {
for (int j=0; j<dimension; j++) {
if (grid[i][j] == null) {
list.add(new Position(i,j));
}
}
}
return list;
}
14
Agent.isDiscontent(..)
// defines the minimum number of agents
// of the same color to be content
private int[] limits = {0,1,1,2,2,2,3,3,3};
protected boolean isDiscontent(Position pos) {
// we ask the grid about the number and color of our neighbors
int[] neighborStats = model.grid.getNeighborStats(pos);
int numNeighbors = neighborStats[WHITE] + neighborStats[BLACK];
// we use limits[] to see if we're satisfied
boolean isDiscontent = false;
if (neighborStats[color] < limits[numNeighbors])
isDiscontent = true;
return isDiscontent;
}
15
PickyAgent.move()
16
public void move() {
Remove agent temporarily from grid
model.grid.removeAgentAt(position);
if (isDiscontent(position)) {
ArrayList freePositions = model.grid.getFreePositions();
Iterator it = freePositions.iterator();
We don‘t want our previous position and
Position pos;
neither an unsatifying one
while (it.hasNext()) {
pos = (Position) it.next();
if ((pos.x == position.x && pos.y == position.y) || isDiscontent(pos))
it.remove();
}
if (freePositions.size() > 0) {
int randIndex = model.random.nextInt(freePositions.size());
Position newPos = (Position) freePositions.get(randIndex);
if (model.printResults)
System.out.println("Agent “ + agentID +
" moves from (“ + position.x + ",“ + position.y +
") to ("+newPos.x+","+newPos.y+").");
position = newPos;
Set the new position
}
}
model.grid.putAgentAt(this, position);
}
Put agent back on grid
Homework B1
Consider a modified implementation of the isDiscontent(..)
method that requires at least 1/3 of an agent‘s neighbors to be of
the same color. Draw a configuration of a 4x4 grid where at least
one agent would be satisfied using this implementation, but the
same agent would be discontent using Schelling‘s original
implementation. Clearly mark that agent.
17
Homework B2
In the following, we consider two agent types in
addition to the PickyAgent which as well extend
Agent. EuclidianAgent moves to a convenient square
closest to its present position. OptimalAgent moves
to a convenient position surrounded by the largest
number of agents of the same color.
a) In the configuration shown in fig. 1, indicate the
positions potentially picked by agent A if A was
(i) a PickyAgent, (ii) a EuclidianAgent, or (iii) an
OptimalAgent.
b) Submit implementations of EuclidianAgent and
OptimalAgent (both extend Agent!)
18
Agent A
O
#
#
O
#
#
#
#
O
#
O O
O
Fig. 1
ElevatorProject
2
1
0
Classes Objects
Tenant
Elevator
19
• Two tenants live in an apartment
complex with 1 occupying the first
floor and 2 the second
• The tenants move in and out of the
building using the elevator
• Calculate the expected waiting time
for both tenants
Calculating expected waiting time
20
W(i,j) waiting time for tenant i in position j
W(i,j|k) waiting time conditional on k's being last user
EW(1,0) = 0.5 EW(1,0|1) + 0.5 EW(1,0|2) =
0.5 x 0 + 0.5(0.5 x 0 + 0.5 x 2) = 0.5
EW(2,0) = 0.5 x 0 + 0.5 (0.5 x 0 + 0.5 x 1) = 0.25
EW(1,1) = 0.5 x 0 + 0.5 (0.5 x 1 + 0.5 x 1) = 0.5
EW(2,2) = 0.5 x 0 + 0.5 (0.5 x 1 + 0.5 x 2) = 0.75
EW = {EW(1,0) + EW(2,0) + EW(1,1) + EW(2,2)}/4 = 0.5
Elevator Project: Code
21
public class Model {
public static void main(String[] args) {
int n = 1000;
Tenant tenant1 = new Tenant(1);
Tenant tenant2 = new Tenant(2);
Elevator elevator = new Elevator();
for (int i=0; i<n; i++) {
if (Math.random()<0.5)
tenant1.move(elevator);
else
tenant2.move(elevator);
}
System.out.println("Waiting time = " + elevator.averageWaitingTime());
}
}
Tenant class
22
public class Tenant {
int home,floor;
public Tenant(int f) {
home = f;
if (Math.random()< 0.5)
floor = 0;
else
floor = f;
}
public boolean atHome() {
return floor == home;
}
public void move(Elevator elevator) {
elevator.callToFloor(floor);
if (atHome())
elevator.takeToFloor(this,0);
else
elevator.takeToFloor(this,home);
}
}
Elevator class
23
public class Elevator {
int floor, waitingTime, numTrips;
public Elevator() {
if (Math.random()< 0.5)
floor = 0;
else
floor = (int)(2.0*Math.random())+1;
waitingTime = 0;
numTrips = 0;
}
public void callToFloor(int f) {
waitingTime = waitingTime + Math.abs(f-floor);
numTrips++;
floor = f;
}
public void takeToFloor(Tenant tenant,int f) {
floor = f;
tenant.floor = f;
}
public double averageWaitingTime() {
return (double)waitingTime/(double)numTrips;
}
}
Example: ElevatorNProject
24
Apartment
building with
elevator:
What is the
average waiting
time?
n
...
3
2
1
0
Two types of elevators:
•Standard Type 0: Elevator
remains where it is after use
•Modified Type 1: Elevator
returns to zero after use
Homework B3
a) Modify the ElevatorProject program to the n-person
case. Introduce the modified (type 1) elevator that goes back to
floor 0 as an extended class of Elevator.
b) Simulate the average waiting time for both elevator types for floors
from n=2 up to n=10.
c) Under what circumstances is the modified elevator type more
efficient?
d**) Derive the theoretical waiting time of both elevator types
25