source: src/main/java/agents/anac/y2015/fairy/bidSearch.java

Last change on this file was 1, checked in by Wouter Pasman, 6 years ago

Initial import : Genius 9.0.0
File size: 9.8 KB
Line 
1package agents.anac.y2015.fairy;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.List;
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.ValueInteger;
16import genius.core.issue.ValueReal;
17import genius.core.utility.AdditiveUtilitySpace;
18
19public class bidSearch {
20 private AdditiveUtilitySpace utilitySpace;
21 private negotiatingInfo negotiatingInfo; // �����
22 private Bid maxBid = null; // �ő��p�lBid
23
24 // �T���̃p�����[�^
25 private static int SA_ITERATION = 1;
26 static double START_TEMPERATURE = 1.0; // �J�n���x
27 static double END_TEMPERATURE = 0.0001; // �I�����x
28 static double COOL = 0.999; // ��p�x
29 static int STEP = 1;// �ύX���镝
30 static int STEP_NUM = 1; // �ύX�����
31
32 public bidSearch(AdditiveUtilitySpace utilitySpace,
33 negotiatingInfo negotiatingInfo) throws Exception {
34 this.utilitySpace = utilitySpace;
35 this.negotiatingInfo = negotiatingInfo;
36 initMaxBid(); // �ő��p�lBid�̏���T��
37 negotiatingInfo.setValueRelativeUtility(maxBid); // ���Ό�p�l�𓱏o����
38 }
39
40 // �ő��p�lBid�̏���T��(�ŏ��͌�p��Ԃ̃^�C�v���s���ł��邽�߁CSA��p���ĒT������)
41 private void initMaxBid() throws Exception {
42 int tryNum = utilitySpace.getDomain().getIssues().size(); // ���s��
43 maxBid = utilitySpace.getDomain().getRandomBid(null);
44 for (int i = 0; i < tryNum; i++) {
45 try {
46 do {
47 SimulatedAnnealingSearch(maxBid, 1.0);
48 } while (utilitySpace.getUtility(maxBid) < utilitySpace
49 .getReservationValue());
50 if (utilitySpace.getUtility(maxBid) == 1.0) {
51 break;
52 }
53 } catch (Exception e) {
54 System.out.println("�ő��p�lBid�̏���T���Ɏ��s���܂���");
55 e.printStackTrace();
56 }
57 }
58 }
59
60 // Bid��Ԃ�
61 public Bid getBid(Bid baseBid, double threshold) {
62 // Type:Real�ɑΉ��i�b��Łj
63 for (Issue issue : negotiatingInfo.getIssues()) {
64 switch (issue.getType()) {
65 case REAL:
66 try {
67 return (getRandomBid(threshold));
68 } catch (Exception e) {
69 System.out.println("Bid�̃����_���T���Ɏ��s���܂���(Real)");
70 e.printStackTrace();
71 }
72 break;
73 default:
74 break;
75 }
76 }
77
78 // Type:Integer and Discrete
79 try {
80 Bid bid = getBidbyAppropriateSearch(baseBid, threshold); // 臒l�ȏ�̌�p�l�������ӈČ���T��
81 if (utilitySpace.getUtility(bid) < threshold) {
82 bid = new Bid(maxBid);
83 } // �T���ɂ���ē���ꂽBid��threshold�����������ꍇ�C�ő��p�lBid����Ƃ���
84 return bid;
85 } catch (Exception e) {
86 System.out.println("Bid�̒T���Ɏ��s���܂���");
87 e.printStackTrace();
88 return baseBid;
89 }
90 }
91
92 // �����_���T��
93 private Bid getRandomBid(double threshold) throws Exception {
94 HashMap<Integer, Value> values = new HashMap<Integer, Value>(); // pairs
95 // <issuenumber,chosen
96 // value
97 // string>
98 List<Issue> issues = utilitySpace.getDomain().getIssues();
99 Random randomnr = new Random();
100
101 Bid bid = null;
102 do {
103 for (Issue lIssue : issues) {
104 switch (lIssue.getType()) {
105 case DISCRETE:
106 IssueDiscrete lIssueDiscrete = (IssueDiscrete) lIssue;
107 int optionIndex = randomnr.nextInt(lIssueDiscrete
108 .getNumberOfValues());
109 values.put(lIssue.getNumber(),
110 lIssueDiscrete.getValue(optionIndex));
111 break;
112 case REAL:
113 IssueReal lIssueReal = (IssueReal) lIssue;
114 int optionInd = randomnr.nextInt(lIssueReal
115 .getNumberOfDiscretizationSteps() - 1);
116 values.put(
117 lIssueReal.getNumber(),
118 new ValueReal(lIssueReal.getLowerBound()
119 + (lIssueReal.getUpperBound() - lIssueReal
120 .getLowerBound())
121 * (double) (optionInd)
122 / (double) (lIssueReal
123 .getNumberOfDiscretizationSteps())));
124 break;
125 case INTEGER:
126 IssueInteger lIssueInteger = (IssueInteger) lIssue;
127 int optionIndex2 = lIssueInteger.getLowerBound()
128 + randomnr.nextInt(lIssueInteger.getUpperBound()
129 - lIssueInteger.getLowerBound());
130 values.put(lIssueInteger.getNumber(), new ValueInteger(
131 optionIndex2));
132 break;
133 default:
134 throw new Exception("issue type " + lIssue.getType()
135 + " not supported by Atlas3");
136 }
137 }
138 bid = new Bid(utilitySpace.getDomain(), values);
139 } while (utilitySpace.getUtility(bid) < threshold);
140
141 return bid;
142 }
143
144 // Bid�̒T��
145 private Bid getBidbyAppropriateSearch(Bid baseBid, double threshold) {
146 Bid bid = new Bid(baseBid);
147 try {
148 // ��`��p��ԗp�̒T��
149 if (negotiatingInfo.isLinerUtilitySpace()) {
150 bid = relativeUtilitySearch(threshold);
151 if (utilitySpace.getUtility(bid) < threshold) {
152 negotiatingInfo.utilitySpaceTypeisNonLiner();
153 } // �T���Ɏ��s�����ꍇ�C���`��p��ԗp�̒T���ɐ؂�ւ���
154 }
155
156 // ���`��p��ԗp�̒T��
157 if (!negotiatingInfo.isLinerUtilitySpace()) {
158 Bid currentBid = null;
159 double currentBidUtil = 0;
160 double min = 1.0;
161 for (int i = 0; i < SA_ITERATION; i++) {
162 currentBid = SimulatedAnnealingSearch(bid, threshold);
163 currentBidUtil = utilitySpace.getUtility(currentBid);
164 if (currentBidUtil <= min && currentBidUtil >= threshold) {
165 bid = new Bid(currentBid);
166 min = currentBidUtil;
167 }
168 }
169 }
170 } catch (Exception e) {
171 System.out.println("SA�T���Ɏ��s���܂���");
172 System.out.println("Problem with received bid(SA:last):"
173 + e.getMessage() + ". cancelling bidding");
174 }
175 return bid;
176 }
177
178 // ���Ό�p�l�Ɋ�Â��T��
179 private Bid relativeUtilitySearch(double threshold) throws Exception {
180 Bid bid = new Bid(maxBid);
181 double d = threshold - 1.0; // �ő��p�l�Ƃ̍�
182 double concessionSum = 0.0; // ���炵����p�l�̘a
183 double relativeUtility = 0.0;
184 HashMap<Issue, HashMap<Value, Double>> valueRelativeUtility = negotiatingInfo
185 .getValueRelativeUtility();
186 List<Issue> randomIssues = negotiatingInfo.getIssues();
187 Collections.shuffle(randomIssues);
188 ArrayList<Value> randomValues = null;
189 for (Issue issue : randomIssues) {
190 randomValues = negotiatingInfo.getValues(issue);
191 Collections.shuffle(randomValues);
192 for (Value value : randomValues) {
193 relativeUtility = valueRelativeUtility.get(issue).get(value); // �ő��p�l����Ƃ������Ό�p�l
194 if (d <= concessionSum + relativeUtility) {
195 bid = bid.putValue(issue.getNumber(), value);
196 concessionSum += relativeUtility;
197 break;
198 }
199 }
200 }
201 return bid;
202 }
203
204 // SA
205 private Bid SimulatedAnnealingSearch(Bid baseBid, double threshold)
206 throws Exception {
207 Bid currentBid = new Bid(baseBid); // ������̐���
208 double currenBidUtil = utilitySpace.getUtility(baseBid);
209 Bid nextBid = null; // �]��Bid
210 double nextBidUtil = 0.0;
211 ArrayList<Bid> targetBids = new ArrayList<Bid>(); // �œK��p�lBid��ArrayList
212 double targetBidUtil = 0.0;
213 double p; // �J�ڊm��
214 Random randomnr = new Random(); // ����
215 double currentTemperature = START_TEMPERATURE; // ���݂̉��x
216 double newCost = 1.0;
217 double currentCost = 1.0;
218 List<Issue> issues = negotiatingInfo.getIssues();
219
220 while (currentTemperature > END_TEMPERATURE) { // ���x���\��������܂Ń��[�v
221 nextBid = new Bid(currentBid); // next_bid������
222 for (int i = 0; i < STEP_NUM; i++) { // �ߖT��Bid���擾����
223 int issueIndex = randomnr.nextInt(issues.size()); // �_�_�������_���Ɏw��
224 Issue issue = issues.get(issueIndex); // �w�肵��index��issue
225 ArrayList<Value> values = negotiatingInfo.getValues(issue);
226 int valueIndex = randomnr.nextInt(values.size()); // ��蓾��l�͈̔͂Ń����_���Ɏw��
227 nextBid = nextBid.putValue(issue.getNumber(),
228 values.get(valueIndex));
229 nextBidUtil = utilitySpace.getUtility(nextBid);
230 if (maxBid == null
231 || nextBidUtil >= utilitySpace.getUtility(maxBid)) {
232 maxBid = new Bid(nextBid);
233 } // �ő��p�lBid�̍X�V
234 }
235
236 newCost = Math.abs(threshold - nextBidUtil);
237 currentCost = Math.abs(threshold - currenBidUtil);
238 p = Math.exp(-Math.abs(newCost - currentCost) / currentTemperature);
239 if (newCost < currentCost || p > randomnr.nextDouble()) {
240 currentBid = new Bid(nextBid); // Bid�̍X�V
241 currenBidUtil = nextBidUtil;
242 }
243
244 // �X�V
245 if (currenBidUtil >= threshold) {
246 if (targetBids.size() == 0) {
247 targetBids.add(new Bid(currentBid));
248 targetBidUtil = utilitySpace.getUtility(currentBid);
249 } else {
250 if (currenBidUtil < targetBidUtil) {
251 targetBids.clear(); // ����
252 targetBids.add(new Bid(currentBid)); // �v�f��lj�
253 targetBidUtil = utilitySpace.getUtility(currentBid);
254 } else if (currenBidUtil == targetBidUtil) {
255 targetBids.add(new Bid(currentBid)); // �v�f��lj�
256 }
257 }
258 }
259 currentTemperature = currentTemperature * COOL; // ���x��������
260 }
261
262 if (targetBids.size() == 0) {
263 return new Bid(baseBid);
264 } // ���E�l���傫�Ȍ�p�l������Bid�����‚���Ȃ������Ƃ��́CbaseBid��Ԃ�
265 else {
266 return new Bid(targetBids.get(randomnr.nextInt(targetBids.size())));
267 } // ��p�l�����E�l�t�߂ƂȂ�Bid��Ԃ�
268 }
269}
Note: See TracBrowser for help on using the repository browser.