Problémy a algoritmy Semestrální práce

Problémy a algoritmy Semestrální práce

Vladimír Macek, 5. ročník kombinované studium FEL ČVUT

Obsah Úloha I. – Problém batohu 0/1.......................................................................................2 I.1 Zadání I.2 Základ problému I.3 Řešení hrubou silou I.4 Řešení heuristikou podle poměru cena/váha I.5 Závěr Úloha II. - Problém přelévání vody..................................................................................4 II.1 Zadání II.2 Řešení II.3 Výsledky a zdrojový kód II.4 Závěr Úloha III. - Problém batohu 0/1 dalšími metodami...............................................................8 III.1 Zadání III.2 Řešení metodou větví a hranic III.3 Řešení metodou dynamického programování III.4 Řešení heuristikou cena/váha s testem nejcennější věci III.5 Závěr Úloha IV. - Experimentální hodnocení.............................................................................11 IV.1 Počet navštívených stavů IV.2 Generátor instancí IV.2.1 Závislost: Maximální váha věci → počet navštívených stavů IV.2.2 Závislost: Maximální cena věci → počet navštívených stavů IV.2.3 Kapacita batohu / celková váha věcí → počet navštívených stavů IV.3 Závěr Úloha V. - Splnitelnost booleovské formule pomocí GA........................................................14 V.1 Zadání V.2 Řešení V.3 Vstupní data V.4 Příklad výsledku (V=C=1000, K=3) Vysvětlivky k výstupu V.5 Implementace Zdrojový kód V.6 Závěr Testující konfigurace: •

AMD Athlon XP 2200+, 1800MHz, chipset nVidia nForce 2, 32bitová architektura

•

3563.52 bogomips (kernel 2.6.8)

•

OS Linux Debian Sarge

•

překladač gcc 3.3.5 s optimalizací -O3

•

interpretr jazyka Python 2.3.5

Problémy a algoritmy – semestrální práce - Vladimír Macek

Stránka 1/20

Úloha I. – Problém batohu 0/1 I.1 Zadání • •

Naprogramujte řešení 0/1 problému batohu hrubou silou. Na zkušebních datech pozorujte závislost výpočetního času na n. Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha. Pozorujte • závislost výpočetního času na n, • průměrné zhoršení proti exaktní metodě, • maximální chybu.

Měření nechť je orientační - doba chodu jednotlivých testů nemusí překračovat několik málo minut.

I.2 Základ problému • • • •

Je dáno: celé číslo n (počet věcí), celé číslo M (kapacita batohu), konečná množina V = {v1, v2, ... ,vn} konečná množina C = {c1, c2, ... ,cn}

(hmotnosti věcí), (ceny věcí).

Nejznámější varianta je optimalizační. Pokud se mluví o „problému batohu“ bez bližšího určení, většinou se rozumí tato verze. Zkonstruujte množinu X= {x1, x2, ... ,xn}, kde každé xi je 0 nebo 1, tak, aby platilo: 1. v1.x1 + v2.x2 + ... + vn.xn <= M 2. c1.x1 + c2.x2 + ... + cn.xn bylo maximální

(batoh nebyl přetížen), (cena věcí v batohu byla maximální).

I.3 Řešení hrubou silou Řešení problémů hrubou silou klade nejnižší nároky na uvažování programátora. Stavový prostor úlohy se prohledává postupně a zde má velikost 2n, neboť je třeba otestovat všechny kombinace umístění nebo neumístění věcí do batohu. I v případě, kdy jsme naše řešení ochudili alespoň o prohledávání těch irelevantních stavů, které překročí kapacitu batohu, časová složitost rychle roste. Do hodnoty 25 včetně byla doba jedné instance T počítána jako padesátina z celé sady o 50 instancích. U vyšších četností se měřila pouze doba první instance ze zadaných dat.

n

T [ms]

n

T [ms]

4

<1

27

2495

10

<1

30

22098

15

2

32

100772

20

19

35

710108

22

74

37

příliš

25

602

40

příliš


Stránka 2/20

I.4 Řešení heuristikou podle poměru cena/váha Předpokládáme, že věc, která má nejlepší poměr cena/váha a zároveň ji ještě batoh unese, bude s největší pravděpodobností součástí výsledného řešení. Výpočet řešení takto velmi zjednodušíme, avšak může být zatížen velkými chybami. Velikost této chyby není shora omezena a závisí na konkrétní instanci. Postup řešení: Věci budou seřazeny sestupně podle poměru cena/váha. Pak budou postupně vkládány do batohu až do naplnění jeho kapacity. Časovou složitost zde již z výsledků vypouštíme, protože rychlost výpočtu je závislá na optimálním řadicím algoritmu QuickSort a je velice krátká.

n

Optimálních řešení [%]

Maximální chyba [%]

Průměrné zhoršení [%]

4

72

68,37

7,19

10

46

15,75

2,93

15

60

5,64

0,80

20

40

6,12

1,27

22

30

8,75

1,43

25

32

5,42

1,26

27

36

3,87

0,91

30

16

3,33

0,96

32

28

3,61

0,69

35

28

3,82

0,95

37

32

2,20

0,61

40

24

2,57

0,62

I.5 Závěr Z uvedeného je zřejmé, že existují reálné problémy, které jsou a i nadále budou hrubou silou v podstatě neřešitelné. Pro jejich vyřešení je potřeba zvolit jinou cestu, například vhodnou heuristiku. To však vždy vnáší nejistotu správného řešení.


Stránka 3/20

