Úloha 6 - Problém vážené splnitelnosti booleovské formule (simulované ochlazování)


Tabulka nalezených řešení v závislosti na parametru jmenovatele:

počáteční stav:

nulový stav

nahodný stav

 

počáteční stav:

nulový stav

nahodný stav

parametr jmenovatele

klauzuli

počet řešení

poměr

řešení

poměr

 

parametr jmenovatele

klauzuli

počet

řešení

poměr

řešení

poměr

0.25

 

 

 

 

 

 

1,5

 

 

 

 

 

 

20

462,70

1,0000

447,78

1,0000

 

 

20

2179,58

0,9995

2172,87

1,0000

 

30

748,61

1,0000

750,42

1,0000

 

 

30

1559,03

1,0000

1567,08

1,0000

 

40

424,47

1,0000

428,49

1,0000

 

 

40

749,66

1,0000

749,69

1,0000

 

50

274,15

1,0000

270,74

1,0000

 

 

50

358,06

1,0000

353,85

1,0000

 

60

71,34

0,9997

74,19

0,9997

 

 

60

82,75

0,9992

81,92

0,9997

 

70

72,71

0,9993

70,93

0,9996

 

 

70

81,36

1,0000

81,37

0,9994

 

80

9,20

0,9957

9,36

0,9954

 

 

80

10,17

0,9959

9,71

0,9959

0,5

 

 

 

 

 

 

1,75

 

 

 

 

 

 

20

1223,35

1,0000

1228,72

1,0000

 

 

20

2147,85

1,0000

2152,18

1,0000

 

30

1166,29

1,0000

1168,63

1,0000

 

 

30

1542,80

0,9997

1528,64

1,0000

 

40

711,09

1,0000

696,09

1,0000

 

 

40

724,17

0,9997

730,66

1,0000

 

50

380,41

1,0000

372,81

1,0000

 

 

50

387,82

0,9998

381,95

0,9998

 

60

83,93

0,9998

82,82

0,9998

 

 

60

83,41

0,9993

86,03

0,9987

 

70

73,98

0,9997

73,57

0,9991

 

 

70

74,24

0,9993

77,98

0,9994

 

80

10,27

0,9967

10,51

0,9964

 

 

80

9,27

0,9959

8,86

0,9955

0,75

 

 

 

 

 

 

2

 

 

 

 

 

 

20

1663,68

1,0000

1648,42

1,0000

 

 

20

2054,64

1,0000

2064,35

0,9995

 

30

1439,52

1,0000

1455,28

1,0000

 

 

30

1621,71

1,0000

1618,43

1,0000

 

40

758,61

1,0000

750,84

1,0000

 

 

40

742,95

0,9995

757,41

0,9997

 

50

389,13

1,0000

381,41

1,0000

 

 

50

421,27

0,9998

410,05

0,9998

 

60

79,23

0,9987

78,53

0,9995

 

 

60

76,14

0,9985

76,60

0,9987

 

70

77,09

0,9997

82,08

0,9996

 

 

70

81,65

0,9991

81,46

0,9984

 

80

9,60

0,9960

9,81

0,9962

 

 

80

9,75

0,9940

9,71

0,9956

1

 

 

 

 

 

 

2,25

 

 

 

 

 

 

20

1834,08

1,0000

1847,91

1,0000

 

 

20

2142,31

1,0000

2159,31

0,9995

 

30

1523,23

1,0000

1529,67

1,0000

 

 

30

1581,13

0,9997

1599,39

1,0000

 

40

707,66

1,0000

704,04

1,0000

 

 

40

692,74

0,9997

699,36

0,9995

 

50

351,82

1,0000

350,99

1,0000

 

 

50

367,89

1,0000

381,11

0,9996

 

60

83,62

0,9985

82,05

0,9990

 

 

60

86,63

0,9978

89,56

0,9975

 

70

76,99

0,9999

77,72

0,9997

 

 

70

82,57

0,9994

81,82

0,9996

 

80

9,67

0,9959

9,88

0,9965

 

 

80

10,53

0,9969

10,76

0,9969

1,25

 

 

 

 

 

 

2,5

 

 

 

 

 

 

20

1850,66

1,0000

1848,07

1,0000

 

 

20

2004,26

1,0000

2005,10

0,9990

 

30

1569,44

1,0000

1559,88

1,0000

 

 

30

1455,91

0,9980

1434,80

0,9987

 

40

777,16

1,0000

762,99

1,0000

 

 

40

683,18

0,9993

696,50

0,9988

 

50

365,39

1,0000

371,05

1,0000

 

 

50

343,73

0,9984

350,90

0,9992

 

60

79,92

0,9985

83,25

0,9987

 

 

60

79,33

0,9983

77,32

0,9985

 

70

79,08

0,9997

78,43

0,9999

 

 

70

81,29

0,9989

79,80

0,9980

 

80

10,02

0,9937

9,83

0,9951

 

 

80

10,58

0,9949

10,90

0,9934

Z hodnot je vidět, že nejlepšího výsledku (nejvíce nalezených řešení) se dosáhlo použitím parametru jmenovatele 1,5. Také je vidět, že není velký rozdíl v poćtu nalezených řešení, pokud je počáteční stav náhodně generovaný. Od tohoto měření dále je počáteční stav nulový.

Abych viděl, jaký vliv má hodnota jmenovatele na průběh algoritmu, sestavil jsem si následující tabulku:

cyklus

0,75

1,5

2,25

počet zhoršení

počet zlepšení

počet zhoršení

počet zlepšení

počet zhoršení

počet zlepšení

1

110

116

131

138

137

136

2

110

104

122

132

140

135

3

103

107

129

129

134

138

4

100

98

117

131

133

132

5

86

91

114

117

133

138

6

94

85

120

117

128

125

7

86

89

112

118

128

129

8

69

69

117

112

123

119

9

66

83

111

100

123

115

10

83

74

105

98

113

121

11

57

56

97

107

118

121

12

63

55

85

88

107

115

13

52

53

95

95

99

105

14

31

35

71

81

95

100

15

38

33

71

72

99

96

16

43

39

77

76

91

102

17

32

35

77

70

78

78

18

36

40

60

71

82

86

19

33

36

53

43

67

72

20

17

17

59

57

66

65

21

13

12

51

54

58

55

22

17

18

35

42

60

59

23

10

8

26

27

59

58

24

12

13

33

38

48

43

25

11

12

36

28

38

48

26

13

13

27

30

38

43

27

13

11

23

25

47

43

28

9

10

27

26

35

41

29

11

11

15

15

39

41

30

11

11

23

21

30

30

31

6

7

16

19

23

17

32

7

5

16

14

24

27

33

4

5

13

14

21

24

34

7

7

9

10

18

16

35

6

7

9

9

19

20

36

6

5

11

10

17

18

Je vidět, že velikost parametru jmenovatele ovlivňuje jak počet zhoršení na jednu iteraci, tak počet zlepšení. Je to vcelku pochopitelné – algoritmus se náhodně dostává do horších stavů, aby se z nich následně dostal zpět změnou té samé proměnné. Později se pokusím otestovat, jaký bude mít vliv na chování algoritmu zvýšené ohodnocení splněných klauzulí, případně zavedení bonusu za splněnou formuli.