Download Parallel Problem Solving from Nature - PPSN VIII: 8th International Conference, Birmingham, UK, September 18-22, 2004. Proceedings PDF

TitleParallel Problem Solving from Nature - PPSN VIII: 8th International Conference, Birmingham, UK, September 18-22, 2004. Proceedings
Author
LanguageEnglish
File Size14.5 MB
Total Pages1203
Table of Contents
                            Frontmatter
Theory
	On the Quality Gain of (1,$\lambda$)-ES Under Fitness Noise
	Fitness Distributions and GA Hardness
	Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization
	The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes
	Evolutionary Algorithms with On-the-Fly Population Size Adjustment
	Search Space Features Underlying the Performance of Stochastic Local Search Algorithms for MAX-SAT
	Bridging the Gap Between Theory and Practice
	A Reduced Markov Model of GAs Without the Exact Transition Matrix
	Expected Runtimes of a Simple Evolutionary Algorithm for the Multi-objective Minimum Spanning Tree Problem
	On the Importance of Information Speed in Structured Populations
	Estimating the Number of Solutions for SAT Problems
	Behavior of Evolutionary Algorithms in Chaotically Changing Fitness Landscapes
	Expected Rates of Building Block Discovery, Retention and Combination Under 1-Point and Uniform Crossover
	An Analysis of the Effectiveness of Multi-parent Crossover
	On the Use of a Non-redundant Encoding for Learning Bayesian Networks from Data with a GA
	Phase Transition Properties of Clustered Travelling Salesman Problem Instances Generated with Evolutionary Computation
	A Simple Two-Module Problem to Exemplify Building-Block Assembly Under Crossover
	Statistical Racing Techniques for Improved Empirical Evaluation of Evolutionary Algorithms
New Algorithms
	LS-CMA-ES: A Second-Order Algorithm for Covariance Matrix Adaptation
	Learning Probabilistic Tree Grammars for Genetic Programming
	Sequential Sampling in Noisy Environments
	Evolutionary Continuous Optimization by Distribution Estimation with Variational Bayesian Independent Component Analyzers Mixture Model
	Spread of Vector Borne Diseases in a Population with Spatial Structure
	Hierarchical Genetic Algorithms
	Migration of Probability Models Instead of Individuals: An Alternative When Applying the Island Model to EDAs
	Comparison of Steady-State and Generational Evolution Strategies for Parallel Architectures
	Control of Bloat in Genetic Programming by Means of the Island Model
	Saving Resources with Plagues in Genetic Algorithms
	Evaluating the CMA Evolution Strategy on Multimodal Test Functions
	Exploring the Evolutionary Details of a Feasible-Infeasible Two-Population GA
	An Evolutionary Algorithm for the Maximum Weight Trace Formulation of the Multiple Sequence Alignment Problem
	A Novel Programmable Molecular Computing Method Based on Signaling Pathways Regulated by Rho-GTPases in Living MDCK Epithelial Mammalian Cells
	Empirical Investigations on Parallelized Linkage Identification
	The EAX Algorithm Considering Diversity Loss
	Topology-Oriented Design of Analog Circuits Based on Evolutionary Graph Generation
	A Mixed Bayesian Optimization Algorithm with Variance Adaptation
	A Swarm Intelligence Based VLSI Multiplication-and-Add Scheme
	Distribution Tree-Building Real-Valued Evolutionary Algorithm
	Optimization via Parameter Mapping with Genetic Programming
	Multi-cellular Development: Is There Scalability and Robustness to Gain?
	Constrained Evolutionary Optimization by Approximate Ranking and Surrogate Models
	Robust Parallel Genetic Algorithms with Re-initialisation
	Improving Evolutionary Algorithms with Multi-representation Island Models
	A Powerful New Encoding for Tree-Based Combinatorial Optimisation Problems
	Partially Evaluated Genetic Algorithm Based on Fuzzy c-Means Algorithm