Úloha II. - Problém přelévání vody II.1 Zadání K dispozici je určitý počet kýblů o různých objemech, neomezený zdroj vody a nenasytný kanál. Kýble mají libovolný, známý počáteční obsah. Úkolem je dosáhnout ve všech kýblech předepsaného stavu vody. Možné úkony: •

naplnění kýblu po okraj,

•

vylití obsahu kýblu do kanálu,

•

přelití vody z jednoho kýblu do druhého tak, aby druhý kýbl nepřetekl.

Navrhněte a implementujte heuristiku řešící tento problém. Heuristiku otestujte na zadaných příkladech (viz zdrojový text).

II.2 Řešení K řešení byla použita metoda prohledávání do šířky o třech typech hledání: 0. Neinformované (hrubou silou), 1. Informované s dvoustavovou heuristikou (+2 body za správně naplněný kýbl), 2. Informované s třístavovou heuristikou (jako předchozí, navíc +1 bod za vhodný objem v jiném než správném kýblu). Vybírání z fronty se dělo tak, že neinformovaný typ hledání odebírá první prvek, informované typy také, ale předtím si frontu seřadí sestupně podle ohodnocení stavů. Nově expandovaný stav nebyl vkládán do fronty v případě, že už byl někdy dříve expandován. Ke zjištění této skutečnosti bylo použito asociativní pole. Výpočet byl ukončen při prvním dosažení cílového stavu. Tato situace byla zjišťována nalezením stavu ohodnoceném dvojnásobkem počtu kýblu (= všechny kýble mají cílový objem, hodnocení 2). Implementace byla provedena v jazyce Python, a celý výpočet trval přibližně 3m20s.

II.3 Výsledky a zdrojový kód Na následujících stranách. Vysvětlivky k výsledkům: SType – Typ hledání, Found – řešení nalezeno, Explored – počet zkoumaných stavů, Expanded – celkový počet expandovaných stavů ve frontě, Depth – hloubka řešení ve stavovém stromě, Time – čas řešení v milisekundách.

II.4 Závěr Lze prohlásit některá tvrzení: •

Neinformované hledání do šířky z principu vždy najde nejkratší cestu,

•

delší nalezená cesta informovaných metod stojí zlomek času,

•

třístavová heuristika nabízí obvykle lepší výsledky než dvoustavová (méně informovaná),

•

počet navštívených a expandovaných stavů se pro jednotlivé instance může dosti lišit,

•

heuristika nemusí poskytovat nejkratší cestu nebo vůbec selže, protože je příliš jednoduchá.


Stránka 4/20

SType

Found

Explored

Expanded

Depth

Time

Problem: 2 1 0

{'volume': (14, 10, 6, 2, 8), 'state': [0, 0, 1, 0, 0], 'goal': (12, 6, 4, 1, 8)} True 46 598 18 41.1 True 123 1211 14 151.2 True 8992 8992 11 4265.1

Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0


Problem: 2 1 0



Stránka 5/20

#!/usr/bin/python

if self.verbose_level >= 3: print "Expanding: %s" % state

import time # Instance vstupnich dat -- po radcich jednotlive problemy # volume - objem kbeliku # state - naplnenost jednotlivych kbeliku na pocatku # goal - cilovy stav jednotlivych kbeliku INPUT_DATA = (\ {'volume': (14,10,6,2,8), 'state': [0,0,1,0,0], 'goal': (12,6,4,1,8)}, {'volume': (14,10,6,2,8), 'state': [0,0,1,0,0], 'goal': (14,4,5,0,4)}, {'volume': (14,10,6,2,8), 'state': [0,0,1,0,0], 'goal': (12,6,6,2,4)}, {'volume': (14,10,6,2,8), 'state': [0,0,1,0,0], 'goal': (0,2,1,2,8)}, {'volume': (15,12,8,4,6), 'state': [0,0,0,0,0], 'goal': (5,5,5,0,1)}, {'volume': (15,12,8,4,6), 'state': [0,0,0,0,0], 'goal': (12,1,3,4,5)}, {'volume': (15,12,8,4,6), 'state': [0,0,0,0,0], 'goal': (11,1,3,4,5)}, {'volume': (15,12,8,4,6), 'state': [0,0,0,0,0], 'goal': (3,12,4,0,6)}, {'volume': (15,12,8,4,6), 'state': [0,0,0,0,0], 'goal': (2,0,4,3,6)}, {'volume': (14,10,12,3,8), 'state': [0,0,0,0,0], 'goal': (13,9,12,2,7)}, {'volume': (14,10,12,3,8), 'state': [0,0,0,0,0], 'goal': (1,5,5,3,4)}, {'volume': (14,10,12,3,8), 'state': [0,0,0,0,0], 'goal': (0,9,6,3,1)}, {'volume': (14,10,12,3,8), 'state': [0,0,0,0,0], 'goal': (12,0,12,0,2)}, {'volume': (14,10,12,3,8), 'state': [0,0,0,0,0], 'goal': (7,3,7,0,0)}, {'volume': (14,10,12,3,8), 'state': [0,0,0,0,0], 'goal': (7,0,7,0,7)} ) TYPE_UNINFORMED = 0 TYPE_HEURISTIC1 = 1 TYPE_HEURISTIC2 = 2

# Prohledavani bez heuristiky # Prohledavani s dvoustavovou heuristikou # Prohledavani s tristavovou heuristikou

