source: src/main/java/agents/anac/y2018/agentnp1/etc/bidSearch.java@ 345

Last change on this file since 345 was 343, checked in by Tim Baarslag, 4 years ago

Fixed all errors in all 2018 agents
File size: 10.9 KB
Line 
1package agents.anac.y2018.agentnp1.etc;
2
3import java.util.List;
4
5import java.util.ArrayList;
6import java.util.HashMap;
7import java.util.Random;
8
9import genius.core.Bid;
10import genius.core.issue.Issue;
11import genius.core.issue.IssueDiscrete;
12import genius.core.issue.IssueInteger;
13import genius.core.issue.IssueReal;
14import genius.core.issue.Value;
15import genius.core.issue.ValueDiscrete;
16import genius.core.issue.ValueInteger;
17import genius.core.issue.ValueReal;
18import genius.core.parties.NegotiationInfo;
19import genius.core.utility.UtilitySpace;
20
21public class bidSearch {
22 private NegotiationInfo info;
23 private UtilitySpace utilitySpace;
24 private Bid maxBid = null; // 最大効用値Bid
25
26 public bidSearch(UtilitySpace utilitySpace, NegotiationInfo info) throws Exception {
27 this.info = info;
28 this.utilitySpace = utilitySpace;
29 initMaxBid(); // 最大効用値Bidの初期探索
30// negoStats.setValueRelativeUtility(maxBid); // 相対効用値を導出する
31 }
32
33 private void initMaxBid() throws Exception{
34 int tryNum = info.getUtilitySpace().getDomain().getIssues().size(); // 試行回数
35 Random rnd = new Random(info.getRandomSeed()); //Randomクラスのインスタンス化
36 //maxBid = info.getUtilitySpace().getDomain().getRandomBid(rnd);
37 maxBid = info.getUtilitySpace().getMaxUtilityBid();
38 for (int i = 0; i < tryNum; i++) {
39 try {
40 do{
41 SimulatedAnnealingSearch(maxBid, 1.0);
42 } while (info.getUtilitySpace().getUtility(maxBid) < info.getUtilitySpace().getReservationValue());
43 if(info.getUtilitySpace().getUtility(maxBid) == 1.0){
44 break;
45 }
46 } catch (Exception e) {
47 System.out.println("[Exception_Search] Failed to find the first Bid");
48 e.printStackTrace();
49 }
50 }
51// System.out.println("[isPrinting_Search]:" + maxBid.toString() + " " + info.getUtilitySpace().getUtility(maxBid));
52 }
53
54 public Bid getBid(Bid baseBid, double threshold) {
55 try {
56 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 閾値以上の効用値を持つ合意案候補を探索
57 // 探索によって得られたBidがthresholdよりも小さい場合，最大効用値Bidを基準とする
58 if (info.getUtilitySpace().getUtility(bid) < threshold) {
59 bid = new Bid(maxBid);
60 }
61
62 Bid tempBid = new Bid(bid);
63
64 // 探索によって得られたBidがthresholdよりも小さい場合
65 if (info.getUtilitySpace().getUtility(tempBid) < threshold) {
66 return bid;
67 } else {
68 return tempBid;
69 }
70
71 } catch (Exception e) {
72 System.out.println("[Error]: failed to search bids");
73 e.printStackTrace();
74 return baseBid;
75 }
76 }
77
78 private static int SA_ITERATION = 1;
79
80 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
81 Bid bid = new Bid(baseBid);
82
83 // In case of nonlinear, search is carried out, ★ In case of linear, change to generate bid randomly
84 try {
85 if(info.getUtilitySpace().getUtility(bid) < threshold){
86
87 Bid currentBid = null;
88 double currentBidUtil = 0;
89 double min = 1.0;
90 for (int i = 0; i < SA_ITERATION; i++) {
91 currentBid = SimulatedAnnealingSearch(bid, threshold);
92 currentBidUtil = info.getUtilitySpace().getUtility(currentBid);
93 if (currentBidUtil <= min && currentBidUtil >= threshold) {
94 bid = new Bid(currentBid);
95 min = currentBidUtil;
96 }
97 }
98 } else {
99 bid = generateRandomBid();
100 }
101 } catch (Exception e) {
102 System.out.println("[Error] failed to SA search");
103 System.out.println("[Error] Problem with received bid(SA:last):" + e.getMessage() + ". cancelling bidding");
104 }
105 return bid;
106 }
107
108 // SA
109 static double START_TEMPERATURE = 1.0; // start temperature
110 static double END_TEMPERATURE = 0.0001; // end temperature
111 static double COOL = 0.999; // cooling degree
112 static int STEP = 1;// changable width
113 static int STEP_NUM = 1; // changable number
114 /**
115 * SA
116 * @param baseBid
117 * @param threshold
118 * @return
119 * @throws Exception
120 */
121 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold) throws Exception {
122 Bid currentBid = new Bid(baseBid); //Generation of initial value
123 double currenBidUtil = info.getUtilitySpace().getUtility(baseBid);
124 Bid nextBid = null; // Evaluation Bid
125 double nextBidUtil = 0.0;
126 ArrayList<Bid> targetBids = new ArrayList<Bid>(); //ArrayList of optimum utility value Bid
127 double targetBidUtil = 0.0;
128 double p; // Transition probability
129 Random randomnr = new Random(); // random number
130 double currentTemperature = START_TEMPERATURE; // current temparature
131 double newCost = 1.0;
132 double currentCost = 1.0;
133 List<Issue> issues = info.getUtilitySpace().getDomain().getIssues();
134
135 // Loop until temperature drops sufficiently
136 while (currentTemperature > END_TEMPERATURE) {
137 nextBid = new Bid(currentBid); // initialize next_bid
138
139 // Get nearby Bid
140 for (int i = 0; i < STEP_NUM; i++) {
141 int issueIndex = randomnr.nextInt(issues.size()); // Randomly specify issues
142 Issue issue = issues.get(issueIndex); // Issue with the specified index
143 ArrayList<Value> values = getValues(issue);
144 int valueIndex = randomnr.nextInt(values.size()); // Randomly specified within the range of possible values
145 nextBid = nextBid.putValue(issue.getNumber(), values.get(valueIndex));
146 nextBidUtil = info.getUtilitySpace().getUtility(nextBid);
147
148 // Update maximum utility value Bid
149 if (maxBid == null || nextBidUtil >= info.getUtilitySpace().getUtility(maxBid)) {
150 maxBid = new Bid(nextBid);
151 }
152 }
153
154 newCost = Math.abs(threshold - nextBidUtil);
155 currentCost = Math.abs(threshold - currenBidUtil);
156 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
157 if (newCost < currentCost || p > randomnr.nextDouble()) {
158 currentBid = new Bid(nextBid); // updatevBid
159 currenBidUtil = nextBidUtil;
160 }
161
162 // update
163 if (currenBidUtil >= threshold){
164 if(targetBids.size() == 0){
165 targetBids.add(new Bid(currentBid));
166 targetBidUtil = info.getUtilitySpace().getUtility(currentBid);
167 } else{
168 if(currenBidUtil < targetBidUtil){
169 targetBids.clear(); // initialize
170 targetBids.add(new Bid(currentBid)); // Add element
171 targetBidUtil = info.getUtilitySpace().getUtility(currentBid);
172 } else if (currenBidUtil == targetBidUtil){
173 targetBids.add(new Bid(currentBid)); // Add element
174 }
175 }
176 }
177 currentTemperature = currentTemperature * COOL; // Lower temperature
178 }
179
180 if (targetBids.size() == 0) {
181 // If a Bid having a utility value larger than the boundary value is not found, baseBid is returned
182 return new Bid(baseBid);
183 } else {
184 // Returns Bid whose utility value is around the boundary value
185 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
186 }
187 }
188
189 protected Bid generateRandomBid() {
190
191 Bid randomBid = null;
192 HashMap<Integer, Value> values = new HashMap<Integer, Value>();
193 List<Issue> issues = utilitySpace.getDomain().getIssues();
194 for (Issue issue : issues) {
195 try {
196 values.put(Integer.valueOf(issue.getNumber()), getRandomValue(issue));
197 } catch (Exception e) {
198 e.printStackTrace();
199 }
200 }
201
202 try {
203 randomBid = new Bid(utilitySpace.getDomain(), values);
204 } catch (Exception e) {
205 e.printStackTrace();
206 }
207 return randomBid;
208 }
209
210 protected Value getRandomValue(Issue currentIssue) throws Exception {
211
212 Value currentValue = null;
213 int index = 0;
214 Random randomnr = new Random();
215
216 switch (currentIssue.getType()) {
217 case REAL:
218 IssueReal lIssueReal = (IssueReal) currentIssue;
219 index = randomnr.nextInt(lIssueReal.getNumberOfDiscretizationSteps());
220 currentValue = new ValueReal(
221 lIssueReal.getLowerBound() + ((lIssueReal.getUpperBound() - lIssueReal.getLowerBound())
222 / (double) lIssueReal.getNumberOfDiscretizationSteps()) * (double) index);
223 break;
224
225 case DISCRETE:
226 IssueDiscrete lIssueDiscrete = (IssueDiscrete) currentIssue;
227 index = randomnr.nextInt(lIssueDiscrete.getNumberOfValues());
228 currentValue = lIssueDiscrete.getValue(index);
229 break;
230
231 case INTEGER:
232 IssueInteger lIssueInteger = (IssueInteger) currentIssue;
233 index = randomnr.nextInt((lIssueInteger.getUpperBound() - lIssueInteger.getLowerBound()) + 1);
234 currentValue = new ValueInteger(lIssueInteger.getLowerBound() + index);
235 break;
236
237 default:
238 throw new Exception((new StringBuilder("issue type ")).append(currentIssue.getType())
239 .append(" not supported").toString());
240 }
241 return currentValue;
242 }
243
244 public ArrayList<Value> getValues(Issue issue) {
245 ArrayList<Value> values = new ArrayList<Value>();
246
247 switch(issue.getType()) {
248 case DISCRETE:
249 List<ValueDiscrete> valuesDis = ((IssueDiscrete)issue).getValues();
250 for(Value value:valuesDis){
251 values.add(value);
252 }
253 break;
254 case INTEGER:
255 int min_value = ((IssueInteger)issue).getUpperBound();
256 int max_value = ((IssueInteger)issue).getUpperBound();
257 for(int j=min_value; j<=max_value; j++){
258 Object valueObject = new Integer(j);
259 values.add((Value)valueObject);
260 }
261 break;
262 default:
263 try {
264 throw new Exception("issue type \""+ issue.getType() + "\" not supported by" + info.getAgentID().getName());
265 } catch (Exception e) {
266 System.out.println("[Exception] Failed to get the value of issues");
267 e.printStackTrace();
268 }
269 }
270
271 return values;
272 }
273
274}
Note: See TracBrowser for help on using the repository browser.