Transcript Evolutionary Cross

DREAM
Napier University - Scotland
University of Dortmund - Germany
Ecole Polytechnique - France
Leiden University - The Netherlands
University of Granada - Spain
South Bank University - England
People
•
•
•
•
•
•
Ben Paechter
Daniele Denaro
Thomas Baeck MikePreuß
Marc Schoenauer Pierre Collet
Gusz Eiben
Mark Jelasity
JJ Merelo
Maribel Arenas
Terry FogartyMing Feng
DREAM
2
European Commission
Universal Information Ecosystems
• “The Universal Information Ecosystems
(UIE) proactive initiative is aimed at exploring
and validating new technologies and
scenarios that can turn the complex
information infrastructure as it is emerging
today into a rich, adaptive, responsive and
truly open environment.”
DREAM
3
Infohabitants
Individuals, organisations, as well as
virtual entities acting on their behalf,
smart appliances, etc. could be denoted
as "infohabitants" of a Universal
Information Ecosystem.
Infohabitant:
Chromosome? Individual? Agent?
DREAM
4
DREAM
Distributed
Resource
Evolutionary
Algorithm
Machine
A virtual machine constructed
using a number of simple
machines connected over the
internet, that allows
infohabitants to evolve,
communicate, negotiate and
trade, in the pursuit of some
individual goal, with the possible
achievement of some global
goal.
DREAM
5
DREAM Objectives - 1
 To create the software infrastructure necessary to support
evolving infohabitants in an open and scalable fashion, using
existing Internet infrastructure and existing hardware resources
 To unify evolution approaches, so that infohabitants can evolve
using a number of complementary mechanisms
 To allow meta-optimisation procedures, so that the algorithms
for evolution themselves can be optimised by co-evolving a
virtual world with the infohabitants it contains
DREAM
6
DREAM Objectives - 2
 To create the software infrastructure necessary to support the
emergent virtual economy that will result from the
implementation of virtual machine onto physical resources
 To demonstrate the usefulness of the infrastructure by using it to
implement three applications which can make full use of it
 Optimisation - Scheduling
 Modelling - Data Mining
 Simulation - economic and social systems
DREAM
7
Innovation
A framework in which to develop instantiations of
applications, rather than having the models or
problems hard-coded into it, which allows:
 the solution of industrial optimisation problems and the
simulation of the behaviour of large systems
 free migration of infohabitants through the internet, thus allowing
the formation of diverse niches
 the use of spare CPU cycles in an automated and secure
manner
 behaviour at the macro level to be observed
 scalability and openness
DREAM
8
Virtual Level
Any number of
experiments may
exist at the same
time on one DREAM
DREAM A
Experiment 1
Experiment 3
Experiment 2
DREAM
9
Virtual Level
• Problems can be tackled in an adaptive fashion
• Individual infohabitants or sub-population can
compete - giving quality pressures
• Possibility for co-operation, negotiation or trade
• This will lead to a collective intelligence that divides
the problem at hand and allows infohabitants to
generate a solution jointly
• In addition, a virtual society can be set up to simulate
aspects of real society
DREAM
10
DREAM Evolution
• The system will be designed to include at least all
the existing systems for evolution (Genetic
Algorithms, Evolution Strategies, Evolutionary
Programming, Genetic Programming, etc.) and will
unify these
• Meta-evolution procedures will be allowed, so that
algorithms for evolution can be optimised by coevolving a virtual world with the inhabitants in
contains
DREAM
11
Standard Island Model EA
• Individual :
• genome
• Each island implements a local EA :
• Infohabitants selection,
• Reproduction / mutation,
• Evaluation,
• Individuals are migrated periodically
(distribution).
DREAM
12
Extensions to Island Model
• Simulator for human societies.
• Emergence of economic and social aspects.
• Evaluation of given policy and design of new
policies (inverse pb).
 The standard algorithm must be enriched.
DREAM
13
Proposed algorithm
•
•
Local economy based on ACUs (Activation Currency Unit)
Individual : •genome •UID •Other personal
•
Each island implements a specific local EA :
•“brain”
•
•
•
•
•
•
•purse
methods
Several ACUs per infohabitant.
Selection of parents + Reproduction / variation,
N ACUs per newborn,
Activation of infohabitants (fixed tax),
Reward,
Selection (poor infohabitants die).
+ “Governmental” activities (island policy, migration management,
environmental tasks (library), creation of new islands, …)
DREAM
14
Possible activities for
infohabitants



Evaluation
Migration
Communication:


With the island
(queries on island
policy, on other
islands,…)
(1-1 / 1-n),