Applications
	Metaheuristics for the Vehicle Routing Problem with Stochastic Demands
	AntHocNet: An Ant-Based Hybrid Routing Algorithm for Mobile Ad Hoc Networks
	A Scatter Search Algorithm for the 3D Image Registration Problem
	A Hybrid GRASP -- Evolutionary Algorithm Approach to Golomb Ruler Search
	Design of an Efficient Search Algorithm for P2P Networks Using Concepts from Natural Immune Systems
	A Novel Ant Algorithm for Solving the Minimum Broadcast Time Problem
	Designing Multiple-Use Primer Set for Multiplex PCR by Using Compact GAs
	Robust Inferential Sensors Based on Ensemble of Predictors Generated by Genetic Programming
	Searching Transcriptional Modules Using Evolutionary Algorithms
	Evolution of Voronoi-Based Fuzzy Controllers
	Analyzing Sensor States and Internal States in the Tartarus Problem with Tree State Machines
	Evolving Genetic Regulatory Networks for Hardware Fault Tolerance
	Evolving Dynamics in an Artificial Regulatory Network Model
	The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling
	An Evolutionary Approach to Modeling Radial Brightness Distributions in Elliptical Galaxies
	Conference Paper Assignment Using a Combined Greedy/Evolutionary Algorithm
	A Primer on the Evolution of Equivalence Classes of Bayesian-Network Structures
	The Infection Algorithm: An Artificial Epidemic Approach for Dense Stereo Matching
	Optimising Cancer Chemotherapy Using Particle Swarm Optimisation and Genetic Algorithms
	An Evolutionary Algorithm for Column Generation in Integer Programming: An Effective Approach for 2D Bin Packing
	An Improved Evaluation Function for the Bandwidth Minimization Problem
	Coupling of Evolution and Learning to Optimize a Hierarchical Object Recognition Model
	Evolution of Small-World Networks of Automata for Computation
	Recognizing Speed Limit Sign Numbers by Evolvable Hardware
	Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation
	Optimising the Performance of a Formula One Car Using a Genetic Algorithm
Multi-objective Optimisation
	An Inexpensive Cognitive Approach for Bi-objective Optimization Using Bliss Points and Interaction
	Finding Knees in Multi-objective Optimization
	Multi-objective Parallel Tabu Search
	SPEA2+: Improving the Performance of the Strength Pareto Evolutionary Algorithm 2
	An Extension of Generalized Differential Evolution for Multi-objective Optimization with Constraints
	Adaptive Weighted Particle Swarm Optimisation for Multi-objective Optimal Design of Alloy Steels
	Multi-objective Optimisation by Co-operative Co-evolution
	Sequential Process Optimisation Using Genetic Algorithms
	On Test Functions for Evolutionary Multi-objective Optimization
	Multi-objective Optimization of a Composite Material Spring Design Using an Evolutionary Algorithm
	Dominance Based Crossover Operator for Evolutionary Multi-objective Algorithms
	Evolutionary Bi-objective Controlled Elevator Group Regulates Passenger Service Level and Minimises Energy Consumption
	Indicator-Based Selection in Multiobjective Search
Co-evolution
	Intransitivity in Coevolution
	Group Transport of an Object to a Target That Only Some Group Members May Sense
	Hawks, Doves and Lifetime Reproductive Success
	Evolutionary Multi-agent Systems
	Credit Assignment Among Neurons in Co-evolving Populations
	A Visual Demonstration of Convergence Properties of Cooperative Coevolution
	Cooperative Coevolution of Image Feature Construction and Object Detection
	Spatial Embedding and Loss of Gradient in Cooperative Coevolutionary Algorithms
	A High Performance Multi-objective Evolutionary Algorithm Based on the Principles of Thermodynamics
Robotics and Multi-agent Systems
	Robustness in the Long Run: Auto-teaching {\itshape vs} Anticipation in Evolutionary Robotics
	A Self-adaptive Neural Learning Classifier System with Constructivism for Mobile Robot Control
	An Approach to Evolutionary Robotics Using a Genetic Algorithm with a Variable Mutation Rate Strategy
	Translating the Dances of Honeybees into Resource Location
	Natural Policy Gradient Reinforcement Learning for a CPG Control of a Biped Robot
	Evaluation of Adaptive Nature Inspired Task Allocation Against Alternate Decentralised Multiagent Strategies
	A Neuroevolutionary Approach to Emergent Task Decomposition
	Evolving the ``Feeling'' of Time Through Sensory-Motor Coordination: A Robot Based Model
