[200] | 1 | package agents.anac.y2019.sacra;
|
---|
| 2 |
|
---|
[204] | 3 | import agents.anac.y2019.sacra.yacomponents.BidUtilComparator;
|
---|
| 4 | import agents.anac.y2019.sacra.yacomponents.BidUtility;
|
---|
[200] | 5 | import genius.core.AgentID;
|
---|
| 6 | import genius.core.Bid;
|
---|
| 7 | import genius.core.actions.Accept;
|
---|
| 8 | import genius.core.actions.Action;
|
---|
| 9 | import genius.core.actions.Offer;
|
---|
| 10 | import genius.core.issue.IssueDiscrete;
|
---|
| 11 | import genius.core.issue.ValueDiscrete;
|
---|
| 12 | import genius.core.parties.AbstractNegotiationParty;
|
---|
| 13 | import genius.core.parties.NegotiationInfo;
|
---|
| 14 | import genius.core.uncertainty.AdditiveUtilitySpaceFactory;
|
---|
| 15 | import genius.core.uncertainty.BidRanking;
|
---|
| 16 | import genius.core.utility.AbstractUtilitySpace;
|
---|
| 17 | import genius.core.utility.AdditiveUtilitySpace;
|
---|
| 18 | import genius.core.utility.EvaluatorDiscrete;
|
---|
| 19 |
|
---|
| 20 | import java.util.*;
|
---|
| 21 |
|
---|
| 22 | public 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);
|
---|
| 103 | return 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 | }
|
---|