Reproduction (cloning).
Variation (mutation,
recombination …).
ACUs management:
– Borrowing (w or w/o interests)
– Lending (w or w/o interests)
– Trade (sell / buy)
Whenever activated, the brain decides of the action to take.
Each activity has a cost  possible emergence of an economy.
Communication  possible emergence of social aspects.
DREAM
15
Downgraded Algorithm
• Mono-ACU local economy.
•genome •UID
•Other personal
• Individual :
•“brain ” •purse
methods
Each island implements a specific local EA :
•
•
•
•
•
•
1 ACU per infohabitant.
Selection of parents + Reproduction / variation,
1 ACU per newborn,
Activation of infohabitants = evaluation (fixed tax of 1 ACU),
Reward with at most 1 ACU (selection by the island),
Garbage collection (poor infohabitants die).
+ governmental migration …
DREAM
16
Physical Level
DREAM A
•
•
•
•
•
•
A DREAM may use any number
of physical machines
A physical machine could run
more than one DREAM
The DREAM will not interfere
with the other functions of the
machine
It will use only the CPU time
allocated to it - normally just
spare CPU time
Physical machines could be colocated, or spread world-wide
Allows much more efficient use
of resources
DREAM B
DREAM
17
Structure
• Usually (if there are enough machines) there
will be one island per machine.
• An island cannot be split between machines
• Islands can cause new islands to exist on
some machine
• Each machine will know about at least some
other machines
• The machines will form a connected graph
(hopefully and usually)
DREAM
18
Interacting with the DREAM
• To start an experiment a user must connect
their machine to the DREAM as a console.
• To monitor or control an experiment the
console machine (or some other acting as the
console) must be connected.
• If the console has been unconnected then
there may be delay between connecting and
the time when each of the machines knows
the console is there.
DREAM
19
Sharing of Resources
• How resources should be shared is a difficult
problem.
• Should someone giving more resources be
able to use more resources?
• The DREAM will allow the collection of
resource provision and use data, and the
implementation of distribution policies.
• The distribution policy itself will be left to the
DREAM administrators to decide.
DREAM
20
Implementation
• Using Java
• On Linux and Windows Operating
Systems
• Probably using an existing open source
agent based system as the basis
DREAM
21
DREAM-User Interface
Good interfaces to such a complex system are vital.
• Input interface: Will allow the definition of the
characteristics of the target experiment, and the kind
of infohabitants that will evolve in that world.
Specifying experiments and infohabitants through
graphical manipulation will be possible
• Output interface: Will allow the graphical monitoring
of observables at the infohabitant, island and
experiment level
DREAM
22
Conclusions
• A general framework will be built that will
allow the building of DREAMs and the
specification of experiments to run on those
DREAMs with the minimum of effort
• The framework will unify the different
approaches to evolutionary computing
• There will be a much more efficient use of
resources
• New functionality will (we hope) lead to new
emergent behaviour
DREAM
23
The End
• Slides after this point are not part of the
presentation but just filed here in cases
they are needed!
DREAM
24
Proof of Principle
The usefulness of the framework will be tested by
building three proof-of-principle applications using it:
• Optimisation: Distributed Human Resource Scheduling
• Modelling: Distributed Data Mining
• Simulation: E.g. Road Traffic Balancing, Tax/Welfare Policy Both direct and inverse problem
DREAM
25
Software
Each computer within a DREAM
will have either the DREAM
master software module or the
smaller slave module which
doesn’t allow user interaction.
Each computer will also have a
software module for each
experiment it is participating in.
Not all computers will participate
in each experiment because, for
example, an experiment module
may not exist for each platform.
DREAM
Master
Module
Exp 2
Module
Exp 1
Module
Master
Module
Exp 1
Module
Owns Exp 1
Owns Exp 2
Exp 2
Module
Slave
Module
Exp 1
Module
26
Project Timetable
Whole Project
WP1 – Prototype Construction
%
WP2 – Economic and Social Behaviour
30
WP3 – Distributed Data Mining
20
WP4 – Distributed Scheduling
23.3
WP5 – Evaluation and Redesign
9.2
73.3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
91.7
9.2
WP6 – Documentation, Dissemination and 82..5
Exploitation
WP 7 – Project Co-ordination
8.3
DREAM
27
Conclusion
• Standard EA are still allowed (downgraded
mode)
• The DREAM seems to be able to
implement all WorkPackages.
DREAM
28
Commission Funding
Structure
• Information Society Technologies
• Future and Emerging Technologies
• Proactive Initiatives
– Quantum information processing and communication
– Nanotechnology information devices
– Universal Information Ecosystems
DREAM
29
UIE Features
 Openness and Universality
 Scalable
 Timeliness and relevance
 Adapting to changing conditions
 Realising objectives and intentions
DREAM
30
The Partners
• Napier University - Ben Paechter
• University of Dortmund - Thomas Baeck
• Ecole Polytechnique - Marc Schoenauer
• Leiden University - Gusz Eiben
• University of Granada - JJ Merelo
• South Bank University - Terry Fogarty
Project is worth 1,106,000 euros over
three years
DREAM
31
DREAM Economy
• Infohabitants will use hardware resources owned by
someone other than the infohabitant’s owner
• People giving large amount of computer resources
will want to be able to draw on these “banked
resources” at some later time.
• An economy based on the raw material of computer
resources will emerge
• Infohabitants may use this currency is their
interactions
• Relationships between the economic wealth of an
infohabitant and its fitness will be investigated
DREAM
32