source: src/main/java/agents/anac/y2019/sacra/SACRA.java

Last change on this file was 204, checked in by Katsuhide Fujita, 5 years ago

Fixed errors of ANAC2019 agents
  • Property svn:executable set to *
File size: 10.3 KB
Line 
1package agents.anac.y2019.sacra;
2
3import agents.anac.y2019.sacra.yacomponents.BidUtilComparator;
4import agents.anac.y2019.sacra.yacomponents.BidUtility;
5import genius.core.AgentID;
6import genius.core.Bid;
7import genius.core.actions.Accept;
8import genius.core.actions.Action;
9import genius.core.actions.Offer;
10import genius.core.issue.IssueDiscrete;
11import genius.core.issue.ValueDiscrete;
12import genius.core.parties.AbstractNegotiationParty;
13import genius.core.parties.NegotiationInfo;
14import genius.core.uncertainty.AdditiveUtilitySpaceFactory;
15import genius.core.uncertainty.BidRanking;
16import genius.core.utility.AbstractUtilitySpace;
17import genius.core.utility.AdditiveUtilitySpace;
18import genius.core.utility.EvaluatorDiscrete;
19
20import java.util.*;
21
22public class SACRA extends AbstractNegotiationParty {
23 private final boolean DEBUG = false;
24 private final static int DEFAULT_NUMBER_OF_CANDIDATES = 20000;
25 private final double TEMPERATURE_ALPHA = 0.5;
26 private final int SA_NUMBER_OF_ITERATION = 10000;
27 private final double NEIGHBOR_WEIGHT_RANGE = 0.1;
28
29 /**
30 * Determines the ratio of weight change in the process of generating a neighbor utility space
31 */
32 private final double NEIGHBOR_CHANGE_RATIO = 0.5;
33
34 protected int numberOfCandidates = -1;
35 protected List<BidUtility> candidateOffers;
36 private Bid firstReceivedBid = null;
37 private Bid lastReceivedBid = null;
38
39 public void init(NegotiationInfo info) {
40 Set<BidUtility> candidateSet;
41 super.init(info);
42
43 if (numberOfCandidates < 0)
44 numberOfCandidates = DEFAULT_NUMBER_OF_CANDIDATES;
45
46 this.candidateOffers = new ArrayList<>();
47 for (int i = 0; i < numberOfCandidates; i++)
48 candidateOffers.add(generateRandomBidUtility());
49
50 candidateSet = new HashSet<>(candidateOffers);
51 candidateOffers = new ArrayList<>(candidateSet);
52 candidateOffers.sort(new BidUtilComparator().reversed());
53 }
54
55 @Override
56 public void receiveMessage(AgentID sender, Action action) {
57 super.receiveMessage(sender, action);
58 if (action instanceof Offer) {
59 Bid bid = ((Offer)action).getBid();
60 if (firstReceivedBid == null)
61 firstReceivedBid = bid;
62 lastReceivedBid = bid;
63 }
64 }
65
66 @Override
67 public Action chooseAction(List<Class<? extends Action>> possibleActions) {
68 double concessionRate;
69 double targetUtility;
70 double acceptProbability;
71 Bid maxUtilityBid;
72 Bid offerBid;
73
74 try {
75 maxUtilityBid = utilitySpace.getMaxUtilityBid();
76 }
77 catch (Exception e) {
78 maxUtilityBid = getNearestCandidate(1);
79 }
80
81 if (lastReceivedBid == null || firstReceivedBid == null) {
82 return new Offer(getPartyId(), maxUtilityBid);
83 }
84
85 concessionRate = Math.max(0, utilitySpace.getUtility(lastReceivedBid) - utilitySpace.getUtility(firstReceivedBid))
86 / utilitySpace.getUtility(maxUtilityBid) * 0.7;
87 targetUtility = utilitySpace.getUtility(maxUtilityBid) - concessionRate;
88 acceptProbability = (utilitySpace.getUtility(lastReceivedBid) - targetUtility)
89 / (utilitySpace.getUtility(maxUtilityBid) - targetUtility);
90
91 if (DEBUG)
92 System.out.printf("EstimatedUtil: %.3f, concessionRate: %.3f, targetUtil: %.3f, acceptProb: %.3f\n",
93 utilitySpace.getUtility(lastReceivedBid),
94 concessionRate,
95 targetUtility,
96 acceptProbability);
97
98 if (this.rand.nextDouble() < acceptProbability) {
99 return new Accept(getPartyId(), lastReceivedBid);
100 }
101
102 offerBid = this.getCandidateAboveUtil(targetUtility);
103return new Offer(getPartyId(), offerBid);
104 }
105
106 @Override
107 public String getDescription() {
108 return "Simulated Annealing-based Concession Rate controlling Agent";
109 }
110
111 @Override
112 public AbstractUtilitySpace estimateUtilitySpace() {
113 AdditiveUtilitySpace currentUtilitySpace = generateRandomUtilitySpace();
114 double currentEnergy = getEnergy(currentUtilitySpace);
115
116 AdditiveUtilitySpace nextUtilitySpace;
117 double nextEnergy;
118
119 AdditiveUtilitySpace bestUtilitySpace = currentUtilitySpace;
120 double bestEnergy = currentEnergy;
121
122 for (int nIteration = 0; nIteration < SA_NUMBER_OF_ITERATION; nIteration++) {
123 nextUtilitySpace = generateNeighborUtilitySpace(currentUtilitySpace);
124 nextEnergy = getEnergy(nextUtilitySpace);
125
126 if (nextEnergy < bestEnergy) {
127 bestUtilitySpace = nextUtilitySpace;
128 bestEnergy = nextEnergy;
129 }
130
131 if (this.rand.nextDouble() > getOverrideProbability(
132 currentEnergy, nextEnergy, getTemperature(nIteration / SA_NUMBER_OF_ITERATION))) {
133 currentUtilitySpace = nextUtilitySpace;
134 currentEnergy = nextEnergy;
135 }
136 }
137
138 return bestUtilitySpace;
139 }
140
141 /** Returns "energy" of the additive utility space (Lower is better)
142 * @param additiveUtilitySpace
143 * @return energy
144 */
145 private double getEnergy(AdditiveUtilitySpace additiveUtilitySpace) {
146 return -getAdditiveUtilitySpaceScore(additiveUtilitySpace);
147 }
148
149 /**
150 * Returns score of the additive utility space (Higher is better)
151 * @param additiveUtilitySpace
152 * @return score
153 */
154 private double getAdditiveUtilitySpaceScore(AdditiveUtilitySpace additiveUtilitySpace) {
155 BidRanking bidRank = this.userModel.getBidRanking();
156 Map<Bid, Integer> realRanks = new HashMap();
157 List<Double> estimatedUtils = new ArrayList();
158 Map<Bid, Integer> estimatedRanks = new HashMap();
159
160 for (Bid bid : bidRank.getBidOrder()) {
161 realRanks.put(bid, realRanks.size());
162 estimatedUtils.add(additiveUtilitySpace.getUtility(bid));
163 }
164 Collections.sort(estimatedUtils);
165
166 for (Bid bid : bidRank.getBidOrder()) {
167 estimatedRanks.put(bid, estimatedUtils.indexOf(additiveUtilitySpace.getUtility(bid)));
168 }
169
170 double errors = 0.0D;
171
172 for (Bid bid : bidRank.getBidOrder()) {
173 errors += Math.pow((double)(realRanks.get(bid) - estimatedRanks.get(bid)), 2);
174 }
175
176 double spearman = 1.0D - 6.0D * errors / (Math.pow((double)realRanks.size(), 3.0D) - (double)realRanks.size());
177 double lowDiff = Math.abs(bidRank.getLowUtility() - additiveUtilitySpace.getUtility(bidRank.getMinimalBid()));
178 double highDiff = Math.abs(bidRank.getHighUtility() - additiveUtilitySpace.getUtility(bidRank.getMaximalBid()));
179
180 return spearman * 10.0D + (1.0D - lowDiff) + (1.0D - highDiff);
181 }
182
183 private double getTemperature(double r) {
184 return Math.pow(TEMPERATURE_ALPHA, r);
185 }
186
187 private double getOverrideProbability(double oldEnergy, double newEnergy, double temperature) {
188 if (newEnergy <= oldEnergy)
189 return 1.0;
190 return Math.exp((oldEnergy - newEnergy) / temperature);
191 }
192
193 /**
194 * Generate a neighbor of baseUtilitySpace (only a weight or a value of an issue is changed)
195 * @param baseUtilitySpace
196 * @return neighborUtilitySpace
197 */
198 private AdditiveUtilitySpace generateNeighborUtilitySpace(AdditiveUtilitySpace baseUtilitySpace) {
199 AdditiveUtilitySpaceFactory neighborFactory = new AdditiveUtilitySpaceFactory(this.getDomain());
200 List<IssueDiscrete> issueList = neighborFactory.getIssues();
201 IssueDiscrete targetIssue = issueList.get(this.rand.nextInt(issueList.size()));
202 boolean isChangeWeight = this.rand.nextDouble() < NEIGHBOR_CHANGE_RATIO;
203
204 for (IssueDiscrete issue : neighborFactory.getIssues()) {
205 neighborFactory.setWeight(issue, baseUtilitySpace.getWeight(issue));
206
207 for (ValueDiscrete value : issue.getValues()) {
208 neighborFactory.setUtility(issue, value,
209 ((EvaluatorDiscrete)baseUtilitySpace.getEvaluator(issue)).getDoubleValue(value));
210 }
211 }
212
213 if (isChangeWeight) {
214 neighborFactory.setWeight(targetIssue,
215 Math.max(0, baseUtilitySpace.getWeight(targetIssue)
216 + (this.rand.nextDouble() - 0.5) * NEIGHBOR_WEIGHT_RANGE / issueList.size()));
217 } else {
218 ValueDiscrete targetValue = targetIssue.getValue(this.rand.nextInt(targetIssue.getNumberOfValues()));
219 double evaluatedValue = ((EvaluatorDiscrete)baseUtilitySpace.getEvaluator(targetIssue)).getDoubleValue(targetValue);
220
221 neighborFactory.setUtility(targetIssue, targetValue,
222 Math.max(0, evaluatedValue * (1 + (this.rand.nextDouble() - 0.5) * NEIGHBOR_WEIGHT_RANGE)));
223 }
224
225 neighborFactory.normalizeWeights();
226 return neighborFactory.getUtilitySpace();
227 }
228
229 private AdditiveUtilitySpace generateRandomUtilitySpace() {
230 AdditiveUtilitySpaceFactory randomFactory = new AdditiveUtilitySpaceFactory(this.getDomain());
231
232 for (IssueDiscrete issue : randomFactory.getIssues()){
233 randomFactory.setWeight(issue, this.rand.nextDouble());
234 for (ValueDiscrete value : issue.getValues()) {
235 randomFactory.setUtility(issue, value, this.rand.nextDouble());
236 }
237 }
238
239 randomFactory.normalizeWeights();
240 return randomFactory.getUtilitySpace();
241 }
242
243 protected BidUtility generateRandomBidUtility() {
244 return new BidUtility(generateRandomBid(), utilitySpace);
245 }
246
247 protected Bid getNearestCandidate(double util) {
248 int index = getNearestCandidateIndex(util);
249 return candidateOffers.get(index).getBid();
250 }
251
252 protected Bid getCandidateAboveUtil(double util) {
253 int maxIndex = getNearestCandidateIndex(util);
254 int index = this.rand.nextInt(maxIndex);
255 return candidateOffers.get(index).getBid();
256 }
257
258 protected int getNearestCandidateIndex(double util) {
259 int index;
260 int rangeMin = 0;
261 int rangeMax = candidateOffers.size() - 1;
262
263 do {
264 index = rangeMin + (rangeMax - rangeMin) / 2;
265 if (util < candidateOffers.get(index).getUtil())
266 rangeMin = index;
267 else
268 rangeMax = index;
269 } while (rangeMax - rangeMin > 1);
270
271 return index;
272 }
273
274}
Note: See TracBrowser for help on using the repository browser.