Learning Classifier Systems and Data Mining
	An Artificial Immune System for Fuzzy-Rule Induction in Data Mining
	Speeding-Up Pittsburgh Learning Classifier Systems: Modeling Time and Accuracy
	A Simple Payoff-Based Learning Classifier System
	Lookahead and Latent Learning in a Simple Accuracy-Based Classifier System
	Knowledge Extraction and Problem Structure Identification in XCS
	Forecasting Time Series by Means of Evolutionary Algorithms
	Detecting and Pruning Introns for Faster Decision Tree Evolution
	Evolutionary Multiobjective Clustering
	Web Page Classification with an Ant Colony Algorithm
	Oneiric Processing Utilising the Anticipatory Classifier System
	Self-organizing Neural Grove: Efficient Multiple Classifier System Using Pruned Self-generating Neural Trees
	Evolutionary Multiobjective Knowledge Extraction for High-Dimensional Pattern Classification Problems
	Ensemble Learning with Evolutionary Computation: Application to Feature Ranking
	Fast Unsupervised Clustering with Artificial Ants
	A Novel Method of Searching the Microarray Data for the Best Gene Subsets by Using a Genetic Algorithm
	Using Genetic Programming for Feature Creation with a Genetic Algorithm Feature Selector
	AgentP Model: Learning Classifier System with Associative Perception
Backmatter
                        
Document Text Contents
Page 1

Lecture Notes in Computer Science 3242
Commenced Publication in 1973
Founding and Former Series Editors:
Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison
Lancaster University, UK

Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler
University of Surrey, Guildford, UK

Jon M. Kleinberg
Cornell University, Ithaca, NY, USA

Friedemann Mattern
ETH Zurich, Switzerland

John C. Mitchell
Stanford University, CA, USA

Moni Naor
Weizmann Institute of Science, Rehovot, Israel

Oscar Nierstrasz
University of Bern, Switzerland

C. Pandu Rangan
Indian Institute of Technology, Madras, India

Bernhard Steffen
University of Dortmund, Germany

Madhu Sudan
Massachusetts Institute of Technology, MA, USA

Demetri Terzopoulos
New York University, NY, USA

Doug Tygar
University of California, Berkeley, CA, USA

Moshe Y. Vardi
Rice University, Houston, TX, USA

Gerhard Weikum
Max-Planck Institute of Computer Science, Saarbruecken, Germany

Page 2

Xin Yao Edmund Burke José A. Lozano
Jim Smith Juan J. Merelo-Guervós
John A. Bullinaria Jonathan Rowe Peter Tiňo
Ata Kabán Hans-Paul Schwefel (Eds.)

Parallel Problem Solving
from Nature – PPSNVIII

8th International Conference
Birmingham, UK, September 18-22, 2004
Proceedings

1 3

Page 601

582 Jingpeng Li and Uwe Aickelin

When a human scheduler works, he normally builds a schedule systematically fol-
lowing a set of rules. After much practice, the scheduler gradually masters the knowl-
edge of which solution parts go well with others. He can identify good parts and is
aware of the solution quality even if the scheduling process is not completed yet, thus
having the ability to finish a schedule by using flexible, rather than fixed, rules. In
this paper, we will present two more human-like scheduling approaches, by using a
cutting-edge Bayesian Optimization Algorithm (BOA) and an Adapted Classifier
System (ACS) individually, to implement explicit learning from past solutions.

In our test problem (nurse scheduling) problem, the number of the nurse is fixed
(about 30), and the target is to create a weekly schedule by assigning each nurse one
out of up to 411 shift patterns in the most efficient way. Both of the proposed ap-
proaches achieve this by using one suitable rule, from a rule set that contains a num-
ber of available rules, for each nurse’s assignment. Thus, a potential solution is repre-
sented as a sequence of rules corresponding to the first nurse to the last nurse.

The long-term aim of our research is to model the learning of a human scheduler.
Humans can provide high quality solutions, but this is tedious and time consuming.
Typically, they construct schedules based on rules learnt during scheduling. Due to
human limitations, these rules are typically simple. Hence, our rules will be relatively
simple, too. Nevertheless, human generated schedules are of high quality due to the
ability of the scheduler to switch between the rules, based on the state of the current
solution. We envisage the proposed BOA and the ACS to perform this task.

2 The Nurse Scheduling Problem

Nurse scheduling has been widely studied recently ([4], [5]). The schedules generated
have to satisfy working contracts and meet the demand for a given number of nurses
of different grades on each shift. The problem is complicated by the fact that higher
qualified nurses can substitute less qualified nurses but not vice versa. Thus schedul-
ing the different grades independently is not possible. Due to this characteristic, find-
ing and maintaining feasible solutions for most local search algorithms is difficult.

