Transcript From Interactive Evolutionary Algorithms to Agent

From Interactive Evolutionary Algorithms to
Agent-based Evolutionary Design
• Interactive Evolutionary Algorithm
– When and How
– Current Applications of IEAs
– Requirements and Remaining Problems
• Agent-based Systems
– A Brief Introduction
– Current Applications of ABSs
• Agent-based Design Optimisation: Some Ideas
Yaochu Jin
FTR/HRE-D
August, 2000
1
Interactive Evolutionary Algorithm
• When to use IEAs
– No objective function is explicitly/mathematically
available
– Multiple criteria decision-making/optimisation
– Task decomposition for large-scale problems
• How
Genotype
Phenotype
Selection
Fitness
Genotype
Phenotype
Selection Interface
Conventional EA
Yaochu Jin
FTR/HRE-D
August, 2000
2
Interactive EA
Current Applications of IEAs (I)
• Interactive Evolving of a 8-legged Robot (Gruan et al )
– Syntactic constraints
– Problem decomposition
– Hardwire of fitness
• Interactive Multi-criteria Decision-Making (Tanino et al)
– Identify satisfactory and unsatisfactory solutions
– Input desired level for each objective
– Provide the worst allowable value for each object
• Interactive Evolutionary
Design Systems (Parmee
et al)
– On-line preferences,
constraints
– Dynamic problem
decomposition
– Identification of highperformance regions
Yaochu Jin
FTR/HRE-D
August, 2000
Objective
A
Rule-Based
Preferences
On-line
Database
Machine-Based
Agents
Information
Gathering
Objective
C
Objective
B
External Agents
3
Current Applications of IEAs (II)
• Evolutionary Computer Graphics
• Evolutionary Music (GenJam: GA for generating Jazz solo)
• Speech Processing for Hearing Aid (adjusting filter
parameters)
• Virtual Reality Control of an Arm Wresting Robot
• Fashion Design
• Layout Design (Web page, GUI display design)
• Engineering Design (cars, concrete arc dam, suspension
bridge)
• Knowledge Acquisition and Data Mining
Yaochu Jin
FTR/HRE-D
August, 2000
4
Requirements and Remaining Problems
• Requirements
– Smaller population
– Fast convergence
– Capable of combining quantitative and qualitative evaluations
• Remaining Problems
– How to make the arduous task of the human evaluator easier
a) Human evaluation is done in every N generations (as evolution
control), the rest is done using an approximate model
b) Improving the Interface
– How to better co-ordinate and control different components of an
IEA (Problem decomposition, knowledge incorporation,
preferences for multiple objectives, constraints etc)
Yaochu Jin
FTR/HRE-D
August, 2000
5
What is an Agent?
An autonomous agent is a system situated within and
part of an environment that senses environment and
acts on it over time, in pursuit of its own agenda and so
as to effect what it senses in the future. (Franklin and
Graesser, 1996)
An agent should have the capability:
• to communicate and
• to learn
There are
• Biological agents
• Robotic agents
• Computational agents
Yaochu Jin
FTR/HRE-D
August, 2000
6
Agent-Based Systems (I)
• When Do We Need Agent-Based Systems
–
–
–
–
–
Different components with different (possibly conflicting) goals
Parallelism
Robustness
Scalability
An approach to Intelligence
• What is Agent-Based systems
Distributed AI
Distributed Problem Solving
(Information Management)
Yaochu Jin
FTR/HRE-D
August, 2000
Multi-Agent Systems
(Behavior Management)
7
Agent-Based Systems (II)
• Important Issues
– Agent structure (degree of heterogeneity, reactive/deliberative,
benevolent/competitive, etc.)
– System architecture (communication protocols etc.)
– Learning (reinforcement learning, learn from others, e.g.
stigmergy, modelling of others state, evolving)
• Agent Structures
– Homogeneous non-communicating MAS (Centralised Agents)






Yaochu Jin
FTR/HRE-D
August, 2000
Goals
Actions
Domain
knowledge
Goals
Actions
Domain
knowledge



Goals
Actions
Domain
knowledge
Centralised Agents
8
Agent-Based Systems (III)
– Heterogeneous non-communicating MAS (HNC-MAS)
– Heterogeneous communicating MAS (HC-MAS)






Goals
Actions
Domain
knowledge



Goals
Actions
Domain
knowledge
HNC-MAS
Yaochu Jin
FTR/HRE-D
August, 2000



Goals
Actions
Domain
knowledge



Goals
Actions
Domain
knowledge



Goals
Actions
Domain
knowledge
Goals
Actions
Domain
knowledge
HC-MAS
9
Agent-Based Systems (IV)
• System Architectures
– Facilitators (Federation Multi-Agent Architecture)
Facilitator
Facilitator
Facilitator
Tool
Wrapper
Yaochu Jin
FTR/HRE-D
August, 2000
Agent
10
Agent-Based Systems (V)
– Mediator-Centric Federation Architecture
Agent
Agent
Mediator
Mediator
Agent
Agent
Agent
Agent
– Autonomous Agent Approach
Agent
Agent
Agent
Agent
Yaochu Jin
FTR/HRE-D
August, 2000
Agent
11
Current Applications OF ABSs
•
•
•
•
Software Design
Planning and Scheduling in Manufacturing
Air Traffic Control
Robotics
– Robot leg control, robot joint (multiple arm) control
– Multiple robots
• Economic Systems and E-Commence (negotiation etc.)*
• Engineering Design
• Electric Power Systems
* A special issue on “Agent-based Modeling of Evolutionary
Economic Systems” will appear on IEEE TEC
Yaochu Jin
FTR/HRE-D
August, 2000
12
Design Tools
• General
– C++
– Java
Yaochu Jin
FTR/HRE-D
August, 2000
• Specialised
– Agent Building
Shell
– Voyager
– ZEUS (BT)
13
What can ABSs bring about for design?
• ABSs are capable of
–
–
–
–
Automatic task decomposition
Efficient knowledge incorporation and user interaction
Handling distributed constraints
Handling conflicting multiple criteria
• Well-developed methodologies are available
• More sophisticated design tools can be used
• Possible application to robot behaviour control
Yaochu Jin
FTR/HRE-D
August, 2000
14
Agent-based Design Optimisation:
First Step
CA
DA: Design Agent
CA: Cognitive Agent
HA: Human Agent
W: Wrapper
DA
W
HA
H
U
M
A
N

Show
Blade
Show
NURBS
Control
Points



Fitness
Assignment
Direct
Selection
Preference
Chromosome
Modification
S
e
l
e
c
t
i
o
n
Genotype
Phenotype
Fitness
Other agent model
Local Task
Execution
Yaochu Jin
FTR/HRE-D
August, 2000
15
Agent-based Design Optimisation:
Next Step
DA 3
DA 1
DA 2
M
DA: Design Agent
CA: Cognitive Agent
HA: Human Agent
TDA: Task Decomposition
M: Mediator
W: Wrapper
TDA
W
CA
HA
Yaochu Jin
FTR/HRE-D
August, 2000
16
Conclusion
• Agent-based evolutionary design provides a more
systematic approach to Design of Complex Systems
• Expect to see papers on Agent-based structural design*
* A project proposal is written by a professor at TU Darmstadt
for agent-based structural design. No further information is
available.
* A recent survey paper on On-line Soft Computing Conference
suggests that interactive and more systematic approach to
incorporate qualitative knowledge will be one important trend for
Evolutionary Engineering Design.
Yaochu Jin
FTR/HRE-D
August, 2000
17