Programowanie Mrowiskowe z gramatyką

Mariusz Boryczka

(

[e-mail])

Instytut Informatyki, Zakład Systemów Informatycznych

11 kwietnia 2006

Problemy:

•

Gramatyki

•

Programowanie Genetyczne z gramatyką

•

Programowanie Mrowiskowe z gramatyką

•

Eksperymenty

•

Wnioski

Gramatyka (ogólnie)

Gramatyką formalną nazywamy sposób opisu języka formalnego,
czyli podzbioru zbioru wszystkich słów skończonej długości nad
danym alfabetem. Aby zdefiniować gramatykę formalną trzeba
określić:

•

zbiór symboli terminalnych,

•

zbiór symboli nieterminalnych,

•

zbiór reguł (produkcji) które określają sposób, w jaki
wyprowadzamy słowa,

•

symbol startowy.

Symbole terminalne (równoważne symbolom alfabetu języka) są
symbolami, które pozostaną w wyprowadzonym słowie — w
przeciwieństwie do symboli nieterminalnych używanych tylko
podczas wyprowadzania słowa. Reguły gramatyki postaci S

1

→

S

2

,

gdzie S

1

i S

2

to ciągi symboli terminalnych i nieterminalnych,

określają możliwe podstawienia symboli w wyprowadzanym słowie.

Gramatyka (formalnie)

Gramatyką formalną (gramatyką generacyjną) nazywamy czwórkę:

G

= hΣ, V , S, Pi,

gdzie

Σ i V są dwoma rozłącznymi alfabetami (Σ ∩ V = ∅) oraz

•

Σ jest alfabetem terminalnym,

•

V jest alfabetem nieterminalnym,

•

P jest skończonym zbiorem produkcji, tj. par słów
u

, w ∈ (Σ ∪ V )

∗

zapisywanych w postaci u → w , gdzie słowo u

zawiera co najmniej jeden symbol nieterminalny,

•

S jest wyróżnionym symbolem nieterminalnym, zwanym
symbolem startowym.

Gramatyka (formalnie) - c.d.

Na zbiorze słów nad alfabetem

Σ ∪ V wprowadzamy binarną relację

⇒

G

, zwaną relacją wyprowadzenia w jednym kroku albo relacją

bezpośredniego wyprowadzenia (z gramatyki G ):

uxw ⇒

G

uyw ⇐⇒ (x → y ) ∈ P;

u

, w, x, y ∈ (Σ ∪ V )

∗

Relacja wyprowadzenia

∗

⇒

G

jest zwrotnym i przechodnim

domknięciem relacji bezpośredniego wyprowadzenia, tj. jest
najmniejszą zwrotną i przechodnią relacją binarną na słowach ze
zbioru (

Σ ∪ V )

∗

zawierającą relację ⇒

G

.

Wyprowadzeniem słowa w ze słowa u w gramatyce G nazywamy
ciąg słów u

0

, . . . , u

n

∈

(

Σ ∪ V )

∗

, taki że u

0

= u, u

n

= w, oraz

u

(i −1)

⇒

G

u

i

dla i

= 1, . . . , n. Wyprowadzeniem słowa w z

gramatyki G nazywamy jego wyprowadzenie z symbolu startowego
S tej gramatyki.

Język

Język generowany przez gramatykę G , L(G ), jest zbiorem słów
terminalnych wyprowadzalnych z symbolu startowego S :

L

(G )

= {w ∈ Σ

∗

|

S

∗

⇒

G

w }

Podział gramatyk

Wśród gramatyk formalnych Chomsky wyróżnił pewne klasy
nakładając na postać produkcji gramatyki dodatkowe warunki:

•

Gramatyki struktur frazowych (typu 0): nie nakłada się żadnych
warunków na postać gramatyki. Jeśli dla danego języka istnieje
gramatyka struktur frazowych, która go generuje, język ten
nazywa się rekurencyjnie przeliczalnym. Wszystkich języków
(wszystkich podzbiorów

Σ

∗

) jest kontinuum, gramatyk zaś

przeliczalnie wiele. Istnieją zatem języki, które nie są
rekurencyjnie przeliczalne.

Podział gramatyk (c.d.)

•

Gramatyki kontekstowe (typu 1): każda produkcja ma postać:

uAw → uxw

, gdzie u, x, w ∈ (Σ ∪ V )

∗

, A ∈ V , oraz x 6= 

Żaden język generowany przez taką gramatykę nie zawierałby
słowa pustego  . Dlatego dopuszczamy dodatkowo jeden
wyjątek: gramatyka może zawierać produkcję

S →



ale wówczas S nie może wystąpić po prawej stronie żadnej
produkcji tej gramatyki. Jeśli dla danego języka istnieje
gramatyka kontekstowa, która go generuje, język ten nazywa
się językiem kontekstowym.