2.1 Integer Linear Programming

The nurse scheduling problem can be formulated as an Integer Program as follows:

Indices:
i = 1...n nurse index;
j = 1...m shift pattern index;
k = 1...14 day and night index (1...7 are days and 8...14 are nights);
s = 1...p grade index.

Decision variables:
xij = 1 if nurse i works shift pattern j otherwise xij = 0.

Page 602

The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling 583

Parameters:
m = Number of shift patterns;
n = Number of nurses;
p = Number of grades;
ajk = 1 if shift pattern j covers day/night k otherwise ajk = 0;

qis = 1 if nurse i is of grade s or higher otherwise qis = 0;

pij = Preference cost of nurse i working shift pattern j;

Rks = Demand of nurses with grade s on day/night k;

Ni, Di, Bi = Shifts per week of nurse i if night / day / both shifts are worked;

F(i) = Set of feasible shift patterns for nurse i, where F(i) is defined as



∈∀=

∈∀=

∈∀=

=

=

=

=


Target function is to minimize total preference cost of all nurses, denoted as


= ∈

. (1)

Subject to:

1. Every nurse works exactly one feasible shift pattern:

∀=


;
(2)

2. The demand for nurses is fulfilled for every grade on every day and night:

∈ =

∀≥


. (3)

Constraint set (2) ensures that every nurse works exactly one shift pattern from
his/her feasible set, and constraint set (3) ensures that the demand for nurses is cov-
ered for every grade on every day and night. Note that the definition of qis is such that

higher graded nurses can substitute those at lower grades if necessary.
Typical problem dimensions are n = 30 nurses of p = 3 grades and m = 411 shift

patterns for each nurse. Thus, the integer programming has some 12000 binary vari-
ables and about 100 constraints. This is a moderately sized problem. However, some
problem cases remain unsolved after overnight computation using professional soft-
ware [4].

2.2 A Graphic Representation for Nurse Scheduling

Figure 1 shows a graphical representation of the solution structure of the problem: a
hierarchical and acyclic directed graph. The node ∈∈ in the

Page 1202

1184 Author Index

Hasenjäger, Martina 253
Hasson, Yehudit 501
He, Jun 922
Heering, Oliver 21, 31
Hernández Castro, Julio César 1061
Higuchi, Tatsuo 342
Hingston, Philip 862
Hiroyasu, Tomoyuki 742
Holden, Nicholas 1092
Holley, Julian C. 1103
Homma, Naofumi 342
Hoos, Holger H. 51
Huang, Yu-Cheng 511
Hurst, Jacob 942

Inoue, Hirotaka 1113
Ishibuchi, Hisao 1123
Ishii, Shin 972

Jaeggi, Daniel 732
Jansen, Thomas 21, 31, 61
Jin, Yaochu 792
Jong, Kees 1133
Jordaan, Elsa 522
Joung, Je-Gun 532

Kang, Lishan 922
Kao, Cheng-Yan 511
Katada, Yoshiaki 952
Kavka, Carlos 541
Kern, Stefan 282, 352
Khare, Vineet R. 882
Khosroshahi, Habib G. 591
Kim, DaeEun 551, 962
Kim, Mifa 742
Kimbrough, Steven Orla 292
Kipouros, Timoleon 732
Knowles, Joshua 1081
Kok, Joost N. 1071
Koller, Gabriele 302
Koopman, Arne 561
Kordon, Arthur 522
Körner, Edgar 662
Kosters, Walter A. 1071
Koumoutsakos, Petros 352
Kukkonen, Saku 752
Künzli, Simon 832
Kuo, P. Dwight 571

Labib, Richard 803

Labroche, Nicolas 1143
Lampinen, Jouni 752
Lanzi, Pier Luca 1051
La Poutré, J.A. 692
Lasarczyk, Christian 91
Lecarpentier, Benôıt 803
Leier, André 571
Leifhelm, Michael 21, 31
Li, Jin 591
Li, Jingpeng 581
Linkens, Derek Arthur 762
Liu, Jian-Qin 312
Liu, Juan 1153
Liu, Minzhong 922
Llorà, Xavier 1021, 1051
Lopes, Heitor S. 1011
López, J.I. 272
Lu, Ming 292
Luke, Sean 892
Luque del Arco-Calderón, Cristóbal 1061
Lutton, Evelyne 622