class BucketSolver: def __init__(self, problem_instance, search_type, verbose_level = 0): self.verbose_level = verbose_level self.search_type = search_type self.num = len(problem_instance['volume']) # Pocet kbeliku self.closed = {} # Jiz jednou expandovane stavy nepridavame self.queue = [] self.explored = 0 self.expanded = 0 problem_instance['depth'] = 0 # Hloubka 1. stavu self.push_state(problem_instance) # Pocatecni stav do fronty self.goal_rank = self.num * 2 # Hodnoceni ciloveho stavu

if self.verbose_level >= 5: print "Queue dump:" for s in self.queue: print "\t%s" % s stopwatch = (time.time() - stopwatch) * 1000 if self.verbose_level: print "%-9d%-5s%10d%11d%8d%9.1f" % (self.search_type, found, \ self.explored, self.expanded, state['depth'], stopwatch) if self.verbose_level >= 2: print "State:", state def dequeue(self): """ Vybere z fronty kandidata. Neinformovana verze proste prvniho. Informovana si predtim frontu sestupne seradi podle ohodnoceni. """ if self.search_type != TYPE_UNINFORMED: self.queue.sort(lambda x, y: y['rank'] - x['rank']) return self.queue.pop(0) def expand(self, state): """ Pridame do fronty vsechny stavy, do kt. se lze dostat z aktualniho. """ for i in range(self.num): # i-ty kybl vyprazdneny emptied_state = state.copy() emptied_state['state'] = emptied_state['state'][:] emptied_state['state'][i] = 0 self.push_state(emptied_state) # i-ty kybl naplneny filled_state = state.copy() filled_state['state'] = filled_state['state'][:] filled_state['state'][i] = filled_state['volume'][i] self.push_state(filled_state)

def search(self): stopwatch = time.time() while self.queue: state = self.dequeue() self.explored += 1 found = (state['rank'] == self.goal_rank) if found: break

# Cil dle hodnoceni

self.expand(state)


Stránka 6/20

for j in range(self.num): if i != j: # i-ty kybl prelity do j-teho poured_state = state.copy() poured_state['state'] = poured_state['state'][:] # objem, ktery muzeme prelit volume = min(poured_state['state'][i], \ poured_state['volume'][j] - poured_state['state'][j]) if volume > 0: poured_state['state'][i] -= volume poured_state['state'][j] += volume self.push_state(poured_state)

def solve(problems, verbose_level = 0): if verbose_level: print "SType Found Explored

Expanded

Depth

Time"

for problem in problems: if verbose_level: print "\nProblem: %s" % (problem) for search_type in (TYPE_HEURISTIC2, TYPE_HEURISTIC1, TYPE_UNINFORMED): bs = BucketSolver(problem, search_type, verbose_level) bs.search() del bs if __name__ == '__main__': solve(INPUT_DATA, verbose_level = 1)

def push_state(self, state): """ Pridavame novy expandovany stav s vypoctenym ohodnocenim. Pokud tento stav uz nekdy byl pridavan, nepridavame ho podruhe. """ state_str = str(state['state']) if state_str not in self.closed: self.closed[state_str] = True state['rank'] = self.rank(state) self.expanded += 1 state['depth'] += 1 self.queue.append(state) def rank(self, state): """ Tristavova heuristicka funkce: 1 bod za to, je-li pozadovany objem v jakekoli nadobe 2 body za to, je-li pozadovany objem ve spravne nadobe Dvoustavova je bez hodnoceni "1 bod". """ points = 0 for i in range(self.num): goal = state['goal'][i] if state['state'][i] == goal: points += 2 elif (goal in state['state']) \ and (self.search_type == TYPE_HEURISTIC2): points += 1 return points


Stránka 7/20

Úloha III. - Problém batohu 0/1 dalšími metodami III.1 Zadání •

Naprogramujte řešení 0/1 problému batohu metodou větví a hranic tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria.

•

Naprogramujte řešení 0/1 problému batohu nebo alespoň 0/1 exaktního problému batohu bez cen metodou dynamického programování.

•

Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejcennější věci.

III.2 Řešení metodou větví a hranic Tento algoritmus, je téměř shodný řešení hrubou silou z odstavce I.3. Procházíme stavový prostor rekurzivně do hloubky. Rozdíl se značným dopadem na efektivitu je ten, že před přidáním stavu testujeme, zda podstrom, který se jím může začít, vůbec může vést na řešení lepší než to dosud nalezené. Jedno takové kritérium bylo přidáno už v odstavci I.3 (test překročení kapacity batohu). Druhé přidáme nyní: Budeme zkoumat, zda součet cen zbývajících věcí, které můžeme v dané chvíli přidat, může překročit průběžně vylepšovanou cenu. Metoda dosahuje na optimální řešení za vynechání značné části stavového prostoru.

n

T [ms]

T/50 ø počet kroků

4

<1

<1

10

10

1

<1

180

15

1

<1

361

20

27

<1

6821

22

70

1

26562

25

104

2

74717

27

139

2

95417

30

658

13

451564

32

1176

23

755697

35

3096

61

2035667

37

3504

70

2286085

40

45270

905

25525694

Vidíme, že oproti metodě I.3 dosáhneme na největší z problémů (velikost 40) již v rozumnějším čase.


Stránka 8/20

