source: src/test/java/negotiator/analysis/ParetoTest.java

Last change on this file was 127, checked in by Wouter Pasman, 6 years ago

#41 ROLL BACK of rev.126 . So this version is equal to rev. 125

File size: 9.3 KB
Line 
1package negotiator.analysis;
2
3import static org.junit.Assert.assertNull;
4
5import java.io.IOException;
6import java.lang.management.ManagementFactory;
7import java.lang.management.ThreadMXBean;
8import java.util.ArrayList;
9import java.util.List;
10
11import org.junit.Before;
12import org.junit.Test;
13import org.xml.sax.Attributes;
14import org.xml.sax.SAXException;
15import org.xml.sax.XMLReader;
16import org.xml.sax.helpers.DefaultHandler;
17import org.xml.sax.helpers.XMLReaderFactory;
18
19import genius.core.Domain;
20import genius.core.DomainImpl;
21import genius.core.analysis.BidPoint;
22import genius.core.analysis.BidSpace;
23import genius.core.analysis.pareto.ParetoFrontierF;
24import genius.core.analysis.pareto.PartialBidPoint;
25import genius.core.bidding.BidDetails;
26import genius.core.boaframework.SortedOutcomeSpace;
27import genius.core.misc.Range;
28import genius.core.qualitymeasures.ScenarioInfo;
29import genius.core.utility.AdditiveUtilitySpace;
30import genius.domains.DomainInstaller;
31
32/**
33 * This class can be used to test if the implementation of the Pareto frontier
34 * algorithm in BidSpace returns the correct results on each domain. The
35 * efficient algorithm is compared against a simple bruteforce algorithm.
36 *
37 * No effort was made to optimize the bruteforce algorithm as I wanted to be
38 * sure that it is correct. Therefore, it is not advised to check domains with
39 * more than 200.000 bids.
40 *
41 * @author Mark Hendrikx
42 */
43public class ParetoTest {
44
45 private static final double EPSILON = 0.000000001;
46
47 @Before
48 public void before() throws IOException {
49 DomainInstaller.run();
50 }
51
52 @Test
53 public void testPareto() throws Exception {
54 process();
55 }
56
57 class SimpleTimer {
58 ThreadMXBean bean = ManagementFactory.getThreadMXBean();
59 long start = bean.getCurrentThreadUserTime();
60 long end;
61
62 public void stop() {
63 end = bean.getCurrentThreadUserTime();
64 }
65
66 public double time() {
67 return (end - start) / 1000000000.;
68 }
69 }
70
71 /**
72 * Simple method to compare if the algorithm for calculating the Pareto-bids
73 * in the BidSpace class returns the right results.
74 *
75 * @param dir
76 * in which Genius is installed
77 * @throws Exception
78 * when an error occurs on parsing the files.
79 */
80 public void process() throws Exception {
81 ArrayList<ScenarioInfo> domains = parseDomainFile();
82 ThreadMXBean bean = ManagementFactory.getThreadMXBean();
83
84 for (ScenarioInfo domainSt : domains) {
85 System.out.println("testing pareto on domain " + domainSt);
86 // 1. Load the domain
87 Domain domain = new DomainImpl(domainSt.getDomain());
88 AdditiveUtilitySpace utilitySpaceA, utilitySpaceB;
89 utilitySpaceA = new AdditiveUtilitySpace(domain,
90 domainSt.getPrefProfA());
91 utilitySpaceB = new AdditiveUtilitySpace(domain,
92 domainSt.getPrefProfB());
93 System.out.println("Timing for " + domain.getName() + "("
94 + domain.getNumberOfPossibleBids() + "):");
95
96 List<BidPoint> realParetoBids = null;
97
98 // 2. Determine all Pareto-bids with various algorithms
99
100 SimpleTimer bruteForceT = new SimpleTimer();
101 if (domain.getNumberOfPossibleBids() < 10000) {
102 realParetoBids = bruteforceParetoBids(domain, utilitySpaceA,
103 utilitySpaceB);
104 }
105 bruteForceT.stop();
106
107 SimpleTimer bidSpaceT = new SimpleTimer();
108 BidSpace space = new BidSpace(utilitySpaceA, utilitySpaceB, true);
109 List<BidPoint> estimatedParetoBids = space.getParetoFrontier();
110 bidSpaceT.stop();
111
112 SimpleTimer fastT = new SimpleTimer();
113 List<BidPoint> fastPareto = doFastPareto(utilitySpaceA,
114 utilitySpaceB);
115 fastT.stop();
116
117 // 3. Check if there is a difference in the output
118 if (realParetoBids != null) {
119 assertNull(
120 "Problem in estimatedPareto with domain "
121 + domain.getName(),
122 checkValidity(estimatedParetoBids, realParetoBids));
123 }
124
125 assertNull("Problem in fastPareto with domain " + domain.getName(),
126 checkValidity(fastPareto, estimatedParetoBids));
127
128 System.out.println("bruteforce search:" + (realParetoBids == null
129 ? "skipped" : bruteForceT.time()));
130 System.out.println("bidSpace search:" + bidSpaceT.time());
131 System.out.println("fast search:" + fastT.time());
132 }
133 System.out.println("Finished processing domains");
134 }
135
136 /**
137 * Does the heavy plumbing job
138 *
139 * @throws Exception
140 *
141 */
142 private List<BidPoint> doFastPareto(AdditiveUtilitySpace utilitySpaceA,
143 AdditiveUtilitySpace utilitySpaceB) throws Exception {
144
145 ParetoFrontierF fastparetof = new ParetoFrontierF(utilitySpaceA,
146 utilitySpaceB);
147
148 ArrayList<BidPoint> bidpoints = new ArrayList<BidPoint>();
149 for (PartialBidPoint point : fastparetof.getFrontier()) {
150 bidpoints.add(new BidPoint(null, point.utilA(), point.utilB()));
151 }
152 return bidpoints;
153 }
154
155 /**
156 * Check if the output of the efficient algorithm and the brutefore
157 * algorithm to calculate the Pareto-optimal bids are identical.
158 *
159 * @param estimatedParetoBids
160 * Pareto-bids as estimated by an efficient algorithm in the
161 * BidSpace class.
162 * @param realParetoBids
163 * Pareto-bids as calculated by the bruteforce algorithm.
164 * @return null if sets are equal, or non-null string describing difference.
165 */
166 private static String checkValidity(List<BidPoint> set1,
167 List<BidPoint> set2) {
168 if (set1.size() != set2.size()) {
169 return "pareto sets are not equal size: " + set1.size() + " versus "
170 + set2.size();
171 }
172 for (BidPoint paretoBid : set1) {
173 boolean found = false;
174 for (int a = 0; a < set2.size(); a++) {
175 if (Math.abs(set2.get(a).getUtilityA()
176 - paretoBid.getUtilityA()) < EPSILON
177 && Math.abs(set2.get(a).getUtilityB()
178 - paretoBid.getUtilityB()) < EPSILON) {
179 found = true;
180 break;
181 }
182 }
183 if (!found) {
184 return "set 2 does not contain pareto bid " + paretoBid;
185 }
186 }
187
188 return null;
189 }
190
191 /**
192 * Parses the domainrepository and returns a set of domain-objects
193 * containing all information.
194 *
195 * @param dir
196 * @return set of domain-objects
197 * @throws Exception
198 */
199 private static ArrayList<ScenarioInfo> parseDomainFile() throws Exception {
200 XMLReader xr = XMLReaderFactory.createXMLReader();
201 DomainParser handler = new DomainParser();
202 xr.setContentHandler(handler);
203 xr.setErrorHandler(handler);
204 xr.parse("paretotestdomainrepository.xml");
205
206 return handler.getDomains();
207 }
208
209 /**
210 * Bruteforce algorithm to calculate the Pareto-bids.
211 *
212 * @param domain
213 * @param spaceA
214 * @param spaceB
215 * @return set of Pareto-bids
216 */
217 private static ArrayList<BidPoint> bruteforceParetoBids(Domain domain,
218 AdditiveUtilitySpace spaceA, AdditiveUtilitySpace spaceB) {
219 SortedOutcomeSpace outcomeSpaceA = new SortedOutcomeSpace(spaceA);
220 ArrayList<BidPoint> paretoBids = new ArrayList<BidPoint>();
221 try {
222 for (BidDetails bid : outcomeSpaceA.getAllOutcomes()) {
223 double utilA = spaceA.getUtility(bid.getBid());
224 double utilB = spaceB.getUtility(bid.getBid());
225 boolean found = false;
226
227 for (BidDetails otherBid : outcomeSpaceA
228 .getBidsinRange(new Range(utilA - 0.01, 1.1))) { // -0.01
229 // as
230 // we
231 // want
232 // to
233 // include
234 // duplicates
235 if ((otherBid != bid
236 && ((spaceA.getUtility(otherBid.getBid()) > utilA
237 && spaceB.getUtility(
238 otherBid.getBid()) >= utilB))
239 || (otherBid != bid
240 && spaceA.getUtility(
241 otherBid.getBid()) >= utilA
242 && spaceB.getUtility(
243 otherBid.getBid()) > utilB))) {
244 found = true;
245 break;
246 }
247 }
248 if (!found) {
249 paretoBids.add(new BidPoint(bid.getBid(),
250 bid.getMyUndiscountedUtil(),
251 spaceB.getUtility(bid.getBid())));
252 }
253 }
254 } catch (Exception e) {
255 e.printStackTrace();
256 }
257 return paretoBids;
258 }
259
260 /**
261 * Create an XML parser to parse the domainrepository.
262 */
263 static class DomainParser extends DefaultHandler {
264
265 ScenarioInfo domain = null;
266 ArrayList<ScenarioInfo> domains = new ArrayList<ScenarioInfo>();
267
268 @Override
269 public void startElement(String nsURI, String strippedName,
270 String tagName, Attributes attributes) throws SAXException {
271 if (tagName.equals("domainRepItem") && attributes.getLength() > 0) {
272 domain = new ScenarioInfo(
273 attributes.getValue("url").substring(5));
274 } else if (tagName.equals("profile")) {
275 if (domain.getPrefProfA() == null) {
276 domain.setPrefProfA(
277 attributes.getValue("url").substring(5));
278 } else if (domain.getPrefProfB() == null) {
279 domain.setPrefProfB(
280 attributes.getValue("url").substring(5));
281 } else {
282 System.out.println(
283 "WARNING: Violation of two preference profiles per domain assumption for "
284 + strippedName);
285 }
286 }
287
288 }
289
290 @Override
291 public void endElement(String nsURI, String strippedName,
292 String tagName) throws SAXException {
293 // domain is not null check is required, as the domainRepItem is
294 // used in multiple contexts
295 if (tagName.equals("domainRepItem") && domain != null) {
296 domains.add(domain);
297 domain = null;
298 }
299 }
300
301 public ArrayList<ScenarioInfo> getDomains() {
302 return domains;
303 }
304 }
305
306}
Note: See TracBrowser for help on using the repository browser.