source: src/main/java/agents/anac/y2014/Aster/SearchSA.java@ 209

package agents.anac.y2014.Aster;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import genius.core.Bid;
import genius.core.issue.Issue;
import genius.core.issue.IssueInteger;
import genius.core.issue.ValueInteger;
import genius.core.utility.AbstractUtilitySpace;

public class SearchSA {
        private AbstractUtilitySpace utilitySpace;
        private Random randomnr = new Random();
        private ArrayList<Bid> bidList = new ArrayList<Bid>();
        private double temperature;
        private static final double MINIMUM_UTILITY = 0.70; // �期解�最低効用値（高��る��期解�生������）
        private static final int NUMBER_ITERATIONS = 10000; // 繰り返�回数
        private static final int NUMBER_SOLUTIONS = 50;

        public SearchSA(AbstractUtilitySpace utilitySpace, int sessionNr) {
                this.utilitySpace = utilitySpace;
                this.temperature = 1000000;
                // this.fileWriter = createFileWriter(sessionNr);
        }

        public Bid getBidbySA(double bidTarget) throws Exception {
                Bid currentBid, nextBid, maxBid;
                double currentUtility, nextUtility, maxUtility, probability;
                int iteration = 0;

                // �期設定
                temperature = 1000000;
                do {
                        currentBid = utilitySpace.getDomain().getRandomBid(null);
                        currentUtility = utilitySpace.getUtility(currentBid);
                } while (currentUtility < MINIMUM_UTILITY);

                maxBid = currentBid;
                maxUtility = currentUtility;

                while ((iteration++ < NUMBER_ITERATIONS) && (maxUtility < bidTarget)) {
                        nextBid = nextBid(currentBid);
                        nextUtility = utilitySpace.getUtility(nextBid);
                        temperature = calculateTemperature();
                        probability = calculateProbability(currentUtility, nextUtility,
                                        temperature);

                        if (probability > randomnr.nextDouble()) {
                                currentBid = nextBid;
                                currentUtility = utilitySpace.getUtility(nextBid);
                                if (nextUtility > maxUtility) {
                                        maxBid = nextBid;
                                        maxUtility = nextUtility;
                                }
                        }
                }

                if (maxUtility < bidTarget) {
                        return null;
                } else {
                        return maxBid;
                }
        }

        public Bid getFirstBidbySA(double bidTarget) throws Exception {
                Bid currentBid, maxBid; // �在�Bid�最�Bid
                double currentUtility, maxUtility; // �在�効用値�最大効用値
                int iteration = 0; // 繰り返�回数

                // �期解�生�
                for (int i = 0; i < NUMBER_SOLUTIONS; i++) {
                        do {
                                currentBid = utilitySpace.getDomain().getRandomBid(null);
                                currentUtility = utilitySpace.getUtility(currentBid);
                        } while (currentUtility < MINIMUM_UTILITY);
                        bidList.add(currentBid);
                }

                // 最�解�更新
                maxBid = getMaxBid(bidList);
                maxUtility = utilitySpace.getUtility(maxBid);

                // fileWrite(fileWriter, maxUtility);

                // 指定回数�最�解�見��る��繰り返�
                while ((iteration++ < NUMBER_ITERATIONS) && (maxUtility < bidTarget)) {
                        for (int i = 0; i < bidList.size(); i++) {
                                Bid curBid = bidList.get(i);
                                currentUtility = utilitySpace.getUtility(curBid);
                                Bid nextBid = nextBid(curBid); // 近�Bidを探索
                                double nextUtility = utilitySpace.getUtility(nextBid); // 近�Bid�効用値
                                double probability = calculateProbability(currentUtility,
                                                nextUtility, temperature); // �移確率�算出

                                if (probability > randomnr.nextDouble()) {
                                        bidList.set(i, nextBid); // Bid�更新
                                }
                        }

                        // 温度�算出
                        temperature = calculateTemperature();

                        // 最�解�更新
                        maxBid = getMaxBid(bidList);
                        maxUtility = utilitySpace.getUtility(maxBid);

                        // fileWrite(fileWriter, maxUtility);

                }

                // fileWriter.close();
                return maxBid;
        }