III.3 Řešení metodou dynamického programování Dynamické programování se vyznačuje tím, že úlohy dekomponuje na menší nezávislé a do pomocných datových struktur uchovává jejich výsledky. Výsledek původní úlohy se pak komponuje z mezivýsledků. V ideálním případě se nic nepočítá vícekrát. Nevýhodou je velká spotřeba paměti, která může při jistých úlohách metodu diskvalifikovat. Nepříjemné je, že spotřebovaná paměť je silně závislá na datech. Zde bylo použito dvourozměrné pole VAHY[cena, věc] pro ukládání mezisoučtů hmotností věcí řešené instance. Počáteční nastavení: VAHY[0, 0] ← 0, VAHY[c, 0] ← nekonečno (pro c > 0). Pole se pak plní podle tohoto předpisu: VAHY[c, v+1] ← min( VAHY(c, v), VAHY(c – cv) + vv ) 0 <= c <= celková cena, 0 <= v <= počet věcí – 1 cv je cena v-té věci, vv je váha v-té věci Pak stačí v poli odshora (najde nejvyšší cenu) vyhledat první stav, který vyhovuje omezující podmínce (hodnota v poli je menší nebo rovna kapacitě batohu).

n

T [ms]

T/50

4

11

<1

10

87

1

15

112

2

20

212

4

22

258

5

25

336

6

27

386

7

30

499

9

32

544

10

35

672

13

37

716

14

40

879

17

Stejně jako předchozí algoritmus větví a mezí poskytuje i tento optimální řešení. Časová složitost je polynomiální, což vykupuje paměťovou náročnost. Doba běhu celého testu byla asi 5 sekund.


Stránka 9/20

III.4 Řešení heuristikou cena/váha s testem nejcennější věci Metoda je pouze malým rozšířením heuristické metody z odstavce I.4. Po skončení se testuje, zda jediná nejcennější věc, byla-li by v batohu obsažena sama (a vejde-li se tam), neposkytne lepší (dražší výsledek). Zesložitění je lineární a algoritmus se nijak podstatně nezpomalí. Zato má šanci se přiblížit optimálnímu řešení.

n

Optimálních řešení [%]

Maximální chyba [%]

Průměrné zhoršení [%]

4

76

35,28

4,26

10

46

15,75

2,93

15

60

5,64

0,80

20

40

6,12

1,27

22

30

8,75

1,43

25

32

5,42

1,26

27

36

3,87

0,91

30

16

3,33

0,96

32

28

3,61

0,69

35

28

3,82

0,95

37

32

2,20

0,61

40

24

2,57

0,62

Test nejcennější věci se vyplatil pouze v nejmenším souboru, kdy čtyřikrát pomohl k optimálnímu výsledku.

III.5 Závěr Hledáme-li optimální řešení problému v rozumném čase a máme dost operační paměti, nabízí se použití dynamického programování. Omezují-li nás paměťové nároky, je zde metoda větví a hranic. Jde-li nám o co nejrychlejší „nástin“ řešení, vybereme si některou z heuristických metod.


Stránka 10/20

Úloha IV. - Experimentální hodnocení IV.1 Počet navštívených stavů Jedná se o důležitý údaj sloužící ke srovnání algoritmů. Je nezávislý na výpočetní síle počítače, což je jeho výhoda. Jako v předešlých tabulkách, jedná se i zde o aritmetické průměry, přepočteno z padesáti zadaných instancí na jednu. n

Hrubá síla

Větve a hranice

Heuristika cena/váha

Dynamické programování

4

9

10

2

2023

10

604

180

7

13526

15

31667

361

13

28188

20

946334

6821

15

50659

22

3414819

26562

16

61419

25

28816961

74717

18

81435

27

123921277

95417

20

92540

30

1002829997

451564

22

118089

32

mnoho

755697

24

129374

35

mnoho

2035667

26

156097

37

mnoho

2286085

27

169316

40

mnoho

25525694

29

203263

IV.2 Generátor instancí Následující část popisuje výsledky experimentů prováděných s parametrizovatelným generátorem instancí pro problém batohu. Byl zkoumán vliv maximální váhy věcí, maximální ceny věcí a vliv poměru váhy batohu vůči váze věcí. Poznámka: Metoda hrubou silou zahrnuje již dříve zmíněnou optimalizaci na maximální kapacitu. Parametry experimentů: Počet instancí

50

Počet předmětů

17

Kapacita batohu / celková váha věcí

0,7

Maximální váha věcí

100

Maximální cena věci

300

Exponent granularity

1

Poměr malých a velkých věcí

1


Stránka 11/20

IV.2.1 Závislost: Maximální váha věci → počet navštívených stavů n

Hrubá síla

Větve a hranice



50

121005

2480

14

45328

100

120923

2400

14

43267

150

120916

2571

14

44214

200

121276

2839

14

41626

250

120956

2806

14

43938

300

121124

2213

13

42785

350

120861

2145

14

44461

400

120895

1956

14

42993

450

120391

2250

14

41938

500

121025

2722

14

42991

U žádné z metod není patrná prokazatelná závislost počtu navštívených stavů na velikosti instance.

IV.2.2 Závislost: Maximální cena věci → počet navštívených stavů n

Hrubá síla

Větve a hranice



50

120736

2420

13

7420

100

120797

2315

14

14928

150

121120

2505

14

22265

200

121190

2569

14

29730

250

120855

2244

14

35589

300

120583

2558

14

44186

350

120861

2530

14

50084

400

121080

2871

15

59244

450

121168

2530

14

63695

500

121110

2645

14

70830

Zde je patrná lineární závislost počtu navštívených stavů u poslední metody v tabulce. Fakt vychází z podstaty algoritmu založeném na dynamickém programování. Velikost jeho stavového prostoru je dána součinem počtu věcí a součtu jejich cen. Je zde přímá souvislost.


