1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
4 | * and the BEACON Center for the Study of Evolution in Action.
|
---|
5 | *
|
---|
6 | * This file is part of HeuristicLab.
|
---|
7 | *
|
---|
8 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
9 | * it under the terms of the GNU General Public License as published by
|
---|
10 | * the Free Software Foundation, either version 3 of the License, or
|
---|
11 | * (at your option) any later version.
|
---|
12 | *
|
---|
13 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
16 | * GNU General Public License for more details.
|
---|
17 | *
|
---|
18 | * You should have received a copy of the GNU General Public License
|
---|
19 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
20 | */
|
---|
21 | #endregion
|
---|
22 |
|
---|
23 |
|
---|
24 | using System.Diagnostics.Contracts;
|
---|
25 |
|
---|
26 | namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
|
---|
27 |
|
---|
28 | // more states for individual variables are created dynamically
|
---|
29 | internal class ConstraintHandler {
|
---|
30 | private int nVars;
|
---|
31 | private readonly int maxVariables;
|
---|
32 |
|
---|
33 | public int prevTermFirstVariableState;
|
---|
34 | public int curTermFirstVariableState;
|
---|
35 | public int prevTermFirstFactorType;
|
---|
36 | public int curTermFirstFactorType;
|
---|
37 | public int prevFactorType;
|
---|
38 | public int curFactorType;
|
---|
39 | public int prevFactorFirstVariableState;
|
---|
40 | public int curFactorFirstVariableState;
|
---|
41 | public int prevVariableRef;
|
---|
42 |
|
---|
43 |
|
---|
44 | public ConstraintHandler(int maxVars) {
|
---|
45 | this.maxVariables = maxVars;
|
---|
46 | }
|
---|
47 |
|
---|
48 | // 1) an expression is a sum of terms t_1 ... t_n
|
---|
49 | // FirstFactorType(t_i) <= FirstFactorType(t_j) for each pair t_i, t_j where i < j
|
---|
50 | // FirstVarReference(t_i) <= FirstVarReference(t_j) for each pair t_i, t_j where i < j and FirstFactorType(t_i) = FirstFactorType(t_j)
|
---|
51 | // 2) a term is a product of factors, each factor is either a variable factor, an exp factor, a log factor or an inverse factor
|
---|
52 | // FactorType(f_i) <= FactorType(f_j) for each pair of factors f_i, f_j and i < j
|
---|
53 | // FirstVarReference(f_i) <= FirstVarReference(f_j) for each pair of factors f_i, f_j and i < j and FactorType(f_i) = FactorType(f_j)
|
---|
54 | // 3) a variable factor is a product of variable references v1...vn
|
---|
55 | // VarIdx(v_i) <= VarIdx(v_j) for each pair of variable references v_i, v_j and i < j
|
---|
56 | // (IMPLICIT) FirstVarReference(t) <= VarIdx(v_i) for each variable reference v_i in term t
|
---|
57 | // 4) an exponential factor is the exponential of a product of variables v1...vn
|
---|
58 | // VarIdx(v_i) <= VarIdx(v_j) for each pair of variable references v_i, v_j and i < j
|
---|
59 | // (IMPLICIT) FirstVarReference(t) <= VarIdx(v_i) for each variable reference v_i in term t
|
---|
60 | // 5) a log factor is a sum of terms t_i where each term is a product of variables
|
---|
61 | // FirstVarReference(t_i) <= FirstVarReference(t_j) for each pair of terms t_i, t_j and i < j
|
---|
62 | // for each term t: VarIdx(v_i) <= VarIdx(v_j) for each pair of variable references v_i, v_j and i < j in t
|
---|
63 | public bool IsAllowedFollowState(int currentState, int followState) {
|
---|
64 | // the following states are always allowed
|
---|
65 | if (
|
---|
66 | followState == Automaton.StateVariableFactorEnd ||
|
---|
67 | followState == Automaton.StateExpFEnd ||
|
---|
68 | followState == Automaton.StateExpFactorEnd ||
|
---|
69 | followState == Automaton.StateLogTFEnd ||
|
---|
70 | followState == Automaton.StateLogTEnd ||
|
---|
71 | followState == Automaton.StateLogFactorEnd ||
|
---|
72 | followState == Automaton.StateInvTFEnd ||
|
---|
73 | followState == Automaton.StateInvTEnd ||
|
---|
74 | followState == Automaton.StateInvFactorEnd ||
|
---|
75 | followState == Automaton.StateFactorEnd ||
|
---|
76 | followState == Automaton.StateTermEnd ||
|
---|
77 | followState == Automaton.StateExprEnd
|
---|
78 | ) return true;
|
---|
79 |
|
---|
80 |
|
---|
81 | // all other states are only allowed if we can add more variables
|
---|
82 | if (nVars >= maxVariables) return false;
|
---|
83 |
|
---|
84 | // the following states are always allowed when we can add more variables
|
---|
85 | if (
|
---|
86 | followState == Automaton.StateTermStart ||
|
---|
87 | followState == Automaton.StateFactorStart ||
|
---|
88 | followState == Automaton.StateExpFStart ||
|
---|
89 | followState == Automaton.StateLogTStart ||
|
---|
90 | followState == Automaton.StateLogTFStart ||
|
---|
91 | followState == Automaton.StateInvTStart ||
|
---|
92 | followState == Automaton.StateInvTFStart
|
---|
93 | ) return true;
|
---|
94 |
|
---|
95 | // enforce non-decreasing factor types
|
---|
96 | if (currentState == Automaton.StateFactorStart) {
|
---|
97 | if (curFactorType < 0) {
|
---|
98 | // FirstFactorType(t_i) <= FirstFactorType(t_j) for each pair t_i, t_j where i < j
|
---|
99 | return prevTermFirstFactorType <= followState;
|
---|
100 | } else {
|
---|
101 | // FactorType(f_i) <= FactorType(f_j) for each pair of factors f_i, f_j and i < j
|
---|
102 | return curFactorType <= followState;
|
---|
103 | }
|
---|
104 | }
|
---|
105 | // enforce non-decreasing variables references in variable and exp factors
|
---|
106 | if (currentState == Automaton.StateVariableFactorStart || currentState == Automaton.StateExpFStart || currentState == Automaton.StateLogTFStart || currentState == Automaton.StateInvTFStart) {
|
---|
107 | if (prevVariableRef > followState) return false; // never allow decreasing variables
|
---|
108 | if (prevFactorType < 0) {
|
---|
109 | // FirstVarReference(t_i) <= FirstVarReference(t_j) for each pair t_i, t_j where i < j
|
---|
110 | return prevTermFirstVariableState <= followState;
|
---|
111 | } else if (prevFactorType == curFactorType) {
|
---|
112 | // (FirstVarReference(f_i) <= FirstVarReference(f_j) for each pair of factors f_i, f_j and i < j and FactorType(f_i) = FactorType(f_j)
|
---|
113 | return prevFactorFirstVariableState <= followState;
|
---|
114 | }
|
---|
115 | }
|
---|
116 |
|
---|
117 |
|
---|
118 | return true;
|
---|
119 | }
|
---|
120 |
|
---|
121 |
|
---|
122 | public void Reset() {
|
---|
123 | nVars = 0;
|
---|
124 |
|
---|
125 |
|
---|
126 | prevTermFirstVariableState = -1;
|
---|
127 | curTermFirstVariableState = -1;
|
---|
128 | prevTermFirstFactorType = -1;
|
---|
129 | curTermFirstFactorType = -1;
|
---|
130 | prevVariableRef = -1;
|
---|
131 | prevFactorType = -1;
|
---|
132 | curFactorType = -1;
|
---|
133 | curFactorFirstVariableState = -1;
|
---|
134 | prevFactorFirstVariableState = -1;
|
---|
135 | }
|
---|
136 |
|
---|
137 | public void StartTerm() {
|
---|
138 | // reset factor type. in each term we can start with each type of factor
|
---|
139 | prevTermFirstVariableState = curTermFirstVariableState;
|
---|
140 | curTermFirstVariableState = -1;
|
---|
141 |
|
---|
142 | prevTermFirstFactorType = curTermFirstFactorType;
|
---|
143 | curTermFirstFactorType = -1;
|
---|
144 |
|
---|
145 |
|
---|
146 | prevFactorType = -1;
|
---|
147 | curFactorType = -1;
|
---|
148 |
|
---|
149 | curFactorFirstVariableState = -1;
|
---|
150 | prevFactorFirstVariableState = -1;
|
---|
151 | }
|
---|
152 |
|
---|
153 | public void StartFactor(int state) {
|
---|
154 | prevFactorType = curFactorType;
|
---|
155 | curFactorType = -1;
|
---|
156 |
|
---|
157 | prevFactorFirstVariableState = curFactorFirstVariableState;
|
---|
158 | curFactorFirstVariableState = -1;
|
---|
159 |
|
---|
160 |
|
---|
161 | // store the first factor type
|
---|
162 | if (curTermFirstFactorType < 0) {
|
---|
163 | curTermFirstFactorType = state;
|
---|
164 | }
|
---|
165 | curFactorType = state;
|
---|
166 |
|
---|
167 | // reset variable references. in each factor we can start with each variable reference
|
---|
168 | prevVariableRef = -1;
|
---|
169 | }
|
---|
170 |
|
---|
171 |
|
---|
172 | public void AddVarToCurrentFactor(int state) {
|
---|
173 |
|
---|
174 | Contract.Assert(prevVariableRef <= state);
|
---|
175 |
|
---|
176 | // store the first variable reference for each factor
|
---|
177 | if (curFactorFirstVariableState < 0) {
|
---|
178 | curFactorFirstVariableState = state;
|
---|
179 |
|
---|
180 | // store the first variable reference for each term
|
---|
181 | if (curTermFirstVariableState < 0) {
|
---|
182 | curTermFirstVariableState = state;
|
---|
183 | }
|
---|
184 | }
|
---|
185 | prevVariableRef = state;
|
---|
186 |
|
---|
187 | nVars++;
|
---|
188 | }
|
---|
189 |
|
---|
190 | public void EndFactor() {
|
---|
191 | Contract.Assert(prevFactorFirstVariableState <= curFactorFirstVariableState);
|
---|
192 | Contract.Assert(prevFactorType <= curFactorType);
|
---|
193 | }
|
---|
194 |
|
---|
195 | public void EndTerm() {
|
---|
196 |
|
---|
197 | Contract.Assert(prevFactorType <= curFactorType);
|
---|
198 | Contract.Assert(prevTermFirstVariableState <= curTermFirstVariableState);
|
---|
199 | }
|
---|
200 | }
|
---|
201 | }
|
---|