source: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/ConstraintHandler.cs @ 13645

Last change on this file since 13645 was 13645, checked in by gkronber, 3 years ago

#2581: added an MCTS for symbolic regression models

File size: 7.9 KB
Line 
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
24using System.Diagnostics.Contracts;
25
26namespace 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}
Note: See TracBrowser for help on using the repository browser.