source: src/main/java/agents/anac/y2019/saga/SAGA.java@ 244

Last change on this file since 244 was 202, checked in by Katsuhide Fujita, 6 years ago

Add ANAC 2019 agents (3)
  • Property svn:executable set to *
File size: 13.8 KB
Line 
1package agents.anac.y2019.saga;
2
3import java.util.*;
4
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;
19import genius.core.boaframework.SortedOutcomeSpace;
20import genius.core.uncertainty.UserModel;
21
22
23public class SAGA extends AbstractNegotiationParty {
24 private Random rnd = new Random();
25
26 private Bid lastOffer;
27 private boolean isFirst = true;
28 private double firstUtil = 0.95; // 相手の最初のofferの効用値
29
30// // テスト用
31// int round = -1;
32// private SortedOutcomeSpace sortedOS;
33
34 @Override
35 public void init(NegotiationInfo info) {
36 super.init(info);
37 }
38
39 @Override
40 public Action chooseAction(List<Class<? extends Action>> possibleActions) {
41 double time = timeline.getTime();
42 double target = getTarget(time);
43
44 ////System.out.println("target = " + target);
45
46 // Check for acceptance if we have received an offer
47 if (lastOffer != null) {
48 double util = utilitySpace.getUtility(lastOffer);
49 if (isAcceptable(time, target, util))
50 return new Accept(getPartyId(), lastOffer);
51 }
52
53// // 実験時に見やすいようにスリープ
54// try {
55// Thread.sleep(50);
56// } catch (Exception e) {
57// System.out.println(e);
58// }
59
60 // Otherwise, send out a random offer above the target utility
61 return new Offer(getPartyId(), generateRandomBidAboveTarget(target));
62
63// // テスト用 線形に時間譲歩
64// return new Offer(getPartyId(), sortedOS.getBidNearUtility(1 - timeline.getTime()).getBid());
65
66// // テスト用 BidRankingのBidを順に提案
67// List<Bid> bidOrd = userModel.getBidRanking().getBidOrder();
68// if (round < bidOrd.size() - 1) round++;
69// return new Offer(getPartyId(), bidOrd.get(round));
70 }
71
72 // accept関数
73 private boolean isAcceptable(double time, double target, double util) {
74 // RV以下の提案はすべてReject
75 if (util < utilitySpace.getReservationValue()) return false;
76
77 double timeA = 0.6; // target以下にAccept率を与え始める時刻
78 double timeB = 0.997; // すべてのbidにAccept率を与え始める時刻
79
80 if (time <= timeA) {
81 double acceptProb = Math.pow((util - target) / (1.0 - target), Math.pow(3, (0.5 - time) * 2));
82 return (rnd.nextDouble() < acceptProb);
83 } else if (time >= timeB) {
84 double acceptProb = Math.pow(util, 2);
85 return (rnd.nextDouble() < acceptProb);
86 }
87
88 // 時刻が timeA < time < timeB のとき
89 double APatT = 0.15 * Math.pow((time - timeA) / (1 - timeA), 2);
90 double acceptBase = target - (1 - target) * (time - timeA) / (1 - timeA);
91
92 if (util > target) {
93 double acceptProb = APatT + (1.0 - APatT) * Math.pow((util - target) / (1.0 - target), Math.pow(3, (0.5 - time) * 2));
94 return (rnd.nextDouble() < acceptProb);
95 } else if (util > acceptBase) {
96 double acceptProb = APatT * Math.pow((util - acceptBase) / (target - acceptBase), 2);
97 return (rnd.nextDouble() < acceptProb);
98 }
99 return false;
100 }
101
102 // 譲歩関数
103 private double getTarget(double time) {
104 double A = 0.6; // どこまで譲歩するか決めるパラメータ
105 double B = 5; // 譲歩速度(1-time^B)
106
107 double targetMin = firstUtil + A * (1 - firstUtil);
108 if (targetMin < utilitySpace.getReservationValue())
109 targetMin = utilitySpace.getReservationValue();
110 return targetMin + (1.0 - targetMin) * (1.0 - Math.pow(time, B));
111 }
112
113 private Bid generateRandomBidAboveTarget(double target) {
114 Bid randomBid;
115 double util;
116 int i = 0;
117 int maxLoop = 500;
118
119 // try to find a bid above the target utility
120 do {
121 randomBid = generateRandomBid();
122 util = utilitySpace.getUtility(randomBid);
123 }
124 while (util < target && i++ < maxLoop);
125
126 try {
127 if (i >= maxLoop)
128 return utilitySpace.getMaxUtilityBid();
129 } catch (Exception e) {
130 // Bidが一つもないドメインなんて普通ありえないのでここには来ないはず
131 System.out.println("Exception in generateRandomBidAboveTarget:" + e);
132 }
133 return randomBid;
134 }
135
136 @Override
137 public void receiveMessage(AgentID sender, Action action) {
138 if (action instanceof Offer) {
139 lastOffer = ((Offer) action).getBid();
140
141 if (isFirst) {
142 firstUtil = utilitySpace.getUtility(lastOffer);
143 isFirst = false;
144 }
145 }
146 }
147
148 @Override
149 public String getDescription() {
150 return "Simple Agent based on Genetic Algorithm";
151 }
152
153 // ここをGAでやってみたいと思います
154 @Override
155 public AbstractUtilitySpace estimateUtilitySpace() {
156 int popSize = 500; // 集団サイズ
157 int maxGeneration = 200; // 打ち切り世代数
158 double crossRate = 3.0; // 交叉回数 = popSize * crossRate
159
160 // 初期集団の生成
161 List<AbstractUtilitySpace> population = new ArrayList<>();
162 for (int i = 0; i < popSize * (1.0 + crossRate); i++) {
163 population.add(generateRandomUtilitySpace());
164 }
165
166 // maxGeneration世代まで繰り返す
167 for (int gen = 0; gen < maxGeneration; gen++) {
168 ////System.out.print("gen " + gen + ": ");
169
170 // 適応度関数の計算
171 List<Double> fitnessList = new ArrayList<>();
172 for (AbstractUtilitySpace ind : population) {
173 fitnessList.add(fitness(ind, false));
174 }
175
176 // ルーレット選択
177 population = selectByRoulette(population, fitnessList, popSize);
178
179 // 交叉と突然変異
180 int parentSize = population.size();
181 for (int i = 0; i < popSize * crossRate; i++) {
182 AbstractUtilitySpace parent1 = population.get(rnd.nextInt(parentSize));
183 AbstractUtilitySpace parent2 = population.get(rnd.nextInt(parentSize));
184 AbstractUtilitySpace child = crossover((AdditiveUtilitySpace) parent1, (AdditiveUtilitySpace) parent2);
185 population.add(child);
186 }
187 }
188
189 // 適応度関数の計算
190 List<Double> fitnessList = new ArrayList<>();
191 for (AbstractUtilitySpace ind : population) {
192 fitnessList.add(fitness(ind, false));
193 }
194
195 // 適応度が最大の要素を求める
196 double maxFit = -1.0;
197 int maxIndex = -1;
198 for (int i = 0; i < population.size(); i++) {
199 if (fitnessList.get(i) > maxFit) {
200 maxFit = fitnessList.get(i);
201 maxIndex = i;
202 }
203 }
204
205 ////System.out.println("最終結果:\n" + population.get(maxIndex).toString());
206
207// // テスト用
208// sortedOS = new SortedOutcomeSpace(population.get(maxIndex));
209
210 return population.get(maxIndex);
211 }
212
213 private AbstractUtilitySpace generateRandomUtilitySpace() {
214 AdditiveUtilitySpaceFactory additiveUtilitySpaceFactory = new AdditiveUtilitySpaceFactory(getDomain());
215 List<IssueDiscrete> issues = additiveUtilitySpaceFactory.getIssues();
216 for (IssueDiscrete i : issues) {
217 additiveUtilitySpaceFactory.setWeight(i, rnd.nextDouble());
218 for (ValueDiscrete v : i.getValues())
219 additiveUtilitySpaceFactory.setUtility(i, v, rnd.nextDouble());
220 }
221
222 // Normalize the weights, since we picked them randomly in [0, 1]
223 additiveUtilitySpaceFactory.normalizeWeights();
224
225 // The factory is done with setting all parameters, now return the estimated utility space
226 return additiveUtilitySpaceFactory.getUtilitySpace();
227 }
228
229 // 交叉と突然変異を行います
230 private AbstractUtilitySpace crossover(AdditiveUtilitySpace parent1, AdditiveUtilitySpace parent2) {
231 double alpha = 0.3; // BLX-alphaの値
232 double mutateProb = 0.005; // 突然変異確率
233 double low, high;
234 double w1, w2, wChild;
235
236 AdditiveUtilitySpaceFactory additiveUtilitySpaceFactory = new AdditiveUtilitySpaceFactory(getDomain());
237 List<IssueDiscrete> issues = additiveUtilitySpaceFactory.getIssues();
238 for (IssueDiscrete i : issues) {
239 // 論点の重み
240 w1 = parent1.getWeight(i);
241 w2 = parent2.getWeight(i);
242 low = Math.min(w1, w2) - alpha * Math.abs(w1 - w2);
243 high = Math.max(w1, w2) + alpha * Math.abs(w1 - w2);
244 wChild = rnd.nextDouble() * (high - low) + low;
245 if (wChild < 0.01) wChild = 0.01;
246 additiveUtilitySpaceFactory.setWeight(i, wChild);
247 //突然変異
248 if (rnd.nextDouble() < mutateProb)
249 additiveUtilitySpaceFactory.setWeight(i, rnd.nextDouble());
250
251 for (ValueDiscrete v : i.getValues()) {
252 // 選択肢の評価値
253 w1 = ((EvaluatorDiscrete) parent1.getEvaluator(i)).getDoubleValue(v);
254 w2 = ((EvaluatorDiscrete) parent2.getEvaluator(i)).getDoubleValue(v);
255 low = Math.min(w1, w2) - alpha * Math.abs(w1 - w2);
256 high = Math.max(w1, w2) + alpha * Math.abs(w1 - w2);
257 wChild = rnd.nextDouble() * (high - low) + low;
258 if (wChild < 0.01) wChild = 0.01;
259 additiveUtilitySpaceFactory.setUtility(i, v, wChild);
260 //突然変異
261 if (rnd.nextDouble() < mutateProb)
262 additiveUtilitySpaceFactory.setUtility(i, v, rnd.nextDouble());
263 }
264
265 /* 正規分布で交叉
266 if (rnd.nextBoolean())
267 wChild = rnd.nextGaussian() * Math.abs(w1 - w2) + Math.min(w1, w2);
268 else
269 wChild = rnd.nextGaussian() * Math.abs(w1 - w2) + Math.max(w1, w2);
270 */
271 }
272
273 // Normalize the weights
274 additiveUtilitySpaceFactory.normalizeWeights();
275
276 return additiveUtilitySpaceFactory.getUtilitySpace();
277 }
278
279 // 適応度関数
280 private double fitness(AbstractUtilitySpace individual, boolean print) {
281 BidRanking bidRank = userModel.getBidRanking();
282 List<Double> utilList = new ArrayList<>(); // ランキング下位から上位の予測効用値
283
284 for (Bid b : bidRank.getBidOrder()) {
285 utilList.add(individual.getUtility(b));
286 }
287
288 // {予測効用値:予測順位} の辞書
289 TreeMap<Double, Integer> map = new TreeMap<>(Collections.reverseOrder());
290 for (double util : utilList) {
291 map.put(util, 1);
292 }
293 int rank = 1;
294 for (Map.Entry<Double, Integer> entry : map.entrySet()) {
295 rank += entry.setValue(rank);
296 }
297
298 List<Integer> rankList = new ArrayList<>();
299 for (double util : utilList) {
300 rankList.add(map.get(util));
301 }
302 Collections.reverse(rankList); // ランキング上位から下位のBidの予測順位(1,2,3,...って並んでるとうれしい)
303
304 int sqSum = 0;
305 for (int i = 0; i < rankList.size(); i++) {
306 int diff = i + 1 - rankList.get(i);
307 sqSum += diff * diff;
308 }
309 double spearman = 1.0 - 6.0 * (double) sqSum / (Math.pow(rankList.size(), 3) - rankList.size());
310 double lowDiff = Math.abs(bidRank.getLowUtility() - individual.getUtility(bidRank.getMinimalBid()));
311 double highDiff = Math.abs(bidRank.getHighUtility() - individual.getUtility(bidRank.getMaximalBid()));
312
313 if (print) {
314 System.out.println("spearman = " + spearman + ", lowDiff = " + lowDiff + ", highDiff = " + highDiff);
315 }
316
317 return spearman * 10 + (1 - lowDiff) + (1 - highDiff);
318 }
319
320 // ルーレット選択
321 private List<AbstractUtilitySpace> selectByRoulette(List<AbstractUtilitySpace> population, List<Double> fitnessList, int popSize) {
322 List<AbstractUtilitySpace> nextGeneration = new ArrayList<>();
323
324 // 適応度が最大の要素を求める
325 double maxFit = -1.0;
326 int maxIndex = -1;
327
328 double fitSum = 0.0;
329 for (int i = 0; i < fitnessList.size(); i++) {
330 double fit = fitnessList.get(i);
331 if (maxFit < fit) {
332 maxFit = fit;
333 maxIndex = i;
334 }
335 fitSum += fit;
336 }
337
338 ////System.out.print("average = " + fitSum / population.size() + ", max = " + maxFit + ", ");
339 ////fitness(population.get(maxIndex), true);
340
341 nextGeneration.add(population.get(maxIndex));
342
343 for (int i = 0; i < popSize - 1; i++) {
344 double randomNum = rnd.nextDouble() * fitSum;
345 double count = 0.0;
346 for (int n = 0; n < population.size(); n++) {
347 count += fitnessList.get(n);
348 if (count > randomNum) {
349 nextGeneration.add(population.get(n));
350 break;
351 }
352 }
353 }
354
355 return nextGeneration;
356 }
357}
Note: See TracBrowser for help on using the repository browser.