Mahfouf, Mahdi 762
Maneeratana, Kuntinee 772
Manfrin, Max 450
Manzano, T. 272
Marchiori, Elena 41, 1133
Mastrolilli, Monaldo 450
McCall, John 633
Merelo-Guervós, Juan Julián 602
Meyer-Nieberg, Silja 1
Miki, Mitsunori 742
Moey, Cheah C.J. 72
Mori, Takeshi 972
Munetomo, Masaharu 322
Murao, Naoya 322
Muruzábal, Jorge 612

Nagata, Yuichi 332
Nakamura, Yutaka 972
Namba, Satoshi 1123
Narihisa, Hiroyuki 1113
Natsui, Masanori 342
Neumann, Frank 81
Ni, Bin 1153

Ocenasek, Jiri 352
Oduguwa, Victor 782
Oh, Sok June 532
Ohkura, Kazuhiro 952
Okabe, Tatsuya 792

Page 1203

Author Index 1185

Olague, Gustavo 622
Olhofer, Markus 253, 792
Osswald, Matthias 722

Panait, Liviu 892
Pani, Danilo 362
Paquete, Luis 450
Parks, Geoff 732
Pérez, Cynthia B. 622
Petrovski, Andrei 633
Pipe, Anthony G. 1103
Plociennik, Kai 21, 31
Poli, Riccardo 11, 382
Poš́ık, Petr 372
Preuss, Mike 91
Price, Richard 982
Puchinger, Jakob 642
Puerta, José M. 242
Pujol, Joao C. F. 382

Raffo, Luigi 362
Raidl, Günther R. 302, 642
Ratle, Frédéric 803
Raychaudhury, Somak 591
Reeves, Colin R. 101
Richter, Hendrik 111
Riddle, Patricia 121
Roberts, Mark E. 902
Rodriguez-Tello, Eduardo 652
Roggen, Daniel 391, 561
Röglin, Heiko 21, 31
Rossi-Doria, Olivia 450
Rowe, Jonathan E. 72, 222
Roy, Rajkumar 782
Rudenko, Olga 812
Runarsson, Thomas Philip 401

Santamaŕıa, José 471
Sarma, Jayshree 912
Schiavinotto, Tommaso 450
Schmidt, Christian 202
Schneider, Georg 662
Schoenauer, Marc 182, 541, 812, 932
Schweer, Andrea 21, 31
Sebag, Michèle 932, 1133
Sekaj, Ivan 411
Sekanina, Lukas 682
Sendhoff, Bernhard 253, 662, 792, 882
Shimohara, Katsunori 312
Sipper, Moshe 501
Skinner, Cameron 121
Skolicki, Zbigniew 420

Smith, Matthew G. 1163
Smits, Guido 522
Smyth, Kevin 51
Soak, Sang-Moon 430
Stützle, Thomas 51
Sudha, Bhavani 633
Sudholt, Dirk 21, 31

Tannenbaum, Stefan 21, 31
Thangavelautham, Jekanthan 991
Thierens, Dirk 141, 232
’t Hoen, Pieter J. 872
Ting, Chuan-Kang 131
Tiwari, Ashutosh 782
Tiňo, Peter 982
Tomassini, Marco 672
Torresen, Jim 682
Torres-Jimenez, Jose 652
Trianni, Vito 1001
Trochu, François 803
Tsai, Huai-Kuang 511
Tuci, Elio 1001
Tyni, Tapio 822

Ueda, Kanji 952
Urquhart, Neil B. 151

Valkó, V.A. 41
van Dijk, Steven 141
Vanhaecke, Nicolas 182
van Hemert, Jano I. 151, 692
Venturini, Gilles 1143
Viñuela, Pedro Isasi 1061

Watanabe, Shinya 742
Watson, Richard A. 161, 232
Wegener, Ingo 21, 31
Wersing, Heiko 662
Wiegand, R. Paul 61, 892, 912
Wloch, Krzysztof 702
Wood, David Harlan 292

Yao, Xin 591, 882
Ylinen, Jari 822
Yoo, Si-Ho 440
Yuan, Bo 172

Zatuchna, Zhanna V. 1172
Zhang, Byoung-Tak 212, 532
Zitzler, Eckart 832
Zou, Xiufen 922

Similer Documents