Stránka 12/20

IV.2.3 Kapacita batohu / celková váha věcí → počet navštívených stavů Kapacita / váha

Hrubá síla

Větve a hranice



0,1

155

572

5

44330

0,2

1980

3331

7

43994

0,3

10012

7279

8

43147

0,4

31232

10669

10

43698

0,5

65614

7960

11

41719

0,6

99239

4846

12

43332

0,7

120905

2689

14

43717

0,8

129144

955

15

43284

0,9

130922

354

16

43427

Zde je patrných závislostí několik. Skutečné řešení hrubou silou by nemělo být na zkoumaném poměru závislé. Je zřejmé, že vykázaná silná závislosti nemá příčinu v ničem jiném než v jediné optimalizaci této metody (stav není prozkoumáván, pokud by znamenal překročení maximální kapacity batohu). Metoda větví a hranic obsahuje stejnou optimalizaci, která se projevuje zejména pro nižší hodnoty poměru. Dále však obsahuje také další optimalizační metodu, díky níž se zbytečně neprocházejí stavy, které již nemohou vést k cenově lepšímu řešení než to dosud nejlepší nalezené. Závislost napovídá normální (Gaussovo) rozdělení se středem někde mezi hodnotami 0,4 a 0,5. Heuristická metoda vykazuje lineární závislost a dynamické programování se zdá být na poměru nezávislé.

IV.3 Závěr I když jsme v průběhu experimentu měnili vždy pouze jeden parametr generátoru, bylo možné ilustrovat některé zajímavé závislosti, které vycházejí z použitých metod řešení. Zároveň je však na místě opatrnost, chceme-li dělat obecnější závěry, protože náš výběr nemusel být reprezentativní.


Stránka 13/20

Úloha V. - Splnitelnost booleovské formule pomocí GA V.1 Zadání Je dána booleovská formule F proměnných X = (x1, x2, ... , xV) v konjunktivní normální formě (tj. součin součtů). Dále jsou dány celočíselné kladné váhy proměnných W = (w1, w2, ... , wV). Najděte ohodnocení Y = (y1, y2, ... , yV) proměnných x1, x2, ... , xV tak, aby F(Y) = 1 a součet vah proměnných, které jsou ohodnoceny jedničkou, byl maximální. Je přípustné omezit se na formule, z nichž každá disjunkce má právě K = 3 literály (problém 3-SAT). Problém řešte některou z pokročilých lokálních heuristik (simulované ochlazování, genetické algoritmy, tabu prohledávání).

V.2 Řešení Genetické algoritmy (GA) patří do skupiny stochastických neúplných (nemusíme se dobrat k optimálnímu výsledku) metod, jejichž prohledávací schopnosti jsou posíleny modelováním dědičnosti a posilováním kladných vlastností. Vývoj řešení probíhá v tzv. generacích, z nichž každá nese množinu jedinců, jejíž četnost se nazývá velikost populace (pop_size). První řídicí parametr. Počet generací (dobu běhu celého algoritmu) omezujeme různými druhy podmínek, z nichž pouze jednou je nalezení optimálního řešení, na rozdíl od metod úplných. Míra vhodnosti každého jedince pro šlechtění je vyjádřena jediným vypočítaným číslem nazývaným zdatnost (fitness). K jeho určení se používá toliko jedinec v daném okamžiku. GA se obvykle skládá z těchto fází: • • •

inicializace vyhodnocení cyklus : ■ selekce ■ změna ■ vyhodnocení

Fáze inicializace vytvoří počáteční generaci. V našem případě jsme zvolili náhodné jedince (proměnné jsou nastavené na 0 nebo 1 s 50% pravděpodobností). Fáze vyhodnocení vypočítá zdatnost všech jedinců v generaci a vyhodnotí pár statistických údajů. Implementovaný jednoduchý GA je postupného typu (steady state evolution). To znamená, že selekční fáze nenahrazuje celé generace novými, ale změnami prochází jen část populace a rodiče „žijí dál“ mezi svými potomky. Generace je zde sestupně seřazena podle zdatnosti a z množiny prvních jedinců (o velikosti best_area_fraction, třetí řídicí parametr) je vybrán určitý počet jedinců (o velikosti selection_ratio, druhý ř. p.). Každý z těchto jedinců je naklonován na místo, které obsazoval některý z jedinců z dolní poloviny populace. Fáze změna poskytuje možnost vývoje populace, všichni jedinci bez rozdílu zdatnosti zde mají šanci projít nahodilou mutací ve své výbavě, což je může posunout v žebříčku výš nebo níž. Používáme pouze jeden z mnoha možných rekombinačních operátorů, mutaci bitu. Míra mutace (mutation_rate, čtvrtý řídicí parametr) určuje, kolika náhodným jedincům bude náhodně vybrán bit k invertování. Druhý, třetí a čtvrtý parametr se zadávají v procentech v poměru k velikosti populace. Při řešení pomocí GA dochází často ke stagnacím vývoje populací, kdy mutace už není schopna dodat zlepšení. Na implementovaném algoritmu je to znát, nicméně je dokáže nalézt řešení a vylepšovat váhu proměnných.


Stránka 14/20

