K a t e d r a
P o d s t a w
K o n s t r u k c j i
M a s z y n
W y d z i a B
M e c h a n i c z n y
T e c h n o l o g i c z n y
M e t o d y S z t u c z n e j
P o l i t e c h n i k a
I n t e l i g e n c j i
Zl s k a
R o k a k a d e m i c k i 2 0 0 8 / 0 9
I n s t r u k c j a d o w i c z e D l a b o r a t o r y j n y c h
T e m a t
A l g o r y t m y g e n e t y c z n e
O p r a c o w a B: d r i n |. G . U r b a n e k
u l . K o n a r s k i e g o 1 8 a
4 4 - 1 0 0 G l i w i c e
t e l . 2 3 7 1 4 6 7
f a x . 2 3 7 1 3 6 0
h t t p : / / k p k m . p o l s l . p l
- 1 / 6 -
1 . C e l w i c z e n i a
C e l e m w i c z e n i a j e s t z a p o z n a n i e s i z a l g o r y t m a m i g e n e t y c z n y m i o r a z z i c h p r a k t y c z n y m
z a s t o s o w a n i e m .
2 . W p r o w a d z e n i e t e o r e t y c z n e
P o s z u k i w a n i e r o z w i z a n i a o p t y m a l n e g o w e d Bu g a l g o r y t m u g e n e t y c z n e g o o d b y w a s i p o p r z e z
o d p o w i e d n i e p r z e k s z t a Bc a n i e z b i o r u e l e m e n t w ( o s o b n i k w ) z a p o m o c t z w . o p e r a t o r w g e -
n e t y c z n y c h . Z b i r e l e m e n t w ( o s o b n i k w ) w d a n e j c h w i l i c z a s u n a z y w a n y j e s t p o k o l e n i e m ,
z b i r t e n p r z e k s z t a Bc o n y z a p o m o c o p e r a t o r w g e n e t y c z n y c h s t a n o w i k o l e j n e p o k o l e n i e ; p r z e -
k s z t a Bc e n i e t a k i e w y k o n u j e s i n - r a z y . E l e m e n t y ( o s o b n i c y ) p r z e k s z t a Bc a n e g o z b i o r u n a l e |
d o p r z e s t r z e n i z a d a n i a i s p o t e n c j a l n y m i r o z w i z a n i a m i . K a |d y e l e m e n t ( o s o b n i k ) z a w i e r a
i n f o r m a c j s t a n o w i c j e g o g e n o t y p , k t r y j e s t p r z e p i s e m n a u t w o r z e n i e w w y n i k u o d d z i a By w a -
n i a [r o d o w i s k a f e n o t y p u , c z y l i z b i o r u c e c h , n a p o d s t a w i e k t r y c h f u n k c j a o c e n i a j c a ( f u n k c j a
p r z y s t o s o w a n i a ) , o k r e [l a p r z y s t o s o w a n i e o s o b n i k a . C e l e m a l g o r y t m u g e n e t y c z n e g o j e s t m a k -
s y m a l i z a c j a f u n k c j i p r z y s t o s o w a n i a , t z n . r o z w i z a n i e m o p t y m a l n y m j e s t o s o b n i k o n a j w i k s z e j
w a r t o [c i f u n k c j i p r z y s t o s o w a n i a .
G e n o t y p o s o b n i k a s k Ba d a s i z c h r o m o s o m w ( n a j c z [c i e j j e d n e g o ) , k t r e s k Ba d a j s i z
e l e m e n t a r n y c h c z [c i , z w a n y c h g e n a m i . P r z y k Ba d o w o , w z a d a n i u o p t y m a l i z a c j i ( p o s z u k i w a n i u
m a k s i m u m ) f u n k c j i f , g e n o t y p e m o s o b n i k a s w s p Br z d n e p u n k t u , f e n o t y p e m j e s t w a r t o [
f u n k c j i f w t y m p u n k c i e . W a r t o [ f u n k c j i p r z y s t o s o w a n i a j e s t w y l i c z a n a n a p o d s t a w i e f e n o t y p u .
I s t o t d z i a Ba n i a a l g o r y t m u g e n e t y c z n e g o p r z e d s t a w i a r y s . 1 .
P r z e p r o w a d z e n i e o p t y m a l i z a c j i z a p o m o c a l g o r y t m u g e n e t y c z n e g o w y m a g a o k r e [l e n i a n a -
s t p u j c y c h e l e m e n t w :
R y s . 1 : P o d s t a w o w y a l g o r y t m g e n e t y c z n y ; o z n a c z e n i a : t c z a s ( l i c z n i k k r o k w ) , P p o p u l a c j a ,
R r o d z i c e , D d z i e c i [ 5 ] , [ 3 ]
- 2 / 6 -
" p o d s t a w o w e j r e p r e z e n t a c j i p o t e n c j a l n y c h r o z w i z a D z a d a n i a ,
" s p o s o b u t w o r z e n i a p o c z t k o w e j p o p u l a c j i p o t e n c j a l n y c h r o z w i z a D,
" f u n k c j i o c e n i a j c e j ,
" s p o s o b u p r o w a d z e n i a s e l e k c j i i s u k c e s j i ,
" s p o s o b u p r o w a d z e n i a r e p r o d u k c j i ( o p e r a t o r y k r z y |o w a n i a i m u t a c j i ) ,
" w a r t o [c i r |n y c h p a r a m e t r w u |y w a n y c h w a l g o r y t m i e g e n e t y c z n y m ( r o z m i a r p o p u l a c j i ,
p r a w d o p o d o b i e Ds t w a u |y c i a o p e r a t o r w g e n e t y c z n y c h i t p . ) .
2 . 1 . R e p r e z e n t a c j a p o t e n c j a l n y c h r o z w i z a D z a d a n i a
M e t o d y r e p r e z e n t a c j i e l e m e n t w p r z e s t r z e n i ( n a z y w a n y c h o s o b n i k a m i ) , w k t r e j p o s z u k i w a n e
j e s t r o z w i z a n i e o p t y m a l n e m o |n a p o d z i e l i n a d w i e g r u p y [ 3 ] :
1 . c h r o m o s o m y z l i n i o w o u Bo |o n y m i g e n a m i :
" k o d o w a n i e b i n a r n e ,
" k o d o w a n i e l i c z b o w e ,
" k o d o w a n i e s p e c j a l n e ,
2 . c h r o m o s o m y b d c e z Bo |o n y m i s t r u k t u r a m i g e n w ( n p . d r z e w a )
" k o d o w a n i e b i n a r n e , l i c z b o w e , s p e c j a l n e .
P o w s z e c h n i e w a l g o r y t m a c h g e n e t y c z n y c h s t o s o w a n e s c h r o m o s o m y z l i n i o w o u Bo |o n y -
m i g e n a m i k o d o w a n y m i b i n a r n i e . W a r t o [c i w s z y s t k i c h c e c h ( g e n y ) k a |d e g o o s o b n i k a z o s t a j
p r z e d s t a w i o n e z a p o m o c l i c z b d w j k o w y c h ; s k l e j o n e r a z e m s t a n o w i c h r o m o s o m . R e p r e -
z e n t a c j a t a u Ba t w i a a n a l i z t e o r e t y c z n i u m o |l i w i a w p r o w a d z e n i e b a r d z o p r o s t y c h o p e r a t o r w
g e n e t y c z n y c h . G B w n j e j w a d j e s t b a r d z o d u |a d Bu g o [ c h r o m o s o m u d l a w i e l o w y m i a r o w y c h
z a d a D w y m a g a j c y c h d u |e j d o k Ba d n o [c i , c o p r o w a d z i d o b a r d z o d u |e j l i c z e b n o [c i p r z e s t r z e n i
p r z e s z u k i w a n i a [ 5 ] .
I n n y m s p o s o b e m j e s t z a p i s w a r t o [c i c e c h ( g e n w ) w p o s t a c i d z i e s i t n e j . C h r o m o s o m m a
w t e d y p o s t a m a c i e r z y l i c z b , k a |d a l i c z b a j e s t w a r t o [c i j e d n e j z r o z p a t r y w a n y c h c e c h . T a k i
z a p i s e l i m i n u j e k o n i e c z n o [ k o d o w a n i a c h r o m o s o m w ( p r z e s t r z e D r e p r e z e n t a c j i j e s t p r z e s t r z e -
n i z a d a n i a ) . S t o s o w a n i e c h r o m o s o m w , b d c y c h z Bo |o n y m i s t r u k t u r a m i g e n w , w y m a g a
o p r a c o w a n i a o d p o w i e d n i c h o p e r a t o r w g e n e t y c z n y c h .
2 . 2 . G e n e r o w a n i e r o z w i z a n i a p o c z t k o w e g o
P o p u l a c j a p o c z t k o w a n a j c z [c i e j ( c h y b a |e s u z a s a d n i o n e p o d s t a w y , |e b y p o s t p i i n a c z e j )
g e n e r o w a n a j e s t w s p o s b l o s o w y . W p r z y p a d k u k o d o w a n i a b i n a r n e g o l o s u j e s i w a r t o [ k a |d e g o
b i t u c h r o m o s o m u ( Ba Dc u c h a b i n a r n e g o ) i w t e n s p o s b t w o r z y s i c a B p o p u l a c j . W p r z y p a d k u
- 3 / 6 -
k o d o w a n i a l i c z b o w e g o , w a r t o [ k a |d e g o g e n u j e s t l o s o w a n a z p r z e d z i a Bu z m i e n n o [c i w a r t o [c i
c e c h y , k t r o n r e p r e z e n t u j e .
2 . 3 . F u n k c j a o c e n i a j c a
F u n k c j a o c e n i a j c a j e s t j e d n y m z n a j w a |n i e j s z y c h e l e m e n t w w a r u n k u j c y c h s k u t e c z n e d z i a Ba -
n i e a l g o r y t m u g e n e t y c z n e g o . N i e o d p o w i e d n i a f u n k c j a o c e n i a j c a p r o w a d z i d o b Bd n e g o d z i a Ba -
n i a . N i e s t e t y , n i e i s t n i e j e o g l n y p r z e p i s n a o p r a c o w a n i e d o b r e j f u n k c j i o c e n i a j c e j . F u n k c j
t a k z w y k l e w y z n a c z a s i m e t o d p r b i b Bd w i n d y w i d u a l n i e d o k o n k r e t n e g o z a d a n i a .
2 . 4 . S e l e k c j a i s u k c e s j a
S e l e k c j a o k r e [l a s p o s b w y Ba n i a n i a z r o z p a t r y w a n e j p o p u l a c j i z b i o r u r o d z i c w , k t r y p o d d a w a n y
d z i a Ba n i u o p e r a c j i g e n e t y c z n y c h , d a j e z b i r d z i e c i . S u k c e s j a w y z n a c z a d l a p o k o l e n i a r o d z i c w
i p o t o m k w n o w p o p u l a c j b a z o w d l a k o l e j n e g o k r o k u a l g o r y t m u g e n e t y c z n e g o .
P r z y k Ba d y m e t o d s e l e k c j i :
" s e l e k c j a p r o p o r c j o n a l n a , z w a n a r w n i e | m e t o d r u l e t k i ( n a z w a p o c h o d z i o d n a j p r o s t s z e j
r e a l i z a c j i a l g o r y t m i c z n e j t e g o o p e r a t o r a ) , j e s t p r o c e s e m , w k t r y m c h r o m o s o m y z o s t a j
p o w i e l o n e w s t o s u n k u z a l e |n y m ( w p r o s t p r o p o r c j o n a l n i e ) o d w a r t o [c i , j a k i e p r z y b i e r a d l a
n i c h f u n k c j a o c e n i a j c a ; s t o s o w a n i e t e j m e t o d y j e s t m o |l i w e t y l k o w t e d y , g d y f u n k c j a
o c e n i a j c a p r z y j m u j e w y Bc z n i e w a r t o [c i d o d a t n i e ;
" s e l e k c j a t u r n i e j o w a p o l e g a n a p o w t a r z a n i u d w c h k r o k w : l o s o w a n i a p a r o s o b n i k w w g
m e t o d y r u l e t k i , p o w y l o s o w a n i u p a r y , o s o b n i k o w y |s z y m p r z y s t o s o w a n i u z o s t a j e o g Bo -
s z o n y z w y c i z c i u m i e s z c z o n y w n o w e j p o p u l a c j i ; p r o c e s j e s t k o n t y n u o w a n y a | d o c a B-
k o w i t e g o w y p e Bn i e n i a p o p u l a c j i .
P r z y k Ba d y m e t o d s u k c e s j i :
" s u k c e s j a t r y w i a l n a p o l e g a n a t y m , |e n o w p o p u l a c j s t a j e s i z b i r d z i e c i : P [ t ] : = D [ t ] ;
" s u k c e s j a e l i t a r n a p r z e p r o w a d z a n a j e s t w d w c h k r o k a c h : n a j p i e r w w y b i e r a s i z P [ t - 1 ]
n n a j l e p s z y c h c h r o m o s o m w : P n [ t - 1 ] , n a s t p n i e p o p u l a c j a P [ t ] j e s t t w o r z o n a p r z e z
w y b r m n a j l e p s z y c h c h r o m o s o m w z e z Bc z e n i a P n [ t - 1 ] *"[ t ] .
2 . 5 . R e p r o d u k c j a
N a r e p r o d u k c j s k Ba d a j s i d w a o p e r a t o r y : k r z y |o w a n i a i m u t a c j i .
N a j c z [c i e j p r z y j m u j e s i , |e w k r z y |o w a n i u b i o r u d z i a B d w a o s o b n i k i r o d z i c i e l s k i e , w w y -
n i k u o t r z y m u j e s i j e d e n l u b d w a o s o b n i k i p o t o m n e .
P r z y k Ba d y m e t o d k r z y |o w a n i a :
" k r z y |o w a n i e p r o s t e ( j e d n o p u n k t o w e ) p r z e b i e g a w d w c h e t a p a c h : w p i e r w s z e j f a z i e k o j a -
r z y s i w s p o s b l o s o w y c i g i z p u l i r o d z i c i e l s k i e j w p a r y . N a s t p n i e k a |d a p a r a p r z e c h o d z i
- 4 / 6 -
p r o c e s k r z y |o w a n i a . O d b y w a s i t o n a s t p u j c o : w y b i e r a s i w s p o s b l o s o w y ( z j e d n a k o -
w y m p r a w d o p o d o b i e Ds t w e m ) p u n k t k r z y |o w a n i a k s p o [r d l - 1 p o c z t k o w y c h p o z y c j i
w c h r o m o s o m i e , p o c z y m z a m i e n i a s i m i e j s c a m i w s z y s t k i e z n a k i o d p o z y c j i k + 1 d o
l w Bc z n i e w o b u e l e m e n t a c h p a r y , t w o r z c w t e n s p o s b d w a n o w e c i g i ;
" k r z y |o w a n i e w i e l o p u n k t o w e p r z e b i e g a a n a l o g i c z n i e j a k k r z y |o w a n i e j e d n o p u n k t o w e , z t
r |n i c , |e w y b i e r a s i w i c e j n i | j e d e n p u n k t c i c i a ;
" k r z y |o w a n i e j e d n o r o d n e p r z e b i e g a n a s t p u j c o : d l a k a |d e g o b i t u p i e r w s z e g o p o t o m k a
d e c y d u j e s i ( z p e w n y m p r a w d o p o d o b i e Ds t w e m ) , o d k t r e g o z r o d z i c w p o b i e r z e s i
w a r t o [, d r u g i p o t o m e k o t r z y m u j e b i t o d p o z o s t a Be g o r o d z i c a ;
" r e k o m b i n a c j a p u l i g e n w : k i l k u r o d z i c w t w o r z y j e d n e g o p o t o m k a w t e n s p o s b , |e
k o l e j n e g e n y p o t o m k a s w y b i e r a n e l o s o w o z p u l i g e n w w y b r a n y c h r o d z i c w ;
" k r z y |o w a n i e a r y t m e t y c z n e d e f i n i u j e s i j a k o l i n i o w k o m b i n a c j d w c h w e k t o r w : j e |e l i
k r z y |o w a n i u m a j p o d l e g a r 1 i r 2 , t o p o t o m k o w i e w y z n a c z a n i s n a s t p u j c o : d 1 =
a r 1 + ( 1 - a ) r 2 o r a z d 2 = a r 2 + ( 1 - a ) r 1 ; w a r t o [ a d o b i e r a s i l o s o w o z p r z e d z i a Bu
[ 0 , 1 ] ;
" k r z y |o w a n i e u [r e d n i a j c e j e s t o p e r a t o r e m p r z e z n a c z o n y m d l a r e p r e z e n t a c j i l i c z b o w e j ;
w m e t o d z i e t e j w a r t o [ k a |d e g o g e n u c h r o m o s o m u p o t o m n e g o j e s t l i c z b z a w i e r a j c
s i m i d z y n a j w i k s z i n a j m n i e j s z w a r t o [c i g e n u c h r o m o s o m w r o d z i c i e l s k i c h . J e [l i
k r z y |o w a n i e u [r e d n i a j c e p r z e b i e g a z g o d n i e z e s c h e m a t e m , |e z p a r y c h r o m o s o m w r o -
d z i c i e l s k i c h p o w s t a j e p a r a p o t o m n y c h , w w c z a s c h r o m o s o m y p o t o m n e b d s y m e t r y c z n e
w z g l d e m [r o d k a o d c i n k a Bc z c e g o c h r o m o s o m y r o d z i c i e l s k i e .
P r z y k Ba d y m e t o d m u t a c j i :
" m u t a c j a r w n o m i e r n a z m i e n i a j e d e n l u b w i c e j b i t w n a p r z e c i w n y z o k r e [l o n y m p r a w -
d o p o d o b i e Ds t w e m ;
" m u t a c j a n i e r w n o m i e r n a u w z g l d n i a w i e k p o p u l a c j i : w r a z z e w z r o s t e m w i e k u p o p u l a c j i
b i t y z n a j d u j c e s i b a r d z i e j n a p r a w o w s e k w e n c j i k o d u c h r o m o s o m u o t r z y m u j w i k s z e
p r a w d o p o d o b i e Ds t w o m u t a c j i , z n a j d u j c e s i z a [ n a l e w o m n i e j s z e ;
" m u t a c j a r z e c z y w i s t o l i c z b o w a s t o s o w a n a j e s t w t e d y , j e [l i g e n y p r z y j m u j w a r t o [c i z e
z b i o r u l i c z b r z e c z y w i s t y c h , i p o l e g a n a p e r t u r b a c j i w a r t o [c i g e n u p r z e z d o d a n i e l i c z b y
w y g e n e r o w a n e j w s p o s b l o s o w y .
2 . 6 . W a r u n k i z a k o Dc z e n i a d z i a Ba n i a a l g o r y t m u g e n e t y c z n e g o
M o |n a o k r e [l i d w a w a r u n k i z a k o Dc z e n i a d z i a Ba n i a a l g o r y t m u g e n e t y c z n e g o :
" a l g o r y t m d z i a Ba d o m o m e n t u o s i g n i c i a o s o b n i k a o o k r e [l o n y m p r z y s t o s o w a n i u ,
" p t l a w h i l e j e s t w y k o n y w a n a z a d a n l i c z b r a z y .
N a j c z [c i e j s t o s u j e s i o b y d w a w a r u n k i j e d n o c z e [n i e . A l g o r y t m k o Dc z y d z i a Ba n i a , g d y z o -
s t a n i e s p e Bn i o n y j e d e n z n i c h .
- 5 / 6 -
2 . 7 . P a r a m e t r y a l g o r y t m u g e n e t y c z n e g o
T r a d y c y j n i e a l g o r y t m y g e n e t y c z n e , o p e r u j n a p o p u l a c j i , k t r e j l i c z e b n o [ w c z a s i e o p t y m a l i z a -
c j i n i e z m i e n i a s i . M o |n a z a s t o s o w a a l g o r y t m g e n e t y c z n y z e z m i e n n l i c z e b n o [c i p o p u l a c j i .
A l g o r y t m t e n n i e z a w i e r a |a d n e j o d m i a n y m e c h a n i z m u s e l e k c j i , a l e w p r o w a d z a p o j c i e w i e k u
c h r o m o s o m u , c o j e s t r w n o w a |n e l i c z b i e p o k o l e D, p r z e z k t r e c h r o m o s o m p o z o s t a j e |y w y .
T a k w i c w i e k c h r o m o s o m u p o z w a l a n a s z c z e g l n e d e f i n i o w a n i e p o j c i a s e l e k c j i i , p o n i e w a |
z a l e |y o n o d d o p a s o w a n i a o s o b n i k a , w p By w a n a l i c z e b n o [ p o p u l a c j i w k a |d y m k r o k u p r o c e -
s u [ 5 ] .
N i e m a z a l e c e D c o d o d o b o r u w a r t o [c i p r a w d o p o d o b i e Ds t w a k r z y |o w a n i a i m u t a c j i , n a j c z -
[c i e j d o k o n u j e s i t e g o d o [w i a d c z a l n i e . Z w y k l e p r a w d o p o d o b i e Ds t w o k r z y |o w a n i a z a w i e r a s i
w p r z e d z i a l e [ 0 , 2 5 ; 0 , 7 5 ] , z a [ p r a w d o p o d o b i e Ds t w o m u t a c j i w p r z e d z i a l e [ 0 , 0 0 5 ; 0 , 0 5 ] .
3 . P r z y g o t o w a n i e d o w i c z e n i a
P r z y g o t o w a n i e d o w i c z e n i a o b e j m u j e s z c z e g Bo w e z a p o z n a n i e s i z n i n i e j s z i n s t r u k c j . W c z a -
s i e w i c z e n i a z o s t a n i e p r z e d s t a w i o n e , n a p r o s t y m p r z y k Ba d z i e , d z i a Ba n i e a l g o r y t m u g e n e t y c z -
n e g o ; z o s t a n i e s p r a w d z o n e p r z y g o t o w a n i e s t u d e n t w d o z a j .
4 . P r z y k Ba d y d o s a m o d z i e l n e g o r o z w i z a n i a
O p r a c o w a a l g o r y t m g e n e t y c z n y d o o p t y m a l i z a c j i f u n k c j i d w c h z m i e n n y c h . Z a s t o s o w a k o -
d o w a n i e l i c z b o w e z l i n i o w o u Bo |o n y m i g e n a m i w c h r o m o s o m i e .
L i t e r a t u r a
[ 1 ] A r a b a s J . : A l g o r y t m y e w o l u c y j n e : p r z e g l d t e m a t y k i . A I - M e c h 2 0 0 0 , M a t e r i a By k o n f e r e n -
c y j n e , G l i w i c e 2 0 0 0 , s . 3 2 3 .
[ 2 ] A r a b a s J . : W y k Ba d y z a l g o r y t m w g e n e t y c z n y c h . W N T , W a r s z a w a , 2 0 0 1 .
[ 3 ] C h o l e w a W . : W y k Ba d z p r z e d m i o t u m e t o d y h e u r y s t y c z n e . M a t e r i a By n i e p u b l i k o w a n e ,
G l i w i c e , 2 0 0 1 .
[ 4 ] G o l d b e r g D . E . : A l g o r y t m y g e n e t y c z n e i i c h z a s t o s o w a n i a . W N T , W a r s z a w a , 1 9 9 8 .
[ 5 ] M i c h a l e w i c z Z . : A l g o r y t m y g e n e t y c z n e + s t r u k t u r y d a n y c h = p r o g r a m y e w o l u c y j n e .
W N T , W a r s z a w a , 1 9 9 9 .
- 6 / 6 -
Wyszukiwarka
Podobne podstrony:
Algorytmy genetyczne a logika rozmytaAlgorytmy genetyczne i procesy ewolucyjne Wykład 203 Implementacja komputerowa algorytmu genetycznegoAlgorytm genetyczny – przykład zastosowaniaAlgorytmy genetyczne i procesy ewolucyjne Wykład 402 Podstawy matematyczne algorytmów genetycznychAlgorytmy genetyczne i procesy ewolucyjne Wykład 1klasyczny algorytm genetycznyAlgorytmy GenetyczneEA5 Algorytmy genetyczneALGORYTMY GENETYCZNE DO MINIMALIZACJI RYZYKA ZAWODOWEGO ZWIĄZANEGO Z EKSPOZYCJA NA HAŁASalgorytmy genetyczne i mrówkowe w transporcieAlgorytm Genetyczny wynikalgorytmy genetyczne 204 Niektóre zastosowania algorytmów genetycznychAlgorytmy genetyczne i procesy ewolucyjne Wykład 3t5 algorytmy genetycznewięcej podobnych podstron