source: anac2020/agentKT/src/main/java/geniusweb/exampleparties/simpleshaop/CompRegress.java

Last change on this file was 1, checked in by wouter, 4 years ago

#1910 added anac2020 parties
File size: 10.7 KB
Line 
1package geniusweb.exampleparties.simpleshaop;
2
3import java.math.BigDecimal;
4import java.util.ArrayList;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.Iterator;
8import java.util.List;
9import java.util.Map;
10import java.util.Map.Entry;
11import java.util.Set;
12import java.util.TreeMap;
13
14import geniusweb.issuevalue.Bid;
15import geniusweb.issuevalue.Domain;
16import geniusweb.issuevalue.Value;
17import geniusweb.issuevalue.ValueSet;
18import geniusweb.profile.Profile;
19
20public class CompRegress {
21
22 private final Domain domain;
23 private final int numIssues;
24 private final Bid minBid;
25 private final Bid maxBid;
26 private int totalNonMinMax;
27 private Map<Bid, String> indicatorBidMap;
28 private Map<String, HashMap<Value, BigDecimal>> estUtil;
29 private Map<String, List<Value>> nonMinMaxIndex;
30 private Map<String, Integer> numValuesPerIssue;
31 private List<String> issueOrder; // list of issues in ascending importance
32 private double[] estTheta; // smallest to largest theta values for corresponding issues
33 private Map<BigDecimal, List<Bid>> fullBidOrdering;
34
35 CompRegress(Profile profile, List<Bid> initBidOrder, HashMap<Bid, String> indicatorBidMap) {
36 this.domain = profile.getDomain();
37 this.numIssues = domain.getIssues().size();
38 this.minBid = initBidOrder.get(0);
39 this.maxBid = initBidOrder.get(initBidOrder.size()-1);
40 this.indicatorBidMap = indicatorBidMap;
41 this.issueOrder = new ArrayList<String>();
42 this.estTheta = new double[numIssues];
43 this.estUtil = new HashMap<String, HashMap<Value, BigDecimal>>();
44 this.nonMinMaxIndex = new HashMap<String, List<Value>>();
45 this.numValuesPerIssue = new HashMap<String, Integer>();
46 this.totalNonMinMax = 0;
47
48 initImportance(initBidOrder);
49 initEstUtilMap();
50 fit(initBidOrder);
51 }
52
53 ////////////////////////////////////////////////////////////////////////////////
54 // initialization methods
55 ////////////////////////////////////////////////////////////////////////////////
56
57 /**
58 * initialize the theta values and importance ordering of the issues
59 * @param initBidOrder - initial ordered bid list with the indicator bids
60 */
61 private void initImportance(List<Bid> initBidOrder) {
62 // initialize issue importance ordered list
63 int count = numIssues;
64 int index = initBidOrder.size() - 2;
65 while (count > 0) {
66 Bid bid = initBidOrder.get(index);
67 String issue = indicatorBidMap.get(bid);
68 if (issue != null) {
69 issueOrder.add(issue);
70 count--;
71 }
72 index--;
73 }
74 // initialize theta values
75 double multInverse = 1.0 / numIssues;
76 double minTheta = multInverse / 2.0;
77 double incr = multInverse / (numIssues - 1);
78
79 for (int i = 0; i < numIssues; i++) {
80 estTheta[i] = minTheta + (incr * i);
81 }
82 }
83
84 /**
85 * initialize the HashMap of estimated utilities for each value
86 */
87 public void initEstUtilMap() {
88 for (String issue : issueOrder) {
89 ValueSet values = domain.getValues(issue);
90 int numValues = values.size().intValue();
91
92 numValuesPerIssue.put(issue, numValues);
93 totalNonMinMax += numValues - 2;
94
95 estUtil.put(issue, new HashMap<Value, BigDecimal>());
96 nonMinMaxIndex.put(issue, new ArrayList<Value>());
97
98 int count = 1;
99 for (Value value : values) {
100 if (value.equals(maxBid.getValue(issue))) {
101 estUtil.get(issue).put(value, BigDecimal.ONE);
102 }
103 else if (value.equals(minBid.getValue(issue))) {
104 estUtil.get(issue).put(value, BigDecimal.ZERO);
105 }
106 else {
107 estUtil.get(issue).put(value, BigDecimal.valueOf(0.5 + 0.001 *
108 (count - 0.5*(numValues-1))));
109 nonMinMaxIndex.get(issue).add(value);
110 count++;
111 }
112 }
113 }
114 }
115
116 ////////////////////////////////////////////////////////////////////////////////
117 // utility function learner fit method
118 ////////////////////////////////////////////////////////////////////////////////
119
120 /**
121 * updates the value utilities given a list of ordered Bids
122 * @param orderedBids - a list of ordered bids with ascending utility
123 */
124 public void fit(List<Bid> orderedBids) {
125 int numBids = orderedBids.size();
126 int numConstraints = numBids - 1;
127
128 Calcfc calcfc = setCalcfc(orderedBids);
129
130 double[] x = flattenEstUtil();
131 double rhobeg = 1.0;
132 double rhoend = 2.0e-4;
133 int iprint = 0;
134 int maxfun = 1000;
135
136 Cobyla.FindMinimum(calcfc, totalNonMinMax, numConstraints, x,
137 rhobeg, rhoend, iprint, maxfun);
138
139 updateEstUtil(x);
140
141 createFullOrdering();
142 }
143
144 /**
145 * the function to be minimized in fit()
146 * @param orderedBids - a list of ordered bids with ascending utility
147 * @return a Calcfc to be used in fit()
148 */
149 private Calcfc setCalcfc(List<Bid> orderedBids) {
150 int numBids = orderedBids.size();
151 Calcfc calcfc = new Calcfc() {
152
153 @Override
154 public double Compute(int n, int m, double[] x, double[] con) {
155 double[] bidUtil = new double[numBids];
156 for (int i = 0; i < numBids; i++) {
157 Bid bid = orderedBids.get(i);
158 bidUtil[i] = 0.0;
159 int baseIndex = 0;
160 for (int j = 0; j < numIssues; j++) {
161 String issue = issueOrder.get(j);
162 Value value = bid.getValue(issue);
163 int index = nonMinMaxIndex.get(issue).indexOf(value);
164 if (index >= 0) {
165 bidUtil[i] += x[baseIndex + index] * estTheta[j];
166 }
167 else {
168 bidUtil[i] += estUtil.get(issue).get(value).
169 doubleValue() * estTheta[j];
170 }
171 baseIndex += numValuesPerIssue.get(issue) - 2;
172 }
173 }
174 // constraints
175 double tolerance = 0.0;
176 for (int i = 0; i < numBids - 1; i++) {
177 con[i] = bidUtil[i+1] - (bidUtil[i] + tolerance);
178 }
179 // penalize inversions
180 double err = 0.0;
181 for (int i = 0; i < numBids - 1; i++) {
182 if (bidUtil[i] > bidUtil[i+1]) err += bidUtil[i] - bidUtil[i+1];
183 }
184 return err/n;
185 }
186 };
187 return calcfc;
188 }
189
190 /**
191 * flatten the estUtil values into a single double array
192 * @return a double array that contains the initial estimated utilities
193 */
194 private double[] flattenEstUtil() {
195 double[] x = new double[totalNonMinMax];
196 int baseIndex = 0;
197 for (String issue : issueOrder) {
198 List<Value> valuesIndex = nonMinMaxIndex.get(issue);
199 int numValues = valuesIndex.size();
200 for (int i = 0; i< numValues; i++) {
201 x[baseIndex + i] = estUtil.get(issue).
202 get(valuesIndex.get(i)).doubleValue();
203 }
204 baseIndex += numValues;
205 }
206 return x;
207 }
208
209 /**
210 * update the estUtil values form a single double array
211 * @param x - a double array that contains the calculated estimated utilities
212 */
213 private void updateEstUtil(double[] x) {
214 int baseIndex = 0;
215 for (String issue : issueOrder) {
216 List<Value> valuesIndex = nonMinMaxIndex.get(issue);
217 int numValues = valuesIndex.size();
218 for (int i = 0; i < numValues; i++) {
219 estUtil.get(issue).put(valuesIndex.get(i),
220 BigDecimal.valueOf(x[baseIndex + i]));
221 }
222 baseIndex += numValues;
223 }
224 }
225
226 /**
227 * creates full ordering of bids according to utility function
228 */
229 private void createFullOrdering() {
230 this.fullBidOrdering = new TreeMap<BigDecimal,
231 List<Bid>>(Collections.reverseOrder());
232 this.ordering(0, maxBid);
233 }
234
235 /**
236 * recursive helper method to create bid ordering
237 * @param i - counter
238 * @param bid - base bid
239 */
240 private void ordering(int i, Bid bid) {
241 if (i < issueOrder.size()) {
242 String issue = issueOrder.get(i);
243 ValueSet values = domain.getValues(issue);
244 for (Value value : values) {
245 Bid newBid = putValue(bid, issue, value);
246 BigDecimal util = getUtil(newBid);
247 List<Bid> bidsList;
248 if (fullBidOrdering.get(util) == null) bidsList = new ArrayList<Bid>();
249 else bidsList = fullBidOrdering.get(util);
250 bidsList.add(newBid);
251 fullBidOrdering.put(this.getUtil(newBid), bidsList);
252 this.ordering(i+1, newBid);
253 }
254 }
255 }
256
257 ////////////////////////////////////////////////////////////////////////////////
258 // public helper methods
259 ////////////////////////////////////////////////////////////////////////////////
260
261 /**
262 * calculates the total utility of a bid from the current parameters
263 * @param bid - a bid to calculate its utility
264 * @return BigDecimal; the estimated utility
265 */
266 public BigDecimal getUtil(Bid bid) {
267 if (bid == null) return BigDecimal.ZERO;
268 else {
269 BigDecimal totalUtil = BigDecimal.ZERO;
270 for (int i = 0; i < numIssues; i++) {
271 String issue = issueOrder.get(i);
272 Value value = bid.getValue(issue);
273 BigDecimal util = estUtil.get(issue).get(value);
274 totalUtil = totalUtil.add(util.multiply(BigDecimal.
275 valueOf(estTheta[i])));
276 }
277 return totalUtil;
278 }
279 }
280
281 /**
282 *
283 * @return the list of issues in ascending order of importance
284 */
285 public List<String> getIssues() {
286 return issueOrder;
287 }
288
289 /**
290 * retrieves the values of a specific issue
291 * @param issue - want the values from this issue
292 * @return a ValueSet of the values from the input issue
293 */
294 public ValueSet getValues(String issue) {
295 return domain.getValues(issue);
296 }
297
298 /**
299 * gets list of bids better than the given threshold from estimated utility
300 * @param threshold - the threshold value compared
301 * @param currOrderedBids - a list of current ordered bids
302 * @return a list of bids from the currOrderedBids better than the threshold
303 * in descending order
304 */
305 public List<Bid> getBetterThan(BigDecimal threshold) {
306 List<Bid> betterBids = new ArrayList<Bid>();
307 Set<Entry<BigDecimal, List<Bid>>> set = fullBidOrdering.entrySet();
308 Iterator<Entry<BigDecimal, List<Bid>>> i = set.iterator();
309 BigDecimal currUtil = BigDecimal.ONE;
310 while (currUtil.compareTo(threshold) > 0 && i.hasNext()) {
311 Map.Entry<BigDecimal, List<Bid>> map = (Map.Entry<BigDecimal,
312 List<Bid>>)i.next();
313 List<Bid> bidsList = map.getValue();
314 for (Bid bid : bidsList) {
315 betterBids.add(bid);
316 }
317 currUtil = (BigDecimal) map.getKey();
318 }
319 betterBids.add(maxBid);
320 return betterBids;
321 }
322
323 /**
324 * gets a value from input issue that is neither in maxBid or minBid
325 * @param issue - the issue we want to search the values
326 * @param index - a random index
327 * @return a value from the nonMinMaxIndex
328 */
329 public Value randomNonMinMax(String issue, int index) {
330 return nonMinMaxIndex.get(issue).get(index);
331 }
332
333 ////////////////////////////////////////////////////////////////////////////////
334 // method putValue to put a value in a bid
335 ////////////////////////////////////////////////////////////////////////////////
336
337 /**
338 * replaces one value in a bid with a new value
339 * @param originalBid - the original bid
340 * @param inputIssue - the issue of the value to replace
341 * @param inputValue - the value to replace
342 * @return - the new bid with the replaced value
343 */
344 private Bid putValue(Bid originalBid, String inputIssue, Value inputValue) {
345 Bid modifiedBid = new Bid(inputIssue, inputValue);
346 Set<String> issues = originalBid.getIssues();
347 for (String issue : issues) {
348 if (!issue.equals(inputIssue)) {
349 modifiedBid = modifiedBid.merge(new Bid(issue, originalBid.getValue(issue)));
350 }
351 }
352 return modifiedBid;
353 }
354
355}
Note: See TracBrowser for help on using the repository browser.