V.3 Vstupní data Jako generátor vstupních dat byl použit program G2.c ze stránky autorů M. Motoki a O. Watanabe. http://www.is.titech.ac.jp/~watanabe/gensat/a1. Bylo třeba jej upravit, aby poskytoval náhodné váhy proměnných a výstup byl vhodnější pro načítání. Nový program byl nazván G2w.c. Příklad (N = 5, M = 5, K = 3), vysvětlí i formát: # instance by # 1 line # N lines # M lines # 5 5 3 1 1 0 10 0 7 0 7 0 2 -5 2 -1 -3 -1 4 1 2 3 5 -2 4 -4 5 -1

G2w, format: <M=#-of-clauses>

V generujícím programu se na rozdíl od programu s GA pro počet proměnných V používá označení N a pro počet klauzulí C označení M.

V.4 Příklad výsledku (V=C=1000, K=3) $ bin/gasat < instance-1000-1000.3sat Loading instance from stdin: Vars 1000, clauses 1000, max weight 5491 Evaluating given solution: Match 1000 of 1000, weight 2788 Self test PASSED. Population size: 100 Selecting 2 (2.0%) individuals from best area of 10 (10.0%) Mutating with rate 10.00% Commencing the eVoLUtioN (Ctrl+C to break) ---------------------------------------------------------Time Gener Best Fitness Satisfied Forms Left ---------------------------------------------------------0h00m08 1000 975.2809 0x 25 0h00m16 2000 999.3230 0x 1 0h00m25 3000 1000.3653 100x 0 0h00m33 4000 1000.4047 209x 0 0h00m41 5000 1000.4306 283x 0 0h00m50 6000 1000.4498 353x 0 0h00m59 7000 1000.4617 403x 0 0h01m08 8000 1000.4699 431x 0 0h01m16 9000 1000.4742 449x 0 0h01m24 10000 1000.4776 462x 0 0h01m31 11000 1000.4795 471x 0 0h01m39 12000 1000.4798 472x 0 0h01m47 13000 1000.4800 473x 0 0h01m56 14000 1000.4801 474x 0 0h02m04 15000 1000.4801 474x 0 0h02m12 16000 1000.4802 475x 0 0h02m20 17000 1000.4802 475x 0 0h02m27 18000 1000.4802 475x 0 ^C - User break (SIGINT) The heaviest solution so far (value 4717) comes from generation 15957: 1111'1111'1111'1101'1011'1111'1111'1111'0011'1111'1111'1111'1011'0101'1111'1011'1101'1 111'1111'1111'1111'1111'1111'0111'1011'1101'1101'1001'1111'1101'1011'1111'1101'1101'1111'1111' 1111'1111'1011'1111'1111'1011'1111'1111'1111'1110'1011'1011'1011'1111'1110'1011'1111'1111'1111 '1110'1111'1111'1111'1111'1011'1010'1111'1111'0111'0111'1111'0110'1111'1011'10... (zkráceno)


Stránka 15/20

Vysvětlivky k výstupu Po načtení vstupní instance jsou vypsány zjištěné údaje a je proveden test za účelem zjištění, zda bude dodané řešení CNF, které je součástí vstupu, vyhodnoceno kladně. V negativním případe je program ukončen a chybu je třeba hledat buď v programu s GA nebo ve vstupních datech. Pak jsou vypsány řídicí údaje evolučního algoritmu, načež začíná výpočet, o jehož průběhu je uživatel informován po každé tisící generaci. Tabulka obsahuje: •

Čas od začátku výpočtu.

•

Číslo generace.

•

Zdatnost. Tento údaj kombinuje dvě čísla takto: před tečkou (statisíce) je počet splněných disjunkcí zadané formy, za tečkou je váha řešení. GA tedy optimalizuje obě hodnoty společně, přičemž větší hodnotu má míra splněnosti CNF.

•

Počet nalezených ohodnocení proměnných. Jedná se pouze o informativní údaj, protože jsou zde zahrnuta i ohodnocení, která již mohla být nalezena dříve.

•

Počet zbývajících disjunkcí. Poskytuje rychlou kontrolu, kolik ještě algoritmu zbývá k nalezení alespoň nějakého splňujícího řešení bez ohledu na váhu. Je to však pouze rozdíl čísla K a vyšší poloviny zdatnosti.

Zobrazující se pouze nejlepší dosažené výsledky. Bylo by možné program rozšířit o náhled aktuálního stavu pro ilustraci stagnace. Jsou dvě možná ukončení programu: •

Nalezení optimálního řešení. Program zná nejvyšší hodnotu zdatnosti, při jejím dosažení není potřeba pokračovat dále.

•

Přerušení uživatelem. Program nemá detekci stagnace ani časové omezení na svůj běh.

Pak je vypsán nejzdatnější jedinec, jeho váha a generace, ze které pochází. Na příkladu je vidět, že algoritmus už asi 2000 generací neposunul řešení.

V.5 Implementace Za účelem časově a paměťově efektivní implementace byl vybrán čistý jazyk C s četným použitím nejprimitivnějších datových typů, dynamického přidělování paměti a jejího opětovného využívání bez realokace a aritmetiky ukazatelů. K dispozici jsou dvě řešení pole popisujícího jedince: Obyčejné pole typů int (kde se pro každý bit plýtvá 31 jinými, ale vhodné pro ladění) a skutečné bitové pole zcela využívající hodnoty typu int. Kromě evolučního postupu je k dispozici ještě pokusná funkce brute_cycle hledající nejlepší řešení hrubou silou.

Zdrojový kód Na následujících stránkách.