Podział gramatyk (c.d.)

•

Gramatyki bezkontekstowe (typu 2): każda produkcja
gramatyki ma postać:

A → x

, gdzie A ∈ V , zaś x ∈ (Σ ∪ V )

∗

Jeśli dla danego języka istnieje gramatyka bezkontekstowa,
która go generuje, język ten nazywa się językiem
bezkontekstowym.

Podział gramatyk (c.d.)

•

Gramatyki regularne (typu 3): każda produkcja gramatyki ma
postać:

A → xB lub A → x ,

gdzie A, B ∈ V , zaś x ∈

Σ

∗

Jeśli dla danego języka istnieje gramatyka regularna, która go
generuje, język ten nazywa się językiem regularnym.

Przykład

Gramatyka generująca proste wyrażenia arytmetyczne

G

= h{1, x, y, z, (, )}, {W , S, C, A}, P, W i

gdzie zbiór produkcji P jest następujący:

W

→

W

+ S |

W

−

S

|

S

S

→

S

∗

C

|

S

/

C

|

C

C

→

A

|

(

W

)

A

→

1

|

x

|

y

|

z

za pomocą której można zbudować wyrażenia:

(x

+ 1)/z

(x

+ 1) ∗ (y/z)

x ∗ y

/z

. . .

Przykład (c.d.)

wyrażenie: (x

+ 1)/z

W ⇒ S

W

→

S

⇒

S

/

C

S

→

S

/

C

⇒

C

/

C

S

→

C

⇒

(

W

)

/

C

C

→

(

W

)

⇒

(

W

+ S )

/ C

W

→

W

+

S

⇒

(

S

+ S )

/ C

W

→

W

⇒

(

C

+ S )

/ C

S

→

C

⇒

(

A

+ S )

/ C

C

→

A

⇒

(

x

+ S )

/ C

A

→

x

⇒

(

x

+ C )

/ C

S

→

C

⇒

(

x

+ A )

/ C

C

→

A

⇒

(

x

+ 1 )

/ C

A

→

1

⇒

(

x

+ 1 )

/ A

C

→

A

⇒

(

x

+ 1 )

/ z

A

→

z

Programowanie Genetyczne z gramatyką (GGGP)

Gramatyka:

Przekształcenie genotyp – fenotyp:

Programowanie Mrowiskowe – podejście operatorowe

W ACP z podejściem operatorowym wykorzystuje się zapis prefiksowy wyrażeń
arytmetycznych. W zależności od przyjętej wersji algorytmu stosuje się listę TABU lub
dopuszcza się wielokrotne wykorzystywanie tego samego węzła grafu w tworzonym
wyrażeniu. Dostosowane elementy Systemu Mrowiskowego:

1.

Graf (N, E):

•

N — zbiór symboli terminalnych, operatorów i funkcji (TOF),

•

E — krawędzie reprezentujące połączenia między sąsiednimi elementami
wyrażenia w zapisie prefiksowym.

2.

Prawdopodobieństwo przejścia mrówki k z węzła r do węzła s w chwili t:

p

k

rs

(t)

=

τ

rs

(t) · [

γ

rs

]

β

P

i ∈J

[

τ

ri

(t)] · [

γ

ri

]

β

γ = F (

MOCs

,

długość wyrażenia

)

=

1

2

+

MOCs

!

długość wyrażenia

gdzie MOC

s

jest mocą TOF

s

, wartością związaną z liczbą jego argumentów, a zbiór J

zawiera wszystkie węzły grafu (wersja bez listy TABU) lub węzły dotychczas nieodwiedzone

(wersja z listą TABU).

Programowanie Mrowiskowe – podejście operatorowe

(c.d.)

Mocy wyrażenia wykorzystuje moc (arity) operatorów, funkcji i argumentów (TOF):

TOF

l. argumentów

MOC

stała, x

0

-1

NOT, NEG, funkcje 1–arg.

1

0

+, −, ∗, /, AND, OR, XOR

2

1

Wyrażenie tworzone przez każdą mrówkę jest inicjowane symbolem F odpowiadającym
węzłowi startowemu i otrzymuje początkową wartość mocy równą 1. Dołączenie do
wyrażenia kolejnego TOF powoduje dodanie do mocy wyrażenia wartości równej mocy tego
TOF. Wyrażenie zostaje zamknięte, gdy jego moc jest równa 0:

+1

F

+

x

+

1

1

-1

+1

-1

-1

1

2

1

2

1

0

MOC WYR.:

MOC OPA:

Tak zaprojektowany algorytm generuje poprawne wyrażenia w notacji prefiksowej, np:

/ - + + 10 x * + * x * 1 * 1 - 10 1 2 1 2 + * x x * 2 1 → y

= 10 ·

x

+1

x

2