        /**
         * �移確率�算出
         *
         * @param currentUtil
         *            �在�効用値
         * @param nextUtil
         *            近��効用値
         * @param temperature
         *            温度
         * @return �移確率
         */
        private double calculateProbability(double currentUtil, double nextUtil,
                        double temperature) {
                double diff = currentUtil - nextUtil;
                if (diff > 0.0) {
                        return Math.exp(-diff / temperature); // ç�¾åœ¨ã�®åŠ¹ç”¨å€¤ã�®æ–¹ã�Œé«˜ã�„å ´å�ˆ
                } else {
                        return 1.0; // è¿‘å‚�ã�®åŠ¹ç”¨å€¤ã�®æ–¹ã�Œé«˜ã�„å ´å�ˆ
                }
        }

        /**
         * 温度�算出
         *
         * @param iteration
         *            �在�試行回数
         * @return 温度
         */
        private double calculateTemperature() {
                return temperature *= 0.97;
        }

        /**
         * 指定��Issue���る近��Bidを探索
         *
         * @param bid
         *            �在�Bid
         * @return 近�Bid
         * @throws Exception
         */
        private Bid nextBid(Bid bid) throws Exception {
                List<Issue> issues = utilitySpace.getDomain().getIssues(); // 全issue��得
                Bid nextBid = new Bid(bid); // �在�Bidをコピー

                int issueIndex = randomnr.nextInt(issues.size()); // Issueをランダム�指定
                IssueInteger lIssueInteger = (IssueInteger) issues.get(issueIndex); // 指定��index�issueを�得
                int issueNumber = lIssueInteger.getNumber(); // issue番�
                int issueIndexMin = lIssueInteger.getLowerBound(); // issue�下�値
                int issueIndexMax = lIssueInteger.getUpperBound(); // issue�上�値
                int optionIndex = 0; // 変更�るValue値

                ValueInteger lIssueValue = (ValueInteger) bid.getValue(issueNumber); // 指定��issue�Value
                int issueValue = Integer.valueOf(lIssueValue.toString()).intValue();
                optionIndex = nextOptionIndex(issueIndexMin, issueIndexMax, issueValue); // 値を1増減��る

                nextBid = nextBid.putValue(issueNumber, new ValueInteger(optionIndex)); // �在�Bid�らIssue�値を入れ替�る

                return nextBid;
        }

        /**
         * 近�探索
         *
         * @param issueIndexMin
         *            下�値
         * @param issueIndexMax
         *            上�値
         * @param issueValue
         *            �在�値
         * @return 値を1ã� ã�‘増減ã�•ã�›ã‚‹
         */
        private int nextOptionIndex(int issueIndexMin, int issueIndexMax,
                        int issueValue) {
                int step = 1; // 値を増減��る幅
                int direction = randomnr.nextBoolean() ? 1 : -1; // ランダム�増減を決定

                if (issueIndexMin < issueIndexMax) {
                        if ((issueValue + step) > issueIndexMax) { // +1ã�™ã‚‹ã�¨ä¸Šé™�値を超ã�ˆã‚‹å ´å�ˆ
                                direction = -1;
                        } else if ((issueValue - step) < issueIndexMin) { // -1ã�™ã‚‹ã�¨ä¸‹é™�å€¤ã‚’ä¸‹å›žã‚‹å ´å�ˆ
                                direction = 1;
                        }
                } else {
                        return issueValue; // issueIndexMin == issueIndexMaxã�®å ´å�ˆ
                }

                return issueValue + step * direction;
        }

        private Bid getMaxBid(ArrayList<Bid> bidList) throws Exception {
                Bid maxBid = null;
                double maxUtil = 0.0;
                for (Bid curBid : bidList) {
                        double curUtil = utilitySpace.getUtility(curBid);
                        if (curUtil > maxUtil) {
                                maxBid = curBid;
                                maxUtil = curUtil;
                        }
                }
                return maxBid;
        }
}