V.6 Závěr Vytvořený genetický algoritmus sice poskytuje zajímavé výsledky, nicméně nabízí prostor pro vylepšení v oblasti softwarového generátoru pseudonáhodných čísel, potlačování stagnace, interakce s uživatelem, komplexnosti selekce mutačních operátorů, … Nikde se žádným způsobem nekontrolují duplicity. To má pozitivní dopad na rychlost, ale zřejmě negativní na přesnost. Problémy a algoritmy – semestrální práce - Vladimír Macek

Stránka 16/20

/ * Solving S A T evolutionarily. (c) 2006-06-23 Vla da Macek * /

#

#include #include #include #include #include #include #include #include

#

<stdio.h> <stdlib.h> <sys/time.h> <string.h> <signal.h>

#

#define BIT_ARRAY_IMPLEMENTATION 0 / * array i mple mentation switch * / #define BITS_PER_OCTET 8 / * we start with tough ones :-) * / #define BITS_PER_INT (BITS_PER_OCTET*sizeof(int)) #define COMBINING_MULTIPLIER

100000

/ * puts two n u mbers into one * /

/ * DA TA LOAD ED FRO M I N S T A NC E FILE. * / / * n u m ber of variables, n u mber of clauses, vars per clause * / int V = -1, C = -1, K = -1; int *solution_ba = NULL; / * bit array denoting given solution, freed early * / int *weight = NULL; / * array of weights for each variable * / int *given_clauses = NULL;/ * given problem * / / * ------ end of loaded data * / int *winner = NULL; / * the fittiest in divid ual fou n d so far * / int winning_generation = 0; / * FIX M E: So mewhere in source R A ND_MA X m ay not be enough, check! * / #define RANDOM rand / * fu nction giving so me ran do m ness in 0..R A ND_MA X * / time_t program_start_time; int sum_weight = 0;

/ * su m m ary weight of loaded insta nce * /

void *getmem(size_t size) { void *ptr = calloc(1, size); if (!ptr) { fprintf(stderr, "\nMEMORY ALLOCATION FAILURE! Terminating.\n"); exit(10); } return ptr; } / * BI T A R R A Y (ba) functions, ba is (int *), bi is n u meric bit in dex * / #if BIT_ARRAY_IMPLEMENTATION == 1 # define ba_size(totalbits) (((totalbits)/BITS_PER_OCTET) + 1) # define ba_sizeint(totalbits) (((totalbits)/BITS_PER_INT) + 1) # define ba_get(ba, bi) \ ((*((ba) + (bi)/BITS_PER_INT)) & (1 << ((bi) % BITS_PER_INT)))


define ba_set1(ba, bi) \ (*((ba) + (bi)/BITS_PER_INT) |= (1 << ((bi) % BITS_PER_INT))) define ba_set0(ba, bi) \ (*((ba) + (bi)/BITS_PER_INT) &= ~(1 << ((bi) % BITS_PER_INT))) define ba_setvalue(ba, bi, value) \ ((value) ? ba_set1((ba), (bi)) : ba_set0((ba), (bi)))

void ba_invert(int *ba, int { int val, sel = (1 << (bi % ba += bi/BITS_PER_INT; val *ba = (val & sel) ? (val & }

bi)

/ * inverts the given bit in array * /

BITS_PER_INT)); = *ba; ~sel) : (val | sel);

#else / * E L S E: I m plementation with array of integers (for debugging). * / # define ba_size(totalbits) ((totalbits) * sizeof(int)) # define ba_sizeint(totalbits) (totalbits) # define ba_get(ba, bi) (*((ba) + (bi))) # define ba_set1(ba, bi) (*((ba) + (bi)) = 1) # define ba_set0(ba, bi) (*((ba) + (bi)) = 0) # define ba_setvalue(ba, bi, value) \ ((value) ? ba_set1((ba), (bi)) : ba_set0((ba), (bi))) # define ba_invert(ba, bi) (*((ba) + (bi)) = !*((ba) + (bi))) #endif void init_time_seed() { int t = time(NULL); struct timeval tv; program_start_time = t; gettimeofday(&tv, NULL); t = tv.tv_usec % t; srand((int)t); } void load_instance() { char *p, buf[2048]; int vari = -1, ci = -1, *cp = NULL; printf("Loading instance from stdin: "); buf[sizeof(buf)-1] = '\0'; while (fgets(buf, sizeof(buf)-1, stdin)) { p = strchr(buf, '\n'); assert(p); *p = '\0'; / * required \ n ter mination * / while (*(p = buf + strlen(buf)-1) == ' ') *p = '\0'; / * right tri m * / if (*buf == '#') continue; / * com ments out * / p = buf;

Stránka 17/20

if (V == -1) { V = atoi(strsep(&p, " ")); C = atoi(strsep(&p, " ")); K = atoi(strsep(&p, " ")); assert(!p); / * syntax check: required out of inp ut now * / assert(C>0); / * assert(K == V A R S_PE R_CLA U S E); * / continue; }

return sumw; }

if (!solution_ba) { solution_ba = getmem(ba_size(V)); weight = getmem(V*sizeof(int)); vari = 0; } if ((vari >= 0) && (vari < V)) { ba_setvalue(solution_ba, vari, atoi(strsep(&p, " "))); weight[vari] = atoi(strsep(&p, " ")); sum_weight += weight[vari]; assert(!p); / * syntax check: required out of inp ut now * / vari++; continue; }

