TECHNISCHE UNIVERSITEIT
DELFT
Faculteit Elel<;trotechniek, W i s k u n d e en I n f o r m a t i c a
foj Delft
Tentamen TI2736-A - Computational Intelligence 5-nov-2014, 14:00-15:30
e H e t hele t e n t a m e n heeft 5 meerkeuzevragen in t o t a a l goed voor 10 p u n t e n en 5 open vragen m e t in t o t a a l 37 p u n t e n . O W a t b e t r e f t de meerkeuzevragen: -
Er is voor iedere vraag telkens maar één goed a n t w o o r d mogelijk.
O W a t b e t r e f t de open vragen:
•
-
Geef a n t w o o r d in correct Nederlands of Engels en schrijf leesbaar ( g e b r u i k eerst k l a d p a p i e r ) .
-
Motiveer je antwoorden.
-
Geef geen irrelevante i n f o r m a t i e . D i t kan leiden t o t p u n t e n a f t r e k .
H e t gebruik van b o e k of aantekeningen t i j d e n s d i t t e n t a m e n is niet t o e g e s t a a n ,
e H e t gebruik van een rekenmachine is t o e g e s t a a n . © Controleer, v o o r d a t j e j e a n t w o o r d e n inlevert, of op ieder blaadje j e naam en s t u d i e n u m m e r s t a a t en geef het aantal ingeleverde bladen aan op t e n m i n s t e de eerste pagina. O De t e n t a m e n s t o f bestaat uit de o n d e r w e r p e n zoals behandeld t i j d e n s de colleges. O Uiteraard komen in één t e n t a m e n niet alle onderwerpen aan b o d . Trek d a a r o m op basis van d i t t e n t a m e n geen conclusies over s t o f die n o o i t g e t o e t s t w o r d t . O T o t a a l aantal pagina's: 4 .
Succes!
T I 2 7 3 6 - A - C o m p u t a t i o n a l Intelligence
pagina 1 van 4
5-nov-2014
Meerkeuzevragen 1. (2 p u n t e n )
C o m p e t i t i v e learning is a f o r m of:
A . reinforcement learning. B. supervised learning. C. unsupervised learning. D. swarm intelligence. 2. (2 p u n t e n )
Local-best and Global-best PSO differ i n :
A . Tine f o r m u l a t i o n of the particles velocity. B. T h e c o m p u t a t i o n o f t h e Social C o m p o n e n t . C. T h e value o f t h e fitness f u n c t i o n D. T h e c o m p u t a t i o n o f t h e cognitive C o m p o n e n t . 3. (2 p u n t e n ) W h i c h of these a c t i v a t i o n f u n c t i o n s c a n n o t be used in a feed f o r w a r d neural network, if we plan t o t r a i n it w i t h b a c k p r o p a g a t i o n : A . A hyperbolic t a n g e n t B. A s i g m o i d . C. A sinusoid D. A step f u n c t i o n 4. (2 p u n t e n ) Bij Reinforcement Learning ( R L ) w o r d t er geleerd o m acties in states wel o f niet t e herhalen op basis van het verkrijgen van reinforcement (feedback) na het uitvoeren van een actie.
Hierbij v e r g r o o t
positieve feedback de kans op herhaling, t e r w i j l negative feedback deze kans verkleint. Welke van de volgende stellingen is onwaar: A. V{s)
de d i s c o u n t factor 7 zorgt er voor dat naar m a t e reinforcement verder in de t o e k o m s t verwijderd
is deze minder waard is voor de berekening van de waarde van een s t a t e s. B. H e t aantal mogelijke acties en het aantal mogelijke states bepaalt in sterke m a t e de leerbaarheid van een o p t i m a l e oplossing. C. Reinforcement is positief of negatief en w o r d t formeel genoteerd als
R(s,af-^).
D. O m d a t RL een C o m p u t a t i o n a l Intelligence techniek is, is het e r g goed in het leren van o p t i m a a l gedrag in hele grote state spaces. 5. (2 p u n t e n ) In C o m p u t a t i o n a l Intelligence is de fitness f u n c t i e w i s k u n d i g gezien: A . Een projectie van states naar waardes. B. Een landschap m e t bergen en dalen. C. Een manier o m zoeken t e o p t i m a l i s e r e n . D. Een projectie van waardes naar states.
Open vragen 6. De onderstaande vraagstukken gaan over Cl technieken in de p r a k t i j k . Geef voor ieder van de onderstaande vraagstukken aan welke van de in dit
val< behandelde oplossingsmethoden het meest
geschikt is ( z i j n ) .
[Vlotiveer j e a n t w o o r d e n door k o r t ( ! ) t e beschrijven (a) w a t v o o r T Y P E problemen (beslisprobleem, o p t i m a l i satieprobleem, e t c . ) een rol in het vraagstuk spelen, ( b ) waarom j u i s t j o u w gekozen methodes geschikt zijn v o o r deze problemen, en (c) hoe j e m e t die m e t h o d e s de problemen oplost ( h e t laatste m a g kort, maar m o e t wel inzicht verschaff^en in w a a r o m de m e t h o d e het probleem op kan lossen). (a) (3 p u n t e n ) Een afgevaardigde van de N A S A k o m t bij j e langs m e t het volgende probleem. een w e r e l d w i j d netwerk van satelieten die een vernieuwde versie van GPS m o e t e n opleveren.
Ze willen K e r n is
T I 2 7 3 6 - A - C o m p u t a t i o n a l Intelligence
pagina 2 van 4
5-nov-2014
clat ze de n satelieten zo in een baan o m de aarde willen schieten d a t d i t (a) in d r u k b e w o o n d e gebieden een f i j n m a z i g netwerk geeft, en (b) overal op aarde t e n m i n s t e m i n i m a l e d e k k i n g geeft ( o f te wel, overal op aarde m o e t t e n m i n s t e 3 satelieten meetbaar z i j n ) . Een sateliet kan boven een willekeurig te kiezen breedte en lengtegraad (de locatie) op aarde blijven zweven (ze zijn geostationair).
Hoe los j e d i t op?
(b) (3 p u n t e n ) O m de veiligheid op de weg te garanderen w i l rijkswaterstaat een systeem dat voorspelt hoe druk de snelweg w o r d t als er een rijbaan dichtgezet w o r d t . A l l e snelwegen in Nederland zijn ingedeeld in korte s e g m e n t e n . H e t wegennet is dus een g r o o t netwerk van segmenten. Elk segment heeft een camera die naar een centraal c o m p u t e r systeem loopt. O m te beginnen willen ze precies weten hoeveel autos er op een segment r i j d e n . Hoe los j e d i t op? Daarna willen ze voorspellen o f er file onstaat ( j a / n e e ) door het d i c h t z e t t e n van een rijbaan op een segment.
De voorspelling m o e t op basis van de d r u k t e op d a t
segment alsmede de 5 segmenten ervoor en 5 erna z i j n . Hoe los j e dat op? 7. Binnen C o m p u t a t i o n a l Intelligence kun j e stellen dat exploratie staat voor " z o e k e n " t e r w i j l e x p l o i t a t i e staat voor " h e t u i t b u i t e n van een oplossing met hoge f i t n e s s " . Leg u i t , door gebruik t e maken van parameters in de formules, hoe exploratie en exploitatie t o t u i t i n g komen i n . . . : (a) (2 p u n t e n ) ...de B o l t m a n n ( s o f t - m a x ) actie selectie (bijv. bij Reinforcement Learning). (b) (2 p u n t e n ) ...de standaard f o r m u l e voor een A C O ( A n t Colony O p t i m i z a t i o n ) . (c) (2 p u n t e n ) ...het standaard protocol voor een Evolutionary A l g o r i t h m . ( d ) (2 p u n t e n ) ...de standaard f o r m u l e voor PSO (Partiele S w a r m O p t i m i z a t i o n ) . (e) (2 p u n t e n ) Leg ten s l o t t e in algemene b e w o o r d i n g uit w a t de exploratie-exploitatie t r a d e o f f is, en geef hierbij aan w a a r o m het een t r a d e o f f is, m e t andere w o o r d e n , w a t er gebeurt bij te veel o f te w e i n i g van het een of het ander. 8. Ik kwam van de week t h u i s en had 's morgens een was ingezet. B i j t h u i s k o m s t was de vloer bij de wasmachine weer helemaal nat. O m d a t m i j n wasmachine nog steeds best nieuw is, w i l ik graag weten o f de oorzaak van de plas water k o m t door een k a p o t t e wasmachine of gewoon o m d a t ik het p u t j e weer eens m o e t o n s t o p p e n . De kans op een k a p o t t e wasmachine is in het algemeen klein, z o ' n 0.05, t e r w i j l de kans op een verstopt p u t j e groter is, zo'n 0 . 1 . Als de wasmachine stuk is, dan w o r d t de was meestal o o k niet schoon. Ik schat de kans dat de was schoon is als de wasmachine k a p o t is op ongeveer 0 . 1 , t e r w i j l de kans op schone was bij een goed werkende wasmachine ongeveer 0.9 is. Verder denk ik dus dat er twee mogelijke oorzaken zijn v o o r de plas water: een verstopt p u t j e en een k a p o t t e wasmachine. De kans d a t er een plas water ligt als het p u t j e niet verstopt is en de w a s m a c h i n e wel goed w e r k t is 0 . 0 1 . D a t gebeurt bijna n o o i t . De kans d a t er een plas w a t e r ligt als het p u t j e v e r s t o p t z i t is g r o o t , 0.8, en dat is niet afhankelijk van of de wasmachine nu wel of niet s t u k is. Als alleen de w a s m a c h i n e stuk is, en het p u t j e niet v e r s t o p t , dan schat ik de kans dat er w a t e r l i g t op ongeveer 0.3. Als het p u t j e v e r s t o p t zit, dan hoor ik meestal o o k geborrel, die kans schat ik in op 0.7.
Als
het p u t j e niet v e r s t o p t zit, l<;an er n o g steeds wel geborrel te horen z i j n , maar de kans daarop is beduidend kleiner, ongeveer 0.2. (a) (2 p u n t e n ) T e k e n , aan hand van bovenstaande gegevens, een Bayesiaans netwerk waarmee we k u n n n e n bepalen w a t de oorzaak van de o v e r s t r o m i n g is. W a t zijn de variabelen, w a t zijn de (conditionele) kansen, en hoe lopen de afhankelijkheden? (b) (3 p u n t e n ) Bereken de kans d a t de wasmachine k a p o t is, gegeven d a t we w e t e n dat de vloer nat is. Ik heb nog niet aan de was geroken su ik weet verder niets over o f de was schoon, en o m d a t ik er niet bij was t i j d e n s het wassen weet ik ok niet of er geborrel t e horen was. Laat j e berekening zien. (c) (2 p u n t e n ) Als ik de volgende keer de wasmachine aandoe, dan luister ik eens goed w a t er g e b e u r t . Ik hoor geen geborrel. W a t betekent d i t voor de kans dat de wasmachine k a p o t is, w o r d t deze g r o t e r , kleiner of b l i j f t die gelijk? Leg uit aan de hand van het bayesiaanse netwerk. Je h o e f t niets uit t e rekenen, maar de uitleg m o e t wel V O L L E D I G z i j n , precies kloppen m e t de afhankelijkheden in het netwerk, en j e m o e t gebruik maken van de variabelen en o f ze t r u e of false z i j n / w o r d e n .
5-nov-2014
pagina 3 van 4
T I 2 7 3 6 - A - C o m p u t a t i o n a l Intelligence
9. Consider a Hopfield network where you w a n t t o store t h e f u n d a m e n t a l memories: ' -1
1
'
1
-1 Xi
=
;x2
1
=
(1)
-1 -1
1
(a) ( 1 p u n t ) design t h e Hopfield network t h a t can accomplish t h e task. o u t p u t neurons and t h e n u m b e r o f layers.
Indicate t h e n u m b e r o f i n p u t and
Give a graphical representation o f t h e network, specifying
where t h e i n p u t signals enter t h e network and how t h e neurons are c o n n e c t e d . (b)
(2 p u n t e n ) r e m e m b e r i n g t h a t t h e learning rule for a Hopfield network t h a t needs t o store M f u n d a m e n t a l memories is: M
PF=X:x.xr„^M7
(2)
t r a i n t h e network you desinged at p o i n t (a) t o store t h e f u n d a m e n t a l memories X i and X2. (c)
(1 p u n t )
Use t h e trained network t o retrieve t h e f u n d a m e n t a l memories X i and X2 r e m e m b e r i n g t h a t Y = sign{Wx,n
+ 6)
and
6 = 0
(3)
(d) (2 p u n t e n ) w h a t is a main application f o r Hopfield networks? Show w h e t h e r your t r a i n e d network can he used t o do t h e j o b ( h i n t : flip a bit o f X2 and test your network on i t ) . (e) ( 1 p u n t ) w h a t is t h e main l i m i t a t i o n o f Hopfield networks? 10. A care h o m e needs t o plan in advance t h e holiday schedule o f its employees for t h e Christmas break, w h i c h lasts for 3 weeks around Christmas. T h e r e are 8 nurses w o r k i n g in t h e care h o m e , each nurse works 5 days a week, and each o f t h e m wants t o go on holidays for either one or t w o weeks. If a nurse goes on holidays for 2 weeks, these t w o have t o be consecutive. T h e main concern o f t h e care h o m e is t h a t there should always be a 2 4 hour coverage every d a y A l t h o u g h each nurse works 5 days a week, t h e y w o r k in shifts and t h e i r shifts are not o f equal l e n g t h . Each nurse can cover a t most one shift per day, and there is no need t o have overlap between t h e nurses shifts ( t h a t is, when one starts t h e shift, t h e other can f i n i s h ) . So, w h a t t h e care home w a n t s , is t o schedule t h e holidays o f t h e nurses so t h a t every week t h e r e m a i n i n g nurses can cover w i t h t h e i r shifts at least 24 hours per day. A n o t h e r way t o p u t it is t h a t t h e s u m o f t h e length o f t h e shifts per day of t h e nurses t h a t are n o t on holiday should be equal or greater t h a n 24 (and more is b e t t e r t o cover emergencies). K n o w i n g t h a t t h e nurses have different w o r k i n g s h i f t lengths, and request t h e a m o u n t o f holidays indicated in t h e t a b l e below:
nurse
N u m b e r o f weeks o f holidays requested
N u m b e r o f worked hours per s h i f t
1
1
4
2
1
8
3
2
8
4
2
4
5
1
4
6
2
8
7
1
8
1
6
8
Use an e v o l u t i o n a r y c o m p u t a t i o n m e t h o d t o f i n d t h e schedule t h a t ( 1 ) allows all nurses t o go on holidays and (2) maximises t h e t i m e covered by t h e shifts o f t h e available nurses In particular: (a) ( 1 p u n t )
Indicate w h e t h e r you w o u l d use a Genetic A l g o r i t h m or an E v o l u t i o n a r y s t r a t e g y t o do t h e j o b ,
and m o t i v a t e your answer. (b) (1 punt)
Describe how you w o u l d encode your c a n d i d a t e solutions i n t o a c h r o m o s o m e , also s p e c i f y i n g
T I 2 7 3 6 - A - C o m p u t a t i o n a l Intelligence
pagina 4 van 4
5-nov-2014
w h a t each gene represents. Schemes are welcome. Please j u s t i f y your choices. (c) ( 1 p u n t ) Describe how you w o u l d initialize the p o p u l a t i o n (d) ( 1 p u n t ) Define the fitness f u n c t i o n (e) ( 1 p u n t ) Describe your selection scheme ( f ) ( 1 p u n t ) Describe genetic operators, t a k i n g care of a d a p t i n g t h e i r f u n c t i o n i n g t o this specific p r o b l e m , if necessary ( g ) ( 1 p u n t ) Indicate w h e n / w h y t h e a l g o r i t h m will t e r m i n a t e .
Einde t e n t a m e n o p g a v e n . Controleer voor de zekerheid of j e alle vragen hebt b e a n t w o o r d . H e t zouden er 10 moeten z i j n .
