source: src/main/java/agents/anac/y2014/E2Agent/myUtility/SimulatedAnealing.java@ 346

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

Initial import : Genius 9.0.0
File size: 7.1 KB
Line 
1package agents.anac.y2014.E2Agent.myUtility;
2
3import java.util.List;
4import java.util.Random;
5
6import genius.core.Bid;
7import genius.core.issue.Issue;
8import genius.core.issue.IssueInteger;
9import genius.core.issue.ValueInteger;
10import genius.core.utility.AbstractUtilitySpace;
11
12public class SimulatedAnealing {
13 private List<Issue> issues = null; // 効用空間�全��論点
14 private Random randomnr = null;
15 private AbstractUtilitySpace utilitySpace = null;
16 private MethodForSA methods = null;
17
18 public SimulatedAnealing(AbstractUtilitySpace u) {
19 utilitySpace = u;
20 issues = utilitySpace.getDomain().getIssues();
21 randomnr = new Random();
22 ;
23 // methods = new RandomSearch();
24 methods = new StepSearch();
25 }
26
27 /**
28 * 焼����法を利用��最�解を探索
29 *
30 * @param startBid
31 * 探索開始Bid
32 * @param thresholdUtility
33 * 効用値閾値
34 * @param kmax
35 * 最大ループ回数
36 * @return 最�Bid
37 * @throws Exception
38 */
39 public BidStorage run(Bid startBid, double targetUtility, int kmax)
40 throws Exception {
41 int k = 0;
42 Bid bid = startBid; // 最��Bid�置
43 double utility = utilitySpace.getUtility(bid); // 効用値
44 Bid bestBid = bid; // 最�候補Bid
45 double bestUtility = utility; // 最�候補Bid効用値
46
47 // 指定回数��ループ
48 while (k < kmax) {
49 // 近隣�Bidを�得
50 Bid neighbourBid = methods.searchNeighbourBid(bid);
51 double neighbourUtility = utilitySpace.getUtility(neighbourBid);
52 // 温度
53 double temperature = methods.calculateTemperature(k, kmax);
54 // �移�る����
55 boolean trans = methods.calculateWheterToUpdateBid(targetUtility,
56 utility, neighbourUtility, temperature);
57
58 if (trans) {
59 utility = neighbourUtility;
60 bid = neighbourBid;
61 // System.out.printf("%f ",utility);
62 // 最�効用値更新
63 if (Math.abs(targetUtility - bestUtility) > Math
64 .abs(targetUtility - utility)) {
65 bestUtility = utility;
66 bestBid = bid;
67 if (Math.abs(targetUtility - utility) < 0.01) {
68 break;
69 }
70 }
71 }
72 ++k;
73 }
74 // System.out.printf("\n",utility);
75 return new BidStorage(bestBid, bestUtility, -1);
76 }
77
78 /**
79 * 検索クラス
80 */
81 class RandomSearch implements MethodForSA {
82 @Override
83 public Bid searchNeighbourBid(Bid bid) {
84 // 整数型論点�定義��択�能�論点値�範囲を得られる
85 IssueInteger lIssueInteger = (IssueInteger) issues.get(randomnr
86 .nextInt(issues.size()));
87 int issueIndexMin = lIssueInteger.getLowerBound();
88 int issueIndexMax = lIssueInteger.getUpperBound();
89 int optionIndex = issueIndexMin;
90
91 if (issueIndexMin < issueIndexMax) {
92 // 最大最�値�間�インデックスを得る
93 optionIndex = issueIndexMin
94 + randomnr.nextInt(issueIndexMax - issueIndexMin);
95 }
96
97 Bid neighbourBid = new Bid(bid);
98 neighbourBid = neighbourBid.putValue(lIssueInteger.getNumber(),
99 new ValueInteger(optionIndex));
100 return neighbourBid;
101 }
102
103 @Override
104 public double calculateTemperature(int k, int kmax) {
105 double T = 1000;
106 // double val = T * Math.pow(1.0 - ((double)k / kmax), 2);
107 double val = T * Math.pow(0.9, k);
108 // System.out.printf("%f\n",val);
109 return val;
110 }
111
112 @Override
113 public boolean calculateWheterToUpdateBid(double targetUtility,
114 double utility, double neighbourUtility, double temperature) {
115 double diff = Math.abs(targetUtility - neighbourUtility)
116 - Math.abs(targetUtility - utility);
117 double p = 1.0;
118
119 if (0.0 < diff) {
120 p = Math.exp(-diff / temperature);
121 }
122 return randomnr.nextDouble() < p;
123 }
124 }
125
126 /**
127 * 検索クラス
128 */
129 class StepSearch implements MethodForSA {
130 private int indexes = 1;
131
132 public StepSearch() {
133 indexes = issues.size() / 10;
134 if (indexes < 1) {
135 indexes = 1;
136 }
137 }
138
139 @Override
140 public Bid searchNeighbourBid(Bid bid) {
141 Bid neighbourBid = new Bid(bid);
142 for (int i = 0; i < indexes; ++i) {
143 // 整数型論点�定義��択�能�論点値�範囲を得られる
144 int targetIssueIndex = randomnr.nextInt(issues.size());
145 IssueInteger lIssueInteger = (IssueInteger) issues
146 .get(targetIssueIndex);
147 int issueIndexMin = lIssueInteger.getLowerBound();
148 int issueIndexMax = lIssueInteger.getUpperBound();
149 int currentIndex;
150 try {
151 currentIndex = ((ValueInteger) bid
152 .getValue(targetIssueIndex + 1)).getValue();
153 } catch (Exception e) {
154 e.printStackTrace();
155 currentIndex = issueIndexMin;
156 }
157
158 currentIndex += (randomnr.nextFloat() < 0.5) ? 1 : -1;
159
160 if (currentIndex < issueIndexMin) {
161 currentIndex = issueIndexMax;
162 } else if (currentIndex > issueIndexMax) {
163 currentIndex = issueIndexMin;
164 }
165
166 neighbourBid = neighbourBid.putValue(targetIssueIndex + 1,
167 new ValueInteger(currentIndex));
168 }
169 return neighbourBid;
170 }
171
172 @Override
173 public double calculateTemperature(int k, int kmax) {
174 double T = 1000;
175 // double val = T * Math.pow(1.0 - ((double)k / kmax), 2);
176 double val = T * Math.pow(0.95, k);
177 // System.out.printf("%f\n",val);
178 return val;
179 }
180
181 @Override
182 public boolean calculateWheterToUpdateBid(double targetUtility,
183 double utility, double neighbourUtility, double temperature) {
184 double diff = Math.abs(targetUtility - neighbourUtility)
185 - Math.abs(targetUtility - utility);
186 double p = 1.0;
187
188 if (0.0 < diff) {
189 p = Math.exp(-diff / temperature);
190 }
191 return randomnr.nextDouble() < p;
192 }
193 }
194
195}
196
197interface MethodForSA {
198 /**
199 * 隣接�るBidを探索
200 *
201 * @param bid
202 * 対象��るBid
203 * @return 隣接�るBid
204 */
205 Bid searchNeighbourBid(Bid bid);
206
207 /**
208 * 温度�算出
209 *
210 * @param k
211 * ループ回数
212 * @param kmax
213 * 最大ループ回数
214 * @return 温度
215 */
216 double calculateTemperature(int k, int kmax);
217
218 /**
219 * �移確率�算出
220 *
221 * @param utility
222 * 効用値
223 * @param neighbourUtility
224 * 近隣�効用値
225 * @param temperature
226 * 温度
227 * @return �移確率
228 */
229 // double calculateTransitionProbability(double targetUtility,
230 // double utility, double neighbourUtility, double temperature);
231 boolean calculateWheterToUpdateBid(double targetUtility, double utility,
232 double neighbourUtility, double temperature);
233}
Note: See TracBrowser for help on using the repository browser.