+2

Programowanie Mrowiskowe z gramatyką

Przyjęte założenia:

•

Zastosowano podejście oparte na wersji operatorowej bez listy TABU.

•

Węzły grafu stanowią produkcje zadanej gramatyki bezkontekstowej.

•

Moc wyrażenia została zastąpiona liczbą nierozwiniętych symboli
nieterminalnych w generowanym wyrażeniu (słowie), a moc TOF –
liczbą symboli nieterminalnych w produkcji.

•

Nowa wartość współczynnika γ:

γ = F (

LSN

s

,

długość wyrażenia

)

=

1

1

+

LSN

s

!

długość wyrażenia

(LSN – liczba symboli nieterminalnych)

•

Reguła przejścia mrówki została uzupełniona o warunek losowania
jedynie spośród produkcji rozwijających symbole nieterminalne
zawarte w aktualnej postaci generowanego wyrażenia.

•

Określono nowy warunek stopu: LSN = 0.

Eksperymenty

•

Prosta funkcja dwu zmiennych:

f (x

, y) = x

3

+ 2y

dla 26 par x , y ∈ h−25; 25i
Produkcje:

W

→

W

+ S

|

W

−

S

|

S

S

→

S

∗

C

|

S

/

C

|

S

↑

C

|

C

C

→

A

|

(

W

)

|

−

C

A

→

1

|

. . .

|

9

|

x

|

y

Parametry:

•

l. mrówek = 500,

•

τ

0

= 0.7,

•

q

0

= 0.3,

•

ρ = 0.1,

•

β = 1.

Eksperymenty (c.d.)

Przebieg przykładowego eksperymentu:

Eksperymenty (c.d.)

Wyniki:

Eksperymenty (c.d.)

Inne testowane funkcje:

•

f (x )

= x

4

+ x

3

+ x

2

+ x

•

f (x )

= x

3

·

e

−

x

·

cos x · sin x · (sin

2

x · cos x − 1)

•

f (x )

= gd

−

1

=

1
2

ln



1

+sin x

1−sin x



•

f (x

, y, z) = (1 + x

0

.5

+ y

−

1

+ z

−

1

.5

)

2

Eksperymenty (c.d.)

Przykładowe rozwiązania przybliżone:

f (x )

= x

4

+ x

3

+ x

2

+ x

-1

-0,5

0

0,5

1

1,5

2

2,5

3

3,5

4

4,5

-1

-0,8

-0,6

-0,4

-0,2

0

0,2

0,4

0,6

0,8

1

x

f(

x

)

Funkcja aproksymuj¹ca

Funkcja aproksymowana

Eksperymenty (c.d.)

Przykładowe rozwiązania przybliżone:

f (x )

= x

3

·

e

−

x

·

cos x · sin x · (sin

2

x · cos x − 1)

-1

-0,8

-0,6

-0,4

-0,2

0

0,2

0,4

0,6

0,8

1

0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 5,5 6 6,5 7 7,5 8 8,5 9 9,5

x

f(

x

)

Funkcja aproksymuj¹ca

Funkcja aproksymowana

Eksperymenty (c.d.)

Przykładowe rozwiązania przybliżone:

f (x )

= gd

−

1

=

1

2

ln

1

+ sin x

1 − sin x

!

-5

-4

-3

-2

-1

0

1

2

3

4

5

-4

-3,4

-2,7

-2,1

-1,4

-0,8

-0,2

0,48 1,12 1,76

2,4

3,04 3,68

x

f(x

)

Funkcja aproksymowana

Funkcja aproksymuj¹ca

Eksperymenty (c.d.)

Porównanie wyników dla (najgorzej aproksymowanej) funkcji:

f (x )

= x

3

·

e

−

x

·

cos x · sin x · (sin

2

x · cos x − 1)

met.

błąd

błąd

dł. rozw.

nr cyklu

bezwzgl.

APE

orygin.

rozw.

IBT

8.9760

58.2407%

75

89

OG

5.0800

20.1800%

45

5000

OBT

0.7774

3.4905%

117

87354

OT

0.2743

1.8234%

72

72228

IT

0.0001

0.0008%

87

18

Wnioski:

•

Na wynik działania ma duży wpływ zadana gramatyka.

•

Metoda (w przedstawionej wersji) sprawdza się dla niezbyt
złożonych funkcji, ale znajduje rozwiązania dokładne
stosunkowo szybko (kilkaset cykli).

•

Dla złożonych funkcji znajduje się jedynie rozwiązania
przybliżone, czasem z błędem dość znacznym.

•

Należy zmodyfikować regułę przejścia wprowadzając elementy
strategii zachłannej.

•

Należy zbadać przydatność listy TABU.

•

Należy zbadać podejście naśladujące wesję instrukcyjną
Programowania Mrowiskowego.