[1] | 1 | package agents.anac.y2017.agentkn.etc;
|
---|
| 2 |
|
---|
| 3 | import java.util.ArrayList;
|
---|
| 4 | import java.util.Collections;
|
---|
| 5 | import java.util.HashMap;
|
---|
| 6 | import java.util.Iterator;
|
---|
| 7 | import java.util.List;
|
---|
| 8 | import java.util.Random;
|
---|
| 9 |
|
---|
| 10 | import genius.core.Bid;
|
---|
| 11 | import genius.core.issue.Issue;
|
---|
| 12 | import genius.core.issue.IssueDiscrete;
|
---|
| 13 | import genius.core.issue.IssueInteger;
|
---|
| 14 | import genius.core.issue.IssueReal;
|
---|
| 15 | import genius.core.issue.Value;
|
---|
| 16 | import genius.core.issue.ValueInteger;
|
---|
| 17 | import genius.core.issue.ValueReal;
|
---|
| 18 | import genius.core.utility.AbstractUtilitySpace;
|
---|
| 19 |
|
---|
| 20 | public class bidSearch {
|
---|
| 21 | private AbstractUtilitySpace utilitySpace;
|
---|
| 22 | private negotiationInfo negotiationInfo; // 交渉情報
|
---|
| 23 | private Bid maxBid = null; // 最大効用値Bid
|
---|
| 24 |
|
---|
| 25 | private boolean isPrinting = false; // デバッグ用
|
---|
| 26 |
|
---|
| 27 | public bidSearch(AbstractUtilitySpace utilitySpace, negotiationInfo negotiationInfo, boolean isPrinting)
|
---|
| 28 | throws Exception {
|
---|
| 29 | this.utilitySpace = utilitySpace;
|
---|
| 30 | this.negotiationInfo = negotiationInfo;
|
---|
| 31 | this.isPrinting = isPrinting;
|
---|
| 32 |
|
---|
| 33 | initMaxBid(); // 最大効用値Bidの初期探索
|
---|
| 34 | negotiationInfo.setValueRelativeUtility(maxBid); // 相対効用値を導出する
|
---|
| 35 | }
|
---|
| 36 |
|
---|
| 37 | /**
|
---|
| 38 | * 最大効用値Bidの初期探索(最初は効用空間のタイプが不明であるため,SAを用いて探索する)
|
---|
| 39 | *
|
---|
| 40 | * @throws Exception
|
---|
| 41 | */
|
---|
| 42 | private void initMaxBid() throws Exception {
|
---|
| 43 | int tryNum = utilitySpace.getDomain().getIssues().size(); // 試行回数
|
---|
| 44 | maxBid = this.utilitySpace.getDomain().getRandomBid((Random) null);
|
---|
| 45 |
|
---|
| 46 | for (int i = 0; i < tryNum; i++) {
|
---|
| 47 | try {
|
---|
| 48 | do {
|
---|
| 49 | SimulatedAnnealingSearch(maxBid, 1.0);
|
---|
| 50 | } while (utilitySpace.getUtility(maxBid) < utilitySpace.getReservationValue());
|
---|
| 51 | if (utilitySpace.getUtility(maxBid) == 1.0) {
|
---|
| 52 | break;
|
---|
| 53 | }
|
---|
| 54 | } catch (Exception e) {
|
---|
| 55 | System.out.println("最大効用値Bidの初期探索に失敗しました");
|
---|
| 56 | e.printStackTrace();
|
---|
| 57 | }
|
---|
| 58 | }
|
---|
| 59 | }
|
---|
| 60 |
|
---|
| 61 | /**
|
---|
| 62 | * Bidを返す
|
---|
| 63 | *
|
---|
| 64 | * @param baseBid
|
---|
| 65 | * @param threshold
|
---|
| 66 | * @return
|
---|
| 67 | */
|
---|
| 68 | public Bid getBid(Bid baseBid, double threshold) {
|
---|
| 69 | Iterator var5 = negotiationInfo.getIssues().iterator();
|
---|
| 70 |
|
---|
| 71 | System.out.println("AgentKN's Threshold : " + threshold);
|
---|
| 72 | while (true) {
|
---|
| 73 | threshold = Math.max(emax(), threshold);
|
---|
| 74 | System.out.println("search threshold: " + threshold);
|
---|
| 75 | try {
|
---|
| 76 | Bid e1 = this.getBidbyAppropriateSearch(baseBid, threshold);
|
---|
| 77 | // 自分の最大効用知となるものを取得
|
---|
| 78 | List<Bid> targets = new ArrayList<>();
|
---|
| 79 | for (int i = 0; i < 10; i++) {
|
---|
| 80 | Bid e = this.getBidbyAppropriateSearch(getRandomBid(utilitySpace.getUtility(e1)), threshold);
|
---|
| 81 | System.out.println("search result--------------------------------------");
|
---|
| 82 | System.out.println("result : " + e);
|
---|
| 83 | System.out.println("frequency : " + negotiationInfo.getBidFrequcncy(e));
|
---|
| 84 | System.out.println("searched utility : " + this.utilitySpace.getUtility(e1));
|
---|
| 85 | System.out.println("---------------------------------------------------");
|
---|
| 86 | targets.add(e);
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 | // 頻度と自分の効用ちでソーと
|
---|
| 90 | // targets.sort((b1, b2) -> (sortFuncUtility(b1) >
|
---|
| 91 | // sortFuncUtility(b2)) ? 1 : 0);
|
---|
| 92 | e1 = targets.get(0);
|
---|
| 93 |
|
---|
| 94 | if (this.utilitySpace.getUtility(e1) < threshold) {
|
---|
| 95 | e1 = new Bid(this.maxBid);
|
---|
| 96 | }
|
---|
| 97 | return e1;
|
---|
| 98 | } catch (Exception var7) {
|
---|
| 99 | System.out.println("Bidの探索に失敗しました");
|
---|
| 100 | var7.printStackTrace();
|
---|
| 101 | return baseBid;
|
---|
| 102 | }
|
---|
| 103 | }
|
---|
| 104 | }
|
---|
| 105 |
|
---|
| 106 | private double sortFuncUtility(Bid aBid) {
|
---|
| 107 | int frequency = negotiationInfo.getBidFrequcncy(aBid);
|
---|
| 108 | int k = (int) (Math.log10(frequency) + 1);
|
---|
| 109 | return utilitySpace.getUtility(aBid) + Math.pow(0.1, k) * frequency;
|
---|
| 110 | }
|
---|
| 111 |
|
---|
| 112 | private boolean frequencyCheck(Bid aSearchedBid) {
|
---|
| 113 | System.out.println("check!!!!!!!!!!!!!!!!!!!!!!!");
|
---|
| 114 | List issues = this.negotiationInfo.getIssues();
|
---|
| 115 | ArrayList senders = this.negotiationInfo.getOpponents();
|
---|
| 116 | Iterator var6 = senders.iterator();
|
---|
| 117 | int point = 0;
|
---|
| 118 | while (var6.hasNext()) {
|
---|
| 119 | Object sender = var6.next();
|
---|
| 120 | Iterator var8 = issues.iterator();
|
---|
| 121 | while (var8.hasNext()) {
|
---|
| 122 | Issue issue = (Issue) var8.next();
|
---|
| 123 | Value freqValue = this.negotiationInfo.getHighFrequencyValue(sender, issue);
|
---|
| 124 | if (aSearchedBid.getValues().get(issue).equals(freqValue))
|
---|
| 125 | point++;
|
---|
| 126 | }
|
---|
| 127 | }
|
---|
| 128 | System.out.println("searched bid frequency point : " + point);
|
---|
| 129 | return point > issues.size() * 0.6;
|
---|
| 130 | }
|
---|
| 131 |
|
---|
| 132 | // Bidの探索
|
---|
| 133 | private static int SA_ITERATION = 1;
|
---|
| 134 |
|
---|
| 135 | private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
|
---|
| 136 | Bid bid = new Bid(baseBid);
|
---|
| 137 | try {
|
---|
| 138 | // 線形効用空間用の探索
|
---|
| 139 | if (negotiationInfo.isLinerUtilitySpace()) {
|
---|
| 140 | bid = relativeUtilitySearch(threshold);
|
---|
| 141 | if (utilitySpace.getUtility(bid) < threshold) {
|
---|
| 142 | negotiationInfo.utilitySpaceTypeisNonLiner();
|
---|
| 143 | } // 探索に失敗した場合,非線形効用空間用の探索に切り替える
|
---|
| 144 | }
|
---|
| 145 |
|
---|
| 146 | // 非線形効用空間用の探索
|
---|
| 147 | if (!negotiationInfo.isLinerUtilitySpace()) {
|
---|
| 148 | Bid currentBid = null;
|
---|
| 149 | double currentBidUtil = 0;
|
---|
| 150 | double min = 1.0;
|
---|
| 151 | for (int i = 0; i < SA_ITERATION; i++) {
|
---|
| 152 | currentBid = SimulatedAnnealingSearch(bid, threshold);
|
---|
| 153 | currentBidUtil = utilitySpace.getUtility(currentBid);
|
---|
| 154 | System.out.println(currentBidUtil);
|
---|
| 155 | bid = currentBid;
|
---|
| 156 | if (currentBidUtil <= min && currentBidUtil >= threshold) { // 効用値は推定値を用いている。
|
---|
| 157 | bid = new Bid(currentBid);
|
---|
| 158 | min = currentBidUtil;
|
---|
| 159 | }
|
---|
| 160 | }
|
---|
| 161 | }
|
---|
| 162 | } catch (Exception e) {
|
---|
| 163 | System.out.println("SA探索に失敗しました");
|
---|
| 164 | System.out.println("Problem with received bid(SA:last):" + e.getMessage() + ". cancelling bidding");
|
---|
| 165 | }
|
---|
| 166 | return bid;
|
---|
| 167 | }
|
---|
| 168 |
|
---|
| 169 | /**
|
---|
| 170 | * 論点ごとに最適化を行う探索
|
---|
| 171 | *
|
---|
| 172 | * @param threshold
|
---|
| 173 | * @return
|
---|
| 174 | * @throws Exception
|
---|
| 175 | */
|
---|
| 176 |
|
---|
| 177 | private Bid relativeUtilitySearch(double threshold) throws Exception {
|
---|
| 178 | Bid bid = new Bid(maxBid);
|
---|
| 179 | double d = threshold - 1.0; // 最大効用値との差
|
---|
| 180 | double concessionSum = 0.0; // 減らした効用値の和
|
---|
| 181 | double relativeUtility = 0.0;
|
---|
| 182 | HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiationInfo.getValueRelativeUtility();
|
---|
| 183 | List<Issue> randomIssues = negotiationInfo.getIssues();
|
---|
| 184 | Collections.shuffle(randomIssues);
|
---|
| 185 | ArrayList<Value> randomValues = null;
|
---|
| 186 | for (Issue issue : randomIssues) {
|
---|
| 187 | randomValues = negotiationInfo.getValues(issue);
|
---|
| 188 | Collections.shuffle(randomValues);
|
---|
| 189 | for (Value value : randomValues) {
|
---|
| 190 | relativeUtility = valueRelativeUtility.get(issue).get(value); // 最大効用値を基準とした相対効用値
|
---|
| 191 | if (d <= concessionSum + relativeUtility) {
|
---|
| 192 | bid = bid.putValue(issue.getNumber(), value);
|
---|
| 193 | concessionSum += relativeUtility;
|
---|
| 194 | break;
|
---|
| 195 | }
|
---|
| 196 | }
|
---|
| 197 | }
|
---|
| 198 | return bid;
|
---|
| 199 | }
|
---|
| 200 |
|
---|
| 201 | // SA
|
---|
| 202 | static double START_TEMPERATURE = 1.0; // 開始温度
|
---|
| 203 | static double END_TEMPERATURE = 0.0001; // 終了温度
|
---|
| 204 | static double COOL = 0.999; // 冷却度
|
---|
| 205 | static int STEP = 1;// 変更する幅
|
---|
| 206 | static int STEP_NUM = 1; // 変更する回数
|
---|
| 207 |
|
---|
| 208 | private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold) throws Exception {
|
---|
| 209 | Bid currentBid = new Bid(baseBid);
|
---|
| 210 | double currenBidUtil = this.utilitySpace.getUtility(baseBid);
|
---|
| 211 | Bid nextBid = null;
|
---|
| 212 | double nextBidUtil = 0.0D;
|
---|
| 213 | ArrayList targetBids = new ArrayList();
|
---|
| 214 | double targetBidUtil = 0.0D;
|
---|
| 215 | Random randomnr = new Random();
|
---|
| 216 | double currentTemperature = START_TEMPERATURE;
|
---|
| 217 | double newCost = 1.0D;
|
---|
| 218 | double currentCost = 1.0D;
|
---|
| 219 |
|
---|
| 220 | for (List issues = this.negotiationInfo
|
---|
| 221 | .getIssues(); currentTemperature > END_TEMPERATURE; currentTemperature *= COOL) {
|
---|
| 222 | nextBid = new Bid(currentBid);
|
---|
| 223 |
|
---|
| 224 | for (int i = 0; i < STEP_NUM; ++i) {
|
---|
| 225 | int issueIndex = randomnr.nextInt(issues.size());
|
---|
| 226 | Issue issue = (Issue) issues.get(issueIndex);
|
---|
| 227 | ArrayList values = this.negotiationInfo.getValues(issue);
|
---|
| 228 | int valueIndex = randomnr.nextInt(values.size());
|
---|
| 229 | nextBid = nextBid.putValue(issue.getNumber(), (Value) values.get(valueIndex));
|
---|
| 230 | nextBidUtil = this.utilitySpace.getUtility(nextBid);
|
---|
| 231 | if (this.maxBid == null || nextBidUtil >= this.utilitySpace.getUtility(this.maxBid)) {
|
---|
| 232 | this.maxBid = new Bid(nextBid);
|
---|
| 233 | }
|
---|
| 234 | }
|
---|
| 235 |
|
---|
| 236 | newCost = Math.abs(threshold - nextBidUtil);
|
---|
| 237 | currentCost = Math.abs(threshold - currenBidUtil);
|
---|
| 238 | double p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
|
---|
| 239 | if (newCost < currentCost || p > randomnr.nextDouble()) {
|
---|
| 240 | currentBid = new Bid(nextBid);
|
---|
| 241 | currenBidUtil = nextBidUtil;
|
---|
| 242 | }
|
---|
| 243 |
|
---|
| 244 | if (currenBidUtil >= threshold) {
|
---|
| 245 | if (targetBids.size() == 0) {
|
---|
| 246 | targetBids.add(new Bid(currentBid));
|
---|
| 247 | targetBidUtil = this.utilitySpace.getUtility(currentBid);
|
---|
| 248 | } else if (currenBidUtil < targetBidUtil) {
|
---|
| 249 | targetBids.clear();
|
---|
| 250 | targetBids.add(new Bid(currentBid));
|
---|
| 251 | targetBidUtil = this.utilitySpace.getUtility(currentBid);
|
---|
| 252 | } else if (currenBidUtil == targetBidUtil) {
|
---|
| 253 | targetBids.add(new Bid(currentBid));
|
---|
| 254 | }
|
---|
| 255 | }
|
---|
| 256 | }
|
---|
| 257 |
|
---|
| 258 | if (targetBids.size() == 0) {
|
---|
| 259 | return new Bid(baseBid);
|
---|
| 260 | } else {
|
---|
| 261 | return new Bid((Bid) targetBids.get(randomnr.nextInt(targetBids.size())));
|
---|
| 262 | }
|
---|
| 263 | }
|
---|
| 264 |
|
---|
| 265 | /**
|
---|
| 266 | * @return a random bid with high enough utility value.
|
---|
| 267 | * @throws Exception
|
---|
| 268 | * if we can't compute the utility (eg no evaluators have been
|
---|
| 269 | * set) or when other evaluators than a DiscreteEvaluator are
|
---|
| 270 | * present in the util space.
|
---|
| 271 | */
|
---|
| 272 | private Bid getRandomBid(double minUtil) throws Exception {
|
---|
| 273 | HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
|
---|
| 274 | // <issuenumber,chosen
|
---|
| 275 | // value
|
---|
| 276 | // string>
|
---|
| 277 | List<Issue> issues = utilitySpace.getDomain().getIssues();
|
---|
| 278 | Random randomnr = new Random();
|
---|
| 279 |
|
---|
| 280 | // create a random bid with utility>MINIMUM_BID_UTIL.
|
---|
| 281 | // note that this may never succeed if you set MINIMUM too high!!!
|
---|
| 282 | // in that case we will search for a bid till the time is up (3 minutes)
|
---|
| 283 | // but this is just a simple agent.
|
---|
| 284 | Bid bid = null;
|
---|
| 285 | do {
|
---|
| 286 | for (Issue lIssue : issues) {
|
---|
| 287 | switch (lIssue.getType()) {
|
---|
| 288 | case DISCRETE:
|
---|
| 289 | IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
|
---|
| 290 | int optionIndex = randomnr.nextInt(lIssueDiscrete.getNumberOfValues());
|
---|
| 291 | values.put(lIssue.getNumber(), lIssueDiscrete.getValue(optionIndex));
|
---|
| 292 | break;
|
---|
| 293 | case REAL:
|
---|
| 294 | IssueReal lIssueReal = (IssueReal) lIssue;
|
---|
| 295 | int optionInd = randomnr.nextInt(lIssueReal.getNumberOfDiscretizationSteps() - 1);
|
---|
| 296 | values.put(lIssueReal.getNumber(),
|
---|
| 297 | new ValueReal(lIssueReal.getLowerBound()
|
---|
| 298 | + (lIssueReal.getUpperBound() - lIssueReal.getLowerBound()) * (double) (optionInd)
|
---|
| 299 | / (double) (lIssueReal.getNumberOfDiscretizationSteps())));
|
---|
| 300 | break;
|
---|
| 301 | case INTEGER:
|
---|
| 302 | IssueInteger lIssueInteger = (IssueInteger) lIssue;
|
---|
| 303 | int optionIndex2 = lIssueInteger.getLowerBound()
|
---|
| 304 | + randomnr.nextInt(lIssueInteger.getUpperBound() - lIssueInteger.getLowerBound());
|
---|
| 305 | values.put(lIssueInteger.getNumber(), new ValueInteger(optionIndex2));
|
---|
| 306 | break;
|
---|
| 307 | default:
|
---|
| 308 | throw new Exception("issue type " + lIssue.getType() + " not supported by SimpleAgent2");
|
---|
| 309 | }
|
---|
| 310 | }
|
---|
| 311 | bid = new Bid(utilitySpace.getDomain(), values);
|
---|
| 312 | } while (utilitySpace.getUtility(bid) < minUtil);
|
---|
| 313 |
|
---|
| 314 | return bid;
|
---|
| 315 | }
|
---|
| 316 |
|
---|
| 317 | private double emax() {
|
---|
| 318 | double ave = 0.0D;
|
---|
| 319 | double extra = 0.0D;
|
---|
| 320 | ArrayList opponents = negotiationInfo.getOpponents();
|
---|
| 321 |
|
---|
| 322 | double sd = 0.0D;
|
---|
| 323 | for (Iterator i = opponents.iterator(); i.hasNext(); extra = sd) {
|
---|
| 324 | Object sender = i.next();
|
---|
| 325 | if (negotiationInfo.getPartnerBidNum(sender) % 10 == 0) {
|
---|
| 326 | ave = 0.0D;
|
---|
| 327 | extra = 0.0D;
|
---|
| 328 | }
|
---|
| 329 |
|
---|
| 330 | double m = negotiationInfo.getAverage(sender);
|
---|
| 331 | sd = negotiationInfo.getStandardDeviation(sender);
|
---|
| 332 | ave = m;
|
---|
| 333 | }
|
---|
| 334 |
|
---|
| 335 | double d = Math.sqrt(3) * sd / Math.sqrt(ave * (1 - ave));
|
---|
| 336 |
|
---|
| 337 | return ave + (1 - ave) * d;
|
---|
| 338 | }
|
---|
| 339 | } |
---|