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

package agents.anac.y2014.E2Agent.myUtility;

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 SimulatedAnealing {
        private List<Issue> issues = null; // 効用空間�全��論点
        private Random randomnr = null;
        private AbstractUtilitySpace utilitySpace = null;
        private MethodForSA methods = null;

        public SimulatedAnealing(AbstractUtilitySpace u) {
                utilitySpace = u;
                issues = utilitySpace.getDomain().getIssues();
                randomnr = new Random();
                ;
                // methods = new RandomSearch();
                methods = new StepSearch();
        }

        /**
         * 焼����法を利用��最�解を探索
         * 
         * @param startBid
         *            探索開始Bid
         * @param thresholdUtility
         *            効用値閾値
         * @param kmax
         *            最大ループ回数
         * @return 最�Bid
         * @throws Exception
         */
        public BidStorage run(Bid startBid, double targetUtility, int kmax)
                        throws Exception {
                int k = 0;
                Bid bid = startBid; // 最��Bid�置
                double utility = utilitySpace.getUtility(bid); // 効用値
                Bid bestBid = bid; // 最�候補Bid
                double bestUtility = utility; // 最�候補Bid効用値

                // 指定回数��ループ
                while (k < kmax) {
                        // 近隣�Bidを�得
                        Bid neighbourBid = methods.searchNeighbourBid(bid);
                        double neighbourUtility = utilitySpace.getUtility(neighbourBid);
                        // 温度
                        double temperature = methods.calculateTemperature(k, kmax);
                        // �移�る����
                        boolean trans = methods.calculateWheterToUpdateBid(targetUtility,
                                        utility, neighbourUtility, temperature);

                        if (trans) {
                                utility = neighbourUtility;
                                bid = neighbourBid;
                                // System.out.printf("%f ",utility);
                                // 最�効用値更新
                                if (Math.abs(targetUtility - bestUtility) > Math
                                                .abs(targetUtility - utility)) {
                                        bestUtility = utility;
                                        bestBid = bid;
                                        if (Math.abs(targetUtility - utility) < 0.01) {
                                                break;
                                        }
                                }
                        }
                        ++k;
                }
                // System.out.printf("\n",utility);
                return new BidStorage(bestBid, bestUtility, -1);
        }

        /**
         * 検索クラス
         */
        class RandomSearch implements MethodForSA {
                @Override
                public Bid searchNeighbourBid(Bid bid) {
                        // 整数型論点�定義��択�能�論点値�範囲を得られる
                        IssueInteger lIssueInteger = (IssueInteger) issues.get(randomnr
                                        .nextInt(issues.size()));
                        int issueIndexMin = lIssueInteger.getLowerBound();
                        int issueIndexMax = lIssueInteger.getUpperBound();
                        int optionIndex = issueIndexMin;

                        if (issueIndexMin < issueIndexMax) {
                                // 最大最�値�間�インデックスを得る
                                optionIndex = issueIndexMin
                                                + randomnr.nextInt(issueIndexMax - issueIndexMin);
                        }

                        Bid neighbourBid = new Bid(bid);
                        neighbourBid = neighbourBid.putValue(lIssueInteger.getNumber(),
                                        new ValueInteger(optionIndex));
                        return neighbourBid;
                }

                @Override
                public double calculateTemperature(int k, int kmax) {
                        double T = 1000;
                        // double val = T * Math.pow(1.0 - ((double)k / kmax), 2);
                        double val = T * Math.pow(0.9, k);
                        // System.out.printf("%f\n",val);
                        return val;
                }

                @Override
                public boolean calculateWheterToUpdateBid(double targetUtility,
                                double utility, double neighbourUtility, double temperature) {
                        double diff = Math.abs(targetUtility - neighbourUtility)
                                        - Math.abs(targetUtility - utility);
                        double p = 1.0;

                        if (0.0 < diff) {
                                p = Math.exp(-diff / temperature);
                        }
                        return randomnr.nextDouble() < p;
                }
        }

        /**
         * 検索クラス
         */
        class StepSearch implements MethodForSA {
                private int indexes = 1;

                public StepSearch() {
                        indexes = issues.size() / 10;
                        if (indexes < 1) {
                                indexes = 1;
                        }
                }

                @Override
                public Bid searchNeighbourBid(Bid bid) {
                        Bid neighbourBid = new Bid(bid);
                        for (int i = 0; i < indexes; ++i) {
                                // 整数型論点�定義��択�能�論点値�範囲を得られる
                                int targetIssueIndex = randomnr.nextInt(issues.size());
                                IssueInteger lIssueInteger = (IssueInteger) issues
                                                .get(targetIssueIndex);
                                int issueIndexMin = lIssueInteger.getLowerBound();
                                int issueIndexMax = lIssueInteger.getUpperBound();
                                int currentIndex;
                                try {
                                        currentIndex = ((ValueInteger) bid
                                                        .getValue(targetIssueIndex + 1)).getValue();
                                } catch (Exception e) {
                                        e.printStackTrace();
                                        currentIndex = issueIndexMin;
                                }

                                currentIndex += (randomnr.nextFloat() < 0.5) ? 1 : -1;

                                if (currentIndex < issueIndexMin) {
                                        currentIndex = issueIndexMax;
                                } else if (currentIndex > issueIndexMax) {
                                        currentIndex = issueIndexMin;
                                }

                                neighbourBid = neighbourBid.putValue(targetIssueIndex + 1,
                                                new ValueInteger(currentIndex));
                        }
                        return neighbourBid;
                }

                @Override
                public double calculateTemperature(int k, int kmax) {
                        double T = 1000;
                        // double val = T * Math.pow(1.0 - ((double)k / kmax), 2);
                        double val = T * Math.pow(0.95, k);
                        // System.out.printf("%f\n",val);
                        return val;
                }

                @Override
                public boolean calculateWheterToUpdateBid(double targetUtility,
                                double utility, double neighbourUtility, double temperature) {
                        double diff = Math.abs(targetUtility - neighbourUtility)
                                        - Math.abs(targetUtility - utility);
                        double p = 1.0;

                        if (0.0 < diff) {
                                p = Math.exp(-diff / temperature);
                        }
                        return randomnr.nextDouble() < p;
                }
        }

}

interface MethodForSA {
        /**
         * 隣接�るBidを探索
         * 
         * @param bid
         *            対象��るBid
         * @return 隣接�るBid
         */
        Bid searchNeighbourBid(Bid bid);

        /**
         * 温度�算出
         * 
         * @param k
         *            ループ回数
         * @param kmax
         *            最大ループ回数
         * @return 温度
         */
        double calculateTemperature(int k, int kmax);

        /**
         * �移確率�算出
         * 
         * @param utility
         *            効用値
         * @param neighbourUtility
         *            近隣�効用値
         * @param temperature
         *            温度
         * @return �移確率
         */
        // double calculateTransitionProbability(double targetUtility,
        // double utility, double neighbourUtility, double temperature);
        boolean calculateWheterToUpdateBid(double targetUtility, double utility,
                        double neighbourUtility, double temperature);
}