    001    package ifs.perturbations;
    002
    003    import ifs.solution.*;
    004    import ifs.solver.*;
    005    import ifs.model.*;
    006    import ifs.util.*;
    007    import ifs.extension.*;
    008    import java.util.*;
    009
    010    /**
    011     * Default computation of perturbation penalty (minimal perturbation problem).
    012     * <br><br>
    013     * A distance function can be defined with the help of perturbations. A perturbation is a variable that has a different
    014     * value in the solutions of the initial and the new problem. Some perturbations must be present in each new solution.
    015     * So called input perturbation means that a variable must have different values in the initial and changed problem
    016     * because of some input changes (e.g., a course must be scheduled at a different time in the changed problem).
    017     * The distance function can be defined as the number of additional perturbations. They are given by subtraction of
    018     * the final number of perturbations and the number of input perturbations (variables without initial assignments).
    019     * <br><br>
    020     * This implementation is easily extendable. It disassemble all the available cases into a comparison of the initial and
    021     * the assigned value different each other. So, the only method which is needed to be changed is
    022     * {@link DefaultPerturbationsCounter#getPenalty(Value, Value)}. Its current implementation is: <ul><code>
    023     * protected double getPenalty(Value assignedValue, Value initialValue) {<br>
    024     * &nbsp;&nbsp;&nbsp;&nbsp;return 1.0;<br>
    025     * }<br>
    026     * </code></ul>
    027     * It is called only when assignedValue is different to initialValue.
    028     *
    029     * @see Solver
    030     * @see Solution
    031     * @see Variable
    032     *
    033     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    034     * @version 1.0
    035     */
    036
    037    public class DefaultPerturbationsCounter implements PerturbationsCounter {
    038        private ViolatedInitials iViolatedInitials = null;
    039        protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
    040
    041        /** Constructor
    042         * @param properties input configuration
    043         */
    044        public DefaultPerturbationsCounter(DataProperties properties) {
    045        }
    046
    047        /** Initialization */
    048        public void init(Solver solver) {
    049            for (Enumeration i=solver.getExtensions().elements();i.hasMoreElements();) {
    050                Extension extension = (Extension)i.nextElement();
    051                if (extension instanceof ViolatedInitials)
    052                    iViolatedInitials = (ViolatedInitials)extension;
    053            }
    054        }
    055
    056        public double getPerturbationPenalty(Solution solution) {
    057            double penalty = 0.0;
    058            for (Enumeration e=solution.getModel().perturbVariables().elements();e.hasMoreElements();) {
    059                Variable variable = (Variable)e.nextElement();
    060                if (variable.getAssignment()!=null && variable.getInitialAssignment()!=null && !variable.getAssignment().equals(variable.getInitialAssignment()))
    061                    penalty += getPenaltyD(variable.getAssignment(),variable.getInitialAssignment());
    062            }
    063            return penalty;
    064        }
    065
    066        protected ViolatedInitials getViolatedInitials() { return iViolatedInitials; }
    067
    068        /** Computes perturbation penalty between assigned and initial value of the same lecture.
    069         * It is called only when assignedValue is different to initialValue.
    070         * @param assignedValue value assigned to a varuable (null when variable is unassigned)
    071         * @param initialValue initial value of the same varaible (always not null)
    072         */
    073        protected double getPenalty(Value assignedValue, Value initialValue) {
    074            return 1.0;
    075        }
    076
    077        /** Case A: initial value of a different unassigned variable cannot be assigned (computed by {@link ViolatedInitials})
    078         * @param selectedValue value which is going to be assigned to its variable
    079         * @param initialValue value of a different variable, which is currently assigned but which need to be unassifned
    080         * Different variable, which is unassigned and whose initial value is in conflict with the selected value.*/
    081        protected double getPenaltyA(Value selectedValue, Value initialValue) {
    082            return getPenalty(null, initialValue);
    083        }
    084
    085        /** Case B: initial value is unassigned from a conflicting variable.
    086         * @param selectedValue value which is going to be unassigned to its variable
    087         * @param assignedValue value currently assigned to a conflicting variable (different from the one of selectedVariable)
    088         * @param initialValue initial value of the conflicting variable of assignedValue
    089         */
    090        protected double getPenaltyB(Value selectedValue, Value assignedValue, Value initialValue) {
    091            return getPenalty(assignedValue, initialValue);
    092        }
    093
    094        /** Case C: non-initial value is unassigned from a conflicting variable.
    095         * @param selectedValue value which is going to be unassigned to its variable
    096         * @param assignedValue value currently assigned to a conflicting variable (different from the one of selectedVariable)
    097         * @param initialValue initial value of the conflicting variable of assignedValue
    098         */
    099        protected double getPenaltyC(Value selectedValue, Value assignedValue, Value initialValue) {
    100            return -getPenalty(assignedValue, initialValue);
    101        }
    102
    103        /** Case D: different than initial value is assigned to the varaible
    104         * @param selectedValue value which is going to be unassigned to its variable
    105         * @param initialValue initial value of the same variable
    106         */
    107        protected double getPenaltyD(Value selectedValue, Value initialValue) {
    108            return getPenalty(selectedValue, initialValue);
    109        }
    110
    111        public double getPerturbationPenalty(Solution solution, Value selectedValue, Collection conflicts)  {
    112            double penalty = 0;
    113            Set violations = (getViolatedInitials()==null?null:getViolatedInitials().getViolatedInitials(selectedValue));
    114            if (violations!=null)
    115                for (Iterator it1=violations.iterator(); it1.hasNext(); ) {
    116                Value aValue = (Value)it1.next();
    117                if (aValue.variable().getAssignment()==null)
    118                    penalty += getPenaltyA(selectedValue,aValue);
    119                }
    120            for (Iterator it1=conflicts.iterator(); it1.hasNext(); ) {
    121                Value conflictValue = (Value)it1.next();
    122                Value initialValue = conflictValue.variable().getInitialAssignment();
    123                if (initialValue!=null) {
    124                    if (initialValue.equals(conflictValue))
    125                        penalty += getPenaltyB(selectedValue, conflictValue, initialValue);
    126                    else {
    127                        if (violations==null || !violations.contains(initialValue))
    128                            penalty += getPenaltyC(selectedValue, conflictValue, initialValue);
    129                    }
    130                }
    131            }
    132            if (selectedValue.variable().getInitialAssignment()!=null && !selectedValue.equals(selectedValue.variable().getInitialAssignment()))
    133                penalty += getPenaltyD(selectedValue, selectedValue.variable().getInitialAssignment());
    134            return penalty;
    135        }
    136
    137        public void getInfo(Dictionary info, Solution solution) {
    138            info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(solution)));
    139        }
    140
    141    }