void print_individual(int *indi) { / * d u m ps the bits of the individual * / int v; for (v=0; v
if (!given_clauses) { given_clauses = getmem(K*C*sizeof(int)); ci = 0; cp = given_clauses; } if ((ci >= 0) && (ci < C)) { int i; for (i=0; i

void random_individual(int *indi) { int v; / * 0 / 1 with 50% probability: * / for (v=0; v 4); }

void print_process_time() { / * stopwatch of the process activity * / int ts = time(NULL)-program_start_time; printf("%2dh%02dm%02d", ts/3600, (ts/60)%60, ts%60); } int fitness_of_individual(int *indi); void brute_cycle() { int m, f, best_f = 0, best_m = 0, cnt = 0; int *indi = getmem(ba_size(V)); printf("Brute cycle advancing.\n"); while (1) { random_individual(indi); f = fitness_of_individual(indi); m = f/COMBINING_MULTIPLIER; cnt++; if (m > best_m) best_m = m; if (f > best_f) { best_f = f; printf("Best fitness %4d, best match %d of %d, tested %d individuals.\n", \ best_f, best_m, C, cnt);/ / , weight_of_individual(indi)); fflush(stdout); } } free(indi); printf("\n"); }

Stránka 18/20

void user_break(int blind) { printf("\n^C - User break (SIGINT)\n\n"); if (winning_generation) { printf("The heaviest solution so far (value %d) comes from generation " "%d:\n\n\t", weight_of_individual(winner), winning_generation); print_individual(winner+1); printf("\n\n"); exit(0); } } int matchnum_of_individual(int *indi) { / * first part of the fitness counting method: n u m ber of positive clauses * / int c, k, a, *atom = given_clauses; int tuples_ok = 0, tuple_ok; for (c=0; c

fitness_limit = COMBINING_MULTIPLIER*C + sum_weight -1, indi_numint = 1 + ba_sizeint(V), / * step between indivs in an array * / *pop = getmem(pop_size*indi_numint*sizeof(int)), / * place for indivs * / selection_num, best_area, mutation_num; / * I NI TIA LI ZA TIO N * / for (p=0, pp=pop; p<pop_size; p++, pp += indi_numint) { random_individual(pp+1); *pp = fitness_of_individual(pp+1); } winner = getmem(indi_numint*sizeof(int)); / * n u m ber of individ uals with best fitness to select for cloning * / selection_num = (int)((float)pop_size * selection_ratio/100); if (selection_num < 1) selection_num = 1; / * n u m ber of individ uals from the top are peloton from w here to clone * / best_area = (int)((float)pop_size * best_area_fraction/100); if (best_area < 1) best_area = 1; / * how m a ny individ uals to rando mly choose to toggle one variable (m utation) * / mutation_num = (int)((float)pop_size * mutation_rate/100); if (mutation_num < 1) mutation_num = 0; printf("Population size: %d\nSelecting %d (%.1f%%) individuals from best area " "of %d (%.1f%%)\nMutating with rate %.2f%%\n\n" "Commencing the eVoLUtioN (Ctrl+C to break)\n" "----------------------------------------------------------\n" " Time Gener Best Fitness Satisfied Forms Left\n" "----------------------------------------------------------\n", pop_size, selection_num, selection_ratio, best_area, best_area_fraction, mutation_rate); signal(SIGINT, user_break); max_fitness = 0; while (1) { generation++; / * S E L EC TIO N (CLO NI NG) * / if (generation > 1) { qsort(pop, pop_size, indi_numint * sizeof(int), compare_firstint); for (p=0; p<selection_num; p++) { int src = RANDOM() % best_area, / * p ut the clone somewhere in the tail half * / dest = (RANDOM() % (pop_size/2)) + pop_size/2; memcpy(pop + indi_numint*dest, pop + indi_numint*src, indi_numint*sizeof(int)); } }

Stránka 19/20

/ * M U T A TIO N * / for (p=0; p<mutation_num; p++) { int indi_index = RANDOM() % pop_size, var_index = RANDOM() % V; ba_invert(pop + 1 + indi_numint*indi_index, var_index); } / * E V A L U A TIO N * / for (p=0, pp=pop; p<pop_size; p++, pp += indi_numint) { int f = fitness_of_individual(pp+1), m = f/COMBINING_MULTIPLIER; *pp = f; if (f > max_fitness) { max_fitness = f; unmatched = C-m; if (m == C) matches++;

int main() { init_time_seed(); load_instance(); self_test(); start_the_evolution(100, 2, 10, 10); return 0; / * u nreachable currently * / / * brute_cycle(); return 0; * / }

memcpy(winner, pp, indi_numint*sizeof(int)); winning_generation = generation; if (f >= fitness_limit) { free(pop); printf("\nSuccessfully found assignment with the maximum weight.\n" "Individual %d of generation %d:\n\n\t", p+1, generation); print_individual(pp); printf("\n\n"); return; } } } if (!(generation%1000)) { / * don't print each generation * / print_process_time(); printf("%7d%8d.%-5d%12dx%9d\n", generation, max_fitness/COMBINING_MULTIPLIER, \ max_fitness%COMBINING_MULTIPLIER, matches, unmatched); fflush(stdout); } } free(pop); / * but u nreachable currently * / } void self_test() { int m; printf("Evaluating given solution: "); m = matchnum_of_individual(solution_ba); printf("Match %d of %d, weight %d\n", m, C, weight_of_individual(solution_ba)); if (m != C) { printf("FAILED self-test based on input data! Terminating.\n"); exit(9); } else printf("Self test PASSED.\n\n"); free(solution_ba); solution_ba = NULL; / * we don't need it a ny more * / }


Stránka 20/20

Problémy a algoritmy Semestrální práce

Recommend Documents