[12191] | 1 | using System.Text;
|
---|
| 2 | using System.Threading.Tasks;
|
---|
| 3 | using HeuristicLab.Optimization;
|
---|
| 4 | using HeuristicLab.PluginInfrastructure;
|
---|
| 5 | using HeuristicLab.Core;
|
---|
| 6 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 7 | using HeuristicLab.Problems.Instances;
|
---|
| 8 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
| 9 | using HeuristicLab.Common;
|
---|
| 10 | using HeuristicLab.Parameters;
|
---|
| 11 | using HeuristicLab.Data;
|
---|
[12261] | 12 | using HeuristicLab.Random;
|
---|
[12191] | 13 | using System;
|
---|
[12219] | 14 | using System.Linq;
|
---|
[12191] | 15 |
|
---|
| 16 | namespace HeuristicLab.Problems.PTSP {
|
---|
| 17 | [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
|
---|
| 18 | [Creatable("Problems")]
|
---|
| 19 | [StorableClass]
|
---|
| 20 | public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
|
---|
[12306] | 21 | IProblemInstanceConsumer<PTSPData> {
|
---|
[12191] | 22 |
|
---|
[12219] | 23 |
|
---|
[12306] | 24 | #region Parameter Properties
|
---|
[12387] | 25 | public ValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
|
---|
| 26 | get { return (ValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
|
---|
[12306] | 27 | }
|
---|
[12387] | 28 | public ValueParameter<IntValue> RealizationsSizeParameter {
|
---|
| 29 | get { return (ValueParameter<IntValue>)Parameters["RealizationsSize"]; }
|
---|
| 30 | }
|
---|
| 31 |
|
---|
[12306] | 32 | #endregion
|
---|
| 33 |
|
---|
| 34 | #region Properties
|
---|
| 35 | public ItemList<ItemList<IntValue>> Realizations {
|
---|
| 36 | get { return RealizationsParameter.Value; }
|
---|
| 37 | set { RealizationsParameter.Value = value; }
|
---|
| 38 | }
|
---|
[12387] | 39 |
|
---|
| 40 | public IntValue RealizationsSize {
|
---|
| 41 | get { return RealizationsSizeParameter.Value; }
|
---|
| 42 | set { RealizationsSizeParameter.Value = value; }
|
---|
| 43 | }
|
---|
[12306] | 44 | #endregion
|
---|
| 45 |
|
---|
[12191] | 46 | [StorableConstructor]
|
---|
| 47 | private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
|
---|
| 48 | private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
|
---|
| 49 | : base(original, cloner) {
|
---|
[12387] | 50 | RegisterEventHandlers();
|
---|
[12191] | 51 | }
|
---|
[12387] | 52 | public EstimatedProbabilisticTravelingSalesmanProblem() {
|
---|
| 53 | Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation"));
|
---|
| 54 | Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
|
---|
[12799] | 55 |
|
---|
| 56 | Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
|
---|
| 57 | Operators.RemoveAll(x => x is IMoveGenerator);
|
---|
| 58 | Operators.RemoveAll(x => x is IMoveMaker);
|
---|
| 59 |
|
---|
| 60 | Operators.Add(new BestPTSPSolutionAnalyzer());
|
---|
| 61 |
|
---|
[12387] | 62 | Operators.Add(new PTSPEstimatedInversionEvaluator());
|
---|
| 63 | Operators.Add(new PTSPEstimatedInsertionEvaluator());
|
---|
| 64 | Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
|
---|
| 65 | Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
|
---|
[12191] | 66 |
|
---|
[12387] | 67 | Operators.Add(new Exhaustive25MoveGenerator());
|
---|
| 68 | Operators.Add(new Stochastic25MultiMoveGenerator());
|
---|
| 69 | Operators.Add(new Stochastic25SingleMoveGenerator());
|
---|
| 70 | Operators.Add(new TwoPointFiveMoveMaker());
|
---|
| 71 | Operators.Add(new PTSP25MoveEvaluator());
|
---|
| 72 |
|
---|
| 73 | Encoding.ConfigureOperators(Operators.OfType<IOperator>());
|
---|
| 74 | foreach (var twopointfiveMoveOperator in Operators.OfType<I25MoveOperator>()) {
|
---|
| 75 | twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
|
---|
| 76 | }
|
---|
| 77 | RealizationsSize = new IntValue(100);
|
---|
| 78 | RegisterEventHandlers();
|
---|
| 79 | }
|
---|
| 80 |
|
---|
[12191] | 81 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 82 | return new EstimatedProbabilisticTravelingSalesmanProblem(this, cloner);
|
---|
| 83 | }
|
---|
| 84 |
|
---|
| 85 | public override double Evaluate(Individual individual, IRandom random) {
|
---|
| 86 | Permutation p = individual.Permutation();
|
---|
| 87 | // Estimation-based evaluation
|
---|
[12261] | 88 | MersenneTwister r = new MersenneTwister();
|
---|
[12191] | 89 | double estimatedSum = 0;
|
---|
[12306] | 90 | for (int i = 0; i < Realizations.Count; i++) {
|
---|
[12261] | 91 | int singleRealization = -1, firstNode = -1;
|
---|
[12306] | 92 | for (int j = 0; j < Realizations[i].Count; j++) {
|
---|
| 93 | if (Realizations[i][p[j]].Value == 1) {
|
---|
[12191] | 94 | if (singleRealization != -1) {
|
---|
| 95 | estimatedSum += DistanceMatrix[singleRealization, p[j]];
|
---|
[12261] | 96 | } else {
|
---|
| 97 | firstNode = p[j];
|
---|
[12191] | 98 | }
|
---|
| 99 | singleRealization = p[j];
|
---|
| 100 | }
|
---|
| 101 | }
|
---|
[12261] | 102 | if (singleRealization != -1) {
|
---|
| 103 | estimatedSum += DistanceMatrix[singleRealization, firstNode];
|
---|
| 104 | }
|
---|
[12191] | 105 | }
|
---|
[12306] | 106 | return estimatedSum / RealizationsSize.Value;
|
---|
[12191] | 107 | }
|
---|
| 108 |
|
---|
[12261] | 109 | public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
|
---|
| 110 | // Estimation-based evaluation
|
---|
| 111 | MersenneTwister r = new MersenneTwister();
|
---|
| 112 | double estimatedSum = 0;
|
---|
| 113 | double[] partialSums = new double[realizations.Count];
|
---|
| 114 | for (int i = 0; i < realizations.Count; i++) {
|
---|
| 115 | partialSums[i] = 0;
|
---|
| 116 | int singleRealization = -1, firstNode = -1;
|
---|
| 117 | for (int j = 0; j < realizations[i].Count; j++) {
|
---|
| 118 | if (realizations[i][individual[j]].Value == 1) {
|
---|
| 119 | if (singleRealization != -1) {
|
---|
| 120 | partialSums[i] += distances[singleRealization, individual[j]];
|
---|
| 121 | } else {
|
---|
| 122 | firstNode = individual[j];
|
---|
| 123 | }
|
---|
| 124 | singleRealization = individual[j];
|
---|
| 125 | }
|
---|
| 126 | }
|
---|
| 127 | if (singleRealization != -1) {
|
---|
| 128 | partialSums[i] += distances[singleRealization, firstNode];
|
---|
| 129 | }
|
---|
| 130 | estimatedSum += partialSums[i];
|
---|
| 131 | }
|
---|
| 132 | double mean = estimatedSum / realizations.Count;
|
---|
| 133 | double variance = 0;
|
---|
| 134 | for (int i = 0; i < realizations.Count; i++) {
|
---|
| 135 | variance += Math.Pow((partialSums[i] - mean), 2);
|
---|
| 136 | }
|
---|
| 137 | variance = variance / realizations.Count;
|
---|
| 138 | return new double[] {mean,variance};
|
---|
| 139 | }
|
---|
| 140 |
|
---|
[12387] | 141 |
|
---|
[12272] | 142 |
|
---|
[12387] | 143 | private void RegisterEventHandlers() {
|
---|
| 144 | //RealizationsSizeParameter.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
|
---|
| 145 | RealizationsSize.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
|
---|
| 146 | //RealizationsSizeParameter.Value.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
|
---|
| 147 | }
|
---|
[12272] | 148 |
|
---|
[12387] | 149 | private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
|
---|
| 150 | UpdateRealizations();
|
---|
[12191] | 151 | }
|
---|
| 152 |
|
---|
[12387] | 153 | private void UpdateRealizations() {
|
---|
[12261] | 154 | MersenneTwister r = new MersenneTwister();
|
---|
| 155 | int countOnes = 0;
|
---|
[12306] | 156 | Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
|
---|
| 157 | for (int i = 0; i < RealizationsSize.Value; i++) {
|
---|
[12261] | 158 | ItemList<IntValue> newRealization = new ItemList<IntValue>();
|
---|
| 159 | while (countOnes < 4) { //only generate realizations with at least 4 cities visited
|
---|
| 160 | countOnes = 0;
|
---|
| 161 | newRealization.Clear();
|
---|
[12387] | 162 | for (int j = 0; j < DistanceMatrix.Rows; j++) {
|
---|
[12261] | 163 | if (ProbabilityMatrix[j] > r.NextDouble()) {
|
---|
| 164 | newRealization.Add(new IntValue(1));
|
---|
| 165 | countOnes++;
|
---|
| 166 | } else {
|
---|
| 167 | newRealization.Add(new IntValue(0));
|
---|
| 168 | }
|
---|
[12219] | 169 | }
|
---|
| 170 | }
|
---|
[12261] | 171 | countOnes = 0;
|
---|
[12306] | 172 | Realizations.Add(newRealization);
|
---|
[12219] | 173 | }
|
---|
[12387] | 174 | }
|
---|
[12228] | 175 |
|
---|
[12387] | 176 | public override void Load(PTSPData data) {
|
---|
| 177 | base.Load(data);
|
---|
| 178 | UpdateRealizations();
|
---|
| 179 |
|
---|
[12380] | 180 | foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
|
---|
[12306] | 181 | op.RealizationsParameter.Value = Realizations;
|
---|
[12219] | 182 | }
|
---|
[12228] | 183 | foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
|
---|
[12306] | 184 | op.RealizationsParameter.Value = Realizations;
|
---|
[12228] | 185 | }
|
---|
[12272] | 186 | foreach (var op in Operators.OfType<PTSP25MoveEvaluator>()) {
|
---|
[12306] | 187 | op.RealizationsParameter.Value = Realizations;
|
---|
[12272] | 188 | }
|
---|
| 189 |
|
---|
[12191] | 190 | }
|
---|
| 191 | }
|
---|
| 192 | } |
---|